= De Morgan's laws
{c}
{title2=$\neg(P\wedge Q)\equiv\neg P\vee\neg Q$}
{wiki}
= De Morgan laws
{c}
{synonym}
<De Morgan's laws> exchange <logical conjunction> and <logical disjunction> when a <logical negation> moves across them:
$$
\neg(P\wedge Q)\equiv(\neg P)\vee(\neg Q),
\qquad
\neg(P\vee Q)\equiv(\neg P)\wedge(\neg Q).
$$
Here $\equiv$ denotes <logical equivalence>: the two <propositional formulas> agree under every <Boolean valuation>.<Discrete Mathematics: An Open Introduction (3rd edition) by Oscar Levin/3.1 Propositional Logic>[Discrete Mathematics: An Open Introduction (3rd edition) by Oscar Levin; Discrete Mathematics: An Open Introduction, 3rd edition by Oscar Levin, §3.1, Logical Equivalence: definition, Example 3.1.3 and De Morgan's Laws box]{ref}
A complete verification uses the four rows of a <truth table>. In input order $(0,0),(0,1),(1,0),(1,1)$, both sides of the first <logical equivalence> have output sequence $(1,1,1,0)$; both sides of the second have $(1,0,0,0)$. A proof in words is equally short: failure of “both” means at least one failure, whereas failure of “at least one” means both fail. The differing middle rows explain why simply pushing <logical negation> inward without changing AND to OR is wrong.
For the <events> in <Boolean operations on events>, the corresponding <set> identities are
$$
U\setminus(A\cap B)=(U\setminus A)\cup(U\setminus B)=\{1,2,3,5\},
$$
$$
U\setminus(A\cup B)=(U\setminus A)\cap(U\setminus B)=\{1,3\}.
$$
One can prove these identities by checking an arbitrary <set element> $u\in U$: its two membership <truth values> obey <De Morgan's laws>. The same reasoning works for any two <subsets> of a common <universal set>.
\Image[/de-morgan-event-regions.png]
{title=<De Morgan's laws> shade the same <set> whether a compound <event> is complemented first or its component <events> are complemented first}
For a nested program test, let $R$ mean “backup recent”, $V$ mean “backup verified”, and $O$ mean “manual override authorized”. Rejecting when neither an acceptable backup nor an override is present gives
$$
\neg\bigl((R\wedge V)\vee O\bigr)
\equiv\bigl((\neg R)\vee(\neg V)\bigr)\wedge\neg O.
$$
The transformed condition reads “backup stale or unverified, and no override”. Apply the second of <De Morgan's laws> at the outside, then the first at the inner <logical conjunction>. For $(R,V,O)=(1,0,0)$ it rejects; changing only $O$ to one makes it accept. With Boolean operands in <Python>, `not ((recent and verified) or override)` and `((not recent) or (not verified)) and (not override)` have the same result and inspect the operands in the same order, with the same skipped operands.
Back to article page
