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

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 この講義でカバーする内容 命題論理と述語論理 真理値と公理・推論規則・定理 命題論理 （真理値） （公理と推論規則） 述語論理
（モデルと解釈） １ ２ ３ 意味論　semantics syntax　構文論

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

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

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

13 真理値表（２） 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

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

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

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

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

18 基本的なトートロジー （A∧A）⇔A, （A∨A）⇔A 巾等律
（A∧（B∧C））⇔（（A∧B）∧C）,　　　結合律 （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） （A⇒B）⇔（￢A∨B）　　　　　　含意記号の置換

19 命題定数を含むトートロジー ￢ t ⇔ f, ￢ f ⇔ t （A∧t） ⇔ A, （A∨f） ⇔ A
（A∧f） ⇔ f, （A∨t） ⇔ t （A∧￢A） ⇔ f　 矛盾律, （A∨￢A） ⇔ t　 排中律 ￢A ⇔ （A⇒f）, A ⇔ （t⇒A） t の真理値は常に t である。f の真理値は常に f である。

20 トートロジーの判定法 ４左 ８ 論理式に含まれる命題変数の真理値のすべての組合せを列挙して、その論理式の真理値を計算する Ａ Ｂ Ａ∨Ｂ
Ａ∧（Ａ∨Ｂ） （A∧（A∨B））⇔A ｆ ｔ ４左 Ａ Ｂ Ａ⇒Ｂ ￢Ａ ￢Ａ∨Ｂ （A⇒B）⇔（￢A∨B） ｆ ｔ ８

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

22 論理和と論理積の拡張 n 個の論理式の論理和、論理積 命題変数、または命題変数の直前に否定記号が１つだけ付いた形の論理式をリテラルという

23 ni 論理式の標準形 論理和標準形 principal disjunctive form
注意 ni 論理積標準形 principal conjunctive form

24 ｊの範囲が ni　となる理由 i と j の動く範囲 ｊ □ i

25 論理和標準形（第１の方法） Ａ⇔Ｂを（Ａ⇒Ｂ）∧（Ｂ⇒Ａ）で置き換える ⇒を￢と∨で置き換える
否定￢が∧や∨の内側に現われるようにする （ド・モルガンの法則） 偶数個の￢を除去（二重否定の除去） 分配律を用いて、∧の内側に現われる∨を∧の外側に現れるようにする さらにトートロジーを用いて同値な論理式に変形してもよい

26 論理和標準形（例題） ￢（A⇒（B∧C））⇔￢（￢A∨（B∧C）） ⇔￢￢A∧￢（B∧C） ⇔A∧（￢B∨￢C） ⇔（A∧￢B）∨（A∧￢C） 論理和標準形、さらに次のように変形しても良い A∧￢B ⇔ ⇔A∧￢B∧t ⇔A∧￢B∧（C∨￢C ） ⇔（A∧￢B∧C）∨ （A∧￢B∧￢C ） ⇔ （A∧￢B∧C）∨ （A∧￢B∧￢C ）∨（A∧￢C） これも論理和標準形、標準形は一意に定まらない

27 論理和標準形（第２の方法） 論理式 A に命題変数 B1, B2, …, Bm が含まれているとき、論理式 A の真理値は命題変数の真理値に依存して決まる。 論理式 A の真理値が t となるような命題変数B1, B2, …, Bm の組合せが n 通りあるとする。 i番目（1≦i≦n）の組合せにおいて、命題変数Bj （1≦j≦m）の真理値が t の場合は Bj 自身をリテラルとする。Bj の真理値が f の場合は￢Bjをリテラルとする。

28 論理積標準形（例題） （A∧￢B∧￢C）∨（A∧￢B∧C）∨（A∧B∧￢C） A B C B∧C A⇒（B∧C） ￢（A⇒（B∧C）） f
t （A∧￢B∧￢C）∨（A∧￢B∧C）∨（A∧B∧￢C）

29 論理積標準形 論理積標準形を求める第１の方法は、分配律の （A∨（B∧C））⇔（（A∨B)∧（A∨C）） を使う他は論理和標準形と同じ。 つまり、∨の内側に現れる∧を、∨の外側に現れるようにする。 論理積標準形を求める第２の方法は、論理式 A の真理値が f となる組合せにおいて、Bjの真理値が t の場合は￢Bj をリテラルとし、 f の場合には Bj自身をリテラルにする。

30 論理記号の縮約 標準形では論理記号を３つだけ使う（∧, ∨, ￢）
さらにド・モルガンの法則を用いれば、論理記号は２つで済む（∧と￢, または ∨と￢）。 同様のことが（⇒と￢）の２つの論理記号に対しても成立つ。 さらに１つの記号でカバーすることもできる。 Sheffer stroke function　（NAND） A | B ＝ ￢（A∧B） Peirce function　 (NOR) A ↓ B ＝ ￢（A∨B）