Lecture 1: Chapters 1 and 2 of Logic and Proof, beginning Chapter 3

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

Lecture 2: Chapters 3 and 5 of Logic and Proof

… 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

Lecture 3: Chapter 4 of Logic and Proof

Propositional logic in Lean.

L&P 4.1-4.4. Look at 4.6, but we won’t discuss in lecture.

Lecture 4: Chapters 5 and 6 of Logic and Proof

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.)

Lecture 5: Chapters 7 and 8 of Logic and Proof:

Syntax of predicate (first order) logic

terms, forumlas, and parse trees

scope of a quantor

bound and free variables


Natural deduction for predicate logic

Lecture 6: Chapters 8 and 9

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

Lecture 7: Chapter 10

Semantics of predicate logic


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.

Lecture 8:

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

Lecture 9: Chapters 13 and 14

Order relations

Equivalence relations

Relations in Lean

L&P 13.1 - 13.3, 14.1

Lecture 10: Chapters 17 and 18

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

Lecture 11:

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

Lecture 12:

Modal logic: frames, validity on frames

Correspondence between modal formulas and frame properties

Expressing modal properties in predicate logic

Lecture 13: Metatheory

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)

Lecture 14: Metatheory

Decision problems and the Halting Problem

Undecidability of predicate logic (Huth & Ryan Section 2.5)

Incompleteness Theorem (Gödel)

Lecture 15: Preparation for the exam