Elementary Logic and Computation Theory


  • 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

Course Materials



  • 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.
zh-tw/lecture/logic.txt · 上一次變更: 2011/04/29 04:45 來自 mht208