数理論理学 |
Mathematical Logic |
開講部 | 工学部 |
開講学科 | 情報工学科 |
開講学年 | 2年次 |
開講時期 | 前期 |
単位数 | 2 |
単位区分 | 選択 |
系列区分 | 専門 |
講義区分 | 講義 |
講師 | 古宮誠一 | ![]() |
1. | この授業はHuntingtonの公理を用いて命題論理の論理体系を構築しているので, Huntingtonの公理を使って各種の公式を証明できること。 |
2. | 背理法による証明の仕組みを説明できること。 |
3. | 導出原理による証明の仕組みを理解していること。 |
【授業計画】 | 【予習内容】 | |
1. | Huntingtonの公理に基づく命題論理 命題とは何か,命題の例 Huntingtonの公理 否定に関する補助定理 | 独学は困難なので,予習は必ずしも必要ではない。よく復習して下さい。 特に,Huntingtonの公理とはどのようなものかを理解し,Huntingtonの公理を用いて,否定に関する補助定理を証明できるようにすること。 |
2. | ¬(否定),∧(論理積),∨(論理和)に関する基本公式 | 13個ある基本公式をHuntingtonの公理を用いて証明できるようにすること。特に,否定に関する補助定理を用いて証明する基本公式につては,よく復習しておくこと。 |
3. | ¬(否定),∧(論理積),∨(論理和)に関する基本公式(前回の続き) | 同上(特に,ドモルガンの定理を証明できるようにすること。) |
4. | →(含意)や≡(同値)に関する基本公式とその証明 | →(含意)や≡(同値)に関する基本公式を,すべて証明できるようにすること。 |
5. | 排他的論理和,NAND,NORに関する基本公式とその証明 | 排他的論理和,NAND,NORに関する基本公式を,すべて証明できるようにすること。 |
6. | 真理関数 命題変数,真理関数,トートロジー,等値 真理関数の表現定理とその証明 | 真理関数の表現定理は,自分では証明できなくてもよいが,証明を見ながら,その証明の過程を説明できるようにすること。 |
7. | 特別選言標準形 2変数の場合の基本連言 3変数の場合の基本連言 基本連言の組み合わせによる特別選言標準形 | 恒偽式を覗くすべての場合を,基本連言の組み合わせによる特別選言標準形で表現できることを説明できるようにすること。 |
8. | 特別連言標準形 2変数の場合の基本選言 3変数の場合の基本選言 基本選言の組み合わせによる特別連言標準形 | 恒等式(トートロジー)を覗くすべての場合を,基本連言の組み合わせによる特別選言標準形で表現できることを説明できるようにすること。 |
9. | 双対原理とその応用 双対性の定義 双対原理を証明するための補助定理とその証明 双対原理とその証明 双対原理の応用例 | 双対原理を証明するための補助定理は,自分では証明できなくてもよいが,証明を見て証明の過程を説明できるようにすること。 |
10. | 命題論理に対する種々の公理系 Hilbertの公理系 Lukasiewiczの公理系 | 命題論理に対する公理系がいろいろあることを理解すること。 種々の公理系がどのようなものから構成されいるかについて理解すること。 |
11. | 命題論理に対するHilbertの公理系による定理の証明例 条件付き三段論法の証明 排中律の証明 完全性定理の証明 | Hilbertの公理系を用いて,命題論理における定理を 自分では証明できなくてもよいが,証明を見て,証明の過程を説明できるようにすること。 |
12. | 述語論理に対するHilbertの公理系 述語の例 述語論理で用いられる記号 項の定義 論理式の定義 妥当な論理式とトートロジー 述語の意味論 述語論理におけるトートロジー Hilbert流の公理系 | Hilbertの公理系では,命題論理における種々の概念がどのように定義されているかを理解すること。 |
13. | ユニフィケーション | ユニフィケーションの考え方を理解し,説明できるようにすること。 |
14. | 導出原理 | 導出原理の考え方を理解し,説明できるようにすること。 |
15. | 導出原理による証明の事例 | 導出原理の考え方を理解し,その適用例を見て,導出原理の用い方について説明できるようにすること。 |
・ | 疑問があればいつでも良いから,研究室へ押しかけて質問すること。 |