スライ>ド - preining.info

L211 数学と論理学第３回
プライニング　ノルベルト
[email protected]
http://www.preining.info/jaist/l211/2015j/
前の講義
計算からパターンの理論まで
大事な点
I
算術の基本定理
I
素数定理（Prime number theorem）
自然数の中に素数がどのくらいの「割合」で含まれている
π(n) ∼
I
n
ln n
ゴールドバッハの予想
全ての 2 よりも大きな偶数は二つの素数の和として表すこと
ができる。
I
完全化：
足算：N → Z
割算：Z → Q
ルート：Q → A, A → R, R → C
証明
国語辞書
ある物事や判断の真偽を、証拠を挙げて明らかにする
こと。　「身の潔白を―する」
「本人であることを―する
書類」「身分―」
「印鑑―」
訴訟法上、当事者が事実の存否について、裁判官に確信
を抱かせること。または、これに基づき裁判官が確信を
得た状態。
他の人に正確を納得させる！
いろんな証明方法
I
当たり前の証明：「そんなに簡単な証明を述べなくていい」
I
便利さの証明：
「正しかったら、よかった。
。
。
」
I
必要さの証明：
「これは正しくなかったら、世界の終わりだ」
I
脅迫の証明：
「バカにしないで、正しいぞ」
I
悪い類推の証明：「まっ、ちょっとそれに似っているから、
正しい」
I
直感の証明：「僕の感じで正しい」
I
権威の証明：
「XXX はおっしゃったから正しい」
Last but not least . . .
愛情の証明：
「彼氏から指輪をもらったから、
。
。
。」
数学の証明
I
正確さを確かめる
I
推論する
I
I
I
I
公理から
前に証明された定理・補助定理から
ひとつづのステップを確認できる
伝えられるように書く
数学の真偽
真
命題は正しいか正しくない。
「半分正しいというがない！」
命題の組立方法
∨
オア　（選言）
A∨B
∧
アンド
（連言）
A∧B
→
ならば
（含意）
A→B
¬
ノット
（否定）
¬A
必要と十分と必要十分
必要
A は B であるための「必要条件」
x 2 = 1 は x = 1 であるための必要条件
B→A
十分
A は B の「十分条件」
x = 1 は x 2 = 1 の十分条件
A→B
必要十分
必要条件でもあり十分条件でもある条件
A↔B
真理値表
真
偽
基本価値
A
¬A
1
0
0
1
1
0
真理値表２
A
B
A∨B
A
B
A∧B
A
B
A→B
0
0
1
1
0
1
0
1
0
1
1
1
0
0
1
1
0
1
0
1
0
0
0
1
0
0
1
1
0
1
0
1
1
1
0
1
A
B
A↔B
0
0
1
1
0
1
0
1
1
0
0
1
真理値表３
真理値表の練習
(P ∨ Q) → R
量記号
全称記号
記号：∀
「すべての」. . .
例：∀n ∈ N : P(n)
全ての自然数 n に対して P(n) である。
存在記号
記号：∃
「ある」. . .
例：∃n ∈ N : P(n)
ある自然数 n に対して P(n) である。
他の作用素：∃!
量記号の関係
「全ての n に対して P(n) である」と否定すると . . .
¬∀nP(n)
「ある n に対して ¬P(n) である」になる
¬∀nP(n)
⇔
∃n¬P(n)
¬∃nP(n)
⇔
∀n¬P(n)
証明方法
直接証明
定理
２つの集合 A と B は、A ⊆ B かつ B ⊆ A が成り立つならば、
A = B が成り立つ。
証明
I
x ∈ A が成り立つならば、A ⊆ B のため、x ∈ B が成り立つ。
I
(1) それゆえ、全ての x ∈ A に対して、x ∈ B である。
I
x ∈ B が成り立つならば、B ⊆ A のため、x ∈ A が成り立つ。
I
(2) それゆえ、全ての x ∈ A に対して、x ∈ B である。
I
(1) と (2) は A = B を導く。
直接証明
定理
(A ⊆ B) ∧ (B ⊆ A) ⇒ (A = B)
証明
I
(1) x ∈ A ∧ A ⊆ B ⇒ x ∈ B
I
(2) x ∈ B ∧ B ⊆ A ⇒ x ∈ A
I
(1) ∧ (2) ⇒ A = B
対偶証明
直接証明
前提 =⇒ 結論
前提を仮定すると、結論を証明する。
対偶証明の基本パターン
A→B
⇔
¬B → ¬A
結論の否定を仮定して、前提の否定を証明する。
対偶の確認
A
B
A→B
¬A
¬B
¬B → ¬A
0
0
1
1
0
1
0
1
1
1
0
1
1
1
0
0
1
0
1
0
1
1
0
1
対偶の例
定理（n は自然数）
n2 は偶数が成り立つならば、n も偶数が成り立つ。
対偶の式
n は偶数が成り立たないならば、n も偶数が成り立たない。
証明
n は偶数ではないから n = 2k + 1 が成り立つ
n2 = (2k + 1)2
n2 = 4k 2 + 4k + 1
n2 = 2(2k 2 + 2k) + 1
だから n2 も偶数ではない。
矛盾証明
基本のパターン
A を仮定すると、矛盾を推論できる場合は、 A は正しくない。
例
√
2 は無理数である。
証明
√
2 は有理数を仮定する。。。
矛盾証明
素数の数
素数の数は無限である。
証明
素数の数が有限を仮定する。
。
。
まとめ
I
社会の証明と数学の証明は違う
I
証明は公理から一歩一歩続いてる
I
いろんな証明方法
演習の紙
次の講義：帰納法
Sources
I
Ring: http:
//www.fotocommunity.de/pc/pc/display/29133067

Download Report