命题与逻辑推理

“并非两者都”总能分解成两种穷尽情形——至少有一个为假——这正是否定的析取;这是否定“对所有”命题的逻辑骨架,也是把与门转换成反相输入或门的数字电路(NAND/NOR 等价)背后的原理。

由于命题公式完全由其真值表决定,我们通过穷举 $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$ 得到。

一个条件命题与它的逆否命题永远携带相同的信息——“如果下雨则地面湿”与“如果地面不湿则没有下雨”真假完全一致。这个等价关系正是反证法之外另一种常用间接证明技巧——逆否证明法——的逻辑依据。

我们通过比较 $P\to Q$ 与 $\neg Q\to\neg P$ 在全部四种赋值下的真值表来证明 $(P \to Q) \equiv (\neg Q \to \neg P)$。

情形 $P=1, Q=1$:$P\to Q=1$(前提真、结论真)。同时 $\neg Q=0$,故 $\neg Q\to\neg P$ 前提为假,无论 $\neg P$ 为何,整个条件式都为 $1$。两边都是 $1$。

情形 $P=1, Q=0$:$P\to Q=0$(前提真、结论假是使条件式为假的唯一情形)。同时 $\neg Q=1$、$\neg P=0$,故 $\neg Q\to\neg P$ 前提真、结论假,得 $0$。两边都是 $0$。

情形 $P=0, Q=1$:$P\to Q=1$(前提假使条件式恒真)。同时 $\neg Q=0$,故 $\neg Q\to\neg P=1$ 自动成立。两边都是 $1$。

情形 $P=0, Q=0$:$P\to Q=1$(前提假)。同时 $\neg Q=1$、$\neg P=1$,故 $\neg Q\to\neg P=1$(前提真、结论真)。两边都是 $1$。

四行全部吻合,故 $P\to Q$ 与 $\neg Q\to\neg P$ 真值表完全相同,逻辑等价。注意这与 逆命题 $Q\to P$ 和 否命题 $\neg P\to\neg Q$ 不同——它们二者互相等价,但一般与原条件式不等价,这是常见的论证错误来源。