• Moegirl.ICU：萌娘百科流亡社群 581077156（QQ），欢迎对萌娘百科运营感到失望的编辑者加入！
  • Moegirl.ICU：账号认领正在试运行，有意者请参照账号认领流程。

User: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)

use MathJax

检索自“https://moegirl.icu/index.php?title=User:C44986054/數理邏輯/常用的邏輯定理&oldid=5734822”