20466 Logic for Computer Science 1

Credits: 4 intermediate credits in Mathematics or in Computer Science

Prerequisites: none

Required: Two courses in Mathematics, among them Discrete Mathematics: Set Theory, Combinatorics and Graph Theory,2 and two courses in Computer Science

Authors: Yoram Hirshfeld, Yossi Kaufman

The course provides important general knowledge needed by Computer Science students, which has myriad uses in fields such as computability, program verification and databases. The course centers on the most important logic – the mathematical relational logic. This is done in the context of general formal languages, their syntax and their meaning (semantics).

Objectives: To provide students with an understanding of the mechanism of formal specification languages and their role in Computer Science; to discern between syntax and semantics and between ways of handling syntactic objects and semantic objects, impart classical mathematical logic and reinforce the term ‘formal proof’, acquaint students with logics used in Computer Science for program specification and verification, and for database management.

Topics: Introduction – natural and formal languages; The propositional language; Propositional calculus; The predicate language; Predicate calculus and its completeness; The incompleteness of arithmetic; Multi-sorted logic and second-order logic; Herbrand term models; Logical foundation for databases; Modal and temporal logic for program verification.

---

1There is some overlap in the content of this and other courses. For details, see Overlapping Courses.

2or Discrete Mathematics: Set Theory, Combinatorics and Logic (20283), which is no longer offered.