Knowledge of basic parts of propositional and predicate logic (syntax, semantics, completeness). The aim is to deepen the knowledge of these parts, with emphasis on their completeness theorems and related notions in a way which ensures that students will be able to study other logical calculi or apply predicate logic in various fields of computer science (e.g., data analysis, relational databases). 1. Introduction and propositional logic The subject of logic: logic in focus of various disciplines, the evolution of logic, mathematical logic, logic as a formal method in computer science. Propositional logic; language of propositional logic, formulas, truth evaluation, truth of formulas, semantic entailment, tautologies, satisfiable formulas, normal forms, tabular methods. Axiomatic system of propositional logic: axioms, deduction rules, proofs, deduction theorem, replacement theorem, equivalence theorem, neutral formula theorem. Theories, consistency, soundness and (strong) completeness of propositional logic. 2. Basic notions of predicate logic Predicate logic: language, terms, formulas and basic syntactic notions; semantics: structures, valuations of variables, values of terms, truth values of formulas, tautologies, satisfiable formulas, semantic entailment and basic semantic notions, structures and models. Axiomatic system of predicate logic: axioms, deduction rules, proofs, deduction theorem, extensions of theorize, conservative extensions, constant introduction theorem, variants of formulas, consistency. 3. Completeness of predicate logic Soundness of predicate logic. Completeness of predicate logic: Henkin theory, Henkin extensions, complete theories. Completion of theories. Constructions of models form constants, canonical structure, completeness theorem. Compactness of predicate logic. Limitations of predicate logic: properties of structures that cannot be expressed through first-order formulas (e.g., finiteness of models). Prenex normal form, theorem of Hilbert and Ackermann, Herbrand theorem. 4. Selected negative results in logic. Incompleteness (Goedel numbering, arithmetization of logic, first Goedel incompleteness theorem), undecidabilicty (and decidability) of selected problems in logic. 5. Introduction to selected extensions of classical logic. Modal and temporal logics, fuzzy logics, probability logics.
|
-
Ben-Ari M. (2001). Mathematical Logic for Computer Science. Springer-Verlag, London (druhé vydání).
-
Chaitin G. J. (1998). The Limits of Mathematics. Springer-Verlag, Singapore (druhé vydání).
-
Mendelson E. (1997). Introduction to Mathematical Logic. Chapman & Hall, UK (fourth edition).
-
Nerode A., Shore R. A. (1997). Logic for Applications. Springer-Verlag, New York (second edition).
-
Sochor A. (2001). Klasická matematická logika. Karolinum, Praha.
-
Švejdar V. (2002). Logika: neúplnost, složitost a nutnost. Academia, Praha.
-
Zhongwan L. (1998). Mathematical Logic for Computer Science. World Scientific (druhé vydání).
|