Proof

Suppose that $A$ and $B$ are sets.
We want to show that for the set intersection "$\cap$", set union "$\cup$" and set complent "$^C$", the laws $(A\cap B)^C=(A^C)\cup (B^C)$ and $(A\cup B)^C=(A^C)\cap (B^C)$ hold.

Let $x\in (A\cap B)^C$.
According to the definition of complent, we have $x\not\in (A\cap B)$.
According to the definition of set intersection, if $x\in (A\cap B)$, then $x\in A \wedge x\in B$, which is negated, i.e. $\neg (x\in A \wedge x\in B).$
According to the De Morgan's laws for logic, this means that $x\not\in A\vee x\not\in B.$
According to the definition of complent, we get $x\in A^C\vee x\in B^C.$
According to the definition of union, we get $x\in (A^C)\cup (B^C).$
It follows from the definition of subsets $(A\cap B)^C\subseteq (A^C)\cup (B^C).$

Let $x\in (A^C)\cup (B^C)$.
According to the definition of union, we get $x\in (A^C)\vee x\in (B^C).$
According to the definition of complent, we have $x\not\in A\vee x\not\in B$.
According to the De Morgan's laws for logic, this means that $\neg(x\in A\wedge x\in B).$
According to the definition of set intersection, we get $\neg (x\in (A\cap B)).$
According to the definition of negation, this is equivalent to $x\not\in (A\cap B).$
By the definition of complent, we get $x\in(A\cap B)^C.$
It follows from the definition of subsets $(A^C)\cup (B^C)\subseteq (A\cap B)^C.$

From both steps of Part 1 and the equality of sets it follows that $(A\cap B)^C=(A^C)\cup (B^C).$

Let $x\in (A\cup B)^C$.
According to the definition of complent, we have $x\not\in (A\cup B)$.
According to the definition of set union, if $x\in (A\cup B)$, then $x\in A \vee x\in B$, which is negated, i.e. $\neg (x\in A \vee x\in B).$
According to the De Morgan's laws for logic, this means that $x\not\in A\wedge x\not\in B.$
According to the definition of complent, we get $x\in A^C\wedge x\in B^C.$
According to the definition of intersection, we get $x\in (A^C)\cap (B^C).$
It follows from the definition of subsets $(A\cup B)^C\subseteq (A^C)\cap (B^C).$

Let $x\in (A^C)\cap (B^C)$.
According to the definition of intersection, we get $x\in (A^C)\wedge x\in (B^C).$
According to the definition of complent, we have $x\not\in A\wedge x\not\in B$.
According to the De Morgan's laws for logic, this means that $\neg(x\in A\vee x\in B).$
According to the definition of set union, we get $\neg (x\in (A\cup B)).$
According to the definition of negation, this is equivalent to $x\not\in (A\cup B).$
By the definition of complent, we get $x\in(A\cup B)^C.$
It follows from the definition of subsets $(A^C)\cap (B^C)\subseteq (A\cup B)^C.$

From both steps of Part 2 and the equality of sets it follows that $(A\cup B)^C=(A^C)\cap (B^C).$
∎

Thank you to the contributors under CC BY-SA 4.0!