命題の論理演算についての基本性質をまとめた．これらの性質は，論理記号を日本語で解釈することによって，直感的に理解することができる．
この記事では，$P,Q,R$を命題とする．
論理和･論理積の性質
まず，直感的に成り立つのは当然のように思える性質を示す．
\[ P\land P\iff P\]
\[ P\lor P\iff P\]
真理値表を用いて示す．
| $P$ | $P\land P$ |
| T | T |
| F | F |
| $P$ | $P\lor P$ |
| T | T |
| F | F |
以上より，示された．$\blacksquare$
\[ (P\land Q)\land R\iff P\land (Q\land R)\]
\[ (P\lor Q)\lor R\iff P\lor (Q\lor R)\]
真理値表を用いて示す．
| $P$ | $Q$ | $R$ | $P\land Q$ | $Q\land R$ | $(P\land Q)\land R$ | $P\land (Q\land R)$ |
| T | T | T | T | T | T | T |
| T | T | F | T | F | F | F |
| T | F | T | F | F | F | F |
| T | F | F | F | F | F | F |
| F | T | T | F | T | F | F |
| F | T | F | F | F | F | F |
| F | F | T | F | F | F | F |
| F | F | F | F | F | F | F |
| $P$ | $Q$ | $R$ | $P\lor Q$ | $Q\lor R$ | $(P\lor Q)\lor R$ | $P\lor (Q\lor R)$ |
| T | T | T | T | T | T | T |
| T | T | F | T | T | T | T |
| T | F | T | T | T | T | T |
| T | F | F | T | F | T | T |
| F | T | T | T | T | T | T |
| F | T | F | T | T | T | T |
| F | F | T | F | T | T | T |
| F | F | F | F | F | F | F |
以上より，示された．$\blacksquare$
\[ P\land Q\iff Q\land P\]
\[ P\lor Q\iff Q\lor P\]
真理値表を用いて示す．
| $P$ | $Q$ | $P\land Q$ | $Q\land P$ |
| T | T | T | T |
| T | F | F | F |
| F | T | F | F |
| F | F | F | F |
| $P$ | $Q$ | $P\lor Q$ | $Q\lor P$ |
| T | T | T | T |
| T | F | T | T |
| F | T | T | T |
| F | F | F | F |
以上より，示された．$\blacksquare$
\[ P\land (P\lor Q)\iff P\]
\[ P\lor (P\land Q)\iff P\]
真理値表を用いて示す．
| $P$ | $Q$ | $P\lor Q$ | $P\land (P\lor Q)$ |
| T | T | T | T |
| T | F | T | T |
| F | T | T | F |
| F | F | F | F |
| $P$ | $Q$ | $P\land Q$ | $P\lor (P\land Q)$ |
| T | T | T | T |
| T | F | F | T |
| F | T | F | F |
| F | F | F | F |
以上より，示された．$\blacksquare$
吸収法則を一般化したものが，次の分配法則である．
\[ P\land (Q\lor R)=(P\land Q)\lor (P\land R)\]
\[ P\lor (Q\land R)=(P\lor Q)\land (P\lor R)\]
真理値表を用いて示す．
| $P$ | $Q$ | $R$ | $Q\lor R$ | $P\land (Q\lor R)$ | $P\land Q$ | $P\land R$ | $(P\land Q)\lor (P\land R)$ |
| T | T | T | T | T | T | T | T |
| T | T | F | T | T | T | F | T |
| T | F | T | T | T | F | T | T |
| T | F | F | F | F | F | F | F |
| F | T | T | T | F | F | F | F |
| F | T | F | T | F | F | F | F |
| F | F | T | T | F | F | F | F |
| F | F | F | F | F | F | F | F |
| $P$ | $Q$ | $R$ | $Q\land R$ | $P\lor (Q\land R)$ | $P\lor Q$ | $P\lor R$ | $(P\lor Q)\land (P\lor R)$ |
| T | T | T | T | T | T | T | T |
| T | T | F | F | T | T | T | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | T | T | T | T | T |
| F | T | F | F | F | T | F | F |
| F | F | T | F | F | F | T | F |
| F | F | F | F | F | F | F | F |
以上より，示された．$\blacksquare$
分配法則で，$Q$を$P$に，$R$を$Q$に置き換えることで，吸収法則を得る．
否定の性質
(または二重否定の導入(double negation introduction)))
\[ P\iff \lnot (\lnot P)\]
真理値表を用いて示す．
| $P$ | $\lnot P$ | $\lnot (\lnot P)$ |
| T | F | T |
| F | T | F |
以上より，示された．$\blacksquare$
次のド･モルガンの法則は，非常に重要な性質である．
\[ \lnot (P\land Q)\iff \lnot P\lor \lnot Q\]
\[ \lnot (P\lor Q)\iff \lnot P\land \lnot Q\]
真理値表を用いて示す．
| $P$ | $Q$ | $\lnot P$ | $\lnot Q$ | $P\land Q$ | $\lnot (P\land Q)$ | $\lnot P\lor \lnot Q$ |
| T | T | F | F | T | F | F |
| T | F | F | T | F | T | T |
| F | T | T | F | F | T | T |
| F | F | T | T | F | T | T |
| $P$ | $Q$ | $\lnot P$ | $\lnot Q$ | $P\lor Q$ | $\lnot (P\lor Q)$ | $\lnot P\land \lnot Q$ |
| T | T | F | F | T | F | F |
| T | F | F | T | T | F | F |
| F | T | T | F | T | F | F |
| F | F | T | T | F | T | T |
以上より，示された．$\blacksquare$
重要な論法
命題の論理関係の重要な帰結として，数学の証明に応用できる論法を紹介しよう．
その準備として，次の概念を導入する．
常に真である命題を恒真命題(またはトートロジー)(tautology)という．
\[ ((P\implies Q)\land P)\implies Q\]
真理値表を用いて示す．
| $P$ | $Q$ | $\lnot P$ | $P\implies Q$ ($\lnot P\lor Q$) | $(P\implies Q)\land P$ | $\lnot ((P\implies Q)\land P)$ | $((P\implies Q)\land P)\implies Q$ |
| T | T | F | T | T | F | T |
| T | F | F | F | F | T | T |
| F | T | T | T | F | T | T |
| F | F | T | T | F | T | T |
以上より，この命題は常に真である．$\blacksquare$
$P\implies Q$が真であることを証明するのが困難であるとき，対偶$\lnot Q\implies \lnot P$が真であることを証明すれば良い．その裏付けを与えるのが，次の対偶論法である．
\[ (P\implies Q)\iff (\lnot Q\implies \lnot P)\]
\[ \begin{array}{lll}&P\implies Q&\\ \iff &\lnot P\lor Q&論理包含の定義\\ \iff &Q\lor \lnot P&論理和の交換法則\\ \iff &\lnot (\lnot Q)\lor \lnot P&二重否定の導入\\ \iff &\lnot Q\implies \lnot P&論理包含の定義\end{array}\]
よって，示された．$\blacksquare$
真理値表を用いて示す．
| $P$ | $Q$ | $\lnot P$ | $\lnot Q$ | $P\implies Q$ ($\lnot P\lor Q$) | $\lnot Q\implies \lnot P$ ($Q\lor \lnot P$) |
| T | T | F | F | T | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
以上より，示された．$\blacksquare$
\[ ((P\implies Q)\land (Q\implies R))\implies (P\implies R)\]
真理値表を用いて示す．
| $P$ | $Q$ | $R$ | $\lnot P$ | $\lnot Q$ | $P\implies Q$ | $Q\implies R$ | $(P\implies Q)\land (Q\implies R)$ | $\lnot ((P\implies Q)\land (Q\implies R))$ | $P\implies R$ | $((P\implies Q)\land (Q\implies R))\implies (P\implies R)$ |
| T | T | T | F | F | T | T | T | F | T | T |
| T | T | F | F | F | T | F | F | T | F | T |
| T | F | T | F | T | F | T | F | T | T | T |
| T | F | F | F | T | F | T | F | T | F | T |
| F | T | T | T | F | T | T | T | F | T | T |
| F | T | F | T | F | T | F | F | T | T | T |
| F | F | T | T | T | T | T | T | F | T | T |
| F | F | F | T | T | T | T | T | F | T | T |
以上より，この命題は常に真である．$\blacksquare$
$P,Q,R$を命題とする．$R$が真であることを直接示すのが難しいとき，$P$の場合と$Q$の場合に分け，$P$のとき$R$が真であり，$Q$のときも$R$が真であることが言えれば，いずれの場合も$R$が真であることが示せたことになる．その裏付けを与えるのが，次の命題11である．
\[ ((P\lor Q)\land (P\implies R)\land (Q\implies R))\implies R\]
真理値表を用いて示す．
| $P$ | $Q$ | $R$ | $\lnot P$ | $\lnot Q$ | $P\lor Q$ | $P\implies R$ | $Q\implies R$ | $(P\lor Q)\land (P\implies R)\land (Q\implies R)$ | $\lnot ((P\lor Q)\land (P\implies R)\land (Q\implies R))$ | $((P\lor Q)\land (P\implies R)\land (Q\implies R))\implies R$ |
| T | T | T | F | F | T | T | T | T | F | T |
| T | T | F | F | F | T | F | F | F | T | T |
| T | F | T | F | T | T | T | T | T | F | T |
| T | F | F | F | T | T | F | T | F | T | T |
| F | T | T | T | F | T | T | T | T | F | T |
| F | T | F | T | F | T | T | F | F | T | T |
| F | F | T | T | T | F | T | T | F | T | T |
| F | F | F | T | T | F | T | T | F | T | T |
以上より，この命題は常に真である．$\blacksquare$
$P,Q$を命題とする．$P$が真であることを直接示すのが難しいとき，$P$が偽，すなわち$\lnot P$が真であると仮定して議論を進めてみる．このように仮定すると，$Q$が真であるということを導くことができるが，実際は$Q$が偽，すなわち$\lnot Q$が真であるとき，$Q$は真でも偽でもあるという状態になってしまい，命題の無矛盾律に反してしまう．つまり，今までの議論のどこかに誤りがあったはずである．$Q$が真であるということが正しく導かれていたのであれば，$P$が偽であると仮定したことが誤っていたことになる．よって，$P$は真であることが示される．この論法は背理法と呼ばれ，その裏付けを与えるのが，次の命題12である．
\[ ((\lnot P\implies Q)\land \lnot Q)\implies P\]
真理値表を用いて示す．
| $P$ | $Q$ | $\lnot Q$ | $\lnot P\implies Q$ ($P\lor Q$) | $(\lnot P\implies Q)\land \lnot Q$ | $\lnot ((\lnot P\implies Q)\land \lnot Q)$ | $((\lnot P\implies Q)\land \lnot Q)\implies P$ |
| T | T | F | T | F | T | T |
| T | F | T | T | T | F | T |
| F | T | F | T | F | T | T |
| F | F | T | F | F | T | T |
以上より，この命題は常に真である．$\blacksquare$
最後に，証明を記述するのに便利な記号を導入しておく．
$\therefore$はゆえに(またはしたがって)(therefore)と読み，それまでの議論から導かれる結論を示す記号である．
$\because$はなぜならば(またはしかるに)(because)と読み，それまでの議論の根拠を示す記号である．
\[ A=B,B=C\]
\[ \therefore A=C\]
\[ A=C\qquad (\because A=B,B=C)\]
- ここでの命題は，論理学でいう｢真偽が定まる主張｣のことを指すのではなく，数学でいう｢真である主張｣のことを指す． ↩︎