- Description:
-
An introduction to propositional and predicate logic.
- Contents:
-
1. Introduction. Propositional logic. Truth tables.
2. Satisfiability, tautology, contradiction. Logical equivalence. Basic laws of propositional logic. Complete systems of connectives.
3. Logical consequence. Disjunctive and conjunctive normal form. Full normal forms.
4. Theory and its logical consequences. Semantic trees. Resolution method.
5. Karnaugh maps. Compactness theorem. P vs. NP problem.
6. Predicate logic. Language, terms, formulas. Formalization of natural language.
7. Interpretation of the language. Logical truth, satisfiability, contradiction. Logical consequence and equivalence.
8. Semantic trees. Basic laws of predicate logic. The problem of decidability.
9. Prenex normal forms. Theories and its models. Isomorphism and elementary equivalence.
10. Examples of the first-order theories.
11. Boolean algebra. Models of Boolean algebra.
12. The isomorphism theorem. Correctness, completeness and consistenc
- Seminar contents:
-
1. Formalization. Truth tables.
2. Satisfiability, tautology, contradiction. Logical equivalence. Universal systems of connectives.
3. Disjunctive and conjunctive normal forms. Full normal forms.
4. Logical consequence. Semantic trees. Satisfiable theories.
5. Resolution method. Karnaugh maps.
6. Predicate logic. Language, terms, formulas.
7. Interpretations. Logical truth, satisfiability, contradiction.
8. Logical consequence and equivalence.
9. Semantic trees. Logical consequence of a theory.
10. Theories and their models, equivalence, ordering, group theory.
11. Boolean algebras.
12. Repetition.
- Recommended literature:
-
Mendelson, E., Introduction to Mathematical Logic, Chapman and Hall, 1997.
Bergmann, M., Moor, J., Nelson, The Logic Book, McGraw-Hill, 2008.
Copi, I.M., Symbolic Logic, The Macmilian Company, London, 1967.
Smullyan, R., What is the Name of this Book?
Demlová, M., Mathematical Logic, ÈVUT, Praha: Kernberg Publishing, 2008.
Starŭ, J., lecture notes (in progress).
Smith, N.J.J., Logic: The Laws of Truth, Princeton University Press, 2012.
Smith, N.J.J., Cusbert J., Logic: The Drill, http://www-personal.usyd.edu.au/~njjsmith/lawsoftruth/
- Keywords:
- propositional logic, predicate logic, semantic truth, theory, model, Boolean algebra, Karnaugh maps, semantic trees
Abbreviations used:
Semester:
- W ... winter semester (usually October - February)
- S ... spring semester (usually March - June)
- W,S ... both semesters
Mode of completion of the course:
- A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
- GA ... Graded Assessment (a grade is awarded for this course)
- EX ... Examination (a grade is awarded for this course)
- A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)
Weekly load (hours per week):
- P ... lecture
- C ... seminar
- L ... laboratory
- R ... proseminar
- S ... seminar