De Morgan's Laws

De Morgan's laws are a pair of transformation rules used to simplify expressions in both propositional logic and set theory. These laws describe how negation (in logic) or the complement (in set theory) interacts with the fundamental operators: conjunction and disjunction, or intersection and union.

In propositional logic, these rules allow us to distribute a negation across parentheses, turning the negation of a conjunction into a disjunction of negations, and vice versa. In set theory, they perform the exact same structural conversion: the complement of a union becomes the intersection of the complements, while the complement of an intersection becomes the union of the complements.

The laws are named after the 19th-century British mathematician and logician Augustus De Morgan (1806–1871), who introduced them formally, although informal versions of these principles date back to ancient and medieval logic.

De Morgan's Laws in Propositional Logic

In propositional logic, De Morgan's laws allow us to rewrite the negation of a compound statement, which is essential when simplifying logical expressions.

Formulas and Logical Meaning

The two laws are formally stated as follows:

1) The negation of a conjunction is logically equivalent to the disjunction of the negations:

¬(p ∧ q) ≡ ¬p ∨ ¬q

2) The negation of a disjunction is logically equivalent to the conjunction of the negations:

¬(p ∨ q) ≡ ¬p ∧ ¬q

The symbol "≡" (or "⇔") indicates that the statements on both sides are logically equivalent, meaning they share identical truth values under all truth assignments.

The first law, ¬(p ∧ q) ≡ ¬p ∨ ¬q, states that denying two things happen at the same time is equivalent to asserting that at least one of them does not happen.

Consider the statement: "Today is Monday and it is raining." If someone claims this statement is false, they are not necessarily saying "Today is not Monday and it is not raining," which would require both conditions to fail. Instead, they are stating that both conditions do not occur together. In plain English: "Today is not Monday or it is not raining." It could be another day, it might not be raining, or neither condition holds. The only scenario ruled out is the exact combination of a rainy Monday.

Similarly, the second law, ¬(p ∨ q) ≡ ¬p ∧ ¬q, explains how to negate an alternative. Denying that either event occurs is equivalent to stating that neither event occurs.

Consider the statement: "I will go to the movies or to the theater." If we deny this entire claim by saying "It is not true that I will go to the movies or to the theater," we are not merely choosing one venue over the other; we are stating that we will visit neither. Thus, the statement becomes: "I will not go to the movies and I will not go to the theater."

Examples

Example 1

Let us define two simple propositions:

p: "The coffee is hot."

q: "The sugar is dissolved."

The conjunction "The coffee is hot and the sugar is dissolved" is represented by p ∧ q. Negating this proposition gives ¬(p ∧ q). Applying the first law of De Morgan, this negation transforms into ¬p ∨ ¬q: "The coffee is not hot or the sugar is not dissolved."

Example 2

p: "The traffic light is green."

q: "The car moves forward."

The disjunction "The traffic light is green or the car moves forward" corresponds to p ∨ q. Its negation, ¬(p ∨ q), becomes ¬p ∧ ¬q using the second law: "The traffic light is not green and the car does not move forward." If neither condition is allowed to be true, both must be false.

Example 3

p: "The team wins the game."

q: "The players celebrate."

The conjunction p ∧ q reads "The team wins the game and the players celebrate." Its negation, ¬(p ∧ q), is equivalent via De Morgan's first law to ¬p ∨ ¬q: "The team does not win the game or the players do not celebrate."

For the original conjunction to fail, both events do not need to fail simultaneously; it suffices if the team loses, or if they win but do not celebrate.

Example 4

p: "The door is open."

q: "The light is on."

The disjunction p ∨ q is "The door is open or the light is on." Its negation, according to the second law, is ¬p ∧ ¬q: "The door is not open and the light is not on." Ruling out an alternative means eliminating both options, which describes a room that is closed and dark.

Example 5

Consider the mathematical statements:

p: "8 is an even number."

q: "8 is a prime number."

The conjunction p ∧ q asserts: "8 is even and prime." Negating this statement, ¬(p ∧ q), yields ¬p ∨ ¬q by the first law: "8 is not even or 8 is not prime." Because 8 is even but not prime, the resulting disjunction is true because its second component ("8 is not prime") holds true.

Example 6

p: "The number -5 is positive."

q: "The number -5 is composite."

The disjunction p ∨ q states: "-5 is positive or -5 is composite." Its negation, ¬(p ∨ q), becomes ¬p ∧ ¬q by the second law: "-5 is not positive and -5 is not composite."

Because -5 is neither positive nor a composite number (composite numbers are defined strictly for positive integers greater than 1), both negative conditions are met, making the negation true.

Example 7: Simplifying Compound Propositions

We can use De Morgan's laws alongside standard equivalence rules to simplify complex logical formulas.

Let us simplify the compound expression ¬[ ¬(¬p ∨ q) ∨ ¬(p ∧ ¬q) ] step by step:

1. ¬[ ¬(¬p ∨ q) ∨ ¬(p ∧ ¬q) ] (Original expression).
2. ¬[ (¬¬p ∧ ¬q) ∨ (¬p ∨ ¬¬q) ] (Apply De Morgan's second law to ¬(¬p ∨ q) and the first law to ¬(p ∧ ¬q)).
3. ¬[ (p ∧ ¬q) ∨ (¬p ∨ q) ] (Simplify double negations: ¬¬p ≡ p and ¬¬q ≡ q).
4. ¬(p ∧ ¬q) ∧ ¬(¬p ∨ q) (Apply De Morgan's second law to the outermost negation: ¬[A ∨ B] ≡ ¬A ∧ ¬B).
5. (¬p ∨ ¬¬q) ∧ (¬¬p ∧ ¬q) (Apply De Morgan's first law to ¬(p ∧ ¬q) and the second law to ¬(¬p ∨ q)).
6. (¬p ∨ q) ∧ (p ∧ ¬q) (Eliminate double negations once more: ¬¬q ≡ q and ¬¬p ≡ p).

The simplified equivalent of the original expression is (¬p ∨ q) ∧ (p ∧ ¬q).

A practical rule of thumb: Whenever a negation sits outside parentheses enclosing an expression, distribute the negation to each term inside, while simultaneously flipping the main connective to its dual (change ∨ to ∧, and change ∧ to ∨).

De Morgan's Laws in Set Theory

In set theory, the fundamental propositional connectives correspond directly to set operations: disjunction (∨) corresponds to the union (∪), conjunction (∧) corresponds to the intersection (∩), and negation (¬) corresponds to the complement of a set, typically written as A' (or Aᶜ / Ā).

This correspondence translates De Morgan's laws directly into the algebra of sets, where they are used to transform and simplify expressions involving complements, unions, and intersections.

Formulas

The two laws for sets are formulated as follows:

1) The complement of the union of two sets equals the intersection of their complements:

(A ∪ B)' = A' ∩ B'

2) The complement of the intersection of two sets equals the union of their complements:

(A ∩ B)' = A' ∪ B'

Intuitively, the first law states that any element outside the union of A and B is not in A and not in B. The second law states that any element outside the intersection of A and B must fail to belong to at least one of the sets.

Venn Diagrams

De Morgan's laws can be visualized using Venn diagrams, where the shaded regions represent the resulting sets. Below are the visual representations for both laws.

Examples

Example 1

Suppose a college department defines L as the set of students enrolled in Logic, and A as the set of students enrolled in Algebra. The union L ∪ A represents all students enrolled in at least one of the two courses.

The group of students who are not enrolled in either course corresponds to the complement of the union: (L ∪ A)'. By De Morgan's first law, this group is equal to the intersection of the individual complements: L' ∩ A'. These are students who are not taking Logic and are not taking Algebra.

Example 2

Now consider the intersection L ∩ A, which represents the students enrolled in both Logic and Algebra simultaneously. Its complement, (L ∩ A)', consists of all students who are not taking both classes together.

Applying the second law, (L ∩ A)' = L' ∪ A'. A student belongs to this set if they are not in Logic, or not in Algebra, or in neither course. Missing either course is enough to place a student in this complement.

Example 3

In a library, let R be the set of romance novels and M be the set of mystery novels. A librarian needs an inventory of all books that are neither romance nor mystery. This list is described by (R ∪ M)'. Applying the law, this equals R' ∩ M': books that are not romance titles and are simultaneously not mystery titles.

Example 4

In an athletic club, let S represent members who play soccer and T represent members who play tennis. The members who do not play both sports are given by (S ∩ T)'. By De Morgan's second law, this set equals S' ∪ T'. An athlete belongs to this group if they do not play soccer, or do not play tennis, or participate in neither.

Example 5

Consider the subsets A = {1, 2, 3, 4, 5} and B = {4, 5, 6, 7, 8} within the universal set U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

The union is A ∪ B = {1, 2, 3, 4, 5, 6, 7, 8}. Its complement, (A ∪ B)', contains elements of U not found in that union: (A ∪ B)' = {9, 10}.

Now, let us verify De Morgan's first law by calculating A' ∩ B':

A' = {6, 7, 8, 9, 10} (elements in U not in A).

B' = {1, 2, 3, 9, 10} (elements in U not in B).

The intersection of these two complements is A' ∩ B' = {9, 10}. Both expressions produce the identical set, confirming the first law.

Example 6

Let C = {a, b, c, d, e} and D = {d, e, f, g, h}, with the universal set U defined as the first ten letters of the English alphabet:

U = {a, b, c, d, e, f, g, h, i, j}

The intersection is C ∩ D = {d, e}. Its complement, (C ∩ D)', includes all elements in U except "d" and "e": (C ∩ D)' = {a, b, c, f, g, h, i, j}.

We verify De Morgan's second law by computing C' ∪ D':

C' = {f, g, h, i, j}

D' = {a, b, c, i, j}

Taking their union yields C' ∪ D' = {a, b, c, f, g, h, i, j}. Both sets match, proving that an element outside the intersection must be missing from C, from D, or from both.

De Morgan's Laws in Boolean Algebra & Logic Gates

In computer science and digital electronics, De Morgan's laws are central to Boolean algebra. Before examining the rules in this context, notice how the notation shifts compared to propositional logic and set theory:

• The logical AND operation is written as multiplication or juxtaposition: \( A \cdot B \) or \( AB \).
• The logical OR operation is written as addition: \( A + B \).
• The NOT operation (inversion or complement) is denoted by an overbar: \( \overline{A} \).

Boolean Formulas

Using standard Boolean notation, De Morgan's laws are written as follows:

1) \(\overline{A \cdot B} = \overline{A} + \overline{B}\)

2) \(\overline{A + B} = \overline{A} \cdot \overline{B}\)

The first equation states that the complement of a product (a NAND operation) is equal to the sum of the complements (an OR gate with inverted inputs). The second equation states that the complement of a sum (a NOR operation) is equal to the product of the complements (an AND gate with inverted inputs).

Application to Logic Gates

These equivalences provide electrical engineers and circuit designers with practical circuit optimization tools:

• NAND Gate Equivalence: A NAND gate (\(\overline{A \cdot B}\)) is functionally equivalent to an OR gate with active-low (inverted) inputs (\(\overline{A} + \overline{B}\)), often referred to as a Negative-OR gate.
• NOR Gate Equivalence: A NOR gate (\(\overline{A + B}\)) is functionally equivalent to an AND gate with active-low (inverted) inputs (\(\overline{A} \cdot \overline{B}\)), often referred to as a Negative-AND gate.

This property allows entire digital circuits to be built using only universal gates (such as NAND or NOR gates), minimizing silicon area and manufacturing cost in integrated circuits.

Comparison Across Logic, Sets, and Boolean Algebra

The following table summarizes the structural isomorphism between all three systems:

Domain / Operation	Propositional Logic	Set Theory	Boolean Algebra
Conjunction / AND	∧	∩	·
Disjunction / OR	∨	∪	+
Negation / Complement	¬p	A' (or Aᶜ)	\(\overline{A}\)
First Law	¬(p ∧ q) ≡ ¬p ∨ ¬q	(A ∩ B)' = A' ∪ B'	\(\overline{A \cdot B} = \overline{A} + \overline{B}\)
Second Law	¬(p ∨ q) ≡ ¬p ∧ ¬q	(A ∪ B)' = A' ∩ B'	\(\overline{A + B} = \overline{A} \cdot \overline{B}\)

Proofs of De Morgan's Laws

To demonstrate the mathematical validity of De Morgan's laws, we can use truth tables for propositional logic and the element method (proof by double inclusion) for set theory.

Proof Using Truth Tables (Propositional Logic)

The most straightforward method to prove logical equivalence between two compound statements is to construct their truth tables and confirm that their final truth values match for every possible case.

Here is the truth table for the first law: ¬(p ∧ q) ≡ ¬p ∨ ¬q:

p	q	¬p	¬q	p ∧ q	¬(p ∧ q)	¬p ∨ ¬q
T	T	F	F	T	F	F
T	F	F	T	F	T	T
F	T	T	F	F	T	T
F	F	T	T	F	T	T

The columns for ¬(p ∧ q) and ¬p ∨ ¬q are identical across all rows. Regardless of the individual truth values assigned to p and q, both expressions evaluate to the same result.

Next, we construct the truth table for the second law: ¬(p ∨ q) ≡ ¬p ∧ ¬q:

p	q	¬p	¬q	p ∨ q	¬(p ∨ q)	¬p ∧ ¬q
T	T	F	F	T	F	F
T	F	F	T	T	F	F
F	T	T	F	T	F	F
F	F	T	T	F	T	T

Again, the final two columns are identical, which proves the second law.

Proof by Double Inclusion (Set Theory)

We can prove De Morgan's laws for sets by applying the definition of set membership and properties of logical connectives. We establish set equality by showing that each set is a subset of the other (double inclusion).

1) Proof of the first law: (A ∪ B)' = A' ∩ B'

We will demonstrate that (A ∪ B)' ⊆ A' ∩ B' and that A' ∩ B' ⊆ (A ∪ B)'.

Part 1: Show (A ∪ B)' ⊆ A' ∩ B'

Let x be an arbitrary element.

x ∈ (A ∪ B)' (Hypothesis)

⇒ x ∉ (A ∪ B) (By the definition of complement)

⇒ ¬(x ∈ A ∨ x ∈ B) (By the definition of union)

⇒ ¬(x ∈ A) ∧ ¬(x ∈ B) (By De Morgan's law of logic)

⇒ x ∉ A ∧ x ∉ B (By the definition of non-membership)

⇒ x ∈ A' ∧ x ∈ B' (By the definition of complement)

⇒ x ∈ (A' ∩ B') (By the definition of intersection)

Because every x ∈ (A ∪ B)' is also in A' ∩ B', we have proven that (A ∪ B)' ⊆ A' ∩ B'.

Part 2: Show A' ∩ B' ⊆ (A ∪ B)'

Let x be an arbitrary element.

x ∈ (A' ∩ B') (Hypothesis)

⇒ x ∈ A' ∧ x ∈ B' (By the definition of intersection)

⇒ x ∉ A ∧ x ∉ B (By the definition of complement)

⇒ ¬(x ∈ A) ∧ ¬(x ∈ B) (By the definition of non-membership)

⇒ ¬(x ∈ A ∨ x ∈ B) (By De Morgan's law of logic)

⇒ x ∉ (A ∪ B) (By the definition of union)

⇒ x ∈ (A ∪ B)' (By the definition of complement)

Thus, A' ∩ B' ⊆ (A ∪ B)'.

Since (A ∪ B)' ⊆ A' ∩ B' and A' ∩ B' ⊆ (A ∪ B)', we conclude that (A ∪ B)' = A' ∩ B'.

2) Proof of the second law: (A ∩ B)' = A' ∪ B'

We proceed in the same manner by showing bidirectional subset inclusion.

Part 1: Show (A ∩ B)' ⊆ A' ∪ B'

Let x be an arbitrary element.

x ∈ (A ∩ B)' (Hypothesis)

⇒ x ∉ (A ∩ B) (By the definition of complement)

⇒ ¬(x ∈ A ∧ x ∈ B) (By the definition of intersection)

⇒ ¬(x ∈ A) ∨ ¬(x ∈ B) (By De Morgan's law of logic)

⇒ x ∉ A ∨ x ∉ B (By the definition of non-membership)

⇒ x ∈ A' ∨ x ∈ B' (By the definition of complement)

⇒ x ∈ (A' ∪ B') (By the definition of union)

Therefore, (A ∩ B)' ⊆ A' ∪ B'.

Part 2: Show A' ∪ B' ⊆ (A ∩ B)'

Let x be an arbitrary element.

x ∈ (A' ∪ B') (Hypothesis)

⇒ x ∈ A' ∨ x ∈ B' (By the definition of union)

⇒ x ∉ A ∨ x ∉ B (By the definition of complement)

⇒ ¬(x ∈ A) ∨ ¬(x ∈ B) (By the definition of non-membership)

⇒ ¬(x ∈ A ∧ x ∈ B) (By De Morgan's law of logic)

⇒ x ∉ (A ∩ B) (By the definition of intersection)

⇒ x ∈ (A ∩ B)' (By the definition of complement)

Therefore, A' ∪ B' ⊆ (A ∩ B)'.

Since both inclusions hold, we conclude that (A ∩ B)' = A' ∪ B'.