An introduction to default logic

Publication date 5 June 1993

Circumscription completeness deduction theorem Default Reasoning first order languages first order proof theory Herbrand theorem Knowledge Representation nonmonotonic reasoning order model theory prenex form theorem semi-decidability soundness undecidability

Mathematics Subject Classification ID

Other nonclassical logic (03B60) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Review text

``The goal of Artificial Intelligence is to understand intelligence well enough to make intelligent computer programs (McCarthy). ``... deductive reasoning is a crucial ingredient of intelligence.... the ability to reason with common sense is indispensable to intelligent agents.... That Tweety can fly is a conclusion which can be drawn from the fact that Tweety is a bird, provided that `there is no evidence that Tweety cannot fly'.... this form of reasoning is called default reasoning. Default reasoning is fundamental in Artificial Intelligence because it appears to be the only tractable method to deal with the problem of incomplete information... (from Chapter 1 of the book). ``This book is written for those who are interested in a formalization of human reasoning, especially in order to build `intelligent' computer systems.... the book places a heavy emphasis on the formal development of default logic, results and problems. (from Preface). Let's have a closer look at the book's contents: Chapter 1: Default Reasoning explains (in a two-page summary) Default Reasoning as being essentially nonmonotonic and qualitative, after having discussed briefly why Artificial Intelligence needs common sense and default reasoning. Chapter 2: Formal Logic as a Knowledge Representation Scheme starts off by discussing the adequacy of formal logic for knowledge representation and then looks into formal logic: Syntactical part (a brief look at the relation) and formal logic: Semantical part (the informal notion of a model) before delving into properties for formal logic (soundness and completeness) and logical languages for knowledge representation (the classical 1st-order one). Chapter 3: First Order Logic defines precisely first order languages (in the usual fashion), then goes into first order model theory (the usual precise definitions of the relation and that of a model) and first order proof theory (the Hilbert-style axiom system) before coming to properties of first order logic (Herbrand theorem, prenex form theorem, deduction theorem, soundness and completeness theorems, undecidability and semi- decidability: all for 1st-order classical logic, without proofs). Chapter 4: Nonmonotonic Extensions for First Order Logic explores very briefly formalizing nonmonotonic reasoning (monotonicity and Gabbay's \(|\)-relation) and retaining the advantages of first order logic (good reasons for nonmonotonic logics as extensions of 1st-order logic). Chapter 5: Presentation of Default Logic gives some examples of default reasoning in detail, viewed as nonmonotonic inference rules. Chapter 6: Formal Development of Default Logic gives basic definitions (defaults, default theories, surface form, the \(\nabla\) relation, the \(\Lambda\) relation, extensions of default theories) before considering general properties of default-theories (N \& S condition for a set of sentences to be an extension of a default theory, for inconsistent extensions, the absorption property, maximality of extensions, a condition for having exactly one extension). Chapter 7: Normal Defaults starts off with existence of extensions (normal defaults, semi-monotonicity, existence of an extension for normal default theories, incompatibility of extensions of a normal default theory) then considers default proof theory (in Hilbert style) and default model theory (à la Lukasiewicz: validity, applicability, admissibility, tability) finishing off with completeness and decidability matters (neither of which holds for normal default logic). Chapter 8: Further topics in default logic goes first into ontology (``... defaults are not just technical devices that perform only inferencing... default theories can be naturally regarded as a special class of axiomatic theories in a nonmonotonic logic, over a suitable modal language) before considering interacting defaults (``... the investigation of which, if any, important form of default reasoning is out of the scope of normal default logic...): syntax-sensitive aspects, unconditional prerequisites, case analysis, semi-normal defaults, taxonomic default theories. Chapter 9: Fragments of Default Logic studies free default theories (sets of defaults with unconditional prerequisites) which can replace, in a sense made precise, default theories, then semi-normal default theories and taxonomic default theories (cf. Chapter 8 for motivation). Chapter 10: Problems with default logic considers defects in fragments of default logic (problems with the semantics of extensions of non normal default theories) and undesirable features of default logic (defects inherent to default logic itself, related to quantification and skolemization). Chapter 11: Default Logic Revisited starts by preliminary discussion (Lukasiewicz's approach to the fact that not all theories of default logic have extensions and that there is no proof theory) then goes on to modified extensions and to Lukasiewicz's proof-theoretic approach to default logic as well as Lukasiewicz's model-theoretic approach to default logic and finally to the belief-justifications pairs setting, finishing with default logic revisisted versus default logic? Chapter 12: Circumscription starts with predicate circumscription (McCarthy's formalization of the Closed World Assumption), goes on to model theory for predicate circumscription (models of circumsription as minimal models) and to existence of minimal models and equality and predicate circumscription before joint predicate circumscription, first order formula circumscription, second order formula circumscription, prioritized formula circumscription and pointwise circumscription. Chapter 13: Other Logic formalizations of Nonmonotonic Reasoning considers nonmonotonic logic I and nonmonotonic logic II (originating with McDermott \& Doyle) before intuitionistic nononotonic logic (à la Gabbay), modal nonmonotonic logic for axiomatic default theories (due to Lukasiewicz), three-valued nonmonotonic logic (Turner's point of view), autoepistemic logic (Moore's approach) and the logic of theory change (as defined by Alchourron, Gardenfors and Makinson), finishing off with a very brief page on logic systems for belief revision. There is a very welcome Appendix: origin of the theorems, a copious list of references, a table of symbols, and a somewhat brief index. On the negative side, the book could have benefited from serious proofreading (numerous gallicisms and some misprints) and alas! from a more pleasant typography; but everybody knows that this is a four-letter word nowadays, especially for editors and wordprocessor vendors. The style suffers sometimes from awkwardness and some gallicisms, but that is the price we pay nowadays for using `English' as a scientific Lingua Franca. The book itself is rather hard reading for a computer scientist, even if specializing in AI, being clearly aimed at a reader kowledgeable in logic. But all these shortcomings are finally minor points versus the fact that the author has given us a very welcome and rather complete overview of a new domain where textbooks are sadly lacking. Moreover there are many examples throughout the book, justifying via intuitive arguments the rather elaborate technical notions introduced. For students and beginning searchers this book is a must.

Recommendations

Cited in

(41)

This page was built for publication: An introduction to default logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4692931)