FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 |

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

-- [ Page 1 ] --

Propositional Clausal Defeasible Logic

David Billington

School of ICT, Nathan campus, Griffith University,

Brisbane, Queensland 4111, Australia.


Abstract. Defeasible logics are non-monotonic reasoning systems that

have efficient implementations and practical applications. We list several

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

of these properties. We define 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, Artificial intelligence.

1 Introduction Non-monotonic reasoning systems represent and reason with incomplete infor- mation where the degree of incompleteness is not quantified. 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 sufficient 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 nullified 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]. (Different formal definitions of “accepted”, “evidence against”, and “nullified” have been used by different 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 different intuitions about what should follow from a reasoning situation.

A key feature of these defeasible logics is that they all have efficient 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 identification [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 efficiently 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 define 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 definitions 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 first 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 different 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 conflict property iff the logic recognises that two defeasible rules, r1 and r2, conflict 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 conflict property will recognise that {a} ⇒ ¬c and {b} ⇒ ¬d conflict.

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 nullified 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 nullified and so we conclude c. No previous defeasible logic does this.

A logic has a linear proof hierarchy iff 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 finite 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 first 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 different degrees of confidence 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 flaws 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 define 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 “finite-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 nullified 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 fly.” is represented by {sick (x), bird (x)} ; ¬fly(x). The idea is that a bird being sick is not sufficient evidence to conclude that it usually does not fly; it is only evidence against the conclusion that it usually flies.

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)} ⇒ fly(x) [Birds usually fly.] r2 : {quail (x)} ⇒ ¬fly(x) [Quails usually do not fly.] Since r2 is more specific 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 finite number of steps, 0 means that the proof got into a loop which was detected in a finite number of steps, and −1 means that in a finite 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 finite 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.

–  –  –

Definition 3. (rule). A rule, r, is a triple (A(r), arrow(r), c(r)), where A(r) is a finite 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).

–  –  –

Pages:   || 2 |

Similar works:

«Bitter Coffee: How the Poor are Paying for the Slump in Coffee Prices Author: Celine Charveriat May 2001 Bitter Coffee: How the Poor are Paying for the Slump in Coffee Prices Embargoed until 16 May at 9.00 a.m. ‘The coffee market cannot sacrifice millions of poor farmers. Nobody should forget that it is precisely these poor farmers who, with their hard work, have fostered not only the growth of their sector, but the wealth of the world coffee industry.’ Jorge Cardenas, President of...»

«Graduate School of Asia-Pacific Studies Waseda University Doctoral Thesis Media coverage in the context of Education for Sustainable Development: Climate change in Thailand’s newspapers Jessada Salathong ACKNOWLEDGMENTS First of all, I would like to express my great gratitude to Prof. Kazuo Kuroda, my advisor and mentor. With his kindness and support from the beginning of my study at Waseda University, I could achieve my academic goal and gained a lot of precious opportunities. I am also very...»

«The Antichrist by Arthur W. Pink About The Antichrist by Arthur W. Pink Title: The Antichrist URL: http://www.ccel.org/ccel/pink/antichrist.html Author(s): Pink, Arthur W. Publisher: Grand Rapids, MI: Christian Classics Ethereal Library Source: Logos Research Systems, Inc. Rights: Public Domain Contributor(s): Steve Liguori (Converter) CCEL Subjects: All; LC Call no: BT985.P5 LC Subjects: Doctrinal theology Invisible world (saints, demons, etc.) The Antichrist Arthur W. Pink Table of Contents...»

«Robert Kauzlaric www.robertkauzlaric.com, rob@robertkauzlaric.com Playwriting – Theatrical Adaptations The Island of Dr. Moreau (2007) Based on the novel by H.G. Wells Published by Playscripts, Inc. Commissioned by: Lifeline Theatre (Chicago, IL); premiered October 2007. Produced by: Mulvane High School (Mulvane, KS); Spanish River Community High School (Boca Raton, FL); T.C Williams High School (Alexandria, VA); The Theatre Lab School of the Dramatic Arts (Washington, DC);. The Picture of...»

«TFM Trabajo Fin de Master Título: EL DIBUJO Y LA TINTA EN LA CREACIÓN DEL VIDEO MUSICAL Autor/a: Chih Ju Huang Tutor/a: Jesús Pertiñez López Línea de Investigación en la que se encuadra el TFM: Audiovisual Departamento de Dibujo Convocatoria: Junio Año: 2013 1 TFM Trabajo Fin de Master Título: EL DIBUJO Y LA TINTA EN LA CREACIÓN DEL VIDEO MUSICAL Autor/a: Chih Ju Huang Tutor/a: Jesús Pertiñez López Línea de Investigación en la que se encuadra el TFM: Audiovisual Departamento de...»

«University of Nevada Reno A Generic Queuing System and Time-Saving Region Restrictions for Calculating the Crossing Number of Kn A thesis submitted in partial fulfillment of the requirements for the degree of Master of Science with a major in Computer Science. by Bei Yuan Dr. Frederick C. Harris, Jr., Thesis advisor December 2004 We recommend that the thesis prepared under our supervision by BEI YUAN entitled A Generic Queuing System and Time-Saving Region Restrictions for Calculating the...»

«STROUD DISTRICT COUNCIL AGENDA ITEM NO Audit Committee 9 7 January 2010 Report Title INTERNAL AUDIT CHARTER Purpose of Report To present to members for their consideration and approval the Internal Audit Charter. This document is an important element in providing the required independent and objective opinion to the organisation on the adequacy of the control environment. Decision(s) Members approve the Internal Audit Charter as detailed in Appendix A. Consultation and Not applicable Feedback...»

«Textual and Quantitative Analysis: Towards a new, e-mediated Social Science Khurshid Ahmad, Lee Gillam, and David Cheng Centre for Knowledge Management, Department of Computing, University of Surrey, Guildford, Surrey. UNITED KINGDOM [k.ahmad, l.gillam, d.cheng}@surrey.ac.uk Introduction The analysis of large volumes of quantitative data in social sciences has a long tradition: mathematical modelling and statistical analysis can now be performed on large, distributed data sets and the results...»

«© Journal of Language and Literature, ISSN: 2078-0303, Vol. 5. No. 3. 2014 Arkady P. Sedykh, Larisa R. Ermakova. Gluttonic nomination in Russian and British linguistic cultures. Journal of Language and Literature 2014; 5(3), 338-342. DOI: 10.7813/jll.2014/5-3/57 GLUTTONIC NOMINATION IN RUSSIAN AND BRITISH LINGUISTIC CULTURES Arkady Petrovich Sedykh, Larisa Robertovna Ermakova Federal State Autonomous Educational Institution of Higher Professional Education “The Belgorod State National...»

«Melanesian Journal of Theology 24-2 (2008) A CRITIQUE OF OPEN THEISTS’ ATONEMENT VIEWS WITHIN THE CONTEXT OF MISSION THEOLOGY Doug Hanson Doug lectures at the Christian Leaders’ Training College in Papua New Guinea. He holds a Master of Theology degree from the Capital Bible Seminary in the USA. This article is an adaptation of his master’s thesis. INTRODUCTION The close of the 20th century saw the rise of the theological movement called Open Theism.1 With the publication of The Openness...»

«Foster Manual Thank you for participating in our greyhound-fostering program. Fostering is the heart and soul of our organization and is a unique and rewarding way to make a difference in a retired racing greyhound’s life. Through fostering, you will touch the lives of so many greyhounds, and in return, they will touch yours. Fostering helps make the transition into their “forever home” a smooth and safe one. Up until the time of retirement, these wonderful athletes have spent their lives...»

«T: +39 02 580021 W: www.cardiologicomonzino.it Area Imaging Cardiovascolare Coordinatore: Dr Mauro Pepi Risonanza Magnetica Responsabile: Dr Gianluca Pontone Istituto di Ricovero e Cura a Carattere Scientifico S: +39 – 02 58002003 (h 9.00 – 15.00) Via Carlo Parea, 4 20138 Milano T: +39 – 02 – 58002449/2452 F: + 39 – 02 58002231 Egregio Signore, Gentile Signora, in allegato alla presente, Le consegniamo la seguente documentazione: 1. Consenso Informato all’esecuzione di esame di...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.