命題に対するド・モルガンの法則

真理値表によって命題論理式は完全に決まるので、$P$ と $Q$ の真理値の4通りの組み合わせをすべて調べて $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ を証明する。

場合 $P=1, Q=1$: $P \wedge Q = 1$ なので $\neg(P\wedge Q)=0$。また $\neg P=0$、$\neg Q=0$ なので $(\neg P)\vee(\neg Q)=0$。両辺とも $0$ で一致する。

場合 $P=1, Q=0$: $P\wedge Q=0$ なので $\neg(P\wedge Q)=1$。また $\neg P=0$、$\neg Q=1$ なので $(\neg P)\vee(\neg Q)=1$。両辺とも $1$ で一致する。

場合 $P=0, Q=1$: 先の場合と対称なので $\neg(P\wedge Q)=1$、$(\neg P)\vee(\neg Q)=1$。両辺一致する。

場合 $P=0, Q=0$: $P\wedge Q=0$ なので $\neg(P\wedge Q)=1$。また $\neg P=1$、$\neg Q=1$ なので $(\neg P)\vee(\neg Q)=1$。両辺一致する。

真理値表の4行すべてが一致するので、$\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ はトートロジー(すべての割り当てで真になる恒真式)として成り立つ。第二法則 $\neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$ も同様に4行を調べれば得られるし、あるいは第一法則で $P, Q$ を $\neg P, \neg Q$ に置き換えて両辺を否定し $\neg\neg X \equiv X$ を使う代数的方法でも得られる。