Show The Graduate Center Menu

Logical Fundamentals of Computer Science

Instructor: Distinguished Professor Rohit Parikh


Logic is one of the foundations of computer science. This course will give students the basic tools to pursue other areas in computer science, or build on this basic course towards more ambitious use of logic in computer science.

Course Description

This course will cover propositional and first order logic and provide an introduction to other logics like intuitionistic logic and modal logic.

Detailed List of Topics

  • Propositional logic and truth tables.
  • Notions of satisfaction and validity.
  • A quick introduction to NP-completeness.
  • First order logic, quantifiers.
  • Satisfaction, validity.
  • Gödel's completeness theorem.
  • Intuitionistic and Modal logic.
  • Logics of Justification and Knowledge.
  • Dynamic Logic and Logic of Programs
  • Basic model theory if there is time.

Learning Goals/Outcomes

  • Students will learn how to work with proofs in propositional logic, first order logic and various modal logics.
  • They will be expected to show familiarity with the main notions and results in logic
  • They should be able to reproduce proofs of major theorems, especially the completeness theorem of Gödel but also the soundness and completeness results in modal and related logics.
  • The students should know the history of justification logic, Gödel's problem and Artemov's solution to it.
  • Students should be familiar with Hoare logic and Dynamic Logic and how they are used to prove correctness of programs.
  • Students should be aware of the applications of epistemic logic in social reasoning and game theory.


Homeworks will be assigned each week and graded. There will be a final and a midterm examination as well. Students who do exceptionally well in the midterm examination will have the option to write a paper in lieu of the final. Typically, the homeworks and the midterm count for 25% of the course each and the final for 50%.