COURSE AIMS AND OBJECTIVES: The course begins with study of syntax and semantics of propositional logic. The basic aim is to define the notions of formula, interpretation, truth and validity, proof, theorem and consistency, for the very simple theory. Hilbert-style system and natural deduction for propositional logic are defined, and the Soundness and Completeness theorems are proved.
The first order theories are considered in the second part. The syntax and semantics are defined. Sketch of Henkin's proof of the completeness theorem and its consequences are given.
COURSE DESCRIPTION AND SYLLABUS:
I. Propositional logic
1. Introduction. Syntax, formulas, interpretations and truth. Validity and satisfiability.
2. Normal forms. Craig interpolation lemma.
3. Compactness theorem. Applications (ordering of abelian groups and graph coloring)
4. Frege - Łukasievicz system, proof, theorem, deduction. Soundness theorem. Deduction theorem.
6. Completeness theorem for Frege-Łukasievicz system.
7. Consistency. Generalized completeness theorem.
8. Natural deduction. Soundness theorem.
9. Completeness theorem for natural deduction.
10. Some non-classical propositional logic: modal and intuitionistic logic
II. First order logic.
1. Signature of first order theories. First order logic. Structures and interpretations. The truth of formulas. Validity and satisfiability.
2. Prenex normal forms. Semantic trees.
3. Hilbert system. Deduction theorem.
4. Generalized completeness theorem (sketch of Henkin's proof). Consequences: Gödel
5. completeness theorem, compactness theorem, Löwenheim-Skolem theorem. 6. Some examples of first order theories: theories with equality, Peano arithmetic and
7. Zermelo-Fraenkel set theory.
|
Pristupačnost
