命題と論理的推論

「両方ではない」は常に「少なくとも一方が偽」という2つの網羅的な場合に分かれ、これはまさに否定の選言である。これは「すべての」文を否定する論理的骨格であり、ANDゲートを反転入力のORゲートに変換するデジタル回路(NAND/NOR の等価性)の裏にある考え方でもある。

真理値表によって命題論理式は完全に決まるので、$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$ を使う代数的方法でも得られる。

条件文とその対偶は常に同じ情報を持つ——「雨が降れば地面が濡れる」は「地面が濡れていなければ雨は降っていない」とまったく同じ真理値を持つ。この同値性は、間接証明の2大手法の一つである対偶証明法(もう一つは背理法)の論理的根拠である。

$(P \to Q) \equiv (\neg Q \to \neg P)$ を、$P\to Q$ と $\neg Q\to\neg P$ の真理値表を4通りの割り当てすべてで比較して証明する。

場合 $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$。

4行すべてが一致するので、$P\to Q$ と $\neg Q\to\neg P$ は真理値表が同一であり、論理的に同値である。これは 逆 $Q\to P$ や 裏 $\neg P\to\neg Q$ とは異なる点に注意。これらは互いに同値だが、一般には元の条件文とは同値ではない——よくある誤った論証の原因である。