用戶:C44986054/數理邏輯/常用的邏輯定理
本章所採用的形式理論，其完整內容可以參考一階邏輯#型式理論。
前提假設以Hyp簡記
推論元定理以"D"簡記，內容可以參考形式理論#推論元定理。
由推論元定理可以知道$\vdash\mathcal{A}\Rightarrow\mathcal{B}$和$\mathcal{A}\vdash\mathcal{B}$是一樣的意思。所以證明過程中，你會看到代號D跟中途運用定理的代號寫在一起的簡記法，因為我們有時候會用$\mathcal{A}\vdash\mathcal{B}$的形式表達定理。
另外有兩個常用的推論，是來自於推論元定理
$\displaystyle (D1)$$\mathcal{A}\Rightarrow\mathcal{B},\mathcal{B}\Rightarrow\mathcal{C}\vdash\mathcal{A}\Rightarrow\mathcal{C}$
$\displaystyle (D2)$$\mathcal{A}\Rightarrow(\mathcal{B}\Rightarrow\mathcal{C}),\mathcal{B}\vdash\mathcal{A}\Rightarrow\mathcal{C}$
下面應用(D1)或(D2)構造證明的時候，實際上相當於施用兩次MP律；但只要我們寫出應用(D1)或(D2)所需要的兩段$\displaystyle wfs$的代號，省略中間這段真正的過程，對理解證明是無傷大雅的。類似的，證明過程採用的定理，會以代號標記在它的推理結果後面，並寫明是運用哪個推理規則，但不會直接列出定理的完全形式。
恆等
$\displaystyle(I)$推論的恆等(Identity of imply)
$\vdash\mathcal{A}\Rightarrow\mathcal{A}$
證明：請參考形式理論#證明講解的範例。
否定
$\displaystyle (DNe)$雙否定(消去)(Double negation, elimination)
$\vdash\neg\neg\mathcal{A}\Rightarrow\mathcal{A}$
| 證明 |
|---|
|
(1)$(\neg\mathcal{A}\Rightarrow\neg\neg\mathcal{A})\Rightarrow[(\neg\mathcal{A}\Rightarrow\neg\mathcal{A})\Rightarrow\mathcal{A}]$ (A3) (2)$\neg\mathcal{A}\Rightarrow\neg\mathcal{A}$ (I) (3)$(\neg\mathcal{A}\Rightarrow\neg\neg\mathcal{A})\Rightarrow\mathcal{A}$ (D2 with 1, 2) (4)$\neg\neg\mathcal{A}\Rightarrow(\neg\mathcal{A}\Rightarrow\neg\neg\mathcal{A})$ (A1) (5)$\neg\neg\mathcal{A}\Rightarrow\mathcal{A}$ (D1 with 3, 4) |
$\displaystyle (DNi)$雙否定(引入)(Double negation, introduction)
$\vdash\mathcal{A}\Rightarrow\neg\neg\mathcal{A}$
| 證明 |
|---|
|
(1)$(\neg\neg\neg\mathcal{A}\Rightarrow\neg\mathcal{A})\Rightarrow[(\neg\neg\neg\mathcal{A}\Rightarrow\mathcal{A})\Rightarrow\neg\neg\mathcal{A}]$ (A3) (2)$(\neg\neg\neg\mathcal{A}\Rightarrow\mathcal{A})\Rightarrow\neg\neg\mathcal{A}$ (MP with DNe, 1) (3)$\mathcal{A}\Rightarrow(\neg\neg\neg\mathcal{A}\Rightarrow\mathcal{A})$ (A1) (4)$\mathcal{A}\Rightarrow\neg\neg\mathcal{A}$ (D1 with 2,3) |
上面兩定理表達了雙否定推理上等價於於原$\displaystyle wf$，日後引用兩者任一會以DN簡寫。
換位
$\displaystyle (T1)$(Transposition)
$\neg\mathcal{A}\Rightarrow\neg\mathcal{B}\vdash\mathcal{B}\Rightarrow\mathcal{A}$
| 證明 |
|---|
|
(1)$(\neg\mathcal{A}\Rightarrow\neg\mathcal{B})\Rightarrow[(\neg\mathcal{A}\Rightarrow\mathcal{B})\Rightarrow\mathcal{A}]$ (A3) (2)$\neg\mathcal{A}\Rightarrow\neg\mathcal{B}$ (Hyp) (3)$(\neg\mathcal{A}\Rightarrow\mathcal{B})\Rightarrow\mathcal{A}$ (MP with 1, 2) (4)$\mathcal{B}\Rightarrow(\neg\mathcal{A}\Rightarrow\mathcal{B})$ (A1) (5)$\mathcal{B}\Rightarrow\mathcal{A}$ (D1 with 3, 4) |
$\displaystyle (T2)$(Transposition)
$\mathcal{B}\Rightarrow\mathcal{A}\vdash\neg\mathcal{A}\Rightarrow\neg\mathcal{B}$
| 證明 |
|---|
|
(1)$\neg\neg\mathcal{B}\Rightarrow\mathcal{B}$ (DN) (2)$\mathcal{B}\Rightarrow\mathcal{A}$ (Hyp) (3)$\neg\neg\mathcal{B}\Rightarrow\mathcal{A}$ (D1 with 1, 2) (4)$\mathcal{A}\Rightarrow\neg\neg\mathcal{A}$ (DN) (5)$\neg\neg\mathcal{B}\Rightarrow\neg\neg\mathcal{A}$ (D1 with 3,4) (6)$(\neg\neg\mathcal{B}\Rightarrow\neg\neg\mathcal{A})\Rightarrow(\neg\mathcal{A}\Rightarrow\neg\mathcal{B})$ (T1, D) (7)$\neg\mathcal{A}\Rightarrow\neg\mathcal{B}$ (MP with 5, 6) |
這兩個定理表說明$\mathcal{B}\Rightarrow\mathcal{A}$推理上等價於$\neg\mathcal{A}\Rightarrow\neg\mathcal{B}$，日後引用這兩個定理其中任一，都用(T)表示。
另外這兩個定理也是反證法(proof by contradiction)其中的兩種狀況。
實質條件
以下的定理重現了實質條件直觀的定義
$\displaystyle(M0)$(material condition)
$\neg\mathcal{A},\mathcal{A}\vdash\mathcal{B}$
(由(D)，也就是$\neg\mathcal{A}\vdash\mathcal{A}\Rightarrow\mathcal{B}$)
| 證明 |
|---|
|
(1)$\neg\mathcal{A}$ (Hyp) (2)$\mathcal{A}$ (Hyp) (3)$(\neg\mathcal{B}\Rightarrow\neg\mathcal{A})\Rightarrow[(\neg\mathcal{B}\Rightarrow\mathcal{A})\Rightarrow\mathcal{B}]$ (A3) (4)$\neg\mathcal{A}\Rightarrow(\neg\mathcal{B}\Rightarrow\neg\mathcal{A})$ (A1) (5)$\neg\mathcal{B}\Rightarrow\neg\mathcal{A}$ (MP with 4, 1) (6)$\mathcal{A}\Rightarrow(\neg\mathcal{B}\Rightarrow\mathcal{A})$ (A1) (7)$\neg\mathcal{B}\Rightarrow\mathcal{A}$ (MP with 6, 2) (8)$(\neg\mathcal{B}\Rightarrow\mathcal{A})\Rightarrow\mathcal{B}$ (MP with 3,5) (9)$\mathcal{B}$ (MP with 8,7) |
$\displaystyle (M1)$(material condition)
$\mathcal{A},\neg\mathcal{B}\vdash\neg(\mathcal{A}\Rightarrow\mathcal{B})$
| 證明 |
|---|
|
首先注意到(0)$\mathcal{A},\mathcal{A}\Rightarrow\mathcal{B}\vdash\mathcal{B}$ (MP) (1)$\mathcal{A}\Rightarrow[(\mathcal{A}\Rightarrow\mathcal{B})\Rightarrow\mathcal{B}]$ (0, D) (2)$[(\mathcal{A}\Rightarrow\mathcal{B})\Rightarrow\mathcal{B}]\Rightarrow\{\neg\mathcal{B}\Rightarrow[\neg(\mathcal{A}\Rightarrow\mathcal{B})]\}$ (T) (3)$\mathcal{A}$ (Hyp) (4)$(\mathcal{A}\Rightarrow\mathcal{B})\Rightarrow\mathcal{B}$ (MP with 1, 3) (5)$\neg\mathcal{B}\Rightarrow[\neg(\mathcal{A}\Rightarrow\mathcal{B})]$ (MP with 2, 4) (6)$\neg\mathcal{B}$ (Hyp) (7)$\neg(\mathcal{A}\Rightarrow\mathcal{B})$ (MP 5, 6) |
$\displaystyle (M2)$(material condition)
$\neg(\mathcal{A}\Rightarrow\mathcal{B})\vdash\neg\mathcal{B}$
| 證明 |
|---|
|
(1)$\mathcal{B}\Rightarrow(\mathcal{A}\Rightarrow\mathcal{B})$ (A1) (2)$[\mathcal{B}\Rightarrow(\mathcal{A}\Rightarrow\mathcal{B})]\Rightarrow\{[\neg(\mathcal{A}\Rightarrow\mathcal{B})]\Rightarrow(\neg\mathcal{B})\}$ (T) (3)$[\neg(\mathcal{A}\Rightarrow\mathcal{B})]\Rightarrow(\neg\mathcal{B})$ (MP with 1, 2) (4)$\neg(\mathcal{A}\Rightarrow\mathcal{B})$ (Hyp) (5)$\neg\mathcal{B}$ (MP with 3, 4) |
$\displaystyle (M3)$(material condition)
$\neg(\mathcal{A}\Rightarrow\mathcal{B})\vdash\mathcal{A}$
| 證明 |
|---|
|
(1)$\neg\mathcal{A}\Rightarrow(\mathcal{A}\Rightarrow\mathcal{B})$ (M0, D) (2)$[\neg\mathcal{A}\Rightarrow(\mathcal{A}\Rightarrow\mathcal{B})]\Rightarrow\{[\neg(\mathcal{A}\Rightarrow\mathcal{B})]\Rightarrow(\neg\neg\mathcal{A})\}$ (T) (3)$[\neg(\mathcal{A}\Rightarrow\mathcal{B})]\Rightarrow(\neg\neg\mathcal{A})$ (MP with 1, 2) (4)$\neg(\mathcal{A}\Rightarrow\mathcal{B})$ (Hyp) (5)$\neg\neg\mathcal{A}$ (MP with 3,4) (6)$\mathcal{A}$ (MP with 5, DN) |
反證法
$\displaystyle(C1)$(proof by contradiction)
$\mathcal{A}\Rightarrow\neg\mathcal{B},\mathcal{B}\vdash\neg\mathcal{A}$
| 證明 |
|---|
|
(1)$(\mathcal{A}\Rightarrow\neg\mathcal{B})\Rightarrow(\neg\neg\mathcal{B}\Rightarrow\neg\mathcal{A})$ (T, D) (2)$\mathcal{A}\Rightarrow\neg\mathcal{B}$ (Hyp) (3)$\neg\neg\mathcal{B}\Rightarrow\neg\mathcal{A}$ (MP with 1, 2) (4)$\mathcal{B}$ (Hyp) (5)$\neg\neg\mathcal{B}$ (MP with DN, 4) (6)$\neg\mathcal{A}$ (MP with 3, 5) |
$\displaystyle(C2)$(proof by contradiction)
$\neg\mathcal{A}\Rightarrow\mathcal{B},\neg\mathcal{B}\vdash\mathcal{A}$
證明提示：仿$\displaystyle(C1)$的證明。
利用推論元定理把前提條件移到"$\vdash$"後面，可以發現(C1)和(C2)也是換位。
$\displaystyle (A3')$(Proof by contradiction)
$\mathcal{A}\Rightarrow\mathcal{B},\neg\mathcal{A}\Rightarrow\mathcal{B}\vdash\mathcal{B}$
| 證明 |
|---|
|
(1)$(\neg\mathcal{B}\Rightarrow\neg\neg\mathcal{A})\Rightarrow[(\neg\mathcal{B}\Rightarrow\neg\mathcal{A})\Rightarrow\mathcal{B}]$ (A3) (2)$(\neg\mathcal{A}\Rightarrow\mathcal{B})\Rightarrow(\neg\mathcal{B}\Rightarrow\neg\neg\mathcal{A})$ (T, D) (3)$\neg\mathcal{A}\Rightarrow\mathcal{B}$ (Hyp) (4)$\neg\mathcal{B}\Rightarrow\neg\neg\mathcal{A}$ (MP with 2, 3) (5)$(\neg\mathcal{B}\Rightarrow\neg\mathcal{A})\Rightarrow\mathcal{B}$ (MP with 1, 4) (6)$(\mathcal{A}\Rightarrow\mathcal{B})\Rightarrow(\neg\mathcal{B}\Rightarrow\neg\mathcal{A})$ (T, D) (7)$\mathcal{A}\Rightarrow\mathcal{B}$ (Hyp) (8)$\neg\mathcal{B}\Rightarrow\neg\mathcal{A}$ (MP with 6, 7) (9)$\mathcal{B}$ (MP with 5, 8) |
且和或
"且"和"或"的形式定義請參考命題邏輯#且和或
其實由(C1)可以發現"且"的"交換性"：
$\vdash(\mathcal{A}\wedge\mathcal{B})\Rightarrow(\mathcal{B}\wedge\mathcal{A})$
| 證明 |
|---|
|
(1)$(\mathcal{B}\Rightarrow\neg\mathcal{A})\Rightarrow(\mathcal{A}\Rightarrow\neg\mathcal{B})$ (C1, D) (2)$[(\mathcal{B}\Rightarrow\neg\mathcal{A})\Rightarrow(\mathcal{A}\Rightarrow\neg\mathcal{B})]\Rightarrow\{[\neg(\mathcal{A}\Rightarrow\neg\mathcal{B})]\Rightarrow[\neg(\mathcal{B}\Rightarrow\neg\mathcal{A})]\}$ (T, D) (3)$[\neg(\mathcal{A}\Rightarrow\neg\mathcal{B})]\Rightarrow[\neg(\mathcal{B}\Rightarrow\neg\mathcal{A})]$ (MP with 1,2) |
類似的，(C2)正是"或"的"可交換性"：
$\mathcal{A}\vee\mathcal{B}\vdash\mathcal{B}\vee\mathcal{A}$ (C2, D)
"且"的直觀意義是實質條件定理的直接結果
$\mathcal{A},\mathcal{B}\vdash\mathcal{A}\wedge\mathcal{B}$ (M1)
$\mathcal{A}\wedge\mathcal{B}\vdash\mathcal{A}$ (M3)
$\mathcal{A}\wedge\mathcal{B}\vdash\mathcal{B}$ (M2)
類似的，"或"的直觀意義是(M0)跟推論元定理的直截結果
$\mathcal{A}\vdash\mathcal{A}\vee\mathcal{B}$ (M0, DN)
$\mathcal{B}\vdash\mathcal{A}\vee\mathcal{B}$ (A1, D)
$\mathcal{A}\vee\mathcal{B},\neg\mathcal{A}\vdash\mathcal{B}$ (D)
$\mathcal{A}\vee\mathcal{B},\neg\mathcal{B}\vdash\mathcal{A}$ (交換性, D)
以下的定理則是(A3')的直截結果
$\displaystyle (Dis)$(Disjunction)
$\mathcal{A}\Rightarrow\mathcal{C},\mathcal{B}\Rightarrow\mathcal{C},\mathcal{A}\vee\mathcal{B}\vdash\mathcal{C}$
| 證明 |
|---|
|
(1)$\neg\mathcal{A}\Rightarrow\mathcal{B}$ (Hyp) (2)$\mathcal{B}\Rightarrow\mathcal{C}$ (Hyp) (3)$\neg\mathcal{A}\Rightarrow\mathcal{C}$ (D1 with 1, 2) (4)$\mathcal{A}\Rightarrow\mathcal{C}$ (Hyp) 3,4帶入定理(A3')就會得到$\mathcal{C}$。$\Box$ |
De Morgan定理
以下的定理都可以用真假值去理解；所以被引用時一律以De Morgan代稱(紀念英國邏輯學家Augustus De Morgan)
De Morgan I(left)：
$\neg(\mathcal{A}\wedge\mathcal{B})\vdash(\neg\mathcal{A})\vee(\neg\mathcal{B})$
| 證明 |
|---|
|
(1)$\neg\neg[\mathcal{A}\Rightarrow(\neg\mathcal{B})]$ (Hyp) (2)$\mathcal{A}\Rightarrow(\neg\mathcal{B})$ (MP with 1, DN) (3)$\neg\neg\mathcal{A}\Rightarrow\mathcal{A}$ (DN) (4)$\neg\neg\mathcal{A}\Rightarrow(\neg\mathcal{B})$ (D1 with 2, 3) |
De Morgan I(Right)：
$(\neg\mathcal{A})\vee(\neg\mathcal{B})\vdash\neg(\mathcal{A}\wedge\mathcal{B})$
| 證明 |
|---|
|
(1)$\neg\neg\mathcal{A}\Rightarrow(\neg\mathcal{B})$ (Hyp) (2)$\mathcal{A}\Rightarrow\neg\neg\mathcal{A}$ (DN) (3)$\mathcal{A}\Rightarrow(\neg\mathcal{B})$ (D1 with 1, 2) (4)$\neg\neg[\mathcal{A}\Rightarrow(\neg\mathcal{B})]$ (MP with DN, 3) |
De Morgan II(left)：
$\vdash[\neg(\mathcal{A}\vee\mathcal{B})]\Rightarrow[(\neg\mathcal{A})\wedge(\neg\mathcal{B})]$
| 證明 |
|---|
|
注意到(0)$(\neg\mathcal{A})\Rightarrow(\neg\neg\mathcal{B}),\neg\mathcal{A}\vdash\mathcal{B}$ (DN) (1)$[(\neg\mathcal{A})\Rightarrow(\neg\neg\mathcal{B})]\Rightarrow(\neg\mathcal{A}\Rightarrow\mathcal{B})$ (0, D) (2)$\{[(\neg\mathcal{A})\Rightarrow(\neg\neg\mathcal{B})]\Rightarrow(\neg\mathcal{A}\Rightarrow\mathcal{B})\}\Rightarrow\{\neg(\neg\mathcal{A}\Rightarrow\mathcal{B})\Rightarrow\neg[(\neg\mathcal{A})\Rightarrow(\neg\neg\mathcal{B})]\}$ (T) (3)$\neg(\neg\mathcal{A}\Rightarrow\mathcal{B})\Rightarrow\neg[(\neg\mathcal{A})\Rightarrow(\neg\neg\mathcal{B})]$ (MP with 1, 2) |
De Morgan II(right)：
$\vdash[(\neg\mathcal{A})\wedge(\neg\mathcal{B})]\Rightarrow[\neg(\mathcal{A}\vee\mathcal{B})]$
證明提示：仿De Morgan II(left)