De Morgan’s Laws

De Morgan’s laws are fundamental principles in set theory and boolean algebra. They are attributed to the British mathematician and logician Augustus De Morgan. 

In set theory, the laws establish the relations between union, intersection, and complements of sets, while in Boolean algebra, they relate the operations of conjunction (AND, denoted by ∧), disjunction (OR, denoted by ∨), and negation or complement (NOT, denoted by ¬).

In Set Theory

First Law

The first De Morgan’s law (or De Morgan’s law of union) states that the complement of the union of two sets is the intersection of the complements of each set.

Mathematically, if A and B are two sets, then

(A ∪ B)’ = A’ ∩ B’

Example

If A = {a, b, c, d}, B = {b, c, d, e}, and U = {a, b, c, d, e, f, g}, then we have

(A ∪ B) = {a, b, c, d} ∪ {b, c, d, e} = {a, b, c, d, e} 

A’ = U – A = {a, b, c, d, e, f, g} – {a, b, c, d} = {e, f, g}

B’ = U – B = {a, b, c, d, e, f, g} – {b, c, d, e} = {a, f, g}

Now, (A ∪ B)’ = U – (A ∪ B) = {a, b, c, d, e, f, g} – {a, b, c, d, e} = {f, g}

A’ ∩ B’ = {e, f, g} ∩ {a, f, g} = {f, g}

Thus, (A ∪ B)’ = A’ ∩ B’

Proof

Let us consider an element ‘x’ such that x ∈ (A ∪ B)’

⇒ x ∉ (A ∪ B)

⇒ x ∉ A or x ∉ B

⇒ x ∈ A’ and x ∈ B’

⇒ x ∈ A’ ∩ B’

Thus, (A ∪ B)’ ⊂ A’ ∩ B’ …..(i)

Again, considering another element, ‘y,’ where y ∈ A’ ∩ B’

⇒ y ∈ A’ and y ∈ B’

⇒ y ∉ A or y ∉ B

⇒ y ∉ (A ∪ B)

⇒ y ∈ (A ∪ B)’

Thus, A’ ∩ B’ ⊂ (A ∪ B)’ …..(ii)

From (i) and (ii), we get

(A ∪ B)’ = A’ ∩ B’

Now, using the Venn diagram, the De Morgan’s law of union is shown

Thus, (A ∪ B)’ = A’ ∩ B’

Hence, the first De Morgan’s law is proved.

In general, for ‘n’ sets, {A₁, A₂, …, A_n}, the formula is written as:

${\left( \cup ^{n}_{k=1} A_{k}\right) ^{c}=\cap ^{n}_{k=1}A_{k}^{c}}$

Second Law

The second De Morgan’s law (or De Morgan’s law of intersection) states that the complement of the intersection of two sets is the union of the complements of each set.

Mathematically, if A and B are two sets, then 

(A ∩ B)’ = A’ ∪ B’

Example

If A = {a, b, c, d}, B = {b, c, d, e}, and U = {a, b, c, d, e, f, g}, then we have

(A ∩ B) = {a, b, c, d} ∩ {b, c, d, e} = {b, c, d} 

A’ = U – A = {a, b, c, d, e, f, g} – {a, b, c, d} = {e, f, g}

B’ = U – B = {a, b, c, d, e, f, g} – {b, c, d, e} = {a, f, g}

Now, (A ∩ B)’ = U – (A ∩ B) = {a, b, c, d, e, f, g} – {b, c, d} = {a, e, f, g}

A’ ∪ B’ = {e, f, g} ∪ {a, f, g} = {a, e, f, g}

Thus, (A ∩ B)’ = A’ ∪ B’

Proof

Let us consider an element ‘x’ such that x ∈ (A ∩ B)’

⇒ x ∉ (A ∩ B)

⇒ x ∉ A and x ∉ B

⇒ x ∈ A’ or x ∈ B’

⇒ x ∈ A’ ∪ B’

Thus, (A ∩ B)’ ⊂ A’ ∪ B’ …..(i)

Again, let us consider another element, ‘y,’ where y ∈ A’ ∪ B’

⇒ y ∈ A’ or y ∈ B’

⇒ y ∉ A and y ∉ B

⇒ y ∉ (A ∩ B)

⇒ y ∈ (A ∩ B)’

Thus, A’ ∪ B’ ⊂ (A ∩ B)’ …..(ii)

From (i) and (ii), we get

(A ∩ B)’ = A’ ∪ B’

Now, using the Venn diagram, the De Morgan’s law of intersection is shown

Similarly, the complement of sets A’ and B’ and their union set A’ ∪ B’ are shown using the Venn diagram. 

Thus, (A ∩ B)’ = A’ ∪ B’

Hence, the second De Morgan’s law is proved.

In general, for ‘n’ sets, {A₁, A₂, …, A_n}, the formula is written as

${\left( \cap ^{n}_{k=1} A_{k}\right) ^{c}=\cup ^{n}_{k=1}A_{k}^{c}}$

In Boolean Algebra

First Law

It states that the complement of OR of two or more variables is the AND of the complement of each variable.

Mathematically, if A and B are two variables, then

(A + B)’ = A’ ⋅ B’

Here,

• + is the OR operator between variables,
• ⋅ is AND operator between variables, and 
• ‘ is a complement operation on the variables

Proof

Here, we will use the following truth table:

These two logic gate circuits are shown:

Second Law

It states that the complement of AND of two or more variables is the OR of the complement of each variable.

Mathematically, if A and B are two variables, then

(A ⋅ B)’ = A’ + B’ 

Here, 

• + is the OR operator between variables,
• ⋅ is AND operator between variables, and 
• ‘ is a complement operation on the variables

Proof

To prove this theorem, we will use the following truth table:

These two logic gate circuits are shown:

Since the complement of a set is similar to negation and union is similar to an OR statement, there are equivalent forms of De Morgan’s Laws in logic.

Negation of the Conjunction of Propositions

It states that if p and q are two propositions, the negation of the conjunction of the propositions is equivalent to the disjunction of the negations of those propositions.

∼(p ∧ q) ⟺ ∼p ∨ ∼q

Here,

• ∧ is the conjunction of statements,
• ∨ is the disjunction of statements,
• ~ is the negation of the statement, and 

≡ is the equivalence of statements.

Proof

Here, we will use a truth table of the propositions p and 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

Negation of the Disjunction of Propositions

It states that if p and q are two propositions, the negation of the disjunction of the propositions is equivalent to the conjunction of the negations of those propositions.

∼(p ∨ q) ⟺ ∼p ∧ ∼q

Here,

• ∨ is the disjunction of statements,
• ∧ is the conjunction of statements,
• ~ is the negation of the statement, and 
• ≡ is the equivalence of statements.

Proof

Here, we use the following truth table of the propositions p and 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

Thus, De Morgan’s laws are used in electronic engineering to develop logic gates. They enable the design of digital circuits using only NAND or NOR gates, which are often more cost-effective and simpler to fabricate.

Formulas

Here is a summary of all the De Morgan’s Laws formulas:

Solved Examples