基本介紹
- 中文名：德·摩根定律
- 外文名：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
(xy)=xy=x≡y
(x≡y)=x≡y=xy
(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屬於Cu(A∪B)
則x屬於u卻不屬於A∪B
所以x屬於u卻不屬於A，也不屬於B
故x屬於CuA且屬於CuB,
故x屬於CuA∩CuB,
反過來，式子仍然成立.
同理，另一式也成立.
發展簡史
奧古斯都·德·摩根首先發現了在命題邏輯中存在著下面這些關係：
非(P 且 Q)=(非 P)或(非 Q)
非(P 或 Q)=(非 P)且(非 Q)
德·摩根的發現影響了喬治·布爾從事的邏輯問題代數解法的研究，這鞏固了德·摩根作為該規律的發現者的地位，儘管亞里士多德也曾注意到類似現象、且這也為古希臘與中世紀的邏輯學家熟知(引自Bocheński《形式邏輯歷史》)。
形式邏輯中此定律表達形式：
在集合論中：
我們將基於基本命題p, q的任意命題算符P(p, q, ...)的對偶定義為：
\neg \MBOX^d(\neg p, \neg q, ...).
該概念可以推廣到邏輯量詞上，例如全稱量詞和存在量詞互為對偶：
“對所有x，P(x)皆成立”等價於“不存在x，使P(x)不成立”；
“存在x，使P(x)成立”等價於“並非對所有x，P(x)都不成立”。
為對德·摩根定律敘述這些量詞的二元性，設定一個在其域D中具有少量元素的模型，例如
“對所有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)不成立’)”
檢驗模型中量詞的二元性。
從而，量詞的二元性可進一步延伸到模態邏輯中的方塊和菱形算符：
