Mathematical Logic and Computability
Basics of classical propositional logic, first-order logic and modal logic. Fundamental knowledge on computability and recursion theory. Experience in determination of normal forms, applying semantic tableux, and determination of recursivness of functions and sets.
- convert a formula of propositional logic to normal form
- define a notion of proof and theorem
- practice semantic tableux
- reproduce the basic facts on modal logic
- define a notion of first-order structure
- convert a first-order formula to prenex normal form
- define the notions of RAM-computable and partial recursive functions
- classify the import of Church thesis
Forms of Teaching
Lectures which contain large number of examples and problems.Exams
Mid-term and final exam during the lectures-free weeks.Consultations
At least once a week.Other
|Type||Threshold||Percent of Grade||Threshold||Percent of Grade|
|Homeworks||0 %||10 %||0 %||10 %|
|Mid Term Exam: Written||0 %||45 %||0 %|
|Final Exam: Written||0 %||45 %|
|Exam: Written||0 %||90 %|
Week by Week Schedule
- The basic on set theory. Introduction to propositional logic. Syntax of propositional logic. Semantics of propositional logic.
- Normal forms in propositional logic. Semantic tableux. Decidability. Problem P=NP.
- Axiomatic system for propositional logic. Proof, theorem and deduction. Theorem of adequacy. Consistency.
- A sketch of proof of completeness theorem for propositional logic.
- Modal logic: system K, Kripke frame and model, theorems on completeness and adequacy of system K.
- First-order logic: syntax of a first-order theory, terms and formulas.
- Semantics of first order logic: interpretation, truth of formulas. Prenex normal form.
- Midterm exam.
- Semantic tableux for first-order logic. Church theorem.
- Axiomatic system for first-order logic. Proof, theorem and deduction. Theorem of deduction. Theorem od adequacy.
- Consistency. A sketch of proof of Goedel completeness theorem. Compactness theorem.
- Computability: RAM-machine, RAM-computable function. Macro-machine.
- Primitive recursive functions: initial functions, composition, primitive recursion. Ackermann function. Partial recursive function. Recursive sets.
- Proof that each partial recursive function is RAM-computable. Coding of finite sequence of natural numbers. Coding of RAM-machine. Universal function.
- Kleene normal form theorem on partial recursive function. The equality of classes of RAM-computable function and partial recursive functions. Recursion theorem. Rice theorem. Church thesis. Halting problem. A sketch oof proof of Church theorem.