You are here: Mathematics > undergraduate > undergraduate studies >course units > level 2 units > MATH20302
School of Mathematics

# MATH20302

General Information
• Title: Propositional Logic
• Unit code: MATH20302
• Credit rating: 10
• Level: 2
• Pre-requisite units: MT1101 or MT1111 (students who have not taken one of these course units should discuss this with the lecturer)
• Co-requisite units:
• School responsible: Mathematics
• Member of staff responsible: George Wilmers
Page Contents
Other Resources

## Unit specification

Aims
The programme unit aims to introduce the student to the idea of formalising arguments, both semantically and syntactically, and to the fundamental connection between these approaches.
Brief description
Logic is the study of arguments, what they are, what it means to say they are sound. As such it is central to Mathematics, Philosophy, and, to an increasing extent in recent years, Computer Science.
This course unit will deal with the most basic sort of argument (i.e., in everyday parlance, what we mean by 'A follows from B'), namely those which depend on their soundness simply on the commonly agreed interpretation of the connectives 'not', 'and', 'or' and 'implies'.
Essentially we shall caracterise this relation of 'follows' in two ways, firstly in terms of preservation of truth (semantically) and secondly in terms of the formal rules it obeys (proof theoretically, or syntactically). The highlight of the course unit will be the Completeness Theorem which say that these two characterisations are equivalent. This is a fundamental result for Mathematics; its essence is that if something isn't formally provable then there must be a counter example.

### Intended learning outcomes

On completion of this unit successful students will be able to:

• appreciate how arguments can be formalised semantically and syntactically and how these are connected (via the Completeness Theorem)
• in simple cases be able to show that 'A follows from B' both by giving a semantic argument and by constructing a formal proof
• in simple cases be able to show that 'A does not follow from B' by using semantics.
Future topics requiring this course unit
The course unit forms a coherent subject on its own, and provides necessary background knowledge for the third and fourth level Logic course units.

### Syllabus

1. Motivation, syntax, propositional variables, connectives, sentences. [2]
2. Valuations, logical consequence, logical equivalence, truth tables, satisfiability, Beth Trees. The Disjunctive Normal Form Theorem, expressibility, adequate sets of connectives. The Interpolation Theorem. [8]
3. Rules of proof, formal proofs, the Correctness Theorem. [6]
4. Consistency, the Completeness and Compactness Theorems. [6]
5. Switching circuits. [2]
Textbooks
Course unit notes will be provided. It will not be necessary to buy any books, but there a number of good books around which the student might enjoy (although they all tend to use substantially different notation, so that they are definitely not alternatives to the course unit notes), for example:
H.B. Henderton, A Mathematical Introduction to Logic, (second edition) Academic Press 2001, ISBN 0122384520
E. Mendelson, Introduction to Mathematical Logic, Wadsworth and Brooks 1997, ISBN 0534066240
E.J. Lemmon, Beginning Logic, Van Nostrand Reinhold (UK) 1971, ISBN 0442306768
Learning and teaching processes
Two lectures and one examples class each week
Assessment
Two take home tests Weighting within unit 20%
2 hours end of semester examination; Weighting within unit 80%

## Arrangements

Online course materials are available for this unit.