スライド 1 - GOTO Laboratory

2008年度情報数学
(後藤滋樹 担当分)
• 2008年度の講義予定(後藤の担当は3回)
(1) 5月19日(月) ブール代数と命題論理
(2) 5月26日(月) 述語論理と∀∃
(3) 6月2日(月) 完全性と不完全性
• 講義資料(本資料を含む)
http://www.goto.info.waseda.ac.jp/~goto/infomath.html
上のURLはシラバスに掲載されている
(念のために次ページに拡大表示します)
1
URL の 拡大表示
http://
www.goto.info.waseda.ac.jp
/~goto/infomath.html
2
2007年度以前の「情報数学」
を再履修している諸君
• 今期の授業は2単位
• 再履修科目の「情報数学」は3単位
• 今期の授業で2単位を取得、残る1単位につい
ては上田和紀教授の指示に従う。
その連絡がCourseN@viに登録したメールアドレ
スに届く。
・ 履修登録を正確な科目で行うこと
・ Waseda_netのquotaがオーバーしないように
3
参考書と使い方
• 本講義の内容は概ね次の書籍の1章の全部お
よび2章の一部に相当する内容を扱う。
廣瀬健「論理」(現代応用数学の基礎)
日本評論社, 1994. ISBN4-535-60829-6
同書は現在「品切」と表示されている。
オンデマンド版が入手可能となるよう交渉中。
• 上の本では細部の説明が省略されている箇所
がある。細部を補うには、次の本の第1章と第2
章が参考になる。
小野寛晰「情報科学における論理」
日本評論社, 1994. ISBN4-535-60814-8
4
論理記号が書籍によって異なる
• この授業では次の記号を使う(JIS第一水準漢字)
∧, ∨, ⇒, ⇔, ¬ ,
∀, ∃.
• 第1回授業の開始時点では上の論理記号の意味
が分からなくても差し支えない。
• 第1回授業の終了時には最初の5つの記号を理解
していること。
• 第2回授業の終了時には残りの2つの記号を理解
していること。
5
記号論理あるいは数理論理
• 廣瀬健先生の「論理」による導入:
数学的な議論の展開は、論理的な推論の積
み重ねである。
論理学は、真な命題から真な命題を導く推論
法則を研究する学問である。
論理的な推論を記号を用いて表現し、数学的
な方法で研究する分野を、記号論理あるいは
数理論理という。
• 記号論理: symbolic logic
数理論理: mathematical logic
6
論理記号の登場
• 廣瀬先生による導入の続き:
記号論理では、推論や推論の対象を記号で
表現する。まず「概念」を記号で表現すること
が重要である。次に命題や述語で表現された
概念の「正しさの説明=証明」についての考
察をする。
• 数学的理論では、基本概念を論理的な言葉
で結びつけている。
「かつ」, 「あるいは」, 「ならば」, 「同値である」,
「~でない」,
「すべての…について…が成り立つ」,
「…を満たす…が存在する」.
7
論理記号の登場(2)
∧ かつ,
conjunction
∨ あるいは,
disjunction
⇒ ならば,
implication
⇔ 同値である, equivalence
¬ …でない,
negation
∀ すべての…について…が成り立つ, universal
∃ …を満たす…が存在する.
existential
いずれの記号も、具体的な使い方を後に学ぶ。
8
命題論理
命題:proposition
• 命題とは、真偽が確定している文のこと。
例: 100 ≦ 200
(真)
17は素数である
(真)
平行な2直線は1点で交わる (偽)
• 原理的に確定していれば良い。
例: 2より大きな偶数は2つの素数の和で
表すことができる (Goldbachの予想) (?)
• 変数を含む文は、真偽を確定できない。
例: x ≦ 200
y は素数である
(後に述語として登場)
9
真理値表 truth table
• 真(true)を t と表す。偽(false)を f と表す。
集合 T = { t, f } とする。
φ : T  T を1変数(引数)の真理関数という。
φ : T×T  T を2変数(引数)の真理関数という。
• 論理記号 ∧, ∨, ⇒, ⇔ の意味は、2変数の真理関
数として定義される。
論理記号 ¬ の意味は、1変数の真理関数として
定義される。
• 真理関数: truth function
変数: argument
(変数=variable と区別)
T×T は集合の直積(direct product, Cartesian product)
10
直積(デカルト積,Cartesian product)
A×B = { < a, b > | a∈A,b∈B }
A の要素(元)と B の要素(元)の順序対の集合
集合の共通部分を「積集合」と呼ぶことがあるが別物
例:
T×T = { < f, f >, < f, t >, < t, f >, < t, t >}
Tは2つの要素からなる集合
T×Tは、4つの要素からなる集合
順序対であるから < f, t > と < t, f > を区別する
11
真理値表(2)
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
12
論理回路
• 論理回路(ろんりかいろ)は、ブール代数(論理演算)
を行う回路、およびデジタル信号を記憶する回路。
(出典: フリー百科事典『ウィキペディア(Wikipedia)』)
AND A・B
OR A+B
NOT A
• 論理回路の設計をする技術者は、数学の論理演算
記号とは違う記号を用いて論理式を記述することが
多い。(同上)
13
または(∨), ならば(⇒)
• または(∨) 論理和
inclusive or : 紅茶 または コーヒー
包含的論理和
exclusive or : 両方を取るのは駄目
A
排他的論理和
排他的論理和
B t
t
f
f
t
• ならば(⇒) 含意
日常的な含意は、因果関係、
時間的な前後を意味する場合がある。
例: レポートを出さない ならば 成績が下がる
真理値表の含意は実質的(material)含意
例: 0=1 ならば 私はローマ法王である(真)
f
t
f
14
論理式 (formula) の定義
1. 個々の命題定数 t, f は、それ自身で論理式である
2. 個々の命題変数は、それ自身で論理式である
3. A, B が論理式であるとき
(A∧B), (A∨B), (A⇒B), (A⇔B), (¬A)
は、いずれも論理式である
論理式の例示は後出
• 一番外側の括弧を省略して良い
• 否定記号は結合力が強いと見なして、(¬A)の
括弧を省略して良い
15
トートロジー (tautology)
恒真論理式
• 論理式 A に n 個の命題変数が含まれていると
する。この時、個々の命題変数の真理値(t, f)の
n
n
値の取り方は 2 通りある。この 2 通りの真理
値のすべての場合に A が真となるとき、論理式
A をトートロジー、あるいは恒真(valid)な論理式
という。
• ある論理式 B がトートロジーであるかどうかを判
定するには、B に含まれる命題変数の真理値の
すべての組合せを列挙して、Aの真理値を計算
すれば良い。(有限の手続きで判定可能)
16
基本的なトートロジー
(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))
6. (¬(¬A)))⇔A
二重否定の除去
7. (¬(A∨B))⇔(¬A∧¬B) ド・モルガンの法則
8. (A⇒B)⇔(¬A∨B)
含意記号の置換
1.
2.
3.
4.
5.
17
トートロジーの判定法
18
充足可能な論理式
• 論理式 A に n 個の命題変数が含まれているとする。
この時、個々の命題変数の真理値(t, f)の値の取り
方は 2n 通りある。この 2n 通りの真理値のある取り方
の場合に A が真となるとき、論理式 A を充足可能
(satisfiable)な論理式という。
• 充足可能でない論理式を充足不可能(unsatisfiable)
という
論理式Aが充足不可能であるための必要十分条件
は論理式¬Aがトートロジーとなることである。
19
論理的に同値
20
標準形
21
Keywords(廣瀬)
•
•
•
•
ブール代数
記号論理、命題論理、真理関数、論理記号
標準形、恒真論理式、命題計算、定理
述語論理、全称記号、存在記号、
22
Keywords(小野)
• ブール代数、
命題、論理式、真理値表、恒真、部分論理式、
付値、充足可能性、同値、標準形
• 公理、推論規則、定理、証明、シンタックス、
セマンティックス、健全性、完全性、双対性
• 述語論理、(命題論理)、全称記号、存在記
号、論理式
23
述語論理と∀∃
24
完全性と不完全性
25