Nonclassical Logics ALG500014
Topic outline

Classical propositional logic (CPC) as a point of departure
 logic as algebra  Boolean algebras, algebraic semantics and completeness of classical propositional logic (w.r.t. BA via a LindenbaumTarski algebra construction, w.r.t. powerset algebras via possible worlds, w.r.t the twoelement BA).
 Stone representation theorem and how it connects to the above
 Some distinguishing properties of CPC we usually take for granted: local finiteness (only finitely many formulas in n variables up to provable equivalence), functional completeness (expresses all finitevalued boolean functions), strong completeness and compactness (finitarity), decidability (coNP completeness), normal forms,...

Nonclassical models of reasoning I: Intuitionistic Logic and Mathematics
This part of the course concentrates on intuitionistic logic and its applications in (constructive) metamathematics. The main topics covered by the course are:
 Predicate intuitionistic logic and its main properties (Kripke and algebraic semantics, completeness, disjunction and existence property)
 Intuitionistic axiomatic theories: Heyting arithmetics and its properties (incompleteness, disjunction and existence property, de Jongh's theorem)
 Algebraic semantics of intuitionistic logic (Heyting algebras) and its duality to Kripke semantics
 Decidability of intuitionistic propositional logic
Study materials:
N. Bezhanishvilli, D. de Jongh, Intuitionistic Logic, ESSLLI 2006 Lecture notes.
D. van Dalen, Logic and Structure, Springer 2nd edition 2008 (2013 ebook). available here.

Nonclassical models of reasoning II: Advanced topics in Modal Logics
The second part of the course is devoted to some advanced topics in modal logics (those not covered by the introductory course Modal logics).
 Algebraic semantics of modal logics and its duality to Kripke semantics, applications (GoldblattThomason Theorem  a proof via duality, and a modeltheoretic proof)
 van Benthem's theorem  a characterization of the modal fragment of first order logic
 Coalgebraic perspective on modal logics
 Proof theory of modal logics (different formalisms  nested sequents, display calculi, labelled calculi)

Nonclassical models of reasoning III: logics of information
Examples of logics whose semantics is underlined by a concept of information rather than that of a truth value.
 DunnBelnap logic of first degree entailment FDE, and its cousins (some of simplest examples of manyvalued and/or paraconsistent logics)
 Logics with frame semantics based on information states, including relevant logics
 Substructural logics
 Manyvalued (fuzzy) logics
 Twolayered logics for uncertainty

Forum

N. Bezhanishvilli, D. de Jongh, Intuitionistic Logic, ESSLLI 2006 Lecture notes

Intuitionistic logic (23.2.)
Intuitionism, BHKinterpretation of intuitionistic logic, Kripke semantics of intuitionistic predicate logic.

Completeness and applications (1.3.):
Kripke's proof of completeness of intuitionistic predicate logic and its applications, Disjunction property, Existence property.

File


Heyting arithmetics and its main properties: axiomatics, models, incompleteness.
Presentation topic 1.: Smorynski's trick, disjunction and existence property, de Jongh's theorem

File
C.A. Smorynski, Applications of Kripke models.


Heyting algebras, algebraic semantics and completeness of intuitionistic propositional logic.
Presentation Topic 2.: Duality between algebraic and Kripke semantics of intuitionistic logic (see ESSLLI Lecture notes).

Proof theory (single conclusion and multiconclusion sequent calculi) and decidability of propositional intuitionistic logic
Presentation topic 3: decidability proofs based on sequent calculi.

File
V. Švejdar, On Sequent Calculi for Intuitionistic Propositional Logic, CMUC 2005.

File


Algebraic semantics of modal logics, Boolean algebras with operators, examples. Completeness via LindenbaumTarski algebra.
Presentation topic: duality and applications  GoldblattThomason Theorem

Algebraic semantics and Duality theory of modal logics, Chapter 5 of
Blackburn P., de Rijke M., Modal logic, Cambridge University Press, 2001.


Overview of various forms of sequent calculi for modal logics: display calculi, nested sequents calculi, and ordinary sequents calculi. A more detailed look at the Display calculi for modal logics.

File

FDE: Belnap's firstdegree entailment logic FDE, also known as Belnap and Dunn’s "useful fourvalued logic". We cover its extensional, 4valued semantic, axiomatization and algebraic completeness as well as its frame doublevaluation semanitcs and frame completeness.
Expansions of FDE: we look at various expansions with additional connectives (negations, implications, modalities) both from extensional and intensional perspective. In particular, we will see Nelson's paraconsistent logic N4 and Wansing's logic I_4C_4 of constructive negation, and their relation to intitionistic or biintuitionistic logic.

Logics of relevance (and necessity): logic of entailment E, relevant logics R and RM. Variable sharing property. Algebraic semantics. Frame semantics: modelling implication with a ternary relation.



We will look at a specific format of a logic  twolayered (modal) logics  where two layers of reasoning (which can be two different logics) are separated syntactically and semantically: the inner layer of reasoning about events or evidence, and the outer layer of reasoning about (un)certainty about the events or evidence (or belief or likelihood). The two layers are connected with a modality interpreted via a chosen uncertainty measure defined on the formulas of the inner logic. We will first look at classical propositional logicbased twolayered logics for probability introduced in 90's, and then at some paraconsistent BDbased generalizations.