De Morgan's laws

Worked Example

Here is a more concrete example to illustrate how De Morgan's laws operate in practice.

Let's consider the statement: "It is not the case that a number is both even and positive". Using De Morgan's laws, this statement can be rewritten to read: "The number is either not even or it is not positive"

This transformation demonstrates how negation is distributed across a conjunction by negating each component and switching the logical operator. Step-by-step rewrites such as this are especially useful when simplifying logical expressions in proofs and problem solving.

History

The laws are named after Augustus De Morgan (1806–1871), who introduced a formal version of the laws to classical propositional logic. The first explicit statement of De Morgan's laws in his own work can be found in his 1847 book Formal Logic. De Morgan's formulation was influenced by the algebraization of logic undertaken by George Boole, which later cemented De Morgan's claim to the find. Nevertheless, a similar observation was made by Aristotle, and was known to Greek and Medieval logicians. For example, in the 14th century, William of Ockham wrote down the words that would result by reading the laws out. Jean Buridan, in his Summulae de Dialectica, also describes rules of conversion that follow the lines of De Morgan's laws. Still, De Morgan is given credit for stating the laws in the terms of modern formal logic, and incorporating them into 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.

Proof for Boolean algebra

De Morgan's theorem may be applied to the negation of a disjunction or the negation of a conjunction in all or part of a formula.

Negation of a disjunction

In the case of its application to a disjunction, consider the following claim: "it is false that either of A or B is true", which is written as: $${\displaystyle \mathrm{\neg }(A\vee B).}$$ In that it has been established that neither A nor B is true, then it must follow that both A is not true and B is not true, which may be written directly as: $${\displaystyle (\mathrm{\neg }A)\wedge (\mathrm{\neg }B).}$$ If either A or B were true, then the disjunction of A and B would be true, making its negation false. Presented in English, this follows the logic that "since two things are both false, it is also false that either of them is true".

Working in the opposite direction, the second expression asserts that A is false and B is false (or equivalently that "not A" and "not B" are true). Knowing this, a disjunction of A and B must be false also. The negation of said disjunction must thus be true, and the result is identical to the first claim.

Negation of a conjunction

The application of De Morgan's theorem to conjunction is very similar to its application to a disjunction both in form and rationale. Consider the following claim: "it is false that A and B are both true", which is written as: $${\displaystyle \mathrm{\neg }(A\wedge B).}$$ In order for this claim to be true, either or both of A or B must be false, for if they both were true, then the conjunction of A and B would be true, making its negation false. Thus, one (at least) or more of A and B must be false (or equivalently, one or more of "not A" and "not B" must be true). This may be written directly as, $${\displaystyle (\mathrm{\neg }A)\vee (\mathrm{\neg }B).}$$ Presented in a natural language like English, it is expressed as "since it is false that two things are both true, at least one of them must be false".

Working in the opposite direction again, the second expression asserts that at least one of "not A" and "not B" must be true, or equivalently that at least one of A and B must be false. Since at least one of them must be false, then their conjunction would likewise be false. Negating said conjunction thus results in a true expression, and this expression is identical to the first claim.

Proof for set theory

Here we use ${\displaystyle \overline{A}}$ to denote the complement of A, as above in § Set theory and Boolean algebra. The proof that ${\displaystyle \overline{A\cap B}=\overline{A}\cup \overline{B}}$ is completed in 2 steps by proving both ${\displaystyle \overline{A\cap B}\subseteq \overline{A}\cup \overline{B}}$ and ${\displaystyle \overline{A}\cup \overline{B}\subseteq \overline{A\cap B}}$.

Part 1

Let ${\displaystyle x\in \overline{A\cap B}}$. Then, ${\displaystyle x\notin A\cap B}$.

Because ${\displaystyle A\cap B=\{y|y\in A\wedge y\in B\}}$, it must be the case that ${\displaystyle x\notin A}$ or ${\displaystyle x\notin B}$.

If ${\displaystyle x\notin A}$, then ${\displaystyle x\in \overline{A}}$, so ${\displaystyle x\in \overline{A}\cup \overline{B}}$.

Similarly, if ${\displaystyle x\notin B}$, then ${\displaystyle x\in \overline{B}}$, so ${\displaystyle x\in \overline{A}\cup \overline{B}}$.

Thus, ${\displaystyle \mathrm{\forall }x(x\in \overline{A\cap B}⟹x\in \overline{A}\cup \overline{B})}$;

that is, ${\displaystyle \overline{A\cap B}\subseteq \overline{A}\cup \overline{B}}$.

Part 2

To prove the reverse direction, let ${\displaystyle x\in \overline{A}\cup \overline{B}}$, and for contradiction assume ${\displaystyle x\notin \overline{A\cap B}}$.

Under that assumption, it must be the case that ${\displaystyle x\in A\cap B}$,

so it follows that ${\displaystyle x\in A}$ and ${\displaystyle x\in B}$, and thus ${\displaystyle x\notin \overline{A}}$ and ${\displaystyle x\notin \overline{B}}$.

However, that means ${\displaystyle x\notin \overline{A}\cup \overline{B}}$, in contradiction to the hypothesis that ${\displaystyle x\in \overline{A}\cup \overline{B}}$,

therefore, the assumption ${\displaystyle x\notin \overline{A\cap B}}$ must not be the case, meaning that ${\displaystyle x\in \overline{A\cap B}}$.

Hence, ${\displaystyle \mathrm{\forall }x(x\in \overline{A}\cup \overline{B}⟹x\in \overline{A\cap B})}$,

that is, ${\displaystyle \overline{A}\cup \overline{B}\subseteq \overline{A\cap B}}$.

Conclusion

If ${\displaystyle \overline{A}\cup \overline{B}\subseteq \overline{A\cap B}}$ and ${\displaystyle \overline{A\cap B}\subseteq \overline{A}\cup \overline{B}}$, then ${\displaystyle \overline{A\cap B}=\overline{A}\cup \overline{B}}$; this concludes the proof of De Morgan's law.

The other De Morgan's law, ${\displaystyle \overline{A\cup B}=\overline{A}\cap \overline{B}}$, is proven similarly.

Generalising De Morgan duality

In extensions of classical propositional logic, the duality still holds (that is, to any logical operator one can always find its dual), since in the presence of the identities governing negation, one may always introduce an operator that is the De Morgan dual of another. This leads to an important property of logics based on classical logic, namely the existence of negation normal forms: any formula is equivalent to another formula where negations only occur applied to the non-logical atoms of the formula. The existence of negation normal forms drives many applications, for example in digital circuit design, where it is used to manipulate the types of logic gates, and in formal logic, where it is needed to find the conjunctive normal form and disjunctive normal form of a formula. Computer programmers use them to simplify or properly negate complicated logical conditions. They are also often useful in computations in elementary probability theory.

Let one define the dual of any propositional operator P(p, q, ...) depending on elementary propositions p, q, ... to be the operator ${\displaystyle {\text{P}}^d}$ defined by

$${\displaystyle {\text{P}}^d(p,q,...)=\mathrm{\neg }P(\mathrm{\neg }p,\mathrm{\neg }q,\dots ).}$$

Extension to predicate and modal logic

This duality can be generalised to quantifiers, so for example the universal quantifier and existential quantifier are duals:

$${\displaystyle \begin{array}{cc}\mathrm{\forall }xP(x)& \equiv \mathrm{\neg }[\mathrm{\exists }x\mathrm{\neg }P(x)]\\ \mathrm{\exists }xP(x)& \equiv \mathrm{\neg }[\mathrm{\forall }x\mathrm{\neg }P(x)]\end{array}}$$

To relate these quantifier dualities to the De Morgan laws, consider a domain of discourse D (with some small number of entities) to which properties are ascribed universally and existentially, such as

D = {a, b, c}.

Then express universal quantifier equivalently by conjunction of individual statements $${\displaystyle \mathrm{\forall }xP(x)\equiv P(a)\wedge P(b)\wedge P(c)}$$ and existential quantifier by disjunction of individual statements $${\displaystyle \mathrm{\exists }xP(x)\equiv P(a)\vee P(b)\vee P(c).}$$ But, using De Morgan's laws, $${\displaystyle P(a)\wedge P(b)\wedge P(c)\equiv \mathrm{\neg }(\mathrm{\neg }P(a)\vee \mathrm{\neg }P(b)\vee \mathrm{\neg }P(c))}$$ and $${\displaystyle P(a)\vee P(b)\vee P(c)\equiv \mathrm{\neg }(\mathrm{\neg }P(a)\wedge \mathrm{\neg }P(b)\wedge \mathrm{\neg }P(c)),}$$ verifying the quantifier dualities in the model.

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

$${\displaystyle \begin{array}{cc}◻p& \equiv \mathrm{\neg }◊\mathrm{\neg }p\\ ◊p& \equiv \mathrm{\neg }◻\mathrm{\neg }p.\end{array}}$$

In its application to the alethic modalities of possibility and necessity, Aristotle observed this case, and in the case of normal modal logic, the relationship of these modal operators to the quantification can be understood by setting up models using Kripke semantics.

In intuitionistic logic

Three out of the four implications of de Morgan's laws hold in intuitionistic logic. Specifically, we have $${\displaystyle \mathrm{\neg }(P\vee Q)\leftrightarrow ((\mathrm{\neg }P)\wedge (\mathrm{\neg }Q)),}$$ and $${\displaystyle ((\mathrm{\neg }P)\vee (\mathrm{\neg }Q))\to \mathrm{\neg }(P\wedge Q).}$$ The converse of the last implication does not hold in pure intuitionistic logic. That is, the failure of the joint proposition ${\displaystyle P\wedge Q}$ cannot necessarily be resolved to the failure of either of the two conjuncts. For example, from knowing it not to be the case that both Alice and Bob showed up to their date, it does not follow who did not show up. The latter principle is equivalent to the principle of the weak excluded middle ${\displaystyle \mathrm{W}\mathrm{P}\mathrm{E}\mathrm{M}}$, $${\displaystyle (\mathrm{\neg }P)\vee \mathrm{\neg }(\mathrm{\neg }P).}$$ This weak form can be used as a foundation for an intermediate logic. For a refined version of the failing law concerning existential statements, see the lesser limited principle of omniscience ${\displaystyle \mathrm{L}\mathrm{L}\mathrm{P}\mathrm{O}}$, which however is different from ${\displaystyle \mathrm{W}\mathrm{L}\mathrm{P}\mathrm{O}}$.

The validity of the other three De Morgan's laws remains true if negation ${\displaystyle \mathrm{\neg }P}$ is replaced by implication ${\displaystyle P\to C}$ for some arbitrary constant predicate C, meaning that the above laws are still true in minimal logic.

Similarly to the above, the quantifier laws: $${\displaystyle \mathrm{\forall }x\mathrm{\neg }P(x)\leftrightarrow \mathrm{\neg }\mathrm{\exists }xP(x)}$$ and $${\displaystyle \mathrm{\exists }x\mathrm{\neg }P(x)\to \mathrm{\neg }\mathrm{\forall }xP(x).}$$ are tautologies even in minimal logic with negation replaced with implying a fixed ${\displaystyle Q}$, while the converse of the last law does not have to be true in general.

Further, one still has $${\displaystyle \begin{array}{cc}(P\vee Q)& \to \mathrm{\neg }((\mathrm{\neg }P)\wedge (\mathrm{\neg }Q)),\\ (P\wedge Q)& \to \mathrm{\neg }((\mathrm{\neg }P)\vee (\mathrm{\neg }Q)),\\ \mathrm{\forall }xP(x)& \to \mathrm{\neg }\mathrm{\exists }x\mathrm{\neg }P(x),\\ \mathrm{\exists }xP(x)& \to \mathrm{\neg }\mathrm{\forall }x\mathrm{\neg }P(x),\end{array}}$$ but their inversion implies excluded middle, ${\displaystyle \mathrm{P}\mathrm{E}\mathrm{M}}$.

In computer engineering

• De Morgan's laws are widely used in computer engineering and digital logic for the purpose of simplifying circuit designs.
• In modern programming languages, compilers and interpreters use De Morgan's laws to optimize Boolean expressions. Therefore, performance differences between logically equivalent expressions are usually negligible or completely absent.

Expanded Applications

De Morgan's laws are commonly cited in digital circuit design and Boolean algebra, however, they also play an important role in reasoning and computation. De Morgan's laws are utilized in probability theory, allowing one to simplify complements of compound events. Expressions involving "not both" or "not either" can be rewritten in more manageable forms.

In computer science, these laws are frequestly applied when rewriting conditional statements. Negating a compound condition in code often requires transforming an AND condition into an OR condition with negated components, illustrating how these laws improve both readability and correctness when designing algorithms.

De Morgan's laws are also useful in formal proofs. where transforming logical statements into equivalent forms can make arguments easier to construct and verify.