1. komponenta

Lecture type	Total
Lectures	30
Exercises	30

* Load is given in academic hour (1 academic hour = 45 minutes)

COURSE AIMS AND OBJECTIVES:
Enable students to:
- distinguish syntactic and semantic terms
- create semantic trees and proofs in various formal systems.

COURSE DESCRIPTION AND SYLLABUS:
I. Classical propositional logic.
1. Introduction. The language of propositional logic. Interpretations. The truth value of a formula for a given interpretation. Tautologies, antitautologies, satisfiable and refutable formulas.
2. Disjunctive and conjunctive normal form. Craig interpolation lemma.
3. The compactness theorem. Applications (order relation on commutative group and graph coloring).
4. Propositional proof system: Frege-Łukasiewicz system, proof, theorem, derivation. The soundness theorem. The deduction theorem.
5. The completeness theorem of propositional logic.
6. Consistency. Generalized completeness theorem.
7. Natural deduction system. The soundness theorem.
8. The completeness theorem for natural deduction system.
9. Non-classical logics: modal logic and intuitionistic logic.

II. First-order logic.
10. First-order languages. Structures and interpretations. The truth value of a formula. Valid, satisfiable, and refutable formulas.
11. Prenex normal form. The main test for first-order logic.
12. Proof system for first-order logic. The deduction theorem.
13. Generalized completeness theorem (a sketch of Henkin's proof). Consequences: Gödel completeness theorem, compactness theorem, Löwenheim - Skolem theorem.
14. Examples of first-order theories: theories with equality, Peano arithmetics and Zermelo-Fraenkel set theory.

1. Matematička logika, M. Vuković, Element, Zagreb, 2009.
2. Logic and structures, D. van Dalen, Springer Verlag, 1997.
3. Introduction to Mathematical Logic, 6th ed, E. Mendelson, CRC Press, 2015.

Izborni modul B - Teorijsko računarstvo, 1. godina - Regular study - Computer Science and Mathematics
Ostali izborni predmeti - Regular study - Computer Science and Mathematics

Izborni modul B - Teorijsko računarstvo, 1. godina - Regular study - Computer Science and Mathematics
Ostali izborni predmeti - Regular study - Computer Science and Mathematics

Ostali izborni predmeti - Regular study - Computer Science and Mathematics

Ostali izborni predmeti - Regular study - Computer Science and Mathematics