奧古斯都·德·摩根首先發現了在命題邏輯中存在著下面這些關係:
非(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.
在其用於可能性和必然性的真勢模態的套用中,亞里士多德注意到該情況,以及在正規模態邏輯的情況中,這些模態算符對量化的關係可藉助按關係語義設定模型來理解。
相關詞條
-
德·摩根定律
在命題邏輯和邏輯代數中,德·摩根定律(或稱德·摩根定理)是關於命題邏輯規律的一對法則。 奧古斯都·德·摩根首先發現了在命題邏輯中存在著下面這些關係: 非...
定理定義 定理推廣 推導過程 實驗驗證 發展簡史 -
德摩根
德·摩根1806年6月27日出生於英國,於1823至1827年間入讀劍橋大學三一學院,1828年,他的老師如皮科克等人,推薦他任倫敦大學學院數學教授一職...
生平 人物貢獻 與中國的聯繫 軼事 -
德·摩根
德·摩根1806年6月27日出生於英國,於1823至1827年間入讀劍橋大學三一學院,1828年,他的老師如皮科克等人,推薦他任倫敦大學學院數學教授一職...
生平 人物貢獻 與中國的聯繫 軼事 -
德摩根律
德摩根律是數學中的邏輯學法則,用文字表述就是:C並上A與B的交集等於C與A的並集並上C與B的並集;C並上A與B的並集等於C與A的並集交上C與B的並集。
文字表述 發展歷程與表達形式 -
德摩根定理
德摩根定理是講解關於交集,並集和補集的關係:也叫做對偶原則。
德摩根定理的表達形式 檢驗模型中量詞的二元性 德摩根定理的證明 -
奧古斯都·德·摩根
奧古斯都·德·摩根明確陳述了德·摩根定律,將數學歸納法的概念嚴格化。
生平 德·摩根環形山 -
摩根定律
摩根定律,由奧古斯塔斯·德·摩根提出。
Morgan’s Law 一.摩根定律 二.摩根定律的套用 三.套用舉例 -
德尼摩定律
英國管理學家德尼摩提出凡事都應有一個可安置的所在,一切都應在它該在的地方。知人善任才能成就事業。這被稱為德尼摩定律。
簡介 定律釋義 古為今用 經典案例 操作實務