德·摩根定律

在命題邏輯和邏輯代數中，德·摩根定律（或稱德·摩根定理）是關於命題邏輯規律的一對法則。

奧古斯都·德·摩根首先發現了在命題邏輯中存在著下面這些關係：

非(P 且 Q) = (非 P) 或 (非 Q)

非(P 或 Q) = (非 P) 且 (非 Q)

德·摩根定律在數理邏輯的定理推演中，在計算機的邏輯設計中以及數學的集合運算中都起著重要的作用。他的發現影響了喬治·布爾從事的邏輯問題代數解法的研究。這鞏固了德摩根作為該規律的發現者的地位，儘管亞里士多德也曾注意到類似現象，且這也為古希臘與中世紀的邏輯學家熟知。

該定律也被稱作反演律。

基本介紹

• 中文名：德·摩根定律
• 外文名：De Morgan's laws 
• 別稱：狄摩根定律
• 表達式：非(P且Q)=(非P)或(非Q)
• 提出者：奧古斯都·德·摩根
• 套用學科：代數
• 適用領域範圍：真勢模態
• 適用領域範圍：命題邏輯規律、電子技術

定理定義

形式邏輯中此定律表達形式：

在集合論中：

在機率論中;

定理推廣

在經典命題邏輯的外延中，此二元性依然有效（即對於任意的邏輯運算符，我們都能找他它的對偶），由於存在於調節否定關係的恆等式中，人們總會引入作為一個算符的德·摩根對偶的另一個算符。這導致了基於傳統邏輯的邏輯學的一個重要性質，即否定範式的存在性：任何公式等價於另外一個公式，其中否定僅出現在作用於公式中非邏輯的原子時。否定常型的存在推進了許多套用，例如在數字電路設計中該性質用於操縱邏輯門，以及在形式邏輯中該性質是尋找一個公式的合取範式和析取範式的必要條件；電腦程式員們則用它們將一個類似於IF ... AND (... OR ...) THEN ... 這樣的複雜語句轉變為其對等形式；它們也同樣經常用於初等機率論中的計算。

我們將基於基本命題p,q的任意命題算符P(p,q,...）的對偶定義為：

.

該概念可以推廣到邏輯量詞上，例如全稱量詞和存在量詞互為對偶：

,

“對所有x，P(x）皆成立”等價於“不存在x，使P(x）不成立”；

.

“存在x，使P(x）成立”等價於“並非對所有x，P(x）都不成立”。

為對德·摩根定律敘述這些量詞的二元性，設定一個在其域D中具有少量元素的模型，例如

D = {a,b,c}.

則

“對所有x，P(x）成立”等價於“P(a）成立”且“P(b）成立”且“P(c）成立”

以及

.

“存在x，使P(x）成立”等價於“P(a）成立”或“P(b）成立”或“P(c）成立”

但，套用德·摩根定律，

.

“‘P(a)成立’且‘P(b）成立’且‘P(c）成立’”等價於“非（‘P(a）不成立’或‘P(b）不成立’或‘P(c）不成立’）”

以及

,

“‘P(a)成立’或‘P(b）成立’或‘P(c）成立’”等價於“非（‘P(a）不成立’且‘P(b）不成立’且‘P(c）不成立’）”

檢驗模型中量詞的二元性。

從而，量詞的二元性可進一步延伸到模態邏輯中的方塊和菱形算符：

,

.

推導過程

(xy)=x|y

(x|y)=xy

(x+1)=x-1

(x-1)=x+1

-x=x-1

(xy)=xy=x≡y

(x≡y)=x≡y=xy

(x+y)=x-y

(x-y)=x+y

上述公式可以這樣用：(x|-(x+1))=x-(x+1)=-x((x+1)-1)=xx=0。

實驗驗證

真值證明

假設你要證明： (A v B) = A ^ B，則可構造真值表如下：

A	B	A v B	(A v B)	A	B	A ^; B
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

可見，在A和B的所有可能取值下， (A v B)與 A ^ B的值都相同，故要證明的式子成立.
對於 (A ^ B) = A v B 的情形可以同樣的方法證明.

邏輯證明

設x屬於C_u(A∪B)
則x屬於u卻不屬於A∪B
所以x屬於u卻不屬於A，也不屬於B
故x屬於C_uA且屬於C_uB,
故x屬於C_uA∩C_uB,
反過來，式子仍然成立.
同理，另一式也成立.

發展簡史

奧古斯都·德·摩根首先發現了在命題邏輯中存在著下面這些關係：
非(P 且 Q)=(非 P)或(非 Q)
非(P 或 Q)=(非 P)且(非 Q)
德·摩根的發現影響了喬治·布爾從事的邏輯問題代數解法的研究，這鞏固了德·摩根作為該規律的發現者的地位，儘管亞里士多德也曾注意到類似現象、且這也為古希臘與中世紀的邏輯學家熟知(引自Bocheński《形式邏輯歷史》)。
形式邏輯中此定律表達形式：
\neg(P\wedge Q)=(\neg P)\VEE(\neg Q)
\neg(P\vee Q)=(\neg P)\wedge(\neg Q)
在集合論中：
(A\cap B)^C=A^C\cup B^C
(A\cup B)^C=A^C\cap B^C.
在經典命題邏輯的外延中，此二元性依然有效(即對於任意的邏輯運算符，我們都能找他它的對偶)，由於存在於調節否定關係的恆等式中，人們總會引入作為一個算符的德·摩根對偶的另一個算符。這導致了基於傳統邏輯的邏輯學的一個重要性質，即否定範式的存在性：任何公式等價於另外一個公式，其中否定僅出現在作用於公式中非邏輯的原子時。否定常型的存在推進了許多套用，例如在數字電路設計中該性質用於操縱邏輯門，以及在形式邏輯中該性質是尋找一個公式的合取範式和析取範式的必要條件；電腦程式員們則用它們將一個類似於IF ... AND (... OR ...) THEN ... 這樣的複雜語句轉變為其對等形式；它們也同樣經常用於初等機率論中的計算。
我們將基於基本命題p, q的任意命題算符P(p, q, ...)的對偶定義為：
\neg \MBOX^d(\neg p, \neg q, ...).
該概念可以推廣到邏輯量詞上，例如全稱量詞和存在量詞互為對偶：
\forall x \, P(x) \equiv \neg \exists x \, \neg P(x),
“對所有x，P(x)皆成立”等價於“不存在x，使P(x)不成立”；
\exists x \, P(x) \equiv \neg \forall x \, \neg P(x).
“存在x，使P(x)成立”等價於“並非對所有x，P(x)都不成立”。
為對德·摩根定律敘述這些量詞的二元性，設定一個在其域D中具有少量元素的模型，例如
D = {a, b, c}.
則
\forall x \, P(x) \equiv P(a) \wedge P(b) \wedge P(c)
“對所有x，P(x)成立”等價於“P(a)成立”且“P(b)成立”且“P(c)成立”
以及
\exists x \, P(x) \equiv P(a) \vee P(b) \vee P(c).
“存在x，使P(x)成立”等價於“P(a)成立”或“P(b)成立”或“P(c)成立”
但，套用德·摩根定律，
P(a) \wedge P(b) \wedge P(c) \equiv \neg (\neg P(a) \vee \neg P(b) \vee \neg P(c))
“‘P(a)成立’且‘P(b)成立’且‘P(c)成立’”等價於“非(‘P(a)不成立’或‘P(b)不成立’或‘P(c)不成立’)”
以及
P(a) \vee P(b) \vee P(c) \equiv \neg (\neg P(a) \wedge \neg P(b) \wedge \neg P(c)),
“‘P(a)成立’或‘P(b)成立’或‘P(c)成立’”等價於“非(‘P(a)不成立’且‘P(b)不成立’且‘P(c)不成立’)”
檢驗模型中量詞的二元性。
從而，量詞的二元性可進一步延伸到模態邏輯中的方塊和菱形算符：
\Box p \equiv \neg \Diamond \neg p,
\Diamond p \equiv \neg \Box \neg p.
在其用於可能性和必然性的真勢模態的套用中，亞里士多德注意到該情況，以及在正規模態邏輯的情況中，這些模態算符對量化的關係可藉助按關係語義設定模型來理解。

套用領域

在其用於可能性和必然性的真勢模態的套用中，亞里士多德注意到該情況，以及在正規模態邏輯的情況中，這些模態算符對量化的關係可藉助按關係語義設定模型來理解。