命题的德摩根定律

由于命题公式完全由其真值表决定,我们通过穷举 $P$ 与 $Q$ 的四种真值组合来证明 $\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$。两边一致。

真值表全部四行都吻合,故 $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ 作为重言式(在每种赋值下都为真的恒等式)成立。第二条定律 $\neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$ 可用同样的四行核验得到,也可用代数方法:把第一条定律中的 $P, Q$ 换成 $\neg P, \neg Q$ 并对两边取否定,利用 $\neg\neg X \equiv X$ 得到。