Computer Laboratory

Course pages 2012–13

Introductory Logic

To discuss the material covered in the lectures or any of the exercises handed out, please find me after the lectures or e-mail to arrange for a time to meet.

Exercise sheets


Summary of lectures and suggested exercises

There will not be any written notes or slides to accompany the course. After each lecture, I will add a brief summary of what was lectured and suggest further reading. I will also list some simple exercises, related to the lecture material, that I encourage you to work on (ideally, before the next lecture). If you are not sure whether you are on the right track, you are always welcome to show me and discuss your attempts at these exercises.

Part 1. Background and revision

  • Lecture 1:

    Summary: Cartesian product of sets and An. Power set. Some common sets (N, Q, R, B = {0,1}, etc). Relations and their arity. Functions: injective, surjective, bijective. Scröder-Bernstein theorem. Cardinality of a set and ordering of cardinals. Cantor's theorem. Countable sets and uncountable sets. If A is countable and infinite then cardinality of A is the same as the cardinality of the natural numbers. Recursively enumerable (r.e.) and decidable sets. A set is decidable iff both the set and its complement are recursively enumerable. Example of a set that is r.e. but not decidable.

    Suggested exercises: Verify that the definition of cardinality that was given agrees with the usual notion of size for finite sets. Show that the mapping from Q to N that was given in one of the examples is an injection. The construction used in that example is known as the 'prime-powers trick': essentially, it gives an injection from N x N to N by mapping each pair (a,b) to the integer 2a 3b. Can you generalise this construction to give an injection from Nm to N for any positive integer m? Can you use this construction to show that for any m and countable set A, the set Am is also countable? Cantor's theorem shows that the power set of any set A has a strictly larger cardinality than A. How about the set of all finite subsets of A? Can you show, using the prime-powers trick, that if A is countable then the set of all finite subsets of A is also countable?

Further reading: For a proof of Cantor's theorem, see for example section 4.3.2 of these lecture notes. Further background on cardinals can be found in Chapter 0 of Enderton's book.

Part 2. Propositional logic

  • Lecture 2:

    Summary: Syntax of propositional logic: the language L(P) of propositional formulas over a countable set P of primitive propositions. Semantics of L(P) in terms of valuations on P. Truth tables, tautologies and semantic entailment. A Hilbert-style proof system for propositional logic: an infinite set of axioms and only one rule of inference (modus ponens). Formal deduction, syntactic entailment and theorems of the propositional logic. Connection between semantic and syntactic entailment. Proof of the soundness theorem for propositional logic.

    Suggested exercises: Using truth-tables (or otherwise), verify the correcness of the short-hand notation we gave for the standard logical connectives (∧, ∨, ¬) in terms of ⇒ and ⊥. Show that each of the axioms of the proof system for propositional logic is a tautology (where you substitute any formulas for s, t and u). Give a deduction of (p ⇒ r) from the set H = {(p ⇒ q), (q ⇒ r)}. What is this theorem (with respect to the hypotheses H) telling us?

    Lecture 3:

    Summary: Deduction Theorem and its proof. Consistent and maximal consistent sets of propositional formulas. Deductively closed sets of formulas. Proof that there exists a maximal consistent extension of any consistent set H. A model for a set of formulas. Proof that every consistent set has a model (the Adequacy Theorem). Completeness Theorem and its proof. Compactness Theorem for propositional logic.

    Suggested exercises: Work out Exercise 2.10 given in the lecture.

Further reading: Propositional logic has many names in the literature, including "propositional calculus", "sentenial logic" and "sentential calculus". Don't let this confuse you. For further details on propositional logic, see Chapter 1 of Enderton's book (he uses the term sentenial logic). See also Chapter 1 of Forster's online lecture notes for further details.

Part 3. First-order logic

  • Lecture 4:

    Summary: Signatures and relational structures. Restriction to signatures with no function symbols. Syntax of first-order logic in signature τ: terms and formulas. Free and bound variables. Assignments in a τ-structure A. Semantics of first-order logic.

    Suggested exercises: Write down formally the semantics for derived connectives and operators ∃, ∧, ∨ and ¬.

    Lecture 5:

    Summary: Satisfiable and valid formulas. Semantic entailment. Substitution. Proof system for first-order logic (Hilbert-style): axioms of type (a) - (g) and two rules of inference, Modus Ponens (MP) and Universal Generalisation (Gen). Deduction theorem and its proof (building on the correspondiong proof for propositional logic). Soundness and completeness of the proof system. Compactness theorem for first-order logic.

    Suggested exercises: Exercise 15 from the first problem sheet: show the equivalence between the two stated versions of the Compactness theorem in the case of first-order logic.

Further reading: First-order logic is sometimes also called "predicate logic" or "predicate calculus". For further details on first-order logic logic, see Chapter 2 of Enderton's book.

Part 4. Model theory of first-order logic

Further reading: For further details on model theory, I recommend Hodges' textbook (which you can get at a discount in the CUP bookstore).

Resources

All these books should be available in the CL library. For alternatives, you may want to check your college library or the Betty and Gordon Moore library (in the Centre for Mathematical Sciences). You can search through the catalogues of all CU libraries here.

  • A Mathematical Introduction to Logic by Herbert B. Enderton (2nd edition, 2001).
  • Logic, Induction and Sets by Thomas Forster (2003).
  • A shorter model theory by Wilfrid Hodges (2002).
  • See also Thomas Forster's excellent lecture notes on Introductory logic (requires a Raven login).

(Page last updated: October 25, 2012 at 17:30)