# 常用的邏輯定理

## 用語說明

**前提假設**以Hyp簡記

[推論元定理](/XPmOwUeISle8_ixoUrge1Q?view#推論元定理)以"D"簡記。

由推論元定理可以知道$\vdash\mathcal{A}\Rightarrow\mathcal{B}$和$\mathcal{A}\vdash\mathcal{B}$是一樣的意思。所以證明過程中，你會看到代號D跟中途運用定理的代號寫在一起的簡記法，因為我們有時候會用$\mathcal{A}\vdash\mathcal{B}$的形式表達定理。

另外有兩個常用的推論，是來自於推論元定理
:::success
$\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$的代號，省略中間這段真正的過程，對理解證明是無傷大雅的。類似的，證明過程採用的定理，會以代號標記在它的推理結果後面，並寫明是運用哪個推理規則，但不會直接列出定理的完全形式。

而因為[(AND)](#直觀意義)，想要證明

$\vdash \mathcal{A}\Leftrightarrow\mathcal{B}$

等價於要證明下面兩式

$\vdash \mathcal{A}\Rightarrow\mathcal{B}$

$\vdash \mathcal{B}\Rightarrow\mathcal{A}$

我們習慣用($\Rightarrow$)標示$\mathcal{A}\Rightarrow\mathcal{B}$部分的證明，反之($\Leftarrow$)標示$\mathcal{B}\Rightarrow\mathcal{A}$部分的證明。

## 恆等
:::success
$\displaystyle(I)$推論的恆等(Identity of imply)

$\vdash\mathcal{A}\Rightarrow\mathcal{A}$

**證明**：
請參考[形式理論](/XPmOwUeISle8_ixoUrge1Q?view#證明)講解的範例。
:::

## 否定
:::success
$(DN)$(Double negation)

($\Rightarrow$)

$\vdash\neg\neg\mathcal{A}\Rightarrow\mathcal{A}$

($\Leftarrow$)

$\vdash\mathcal{A}\Rightarrow\neg\neg\mathcal{A}$

**證明**
<details>

($\Rightarrow$)

(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)

($\Leftarrow$)

(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)

</details>
:::

## 換位
:::success
$(T)$(Transposition)

($\Rightarrow$)

$\vdash(\neg\mathcal{A}\Rightarrow\neg\mathcal{B})\Rightarrow(\mathcal{B}\Rightarrow\mathcal{A})$

($\Leftarrow$)

$\vdash(\mathcal{B}\Rightarrow\mathcal{A})\Rightarrow(\neg\mathcal{A}\Rightarrow\neg\mathcal{B})$

**證明**
<details>

($\Rightarrow$)

(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)

($\Leftarrow$)

(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)

</details>
:::
(T)也是**反證法**(proof by contradiction)其中一種狀況。

## 實質條件
回憶一下，我們用真值表定義實質條件$A\Rightarrow B$為**不可能$\displaystyle A$是對的情況下$\displaystyle B$是錯的**。以下的定理重現了這個直觀的定義
:::success
$\displaystyle(M0)$(material condition)

$\neg\mathcal{A},\mathcal{A}\vdash\mathcal{B}$ (由(D)，也就是$\neg\mathcal{A}\vdash\mathcal{A}\Rightarrow\mathcal{B}$)

**證明**
<details>

(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)

</details>
:::

:::success
$\displaystyle (M1)$(material condition)

$\mathcal{A},\neg\mathcal{B}\vdash\neg(\mathcal{A}\Rightarrow\mathcal{B})$

**證明**
<details>

(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)

</details>
:::

:::success
$\displaystyle (M2)$(material condition)

$\neg(\mathcal{A}\Rightarrow\mathcal{B})\vdash\neg\mathcal{B}$

**證明**
<details>

(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)

</details>
:::

:::success
$\displaystyle (M3)$(material condition)

$\neg(\mathcal{A}\Rightarrow\mathcal{B})\vdash\mathcal{A}$

**證明**
<details>

(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)

</details>
:::

## 反證法
:::success
$(C1)$(proof by contradiction)

$\mathcal{A}\Rightarrow\neg\mathcal{B},\mathcal{B}\vdash\neg\mathcal{A}$

**證明**
<details>

(1)$(\mathcal{A}\Rightarrow\neg\mathcal{B})\Rightarrow(\neg\neg\mathcal{B}\Rightarrow\neg\mathcal{A})$ (T)

(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)

</details>
:::

:::success
$(C2)$(proof by contradiction)

$\neg\mathcal{A}\Rightarrow\mathcal{B},\neg\mathcal{B}\vdash\mathcal{A}$

**證明提示**：
將$(C1)$中的$\mathcal{A}$換成$\neg\mathcal{A}$，$\mathcal{B}$換成$\neg\mathcal{B}$，然後套用(DN)和(D2)。
:::

利用推論元定理把前提條件移到"$\vdash$"後面，可以發現(C1)和(C2)也是$\neg$的**換位**。

:::success
$\displaystyle (A3')$(Proof by contradiction)

$\mathcal{A}\Rightarrow\mathcal{B},\neg\mathcal{A}\Rightarrow\mathcal{B}\vdash\mathcal{B}$

**證明**
<details>

(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)

</details>
:::

## 且和或

### 交換性

我們有"且"的交換性

:::success
$\vdash(\mathcal{A}\wedge\mathcal{B})\Rightarrow(\mathcal{B}\wedge\mathcal{A})$

**證明**：

<details>

(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)

</details>
:::

類似的，(C2)正是"或"的"可交換性"：

:::success
$\mathcal{A}\vee\mathcal{B}\vdash\mathcal{B}\vee\mathcal{A}$ (C2, D)
:::

### 直觀意義

"且"的直觀意義是實質條件定理的直接結果

:::success
($AND$, Intuitive meaning of And)

$\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)跟推論元定理的直截結果

:::success

($OR$, Intuitive meaning of Or)

$\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')的直截結果

:::success
($DisJ$, Disjunction)

$\mathcal{A}\Rightarrow\mathcal{C},\mathcal{B}\Rightarrow\mathcal{C},\mathcal{A}\vee\mathcal{B}\vdash\mathcal{C}$

**證明**：

<details>

(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)

(5) $\mathcal{C}$ (A3' with 3, 4)

</details>
:::

### 結合律

對於"且"，我們可以從直觀意義輕鬆地得到

:::success
$(ASO)$ (Association)

$\vdash\mathcal{A}\wedge(\mathcal{B}\wedge\mathcal{C})\Leftrightarrow(\mathcal{A}\wedge\mathcal{B})\wedge\mathcal{C}$

**證明提示**： (AND)

:::

"或"也有類似的性質

:::success
$(ASO)$ (Association)

$\vdash\mathcal{A}\vee(\mathcal{B}\vee\mathcal{C})\Leftrightarrow(\mathcal{A}\vee\mathcal{B})\vee\mathcal{C}$

**證明提示**： (M1), (M2), (M3)

:::

### 分配律

"且"和"或"之間還有分配律

:::success
$(DIS)$(Distribution)

$\vdash\mathcal{A}\wedge(\mathcal{B}\vee\mathcal{C})\Leftrightarrow(\mathcal{A}\wedge\mathcal{B})\vee(\mathcal{A}\wedge\mathcal{C})$

**證明**：

<details>

($\Rightarrow$)

(1)$\mathcal{A}\wedge(\mathcal{B}\vee\mathcal{C})$ (Hyp)

(2)$\mathcal{A}$ (MP with 1, $\mathcal{D}\wedge\mathcal{E}\vdash\mathcal{D}$)

(3)$\neg\mathcal{B}\Rightarrow\mathcal{C}$ (MP with 1, $\mathcal{D}\wedge\mathcal{E}\vdash\mathcal{E}$)

(4)$\neg\neg(\mathcal{A}\Rightarrow\neg\mathcal{B})$ (Hyp)

(5)$\mathcal{A}\Rightarrow\neg\mathcal{B}$ (MP with 4, DN)

(6)$\mathcal{A}\Rightarrow\mathcal{C}$ (D1 with 3, 5)

(7)$\mathcal{C}$ (MP with 2, 5)

(8)$\mathcal{A}\wedge\mathcal{C}$ (MP twice with 2, 7, $\mathcal{D},\,\mathcal{E}\vdash\mathcal{D}\wedge\mathcal{E}$)

也就是

$\mathcal{A}\wedge(\mathcal{B}\vee\mathcal{C}),\,\neg(\mathcal{A}\wedge\mathcal{B})\vdash\mathcal{A}\wedge\mathcal{C}$

再套用一次推論元定理就會得到

$\mathcal{A}\wedge(\mathcal{B}\vee\mathcal{C})\vdash(\mathcal{A}\wedge\mathcal{B})\vee(\mathcal{A}\wedge\mathcal{C})$

($\Leftarrow$)

(1)$\neg(\mathcal{A}\wedge\mathcal{B})\Rightarrow\mathcal{A}\wedge\mathcal{C}$ (Hyp)

(2)$\neg(\mathcal{A}\wedge\mathcal{B})\Rightarrow\mathcal{A}$ (D1 with 1, $\mathcal{D}\wedge\mathcal{E}\vdash\mathcal{D}$)

(3)$\neg(\mathcal{A}\wedge\mathcal{B})\Rightarrow\mathcal{C}$ (D1 with 1, $\mathcal{D}\wedge\mathcal{E}\vdash\mathcal{E}$)

(4)$\neg\mathcal{A}\Rightarrow(\mathcal{A}\wedge\mathcal{B})$ (MP with 2, C2)

(5)$\neg\mathcal{C}\Rightarrow(\mathcal{A}\wedge\mathcal{B})$ (MP with 3, C2)

(6)$\neg\mathcal{A}\Rightarrow\mathcal{A}$ (D1 with 4, $\mathcal{D}\wedge\mathcal{E}\vdash\mathcal{D}$)

(7)$\neg\mathcal{C}\Rightarrow\mathcal{B}$ (D1 with 4, $\mathcal{D}\wedge\mathcal{E}\vdash\mathcal{E}$)

(8)$\mathcal{A}$ (A3' with 6, I)

(9)$\mathcal{A}\wedge(\mathcal{B}\vee\mathcal{C})$ (MP twice with 7, 8, $\mathcal{D},\,\mathcal{E}\vdash\mathcal{D}\wedge\mathcal{E}$)

也就是

$(\mathcal{A}\wedge\mathcal{B})\vee(\mathcal{A}\wedge\mathcal{C})\vdash\mathcal{A}\wedge(\mathcal{B}\vee\mathcal{C})$

</details>
:::

:::success
$(DIS)$(Distribution)

$\vdash\mathcal{A}\vee(\mathcal{B}\wedge\mathcal{C})\Leftrightarrow(\mathcal{A}\vee\mathcal{B})\wedge(\mathcal{A}\vee\mathcal{C})$

**證明**：

<details>

($\Rightarrow$)

(1)$\neg\mathcal{A}\Rightarrow(\mathcal{B}\wedge\mathcal{C})$(Hyp)

(2)$\neg\mathcal{A}\Rightarrow\mathcal{B}$ (D1 with 1, $\mathcal{D}\wedge\mathcal{E}\vdash\mathcal{D}$)

(3)$\neg\mathcal{A}\Rightarrow\mathcal{C}$ (D1 with 1, $\mathcal{D}\wedge\mathcal{E}\vdash\mathcal{E}$)

(4)$(\mathcal{A}\vee\mathcal{B})\wedge(\mathcal{A}\vee\mathcal{C})$(MP twice with 2, 3, $\mathcal{D},\,\mathcal{E}\vdash\mathcal{D}\wedge\mathcal{E}$)

也就是

$\mathcal{A}\vee(\mathcal{B}\wedge\mathcal{C})\vdash(\mathcal{A}\vee\mathcal{B})\wedge(\mathcal{A}\vee\mathcal{C})$

($\Leftarrow$)

(1)$(\neg\mathcal{A}\Rightarrow\mathcal{B})\wedge(\neg\mathcal{A}\Rightarrow\mathcal{C})$ (Hyp)

(2)$\neg\mathcal{A}\Rightarrow\mathcal{B}$ (MP with 1, $\mathcal{D}\wedge\mathcal{E}\vdash\mathcal{D}$)

(3)$\neg\mathcal{A}\Rightarrow\mathcal{C}$ (MP with 1, $\mathcal{D}\wedge\mathcal{E}\vdash\mathcal{E}$)

(4)$\neg\mathcal{A}$ (Hyp)

(5)$\mathcal{B}$ (MP with 2,4)

(6)$\mathcal{C}$ (MP with 3,4)

(7)$\mathcal{B}\wedge\mathcal{C}$ (MP twice with 5, 6, $\mathcal{D},\,\mathcal{E}\vdash\mathcal{D}\wedge\mathcal{E}$)

也就是

$\mathcal{A}\wedge(\mathcal{B}\vee\mathcal{C}),\,\neg\mathcal{A}\vdash\mathcal{B}\wedge\mathcal{C}$

再使用一次推論元定理會得到

$\mathcal{A}\wedge(\mathcal{B}\vee\mathcal{C})\vdash\mathcal{A}\vee(\mathcal{B}\wedge\mathcal{C})$

</details>
:::

## 等價性
直觀上可以用"等價"的敘述去取代另一個敘述，以下的元定理重現了這個直觀

:::success
($Equv$, Equivalence of wf)
若 $\ulcorner\vdash\mathcal{A}\Leftrightarrow\mathcal{B}\urcorner$ 且 $\ulcorner\vdash\mathcal{C}\Leftrightarrow\mathcal{D}\urcorner$ 則

(1) $\ulcorner\vdash(\mathcal{C}\Rightarrow\mathcal{A})\Leftrightarrow(\mathcal{D}\Rightarrow\mathcal{B})\urcorner$ (D)

(2) $\ulcorner\vdash\neg\mathcal{A}\Leftrightarrow\neg\mathcal{B}\urcorner$ (T)

(3) $\ulcorner\vdash(\forall x)\mathcal{A}\Leftrightarrow(\forall x)\mathcal{B}\urcorner$ (GEN and A7)
:::

以上三條可以依據$wf$的遞迴定義，讓任何的$wf$"等價地"寫為另一個$wf$。為了簡便起見這個遞迴的推論過程也會簡寫為(Equv)

## De Morgan定理
以下的定理都可以用真假值去理解；所以被引用時一律以De Morgan代稱(紀念英國邏輯學家Augustus De Morgan)

:::success
**De Morgan I**：

$\vdash\neg(\mathcal{A}\wedge\mathcal{B})\Leftrightarrow(\neg\mathcal{A})\vee(\neg\mathcal{B})$

**證明**
<details>

($\Rightarrow$)

>(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)

($\Leftarrow$)

>(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)

</details>
:::

:::success
**De Morgan II**：

$\vdash[\neg(\mathcal{A}\vee\mathcal{B})]\Leftrightarrow[(\neg\mathcal{A})\wedge(\neg\mathcal{B})]$

**證明**

<details>

($\Rightarrow$)
>(1) $\neg(\neg\mathcal{A}\Rightarrow\mathcal{B})$ (Hyp)

>(2) $\neg\mathcal{A}$ (MP with M2, 1)

>(3) $\neg\mathcal{B}$ (MP with M3, 1)

>(4) $(\neg\mathcal{A})\wedge(\neg\mathcal{B})$ (AND with 2, 3)

($\Leftarrow$)

>(1) $\neg\mathcal{A}$ (Hyp)

>(2) $\neg\mathcal{B}$ (Hyp)

>(3) $\neg(\neg\mathcal{A}\Rightarrow\mathcal{B})$ (M1)

</details>
:::