2.0 VU Nichtklassische Logiken (185.249, WS 2012/13)
2.0 VU Modallogik, Epistemische Logik (185.269, WS 2012/13)

(Nonclassical logics / modal and epistemic logics)

Lecturer: Chris Fermüller.

This course will be held in English, unless all participants are fluent in German.

Important remark:
Students of Informatik (jeder Studienzweig) should take this course as `2.0 VU Nichtklassische Logiken (185.249)' while students in the European Masters Program in Computational Logic (Erasmus Mundus) will receive relevant/necessary credits under the (TU-internal) heading `2.0 VU Modallogik, Epistemische Logik (185.269)'

*** New/recent information ***

• The fourth meeting will take place

  Friday, January 11, 2013, 11:00 (sharp!) - 13:00
  Seminar Room von Neumann
  Favoritenstraße 9 / ground floor

• There will be no meeting on December 21.
• Deadline for submitting solutions to exercises from December 7 and 14 is January 9, 2013.

Contents of the course (tentative)

• We will start with a short reminder on the main concepts of classical first order logic
• Next, a rather informal classification and overview over the vast area of 'nonclassical logics' should serve as a point of orientation
• In the main part of the course we plan to cover the following areas and topics:
  • Modal logics (this will be our main topic):
    • What are modal logics? What are they used for?
    • Introduction into the general theory of modal logics: syntax, (Kripke style) semantics, proof systems, expressibility, 'correspondence theory', relations between important modal logics, multi-modal logics, ...
    • Epistemic logic(s) (for modelling multi-agent systems)
    • Hints at other families of modal logics: temporal logic, deontic logic, dynamic logic, provability logic, ...
  • Constructive logic (intuitionistic logic):
    • general motivation
    • different semantics: Kripke/Beth style semantics, Brouwer-Heyting-Kolmogorov interpretation, topological semantics
    • different proof systems: Hilbert type, sequent system(s), 'natural deduction', ...
    • dialogue games characterizing constuctive (and other) logics
  • Selected topics on other types of logics, e.g.,:
    • many valued logics, fuzzy logics
    • game semantics, dialogue games
    • modal epistemic logic

Prerequisites:

Basic knowledge about classical propositional and first-order logic as covered, e.g., in "Theoretische Informatik und Logik".

TEST YOURSELF whether you are fit for this course:
You should be able to prove without handwaving (and preferably without consulting any book or notes) that (forall x) (exists y) P(x,y) is a logical consequence of (exists x) (forall y) P(y,x), and to (rigorously) show that the converse does not hold. In particular you should be able to present a formal definition of the (logical) consequence relation and of a (formal) model/interpretation of a classical first-order formula.

Meetings

The course will take place in slightly blocked form on 8 or 9 Fridays in October, November, December, and January.

Lectures are currently planned for the following dates:
Oct 12, Oct 19, Nov 9, Nov 16, Nov 30, Dec 7, Dec 14, Jan 11

• Friday, 11:00 (sharp) - (about) 13:00
  Seminar Room von Neumann or Gödel (depending on the date)
  Favoritenstraße 9 / ground floor

Handouts

Various course material - in particular copies of the lecture slides - will be made available here (and/or in the lecture) to all participants.

• Slides, lecture 1 on 12/10/12: [PDF, 13 pages]
• A nice set of solutions to the first block of excercises (1-7b) by Gerald Berger [PDF, 10 pages]
• Slides, lecture 2 on 19/10/12: [PDF, 14 pages]
• Two complete sets of solutions for the second unit (exercises 8-17):
  • PDF, 8 pages by Gerald Berger
  • PDF, 9 pages by Bernhard Kragl
• Slides, lecture 3 on 9/11/12: [PDF, 13 pages]
• Slides, lecture 4 on 16/11/12: [PDF, 13 pages]
  Additional material on the Muddy Children and Three Wise Men examples:
  • Muddy children [PDF, 3 pages]
  • Muddy children / Wise Men [PDF, 3 pages]
  See below for links to further information on epistemic modal logic.
• Hints for derivations in Hilbert-style systems for modal logics [PDF, 1 page]
• A solution to exercise 28 [PDF, 1 page]
• A nice set of solutions to the third block of excercises Bernhard Kragl [PDF, 4 pages]
• A nice set of solutions to the fourth block of excercises Bernhard Kragl [PDF, 6 pages]
• (Lecture 5 on 30/11/12 has been devoted to the discussion of exercises/problems)
• Slides, lecture 6 on 7/12/12:[PDF, 8 pages]
• Hilbert style systems based on standard logical connectives: [PDF, 1 page]
• Slides, lecture 7 on 14/12/12 [PDF, 15 pages]

Hints for the preparation and submission of solutions to exercises

We strongly recommend the use of LaTeX. Useful style files are available from Latex for Logicians.
For drawing graphs and automata - and thus also Kripke models - the LaTeX package VauCanSon-G should be useful. More options for automata/graph drawing with LaTeX can be found at MET - Automata in LaTeX. Also the TeX/LaTeX extension PGF/TikZ is well worth exploring.

Include the problem statement, its number (`Exercise X: ... ') and your name in the submitted solution files. Send corresponding (uncompressed) PDF files via email to Chris Fermüller using "NCL exercises" as subject line.

Evaluation/credits

The evaluation will be based on the amount and quality of submitted solutions to the exercises (as assigned during the course).

Further links

• Some links concerning the so-called paradoxa of material implication, mentioned in the first lecture:
  Paradoxes of Material Implication, a lecture handout by Peter Suber
  Paradoxes of material implication, Wikipedia entry
  Philosophy Dictionary: paradoxes of material implication , a very short, but reliable entry at Answers.com
• Entry on Modal Logic in the Stanford Encyclopedia of Philosophy by James Garson.
• Wikipedia entry for Epistemic Modal logic (starting point for beginners).
• Entry on Epistemic Logic in the Stanford Encyclopedia of Philosophy by Vincent Hendricks.
• Slightly advanced survey article on Epistemic Logic (inlcuding hints on applications) by Wiebe van der Hoek and Rineke Verbrugge.
• Entry on Intuitionistic Logic in the Stanford Encyclopedia of Philosophy by Joan Moschovakis.
  Compare also the entry on Constructive Mathematics by Douglas Bridges.
• Halpern et.al. On the Unusual Effectiveness of Logic in Computer Science, Bulletin of Symbolic Logic, 2001.
• The Wikipedia entry on the Curry-Howard correspondence (aka Curry-Howard isomorphism) is quite reliable and informative.
• A whole book by Sorensen and Urzycyn called Curry-Howard isomorphism is available on the web (click title).
• An article for the Blackwell Companion to Philosophical Logic (ed. Dale Jacquette): Petr Hajek: Why Fuzzy Logic? (PS, preprint version).
• An article for the Handbook of Automated Reasoning (eds. Alan Robinson, Andrei Voronkov): Automated Deduction for Many-Valued Logics (PS, preprint version)