Mathematical Logic
Code  Completion  Credits  Range  Language 

BIEMLO  Z,ZK  5  2+2 
 Lecturer:
 Kateřina Trlifajová (guarantor)
 Tutor:
 Jitka Rybníčková
 Supervisor:
 Department of Applied Mathematics
 Synopsis:

An introduction to predicate logic, the standard language and deductive system of mathematics and computer science.
 Requirements:

Elementary arithmetics,
basic understanding of formal languages.
 Syllabus of lectures:

1. Intro and motivation: logic as a language and a framework of mathematics. Truth and provability, syntax and semantics. Propositional and predicate logic.
2. Syntax of propositional formulas, elementary semantics: evaluations, satisfiability, tautologies, consequences. SAT Problem.
3. Propositional theories. Finite axiomatization. Compactness of propositional logic. Application: graph colorings.
4. Universal language of connectives. Normal forms. Karnaugh maps, minimalization.
5. The Hilbert proof system: language, axioms, deduction. Proofs. Correctness. The deduction theorem.
6. The completeness theorem. Decidability of propositional logic. Resolution.
7. The language of predicate logic, examples. Basic syntax: terms and formulas, quantifiers, free and bound variables, substitution.
8. Semantics: interpreting a languge, evaluating variables and terms. Truth in a structure. The role of free variables, sentences.
9. Theories and models. Isomorphisms and elementary equivalence. Submodels and elementary submodels.
10. The Hilbert proof system. Correctness. Equality. Complete theories.
11. Completeness of predicate logic. Compactness theorem; nonstanard models.
12. Boolean algebras, their relation to logic. The algebra of propositions. Ordering, atoms. Finite algebras.
 Syllabus of tutorials:

1. Formulas of propositional logic, truth values, tautologies, semantic consequence.
2. Reduced languages, universal connectives
3. normal forms, Boolean algebras
4. Hilbert formal system, formal proofs, deduction theorem, compactness.
5. Formulas of predicate logic, terms, quantifiers, substitutions.
6. Theories, proofs, and models.
 Study Objective:

The course introduces the formal system of predicate logic and shows its correctness and completeness,
providing a solid framework for building mathematical theories. Students taking this course should become proficient in using and applying the standard Hilbert system throughout mathematics.
 Study materials:

Barwise: Language, Proof and Logic
Kleene: Mathematical Logic
Kunen: Foundations of Mathematics
Mendelsohn: Introduction to Mathematical Logic
Tarski: Introduction to Logic
 Note:
 Further information:
 https://courses.fit.cvut.cz/BIEMLO/
 Timetable for winter semester 2018/2019:

06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon Tue Fri Thu Fri  Timetable for summer semester 2018/2019:
 Timetable is not available yet
 The course is a part of the following study plans:

 Bc Branch Security and Information Technology, Presented in English, Version 2015, 16, 17 and 18 (compulsory course in the program)
 Bc. Branch WSI, Specialization Software Engineering, Presented in English, Version 2015, 16, 17, 18 (compulsory course in the program)
 Bc. Branch Computer Science, Presented in English, Version 2015, 2016, 2017 and 2018 (compulsory course in the program)