CS 507, Logic In Computer Science

 Autumn, 2004-2005


Purandar Bhaduri, ext: 2360, email: pbhaduri.

Course Contents (Tentative)

Propositional Logic: Syntax, Proof System, Semantics, Soundness and completeness, Compactness, Normal Forms, Resolution, Horn Clauses, propositional satisfiability solvers, Complexity.


First Order Logic: Syntax, Proof System, Semantics, Soundness and Completeness, Compactness, Herbrand Models, Unification and Resolution, Logic Programming and SLD Resolution, Decidability and Undecidability, Expressiveness, Ehrenfeucht-Fraisse Games, Applications.


Modal Logic: Possibility and Necessity, Knowledge or Belief, Frames and Forcing, Modal Tableaux, Soundness and Completeness, Modal Axioms and Special Accessibility Relations, Logics of knowledge. Applications.


CS203 (Discrete Maths), CS301 (Formal Languages and Automata Theory)


A. Nerode and R. A. Shore, Logic for Applications, Springer-Verlag, 1997, 2nd edition.

Reference Books

1.       M. Huth and M. Ryan, Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2000.


2.      M. Fitting, First-order Logic and automated theorem proving, Springer-Verlag, 1990.


3.       Logic for Computer Science: Foundations of Automatic Theorem Proving (Harper & Row Computer Science and Technology Series) Jean H. Gallier, John Wiley & Sons; (January 1986). An online version is available here.

Home Assignment Policy

You may discuss the homework problems among yourselves, but the final solution must be in your own words. No credit will be given for identical solutions. No late submission of homework will be accepted.

Term Paper

You will be required to write a term paper and give a presentation on a topic in Logic in Computer Science of your choice. The list of suggested topics will be announced.

Some Useful Links

LaTeX for Logicians

Mathematical Logic around the World

Logic and Games, an article by Wilfrid Hodges in the Stanford Encyclopedia of Philosophy

An article on Modal Logic from the same source.



 back to homepage