命題論理における必要条件と十分条件

必要条件と十分条件

論理式\(A,B\)を任意に選んだとき、それらに関する含意\begin{equation*}A\rightarrow B
\end{equation*}は恒真式であるとは限りません。つまり、論理式\(A,B\)の選び方によっては、\(A\rightarrow B\)が偽になるような解釈が存在し得るということです。一方、与えられた論理式\(A,B\)について、含意\(A\rightarrow B\)が恒真式である場合には、すなわち、任意の解釈のもとで\(A\rightarrow B\)が真になる場合には、そのことを、\begin{equation*}A\Rightarrow B
\end{equation*}で表記します。またこのとき、\(B\)は\(A\)であるための必要条件（necessary condition）であると言い、\(A\)は\(B\)であるための十分条件（sufficient condition）であると言います。

論理式\(A,B\)が与えられたとき、\begin{equation*}A\Rightarrow B
\end{equation*}は成り立つとは限りません。以下の例より明らかです。

必要条件と十分条件の直感的な解釈

論理式\(A,B\)に関して\(A\Rightarrow B\)が成り立つ場合、\(B\)のことを「\(A\)であるための必要条件」と呼びますが、これを「\(A\)が真であるためには、\(B\)は真である必要がある」と解釈すればその理由を納得できます。以下の真理値表を観察してください。

$$\begin{array}{cccc}
\hline
& A & B & A\rightarrow B \\ \hline
\left( a\right) & 1 & 1 & 1 \\ \hline
\left( b\right) & 1 & 0 & 0 \\ \hline
\left( c\right) & 0 & 1 & 1 \\ \hline
\left( d\right) & 0 & 0 & 1 \\ \hline
\end{array}$$

論理式\(A\rightarrow B\)は\(\left( a\right) \)から\(\left( d\right) \)までの4通りの解釈が可能ですが、それぞれの場合における\(A\rightarrow B\)の値が上の真理値表に記されています。\(A\Rightarrow B\)の場合には\(A\rightarrow B\)の値は\(0\)になり得ないため\(\left( b\right) \)のケースは起こり得ず、残りの3通りのケースだけが議論の対象になります。その中でも\(A\)が真であるケースは\(\left( a\right) \)に限定されるため、\(A\Rightarrow B\)が成り立つ場合、\(A\)が真であることを保証するためには\(B\)は真である必要があります。言い換えると、\(B\)が偽である場合、\(\left( d\right) \)が起こり得るため\(A\)が真であることを保証できません。したがって、「\(A\)が真であるためには、\(B\)は真である必要がある」のです。以上が「必要条件」の直感的な意味です。

論理式\(A,B\)に関して\(A\Rightarrow B\)が成り立つ場合、\(A\)のことを「\(B\)であるための十分条件」と呼びますが、これを「\(B\)が真であるためには、\(A\)が真であれば十分である」と解釈すればその理由を納得できます。先の真理値表を再掲します。

$$\begin{array}{cccc}
\hline
& A & B & A\rightarrow B \\ \hline
\left( a\right) & 1 & 1 & 1 \\ \hline
\left( b\right) & 1 & 0 & 0 \\ \hline
\left( c\right) & 0 & 1 & 1 \\ \hline
\left( d\right) & 0 & 0 & 1 \\ \hline
\end{array}$$

繰り返しになりますが、\(A\Rightarrow B\)の場合には\(A\rightarrow B\)の値は\(0\)になり得ないため\(\left( b\right) \)のケースは起こり得ず、残りの3通りのケースだけが議論の対象になります。加えて、\(A\)が真であるケースは\(\left(a\right) \)に限定されるとともに、その場合に\(B\)は真です。したがって、\(A\Rightarrow B\)が成り立つ場合、\(A\)が真であることを言えれば\(B\)もまた真であることも確定します。したがって、「\(B\)が真であるためには、\(A\)が真であれば十分」なのです。以上が「十分条件」の直感的な意味です。

必要条件と十分条件を意味から理解するのではなく暗記するためには、記号\(\Rightarrow \)をコンパス（方位磁石・羅針盤）の針とみなせばよいでしょう。コンパスの針の先は北（North）を指します。また、含意の記号の先にあるのは必要条件（Necessary condition）です。両者とも英語にした場合の頭文字は「N」であるため、「針の先はN」であることを思い出せば、必要条件と十分条件を混同する恐れはありません。

必要条件と十分条件の代替的な定義

論理式\(A,B\)を任意に選んだとき、それらと恒真式\(\top \)の関係は以下の真理値表として整理されます。

$$\begin{array}{cccccc}
\hline
& A & B & \top & A\rightarrow B & \left( A\rightarrow B\right) \leftrightarrow \top \\ \hline
\left( a\right) & 1 & 1 & 1 & 1 & 1 \\ \hline
\left( b\right) & 1 & 0 & 1 & 0 & 0 \\ \hline
\left( c\right) & 0 & 1 & 1 & 1 & 1 \\ \hline
\left( d\right) & 0 & 0 & 1 & 1 & 1 \\ \hline
\end{array}$$

論理式\(A,B\)について\(A\Rightarrow B\)が成り立つことは、論理式\(A\rightarrow B\)の値が任意の解釈のもとで\(1\)であることと定義されます。したがって、\(A\Rightarrow B\)が成り立つ場合には\(\left( b\right) \)のケースは起こり得ません。それ以外の任意のケースにおいて\(\left( A\rightarrow B\right)\leftrightarrow T\)の値は\(1\)であるため、\(A\Rightarrow B\)が成り立つことを論理式\(\left( A\rightarrow B\right) \leftrightarrow \top \)が恒真式であることとして、すなわち、\begin{equation*}\left( A\rightarrow B\right) \Leftrightarrow \top
\end{equation*}が成り立つこととして定義することもできます。

必要条件や十分条件であることの証明戦略

論理式\(A,B\)について\(A\Rightarrow B\)や\(B\Rightarrow A\)が成り立つことを示すための基本的な証明戦略は、\(A\rightarrow B\)や\(B\rightarrow A\)に関する真理値表を描き、これらの論理式が任意の解釈のもとで値\(1\)をとることを示すというものです。ただ、このような方法とは異なる証明戦略も存在します。

論理式\(A,B\)に関する含意\(A\rightarrow B\)は以下の真理値表によって定義されます。

$$\begin{array}{cccc}
\hline
& A & B & A\rightarrow B \\ \hline
\left( a\right) & 1 & 1 & 1 \\ \hline
\left( b\right) & 1 & 0 & 0 \\ \hline
\left( c\right) & 0 & 1 & 1 \\ \hline
\left( d\right) & 0 & 0 & 1 \\ \hline
\end{array}$$

論理式\(A,B\)について\(A\Rightarrow B\)が成り立つことは、任意の解釈のもとで\(A\rightarrow B\)の値が\(1\)であることとして定義されます。したがって、与えられた論理式\(A,B\)に対して\(A\Rightarrow B\)が成り立つことを証明するためには、上の真理値表中の\(\left( b\right) \)のケースが起こり得ないことを言えれば十分です。\(A\)の値が\(0\)の場合、含意\(\rightarrow \)の定義より、\(B\)の値とは関係なく\(A\rightarrow B\)の値は常に\(1\)になるため、この場合には\(A\Rightarrow B\)を示すために証明しなければならないことは特に存在しません。一方、\(A\)の値が\(1\)の場合、\(A\rightarrow B\)の値が\(1\)であるためには\(B\)の値が\(1\)である必要があります。言い換えると、\(A\)の値が\(1\)の場合には、\(B\)の値が\(1\)であることを証明できれば\(A\Rightarrow B\)が成り立つことを示したことになります。

以上を踏まえた上で結論を整理します。まず、\(A\)が恒偽式である場合には、\(A\Rightarrow B\)は無条件で成立します。また、\(A\)が恒真式の場合には、\(B\)が真であることを証明すれば\(A\Rightarrow B\)が成立することを示したことになります。また、\(A\)が事実式である場合、\(A\)が真であるという仮定のもとで\(B\)が真であることを証明すれば\(A\Rightarrow B\)が成立したことを示したことになります。

演習問題