Show The Graduate Center Menu
 
 

Logical Fundamentals

Rationale

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 intuitionistic logic and modal logic and their applications.

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 logic, constructive semantics, proof systems.

  • Modals and Epistemic logics, applications to Game Theory.

  • Logics of Justification and constructive knowledge.

  • Dynamic Logic and Logic of Programs.

Learning objectives

  • Students will learn how to work with proofs in propositional logic, intuitionistic logic and various modal logics.

  • They will be expected to show familiarity with the main notions and results in logic 3. They should be able to reproduce proofs of major theorems, especially the completeness theorem of G odel but also the soundness and completeness results in modal and related logics.

  • The students should know the constructive semantics of proofs for intuitionistic and modal logics.

  • 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 and justification logic in social reasoning and game theory.

Assessment

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