計算機基礎論

命題論理

(教科書：3.1～3.5)

藤田 聡 (広島大学)

ガイドライン

命題論理(今週) – 「AならばBである」という形の論理式を用い て推論を行う(例：否定、論理和、論理積) – 事実の集まりから、求めたい結論を正しく導 けるかを問う(参考：推理小説) 述語論理(次週) – 命題論理で表現されることに加えて、「すべ ての何某について」という表現が許された論 理体系 – 「すべての整数について」という表現も可

今日の授業内容

「命題」がどのようなものかを理解する 命題論理で用いられる基本演算子 含意について正しく理解する(真理値表) – 逆、裏、対偶、必要十分条件 「命題的同値」という考え方を理解する – 「必要十分」という考え方がわかることが重要

風が吹くと

…

• 風が吹くと砂ぼこりが出る • 砂ぼこりが出ると盲人がふえる • 盲人は三味線をひくのでそれに張る猫の 皮が必要で猫が減る • 猫が減ると、鼠がふえて桶をかじる • 桶がかじられると桶屋が繁盛する 風が吹くと桶屋が儲かる(⇒ 命題論理)

命題

(proposition)

とは？

• 真(true)か偽(false)かどちらかであるよ うな言明のこと – 言明(ある事実を述べた文； statement) • 例)日本の首都は名古屋である • 例)5342×263 = 1404946 • 例)広島大学にはトイレが185箇所ある • 例)ｘ＋ｙ＝ｚである

記法

• 命題を p, q, r, s などの記号であらわす • 命題の真理値(truth value)は真(T)か偽(F)であ る • 命題を取り扱う論理を命題論理(propositional logic)と呼ぶ あるいくつかの命題から 新しい命題をつくることを考える (論理演算子：3.2節)

否定

(negation)

いまpを命題とする ￢pを“pではない”ことを主張する言明 であると定義する(“not p”と読む) ￢pが命題であることに注意 pと￢pの関係は真理値表(truth table)で表 現できる

否定

(negation)

真理値表 p ￢p T F F T pの真理値がTの とき、￢pの真理 値がFになること を示している

例

p 今日は水曜日である ￢p 今日は水曜日ではない 「「今日は水曜日である」のではない」でもOK 実際は「今日」がいつであるかによってこの言明の 真理値は変わるため、厳密にはこれは「命題」ではない

結合子

(connective)

• 二つ以上の命題からひとつの命題を作り 出すための演算子

(a) 論理積(conjunction)

• いまp,qを命題とする • p∧qを「pかつq」であることを主張す る言明であると定義する p きょうは金曜日 q きょうは13日 p∧q きょうは13日の金曜日

(b) 論理和(disjunction)

• いまp,qを命題とする • p∨qを「pまたはq」であることを主張 する言明であると定義する p きょうは金曜日 q きょうは13日 p∨q きょうは13日または金曜日 注意：両方ともTであってもよいことに注意。つまり１３日の金曜日はＯＫ

(c) 排他的論理和(exclusive or)

• いまp,qを命題とする • p

⊕

qを「pまたはqのいずれか一方のみ がT」であることを主張する言明と定義 p きょうは金曜日 q きょうは13日 p

⊕

q ??? 注意：１３日の金曜日はNG

(d) 含意(implication)

あるいは条件式 • いまp,qを命題とする • p→qを「pならばq」であることを主張 する言明であると定義する • pを仮定(hypothesis)又は前提(premise) と呼び、qを結論(conclusion)または帰 結(consequence)と呼ぶ

含意

• 真理値表は右の通り • 仮定がＦならば結論 によらずTになる！ p q p→q T T T T F F F T T F F T

含意をあらわす英文

• 英文で以下のように記述されているのは すべてp→qの意味である: • if p, (then) q • p implies q • p is sufficient for q (pはqの十分条件) • q is necessary for p (qはpの必要条件)

例

p： きょうは13日の金曜日 q： きょうは金曜日

のとき

例

p： 2＋3＝6

q： この授業では皆に「優」がでる のとき

逆と対偶

p→qに対して、 • q→pを逆(converse) • ￢p→￢qを裏(reverse) • ￢q→￢pを対偶(contrapositive) と言う(逆は裏の対偶：確認せよ)

逆と対偶

高いところから落ちると怪我をする 逆：怪我をしたのは、高いところから 落ちたからだ 裏：高いところから落ちないと、怪我 をすることはない 対偶：怪我をしていないのであれば、 その人は高いところから落ちていない けがをする 原因はほか にもある

対偶の真理値表

p q pq ￢p ￢q ￢q ￢p T T T F F T T F F F T F F T T T F T F F T T T T

必要十分条件

ちなみに、(p→q)∧(q→p)は、 • p if and only if q

• p is necessary and sufficient for q (pはqの必要十分条件)

p↔q の真理値表

p q pq qp (pq) ∧(qp) T T T T T T F F T F F T T F F F F T T T

• p↔qは、pとqの真理値が等しいときにT • したがって(pq)↔(￢q￢p) は、p, qの 真理値によらずつねにT • このことから、 ↔ のことを、同等、あるい は同値(equivalent)と呼ぶ

同値

例

p q p∨q p∧q (p∨q)↔(p∧q) T T T T T T F T F F F T T F F F F F F T

命題的同値とは？

(propositional Equivalence)  複合命題(compound proposition)がそれを構成す る命題の真理値にかかわらず常に真となるとき、 これを恒真(命題)(tautology)であるという  逆に常に偽であるとき矛盾(contradiction)である という  複合命題p↔qが恒真であるとき、pはqに論理的 に同値(logically equivalent)と呼び，このとき p⇔qと表記する

例

)

(

)

(

p



q





q





p

p

p





p

p





恒真命題 矛盾 恒真命題

例

p q ￢ (p∨q) ￢ p∧￢ q T T F F T F F F F T F F F F T T

例

• したがって ￢(p∨q)↔ ￢p∧￢q は恒真で あるから、これら２つの命題は論理的に 同値であり、 ￢ (p∨q) ⇔￢p∧￢q

• ドモルガンの法則(de Morgan’s law) • ￢ (p∧q) ⇔￢p∨￢q

恒真であることの意味

① p⇔q_１⇔…⇔q_ｎ⇔r ならばp⇔r したがってpの真理値をr に単純化して得 ることができる ② rが恒真ならばrは正しい推論を示してい る。たとえば(p→q)↔(￢q→￢p)は恒真で あるが、 p→qから￢q→￢pを推論するこ とができる

例 分配則

p∨(q∧r)⇔ (p∨q)∧(p∨r) p∧(q∨r) ⇔ (p∧q)∨(p∧r)

• p,q,rのすべての組み合わせに対して、真 理値表をチェックすること!!

恒真かどうかの判定方法

• 任意に与えられた命題の真理値表は計算 できる • したがって与えられた命題が恒真かどう かは真理値表をつかっても判定できる • 具体的には，p⇔Tが示せれば恒真、p⇔F が示せれば矛盾

背理法による証明

• p→q⇔Tを証明するために， • p∧￢q⇔Fを証明している

• p→q⇔￢p∨q⇔￢(p∧￢q)に注意すると， (p→q)↔ T ⇔ (p∧￢q)↔ F

述語論理

～述語と限定作用素～

(

教科書：3.9～3.11)

藤田 聡 (広島大学)

これまでのまとめ

(１)

命題論理(propositional logic)について述べた 命題変数(propositional variable)と呼ばれる任 意の命題をあらわす変数だけを素論理式とし、 結合子だけによってつくられる論理式だけが 考察の対象であった 特に、どのような論理式が恒真であるかに興 味があった

これまでのまとめ

(２)

論理式の真理値表は容易に計算できるため、 論理式F の恒真性は容易にチェックできる もうひとつの方法として、⇔で結ばれた関係 をたどり、F ⇔Tを導くことによっても式F の恒真性がチェックできる 「変数」という概念を新たに導入 ⇒述語論理

述語

(predicate)とは？

命題関数

(propositional Function)

あるいは 値域 { T, F }をもつ関数 …のこと 命題論理で使っていたpとかqなどの記号は、 ある命題を表す変数(命題変数)であった

例

1 以下のものは述語である

1) p(x): x ＞ 3

2) q(x,y): x ＝ y + 4 3) R(x,y): 2 ＝ 1 + 3

例

1

1) p(x): x ＞ 3

• p(2): 2＞3は値Fをとる命題

例

1

2) q(x,y): x ＝ y + 4

• q(1,2): 1 ＝ 2＋4は値Fをとる命題 • q(5,1): 5 ＝ 1＋4は値Tをとる命題

例

1

3) R(x,y): 2 ＝ 1 + 3

• R(x,y) はx,yに関わらず値Fをとる 定数命題関数

限定作用素

(quantifier)とは？

(ａ)全称限定作用素(Universal quantifier) (ｂ)存在限定作用素(Existential quantifier)

二種類の限定作用素があるが、これらは否定演算を介 することで本質的に同じものであることが理解できる

(ａ)全称限定作用素

(Universal quantifier)

• ∀x p(x): xがとりうるすべての値につい てp(x)は値Tをとる、という命題 xを束縛変数(binding variable)と呼ぶ p(x)の領域(domain)あるいはxの世界 (universe)などと呼ぶ

例

2

• 「この教室の学生はすべて１８歳以上で ある」という文を記述しよう p(x): 学生xは１８歳以上である q(x): 学生xはこの教室に居る ∀x(q(x) →p(x)) ただしxの世界はすべての学生の全体

例

3 xを実数とする

p(x): x+1>xとすると、∀xp(x) はT q(x): x>2とすると、∀xq(x)はF

(ｂ)存在限定作用素

(Existential quantifier)

• ∃x p(x): あるxに対してp(x)がTを返す、 という命題

例

4

• 「この教室の学生の中に女性がいる」 という文を記述する p(x): 学生xは女性である q(x): 学生xはこの教室に居る ∃x(p(x) ∧q(x)) • なぜ∃x(p(x) →q(x))とかけないか？

例

5 xを実数とする

p(x): x>x+1とすると、∃xp(x)はF q(x): x>2とすると、∃xq(x)はT

世界が有限の場合

xの世界が有限集合{x₁,x₂, …, x_n}ならば ∀xp(x)＝p(x₁)∧p(x₂)∧…∧p(x_n)

例

6 論理推論の表現

１)すべてのライオンは獰猛である

２)あるライオンはコーヒーを飲まない ３)ある獰猛な動物はコーヒーを飲まない

例

6

p(x): xはライオンである q(x): xは獰猛である R(x): xはコーヒーを飲む １) ∀x(p(x) →q(x)) ２) ∃x(p(x)∧￢R(x)) ３) ∃x(q(x)∧￢R(x))

例

6

１) ∀x(p(x)→q(x)) ２) ∃x(p(x)∧￢R(x)) ３) ∃x(q(x)∧￢R(x)) • １)と２)がともにTならば３)もT • 我々の目標はこのような推論を 行うための体系を求めること(x の世界が有限ならすべてのxにつ いてチェックすればＯＫ)

束縛変数の拡張について

• n変数述語p(x_１, …, x_ｎ)も自然に考え られる

例

7 x,yを実数とする

• p(x,y): x2_＝y • ∃x p(x,y) はyの関数である • y＜0ならば∃x p(x,y)＝F • y≧0ならば∃ x p(x,y)＝T • xが束縛変数なのに対し、yは自由変数 (free variable)と呼ばれる

例

7

• p(x,y): x2_{＝y のとき}

• ∀x p(x,y)はyの値によらずFをとること に注意せよ(これもyの関数ではある)

例

8 x,yを整数とする

p(x,y): x＋y＝０

• ∃y∀x p(x,y) は ∃y(∀x p(x,y))の ことである

• ∀x p(x,y)をyの関数q(y)とみなし、 ∃y q(y)を考えればＯＫ

例

8

p(x,y): x＋y＝０ • y＝０のとき ∀x(x＋０＝０)⇔F • y＝－１のとき ∀x(x－１＝０)⇔F • y＝１のとき ∀x(x＋１＝０)⇔F • y＝－２のとき ∀x(x－２＝０)⇔F …

例

8

したがって

∃y∀x p(x,y)⇔F …、一方…

例

8

• ∀x∃y p(x,y)は、∀x(∃y p(x,y))の ことである

• R(x)＝ ∃y p(x,y)とみなして∀x R(x) について調べればOK

例

8

p(x,y)： x＋y＝０ • x＝０のとき ∃y(０＋y＝０)⇔T • x＝－１のとき ∃y(－１＋y＝０)⇔T • x＝１のとき ∃y(１＋y＝０)⇔T • x＝－２のとき ∃y(－２＋y＝０)⇔T …

例

8

したがって

∀x∃y p(x,y)⇔T

つまり一般には、∀x∃y p(x,y) と

例

9

以下のことを証明しよう

∃y∀x p(x,y)→∀x∃y p(x,y) ⇔ T

∃y∀x p(x,y)がTならば∀x∃y p(x,y)もTで あることを示せばＯＫ

例

9

∃y∀x p(x,y)がTだから、 あるy_１に対して∀x p(x,y_１)がT そこで、任意にx_１を固定したときに ∃y p(x_１,y)はT すなわち∀x∃y p(x,y)はT

例

10

q(x,y,z)： x＋y＝zとする • ∀x∀y∃z q(x,y,z)を調べる • どのようなx、どのようなyに対して も x＋y＝z を満たすzは存在する • したがってこの命題は真

例

10

q(x,y,z): x＋y＝z とする • ∃z∀x∀y q(x,y,z)を調べる • この命題は、“あるzが存在し、どの ようなx、どのようなyに対してもx＋ y＝zを満たす”ことを主張している • この命題は偽

∀

xp(x)とその否定

• ∀x p(x)は「任意のxについてp(x)が成 立する」ことを主張している • ￢∀x p(x)は「任意のxについてp(x)が 成立することはない」、つまりあるxが 存在してp(x)が成立しないことがあるこ とを主張している • この主張は∃x￢p(x)で表現される したがって…

￢∀x p(x) ⇔ ∃x ￢p(x) 同様に

例

11 以下はすべて等価である

￢∀x∀y∃z q(x,y,z) ∃x￢∀y∃z q(x,y,z) ∃x∃y￢∃z q(x,y,z) ∃x∃y∀z ￢q(x,y,z)

例

12 以下はすべて等価である

￢(∀x∀y p(x,y)∨∃x∀y p(x,y)) ￢∀x∀y p(x,y)∧￢∃x∀y p(x,y) ∃x∃y ￢p(x,y)∧∀x∃y ￢p(x,y)

証明手法

(教科書：3.7)

藤田 聡 (広島大学)

数学的推論

(Mathematical Reasoning)

ここでの目的は、以下の２点に答えることである 1. 数学的議論が正しいのはどの場合か 2. 数学的議論を構成するための手法は何か 特に、定理と呼ばれる言明に興味がある – 定理(theorem)とは、正しいことが証明(proof)できる 言明(statement)のこと – では証明とは何か？

証明

(proof)とは？

• 言明の列 S_０

，

S

_１

，

S

_２

，

…

S_i：① 公理(axiom)、あるいは、仮定や既 に得られている定理等(postlude) ②S_０，S_１，S_２，…，S_i－１：から新たに 導かれる言明 どういう風に？ (→推論規則)

用語の使い分け

• 補題(lemma)

ほかの定理を導くための定理

• 系(corollary)

推論規則

(rule of inference)

(p∧(p→q))→q (modus ponensと呼ばれる) または図式的に p p→q q

例

• きょう雪が降ればスキーにいく • きょうは雪である

↓

例

• p： きょう雪である • q： きょうスキーにいく ((p→q)∧p)→q S0： p→q S1： p S2: q 新しい言明を作り出している！

正当

(valid)な議論

• これらの推論規則を用いて構成された 議論は正当(valid)であるという

• では、誤った推論にはどのようなもの があるか？

例 誤った推論の例

(１)

• “この本のすべての問題を解いたなら ば，離散数学をマスターできる” • “あなたは離散数学をマスターした” • したがって“あなたはこの本のすべて の問題を解いた” どこがどうおかしいでしょうか？

例

(つづき)

• p： この本のすべての問題を解いた • q： 離散数学をマスターした ((p→q)∧q)→p 誤り！ • 正しくは， ((p→q)∧p)→q

例

誤った推論の例

(２)

2 = 1

• aとbを等しい正整数とする 1. a=b : 仮定より 2. a２ = ab : 両辺をa倍 3. a２ –b２ = ab –b２ : 両辺からb２_を引く 4. (a-b)(a+b) = b(a-b) : 因数分解 5. a+b = b : 両辺をa-bで割る 6. 2b = b : a=bより 7. 2 = 1 : 両辺をbで割る

例

Indirect proofの例

３ｎ＋２が奇数ならばｎも奇数である • 対偶を考える。すなわち、ｎが偶数ならば ３ｎ＋２も偶数であることを示す。 • ｎは偶数だから，ｎ＝２ｋとかける。よっ て３ｎ＋２＝３×２ｋ＋２＝２(３ｋ＋１) 証明終了

proof by contradiction (背理法)

￢pを仮定して矛盾を導く。あるいは

例

proof by contradictionの例

sqrt(2)が無理数(irrational)であることを示 そう • sqrt(2)が有理数a/bであると仮定して矛盾 を導く(aとｂは互いに素とする) • sqrt(2)＝a/bより、２＝a2_/b2 • a2_＝２b2_{より、aは偶数２ｃである} • したがって４ｃ2_＝２b2_より２ｃ2_＝b2_、 • すなわちｂも偶数。これは矛盾

proof by cases

(p_１∨p_２∨…∨p_ｎ)→q を示すのに

(p_１→q)∧(p_２→q)∧…∧(p_ｎ→q) を示す

proof by casesの例

もし整数nが２でも３でも割り切れないと き、n2-1が24で割り切れることを示せ • 整数nを６で割ったときの余りによって場 合わけする：6m+j, j=0,1,2,3,4,5 • j=0,2,3,4のときはｎは２で割り切れるか ３で割り切れるので、考えるべき場合は 、6m+1と6m+5の2通りだけであることが わかる

proof by casesの例

• n=6m+1のとき、 n2_{ー１=(6m+1)}2 _{– 1 = 36m}2_{+12m=12m(3m+1)} mが偶数の場合も奇数の場合もm(3m+1)は偶数 • n=6m+5のとき、 n2_{ー１=(6m+5)}2 _{– 1 = 36m}2_+60m+24 =12m(3m+5)+24 mが偶数の場合も奇数の場合もm(3m+5)は偶数

定理と限定作用素

• ∃ｘp(x)の証明 …存在性の証明(existential proof) １) constructive(構成的) p(a)がTとなるaを構成する ２) nonconstructive(非構成的)

例

Constructive proof の例

任意のｎに対して、あるｘが存在して， すべてのi(１≦i≦ｎ)に対してｘ＋iは合成 数である ｘ＝(ｎ＋１)！＋１とする 任意のiについて x＋i≡(n+1)！＋(i+1)≡０(mod i+1)

例１５

Nonconstructive proof の例

どのような整数nに対しても、ｎよりも大きな 素数が存在する(⇒素数は無限に存在する) • 整数ｘ＝ｎ！＋１を考える • ｘは２からnまでのどの整数でも割り切れない • したがって、xが素数であるか，あるいはn以 上の素数が存在してxはその素数で割り切れる

例 前向き推論と後ろ向き推論

互いに異なる実数a, bに対して、 (a+b)/2>sqrt(ab)であることを示せ • 結論からはじめて、その結論が常に成立 することを示す(推論の向きが後ろ向きな だけで、p→qを示すのにq→pを言おうと しているのではないことに注意

• (a+b)/2>sqrt(ab) • (a+b)2_{/4 > ab} • (a+b)2 _{> 4ab} • a2_+2ab+b2 _{> 4ab} • a2_-2ab+b2 _{> 0} • (a-b)2 _{> 0, これはa≠bのときつねに成立}

例 前向き推論と後ろ向き推論

予想

(conjecture)の重要性

• いくつかの観測された事実から予想をたてる • 予想が正しいかどうかを証明する • 予想が正しいことが証明できれば「定理」と なる。予想が正しくないことを証明するため には、反例(counterexample)を示せばよい

「予想⇒定理」の例

• いくつかの連続した合成数の列が存在す る 24,25,26,27,28 90,91,92,93,94,95,96 そのような列の長さはいくらでも長くで きるか？ • つまり、任意に自然数nを与えたとき、 x+1,x+2,…,x+nがすべて合成数であるよ うな自然数xが存在するか(証明済み)

「予想⇒反例」の例

• ピタゴラスの定理： 32+42=52 • フェルマーの最終定理： n>2かつｘｙｚ≠0 のとき、 xn+yn=znを満たすような整数x,y,z は存在しない • オイラーの予想： 3以上の任意の整数ｎに対 して、n-1個の自然数のｎ乗の和が別の自然 数のｎ乗になるようなものは存在しない (x₁)n_+(x 2)n+…+(xn-1)n = yn

「予想⇒反例」の例

• オイラーの予想に対する反例：

275 _{+ 84}5 _{+ 110}5 _{+ 133}5 _{= 144}5

未解決の予想の例

• ３ｘ＋１予想 • 次のような関数f(x)を考える：xが偶数の ときf(x)=x/2, ｘが奇数のとき、 f(x)=3x+1 • このとき、どのようなｘを与えても、関 数f(x)を繰り返し適用することにより、い ずれは必ず１に収束する(予想)

未解決の予想の例

• x＝13のとき、次のように推移する： 13 → 40 (=3×13+1) → 20 (=40/2) → 10 (=20/2) → 5 (=10/2) → 16 (=3×5+1) → 8 → 4 → 2 → 1 • この予想の通りに推移することは、 x=5.6×1013_{の範囲までは確認されているが} 、どのような自然数ｘについても成立する かどうかはわかっていない(証明もされてい ないし反例もみつかっていない)