Translating defeasible theories into CAKE programs

Notation

Let l be a literal of the form P (u) or ¬P (u), where P is a relation symbol and u is a tuple of individual variables and/or constant symbols. We write [l] to denote the expression P^{+} (u) if l is positive and P^{−}(u) otherwise.

For instance, [Q(x, a)] is Q^{+} (x, a), whereas [¬R(x, y)] is R^{−}(x, y).

We start by providing translation of defeasible theories into CAKE programs under the assumption that the considered theories contain neither priorities nor defeaters.

Definition 1 Let D = ⟨F, R, ∅⟩ be a priority-free defeasible theory over a language L_{D} such that R contains no defeater rules. The CAKE program, CR, associated with D is the smallest set of rules defined as follows.^{∗}

1. If l ∈ F, then Δ[l] ∈ CR.

2. If l_{1} ∧ ⋯ ∧ l_{n} → l is a strict rule from R, then (Δ[l_{1}] ∧ ⋯ ∧ Δ[l_{n}] ⇒ Δ[l]) ∈ CR.

3. For each n-ary relation symbol P occurring in the language of the theory D, CR contains the rules ΔP^{+} (x) ⇒ δP^{+} (x) and ΔP^{−}(x) ⇒ δP^{−}(x), where x is an n-tuple of individual variables.

∗Information granules occurring in the CAKE program corresponding to a DL theory will be named by the symbols Δ and δ, the latter possibly with subscripts. To simplify notation, we shall write ΔP^{+} (u), etc. instead of Δ.P^{+} (u), etc.

4. Let P_{1}, … P_{n} be the set of all relation symbols occurring in the heads of strict and defeasible rules from R. For each 1 ≤ i ≤ n:

(a) Suppose that r_{1}^{i}, … r_{k}^{i} is the set of all rules containing P_{i} in their heads. CR contains the following rules: ΔP_{i}^{+} (x) ⇒ δ_{j}P_{i}^{+} (x) and ΔP_{i}^{−}(x) ⇒ δ_{j}P_{i}^{−}(x), for (1 ≤ j ≤ k). For each r_{j}^{i} (1 ≤ j ≤ k) of the form l_{1} ∧ ⋯ ∧ l_{m} ⇒ l (or l_{1} ∧ ⋯ ∧ l_{m} → l), CR contains the rule δ[l_{1}] ∧ ⋯ ∧ δ[l_{m}] ∧ ¬δ_{j}[¬l] ⇒ δ_{j}[l].

(b) In addition, CR contains the following pair of voting rules

k ; ⋁ ; j=1 δ_{j}P_{i}^{+} (x) ∧ k ; ⋀ ; j=1 ¬δ_{j}P_{i}^{−}(x) ⇒ δP_{i}^{+} (x)  (1)

k ; ⋁ ; j=1 δ_{j}P_{i}^{−}(x) ∧ k ; ⋀ ; j=1 ¬δ_{j}P_{i}^{+} (x) ⇒ δP_{i}^{−}(x).  (2)

Remark 1 The points 4(a) and 4(b) can be simplified for those relation symbols from P_{1}, …, P_{n} which occur in the head of exactly one rule. Assume that P_{i} enjoys this property and suppose that P_{i} occurs in the head of the rule of the form l_{1}∧⋯∧l_{m} ⇒ l (or l_{1} ∧ ⋯ ∧ l_{m} → l). In this case, the CAKE rule δ[l_{1}] ∧ ⋯ ∧ δ[l_{m}] ∧ ¬δ_{j}[¬l] ⇒ δ_{j}[l] from point 4(a) can be replaced by δ[l_{1}] ∧ ⋯ ∧ δ[l_{m}] ∧ ¬δ[¬l] ⇒ δ[l] and the voting rules from point 4(b) can be omitted.

Example 1 Consider the defeasible theory D = ⟨F, R, ∅⟩, where^{∗}

F = {Q(n), R(n)} and R = {Q(x) ⇒ P (x), R(x) ⇒ ¬P (x)}.

The CAKE program, Π, corresponding to D is the following.

ΔQ^{+} (n)  (3)
ΔR^{+} (n)  (4)
ΔR^{+} (x) ⇒ δR^{+} (x)  (5)
ΔR^{−}(x) ⇒ δR^{−}(x)  (6)
ΔQ^{+} (x) ⇒ δQ^{+} (x)  (7)
ΔQ^{−}(x) ⇒ δQ^{−}(x)  (8)
ΔP^{+} (x) ⇒ δP^{+} (x)  (9)
ΔP^{−}(x) ⇒ δP^{−}(x)  (10)

∗This is the Nixon diamond theory with n, P, Q, R standing for Nixon, P acifist, Quaker and Republican, respectively.

ΔP^{+} (x) ⇒ δ_{1}P^{+} (x)  (11)
ΔP^{−}(x) ⇒ δ_{1}P^{−}(x)  (12)
ΔP^{+} (x) ⇒ δ_{2}P^{+} (x)  (13)
ΔP^{−}(x) ⇒ δ_{2}P^{−}(x)  (14)
δQ^{+} (x) ∧ ¬δ_{1}P^{−}(x) ⇒ δ_{1}P^{+} (x)  (15)
δR^{+} (x) ∧ ¬δ_{2}P^{+} (x) ⇒ δ_{2}P^{−}(x)  (16)
(δ_{1}P^{+} (x) ∨ δ_{2}P^{+} (x)) ∧ (¬δ_{1}P^{−}(x) ∧
¬δ_{2}P^{−}(x)) ⇒ δP^{+} (x)  (17)
(δ_{1}P^{−}(x) ∨ δ_{2}P^{−}(x)) ∧ (¬δ_{1}P^{+} (x) ∧
¬δ_{2}P^{+} (x)) ⇒ δP^{−}(x).  (18)

The partition Π_{1}={(3)-(14)}, Π_{2}={(15),(16)}, Π_{3}={(17),(18)} provides a stratification of the above set.

The computation of the smallest fixpoint of the operator CS_{Π} is given below.

{ΔQ^{+} (n), ΔR^{+} (n)} {ΔQ^{+} (n), ΔR^{+} (n), δQ^{+} (n), δR^{+} (n)}

{ΔQ^{+} (n), ΔR^{+} (n), δQ^{+} (n), δR^{+} (n), δ_{1}P^{+} (n), δ_{2}P^{−}(n)}  (19)

Observe that according to intuitions neither δP^{+} (n) nor δP^{−}(n) is a member of the set (19).

Defeasible theories with priorities, but without defeater rules.

Definition 2 Let D = ⟨F, R, >⟩ be a defeasible theory such that R contains no defeater rules. The CAKE program associated with D is specified as in Definition 1 with voting rules from point 4(b) replaced by

k ; ⋁ ; j=1 (δ_{j}P_{i}^{+} (x) ∧ k ; ⋀ ; l=1 [δ_{l}P_{i}^{−}(x) ⇒ ^{∗}(r_{j}^{i} > r_{l}^{i})]) ⇒ δP_{i}^{+} (x) (20)
k ; ⋁ ; j=1 (δ_{j}P_{i}^{−}(x) ∧ k ; ⋀ ; l=1 [δ_{l}P_{i}^{+} (x) ⇒ (r_{j}^{i} > r_{l}^{i})]) ⇒ δP_{i}^{−}(x) (21)

∗This ⇒ symbol stands for logical implication and this expression should be evaluated and abbreviated to single C-atom during translation.

Here r_{j}^{i} > r_{l}^{i} evaluates to True or False , depending on whether r_{j}^{i} > r_{l}^{i} holds or not.^{∗}

In the case where the superiority relation > is empty, the rules (20) and (21) are equivalent to the rules (1) and (2), respectively.

∗Note that since the relation > is assumed to be acyclic, r_{j}^{i} > r_{l}^{i} cannot be both True and False .

Example 2 Consider a prioritized version of the theory from Example 1 given by

D = ⟨{Q(n), R(n)}, {r_{1}, r_{2}}, {r_{1} > r_{2}}⟩,

where r_{1} = (Q(x) ⇒ P (x)) and r_{2} = (R(x) ⇒ ¬P (x)). The CAKE program, Π, corresponding to D is as in Example 1 with (17) and (18) replaced by

(δ_{1}P^{+} (x) ∧ (δ_{2}P^{−}(x) ⇒ (r_{1} > r_{2})) ∨ δ_{2}P^{+} (x)∧
(δ_{1}P^{−}(x) ⇒ (r_{2} > r_{1}))) ⇒ δP^{+} (x)  (22)
(δ_{1}P^{−}(x) ∧ (δ_{2}P^{+} (x) ⇒ (r_{1} > r_{2})) ∨ (δ_{2}P^{−}(x)∧
(δ_{1}P^{+} (x) ⇒ (r_{2} > r_{1}))) ⇒ δP^{−}(x)  (23)

respectively.

The set of rules {(3) − (16), (22) − (23)} is stratified by the partition Π_{1} = {(3) − (14)}, Π_{2} = {(15) − (16)}, Π_{3} = {(22) − (23)}. The computation of the smallest fixpoint of the operator CS_{Π} is given below.

{ΔQ^{+} (n), ΔR^{+} (n)} {ΔQ^{+} (n), ΔR^{+} (n), δQ^{+} (n), δR^{+} (n)} {ΔQ^{+} (n), ΔR^{+} (n), δQ^{+} (n), δR^{+} (n), δ_{1}P^{+} (n), δ_{2}P^{−}(n)} {ΔQ^{+} (n), ΔR^{+} (n), δQ^{+} (n), δR^{+} (n), δ_{1}P^{+} (n), δ_{2}P^{−}(n),

δP^{+} (n)}.  (24)

Note that according to intuitions δP^{+} (n) belongs to the set (24).

Arbitrary defeasible theories.

Definition 3 Let D = ⟨F, R, >⟩ be an arbitrary defeasible theory. The CAKE program associated with D is specified as in Definition 1, together with the following modifications and additions.

• Suppose that r_{k+1}^{i} , … r_{k+p}^{i} is the set of all defeater rules containing P_{i} in their heads. For each r_{j}^{i} (k +1 ≤ j ≤ k +p) of the form l_{1} ∧⋯∧l_{m} ⇝ l, the set CR contains the rule δ[l_{1}] ∧ ⋯ ∧ δ[l_{m}] ⇒ d_{j}[l].

• Voting rules from point 4(b) in Definition 1 should be replaced by

k ; ⋁ ; j=1 (δ_{j}P_{i}^{+} (x) ∧ k ; ⋀ ; l=1 [δ_{l}P_{i}^{−}(x) ⇒ (r_{j}^{i} > r_{l}^{i})] ∧

k+p ; ⋀ ; l=k+1 [d_{l}P_{i}^{−}(x) ⇒ (r_{j}^{i} > r_{l}^{i})]) ⇒ δP_{i}^{+} (x)  (25)

k ; ⋁ ; j=1 (δ_{j}P_{i}^{−}(x) ∧ k ; ⋀ ; l=1 [δ_{l}P_{i}^{+} (x) ⇒ (r_{j}^{i} > r_{l}^{i})] ∧

k+p ; ⋀ ; l=k+1 [d_{l}P_{i}^{+} (x) ⇒ (r_{j}^{i} > r_{l}^{i})]) ⇒ δP_{i}^{−}(x).  (26)

Example 3 Consider the theory given by^{∗}

⟨{D(j)}, {D(x) ⇒ A(x), A(x) ⇒ E(x), D(x) ⇝ ¬E(x)}, ∅⟩.

The CAKE program, Π, corresponding to D is the following.

ΔD^{+} (j)  (27)
ΔD^{+} (x) ⇒ δD^{+} (x)  (28)
ΔD^{−}(x) ⇒ δD^{−}(x)  (29)
ΔA^{+} (x) ⇒ δA^{+} (x)  (30)
ΔA^{−}(x) ⇒ δA^{−}(x)  (31)
ΔE^{+} (x) ⇒ δE^{+} (x)  (32)
ΔE^{−}(x) ⇒ δE^{−}(x)  (33)
δD^{+} (x) ⇒ dE^{−}(x)  (34)
δD^{+} (x) ∧ ¬δA^{−}(x) ∧ ¬dA^{−}(x) ⇒ δA^{+} (x)  (35)
δA^{+} (x) ∧ ¬δE^{−}(x) ∧ ¬dE^{−}(x) ⇒ δE^{+} (x).  (36)

∗Here D, A, E and j stand for HighSchoolDropout, Adult, Employed and John, respectively.

Note that the partition Π_{1} = {(27) − (34)}, Π_{2} = {(35) − (36)} provides a stratification of the above set of rules. The computation of the smallest fixpoint of the operator CS_{Π} is given below.

{ΔD(j)}
{ΔD(j), δD(j)}
{ΔD(j), δD(j), dE^{−}(j)}
{ΔD(j), δD(j), dE^{−}(j), δA^{+} (j)}.  (37)

Observe that according to our intuitions δA^{+} (j) is a member of the set (37), but δE^{+} (j) is not.

Remark 2 In general, CAKE programs corresponding to defeasible theories need not be stratified. Consider for instance, the defeasible theory D = ⟨∅, R, ∅⟩, where

R = {⇒ P (a), ⇒ Q(a), ⇒ R(a), P (a) ⇝ ¬Q(a),
Q(a) ⇝ ¬R(a), R(a) ⇝ ¬P (a)}.

The CAKE program corresponding to D is not stratified.

What is derivable in this version of DL?

Definition 4 Let D = ⟨F, R, >⟩ be a defeasible theory and let a stratified program Π be its translation.

A tagged literal +ΔR(u) (resp. +δR(u), +Δ¬R(u), +δ¬R(u)) is derivable from D iff ΔR^{+} (u) (resp. δR^{+} (u), ΔR^{−}(u), δR^{−}(u)) belongs to lfp(CS_{Π}).

A tagged literal −ΔR(u) (resp. −δR(u),−Δ¬R(u), −δ¬R(u)) is derivable from D iff ΔR^{+} (u) (resp. δR^{+} (u), ΔR^{−}(u), δR^{−}(u)) does not belong to lfp(CS_{Π}).

Example 4 Consider the translation Π of the theory D from Example 2.

ΔY 17^{+} (j) ΔA^{+} (x) ⇒ δA^{+} (x) ΔA^{−}(x) ⇒ δA^{−}(x) ΔE^{+} (x) ⇒ δE^{+} (x) ΔE^{−}(x) ⇒ δE^{−}(x) ΔM^{+} (x) ⇒ δM^{+} (x) ΔM^{−}(x) ⇒ δM^{−}(x) ΔM^{+} (x) ⇒ δ_{1}M^{+} (x) ΔM^{−}(x) ⇒ δ_{1}M^{−}(x) ΔM^{+} (x) ⇒ δ_{2}M^{+} (x) ΔM^{−}(x) ⇒ δ_{2}M^{−}(x) ΔY 17^{+} (x) ⇒ δY 17^{+} (x) ΔY 17^{−}(x) ⇒ δY 17^{−}(x) δA^{+} (x) ∧ ¬δE^{−}(x) ⇒ δE^{+} (x) δE^{+} (x) ∧ ¬δA^{−}(x) ⇒ δA^{+} (x) δA^{+} (x) ∧ ¬δ_{1}M^{−}(x) ⇒ δ_{1}M^{+} (x) δY 17^{+} (x) ∧ ¬δ_{2}M^{+} (x) ⇒ δ_{2}M^{−}(x) δ_{1}M^{−}(x) ∧ ¬δ_{2}M^{+} (x) ⇒ δM^{−}(x) δ_{1}M^{+} (x) ∧ ¬δ_{2}M^{−}(x) ⇒ δM^{+} (x) δ_{2}M^{−}(x) ∧ ¬δ_{1}M^{+} (x) ⇒ δM^{−}(x) δ_{2}M^{+} (x) ∧ ¬δ_{1}M^{−}(x) ⇒ δM^{+} (x)

The computation of the smallest fixpoint of the operator CS_{Π} is given below.

{ΔY 17(j)} {ΔY 17(j), δY 17(j)}

{ΔY 17(j), δY 17(j), δM^{−}(j)}  (38)

Note that according to our intuitions, δM^{−}(j) is derivable from D.

Now, we apply well-founded semantics to two non-stratified defeasible theories.

Example 5 Consider the defeasible theory D = ⟨∅, R, ∅⟩, where

R = {⇒ P (a), ⇒ Q(a), ⇒ R(a), P (a) ⇝ ¬Q(a),
Q(a) ⇝ ¬R(a), R(a) ⇝ ¬P (a)}.

The CAKE program Π, corresponding to D is the following.

ΔP^{+} (a) ⇒ δP^{+} (a) ΔQ^{+} (a) ⇒ δQ^{+} (a) ΔR^{+} (a) ⇒ δR^{+} (a) ΔP^{−}(a) ⇒ δP^{−}(a) ΔQ^{−}(a) ⇒ δQ^{−}(a) ΔR^{−}(a) ⇒ δR^{−}(a) ¬δP^{−}(a) ∧ ¬dP^{−}(a) ⇒ δP^{+} (a) ¬δQ^{−}(a) ∧ ¬dQ^{−}(a) ⇒ δQ^{+} (a) ¬δR^{−}(a) ∧ ¬dR^{−}(a) ⇒ δR^{+} (a) δP^{+} (a) ⇒ dQ^{−}(a) δQ^{+} (a) ⇒ dR^{−}(a) δR^{+} (a) ⇒ dP^{−}(a)

The program Π is not stratified. We now compute the wellfounded model of Π. We start with

S_{0} = ⊥ = {¬ΔP^{+} (a), ¬ΔQ^{+} (a), ¬ΔR^{+} (a), ¬ΔP^{−}(a), ¬ΔQ^{−}(a),

¬ΔR^{−}(a), ¬δP^{+} (a), ¬δQ^{+} (a), ¬δR^{+} (a), ¬δP^{−}(a), ¬δQ^{−}(a), ¬δR^{−}(a), ¬dP^{−}(a), ¬dQ^{−}(a), ¬dR^{−}(a)}.

By applying 3-CS _{Π} operator, we obtain the following sequence of interpretations.

S_{1} = {¬ΔP^{+} (a), ¬ΔQ^{+} (a), ¬ΔR^{+} (a), ¬ΔP^{−}(a), ¬ΔQ^{−}(a),

¬ΔR^{−}(a), δP^{+} (a), δQ^{+} (a), δR^{+} (a), ¬δP^{−}(a), ¬δQ^{−}(a),

¬δR^{−}(a), dP^{−}(a), dQ^{−}(a), dR^{−}(a)}
S_{2} = S_{0}
S_{3} = S_{1}.

Thus S_{∗} = S_{3} and S^{∗} = S_{2}. In consequence,

S _{∗}^{∗} = {¬ΔP^{+} (a), ¬ΔQ^{+} (a), ¬ΔR^{+} (a), ¬ΔP^{−}(a),

¬ΔQ^{−}(a), ¬ΔR^{−}(a), ¬δP^{−}(a), ¬δQ^{−}(a), ¬δR^{−}(a)}.

Example 6 Consider the defeasible theory D = ⟨F, R, ∅⟩, where F = {Q(a)} and R = {Q(x) ⇒ P (x), R(x) ⇒ ¬P (x), P (x) ⇒ Q(x), S(x) ⇒ ¬Q(x)}.

The ground CAKE program Π corresponding to D is the following.

ΔQ^{+} (a)
ΔQ^{+} (a) ⇒ δQ^{+} (a)
ΔQ^{−}(a) ⇒ δQ^{−}(a)
ΔP^{+} (a) ⇒ δP^{+} (a)
ΔP^{−}(a) ⇒ δP^{−}(a)
ΔR^{+} (a) ⇒ δR^{+} (a)
ΔR^{−}(a) ⇒ δR^{−}(a)

ΔS^{+} (a) ⇒ δS^{+} (a) ΔS^{−}(a) ⇒ δS^{−}(a) ΔP^{+} (a) ⇒ δ_{1}P^{+} (a) ΔP^{−}(a) ⇒ δ_{1}P^{−}(a) ΔP^{+} (a) ⇒ δ_{2}P^{+} (a) ΔP^{−}(a) ⇒ δ_{2}P^{−}(a) ΔQ^{+} (a) ⇒ δ_{1}Q^{+} (a) ΔQ^{−}(a) ⇒ δ_{1}Q^{−}(a) ΔQ^{+} (a) ⇒ δ_{2}Q^{+} (a) ΔQ^{−}(a) ⇒ δ_{2}Q^{−}(a) δQ^{+} (a) ∧ ¬δ_{1}P^{−}(a) ⇒ δ_{1}P^{+} (a) δR^{+} (a) ∧ ¬δ_{2}P^{+} (a) ⇒ δ_{2}P^{−}(a) δP^{+} (a) ∧ ¬δ_{1}Q^{−}(a) ⇒ δ_{1}Q^{+} (a) δS^{+} (a) ∧ ¬δ_{2}Q^{+} (a) ⇒ δ_{2}Q^{−}(a) (δ_{1}P^{+} (a) ∨ δ_{2}P^{+} (a)) ∧ (¬δ_{1}P^{−}(a) ∧ ¬δ_{2}P^{−}(a)) ⇒ δP^{+} (a) (δ_{1}P^{−}(a) ∨ δ_{2}P^{−}(a)) ∧ (¬δ_{1}P^{+} (a) ∧ ¬δ_{2}P^{+} (a)) ⇒ δP^{−}(a) (δ_{1}Q^{+} (a) ∨ δ_{2}Q^{+} (a)) ∧ (¬δ_{1}Q^{−}(a) ∧ ¬δ_{2}Q^{−}(a)) ⇒ δQ^{+} (a) (δ_{1}Q^{−}(a) ∨ δ_{2}Q^{−}(a)) ∧ (¬δ_{1}Q^{+} (a) ∧ ¬δ_{2}Q^{+} (a)) ⇒ δQ^{−}(a).

The program Π is not stratified. We now compute the wellfounded model of Π.

S_{0} = ⊥ = {¬ΔQ^{+} (a), ¬ΔP^{+} (a), ¬ΔR^{+} (a), ¬ΔS^{+} (a), ¬ΔQ^{−}(a),

¬ΔP^{−}(a), ¬ΔR^{−}(a), ¬ΔS^{−}(a), ¬δQ^{+} (a), ¬δP^{+} (a), ¬δR^{+} (a), ¬δS^{+} (a), ¬δQ^{−}(a), ¬δP^{−}(a), ¬δR^{−}(a), ¬δS^{−}(a), ¬δ_{1}P^{+} (a), ¬δ_{1}P^{−}(a), ¬δ_{2}P^{+} (a), ¬δ_{2}P^{−}(a), ¬δ_{1}Q^{+} (a),

¬δ_{1}Q^{−}(a), ¬δ_{2}Q^{+} (a), ¬δ_{2}Q^{−}(a)}.

Applying 3-CS _{Π} operator, we obtain the following sequence of interpretations.

S_{1} = {ΔQ^{+} (a), ¬ΔP^{+} (a), ¬ΔR^{+} (a), ¬ΔS^{+} (a), ¬ΔQ^{−}(a),

¬ΔP^{−}(a), ¬ΔR^{−}(a), ¬ΔS^{−}(a), δQ^{+} (a), δP^{+} (a), ¬δR^{+} (a), ¬δS^{+} (a), ¬δQ^{−}(a), ¬δP^{−}(a), ¬δR^{−}(a), ¬δS^{−}(a), δ_{1}P^{+} (a), ¬δ_{1}P^{−}(a), ¬δ_{2}P^{+} (a), ¬δ_{2}P^{−}(a), δ_{1}Q^{+} (a), ¬δ_{1}Q^{−}(a),

δ_{2}Q^{+} (a), ¬δ_{2}Q^{−}(a)}.
S_{2} = S_{1}.

Hence, S^{∗} = S_{∗} = S_{1} and thus S _{∗}^{∗} is given by

{ΔQ^{+} (a), ¬ΔP^{+} (a), ¬ΔR^{+} (a), ¬ΔS^{+} (a), ¬ΔQ^{−}(a), ¬ΔP^{−}(a), ¬ΔR^{−}(a), ¬ΔS^{−}(a), δQ^{+} (a), δP^{+} (a), ¬δR^{+} (a), ¬δS^{+} (a), ¬δQ^{−}(a), ¬δP^{−}(a), ¬δR^{−}(a), ¬δS^{−}(a), δ_{1}P^{+} (a), ¬δ_{1}P^{−}(a), ¬δ_{2}P^{+} (a), ¬δ_{2}P^{−}(a), δ_{1}Q^{+} (a), ¬δ_{1}Q^{−}(a), δ_{2}Q^{+} (a), ¬δ_{2}Q^{−}(a)}.

Note that the above interpretation agrees with our intuitions.