什么是證明【proof】?

證明的存在是超越數(shù)學的，那么證明的更高層次的概念是什么？它可能沒有潛在的邏輯推導【logical deduction】，也可能沒有假設(shè)【assumption】。

我認為一般來說，證據(jù)【proof】被認為是，跨多個領(lǐng)域【field】，作為一種確定【ascertaing】真理【truth】的方法。這里所說的確定【ascertaing】，是指建立【establishing】真理，驗證【verifying】真理。

在社會中，甚至在科學中，有很多方法可以確定真理【ascertaing truth】:

• 實驗【experimentation】：觀察【observation】，就像看到那塊粉筆會掉到地上,，它是物理學的基石，誰知道外面是否有重力？我們可以通過觀察，然后我們得出結(jié)論，這就是事實
• 抽樣【sampling】：反例【counter example
• 法官【judge】和陪審團【jury】
• 宗教【religion】：圣經(jīng)
• 信仰【conviction】：我的程序沒有bug

在數(shù)學中，數(shù)學證明是通過一系列公理【axioms】的邏輯推導【logical deduction】來對一個命題【proposition】的驗證【verification】。

這有點拗口，這里有三個重要的組件：

• 命題【proposition】
• 公理【axioms】
• 邏輯推導【logical deduction】

命題?

命題【proposition】是一種非真即假的陳述【statement】。

栗子1（真命題）

2 + 3 = 5

栗子2（假命題）

對所有自然數(shù) {0,1,2,3,4...}? n ，?是一個質(zhì)數(shù)【prime number】

?? n?∈ N? ?，??是一個質(zhì)數(shù)

• ??是一個質(zhì)數(shù)，也被稱為謂詞【predicate】，謂詞【predicate】是一個命題【proposition】，其真值【truth】取決于變量的值。在這里，變量指的是 n。
• ?N? {0,1,2,3,4...}? 則被稱為論域【universe of discourse】，這是我們談?wù)摰乃惺挛锏目臻g，在這里，我們只談?wù)撟匀粩?shù)。
• ? 被稱為量詞【quantifier】

如果要證明該命題成立，那么我們就要證明謂詞在所有自然數(shù)下均成立。

n	?	質(zhì)數(shù)
1	43	true
39	1601	true
40	1681	false 41 * 41
41	1763	false 41 * 43

? ? ? ? ? ? ? ? ? ? ? ? ? ?

?栗子3

?沒有正數(shù)解?

該命題由尤拉提出，218年后，一個名叫諾姆·埃爾基斯的聰明人終于否決了這個猜想。

a = 95800

b = 217519

c = 414560

d = 422481

所以，真命題應(yīng)該是 ：

? a,b,c,d?∈ N+ ，?

其中：

• ? 是量詞【quantifier】，表示存在
• ?是謂詞

??

?栗子4

?? n?∈ Z?，

其中：

• Z?指的是 integer，{0,1,-1,2,-2 ...}
• => 符號是蘊含【implies】

我們現(xiàn)在來定義蘊含【implies】的意義：

當 p 是 false 或者 q 是true 時，則蘊含【implication】p => q 就是真。

下面是真值表【truth table】:

truth table

p	q	p => q
T	T	T
T	F	F
F	T	T
F	F	T

false 蘊含一切都是 true，這看上去有點奇怪。

有一個著名的表達，如果豬能飛，我就當國王了。

這段陳述可以寫作：pigs fly => i'm king，它是 true ，因為豬不會飛，不管我是不是國王。因為豬不會飛，盡管這是 false 的，但這句話的蘊含是 true 的。

栗子5

?? n?∈ Z?，

該命題為假，例如 n = -3?

truth table

p	q	p=>q	q=>q	p<=>q
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

?

這里的關(guān)鍵是總是檢查兩種方式【way】。

這里為了證明 <=>【if and only if】，我們需要檢查 => ，也需要檢查 <=。

提問：每個句子【sentence】都是一個命題嗎?

答案：No～ 比如"hello"，"how are you"

公理 axioms

好消息是，公理和命題其實是一回事~

唯一的區(qū)別是，公理【axioms】是我們假設(shè)【assumed】為真的命題【propositions】

沒有證明【proof】能證實公理【axiom】是真的，你只是假設(shè)它是合理的～～

公理【axiom】一詞來源于希臘，在希臘語中，這并不意味著真，而是意味著值得思考【think worthy】。

在數(shù)學中，有很多公理：

• if a = b，b = c，then a = c

公理在不同的上下文下可能是矛盾的～

在歐幾里得幾何中有這么一個中心公理

• 給定一條線L和一個不在L上的點P，有一條通過P平行于L的線

但是還有一個領(lǐng)域叫做球面幾何，這里，你有一個與之相矛盾的公理：

• 給定一條線L和一個不在L上的點P，不存在一條通過P且平行于L的線

還有一個領(lǐng)域叫雙曲幾何【hyperbolic geometry】:

• 給定一條線L和一個不在L上的點P，有無窮多條經(jīng)過p平行于L的直線

它們在各自的上下文中是有意義的～～

公理有兩個指導原則，公理應(yīng)該：

• consistent 一致的
• complete? ?完備的

Def：如果沒有一個命題可以被證明即是真又是假，則該公理集是一致的【consistent】

Def：如果一組公理能被用來證明每個命題的真或假，那么它就被稱為完備的【complete】

這是可取的，因為這意味著您可以解決所有問題，你可以證明任何事是真還是假。

現(xiàn)在你會認為得到一組滿足這兩個基本性質(zhì)的公理集應(yīng)該不會太難。你想要一個足夠強大的公理集來證明一切的真假。

事實證明并非如此！！事實上，許多邏輯學家的職業(yè)生涯都在試圖找到這樣一組公理，它們是一致且完備的。

事實上，羅素和懷特黑德可能是最有名的兩個，他們花費了整個生涯都在做這件事，但還是沒得到。

然后有一天，這個叫庫爾特·戈德爾【kurt Godel】的家伙出現(xiàn)了，在 1930 年代，他證明不可能存在任何一組既一致又完備的公理集。現(xiàn)在，這個發(fā)現(xiàn)摧毀了這個領(lǐng)域，這是一個巨大的發(fā)現(xiàn)。

這是一個了不起的結(jié)果，因為它說如果你想要一致性【consistent】，就會有你永遠無法證明的真實事實【true fact】。

總結(jié)

以上是生活随笔為你收集整理的Mathematics for Computer Science的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。