Logics for Computer Science

Course plan:

- Historical background: Logic and its connection with different fields of science. Different fields of application of Logics.
- Propositional Logic: Propositional logic its syntax and semantics. Basic properties of Propositional logics. Normal forms. Functional completeness. Decidability. Hilbert propositional Calculus. Deduction theorems. Completeness and compactness. Natural deduction. Tense and modal logics.
- Predicate Calculus: Syntax and semantics of first order language. Examples of Structures for first-order language. Equivalence transformation and Normal forms. Skolem and Herbrand Theorems. Undecidability. Calculus. Completeness and compactness and some consequences. Incompleteness Theorem.
- Applications: Sugaring of first order language - many sorted language, applications to database. Temporal logics and their functional completeness. Logics for reasoning about programs; Hoare and Dynamic logics.

**Assignments: homeworks with exercises.
It is required to submit 80%.
The final grade = 20%homework+80% exam.
**

**Requirements: Discrete Math.
**

**Literature:**

Sperschneider and Antonio, Logic: A foundation of Computer Science.

van Dalen, Logic and Structure.

Mendelson, Mathematical Logic.

Ebbinghaus, Flum and Thomas Mathematical Logic.

**Slides for the lecture on 02/01/07:**
pdf and
ps.gz

**Slides for the lecture on 16/01/07:**
pdf and
ps.gz

**See also the course page of the instructor:**
Zamansky Anna .