Brief repetition of syntax of propositional logic: L&P 2.4
Note: This is a repetition of concepts that you should know already from the course Logic and Sets.
Deduction rules for propositional logic, and how they relate to informal reasoning: L&P 2.1, 2.2, 2.3.1-2.3.3
Natural deduction proofs using and and implies: 3.1
… continuation natural deduction for propositional logic
rules for negation
rules for disjunction
proof by contradiction (PBC)
Strategy for creating natural deduction proofs
L&P 2.3, 3.1-3.4
Propositional logic in Lean.
L&P 4.1-4.4. Look at 4.6, but we won’t discuss in lecture.
Semantics of propositional logic.
Soundness and completeness theorems
Classical reasoning.
All sections of ch. 5 and 6. (Note that some of ch. 6 is review from Logic and Sets.)
Syntax of predicate (first order) logic
terms, forumlas, and parse trees
scope of a quantor
bound and free variables
substitution
Natural deduction for predicate logic
Continuation natural deduction for predicate logic
Predicate logic in Lean
Predicate logic with equality
L&P 7.5, 8.4-8.5, 9.1-9.4
Semantics of predicate logic
models
interpretation of formulas
simplified (without free variables and quantifiers)
environments for dealing with free variables
full truth definition
associated notions
semantic entailment
L&P 10.1-10.4.
Semantics, associated notions:
logical equivalence
satisfiability of formulas
validity of formulas
consistency, inconsistency of sets of formulas
Translating into predicate logic
Interplay between connectives and quantifiers
Order relations
Equivalence relations
Relations in Lean
L&P 13.1 - 13.3, 14.1
No lecture. If you’re bored and want something to read on your own, see below.
These topics will not be on the exam.
The natural numbers and induction
The natural numbers in Lean
L&P 17.1 - 17.3
18.1 -18.2 suggested reading
Language of Modal logic
Kripke models and semantics
Truth in Kripke models
(Huth and Ryan, Chapter 5 up until par. 5.3.1)
Applications of modal logic, not on the exam but if you’re curious: 11b_modal_logic_applications.pdfPreview the document
Modal logic: frames, validity on frames
Correspondence between modal formulas and frame properties
Expressing modal properties in predicate logic
Completeness and Correctness Theorem(Huth and Ryan, p. 136, (2.10))
Consistency (satisfiability) versus syntactical consistency
Consistency Theorem
Compactness Theorem (Huth and Ryan, p. 137, Thm. 2.24)
comparison expressive power modal logic versus predicate logic (just an indication)
Definability and undefinability (Huth and Ryan, Sectie 2.6)
Undefinability of the concept finite
Reachability via a binary relation R is not definable in predicate logic (Huth and Ryan, Thm. 2.27)
Decision problems and the Halting Problem
Undecidability of predicate logic (Huth & Ryan Section 2.5)
Incompleteness Theorem (Gödel)