De Morgan's laws

The De Morgan's laws are named after Augustus De Morgan (1806–1871) who introduced a formal version of the laws to classical propositional logic. De Morgan's formulation was influenced by algebraization of logic undertaken by George Boole, which later cemented De Morgan's claim to the find. Although a similar observation was made by Aristotle and was known to Greek and Medieval logicians (in the 14th century William of Ockham wrote down the words that would result by reading the laws out,) De Morgan is given credit for stating the laws formally and incorporating them in to the language of logic. De Morgan's Laws can be proved easily, and may even seem trivial. Nonetheless, these laws are helpful in making valid inferences in proofs and deductive arguments.

Set theoretic form

"The complement of an intersection is the union of the complements."

and

"The complement of a union is the intersection of the complements."

In set theory it is often stated as "Union and intersection interchange under complementation."

The set theoretic binary form of de Morgan's law is

${\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}\,$

${\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}\,$

with generalization

${\overline {\bigcap _{i\in I}A_{i}}}=\bigcup _{i\in I}{\overline {A_{i}}}\,$

${\overline {\bigcup _{i\in I}A_{i}}}=\bigcap _{i\in I}{\overline {A_{i}}}\,$

where

• A is the complement (relative to a given universal set) of A (the overline being written above the terms to be complemented)
• ∩ is the intersection operator (AND)
• ∪ is the union operator (OR)
• = means set equality

and where $\scriptstyle I\,$ is some, possibly uncountable, indexing set.

In set notation, De Morgan's law can be remembered using the mnemonic "break the line, change the sign."

Logic forms

"The negation of a conjunction is the disjunction of the negations."

and

"The negation of a disjunction is the conjunction of the negations."

Boolean algebra form

The Boolean algebra binary form of de Morgan's law is

${\rm {NOT}}~(A{\rm {~AND~}}B)=({\rm {NOT}}~A){\rm {~OR~}}({\rm {NOT}}~B)\,$

${\rm {NOT}}~(A{\rm {~OR~}}B)=({\rm {NOT}}~A){\rm {~AND~}}({\rm {NOT}}~B)\,$

with generalization

${\rm {NOT}}~{\rm {AND}}(A_{1},\ldots ,A_{n})={\rm {OR}}({\rm {NOT}}~A_{1},\ldots ,{\rm {NOT}}~A_{n})\,$

${\rm {NOT}}~{\rm {OR}}(A_{1},\ldots ,A_{n})={\rm {AND}}({\rm {NOT}}~A_{1},\ldots ,{\rm {NOT}}~A_{n})\,$

where

• NOT is the Boolean negation operator
• AND is the Boolean conjunction operator
• OR is the Boolean disjunction operator
• = means Boolean equality

Boolean algebra compact form

The Boolean algebra binary compact form of de Morgan's law is

${\overline {A\cdot B}}={\overline {A}}+{\overline {B}}\,$

${\overline {A+B}}={\overline {A}}\cdot {\overline {B}}\,$

with generalization

${\overline {\prod _{i\in I}A_{i}}}=\sum _{i\in I}{\overline {A_{i}}}\,$

${\overline {\sum _{i\in I}A_{i}}}=\prod _{i\in I}{\overline {A_{i}}}\,$

where

• A is the Boolean negation operator (compact notation)
• $\scriptstyle \prod \,$ is the Boolean conjunction operator (compact notation)
• $\scriptstyle \sum \,$ is the Boolean disjunction operator (compact notation)
• = means Boolean equality

Propositional logic form

The propositional logic binary form of de Morgan's law is

$\neg (p\land q)\iff (\neg p)\lor (\neg q)\,$

$\neg (p\lor q)\iff (\neg p)\land (\neg q)\,$

where

• ¬ is the logical negation operator (NOT)
• $\land$ is the conjunction operator (AND)
• $\lor$ is the disjunction operator (OR)
• ⇔ means logical equivalence (if and only if)

De Morgan dual operators

The De Morgan dual of any propositional operator $\scriptstyle {\rm {P}}(p,\,q,\,\ldots )\,$ depending on elementary propositions $\scriptstyle p,\,q,\,\ldots \,$ is the operator $\scriptstyle {\rm {Q}}\,\equiv \,{\rm {P}}^{d}\,$ defined as

${\mbox{Q}}(p,q,...)\equiv {\mbox{P}}^{d}(p,q,...)\equiv \neg {\mbox{P}}(\neg p,\neg q,\dots )\,$

then

$\neg {\mbox{P}}(p,q,...)\iff {\mbox{Q}}(\neg p,\neg q,\dots )\,$

$\neg {\mbox{Q}}(p,q,...)\iff {\mbox{P}}(\neg p,\neg q,\dots )\,$

First-order logic form

This idea can be generalized to logical quantifiers, so for example the universal quantifier and existential quantifier are duals.

The first-order logic binary form of de Morgan's law is

$\neg \forall x\,P(x)\equiv \exists x\,\neg P(x)\,$

$\neg \exists x\,P(x)\equiv \forall x\,\neg P(x)\,$

where

• ¬ is the logical negation operator (NOT)
• $\scriptstyle \forall \,$ is the universal quantifier
• $\scriptstyle \exists \,$ is the existential quantifier
• $\scriptstyle \equiv \,$ means logical equivalence (if and only if)

Modal logic generalization

The quantifier dualities can be extended further to modal logic, relating the box ("necessarily") and diamond ("possibly") operators

$\neg \Box p\equiv \Diamond \neg p\,$

$\neg \Diamond p\equiv \Box \neg p\,$

This may be considered to be a formal expression of the observation that was made by Aristotle and was known to Greek and Medieval logicians.

Arithmetic form

"The negation of a minimum is the maximum of the negations."

and

"The negation of a maximum is the minimum of the negations."

The arithmetic binary form of de Morgan's law is

$-{\rm {MIN}}(x,y)={\rm {MAX}}(-x,-y)\,$

$-{\rm {MAX}}(x,y)={\rm {MIN}}(-x,-y)\,$

with generalization

$-{\rm {MIN}}(x_{1},\ldots ,x_{n})={\rm {MAX}}(-x_{1},\ldots ,-x_{n})\,$

$-{\rm {MAX}}(x_{1},\ldots ,x_{n})={\rm {MIN}}(-x_{1},\ldots ,-x_{n})\,$

where

− is the arithmetic negation operator

MIN is the minimum function (Cf. {{min}} and {{MIN}} mathematical function templates)

MAX is the maximum function (Cf. {{max}} and {{MAX}} mathematical function templates)

= means equal

See also

• Negation normal form
• Conjunctive normal form
• Disjunctive normal form