SUBJECT

Logic and theory of computation

lecture + practical

bachelor

Faculty of Informatics

4

Semester 5

Autumn semester

The subject and the aim of logic. The most important mathematical tools. The notion of the language. Propositional logic: Description language and semantical properties of the formulas. Semantical notion of the consequence. Deduction theorem. Decision problems. Semantical/tautological equivalence. Laws of propositional logic. Formalization. Ways of inference. Problem solving. First-order logic. First-order and zero-order statements. Description language, signature. One- and many-sorted logic. Formalization by first-order formulas. Syntactical test of first-order formulas. Term substitution. Mathematical structure and it’s description language. Semantics, interpretation, and variable evaluation. Possible interpretation stuctures for a given universe U and a given signature. Truth table and value table of a formula. Basic expressions. Semantical notion of the consequence. Deduction theorem. Decision problems. Impossibility of the semantical solution. Logical equivalent rewriting of propositional formulas. Decision algorithm, deduction process. Conjunctive normal forms. Set of clauses and the semantical trees. Logical equivalent rewriting of first-order formulas. Prenex and Skolem formulas. The unsatisfiability of a first-order set of clauses. Herbrand universe. The resolution principle. Resolution strategies (Linear-, linear input-, unit resolution). Horn clauses. Horn logic. Complete deduction tree for the linear input strategy. Problem solving. The linear input strategy in connection with Prolog.

The computational and decision problems. The connection between a decidable problem and a formal language. Turing machine as algorithm model. The definition of the Turing machine and the recognized language. Multi tape and nondeterministic Turing machines. Time complexity. Decoding Turing machines in binary words. Undecidable problems concerning Turing machines: the diagonalization and the universal language, the halting problem. Turing machines computing functions on strings. Reductions. Further undecidable problems: PCP, ambiguity of CF grammars, validity of first-order formulas. The P and the NP complexity classes. Polinomial time reduction. NP-completeness. Cook’s theorem: SAT is NP-complete. Further NP-complete problems: variants of SAT, problems concerning graphs, Hamilton circle problem). The polinomial space and PSPACE-complete problems.

• M. Ben Ari: Mathematical logic for Computer Science, Springer 2001
• J. H. Gallier: Logic for Computer Science Wiley 1986
• Lecture notes of the part „Theory of computation” is available in electronic form on the web
• Pásztorné Varga Katalin, Várterész Magda: A matematikai logika alkalmazásszemléletű tárgyalása, 2003.

Recommended literature:

• C. L. Chang & R. C. T. Lee: Symbolic Logic and Mechanical Theorem Proving. 1973
• Ruzsa, I, Máté A. Bevezetés a modern logikába. 1997.
• M. Huth, M. Ryan: Logic in Computer Science Cambridge University Press, 2000
• Samuel D. Guttenplan, Martin Tamny: Logic, a Comprehensive Introduction, Basic Books,1971.
• Michael Sipser: Introduction to the Theory of Computation, 2006.
• J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation, 2003.
• C. H. Papadimitriou: Számítási Bonyolultság, 1999.
• Demetrovics János, Jordan Denev, Anton Pavlov: A számítástudomány matematikai alapjai, Tankönyvkiadó, Budapest, 1985.