next up previous
Next: Other logical systems Up: System Specification Previous: Temporal logic

Defeasible logic

The next cluster of logical systems we discuss fall under defeasible logic (or revisable, or nonmonotonic, tex2html_wrap_inline1275 logic), an area that has for a long while justifiably received the attention of many LAIniks. Such systems mark attempts to circumvent monotonicity, a property that, put in terms of tex2html_wrap_inline773 tex2html_wrap_inline775 , amounts to the fact that if tex2html_wrap_inline791 is provable from tex2html_wrap_inline797 , then adding new information to tex2html_wrap_inline797 , no matter what that information is, never invalidates tex2html_wrap_inline807 . Clearly, our everyday reasoning isn't monotonic. Nearly all readers, for example, will at one time or another have affirmed the proposition that birds can fly. Expressed in straight first-order logic, this fact could be captured by


But such readers will also have confronted the fact that ostriches can't fly. Clearly, there is a need to revise what had earlier been believed. But, just as clearly, it's very implausible that humans, in everyday reasoning, employ modifications of (4) like


because, for starters, there are an infinite number of exceptions to (4). The solution, in general, would seem to be that we use a system that allows us to make defeasible or revisable inferences. The challenge is to find and implement a correlate to this system.

There are a number of different families of attacks on the revisable reasoning challenge, among which are the following.

Chapter 5 of Thayse 1989, ``Formalization of Revisable Reasoning'', provides what is in our opinion one of the best introductions anywhere to minimization techniques. The treatment explains the intuitions behind minimization techniques and then proceeds to formalize the approach, gradually moving from the simplest incarnation of minimization techniques to circumscription.

Though Drew McDermott once claimed that only two people on the planet understood circumscription, the basic idea behind the technique, as Thayse 1989 shows, is really quite simple: Suppose some agent has knowledge represented by a set tex2html_wrap_inline797 of formulas in tex2html_wrap_inline773 tex2html_wrap_inline775 . We partition the relation symbols, or predicates, deployed in tex2html_wrap_inline797 into three sets, tex2html_wrap_inline1299 tex2html_wrap_inline1301 , tex2html_wrap_inline1299 tex2html_wrap_inline1305 , and tex2html_wrap_inline1299 tex2html_wrap_inline1309 . The predicates in tex2html_wrap_inline1299 tex2html_wrap_inline1301 contain those to be circumscribed, or ``minimized''; the predicates in tex2html_wrap_inline1299 tex2html_wrap_inline1305 are the ones whose extensions (= the things in the domain picked out by the predicates) are permitted to change during the circumscription process; and tex2html_wrap_inline1299 tex2html_wrap_inline1309 holds all remaining predicates. Now, let tex2html_wrap_inline809 tex2html_wrap_inline1301 and tex2html_wrap_inline809 tex2html_wrap_inline1305 be two interpretations that model tex2html_wrap_inline797 . (An interpretation tex2html_wrap_inline809 models a set of formulas tex2html_wrap_inline797 just in case it models every formula in the set.) tex2html_wrap_inline809 tex2html_wrap_inline1301 is said to be inferior to tex2html_wrap_inline809 tex2html_wrap_inline1305 exactly when the following three conditions are satisfied:

  1. tex2html_wrap_inline809 tex2html_wrap_inline1301 and tex2html_wrap_inline809 tex2html_wrap_inline1305 have the same domain and interpret function symbols and variables in exactly the same way.
  2. tex2html_wrap_inline809 tex2html_wrap_inline1301 and tex2html_wrap_inline809 tex2html_wrap_inline1305 interpret the predicates in tex2html_wrap_inline1299 tex2html_wrap_inline1309 in exactly the same way.
  3. For every predicate R in the set tex2html_wrap_inline1299 tex2html_wrap_inline1301 of circumscribed predicates, the extension of R in tex2html_wrap_inline809 tex2html_wrap_inline1301 is a subset of the extension of R in tex2html_wrap_inline809 tex2html_wrap_inline1305 .

These three conditions can be understood intuitively as follows: The two interpretations in question, as it is said in Thayse 1989, interpret our agents knowledge, tex2html_wrap_inline797 , ``almost identically''. But interpretation tex2html_wrap_inline809 tex2html_wrap_inline1301 interprets the predicates in tex2html_wrap_inline1299 tex2html_wrap_inline1301 as true ``less often'' than interpretation tex2html_wrap_inline809 tex2html_wrap_inline1305 does. The key interpretations are those that model tex2html_wrap_inline797 and are minimal with respect to the ordering relation produced by these three conditions. A formula can be inferred from a circumscribed knowledge base when it is true in all minimal models. The hope is that the formulas that can be inferred will be precisely those that are desirable in cases like the ostrich one we presented above. Thayse 1989 shows, in fact, that


can be deduced in the ostrich example. The demonstration follows the traditional proof-theoretic route through circumscription: It's shown that if a certain second-order formula tex2html_wrap_inline1401 , (i.e., a formula from the logical system tex2html_wrap_inline773 tex2html_wrap_inline889 described at the outset of this paper) is added to the knowledge in this case, the desired deduction can be performed. Thayse 1989 then explain the problems plaguing circumscription, at least in its traditional form (e.g., partitioning the predicates seems to require knowledge of the desired outcome).

Readers who assimilate the material we presented earlier in §2 and then the presentation of circumscription in Thayse 1989 will be able to proceed to the many papers in Brachman et al. that relate to revisable reasoning. We mention a number of these papers below under the ``Metatheory'' category of our four-fold breakdown of LAI.

next up previous
Next: Other logical systems Up: System Specification Previous: Temporal logic

Selmer Bringsjord
Mon Nov 17 14:57:06 EST 1997