計算機科学の基礎となる記号論理学と,計算可能性の理論について,入門的な講義を行う.
具体的には以下の項目について解説する.
記号論理学:
等式論理を用いた形式論理の導入,
命題論理の構文論と意味論,構造帰納法による証明,極大無矛盾集合による完全性証明
一階述語論理の構文論と意味論,Herbrandの定理
計算可能性の理論:
原子帰納的関数,帰納的関数,クリーネの標準形定理,
ゲーデルの不完全性定理
In this lecture, we introduce basic concepts of symbolic logic and computability theory.
The main topics are as follows.
Symbolic logic:
syntax and semantics of propositional logic, proofs by structural induction,
proofs of completeness by using a maximally consistent set,
syntax and semantics of first-order predicate logic, Herbrand's theorem
Computability theory:
primitive recursive functions, recursive functions, Kleene's normal form theorem,
Gödel's incompleteness theorems