Table of Contents

# Elementary Logic and Computation Theory

Lecturer: 蔡益坤 Yih-Kuen Tsay

# Syllabus

- Lecture 1: Elementary Logic (3 hours)
- propositional logic: syntax and semantics, satisfiability, tautology, normal forms, proofs, natural deduction, soundness, completeness, compactness, consistency
- first-order logic: syntax and semantics, validity, natural deduction, soundness, completeness, first-order theory

- Lecture 2: Elementary Computation Theory (3 hours)
- finite-state automata, nondeterminism, regular languages, context-free languages, pushdown automata
- Turing machines, decidability/undecidability, complexity, P, NP, coNP, PSPACE, reduction, completeness

# Course Materials

# References

**Logic**

- J.H. Gallier.
*Logic for Computer Science: Foundations of Automatic Theorem Proving*, Harper & Row Publishers, 1985. - J. Goubault-Larrecq and I. Mackie.
*Proof Theory and Automated Deduction*, Kluwer Academic Publishers, 1997. - M. Huth and M. Ryan.
*Logic in Computer Science: Modelling and Reasoning about Systems*, Cambridge University Press, 2004.

**Computation Theory**

- M. Sipser.
*Introduction to the Theory of Computation*, Thomson Course Technology, 2006. - C.H. Papadimitriou.
*Computational Complexity*, Addison-Wesley, 2003. - J.E. Hopcroft and J.D. Ullman.
*Introduction to Automata Theory, Languages, and Computation*, Addison-Wesley, 1979.