### Mathematical Logic and Computability

#### Course Description

The course is divided into three parts. In the first part we consider propositional logic. The main aim of the first part is to emphasize the difference between syntax and semantics. The first part is a motivation and introduction for the second part in that we study first-order logic. Specially considered is the undecidability of first-order logic, and a necessity of a formal definition of algorithm is emphasized. In the third part we study theory of computation. RAM-machines are considered as a basic model of computation. Then we define the class of partial recursive function, and prove that the class of partial recursive functions is equal to the class of RAM-computable functions. It is a motivation for Church thesis.

#### Learning Outcomes

1. convert a formula of propositional logic to normal form
2. define a notion of proof and theorem
3. practice semantic tableux
4. reproduce the basic facts on modal logic
5. define a notion of first-order structure
6. convert a first-order formula to prenex normal form
7. define the notions of RAM-computable and partial recursive functions
8. classify the import of Church thesis

#### Forms of Teaching

Lectures

Lectures which contain large number of examples and problems.

Continuous Assessment Exam
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

1. The basic on set theory. Introduction to propositional logic. Syntax of propositional logic. Semantics of propositional logic.
2. Normal forms in propositional logic. Semantic tableux. Decidability. Problem P=NP.
3. Axiomatic system for propositional logic. Proof, theorem and deduction. Theorem of adequacy. Consistency.
4. A sketch of proof of completeness theorem for propositional logic.
5. Modal logic: system K, Kripke frame and model, theorems on completeness and adequacy of system K.
6. First-order logic: syntax of a first-order theory, terms and formulas.
7. Semantics of first order logic: interpretation, truth of formulas. Prenex normal form.
8. Midterm exam
9. Semantic tableux for first-order logic. Church theorem.
10. Axiomatic system for first-order logic. Proof, theorem and deduction. Theorem of deduction. Theorem od adequacy.
11. Consistency. A sketch of proof of Goedel completeness theorem. Compactness theorem.
12. Computability: RAM-machine, RAM-computable function. Macro-machine.
13. Primitive recursive functions: initial functions, composition, primitive recursion. Ackermann function. Partial recursive function. Recursive sets.
14. Proof that each partial recursive function is RAM-computable. Coding of finite sequence of natural numbers. Coding of RAM-machine. Universal function.
15. 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.

#### Study Programmes

Audio Technologies and Electroacoustics (profile)
Free Elective Courses (1. semester)
Communication and Space Technologies (profile)
Free Elective Courses (1. semester)
Computational Modelling in Engineering (profile)
Free Elective Courses (1. semester)
Computer Engineering (profile)
Free Elective Courses (1. semester) Mathematics and Science (1. semester)
Computer Science (profile)
Free Elective Courses (1. semester) Mathematics and Science (1. semester)
Control Engineering and Automation (profile)
Mathematics and Science (1. semester)
Control Systems and Robotics (profile)
Free Elective Courses (1. semester)
Data Science (profile)
Free Elective Courses (1. semester)
Electrical Engineering Systems and Technologies (profile)
Mathematics and Science (1. semester)
Electrical Power Engineering (profile)
Free Elective Courses (1. semester) Mathematics and Science (1. semester)
Electric Machines, Drives and Automation (profile)
Free Elective Courses (1. semester)
Electronic and Computer Engineering (profile)
Free Elective Courses (1. semester) Mathematics and Science (1. semester)
Electronics (profile)
Free Elective Courses (1. semester) Mathematics and Science (1. semester)
Information and Communication Engineering (profile)
Free Elective Courses (1. semester)
Information Processing (profile)
Mathematics and Science (1. semester)
Network Science (profile)
Free Elective Courses (1. semester)
Software Engineering and Information Systems (profile)
Elective Course of the Profile (1. semester) Mathematics and Science (1. semester)
Telecommunication and Informatics (profile)
Mathematics and Science (1. semester)
Wireless Technologies (profile)
Mathematics and Science (1. semester)

#### Literature

Mladen Vuković (2009.), Matematička logika, Element, Zagreb R. Cori, D. Lascar (2000.), Mathematical Logic, Part I,, Oxford University Press Michael Sipser (1997.), Introduction to the Theory of Computation, Course Technology Ptr
J. R. Shoefield (2017.), Recursion Theory, Cambridge University Press

#### General

ID 222646
Winter semester
5 ECTS
L3 English Level
L1 e-Learning
45 Lectures