Lecturer: 蔡益坤 Yih-Kuen Tsay
- 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
- 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.
- 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.