De Morgan's Law is a fundamental principle in Logic and Set Theory. It establishes a useful relationship between the logical operators 'AND' and 'OR' when negations (NOT) are applied. There are two primary forms of De Morgan's Law, known as De Morgan's First Law and De Morgan's Second Law. These laws state that,
The negation of a disjunction is the conjunction of the negations,
(
A
∪
B
)
′
=
A
′
∩
B
′
{\displaystyle (A\cup B)'=A'\cap B'}
The negation of a conjunction is the disjunction of the negations,
(
A
∩
B
)
′
=
A
′
∪
B
′
{\displaystyle (A\cap B)'=A'\cup B'}
De Morgan's Law for sets
A
{\displaystyle A}
B
{\displaystyle B}
Let
A
{\displaystyle A}
B
{\displaystyle B}
A
{\displaystyle A}
B
{\displaystyle B}
A
{\displaystyle A}
B
{\displaystyle B}
(
A
∪
B
)
′
=
A
′
∩
B
′
{\displaystyle (A\cup B)'=A'\cap B'}
(
A
⋅
B
)
¯
=
(
A
¯
+
B
¯
)
{\displaystyle {\overline {(A\cdot B)}}=({\overline {A}}+{\overline {B}})}
A
{\displaystyle A}
B
{\displaystyle B}
(
A
∩
B
)
′
=
A
′
∪
B
′
{\displaystyle (A\cap B)'=A'\cup B'}
(
A
+
B
)
¯
=
(
A
¯
⋅
B
¯
)
{\displaystyle {\overline {(A+B)}}=({\overline {A}}\cdot {\overline {B}})}
Assume
x
∈
(
A
∪
B
)
′
{\displaystyle x\in (A\cup B)'}
x
∉
A
∪
B
{\displaystyle x\not \in A\cup B}
⟹
x
∉
A
{\displaystyle \implies x\not \in A}
x
∉
B
{\displaystyle x\not \in B}
⟹
x
∈
A
′
{\displaystyle \implies x\in A'}
x
∈
B
′
{\displaystyle x\in B'}
⟹
x
∈
(
A
′
∩
B
′
)
{\displaystyle \implies x\in (A'\cap B')}
∴
(
A
∪
B
)
′
⊆
(
A
′
∩
B
′
)
{\displaystyle \therefore (A\cup B)'\subseteq (A'\cap B')}
x
∈
(
A
′
∩
B
′
)
{\displaystyle x\in (A'\cap B')}
x
∈
A
′
{\displaystyle x\in A'}
x
∈
B
′
{\displaystyle x\in B'}
⟹
x
∉
A
{\displaystyle \implies x\not \in A}
x
∉
B
{\displaystyle x\not \in B}
⟹
x
∉
A
∪
B
{\displaystyle \implies x\not \in A\cup B}
⟹
x
∈
(
A
∪
B
)
′
{\displaystyle \implies x\in (A\cup B)'}
∴
(
A
′
∩
B
′
)
⊆
(
A
∪
B
)
′
{\displaystyle \therefore (A'\cap B')\subseteq (A\cup B)'}
(
A
∩
B
)
′
=
A
′
∪
B
′
{\displaystyle (A\cap B)'=A'\cup B'}
[Proved]
Assume
x
∈
(
A
∩
B
)
′
{\displaystyle x\in (A\cap B)'}
x
∉
A
∩
B
{\displaystyle x\not \in A\cap B}
⟹
x
∉
A
{\displaystyle \implies x\not \in A}
x
∉
B
{\displaystyle x\not \in B}
⟹
x
∈
A
′
{\displaystyle \implies x\in A'}
x
∈
B
′
{\displaystyle x\in B'}
⟹
x
∈
(
A
′
∪
B
′
)
{\displaystyle \implies x\in (A'\cup B')}
∴
(
A
∩
B
)
′
⊆
(
A
′
∪
B
′
)
{\displaystyle \therefore (A\cap B)'\subseteq (A'\cup B')}
x
∈
(
A
′
∪
B
′
)
{\displaystyle x\in (A'\cup B')}
x
∈
A
′
{\displaystyle x\in A'}
x
∈
B
′
{\displaystyle x\in B'}
⟹
x
∉
A
{\displaystyle \implies x\not \in A}
x
∉
B
{\displaystyle x\not \in B}
⟹
x
∉
A
∩
B
{\displaystyle \implies x\not \in A\cap B}
⟹
x
∈
(
A
∩
B
)
′
{\displaystyle \implies x\in (A\cap B)'}
∴
(
A
′
∪
B
′
)
⊆
(
A
∩
B
)
′
{\displaystyle \therefore (A'\cup B')\subseteq (A\cap B)'}
(
A
∩
B
)
′
=
A
′
∪
B
′
{\displaystyle (A\cap B)'=A'\cup B'}
[Proved]
