第摩根定理 (DeMorgan’s Law) 的證明

Proof of DeMorgan’s Law

集合代數的第摩根定理：

($a$)    $(x\cup y)^{c} = x^{c}\cap y^{c}$              ($b$)     $(x\cap y)^{c} = x^{c} \cup y^{c}$

布林代數的第摩根定理：

($a^{'}$)    $(x+y)^{'} = x^{'}·y^{'} $               ($b^{'}$)    $(x·y)^{'} = x^{'}+y^{'} $

集合代數的第摩根定理，一般可藉由文氏圖 (Venn Diagrams) 輕易得到證明。本文除了介紹以文氏圖及代數證明集合運算的第摩根定理之外，將以在 $x$ 與 $y$ 為布林代數的二元變數情況下，證明布林代數的第摩根定理。最後並嘗試以真值表搭配卡諾圖化簡來提供布林代數的第摩根定理另一種證明方法。

以文氏圖證明集合論的第摩根定理

證明 (a)：

設 $x$ 及 $y$ 為兩相異集合，如下的文氏圖所示：

$x\cup y$

$(x\cup y)^c$

其中的 $(x\cup y)^c$ 為 $(x\cup y)$ 的補集。

$x^c$

$y^c$

$x^c\cap y^c$

可知 $(x\cup y)^c$ 與 $x^c\cap y^c$ 的圖是一樣的，所以，

$$(x\cup y)^c = x^c\cap y^c \;\;\;\;\;\;\;\;\; 得證。$$

證明 (b)：

$(x\cap y)^c$

$x^c$

$y^c$

$x^c\cup y^c$

可知 $(x\cap y)^c$ 與 $x^c\cup y^c$ 的圖是一樣的，所以

$$(x\cap y)^c = x^c\cup y^c\;\;\;\;\;\;\;\;\;\; 得證。$$

以代數證明集合論的第摩根定理

證明 (a)：

$$\forall \; z \in (x\cup y)^c$$

$$\iff  z \notin (x\cup y)\;\;\;\;\;\;\;\;\;$$

$$\;\;\;\;\;\;\;\;\iff  z \notin x\;\;\;\;\;\;and\;\;\;\;\;\;z \notin y$$

$$\;\;\;\;\;\;\;\;\;\;\;\iff  z \in x^c\;\;\;\;\;\;and\;\;\;\;\;\;z \in y^c$$

$$\iff z \in  x^c \cap y^c\;\;\;\;\;\;\;\;\;$$      

所以，

$$(x\cup y)^c = x^c \cap y^c\;\;\;\;\;\;\;\;得證。$$

證明 (b)：

$$\forall  z \in (x\cap y)^c$$

$$\iff z \notin (x\cap y)\;\;\;\;\;\;\;$$

$$\;\;\;\;\;\;\;\;\iff  z\notin x\;\;\;\;\;\;or\;\;\;\;\;\;z\notin y$$

$$\;\;\;\;\;\;\;\;\;\;\;\iff z\in x^c\;\;\;\;\;\;or\;\;\;\;\;\;z\in y^c$$

$$\;\;\;\iff z \in x^c  \cup y^c\;\;\;\;\;\;\;\;\;$$

所以，

$$(x\cap y)^c = x^c \cup y^c\;\;\;\;\;\;\;\; 得證。$$

以布林代數證明第摩根定理

證明 ($a^{'}$)：

假設 $x$、$y$ 及 $z$ 為布林變數 (Boolean Variables)，亦即 $x$、$y$ 及 $z$ 為二元變數，其值為 $0$ 或 $1$。若

$$z = (x+y)^{'}$$

$$\iff z\neq (x+y)\;\;\;\;\;\;\;$$

$$\;\;\;\;\;\;\;\;\;\;\iff z\neq x\;\;\;\;\;\;and\;\;\;\;\;\;z\neq y$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\iff  z = x^{'}\;\;\;\;\;\;and\;\;\;\;\;\;z = y^{'}$$

$$\iff z = x^{'}\cdot y^{'}\;\;\;\;\;\;\;\;$$

亦即

$$(x+y)^{'} = x^{'}·y^{'} $$

得證。

證明 ($b^{'}$)：

若

$$z = (x\cdot y)^{'}$$

$$\iff z \neq (x\cdot y)\;\;\;\;\;\;\;$$

$$\;\;\;\;\;\;\;\;\;\iff z\neq x\;\;\;\;\;\;or\;\;\;\;\;\;z\neq y$$

$$\;\;\;\;\;\;\;\;\;\;\;\iff z = x^{'}\;\;\;\;\;\;or\;\;\;\;\;\;z = y^{'}$$

$$\iff z = x^{'}+y^{'}\;\;\;\;\;\;$$

亦即，

$$(x·y)^{'} = x^{'}+y^{'} $$

得證。

以真值表證明第摩根定理

證明 ($a^{'}$)：

假設 $x$、$y$ 及 $z$ 為布林變數，若 $z = (x+y)^{'}$，則 $z^{'} = x+y$，則其真值表如下表所示：

則可得布林代數式  $z = x^{'}\cdot y^{'}$ ，亦即

$$(x+y)^{'} = x^{'}\cdot y^{'}$$  

得證。

證明 ($b^{'}$)：

若 $z = (x\cdot y)^{'}$，則 $z^{'} = x\cdot y$，則其真值表如下表所示：

則可得布林代數式 $z = x^{'}\cdot y^{'}+x^{'}\cdot y + x\cdot y^{'}$。

上式經如下所示的卡諾圖 (K-map) 化簡，可得

$z = x^{'}+y^{'}$ ，亦即

$$(x\cdot y)^{'} = x^{'}+y^{'}$$

得證。