德摩根律

德摩根律

德摩根律是數學中的邏輯學法則,用文字表述就是:C並上A與B的交集等於C與A的並集並上C與B的並集;C並上A與B的並集等於C與A的並集交上C與B的並集。

德摩根律(德·摩根)的公式表述

DeMorgan's Theorem 
1.Cs (A∩B)=CsA U CsB
2.Cs (A∪B)=CsA ∩CsB
CUAcub=Cu(A∪B),CuA∪CuB=Cu(A∩B)
3.設全集為U,其子集為A,B.則
Cu(A∪B)=CuA∩CuB, Cu(A∩B)=CuA∪CuB,
稱為德摩根律又叫反演律

文字表述

1.集合A與集合B的交集的補集等於集合A的補集與集合B的補集的並集;
2.集合A與集合B的並集的補集等於集合A的補集與集合B的補集的交集。

發展歷程與表達形式

奧古斯都·德·摩根首先發現了在命題邏輯中存在著下面這些關係:
非(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.
在其用於可能性和必然性的真勢模態的套用中,亞里士多德注意到該情況,以及在正規模態邏輯的情況中,這些模態算符對量化的關係可藉助按關係語義設定模型來理解。

相關詞條

相關搜尋

熱門詞條

聯絡我們