Mathematical Logic

Lecturer:

Kateřina Trlifajová (gar.)

Tutor:

Kateřina Trlifajová (gar.)

Supervisor:

Department of Applied Mathematics

Synopsis:

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.

Requirements:

Ability to work with mathematical abstractions at a high-school level.

Syllabus of lectures:

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.

Syllabus of tutorials:

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.

Study Objective:

The module aims to show why it is useful to use formulas of propositional and predicate calculus instead of natural language in mathematics, how to formalize the notions of truth and provability, and how to work with axiomatic systems. Boolean algebra is presented as an example of mathematical theory and as a tool for describing digital systems. Standard methods of minimizing Boolean functions are also described.

Study materials:

1. Ben-Ari, M. ''Mathematical Logic for Computer Science.'' Springer, 2008. ISBN 1852333197.

Note:

Time-table for winter semester 2011/2012:

	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	roomTH:A-1030 Trlifajová K. 09:15–10:45 (lecture parallel1) DejviceroomTH:A-1030 Trlifajová K. 11:00–12:30 ODD WEEK (lecture parallel1 parallel nr.101) Dejvice
Tue
Fri
Thu
Fri

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Information Systems and Management (Presented in English) (compulsory course in the program)
• Information Technologies (Presented in English) (compulsory course in the program)
• Computer Engineering (Presented in English) (compulsory course in the program)
• Software Engineering (Presented in English) (compulsory course in the program)
• Computer Science (Presented in English) (compulsory course in the program)
• Web and Multimedia (Presented in English) (compulsory course in the program)
• Informatics (Presented in English) (compulsory course in the program)