Non-monotonic logic (M Peliš)


Last update

back to Courses

Logic and information II (Non-monotonic logics)

Dpt of Logic, Faculty of Arts, Charles University in Prague
2/0 Zk


  1. Classical consequence relation and operation
    1. Consistency and consequnece
    2. Basic properties of classical (Tarski) consequence (reflexivity, cumulative transitivity, monotony - Horn rules)
    3. Supraclassicality
    4. Paraclassicality
    5. Compactness and maximality
    6. Substitution (closed under substitution)
    7. How to get more?
  2. Additional background assumptions
    1. Pivotal-assumptions
    2. Default-assumptions (cautious monotony, non-compactness)
  3. Restrictions of the set of models (valuations)
    1. Pivotal-valuations (non-compactness, definable sets of valuations)
    2. Default-valuations (preferential models, consistency preservation, non-monotonicity, non-transitivity, cautious monotony for well-founded relations on models, not consistency preservation)
  4. Additional background rules
    1. Pivotal-rules (neither disjunction in the premisses nor contraposition)
    2. Default-rules
  5. Default logic
    1. Default rules
    2. Default theories
    3. Operational semantics (process, extension)
    4. General properties (consistency preservation, cautious monotony)
    5. Normal default theories (existence of extensions, monotony in defaults, orthogonalitz of extensions)
    6. Representation in normal default theories (non-normality required)
    7. Semi-normal default theories
    8. Proof theory for default logic
    9. Joint consistency of justifications
    10. Modified extensions
    11. Priorities among defaults
  6. Non-monotonic modal logics and Autoepistemic logics


  1. Exercises A-D (pdf-file)
  2. Exercises E (pdf-file)


The course is also maintained at Moodle UK under the title Logika a informace II. All topics and terms introduced in lectures are covered by emphasized literature, by slides and handouts (see below), and by exercises. Some papers are available at Moodle UK. Moreover, the exercises include all basic terms and theorems. They fully cover the contents of handouts Introduction to Nonmonotonic Logics. For the topics A-D we recommend the book [Makinson 2005], some parts of chapters 1-4. Default logic (with operational semantics, topic E) is presented in [Antoniou 1997], some parts of chapters 3-7. See also [Meyer and van der Hoek 1995].

References - books

  • G Antoniou. Nonmonotonic Reasoning. MIT Press, 1997
  • D Batens, C Mortensen, G Priest, J-P Van Bendegem (eds.) Frontiers of Paraconsistent Logic. Research Studies Press Ltd., 2000
  • A Bochman. A Logical Theory of Nonmonotonic Inference and Belief Change. Springer, 2001
  • P Doherty (ed.) Partiality, Modality, and Nonmonotonicity. CSLI, 1996
  • R Fagin, JY Halpern, Y Moses, MY Vardi. Reasoning about Knowledge. MIT Press, 1995
  • DM Gabbay, CJ Hogger, JA Robinason (eds.) Handbook of Logic in Artificial Intelligence and Logic Programming. Vol 3. Nonmonotonic Reasoning and Uncertain Reasoning. Clarendon Press, Oxford 1994
  • JY Halpern. Reasoning about Uncertainty. MIT Press, 2005
  • JW Lloyd. Foundations of Logic Programming. Springer, 1987
  • D Makinson. Bridges from Classical to Nonmonotonic Logic. King's College Publications, 2005
  • J-J Meyer, W van der Hoek. Epistemic logic for AI and Computer Science. Cambridge, 1995
  • G Priest. An Introduction to Non-Classical Logic. Cambridge, 2001

Slides and handouts