De Morgan's laws for propositions

We prove $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ by exhaustively checking all four combinations of truth values for $P$ and $Q$, since a propositional formula is fully determined by its truth table.

Case $P=1, Q=1$: $P \wedge Q = 1$, so $\neg(P\wedge Q)=0$. Also $\neg P=0$ and $\neg Q=0$, so $(\neg P)\vee(\neg Q)=0$. Both sides equal $0$.

Case $P=1, Q=0$: $P\wedge Q=0$, so $\neg(P\wedge Q)=1$. Also $\neg P=0$, $\neg Q=1$, so $(\neg P)\vee(\neg Q)=1$. Both sides equal $1$.

Case $P=0, Q=1$: by symmetry with the previous case, $\neg(P\wedge Q)=1$ and $(\neg P)\vee(\neg Q)=1$. Both sides agree.

Case $P=0, Q=0$: $P\wedge Q=0$, so $\neg(P\wedge Q)=1$. Also $\neg P=1$, $\neg Q=1$, so $(\neg P)\vee(\neg Q)=1$. Both sides agree.

All four rows of the truth table match, so $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ holds as a tautology (an identity true under every assignment). The second law $\neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$ follows by an identical four-row check, or algebraically by substituting $\neg P, \neg Q$ for $P, Q$ in the first law and negating both sides using $\neg\neg X \equiv X$.