Timeless Theorems of Mathematics/De Morgan's laws

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,

1. The negation of a disjunction is the conjunction of the negations, $(A\cup B)'=A'\cap B'$
2. The negation of a conjunction is the disjunction of the negations, $(A\cap B)'=A'\cup B'$

Proof

De Morgan's Law for sets $A$ and $B$

Let $A$ and $B$ are two sets. De Morgan's First Law states that the complement of the union of $A$ and $B$ sets is the same as the intersection of the complements of $A$ and $B$. That means, $(A\cup B)'=A'\cap B'$, or ${\overline {(A\cdot B)}}=({\overline {A}}+{\overline {B}})$. And De Morgan's First Law states that the complement of the intersection of $A$ and $B$ is the same as the union of their complements, $(A\cap B)'=A'\cup B'$, or ${\overline {(A+B)}}=({\overline {A}}\cdot {\overline {B}})$.

De Morgan's First Law

Assume $x\in (A\cup B)'$. Then $x\not \in A\cup B$.

$\implies x\not \in A$ AND $x\not \in B$

$\implies x\in A'$ AND $x\in B'$

$\implies x\in (A'\cap B')$

$\therefore (A\cup B)'\subseteq (A'\cap B')$

Again, Let, $x\in (A'\cap B')$. Then, $x\in A'$ AND $x\in B'$

$\implies x\not \in A$ AND $x\not \in B$

$\implies x\not \in A\cup B$.

$\implies x\in (A\cup B)'$

$\therefore (A'\cap B')\subseteq (A\cup B)'$

Therefore, $(A\cap B)'=A'\cup B'$ [Proved]

De Morgan's Second Law

Assume $x\in (A\cap B)'$. Then $x\not \in A\cap B$.

$\implies x\not \in A$ OR $x\not \in B$

$\implies x\in A'$ OR $x\in B'$

$\implies x\in (A'\cup B')$

$\therefore (A\cap B)'\subseteq (A'\cup B')$

Again, Let, $x\in (A'\cup B')$. Then, $x\in A'$ OR $x\in B'$

$\implies x\not \in A$ OR $x\not \in B$

$\implies x\not \in A\cap B$.

$\implies x\in (A\cap B)'$

$\therefore (A'\cup B')\subseteq (A\cap B)'$

Therefore, $(A\cap B)'=A'\cup B'$ [Proved]