CS507LOGIC IN COMPUTER SCIENCE3-0-0-6

Pre-requisites : CS203, CS301

Syllabus :
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.

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

References :
1. M. Huth and M. Ryan, Logic in Computer Science: Modelling and Reasoning about Systems, 2nd Ed, Cambridge University Press, 2004.
2. M. Fitting, First-order Logic and automated theorem proving, Springer-Verlag, 1990.
3. J. H. Gallier, Logic for Computer Science: Foundations of Automatic Theorem Proving (Harper & Row Computer Science and Technology Series), John Wiley & Sons, 1986.