De Morgan's laws

De Morgan's laws are normally shown in the compact form above, with the negation of the output on the left and negation of the inputs on the right. A clearer form for substitution can be stated as:

${\displaystyle {\begin{aligned}(P\land Q)&\Longleftrightarrow \neg (\neg P\lor \neg Q),\\(P\lor Q)&\Longleftrightarrow \neg (\neg P\land \neg Q).\end{aligned}}}$

This emphasizes the need to invert both the inputs and the output, as well as change the operator when doing a substitution.

In set theory and Boolean algebra, it is often stated as "union and intersection interchange under complementation",[6] which can be formally expressed as:

${\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}}$

where:

• ${\displaystyle {\overline {A}}}$ is the negation of ${\displaystyle A}$, the overline being written above the terms to be negated,
• ${\displaystyle \cap }$ is the intersection operator (AND),
• ${\displaystyle \cup }$ is the union operator (OR).

The generalized form is

${\displaystyle {\begin{aligned}{\overline {\bigcap _{i\in I}A_{i}}}&\equiv \bigcup _{i\in I}{\overline {A_{i}}},\\{\overline {\bigcup _{i\in I}A_{i}}}&\equiv \bigcap _{i\in I}{\overline {A_{i}}},\end{aligned}}}$

where I is some, possibly countably or uncountably infinite, indexing set.

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

In electrical and computer engineering, De Morgan's laws are commonly written as:

${\displaystyle {\overline {(A\cdot B)}}\equiv ({\overline {A}}+{\overline {B}})}$

and

${\displaystyle {\overline {A+B}}\equiv {\overline {A}}\cdot {\overline {B}},}$

where:

• ${\displaystyle \cdot }$ is the logical AND,
• ${\displaystyle +}$ is the logical OR,
• the overbar is the logical NOT of what is underneath the overbar.

De Morgan's laws commonly apply to text searching using Boolean operators AND, OR, and NOT. Consider a set of documents containing the words "cats" and "dogs". De Morgan's laws hold that these two searches will return the same set of documents:

Search A: NOT (cats OR dogs)

Search B: (NOT cats) AND (NOT dogs)

The corpus of documents containing "cats" or "dogs" can be represented by four documents:

Document 1: Contains only the word "cats".

Document 2: Contains only "dogs".

Document 3: Contains both "cats" and "dogs".

Document 4: Contains neither "cats" nor "dogs".

To evaluate Search A, clearly the search "(cats OR dogs)" will hit on Documents 1, 2, and 3. So the negation of that search (which is Search A) will hit everything else, which is Document 4.

Evaluating Search B, the search "(NOT cats)" will hit on documents that do not contain "cats", which is Documents 2 and 4. Similarly the search "(NOT dogs)" will hit on Documents 1 and 4. Applying the AND operator to these two searches (which is Search B) will hit on the documents that are common to these two searches, which is Document 4.

A similar evaluation can be applied to show that the following two searches will both return Documents 1, 2, and 4:

Search C: NOT (cats AND dogs),

Search D: (NOT cats) OR (NOT dogs).

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 \neg (A\lor 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 (\neg A)\wedge (\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.

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 \neg (A\land 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 (\neg A)\lor (\neg B).}$

Presented in English, this follows the logic that "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.

Let ${\displaystyle x\in (A\cap B)^{\complement }}$. Then, ${\displaystyle x\not \in A\cap B}$.

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

If ${\displaystyle x\not \in A}$, then ${\displaystyle x\in A^{\complement }}$, so ${\displaystyle x\in A^{\complement }\cup B^{\complement }}$.

Similarly, if ${\displaystyle x\not \in B}$, then ${\displaystyle x\in B^{\complement }}$, so ${\displaystyle x\in A^{\complement }\cup B^{\complement }}$.

Thus, ${\displaystyle \forall x{\Big (}x\in (A\cap B)^{\complement }\implies x\in A^{\complement }\cup B^{\complement }{\Big )}}$;

that is, ${\displaystyle (A\cap B)^{\complement }\subseteq A^{\complement }\cup B^{\complement }}$.

To prove the reverse direction, let ${\displaystyle x\in A^{\complement }\cup B^{\complement }}$, and for contradiction assume ${\displaystyle x\not \in (A\cap B)^{\complement }}$.

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\not \in A^{\complement }}$ and ${\displaystyle x\not \in B^{\complement }}$.

However, that means ${\displaystyle x\not \in A^{\complement }\cup B^{\complement }}$, in contradiction to the hypothesis that ${\displaystyle x\in A^{\complement }\cup B^{\complement }}$,

therefore, the assumption ${\displaystyle x\not \in (A\cap B)^{\complement }}$ must not be the case, meaning that ${\displaystyle x\in (A\cap B)^{\complement }}$.

Hence, ${\displaystyle \forall x{\Big (}x\in A^{\complement }\cup B^{\complement }\implies x\in (A\cap B)^{\complement }{\Big )}}$,

that is, ${\displaystyle A^{\complement }\cup B^{\complement }\subseteq (A\cap B)^{\complement }}$.

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

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