De Morgan's laws

Statement

For all propositions $p$ and $q$, these two logical equivalences hold. $$\neg (p \lor q) \equiv \neg p \land \neg q$$ $$\neg (p \land q) \equiv \neg p \lor \neg q$$

Remarks

The first law is also valid in intuitionistic logic. In the second law, only the direction from $\neg p \lor \neg q$ to $\neg (p \land q)$ is. The laws for sets have the same form. See De Morgan's laws for sets. The negation of a universal statement is the analogue for quantifiers.

Explanations

L1 human

To negate "and", change it to "or" and negate each part. "$n$ is not both even and prime" means "$n$ is not even, or $n$ is not prime". A truth table with four rows proves each law.