L0980800

数理論理学

Mathematical Logic

開講部

工学部

開講学科

情報工学科

開講学年

2年次

開講時期

前期

単位数

2

単位区分

選択

系列区分

専門

講義区分

講義
講師古宮誠一この先生のアンケート一覧を参照

授業の概要

数学のあらゆる分野に共通して用いられる理論的な推論を、数学的な記号法を用いて研究する,数学あるいは論理学の1部門を、記号論理学または数理論理学と呼ぶ。そして、数理論理学の中でも、命題結合記号と呼ばれる∧(かつ)、∨(または)、→(ならば),−(否定),≡(同値)の5つの論理記号だけに着目して研究する範囲を命題論理と呼び、これらに加えて、∀(すべての)という全称記号と、∃(存在する)という存在記号をも含めて考える範囲を述語論理と呼ぶ。
この授業では、命題論理と1階の述語論理のみを対象にし、高階の述語論理は対象としない。なお、計算機科学の研究では避けて通れない、古典論理学と、形式主義論理学(有限の立場)や直観主義論理学との立場の違いについても言及する。

達成目標

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.導出原理による証明の事例導出原理の考え方を理解し,その適用例を見て,導出原理の用い方について説明できるようにすること。

評価方法と基準

期末試験によって,成績を評価する。

教科書・参考書

教科書: 町田 元,横森 貴 共著 「計算機数学」 森北出版 2000円+税
参考書: 入江盛一著 「数理論理学入門」(培風館) 2500円+税
参考書: ピータグレイ著 田中穂積・徳永健一翻訳 「論理・代数・データベース ?知の工学の基礎?」(産業図書) 3300円+税

履修登録前の準備

離散数学1を履修していることが望ましい。

オフィスアワー、質問・相談の方法

疑問があればいつでも良いから,研究室へ押しかけて質問すること。

環境との関連

環境に関連しない科目

最終更新 : Thu Sep 19 07:32:26 JST 2013