蘊涵命題演算

在數理邏輯中，蘊涵命題演算是只使用叫做蘊涵或條件的一個連結詞的經典(二值)命題演算。用公式表達，這個二元運算被指示為「implies」「如果 ..., 則 ...」, 「→」, 「 $\rightarrow \!$ 」等等。

作為算子的實質完備性

單獨的蘊涵作為邏輯算子不是完備的，因為不能用它形成所有其他二值真值函數。但是如果有已知為假的一個命題並作為給虛假的零元連結詞那樣使用它，則可以定義所有其他真值函數。所以蘊涵作為算子實質上是完備的。如果 P,Q 和 F 是命題而 F 已知為假，則:

¬P 等價於 P→F
P∧Q 等價於 (P→(Q→F))→F
P∨Q 等價於 (P→F)→Q
P↔Q 等價於 ((P→Q)→((Q→P)→F))→F

更一般的說，因為上述算子對表達任何真值函數是充分的，可以得出任何真值函數都依據「→」和「F」來表達，如果有一個命題 F 已知為假。

公理

公理模式 1 是 P→(H→P)。
公理模式 2 是 (H→(P→Q))→((H→P)→(H→Q))。
公理模式 3 (皮爾士定律)是 ((P→Q)→P)→P。
唯一的推理規則(肯定前件)是: 從 P 和 P→Q 推出 Q。

在這裏每個情況下，P, Q, H 可以被替代為只包含「→」作為連結詞的任何命題。

演繹元定理

首要任務是使用公理 1, 2 和肯定前件導出演繹元定理。

我們開始於證明一個定理模式(這裏的 A 和 B 可替代為只包含「→」作為連結詞的任何命題):

(A→((B→A)→A))→((A→(B→A))→(A→A)) 1. 公理 2
A→((B→A)→A) 2. 公理 1
(A→(B→A))→(A→A) 3. 肯定前件 2,1
A→(B→A) 4. 公理 1
A→A 5. 肯定前件 4,3 QED

後續過程詳見演繹定理。

取代虛假

如果 A 和 Z 是命題，則 A→Z 等價於 (¬A*)∨Z，這裏的 A* 是把 A 中 Z 的所有、某個或零個出現替代為虛假的結果。類似的，(A→Z)→Z 等價於 A*∨Z。所以在某些條件下，它們可以分別作為表說 A* 為假或 A* 為真的替代品。

公理的完備性，第一部分

我們將看到這些公理在任何只包含「→」作為連結詞的重言式都可用從它們演繹出的意義上。考慮只包含 P1, P2, ..., Pn 作為原子命題(命題變量)的重言式 S。

在真值表中選擇一行給 S。它展示了對一個特定賦值(從命題變量到 {假, 真} 的函數)每個 S 的子公式的真值。通過在子公式長度上的數學歸納法，我們將證實從形如 Pk→Z (在 Pk 被給予值假的時候)或(Pk→Z)→Z (在 Pk 被給予值真的時候)的命題，可以為每個 S 的子公式演繹出類似的命題。這需要下面給出的三個引理。

真結論的引理

考慮 S 的子公式 P→Q。如果 Q 被賦值給予值真，則 P→Q 也將被給予值真。所以我們需要證實 ((P→Q)→Z)→Z 可以證明自關於這個賦值的假定。

- (Q→Z)→Z 1. 假設
  - (P→Q)→Z 2. 假設
    - Q 3. 假設
      - P 4. 假設
      - Q 5. 重複 3
    - P→Q 6. 演繹自 4 到 5
    - Z 7. 肯定前件 6,2
  - Q→Z 8. 演繹自 3 到 7
  - Z 9. 肯定前件 8,1
- ((P→Q)→Z)→Z 10. 演繹自 2 到 9
((Q→Z)→Z)→(((P→Q)→Z)→Z) 11. 演繹自 1 到 10 QED

假前提的引理

如果 P 被賦值給予值假，則 P→Q 將給給予值真。所以我們需要證實 ((P→Q)→Z)→Z 可以證明自關於這個賦值的假定。

- P→Z 1. 假設
  - (P→Q)→Z 2. 假設
    - Z→Q 3. 假設
      - P 4. 假設
      - Z 5. 肯定前件使用步驟 4 和 1
      - Q 6. 肯定前件使用步驟 5 和 3
    - P→Q 7. 演繹自 4 到 6
    - Z 8. 肯定前件使用步驟 7 和 2
  - (Z→Q)→Z 9. 演繹自 3 到 8
  - ((Z→Q)→Z)→Z 10. 皮爾士定律
  - Z 11. 肯定前件使用步驟 9 和 10
- ((P→Q)→Z)→Z 12. 演繹自 2 到 11
(P→Z)→((P→Q)→Z)→Z) 13. 演繹自 1 到 12 QED

真前提和假結論的引理

如果 P 被賦值給予值真而 Q 被給予值假，則 P→Q 將被給予值假。所以我們需要證明 (P→Q)→Z 可以證明自關於這個賦值的假定。

- (P→Z)→Z 1. 假設
  - Q→Z 2. 假設
    - P→Q 3. 假設
      - P 4. 假設
      - Q 5. 肯定前件 4,3
      - Z 6. 肯定前件 5,2
    - P→Z 7. 演繹自 4 到 6
    - Z 8. 肯定前件 7,1
  - (P→Q)→Z 9. 演繹自 3 到 8
- (Q→Z)→((P→Q)→Z) 10. 演繹自 2 到 9
((P→Z)→Z)→[(Q→Z)→((P→Q)→Z)] 11. 演繹自 1 到 10 QED

公理的完備性，第二部分

在完備性證明的第一部分，我們證實了假定關於命題變量的適當假設，(S→Z)→Z 可以證明自重言式 S 每個賦值。現在我們將把這些賦值合併起來並除去關於命題變量的假定。

考慮仍未從假定中除去的命題變量中的一個，比如它是 P。則使用演繹元定理，我們得到 (P→Z)→((S→Z)→Z) 並且類似的我們得到 ((P→Z)→Z)→((S→Z)→Z)，二者都從 P 不出現的假定的簡約集合中得出。

- (P→Z)→((S→Z)→Z) 1. 假設
  - ((P→Z)→Z)→((S→Z)→Z) 2. 假設
    - S→Z 3. 假設
      - P→Z 4. 假設
      - (S→Z)→Z 5. 肯定前件 4,1
      - Z 6. 肯定前件 3,5
    - (P→Z)→Z 7. 演繹自 4 到 6
    - (S→Z)→Z 8. 肯定前件 7,2
    - Z 9. 肯定前件 3,8
  - (S→Z)→Z 10. 演繹自 3 到 9
- [((P→Z)→Z)→((S→Z)→Z)]→[(S→Z)→Z] 11. 演繹自 2 到 10
[(P→Z)→((S→Z)→Z)]→([((P→Z)→Z)→((S→Z)→Z)]→[(S→Z)→Z]) 12. 演繹自 1 到 11 QED

所以我們可以組合成對的真值表的行到一起並重複這個過程直到關於命題變量的值的假定都被除去了。結果將是我們已經證明了 (S→Z)→Z，這裏的 S 是重言式而 Z 是任何命題。現在我們選擇 Z 一樣於 S。因此 (S→S)→S 是個定理只要 S 是重言式。但是 S→S 是我們早先證明的定理模式的一個實例。所以通過肯定前件 S 是對於任何重言式 S 的一個定理。我們的公理是完備的。

這個證明是構造性的。就是說給定一個重言式，我們可以服從指導並從我們的公理建立它的一個證明。但是，這種證明的長度隨着重言式中命題變量的數目呈超指數增長。所以除了對非常短的重言式之外它不是實用性的方法。

在完備性定理中的排中律

有趣的是排中律(皮爾士定理形式的公理 3)只在我們的完備性證明中出現了一次。

相反的，Mendelson 命題邏輯的完備性證明在很多地方使用了排中律，特別是在把真值表的行合併在一起來除去命題變量依賴的步驟中。他使用了他的第三個公理 (¬A→¬B)→((¬A→B)→A) 來推導 (A→B)→((¬A→B)→B)，它接着被用來合併真值表的行到一起。

參見

引用

Mendelson, Elliot (1997) Introduction to Mathematical Logic, 4th ed. （頁面存檔備份，存於互聯網檔案館） London: Chapman & Hall.