2010年度：論理学特論

講義メモ

これらのメモは適宜改訂しています．

• 命題論理の構文論
• 命題論理の意味論
• 命題論理の意味論のつづき
• 命題論理のタブロー
• 命題論理の健全性定理、終了した集合
• 命題論理の完全性定理（仮定集合が有限の場合）
• 命題論理の完全性定理（仮定集合が高々加算無限の場合）
• 命題論理の完全性定理（仮定集合が高々加算無限の場合）のつづき
• 述語論理の構文論
• 述語論理の構文論のつづき、述語論理の意味論
• 述語論理の意味論のつづき、述語論理のタブロー
• 述語論理の健全性定理
• 述語論理の完全性定理
• 関数記号と等号を持つ述語論理の構文論と意味論
• 同値関係と合同関係
• 等号と関数記号を持つ述語論理のタブロー、健全性定理、完全性定理
• コンパクト性定理の応用、ペアノ算術
• レジスター機械
• レジスター機械により計算可能な関数、ゲーデル数
• 高度レジスター機械、閉包定理
• 閉包定理
• 万能RMプログラム
• 停止問題、チャーチの定理

課題1

次の論理式のタブロー証明を与えよ．提出期限：5月13日．

• [¬p ⇒ q] ⇒ [[p ⇒ q] ⇒ q]
• [[[[p ⇒ q] ⇒ [¬r ⇒ ¬s]] ⇒ r] ⇒ t] ⇒ [[t ⇒ p] ⇒ [s ⇒ p]]

課題2

次の集合Hを根に持つ終了したタブローを示し、その終了した枝にもとづいてHのモデルを与えよ．提出期限：6月10日．

Last modified: 2010-12-18 15:54:08 JST