# BIE-MLO – Mathematical Logic

### Annotation

Students learn to analyze text and understand it from the logic point of view, and to convert simple texts into a formal notation. Students can decide on the validity of logic formulas and prove them. They understand the difference between syntax and semantics of formal logics. They are able to work with axiomatic systems and know their basic properties. Students master Boolean algebra, both theoretically as a formal system and an instance of universal algebra, and practically as a tool to describe digital systems. They get skills needed to work with Boolean functions, normal forms, maps and minimization methods needed in other modules. They know a wider historical context of mathematical logic.

### Lectures Program

1. Examples of models and theories.
2. Importance of logic, history. Propositional logic. Formalization of natural language sentences. Basic notions: language, formula.
3. Semantics of propositional logic: values, truth tables. Tautology, contradiction, satisfiability, semantic consequence. Basic laws of propositional logic.
4. CNF and DNF, decomposition trees. Analysis of natural language text.
5. Boolean algebra. Boolean function minimization. Maps.
6. Syntax of propositional logic: Hilbert's axiomatic system. Formal proof, types of mathematical proofs.
7. Deduction theorem. Correctness and completeness. Compactness theorem.
8. Predicate logic. Formalization of natural language sentences. Basic notions: language, quantifier, term, formula.
9. Semantics of predicate logic: Tarski's truth definition. Validity of formulas, logically equivalent formulas, basic laws of predicate logic.
10. Interpretation, model, theory. Decomposition trees.
11. Logical analysis of natural language text. Prenex form of formulas.
12. Syntax of predicate logic: Hilbert's axiomatic system. Correctness and completeness.
13. Basic concepts of set theory: Actual and potential infinity, significance of sets, cardinality, continuum hypothesis, selection axiom, formal systems, independent statements.

### Labs Program

1. Formalization of simple statements in propositional logic.
2. Truth tables. Tautology, contradiction, satisfiability, semantic consequence.
3. CNF and DNF. Boolean algebra. Minimization, maps.
4. Decomposition trees. Analysis of natural language text.
5. Proofs in Hilbert's axiomatic system. Types of mathematical proofs.
6. Formalization of simple statements in predicate logic.
7. Three types of logical satisfiability in predicate logic.
8. Interpretation, model, theory. Decomposition trees.
9. Prenex form of formulas. Analysis of natural language text.
10. Examples of models and theories.
11. Correctness, consistency, completeness.
12. Set cardinality, isomorphisms.