Non-classical Logics ALG500014
Osnova sekce
-
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 Lindenbaum-Tarski algebra construction, w.r.t. powerset algebras via possible worlds, w.r.t the two-element 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 finite-valued boolean functions), strong completeness and compactness (finitarity), decidability (coNP completeness), normal forms,...
---------------------------------------------------------------------------
Non-classical 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.
--------------------------------------------------------------------------------------------
Non-classical 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 (Goldblatt-Thomason Theorem - a proof via duality, and a model-theoretic 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)
----------------------------------------------------------------------------------------------
Non-classical 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.
- Dunn-Belnap logic of first degree entailment FDE, and its cousins (some of simplest examples of many-valued and/or paraconsistent logics)
- Logics with frame semantics based on information states, including relevant logics
- Substructural logics
- Many-valued (fuzzy) logics
- Two-layered logics for uncertainty
-
N. Bezhanishvilli, D. de Jongh, Intuitionistic Logic, ESSLLI 2006 Lecture notes
-
Intuitionistic logic (23.2.)
Intuitionism, BHK-interpretation 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.
-
Heyting arithmetics and its main properties: axiomatics, models, incompleteness.
Presentation topic 1.: Smorynski's trick, disjunction and existence property, de Jongh's theorem
-
-
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.
-
-
Algebraic semantics of modal logics, Boolean algebras with operators, examples. Completeness via Lindenbaum-Tarski algebra.
Presentation topic: duality and applications - Goldblatt-Thomason 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.
-
FDE: Belnap's first-degree entailment logic FDE, also known as Belnap and Dunn’s "useful four-valued logic". We cover its extensional, 4-valued semantic, axiomatization and algebraic completeness as well as its frame double-valuation 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 bi-intuitionistic 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 - two-layered (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 logic-based two-layered logics for probability introduced in 90's, and then at some paraconsistent BD-based generalizations.