Lecturer: 蔡益坤 Yih-Kuen Tsay

• Lecture 1: Elementary Logic (3 hours)
  1. propositional logic: syntax and semantics, satisfiability, tautology, normal forms, proofs, natural deduction, soundness, completeness, compactness, consistency
  2. first-order logic: syntax and semantics, validity, natural deduction, soundness, completeness, first-order theory
• Lecture 2: Elementary Computation Theory (3 hours)
  1. finite-state automata, nondeterminism, regular languages, context-free languages, pushdown automata
  2. Turing machines, decidability/undecidability, complexity, P, NP, coNP, PSPACE, reduction, completeness

• Elementary Logic [slides]
• Elementary Computation Theory [slides]
• Suggested solutions to homework assignment #1
• Suggested solutions to homework assignment #2

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.