COMP 409:Logic in Computer Science

Compiled by Moshe Y. Vardi, who has no respect for those with no respect for logic.
P.R.H. Anonymous

If you think that your paper is vacuous,
Use the first-order functional calculus.
It then becomes logic,
And, as if by magic,
The obvious is hailed as miraculous.

Logic has been called "the calculus of computer science". The argument is that logic plays a fundamental role in computer science, similar to that played by calculus in the physical sciences and traditional engineering disciplines. Indeed, logic plays an important role in areas of Computer Science as disparate as architecture (logic gates), software engineering (specification and verification), programming languages (semantics, logic programming), databases (relational algebra and SQL), artificial intelligence (automatic theorem proving), algorithms (complexity and expressiveness), and theory of computation (general notions of computability).

COMP 409 provides the student with a thorough introduction to computational logic, covering in depth the topics of syntax, semantics, decision procedures, formal systems, and definability for both propositional and first-order logic. The material is taught from a computer science perspective, with an emphasis on algorithms and computational complexity. The goal is to prepare the students for using logic as a formal tool in computer science.

Course Material:

  • DIMACS SAT Format
  • A Brief History of Logic
  • On the Unusual Effectiveness of Logic in Computer Science
  • A Postmodern Perspective
  • A Poetic Undecidability Proof
  • Logic is about arguments; see video
  • Unreason's Seductive Charms
  • Logical Fallacies
  • Course Information
  • LaTeX for Logicians
  • Syllabus
  • Lecture Notes
  • Assignments and Solutions
  • 2005 Material
  • 2003 Material

  • Links

    In 2005: The course is offered in the fall. This web page is dormant during the spring.