Mathematical Logic

Přednášející:

Kateřina Trlifajová (gar.)

Cvičící:

Kateřina Trlifajová (gar.)

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

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.

Požadavky:

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

Osnova přednášek:

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.

Osnova cvičení:

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.

Cíle studia:

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.

Studijní materiály:

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

Poznámka:

Rozsah=prednasky+proseminare+cviceni2p+1c, Prednasejici: RNDr. Kateřina Trlifajová Ph.D.

Rozvrh na zimní semestr 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
Po	místnost TH:A-1030 Trlifajová K. 09:15–10:45 (přednášková par. 1) Dejvicemístnost TH:A-1030 Trlifajová K. 11:00–12:30 LICHÝ TÝDEN (přednášková par. 1 paralelka 101) Dejvice
Út
St
Čt
Pá

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Information Systems and Management (povinný předmět programu)
• Information Technologies (povinný předmět programu)
• Computer Engineering (povinný předmět programu)
• Software Engineering (povinný předmět programu)
• Computer Science (povinný předmět programu)
• Web and Multimedia (povinný předmět programu)
• Informatics (povinný předmět programu)