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) 同様に
￢∃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
２， …
Si：① 公理(axiom)、あるいは、仮定や既 に得られている定理等(postlude)
②S０，S１，S２，…，Si－１：から新たに 導かれる言明
どういう風に？ (→推論規則)
用語の使い分け
• 補題(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を仮定して矛盾を導く。あるいは
￢(p→q)＝p∧￢qをTと仮定して矛盾を導く
例 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 = 36m2+12m=12m(3m+1)
mが偶数の場合も奇数の場合もm(3m+1)は偶数
• n=6m+5のとき、
n2ー１=(6m+5)2 – 1 = 36m2+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個の自然数のｎ乗の和が別の自然 数のｎ乗になるようなものは存在しない
(x1)n+(x2)n+…+(xn-1)n = yn
「予想⇒反例」の例
• オイラーの予想に対する反例：
275 + 845 + 1105 + 1335 = 1445
Landerとpartkinによって1966年に発見された
未解決の予想の例
• ３ｘ＋１予想
• 次のような関数f(x)を考える：xが偶数の ときf(x)=x/2, ｘが奇数のとき、
f(x)=3x+1
• このとき、どのようなｘを与えても、関 数f(x)を繰り返し適用することにより、い ずれは必ず１に収束する(予想)