State and prove De Morgan's laws

First theorem: the complement of a sum (OR) of variables equals the product (AND) of their complements.

$$\overline{A + B} = \bar{A} \cdot \bar{B}$$

Second theorem: the complement of a product (AND) of variables equals the sum (OR) of their complements.

$$\overline{A \cdot B} = \bar{A} + \bar{B}$$

In words: "break the bar and change the sign".

Proof by truth table

For all four input combinations, column 3 equals column 4 and column 5 equals column 6, so both theorems are proved.

Algebraic proof (Theorem 1): let $X = A + B$ and $Y = \bar A \bar B$. Then $X + Y = A + B + \bar A \bar B = A + B + \bar B = 1$ and $X Y = A\bar A \bar B + B \bar A \bar B = 0$. A variable that ORs with X to give 1 and ANDs with X to give 0 is $\bar X$, so $\overline{A+B} = \bar A \bar B$. Theorem 2 follows by duality.