 Shawn Hedman, A First Course in Logic: An Introduction to
Model Theory, Proof Theory, Computability and Complexity , Reprinted in 2006,
Oxford Texts in Logic, Oxford University Press (Text for course) .
 Michael Huth and Mark Ryan, Logic in Computer Science: Modelling
and Reasoning about Systems , Second Edition,
Cambridge University Press (Text for course) .
 B. A. Davey and H. A. Priestley, Introduction to
Lattices and Orders, Second edition, Cambridge University Press,
2001 (Text for course)
 D. Kroening and O. Strichman, Decision Procedures:
An Algorithmic Point of View , Springer, 2008
Current Reading List
 Chapters 1 and 2 of Logic in Computer Science:... by M. Huth and
M. Ryan
 Chapters 1, 2 and 3 of A First Course in Logic: ... by
Shawn Hedman.
 Chapters 2 and 10 of Decision Procedures:
An Algorithmic Point of View by D. Kroening and O. Strichman
(available in Central Library)
 Slides (parts 1&2) on firstorder logic.
Lecture Schedule
Date  Topics details  
Jul 24  Course overview and prerequisites. The importance
of logical reasoning in both theory and practice. Introduction to
proofs in propositional logic: what is a proof? 
Jul 27  A proof system for propositional logic, working out a
few proofs, soundness of proof rules 
Jul 31  Completeness of propositional proof system for finite
sets of formulas 
Aug 1  Compactness theorem for propositional logic and its
proof; completeness of propositional logic with infinite sets of formulas as a consequence of compactness 
Aug 3  Application of compactness to show limitations of propositional logic: expressing finiteness, singletonness of a set of natural numbers. Introduction to resolution for propositional logic: converting to CNF, Tseitin encoding for equisatisfiable (not equivalent) CNF conversion 
Aug 7  More on resolution in propositional logic:
soundness of resolution, example, preliminary discussion on
completeness of resolution. Introduction to first order logic
(FOL) 
Aug 8  Syntax and semantics of FOL, Notion of
structures and bindings/environments, examples 
Aug 10  Graphs as firstorder structures, notions of semantic and syntactic entailment, a proof system for FOL, soundness and completeness of proof system, compactness of FOL and some consequences 
