# «Abstract. Defeasible logics are non-monotonic reasoning systems that have eﬃcient implementations and practical applications. We list several ...»

Propositional Clausal Defeasible Logic

David Billington

School of ICT, Nathan campus, Griﬃth University,

Brisbane, Queensland 4111, Australia.

d.billington@griffith.edu.au

Abstract. Defeasible logics are non-monotonic reasoning systems that

have eﬃcient implementations and practical applications. We list several

desirable properties and note that each defeasible logic fails to have some

of these properties. We deﬁne and explain a new defeasible logic, called

clausal defeasible logic (CDL), which has all these properties. CDL is easy to implement, consistent, detects loops, terminates, and has a range of deduction algorithms to cater for a range of intuitions.

Keywords: Defeasible logic, Non-monotonic reasoning, Knowledge rep- resentation and reasoning, Artiﬁcial intelligence.

1 Introduction Non-monotonic reasoning systems represent and reason with incomplete infor- mation where the degree of incompleteness is not quantiﬁed. A very simple and natural way to represent such incomplete information is with a defeasible rule of the form “antecedent ⇒ consequent”; with the meaning that provided there is no evidence against the consequent, the antecedent is suﬃcient evidence for concluding the consequent. Creating such rules is made easier for the knowl- edge engineer as each rule need only be considered in isolation. The interaction between the rules is the concern of the logic designer.

Reiter’s normal defaults [24] have this form, with the meaning that if the an- tecedent is accepted and the consequent is consistent with our knowledge so far then accept the consequent. Of course the consequent could be consistent with current knowledge and yet there be evidence against the consequent. This results in multiple extensions. However multiple extensions are avoided by interpreting a defeasible rule as “if the antecedent is accepted and all the evidence against the consequent has been nulliﬁed then accept the consequent”. This interpre- tation forms the foundation of a family of non-monotonic logics all based on Nute’s original defeasible logic [22]. (Diﬀerent formal deﬁnitions of “accepted”, “evidence against”, and “nulliﬁed” have been used by diﬀerent defeasible logics.) Unlike other non-monotonic reasoning systems, these defeasible logics use Nute’s very simple and natural “defeasible arrow” to represent incomplete in- formation. This simplicity and naturalness is important when explaining an im- plementation to a client. All defeasible logics have a priority relation on rules.

Although preferences between rules can be simulated by more complex rules, this is not so natural or simple. Defeasible logics use classical negation rather than negation-as-failure, and have a type of rule which warns that a conclusion, c, is too risky but does not support the negation of c. Many defeasible logics cater for diﬀerent intuitions about what should follow from a reasoning situation.

A key feature of these defeasible logics is that they all have eﬃcient easily implementable deduction algorithms (see [8, 20, 23] for details). Indeed defeasible logics have been used in an expert system, for learning and planning [23], in a robotic dog which plays soccer [9, 10], and to improve the accuracy of radio frequency identiﬁcation [11]. Defeasible logics have been advocated for various applications including modelling regulations and business rules [3], agent negotiations [13], the semantic web [1, 4], modelling agents [16], modelling intentions [15], modelling dynamic resource allocation [17], modelling contracts [12], legal reasoning [18], modelling deadlines [14], and modelling dialogue games [25].

Moreover, defeasible theories, describing policies of business activities, can be mined eﬃciently from appropriate datasets [19].

The unique features and diverse range of practical applications show that defeasible logics are useful and their language is important for knowledge representation and reasoning. Using defeasible logic as the inference engine in an expert system is obvious. But it is less obvious to use defeasible logic to deal with the error-prone output of sensors (possibly in a robot), because this can be done using classical logic. The advantages of using defeasible logic are that the system can be developed incrementally, there are fewer rules, and the rules are simpler [9–11].

In this paper we shall deﬁne a new defeasible logic, called clausal defeasible logic (CDL), explain how it works, and show why it is needed.

The rest of the paper has the following organisation. Section 2 shows why CDL is needed. Section 3 gives an overview of CDL. The formal deﬁnitions of CDL are in Sections 4 and 5. An explanation of the proof algorithms concludes Section 5. An example is considered in Section 6. Section 7 contains results that show CDL is well-behaved. A summary forms Section 8.

**2 Why Clausal Defeasible Logic is Needed**

There are three classes of defeasible logic: the twin logics NDL and ADL [21] and their variants; the logic DL93 [5] and its variants; and plausible logic [8] and its later developments. Table 1 compares CDL and representatives from the three classes by noting which properties hold. From the ﬁrst class we choose NDL and ADL, from the second class we choose DL93, and from the third class we choose the latest plausible logic PL05 [7].

There are two well-informed but diﬀerent intuitions about what follows from the defeasible theory Ambig = {r1 : {} ⇒ b, r2 : {} ⇒ a, r3 : {} ⇒ ¬a, r4 : {a} ⇒ ¬b}. Rule r1 says there is evidence for b; r2 says there is evidence for a; r3 says there is evidence for not a; and r4 says that a is evidence for not b. All rules have the same reliability or strength. Because there is equal evidence for and against a, we say a is ambiguous. The ambiguity blocking intuition says that since a is not accepted, r4 cannot be used and so b should be accepted because of Table 1. Logics and their Properties

r1. The ambiguity propagating intuition says that although r4 has been weakened by the ambiguity of a, it has not been weakened enough to ignore r4. So r1 is evidence for b and r4 is still evidence against b. Thus b should also be ambiguous, that is the ambiguity of a has been propagated along r4 to b.

Defeasible logics deal with factual, as well as defeasible, information. A defeasible logic has the general conﬂict property iﬀ the logic recognises that two defeasible rules, r1 and r2, conﬂict whenever the factual information means that the consequents of r1 and r2 cannot both hold. For example if c ∨ d is a fact then only a logic with the general conﬂict property will recognise that {a} ⇒ ¬c and {b} ⇒ ¬d conﬂict.

Only plausible logics can prove disjunctions of literals.

Suppose there is a team of rules supporting a and a team of rules supporting ¬a, and there is a priority between rules. If there is a rule supporting a that is superior to all the rules supporting ¬a then clearly a should be concluded. This is what NDL and ADL do. But more intuitive results can be obtained if the following team defeat property is used. If every rule supporting ¬a is inferior to some rule supporting a then conclude a.

To illustrate failure-by-looping consider the following example of a positive loop. {rc : {} ⇒ c, rab : {a} ⇒ b, rba : {b} ⇒ a, rac : {a} ⇒ ¬c}. Rule rc is evidence for c, and rac is evidence against c. But a cannot be proved because rab and rba form a positive loop. Hence the evidence against c has been nulliﬁed and so we conclude c. This is what NDL and ADL do.

The following is an example of a negative loop. NegLoop = {ra : {} ⇒ a, rb : {} ⇒ b, rc : {} ⇒ c, rab : {a} ⇒ ¬b, rba : {b} ⇒ ¬a, rac : {a} ⇒ ¬c}.

Again rc is evidence for c, and rac is evidence against c. But a cannot be proved because rab and rba form a negative loop. Hence the evidence against c has been nulliﬁed and so we conclude c. No previous defeasible logic does this.

A logic has a linear proof hierarchy iﬀ for any two of its proof algorithms, whatever can be proved by one can be proved by the other or vice versa. For NDL and ADL this means that NDL can prove whatever ADL can prove.

Defeasible logics are designed to be implemented on a computer, and so it would be tidy if their deduction algorithms always terminated. The algorithms used in DL93, NDL, and ADL do not terminate when trying to prove c in the NegLoop example.

To nullify evidence defeasible logics have to be able to disprove formulas.

This means that they can demonstrate in a ﬁnite number of steps that there is no proof of the formula. (It does not mean that the negation of the formula can be proved.) It would be nice if every formula could be proved or disproved, called decisiveness in [6]. Unfortunately there are examples that show that decisiveness leads to undesirable results [6]. Weak decisiveness means that every formula can be proved, or disproved, or the attempted proof gets into a loop. If such a loop is detected then the proof can be terminated, otherwise the deduction algorithm does not terminate.

For each of the ﬁrst 6 properties in Table 1, a logic which has this property will give more intuitive results than a logic which does not have the property.

Having a linear proof hierarchy is important because then one does not have to decide which proof algorithm to use. Always use the strongest (most reliable) algorithm. If it succeeds then the weaker algorithms will succeed too. If it fails then use the next weakest (less reliable) algorithm. So diﬀerent degrees of conﬁdence in a proved result can be achieved without using numbers such as probabilities or certainty factors. Ambiguity propagation gives more reliable results, but proves less, than ambiguity blocking. Moreover a range of ambiguity propagating algorithms can be formed giving a range of reliabilities.

Since CDL is based on PL05 we shall consider the ﬂaws of PL05 more closely.

The ambiguity propagating algorithm of PL05 is too strong. Its nullifying subalgorithm is too weak, which makes PL05 fail to have a linear proof hierarchy.

We deﬁne two totally new ambiguity propagating algorithms based on ideas exhibited in a variant of DL93 [2].

PL05 detects all loops, but it only uses this information to terminate loops.

NDL and ADL do not really detect loops, they just use some loops in their failure-by-looping method. If all loops were used in a failure-by-looping method then the logic would be decisive; which, as noted above, leads to undesirable results. CDL determines which loops are usable and which are not. Every loop used by NDL and ADL is regarded as usable by CDL. Moreover CDL gets the desired answer for the NegLoop example, see Section 6.

**3 Overview of Clausal Defeasible Logic (CDL)**

CDL reasons with both factual and plausible information, which is represented by strict rules, defeasible rules, warning rules, and a priority relation,, on the rules. All rules have the form “ﬁnite-set-of-literals arrow literal”.

Strict rules, for example A → l, represent the aspects of a situation that are certain. If all the literals in A are proved then l can be deduced, no matter what the evidence against l is.

Defeasible rules, for example A ⇒ l, mean that if all the literals in A are proved and all the evidence against l has been nulliﬁed then l can be deduced.

Warning rules, for example A ; ¬l, warn against concluding usually l, but do not support usually ¬l. For example, “Sick birds might not ﬂy.” is represented by {sick (x), bird (x)} ; ¬ﬂy(x). The idea is that a bird being sick is not suﬃcient evidence to conclude that it usually does not ﬂy; it is only evidence against the conclusion that it usually ﬂies.

The priority relation,, on the set of non-strict rules allows the representation of preferences among non-strict rules. The priority relation must be acyclic, but does not have to be transitive. Consider the following two rules.

r1 : {bird (x)} ⇒ ﬂy(x) [Birds usually ﬂy.] r2 : {quail (x)} ⇒ ¬ﬂy(x) [Quails usually do not ﬂy.] Since r2 is more speciﬁc than r1 we want r2 r1, meaning that r2 is preferred over r1.

CDL has six proof algorithms. The µ algorithm is monotonic and uses only strict rules. CDL restricted to µ is essentially classical propositional logic. The ambiguity blocking algorithm is denoted by β. There are two ambiguity propagating algorithms denoted by ρ and π, ρ being more reliable than π. Algorithm ρ requires the co-algorithm ι, which only considers supporting evidence for a formula and ignores all contrary evidence. Algorithm π requires the co-algorithm ε, which sees if there is unbeaten evidence for a formula. Let λ be either ρ or π and λ be its required co-algorithm. Then the more λ can prove the less λ can prove. So by changing λ we can make λ more reliable and closer to µ, or less reliable and closer to β.

The task of proving a formula is done by a recursive proof function P. The input to P is the proof algorithm to be used, the formula to be proved, and the background. The background is an initially empty storage bin into which is put all the literals that are currently being proved as P recursively calls itself. The purpose of this background is to detect loops. The output of P is one of the following proof-values +1, 0, or −1. The +1 means that the formula is proved in a ﬁnite number of steps, 0 means that the proof got into a loop which was detected in a ﬁnite number of steps, and −1 means that in a ﬁnite number of steps it has been demonstrated that there is no proof of the formula and that this demonstration does not get into a loop.

Some proofs use the ﬁnite failure of other proofs. Proofs with a proof-value of −1 are always usable. Moreover CDL determines which proofs with a proof-value of 0 are usable and which are not.

Deﬁnition 3. (rule). A rule, r, is a triple (A(r), arrow(r), c(r)), where A(r) is a ﬁnite set of literals called the set of antecedents of r, arrow(r) ∈ {→, ⇒, ;}, and c(r) is a literal called the consequent of r.

Strict rules use the strict arrow, →, and are written A(r) → c(r).

Defeasible rules use the defeasible arrow, ⇒, and are written A(r) ⇒ c(r).

Warning rules use the warning arrow, ;, and are written A(r) ; c(r).