德摩根定律是什麼

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

奧古斯都·德·摩根首先發現了在命題邏輯中存在的關係：

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

非(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）不成立’）”

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

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

,

.