BSc Computer Science and Mathematics

Logic is the study of arguments: what they are and what it means to say that they are sound. As such it is central to Mathematics, Philosophy and, to an increasing extent in recent years, Computer Science.

Most of this course unit will deal with the most basic sort of logical argument (i.e., in everyday parlance, what we mean by 'A follows from B'), namely those which depend for their soundness simply on the commonly agreed interpretations of the logical connectives 'not', 'and', 'or' and 'implies'. That is referred to as propositional logic.

We shall characterise the above notion of 'follows' in two fundamentally different 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 for Propositional Logic, which tells us that these two quite different characterisations are equivalent. This is the younger sibling of the Completeness Theorem for Predicate Logic.That is a fundamental result for Mathematics which says that one can set up a notion of formal mathematical proof which is strong enough to capture mathematical truth:  if something isn't formally provable then there must exist a counterexample.  The propositional logic version of that theorem already allows us to introduce the key concepts and to see how a proof of such a general result can be achieved.

In the final few lectures the student is introduced to some basic ideas about predicate logic.  This deals with languages which allow the use of variables together with the quantifiers "for all..." and "there exists..." as well as functions, relations and constants. Such languages are of far greater expressive power than those of propositional logic and using them one can, in principle, formalise any mathematical argument. The Compactness Theorem for Predicate Logic will be stated and simple applications will be given. This part of the course unit serves as a brief introduction to these logics with quantifiers and to concepts which will be used in some level 3/4 units in Logi (for instance, the level 3 logic course contains a proof of the Compactness Theorem).

The course unit unit aims to introduce the student to the idea of formalising arguments, both semantically and syntactically, and to the fundamental connection between these approaches.

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

• Apply a variety of methods, including truth tables, algebraic manipulation, and logical reasoning, to simplify propositional terms, study logical equivalence and find conjunctive and disjunctive normal forms for propositional terms and interpolants.   
• Apply a variety of methods to determine whether one propositional term follows from another.   
• Determine whether or not a set of propositional connectives is adequate.   
• Reason with valuations to determine whether or not statements about logical consequence are true.   
• Determine whether or not a given sequence is a valid deduction.  
• Prove the equivalence of various forms of the completeness theorem, and prove the equivalence of various forms of the compactness theorem, and prove various forms of the compactness theorem using the completeness theorem.  
• Apply the propositional compactness theorem to relate statements involving infinite sets of terms with statements involving finite sets of terms.
• Interpret first-order formulas in a variety of mathematical structures, and determine the sets that they define in these structures.
• Construct structures satisfying certain axioms, in simple cases, and in simple cases, be able to prove that certain sentences have no model.

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.

1. Motivation, syntax, propositional variables, connectives, propositional terms. [3]

2. Valuations, logical consequence, logical equivalence, truth tables, satisfiability, disjunctive normal form, interpolation, adequate sets of connectives. [5]

3. Rules of proof, formal proofs, the Soundness Theorem. [4]

4. The Completeness and Compactness Theorems. [4]

5. Languages for Predicate Logic, structures, interpretations, and the statement of the Compactness Theorem for Predicate Logic, with examples. [6]

• One in-class test; weighting within unit 20%
• End of semester examination; weighting within unit 80%

Feedback tutorials will provide an opportunity for students' work to be discussed and provide feedback on their understanding.  In-class tests also provide an opportunity for students to receive feedback.  Students can also get feedback on their understanding directly from the lecturer, for example during the lecturer's office hour.

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. Enderton, A Mathematical Introduction to Logic, (second edition) Academic Press 2001, ISBN 0122384520.

E. Mendelson, Introduction to Mathematical Logic, Wadsworth and Brooks 1997, ISBN 0534066240.

I. Chiswell and W. Hodges, Mathematical Logic, Oxford University Press 2007, ISBN 0199215626  (more elementary than the two above).

W. Hodges, Logic, Penguin, 2^nd revised edition 2001, ISBN 0141003146 (aimed at a more general readership; more about the relations with natural language and philosophy)

This course unit detail provides the framework for delivery in 20/21 and may be subject to change due to any additional Covid-19 impact.  

Please see Blackboard / course unit related emails for any further updates