# Introduction to Formal Proof: 2022-2023

| |

| |

| Trinity Term 2023 (10 lectures) |

## Learning outcomes

1. Familiarity with the idea of structured formal proof (a) in propositional logic (b) in first-order predicate logic2. Familiarity with the notions of soundness and completeness as relationships between logics and their semantics.

3. Familiarity with the distinction between proofs in a logic and proofs about a logic and its semantics.

5. An understanding of the relationship between (on the one hand) completely formal proofs and (on the other hand) rigorous proofs of the kind that students are routinely expected to read and to present.

6. Preparedness for the second year course Logic & Proof which treats matters of soundness and completeness rigorously.

## Synopsis

- propositional variables and connectives
- structural induction
- truth assignments and truth tables
- validity and satisfiability
- equivalences; the substitution lemma and the replacement lemma
- normal forms
- natural deduction for propositional logic

• natural deduction rules for predicate calculus

## Syllabus

- propositional variables and connectives
- structural induction
- truth assignments and truth tables
- validity and satisfiability
- equivalences; the substitution lemma and the replacement lemma
- normal forms
- natural deduction for propositional logic

• natural deduction rules for predicate calculus

## Reading list

- Logic in Computer Science (Huth and Ryan, CUP, 2008)
- Logic as a Tool: A Guide to Formal Logial Reasoning (Goranko, Wiley 2016)

## Feedback

Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.