上のＵＲＬはシラバスに掲載されている （念のために次ページに拡大表示します）

Presentation on theme: "上のＵＲＬはシラバスに掲載されている （念のために次ページに拡大表示します）"— Presentation transcript:

1 上のＵＲＬはシラバスに掲載されている （念のために次ページに拡大表示します）
２００８年度情報数学 （後藤滋樹 担当分） 2008年度の講義予定（後藤の担当は３回） （１）　5月19日(月) ブール代数と命題論理 （２）　5月26日(月) 述語論理と∀∃ （３）　6月2日(月) 　完全性と不完全性 講義資料（本資料を含む） 上のＵＲＬはシラバスに掲載されている （念のために次ページに拡大表示します）

2 http:// www.goto.info.waseda.ac.jp /~goto/infomath.html
URL の 拡大表示 /~goto/infomath.html

3 ２００７年度以前の「情報数学」 を再履修している諸君
今期の授業は２単位 再履修科目の「情報数学」は３単位 今期の授業で２単位を取得、残る１単位については上田和紀教授の指示に従う。 ・ 履修登録を正確な科目で行うこと ・ Waseda_netのquotaがオーバーしないように

4 参考書と使い方 本講義の内容は概ね次の書籍の1章の全部および2章の一部に相当する内容を扱う。 廣瀬健「論理」（現代応用数学の基礎） 日本評論社, ISBN 同書は現在「品切」と表示されている。 オンデマンド版が入手可能となるよう交渉中。 上の本では細部の説明が省略されている箇所がある。細部を補うには、次の本の第１章と第２章が参考になる。 小野寛晰「情報科学における論理」 日本評論社, ISBN

5 論理記号が書籍によって異なる この授業では次の記号を使う（ＪＩＳ第一水準漢字） ∧, ∨, ⇒, ⇔, ￢ , ∀, ∃.
この授業では次の記号を使う（ＪＩＳ第一水準漢字） ∧, ∨, ⇒, ⇔, ￢ , ∀, ∃. 第１回授業の開始時点では上の論理記号の意味が分からなくても差し支えない。 第１回授業の終了時には最初の５つの記号を理解していること。 第２回授業の終了時には残りの２つの記号を理解していること。

6 記号論理あるいは数理論理 廣瀬健先生の「論理」による導入： 数学的な議論の展開は、論理的な推論の積み重ねである。 論理学は、真な命題から真な命題を導く推論法則を研究する学問である。 論理的な推論を記号を用いて表現し、数学的な方法で研究する分野を、記号論理あるいは数理論理という。 記号論理： symbolic logic 数理論理： mathematical logic

7 論理記号の登場 廣瀬先生による導入の続き： 記号論理では、推論や推論の対象を記号で表現する。まず「概念」を記号で表現することが重要である。次に命題や述語で表現された概念の「正しさの説明＝証明」についての考察をする。 数学的理論では、基本概念を論理的な言葉で結びつけている。 「かつ」, 「あるいは」, 「ならば」, 「同値である」, 「～でない」, 「すべての…について…が成り立つ」, 「…を満たす…が存在する」.

8 論理記号の登場（２） ∧　かつ, conjunction ∨　あるいは, disjunction ⇒　ならば, implication ⇔　同値である, equivalence ￢ 　…でない, negation ∀　すべての…について…が成り立つ, universal ∃　…を満たす…が存在する existential いずれの記号も、具体的な使い方を後に学ぶ。

9 命題論理 　　　命題：proposition 命題とは、真偽が確定している文のこと。 例：　100 ≦ （真） は素数である （真） 平行な２直線は１点で交わる （偽） 原理的に確定していれば良い。 例： ２より大きな偶数は２つの素数の和で 表すことができる （Goldbachの予想） （？） 変数を含む文は、真偽を確定できない。 例： ｘ ≦ y は素数である （後に述語として登場）

10 真理値表 truth table 真（true）を t と表す。偽（false）を f と表す。 集合　T = { t, f }　とする。 φ : T  T を１変数（引数）の真理関数という。 φ : T×T  T を２変数（引数）の真理関数という。 論理記号 ∧, ∨, ⇒, ⇔ の意味は、２変数の真理関数として定義される。 論理記号 ￢ の意味は、１変数の真理関数として定義される。 真理関数： truth function 変数： argument （変数＝variable と区別） T×T は集合の直積（direct product, Cartesian product）

11 直積（デカルト積，Cartesian product）
Ａ×Ｂ ＝ { < a, b > | a∈Ａ，ｂ∈Ｂ } A の要素(元)と B の要素(元)の順序対の集合 集合の共通部分を「積集合」と呼ぶことがあるが別物 例： Ｔ×Ｔ ＝　{ < f, f >, < f, t >, < t, f >, < t, t >} Ｔは２つの要素からなる集合 Ｔ×Ｔは、４つの要素からなる集合 順序対であるから < f, t > と < t, f > を区別する

12 真理値表（２） A, Bは命題変数（ t または f の値を取る） A B A∧B A∨B A⇒B A⇔B f t A ￢A f t
真理値表（２）　 A, Bは命題変数（ t または f の値を取る） A B A∧B A∨B A⇒B A⇔B f t A ￢A f t A∧B を単独に書けば次の表 A B t f

13 論理回路 論理回路（ろんりかいろ）は、ブール代数(論理演算)を行う回路、およびデジタル信号を記憶する回路。 (出典: フリー百科事典『ウィキペディア（Wikipedia）』) AND Ａ・Ｂ ＯＲ　Ａ＋Ｂ ＮＯＴ　Ａ 論理回路の設計をする技術者は、数学の論理演算記号とは違う記号を用いて論理式を記述することが多い。(同上）

14 または（∨）, ならば（⇒） または（∨）　論理和 inclusive or : 紅茶　または　コーヒー 包含的論理和 exclusive or : 両方を取るのは駄目 排他的論理和 ならば（⇒）　含意 日常的な含意は、因果関係、 時間的な前後を意味する場合がある。 例： レポートを出さない ならば 成績が下がる 真理値表の含意は実質的(material)含意 例：　０＝１　ならば　私はローマ法王である（真） 排他的論理和 A B t f

15 論理式 (formula) の定義 個々の命題定数 t, f は、それ自身で論理式である 個々の命題変数は、それ自身で論理式である
A, B が論理式であるとき （A∧B）, （A∨B）, （A⇒B）, （A⇔B）, （￢A） は、いずれも論理式である 一番外側の括弧を省略して良い 否定記号は結合力が強いと見なして、（￢A）の 括弧を省略して良い 論理式の例示は後出

16 トートロジー (tautology) 恒真論理式
論理式 A に n 個の命題変数が含まれているとする。この時、個々の命題変数の真理値(t, f)の値の取り方は 2n 通りある。この 2n 通りの真理値のすべての場合に A が真となるとき、論理式 A をトートロジー、あるいは恒真(valid)な論理式という。 ある論理式 B がトートロジーであるかどうかを判定するには、B に含まれる命題変数の真理値のすべての組合せを列挙して、Aの真理値を計算すれば良い。（有限の手続きで判定可能）

17 基本的なトートロジー （A∧A）⇔A, （A∨A）⇔A 巾等律 （A∧（B∧C））⇔（（A∧B）∧C） 結合律
（A∧B）⇔（B∧A）, （A∨B）⇔（B∨A)　交換律 （A∧（A∨B））⇔A, （A∨（A∧B））⇔A　吸収律 （A∧（B∨C））⇔（（A∧B)∨（A∧C））　　分配律 （A∨（B∧C））⇔（（A∨B)∧（A∧C）） （￢（￢A）））⇔A　　　　　　　　二重否定の除去 （￢（A∨B））⇔（￢A∧￢B）　ド・モルガンの法則 （A⇒B）⇔（￢A∨B）　　　　　　含意記号の置換

18 トートロジーの判定法

19 充足可能な論理式 論理式 A に n 個の命題変数が含まれているとする。この時、個々の命題変数の真理値(t, f)の値の取り方は 2n 通りある。この 2n 通りの真理値のある取り方の場合に A が真となるとき、論理式 A を充足可能(satisfiable)な論理式という。 充足可能でない論理式を充足不可能(unsatisfiable)という 論理式Aが充足不可能であるための必要十分条件は論理式￢Aがトートロジーとなることである。

20 論理的に同値

21 標準形

22 Keywords(廣瀬) ブール代数 記号論理、命題論理、真理関数、論理記号 標準形、恒真論理式、命題計算、定理
述語論理、全称記号、存在記号、

23 Keywords（小野） ブール代数、 命題、論理式、真理値表、恒真、部分論理式、付値、充足可能性、同値、標準形
公理、推論規則、定理、証明、シンタックス、セマンティックス、健全性、完全性、双対性 述語論理、（命題論理）、全称記号、存在記号、論理式

24 述語論理と∀∃

25 完全性と不完全性