スライド 1 - GOTO Laboratory

２００８年度情報数学
（後藤滋樹担当分）
• 2008年度の講義予定（後藤の担当は３回）
（１） 5月19日(月) ブール代数と命題論理
（２） 5月26日(月) 述語論理と∀∃
（３） 6月2日(月) 完全性と不完全性
• 講義資料（本資料を含む）
http://www.goto.info.waseda.ac.jp/~goto/infomath.html
上のＵＲＬはシラバスに掲載されている
（念のために次ページに拡大表示します）
1
URL の拡大表示
http://
www.goto.info.waseda.ac.jp
/~goto/infomath.html
2
２００７年度以前の「情報数学」
を再履修している諸君
• 今期の授業は２単位
• 再履修科目の「情報数学」は３単位
• 今期の授業で２単位を取得、残る１単位につい
ては上田和紀教授の指示に従う。
その連絡がCourseN@viに登録したメールアドレ
スに届く。
・履修登録を正確な科目で行うこと
・ Waseda_netのquotaがオーバーしないように
3
参考書と使い方
• 本講義の内容は概ね次の書籍の1章の全部お
よび2章の一部に相当する内容を扱う。
廣瀬健「論理」（現代応用数学の基礎）
日本評論社, 1994. ISBN4-535-60829-6
同書は現在「品切」と表示されている。
オンデマンド版が入手可能となるよう交渉中。
• 上の本では細部の説明が省略されている箇所
がある。細部を補うには、次の本の第１章と第２
章が参考になる。
小野寛晰「情報科学における論理」
日本評論社, 1994. ISBN4-535-60814-8
4
論理記号が書籍によって異なる
• この授業では次の記号を使う（ＪＩＳ第一水準漢字）
∧, ∨, ⇒, ⇔, ￢ ,
∀, ∃.
• 第１回授業の開始時点では上の論理記号の意味
が分からなくても差し支えない。
• 第１回授業の終了時には最初の５つの記号を理解
していること。
• 第２回授業の終了時には残りの２つの記号を理解
していること。
5
記号論理あるいは数理論理
• 廣瀬健先生の「論理」による導入：
数学的な議論の展開は、論理的な推論の積
み重ねである。
論理学は、真な命題から真な命題を導く推論
法則を研究する学問である。
論理的な推論を記号を用いて表現し、数学的
な方法で研究する分野を、記号論理あるいは
数理論理という。
• 記号論理： symbolic logic
数理論理： mathematical logic
6
論理記号の登場
• 廣瀬先生による導入の続き：
記号論理では、推論や推論の対象を記号で
表現する。まず「概念」を記号で表現すること
が重要である。次に命題や述語で表現された
概念の「正しさの説明＝証明」についての考
察をする。
• 数学的理論では、基本概念を論理的な言葉
で結びつけている。
「かつ」, 「あるいは」, 「ならば」, 「同値である」,
「～でない」,
「すべての…について…が成り立つ」,
「…を満たす…が存在する」.
7
論理記号の登場（２）
∧ かつ,
conjunction 論理積
∨ あるいは,
disjunction 論理和
⇒ ならば,
implication 含意
⇔ 同値である, equivalence 同値
￢ …でない,
negation
否定
∀ すべての…について…が成り立つ, universal
∃ …を満たす…が存在する.
existential
いずれの記号も、具体的な使い方を後に学ぶ。
8
この講義でカバーする内容
• 命題論理と述語論理
• 真理値と公理・推論規則・定理
１
命題論理
（真理値）
命題論理
（公理と推論規則）
３
２
述語論理
（モデルと解釈）
意味論 semantics
述語論理
（公理と推論規則）
syntax 構文論
9
命題論理
命題：proposition
• 命題とは、真偽が確定している文のこと。
例： 100 ≦ 200
（真）
17は素数である
（真）
平行な２直線は１点で交わる（偽）
• 原理的に確定していれば良い。
例：２より大きな偶数は２つの素数の和で
表すことができる（Goldbachの予想）（？）
• 変数を含む文は、真偽を確定できない。
例：ｘ ≦ 200
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 f
f
f
t
t
f t
f
t
t
f
t f
f
t
f
f
t t
t
t
t
t
A ￢A
f t
t f
A∧B を単独に書けば次の表
A
B t
t
t
f
f
f
f
f
13
論理回路
• 論理回路（ろんりかいろ）は、ブール代数(論理演算)
を行う回路、およびデジタル信号を記憶する回路。
(出典: フリー百科事典『ウィキペディア（Wikipedia）』)
AND Ａ・Ｂ
ＯＲＡ＋Ｂ
ＮＯＴＡ
• 論理回路の設計をする技術者は、数学の論理演算
記号とは違う記号を用いて論理式を記述することが
多い。(同上）
14
または（∨）, ならば（⇒）
• または（∨）論理和
inclusive or : 紅茶またはコーヒー
包含的論理和
exclusive or : 両方を取るのは駄目
A
排他的論理和
排他的論理和
B t
t
f
f
t
• ならば（⇒）含意
日常的な含意は、因果関係、
時間的な前後を意味する場合がある。
例：レポートを出さないならば成績が下がる
真理値表の含意は実質的(material)含意
例：０＝１ならば私はローマ法王である（真）
f
t
f
15
論理式 (formula) の定義
1. 個々の命題定数 t, f は、それ自身で論理式である
2. 個々の命題変数は、それ自身で論理式である
3. A, B が論理式であるとき
（A∧B）, （A∨B）, （A⇒B）, （A⇔B）, （￢A）
は、いずれも論理式である
論理式の例示は後出
• 一番外側の括弧を省略して良い
• 否定記号は結合力が強いと見なして、（￢A）の
括弧を省略して良い
16
トートロジー (tautology)
恒真論理式
• 論理式Ａに n 個の命題変数が含まれていると
する。この時、個々の命題変数の真理値(t, f)の
n
n
値の取り方は 2 通りある。この 2 通りの真理
値のすべての場合にＡが真となるとき、論理式
Ａをトートロジー、あるいは恒真(valid)な論理式
という。
• ある論理式Ｂがトートロジーであるかどうかを判
定するには、Ｂに含まれる命題変数の真理値の
すべての組合せを列挙して、Ｂの真理値を計算
すれば良い。（有限の手続きで判定可能）
17
基本的なトートロジー
1. （A∧A）⇔A,
（A∨A）⇔A
巾等律
2. （A∧（B∧C））⇔（（A∧B）∧C）,
結合律
（A∨（B∨C））⇔（（A∨B）∨C）
3. （A∧B）⇔（B∧A）, （A∨B）⇔（B∨A) 交換律
4. （A∧（A∨B））⇔A, （A∨（A∧B））⇔A 吸収律
5. （A∧（B∨C））⇔（（A∧B)∨（A∧C））, 分配律
（A∨（B∧C））⇔（（A∨B)∧（A∨C））
6. （￢（￢A）））⇔A
二重否定の除去
7. （￢（A∨B））⇔（￢A∧￢B）, ド・モルガンの法則
（￢（A∧B））⇔（￢A∨￢B）
8. （A⇒B）⇔（￢A∨B）
含意記号の置換
18
命題定数を含むトートロジー
￢ t ⇔ f,
￢f⇔t
（A∧t） ⇔ A, （A∨f） ⇔ A
（A∧f） ⇔ f,
（A∨t） ⇔ t
（A∧￢A） ⇔ f
矛盾律,
（A∨￢A） ⇔ t
排中律
13. ￢A ⇔ （A⇒f）, A ⇔ （t⇒A）
9.
10.
11.
12.
t の真理値は常に t である。f の真理値は常に f である。
19
トートロジーの判定法
• 論理式に含まれる命題変数の真理値のすべての組合せを列挙
して、その論理式の真理値を計算する
４左
ＡＢＡ∨Ｂ
ｆｆ
ｆ
ｔｆ
ｔ
ｆ
ｔ
８
ｔ
ｔ
Ａ∧（Ａ∨Ｂ）
ｆ
ｔ
ｔ
ｔ
ｆ
ｔ
ｔ
ｔ
ＡＢＡ⇒Ｂ￢Ａ￢Ａ∨Ｂ
ｆｆ
ｔ
ｔ
ｔ
ｔ
ｆ
ｔ
ｆ
ｔ
ｔ
ｆ
ｔ
ｔ
（A∧（A∨B））⇔A
ｔ
ｔ
ｆ
ｔ
ｆ
ｆ
ｔ
ｔ
（A⇒B）⇔（￢A∨B）
ｔ
ｔ
ｔ
ｔ
20
充足可能な論理式
• 論理式 A に n 個の命題変数が含まれているとする。
この時、個々の命題変数の真理値(t, f)の値の取り
方は 2n 通りある。この 2n 通りの真理値の取り方の
中で１つ以上の取り方において A が真となるとき、
論理式 A を充足可能(satisfiable)な論理式という。
• 充足可能でない論理式を充足不可能(unsatisfiable)
という
論理式Aが充足不可能であるための必要十分条件
は論理式￢Aがトートロジーとなることである。
21
論理和と論理積の拡張
• n 個の論理式の論理和、論理積
A1  A2    Am を
B1  B2    Bn を
m
A
i
i 1
n
B
i 1
i
と書く
と書く
• 命題変数、または命題変数の直前に否定記号
が１つだけ付いた形の論理式をリテラルという
A,  B
22
論理式の標準形
• 論理和標準形 principal disjunctive form
任意の論理式 A に対して
m ni
A    L i j がトートロジーとなる
注意
ような
i 1 j 1
リテラル
ni
L i j が存在する。
• 論理積標準形 principal conjunctive form
任意の論理式 B に対して
m
ni
B    M i j がトートロジーとなる
ような
i 1 j 1
リテラル
M i j が存在する。
23
ｊの範囲が ni となる理由
i と j の動く範囲
ｊ
□ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □
i
□ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □
24
論理和標準形（第１の方法）
1. Ａ⇔Ｂを（Ａ⇒Ｂ）∧（Ｂ⇒Ａ）で置き換える
2. ⇒を￢と∨で置き換える
3. 否定￢が∧や∨の内側に現われるようにする
（ド・モルガンの法則）
4. 偶数個の￢を除去（二重否定の除去）
5. 分配律を用いて、∧の内側に現われる∨を∧の
外側に現れるようにする
6. さらにトートロジーを用いて同値な論理式に変
形してもよい
25
論理和標準形（例題）
￢（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）
これも論理和標準形、標準形は一意に定まらない
26
論理和標準形（第２の方法）
• 論理式 A に命題変数 B1, B2, …, Bm が含まれて
いるとき、論理式 A の真理値は命題変数の真理
値に依存して決まる。
• 論理式 A の真理値が t となるような命題変数B1,
B2, …, Bm の組合せが n 通りあるとする。
• i番目（1≦i≦n）の組合せにおいて、命題変数Bj （
1≦j≦m）の真理値が t の場合は Bj 自身をリテラ
ルとする。Bj の真理値が f の場合は￢Bjをリテラ
ルとする。
27
論理積標準形（例題）
f
t
f
t
B∧C
f
f
f
t
A⇒（B∧C）
t
t
t
t
￢（A⇒（B∧C））
f
f
f
f
f
f
t
f
t
f
f
f
f
f
f
f
t
t
t
t
t
t
t
f
A
B
C
f
f
f
f
f
f
t
t
t
t
t
t
（A∧￢B∧￢C）∨（A∧￢B∧C）∨（A∧B∧￢C）
28
論理積標準形
• 論理積標準形を求める第１の方法は、分配律の
（A∨（B∧C））⇔（（A∨B)∧（A∨C））を使う他は論理
和標準形と同じ。
つまり、∨の内側に現れる∧を、∨の外側に現れる
ようにする。
• 論理積標準形を求める第２の方法は、論理式 A
の真理値が f となる組合せにおいて、Bjの真理
値が t の場合は￢Bj をリテラルとし、 f の場合に
は Bj自身をリテラルにする。
29
論理記号の縮約
• 標準形では論理記号を３つだけ使う（∧, ∨, ￢）
• さらにド・モルガンの法則を用いれば、論理記号
は２つで済む（∧と￢, または ∨と￢）。
• 同様のことが（⇒と￢）の２つの論理記号に対し
ても成立つ。
• さらに１つの記号でカバーすることもできる。
Sheffer stroke function （NAND）
A | B ＝￢（A∧B）
Peirce function (NOR)
A ↓ B ＝￢（A∨B）
30

Download Report