CS 507, Logic In Computer Science
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
Huth and M. Ryan, Logic in Computer Science: Modelling and Reasoning about
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.
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
An article on Modal Logic from the same source.