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:
There are many good books on Math Logic but unfortunately there
is no book suitable for the course on Logic for Computer Science.
Here some books which might be helpful for the course.
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 .