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)