數學證明和數學/邏輯原理/蘊涵的直接證明

我們已經討論了數學中使用哪些型別的語句，所以現在我們可以討論如何將這些語句組合在一起以證明定理。在這一點上，我們只能證明重言式，所以如果這是一個影片遊戲，那麼這將是訓練級別。我們在這裡證明的語句不能真正被稱為定理，所以我們將稱它們為命題。

如前所述，$P$，$Q$，... 將在本節中代表數學語句。

推理規則

在數學中，證明必須基於邏輯推論，換句話說，每一步都必須是前一步的邏輯結果。邏輯結果究竟是什麼，是邏輯學的問題，邏輯學為我們提供了“推理規則”。每個推理規則都是一個將真命題組合在一起的規則，保證會產生另一個真命題。最簡單的例子是

從 $P$ 推匯出 $P$。

這條規則被稱為“迭代”；許多推理規則都有名稱，但在數學證明中，應該從上下文中清楚地知道使用了哪條規則。

還有其他一些規則以簡單的方式組合先前的語句，但事實證明，僅憑它們無法走得太遠。一種方法是新增邏輯公理，例如

$P$ 或 $P$ 蘊涵 $P$。

但這雖然是一種有效的方法，但如果直接使用邏輯公理，數學中的證明將長得多，也更難理解。因此，數學中使用的方法是允許使用“輔助假設”。

這種型別規則最常用的例子是

如果透過做出假設 $P$ 可以推匯出 $Q$，則推匯出 $P$ 蘊涵 $Q$。

這需要一段時間才能理解，所以我們將給出一些使用這條推理規則的證明示例。

證明示例 #1

我們第一個證明示例是針對語句

命題 1 $P$ 蘊涵 $P$。

證明的第一個版本將採用表格格式，以便清楚地說明推理規則的使用方式。

行	語句	理由
1	$P$	假設
2	$P$	迭代第 1 行
3	$P$ 蘊涵 $P$	由 1 和 2

在表格中，第一行縮排表示我們正在引入假設或假設，下一行縮排表示我們在第一行的假設下進行操作。最後一行沒有縮排，這意味著該語句在沒有假設的情況下仍然有效。

所以讓我們來研究一下在這種情況下推理規則是如何應用的。首先，我們做出了假設$P$. 然後我們推匯出$P$，在這種情況下只是簡單地重複$P$。由於透過假設$P$，我們能夠推匯出$P$，推理規則指出你可以得出結論$P$ 意味著 $P$.

證明的表格格式很少在數學中使用。如果你像我們現在這樣非常詳細和謹慎，或者如果你剛開始接觸證明，就像我們現在一樣，你可以使用它。在數學文獻中，你會使用更像散文的形式。我們的第二個版本展示了證明在這種格式下可能是什麼樣的。

命題 1: $P$ 意味著 $P$.

證明: 假設$P$。那麼根據假設$P$。因此$P$ 意味著 $P$.

在這個版本的證明中，有語言來介紹假設。這通常是“假設…”或“設…”。第二行得出結論並給出理由。用於此的語言通常類似於“那麼…因為…”，“因此…透過…”，“所以…既然…”。最後一行實際上不是必需的，因為我們已經知道我們試圖證明哪個語句。但由於它包含在內，因此使用了“因此”一詞來指出這是證明中的一個重要點。在這種情況下，是因為我們將假設與我們能夠從中推匯出來的內容結合起來，從而消除了假設。

經驗豐富的數學家通常能夠毫不費力地完成像這樣的陳述的證明。因此，另一個可接受的證明可能是

命題 1: $P$ 意味著 $P$.

證明: 平凡的。

但是，將一個陳述稱為“平凡的”、“顯然的”或“清晰的”是一種特權，你必須透過做足夠多的證明才能自動填補邏輯證明才能獲得這種特權。它不能用於根據你的直覺似乎為真的陳述。還要記住，對某些人來說是平凡的，對另一些人來說可能不是平凡的，因此在寫證明時，你必須牢記你的讀者，就像所有的寫作一樣。

Q.E.D. 和墓碑

縮寫“Q.E.D.”有時出現在證明的末尾，但在現代數學中很少使用。它是拉丁語短語 quod erat demonstrandum 的縮寫，大致意思是“這是要被證明的”。拉丁語不像以前那樣廣泛為人所知，而且這種縮寫是在作者可以放心地假設他們的讀者具有基本知識的時候使用的。有一些變體，包括 quod erat faciendum 的“Q.E.F.”，意思是“這是要做的”。如果證明的結尾在現代文字中被標記，那麼就會使用墓碑或一個小矩形或正方形。但是，如果你是一位喜歡在日常生活中使用 mutatis mutandis 這樣短語的傳統人士，那麼如果你願意，使用 Q.E.D. 並沒有什麼錯誤。

示例證明 #2

下一個證明示例將針對以下陳述

命題 2: $P$ 意味著 ($Q$ 意味著 $P$).

這有點複雜，但我們鼓勵你在閱讀更多內容之前嘗試一下，記住它可以使用到目前為止我們給出的兩個推理規則來證明。

更復雜的證明不是那麼多的編寫，而是構建的。換句話說，你並不是從頭到尾地寫它們。就像看到一棟已建成的房子並不能告訴你如何建造它一樣，看到一個已完成的證明並不能告訴你如何寫它。因此，我們將嘗試展示用於建立示例證明的過程，而不僅僅是最終結果。

我們首先假設有一個證明，然後試圖找出它的樣子。該陳述是一個蘊涵，所以為了使推理規則起作用，我們需要假設“蘊涵”一詞之前的部分並推匯出“蘊涵”一詞之後的。因此，以表格形式，證明的結構是

行	語句	理由
1	$P$	假設
(something)
n	$Q$ 蘊涵 $P$	?
n+1	$P$ 蘊涵 ($Q$ 蘊涵 $P$)	從 1 和 n

現在我們需要一個關於

$Q$ 蘊涵 $P$

的證明來填補中間。這又是一個蘊涵，所以我們需要假設第一部分，$Q$，並證明第二部分，$P$。這意味著在第一個假設中做出第二個假設，我們當前版本的證明是

行	語句	理由
1	$P$	假設
2	$Q$	假設
(something)
n−1	$P$	?
n	$Q$ 蘊涵 $P$	從 2 和 n−1
n+1	$P$ 蘊涵 ($Q$ 蘊涵 $P$)	從 1 和 n

此時我們需要證明 $P$，但它已經是假設之一，所以只需要重新陳述它。這給了我們證明的最終版本

行	語句	理由
1	$P$	假設
2	$Q$	假設
3	$P$	迭代第 1 行
4	$Q$ 蘊涵 $P$	從 2 和 3
5	$P$ 蘊涵 ($Q$ 蘊涵 $P$)	從 1 和 4

讓我們翻譯成散文格式。

命題 2：$P$ 蘊涵 ($Q$ 蘊涵 $P$)

證明：假設 $P$。現在假設 $Q$。根據原始假設，我們有 $P$。因此，$Q$ 蘊涵 $P$。從原始假設 $P$ 可以得出 $Q$ 蘊涵 $P$，所以我們可以得出結論，$P$ 蘊涵 ($Q$ 蘊涵 $P$).

示例證明 #3

在這個例子中，我們需要一個新的推理規則。

從 $P$，$P$ 蘊含 $Q$ 推匯出 $Q$。

換句話說，如果語句 $P$ 和語句 $P$ 蘊含 $Q$ 都已被證明，那麼你可以新增語句 $Q$。

你可能會認為這是之前推理規則的逆，因為它使用了一個蘊含，而之前的規則證明了一個蘊含。

命題 3： $P$ 蘊含 (($P$ 蘊含 $Q$) 蘊含 $Q$。

同樣，我們鼓勵你在繼續閱讀之前嘗試一下，記住它可以用我們迄今為止給出的三個推理規則來證明。

我們將使用上一個例子中討論的構造方法來達到這一點，留作練習。

行	語句	理由
1	$P$	假設
2	$P$ 蘊含 $Q$	假設
(something)
n−1	$Q$	?
n	($P$ 蘊含 $Q$) 蘊含 $Q$	從 2 和 n−1
n+1	$P$ 蘊含 (($P$ 蘊含 $Q$) 蘊含 $Q$)	從 1 和 n

我們需要證明

$Q$

在這一點上，但我們有

$P$

和

$P$ 蘊含 $Q$

作為假設。因此，只需應用我們新的推理規則即可。證明的最終形式如下：

行	語句	理由
1	$P$	假設
2	$P$ 蘊含 $Q$	假設
3	$P$	迭代第 1 行
4	$Q$	3,2
5	($P$ 蘊含 $Q$) 蘊含 $Q$	從 2 和 5
6	$P$ 蘊含 (($P$ 蘊含 $Q$) 蘊含 $Q$)	從 1 和 6

以散文格式

命題 3： $P$ 蘊涵 (($P$ 蘊涵 $Q$) 蘊涵 $Q$)

證明： 假設 $P$。現在假設 $P$ 蘊涵 $Q$。根據最初的假設，我們有 $P$，所以 $Q$。因此，$Q$ 蘊涵 ($P$ 蘊涵 $Q$)。從最初的假設 $P$ 可以得出 ($Q$ 蘊涵 $P$) 蘊涵 $Q$)，因此我們可以得出結論 $P$ 蘊涵 (($Q$ 蘊涵 $P$) 蘊涵 $Q$)).

引用之前的結果

如果所有東西都必須從頭開始證明，數學將不會取得很大進展。幸運的是，每次證明一個新的結果時，它都可以作為其他證明的捷徑。通常可以清楚地知道使用了哪個結果，否則，如果它是同一文件中之前證明的結果，則在證明中指向它。使用某種標籤或編號系統來簡化此操作非常方便。如果您引用其他來源，請使用您喜歡的引用風格，以清楚地表明您從哪裡引用，並清楚地說明在該來源中哪裡可以找到該結果。請注意，任何形式為$P$ 蘊含 $Q$ 的結果可以與前面的推理規則結合起來，建立一個新的推理規則“從 $P$ 推斷 $Q$”。例如，命題 2 建立了一個新的推理規則

從 $P$ 推斷 $Q$ 蘊含 $P$.

命題 4： $P$ 蘊含 ($Q$ 蘊含 ($R$ 蘊含 $P$))).

證明：假設$P$。那麼$R$ 蘊含 $P$，根據命題 2。同樣，$Q$ 蘊含 ($R$ 蘊含 $P$)，根據命題 2。因此$P$ 蘊含 ($Q$ 蘊含 ($R$ 蘊含 $P$))。

注意，在命題 2 的第一次應用中，語句 $R$ 替換了命題中使用的 $Q$。在第二次應用中，語句 $R$ 蘊含 $P$ 替換了命題中使用的 $P$。

留給讀者完成

以下證明留給讀者完成

命題 5: ($P$ 蘊含 $Q$) 蘊含 (($Q$ 蘊含 $R$) 蘊含 ($P$ 蘊含 $R$))。

命題 6: ($P$ 蘊涵 ($Q$ 蘊涵 $R$)) 蘊涵 ($Q$ 蘊涵 ($P$ 蘊涵 $R$)).

命題 7: ($P$ 蘊涵 ($P$ 蘊涵 $Q$)) 蘊涵 ($P$ 蘊涵 $Q$).

命題 8: ($P$ 蘊涵 ($Q$ 蘊涵 $R$)) 蘊涵 (($P$ 蘊涵 $Q$) 蘊涵 ($P$ 蘊涵 $R$)).

命題 9: (($R$ 蘊含 $Q$) 蘊含 $P$) 蘊含 ($Q$ 蘊含 $P$)

命題 10: (($R$ 蘊含 $Q$) 蘊含 ($Q$ 蘊含 $P$)) 蘊含 ($Q$ 蘊含 $P$)

到目前為止，我們只討論了蘊含，但這並不意味著我們已經完成了它。有一些陳述，雖然為真，但無法用我們目前給出的推理規則證明。其中之一是

命題 ??： (($P$ 蘊含 $Q$) 蘊含 $P$) 蘊含 $P$.

你可能想嘗試一下，記住只使用本頁的推理規則，看看你能走多遠。如果你真的找到了一個證明，那麼這意味著你（可能）做錯了什麼。