德摩根定律

在命題邏輯和邏輯代數中，德摩根定律（英語：De Morgan's laws，又稱笛摩根定理、第摩根定律、對偶律等）是關於命題邏輯規律的一對法則。

19世紀英國數學家奧古斯塔斯·德摩根首先發現了在命題邏輯中存在着下面這些關係：

$\neg (p\land q)\equiv (\neg p)\lor (\neg q)$

$\neg (p\lor q)\equiv (\neg p)\land (\neg q)$

即：

非（ $p$ 且 $q$ ）等價於（ 非 $p$ ）或（ 非 $q$ ）

非（ $p$ 或 $q$ ）等價於（ 非 $p$ ）且（ 非 $q$ ）

德摩根定律在數理邏輯的定理推演中，在電腦的邏輯設計中以及數學的集合運算中都起着重要的作用。他的發現影響了佐治·布爾從事的邏輯問題代數解法的研究，這鞏固了德摩根作為該規律的發現者的地位，亞里士多德亦曾注意到類似的現象、且這也為古希臘與中世紀的邏輯學家熟知（引自Bocheński《形式邏輯歷史》）。

形式表示

形式邏輯中此定律表達形式已在上文提及。

在集合論中：

$\left(A\cap B\right)^{C}=A^{C}\cup B^{C}$

$\left(A\cup B\right)^{C}=A^{C}\cap B^{C}$

詳細解釋

在經典命題邏輯的外延中，此二元性依然有效（即對於任意的邏輯運算子，我們都能找到它的對偶），由於存在於調節否定關係的恆等式中，人們總會引入作為一個算符的德摩根對偶的另一個算符。這導致了基於傳統邏輯的邏輯學的一個重要性質，即否定範式的存在性：任何公式等價於另外一個公式，其中否定僅出現在作用於公式中非邏輯的原子時。否定常型的存在推進了許多應用，例如在數碼電路設計中該性質用於操縱邏輯閘，以及在形式邏輯中該性質是尋找一個公式的合取範式和析取範式的必要條件；電腦程式設計師們則用它們將一個類似於「如果...那麼...否則...」這樣的複雜陳述式轉變為其對等形式（例如：if(...){...} else{...}）；它們也同樣經常用於初等概率論中的計算。我們將基於基本命題$p$, $q$的任意命題算符$P(p,q,\ldots )$的對偶定義為：

$\neg {\mbox{P}}^{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$

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

參見

• 布林代數主題列表

註釋與參考資料

參照

• 「應注意到一個析取命題的對立命題是由該析取命題各部分的對立內容構成的一個合取命題」 ——奧卡姆的威廉著，《邏輯學論文》

外部連結

• 數學世界：德摩根定律 （頁面存檔備份，存於互聯網檔案館）
• 國家教育研究院 樂詞網 （頁面存檔備份，存於互聯網檔案館）