Introduction to Formal Proof: 2021-2022

Lecturer	Edith Elkind
Degrees	Preliminary Examinations — Computer Science
Term	Trinity Term 2022 (10 lectures)

Learning outcomes

1. Familiarity with the idea of structured formal proof (a) in propositional logic (b) in first-order predicate logic

2. 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 logic:

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

First order (predicate) logic

• signatures and structures

• predicate language, quantifiers and substitution
• natural deduction rules for predicate calculus

Syllabus

Propositional logic:

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

First order (predicate) logic

• signatures and structures

• predicate language, quantifiers and substitution
• 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)

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.