CS 507,
Logic In Computer Science
Autumn, 2004-2005Instructor 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. Prerequisites CS203 (Discrete Maths), CS301 (Formal Languages and Automata Theory) Textbook A. Nerode and Reference Books 1. M.
Huth and M. Ryan, Logic in Computer Science: Modelling and Reasoning about
Systems, 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 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. |