World Library  
Flag as Inappropriate
Email this Article

Default logic

Article Id: WHEBN0000889639
Reproduction Date:

Title: Default logic  
Author: World Heritage Encyclopedia
Language: English
Subject: Non-monotonic logic, Artificial intelligence, Stable model semantics, Logic programming, Frame problem
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Default logic

Default logic is a non-monotonic logic proposed by Raymond Reiter to formalize reasoning with default assumptions.

Default logic can express facts like “by default, something is true”; by contrast, standard logic can only express that something is true or that something is false. This is a problem because reasoning often involves facts that are true in the majority of cases but not always. A classical example is: “birds typically fly”. This rule can be expressed in standard logic either by “all birds fly”, which is inconsistent with the fact that penguins do not fly, or by “all birds that are not penguins and not ostriches and ... fly”, which requires all exceptions to the rule to be specified. Default logic aims at formalizing inference rules like this one without explicitly mentioning all their exceptions.

Syntax of default logic

A default theory is a pair \langle W, D \rangle. W is a set of logical formulae, called the background theory, that formalize the facts that are known for sure. D is a set of default rules, each one being of the form:

\frac{\text{Prerequisite : Justification}_1, \dots , \text{Justification}_n}{\text{Conclusion}}

According to this default, if we believe that Prerequisite is true, and each of Justification_i is consistent with our current beliefs, we are led to believe that Conclusion is true.

The logical formulae in W and all formulae in a default were originally assumed to be first-order logic formulae, but they can potentially be formulae in an arbitrary formal logic. The case in which they are formulae in propositional logic is one of the most studied.

Examples

The default rule “birds typically fly” is formalized by the following default:

D = \left\{ \frac{Bird(X) : Flies(X)}{Flies(X)} \right\}

This rule means that, if X is a bird, and it can be assumed that it flies, then we can conclude that it flies. A background theory containing some facts about birds is the following one:

W = \{ Bird(Condor), Bird(Penguin), \neg Flies(Penguin), Flies(Bee) \}.

According to this default rule, a condor flies because the precondition Bird(Condor) is true and the justification Flies(Condor) is not inconsistent with what is currently known. On the contrary, Bird(Penguin) does not allow concluding Flies(Penguin): even if the precondition of the default Bird(Penguin) is true, the justification Flies(Penguin) is inconsistent with what is known. From this background theory and this default, Bird(Bee) cannot be concluded because the default rule only allows deriving Flies(X) from Bird(X), but not vice versa. Deriving the antecedents of an inference rule from the consequences is a form of explanation of the consequences, and is the aim of abductive reasoning.

A common default assumption is that what is not known to be true is believed to be false. This is known as the Closed World Assumption, and is formalized in default logic using a default like the following one for every fact F.

\frac{:{\neg}F}_2-complete;
Model checking
deciding whether a propositional interpretation is a model of an extension of a propositional default theory is \Sigma^P_2-complete.

Implementations

Three systems implementing default logics are DeReS, XRay and GADeL

See also

References

  • G. Antoniou (1999). A tutorial on default logics. ACM Computing Surveys, 31(4):337-359.
  • M. Cadoli, F. M. Donini, P. Liberatore, and M. Schaerf (2000). Space efficiency of propositional knowledge representation formalisms. Journal of Artificial Intelligence Research, 13:1-31.
  • P. Cholewinski, V. Marek, and M. Truszczynski (1996). Default reasoning system DeReS. In Proceedings of the Fifth International Conference on the Principles of Knowledge Representation and Reasoning (KR'96), pages 518-528.
  • J. Delgrande and T. Schaub (2003). On the relation between Reiter's default logic and its (major) variants. In Seventh European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2003), pages 452-463.
  • J. P. Delgrande, T. Schaub, and W. K. Jackson (1994). Alternative approaches to default logic. Artificial Intelligence, 70:167-237.
  • G. Gottlob (1992). Complexity results for nonmonotonic logics. Journal of Logic and Computation, 2:397-425.
  • G. Gottlob (1995). Translating default logic into standard autoepistemic logic. Journal of the ACM, 42:711-740.
  • T. Imielinski (1987). Results on translating defaults to circumscription. Artificial Intelligence, 32:131-146.
  • T. Janhunen (1998). On the intertranslatability of autoepistemic, default and priority logics, and parallel circumscription. In Proceedings of the Sixth European Workshop on Logics in Artificial Intelligence (JELIA'98), pages 216-232.
  • T. Janhunen (2003). Evaluating the effect of semi-normality on the expressiveness of defaults. Artificial Intelligence, 144:233-250.
  • H. E. Kyburg and C-M. Teng (2006). Nonmonotonic Logic and Statistical Inference. Computational Intelligence, 22(1): 26-51.
  • P. Liberatore and M. Schaerf (1998). The complexity of model checking for propositional default logics. In Proceedings of the Thirteenth European Conference on Artificial Intelligence (ECAI'98), pages 18–22.
  • W. Lukaszewicz (1988). Considerations on default logic: an alternative approach. Computational Intelligence, 4(1):1-16.
  • W. Marek and M. Truszczynski (1993). Nonmonotonic Logics: Context-Dependent Reasoning. Springer.
  • A. Mikitiuk and M. Truszczynski (1995). Constrained and rational default logics. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI'95), pages 1509-1517.
  • P. Nicolas, F. Saubion and I. Stéphan (2001). Heuristics for a Default Logic Reasoning System. International Journal on Artificial Intelligence Tools, 10(4):503-523.
  • R. Reiter (1980). A logic for default reasoning. Artificial Intelligence, 13:81-132.
  • T. Schaub, S. Brüning, and P. Nicolas (1996). XRay: A prolog technology theorem prover for default reasoning: A system description. In Proceedings of the Thirteenth International Conference on Automated Deduction (CADE'96), pages 293-297.
  • G. Wheeler (2004). A resource bounded default logic. In Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR-04), Whistler, British Columbia, 416-422.
  • G. Wheeler and C. Damasio (2004). An Implementation of Statistical Default Logic. In Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004), LNCS Series, Springer, pages 121-133.

External links

  • Schmidt, Charles F. RCI.Rutgers.edu, Default Logic. Retrieved August 10, 2004.
  • Ramsay, Allan (1999). UMIST.ac.uk, Default Logic. Retrieved August 10, 2004.
  • Stanford.edu, Defeasible reasoning, Stanford Encyclopedia of Philosophy.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from National Public Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.