德摩根定律

在命题逻辑和逻辑代数中，德摩根定律（英語：De Morgan's laws，又称笛摩根定理、第摩根定律、对偶律等）是关于命题逻辑规律的一对法则^[1]。

19世纪英国数学家奥古斯塔斯·德摩根首先发现了在命题逻辑中存在着下面这些关系：

${\displaystyle \neg (p\land q)\equiv (\neg p)\lor (\neg q)}$

${\displaystyle \neg (p\lor q)\equiv (\neg p)\land (\neg q)}$

即：

非（ ${\displaystyle p}$ 且 ${\displaystyle q}$ ）等价于（ 非 ${\displaystyle p}$ ）或（ 非 ${\displaystyle q}$ ）

非（ ${\displaystyle p}$ 或 ${\displaystyle q}$ ）等价于（ 非 ${\displaystyle p}$ ）且（ 非 ${\displaystyle q}$ ）

德摩根定律在数理逻辑的定理推演中，在计算机的逻辑设计中以及数学的集合运算中都起着重要的作用^[1]。他的发现影响了乔治·布尔从事的逻辑问题代数解法的研究，这巩固了德摩根作为该规律的发现者的地位。亚里士多德亦曾注意到类似的现象、且这也为古希腊与中世纪的逻辑学家熟知（引自Bocheński《形式逻辑历史》）。

形式表示

形式逻辑中此定律表达形式已在上文提及。

在集合论中：

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

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

详细解释

在经典命题逻辑的外延中，此二元性依然有效（即对于任意的逻辑运算符，我们都能找到它的对偶），由于存在于调节否定关系的恒等式中，人们总会引入作为一个算符的德摩根对偶的另一个算符。这导致了基于传统逻辑的逻辑学的一个重要性质，即否定范式的存在性：任何公式等价于另外一个公式，其中否定仅出现在作用于公式中非逻辑的原子时。否定常型的存在推进了许多应用，例如在数位电路设计中该性质用于操纵逻辑閘，以及在形式逻辑中该性质是寻找一个公式的合取范式和析取范式的必要条件；电脑程式設計師们则用它们将一个类似于「如果...那么...否则...」这样的复杂语句转变为其对等形式（例如：if(...){...} else{...}）；它们也同样经常用于初等概率论中的计算。我们将基于基本命题${\displaystyle p}$, ${\displaystyle q}$的任意命题算符${\displaystyle P(p,q,\ldots )}$的对偶定义为：

${\displaystyle \neg {\mbox{P}}^{d}(\neg p,\neg q,...)}$

该概念可以推广到逻辑量词上，例如全称量词和存在量词互为对偶：

${\displaystyle \forall x\,P(x)\equiv \neg \exists x\,\neg P(x)}$

“对所有${\displaystyle x}$，${\displaystyle P(x)}$皆成立”等价于“不存在${\displaystyle x}$，使${\displaystyle P(x)}$不成立”；

${\displaystyle \exists x\,P(x)\equiv \neg \forall x\,\neg P(x)}$

“存在${\displaystyle x}$，使${\displaystyle P(x)}$成立”等价于“并非对所有${\displaystyle x}$，${\displaystyle P(x)}$都不成立”。

为对德摩根定律叙述这些量词的二元性，设置一个在其域${\displaystyle D}$中具有少量元素的模型，例如

${\displaystyle D={a,b,c}}$

则

${\displaystyle \forall x\,P(x)\equiv P(a)\wedge P(b)\wedge P(c)}$

“对所有${\displaystyle x}$，${\displaystyle P(x)}$成立”等价于“${\displaystyle P(a)}$成立”且“${\displaystyle P(b)}$成立”且“${\displaystyle P(c)}$成立”

以及

${\displaystyle \exists x\,P(x)\equiv P(a)\vee P(b)\vee P(c)}$

“存在${\displaystyle x}$，使${\displaystyle P(x)}$成立”等价于“${\displaystyle P(a)}$成立”或“${\displaystyle P(b)}$成立”或“${\displaystyle P(c)}$成立”

但，应用德摩根定律，

${\displaystyle P(a)\wedge P(b)\wedge P(c)\equiv \neg (\neg P(a)\vee \neg P(b)\vee \neg P(c))}$

“‘${\displaystyle P(a)}$成立’且‘${\displaystyle P(b)}$成立’且‘${\displaystyle P(c)}$成立’”等价于“非(‘${\displaystyle P(a)}$不成立’或‘${\displaystyle P(b)}$不成立’或‘${\displaystyle P(c)}$不成立’)”

以及

${\displaystyle P(a)\vee P(b)\vee P(c)\equiv \neg (\neg P(a)\wedge \neg P(b)\wedge \neg P(c))}$

“‘${\displaystyle P(a)}$成立’或‘${\displaystyle P(b)}$成立’或‘${\displaystyle P(c)}$成立’”等价于“非(‘${\displaystyle P(a)}$不成立’且‘${\displaystyle P(b)}$不成立’且‘${\displaystyle P(c)}$不成立’)”

检验模型中量词的二元性。

从而，量词的二元性可进一步延伸到模态逻辑中的方块和菱形算符：

${\displaystyle \Box p\equiv \neg \Diamond \neg p}$

${\displaystyle \Diamond p\equiv \neg \Box \neg p}$

在其用于可能性和必然性的真势模态的应用中，亚里士多德注意到该情况，以及在正规模态逻辑的情况中，这些模态算符对量化的关系可借助按关系语义设置模型来理解。

参见

• 布尔代数主题列表

注释与参考资料

引用

• “应注意到一个析取命题的对立命题是由该析取命题各部分的对立内容构成的一个合取命题” ——奥卡姆的威廉著，《逻辑学论文》