CSE 482 / CIS 582 : Logic in Computer Science. Fall 2005

Instructor: Rajeev Alur (alur@cis)

Class: Tues/Thurs 1.30-3, Towne 309

Office hours: Wednesday 2-3 (Levine 609)

Topics covered in lectures

Homework 1; Solutions

Homework 2; Solutions

Course project, Due Nov 29

Homework 3; Solutions

Final: Dec 15, Noon-2pm, Levine 307


Logic has been called the calculus of computer science as it plays a fundamental role in computer science, similar to that played by calculus in the physical sciences and traditional engineering disciplines. Indeed, logic is useful 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).

CSE 482 provides the students with a thorough introduction to mathematical logic, covering in depth the topics of syntax, semantics, decision procedures, formal proof systems, and soundness and completeness for both propositional and first-order logic. The material is taught from a computer science perspective, with an emphasis on algorithms, computational complexity, and tools. Projects will focus on problems in circuit design, specification and analysis of protocols, and query evaluation in databases.


CSE 260 or equivalent


Grades will based on


The recommended text is The lectures will not follow the text strictly. Following books are recommended for additional reading

Tentative Schedule


Many tools allow declarative specifications using logic, and support powerful analysis based on optimized decision procedures. Here are links to sample tools:

Miscellaneous Links

Last updated on July 2005 by Rajeev Alur