德摩根定律

德摩根定律是命题逻辑和布尔代数中的两个基本等价关系：合取的否定等价于各项否定的析取，而析取的否定等价于各项否定的合取。这两条定律将含有“且”“或”“非”的表达式联系起来，在集合论中也有对应形式。其名称是为了纪念十九世纪数学家奥古斯都·德摩根，他的研究推动了符号逻辑学的发展。(openstax.org)

逻辑表述

对于命题 (P) 和 (Q)，这两条定律为：

[ \neg(P\land Q)\equiv(\neg P\lor\neg Q), ]

[ \neg(P\lor Q)\equiv(\neg P\land\neg Q). ]

这里，(\neg) 表示否定，(\land) 表示合取，(\lor) 表示析取。等价符号表示，无论如何给组成表达式的各个命题赋予真值，两边表达式的真值都相同。因此，这两条定律允许双向替换，而不只是从左向右推导。(cs.cornell.edu)

这里的析取是相容的：只要两个命题中至少一个为真，(P\lor Q) 就为真，包括两者都为真的情况。它不是异或。因此，“并非两者都成立”表示至少有一个命题为假，而“两者都不成立”表示两个命题均为假。例如，“门锁着且窗户关着”的否定是“门没锁或窗户没关”。将原陈述中的“且”改为“或”后，其否定则是“门没锁且窗户没关”。(openstax.org)

仅仅更换联结词，或仅仅否定各个组成部分，都不符合这两条定律。必须去掉外层的否定，同时否定每个组成部分，并将合取与析取互换。(openstax.org)

验证与证明

在经典逻辑中，真值表可以给出直接的数学证明。两个命题共有四种可能的真值赋值：

相应列的真值完全一致，证明了这两个等价关系。若将这两条定律写成双条件命题，它们都是重言式：无论 (P) 和 (Q) 描述什么，它们在所有可能的真值赋值下都为真。(openstax.org)

反复应用这两条定律，可以将其推广到任意有限个命题。因此，“(P_1) 且……且 (P_n)”的否定是“非 (P_1) 或……或非 (P_n)”。对于嵌套表达式，也可以逐个联结词进行变换；表达式的分组结构决定了每一步要否定哪些子表达式。(interactivetextbooks.tudelft.nl)

集合论形式

设 (A) 和 (B) 是固定全集 (U) 的子集，用 (A^c=U\setminus A) 表示 (A) 的补集。这两条定律的集合形式为：

[ (A\cup B)^c=A^c\cap B^c, \qquad (A\cap B)^c=A^c\cup B^c. ]

第一条表示，不属于两个集合的并集，就意味着这两个集合都不属于。第二条表示，不属于两个集合的交集，就意味着至少不属于其中一个集合。全集必须保持不变，因为补集是相对于全集定义的。(interactivetextbooks.tudelft.nl)

考察任意元素 (x\in U)，即可推导出这些恒等式。属于并集对应于析取，属于交集对应于合取，属于补集对应于否定。因此，应用逻辑形式的德摩根定律，就能证明相应集合相等。(interactivetextbooks.tudelft.nl)

量词

在一阶逻辑中，相关的等价关系使全称量化与存在量化互换：

[ \neg\forall x,P(x)\equiv\exists x,\neg P(x), ]

[ \neg\exists x,P(x)\equiv\forall x,\neg P(x). ]

“每个对象都具有性质 (P)”的否定断言存在一个反例，而不是断言每个对象都不具有该性质。“某个对象具有性质 (P)”的否定则断言没有任何对象具有该性质。在这些变换中，量词的论域保持不变。(web.sas.upenn.edu)

例如，“并非每个整数都是偶数”等价于“存在一个不是偶数的整数”。当表达式包含多个量词时，否定逐步向内移动，将每个全称量词换成存在量词，并将每个存在量词换成全称量词，但不改变量词的先后顺序。(inf.ed.ac.uk)

计算领域的应用

在计算机科学中，德摩根定律有助于将公式转换为否定范式，即否定符号只直接出现在原子命题之前的形式。消去其他联结词后，反复应用德摩根定律和双重否定消去，就能将否定向内推进。这是将公式转换为合取范式的一个准备步骤。(comp.nus.edu.sg)

在数字电子技术中，这两条定律给出了逻辑门的等价描述。与非运算等价于先将各输入取反，再进行或运算；或非运算等价于先将各输入取反，再进行与运算。这些等价关系使电路设计人员能够在保持电路所计算的布尔函数不变的前提下，更换逻辑门形式并调整取反的位置。(ocw.mit.edu)

在非经典逻辑中的局限

在直觉主义逻辑中，这两条定律的地位并不相同。等价关系

[ \neg(P\lor Q)\leftrightarrow(\neg P\land\neg Q) ]

仍然成立，蕴涵关系

[ (\neg P\lor\neg Q)\rightarrow\neg(P\land Q) ]

也成立。

然而，(\neg(P\land Q)\rightarrow(\neg P\lor\neg Q)) 一般无法推导出来。从构造性角度看，证明 (P) 和 (Q) 不能同时成立，并不一定能给出证明，指出其中哪一个为假。排中律等经典逻辑原则可以使这一缺失的推导方向成立；通常的二值真值表验证并不能证明它在直觉主义逻辑中有效。(cs.cornell.edu)