必要条件と十分条件

論理式\(A,B\)に関して含意\(A\rightarrow B\)が恒真式であるとき、\(B\)は\(A\)であるための必要条件と言い、\(A\)は\(B\)であるための十分条件と言います。
次のページ >

必要条件と十分条件

論理式\(A,B\)を任意に選んだとき、それらに関する含意\(A\rightarrow B\)は恒真式であるとは限りません。つまり、解釈によって\(A\rightarrow B\)の値が\(0\)になる可能性があります。一方、含意\(A\rightarrow B\)が恒真式である場合には、すなわち、任意の解釈において\(A\rightarrow B\)の値が常に\(1\)であるならば、このことを、\begin{equation*}
A\Rightarrow B
\end{equation*}と表記します。またこのとき、\(B\)は\(A\)であるための必要条件(necessary condition)であると言い、\(A\)は\(B\)であるための十分条件(sufficient condition)であると言います。

恒真式について復習する
例(必要条件と十分条件)
命題変数\(P\)に関する論理式\(\left( P\wedge \lnot P\right) \rightarrow P\)に関して、以下の真理値表が得られます。

$$\begin{array}{cccc}
\hline
P & \lnot P & P\wedge \lnot P & \left( P\wedge \lnot P\right) \rightarrow P \\ \hline
1 & 0 & 0 & 1 \\ \hline
0 & 1 & 0 & 1 \\ \hline
\end{array}$$

表:必要条件と十分条件

つまり、\(\left( P\wedge \lnot P\right) \rightarrow P\)は2通の解釈が可能ですが、いずれの解釈においても\(\left( P\wedge \lnot P\right) \rightarrow P\)の値は\(1\)であるため、\begin{equation*}
\left( P\wedge \lnot P\right) \ \Rightarrow \ P
\end{equation*}が成り立ちます。つまり、\(P\)は\(P\wedge \lnot P\)であるための必要条件であり、\(P\wedge \lnot P\)は\(P\)であるための十分条件です。

例(必要条件と十分条件)
命題変数\(P,Q\)に関する論理式\(\left( P\wedge Q\right) \rightarrow P\)に関して、以下の真理値表が得られます。

$$\begin{array}{cccc}
\hline
P & Q & P\wedge Q & \left( P\wedge Q\right) \rightarrow P \\ \hline
1 & 1 & 1 & 1 \\ \hline
1 & 0 & 0 & 1 \\ \hline
0 & 1 & 0 & 1 \\ \hline
0 & 0 & 0 & 1 \\ \hline
\end{array}$$

表:必要条件と十分条件

つまり、\(\left( P\wedge Q\right) \rightarrow P\)は4通の解釈が可能ですが、いずれの解釈においても\(\left( P\wedge Q\right) \rightarrow P\)の値は\(1\)であるため、\begin{equation*}
\left( P\wedge Q\right) \ \Rightarrow \ P
\end{equation*}が成り立ちます。つまり、\(P\)は\(P\wedge Q\)であるための必要条件であり、\(P\wedge Q\)は\(P\)であるための十分条件です。

 

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

論理式\(A,B\)に関して\(A\Rightarrow B\)が成り立つ場合には、\(B\)のことを「\(A\)であるための必要条件」と呼びますが、これは「\(A\)が真であるためには、\(B\)は真である必要がある」と理解しましょう。その理由は以下の通りです。

$$\begin{array}{ccc}
\hline
A & B & A\rightarrow B \\ \hline
1 & 1 & 1 \\ \hline
1 & 0 & 0 \\ \hline
0 & 1 & 1 \\ \hline
0 & 0 & 1 \\ \hline
\end{array}$$

表:含意の値

\(A,B\)の値の組み合わせは 4 通り存在しますが、それぞれの場合における\(A\rightarrow B\)の値が上の真理値表に記されています。\(A\Rightarrow B\)の場合には\(A\rightarrow B\)の値は\(0\)になり得ないため真理値表の 2 行目の場合は起こり得ず、残りの 3 通りだけが議論の対象になります。つまり、\(A\)が真の場合は 1 行目だけに限定されるため、\(A\)が真であることを保証するためには\(B\)は真である必要があります。以上が必要条件の直感的な意味です。なお、\(A\)が真であるためには\(B\)は真である必要がありますが、\(B\)が偽の場合にも\(A\)が真になる可能性はあります。真理値表の 3 行目の場合が起こり得るからです。

論理式\(A,B\)に関して\(A\Rightarrow B\)が成り立つ場合には、\(A\)のことを「\(B\)であるための十分条件」と呼びますが、これは「\(B\)が真であるためには、\(A\)が真であれば十分である」と理解します。先と同様の議論により、\(A\)が真の場合は真理値表の 1 行目だけに限定されるため、この場合には\(B\)は真です。以上が十分条件の直感的な意味です。なお、\(B\)が真であるためには\(A\)が真であれば十分ですが、\(A\)が偽の場合も\(B\)が真になる可能性はあります。真理値表の 3 行目の場合が起こり得るからです。

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

 

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

論理式\(A,B\)を任意に選んだとき、それと恒真式\(\top \)の間には、以下の真理値表が得られます。

$$\begin{array}{ccccc}
\hline
A & B & \top & A\rightarrow B & \left( A\rightarrow B\right) \leftrightarrow \top \\ \hline
1 & 1 & 1 & 1 & 1 \\ \hline
1 & 0 & 1 & 0 & 0 \\ \hline
0 & 1 & 1 & 1 & 1 \\ \hline
0 & 0 & 1 & 1 & 1 \\ \hline
\end{array}$$

表:含意の値

論理式\(A,B\)について\(A\Rightarrow B\)が成り立つことは、論理式\(A\rightarrow B\)の値が任意の解釈のもとで\(1\)であることと定義されます。したがって、\(A\Rightarrow B\)が成り立つ場合、上の真理値表の2行目の場合は起こり得ません。それ以外の任意の場合において\(\left( A\rightarrow B\right) \leftrightarrow T\)の値は\(1\)であるため、\(A\Rightarrow B\)が成り立つことを、論理式\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}{ccc}
\hline
A & B & A\rightarrow B \\ \hline
1 & 1 & 1 \\ \hline
1 & 0 & 0 \\ \hline
0 & 1 & 1 \\ \hline
0 & 0 & 1 \\ \hline
\end{array}$$

表:含意の値

論理式\(A,B\)について\(A\Rightarrow B\)が成り立つことは、任意の解釈のもとで\(A\rightarrow B\)の値が\(1\)であることとして定義されます。したがって、与えられた論理式\(A,B\)に対して\(A\Rightarrow B\)が成り立つことを証明するためには、上の真理値表中の2行目の場合が起こり得ないことを言えれば十分です。\(A\)の値が\(0\)の場合には、含意\(\rightarrow \)の定義より、\(B\)の値とは関係なく\(A\rightarrow B\)の値は常に\(1\)になります。一方、\(A\)の値が\(1\)の場合、\(B\)の値が\(1\)であることが言えれば\(A\rightarrow B\)の値が\(1\)になることが保証されます。

議論の結論をまとめましょう。論理式\(A,B\)が与えられたとき、\(A\)が恒偽式である場合には\(A\Rightarrow B\)が必ず成り立ちます。また、\(A\)が恒偽式であるとは限らない場合には、\(A\)の値が\(1\)であるという仮定のもとで\(B\)の値が常に\(1\)であることを言えれば、\(A\Rightarrow B\)であることを示したことになります。

例(必要条件・十分条件であることの証明)
命題変数\(P,Q\)について、\begin{equation}
\left( P\wedge \lnot P\right) \ \Rightarrow \ P \tag{1}
\end{equation}は成り立つでしょうか。\(P\wedge \lnot P\)は恒偽式であるため、\(\left( 1\right) \)は成り立ちます。では逆に、\begin{equation}
P\ \Rightarrow \ \left( P\wedge \lnot P\right) \tag{2}
\end{equation}は成り立つでしょうか。\(P\)の値が\(1\)であると仮定します。このとき、\(P\wedge \lnot P\)の値は\(0\)であるため、\(\left( 2\right) \)は成り立ちません。
例(必要条件・十分条件であることの証明)
命題変数\(P,Q\)について、\begin{equation}
\left( P\wedge Q\right) \ \Rightarrow \ P \tag{1}
\end{equation}は成り立つでしょうか。\(P\wedge Q\)の値が\(1\)であると仮定します。このとき、\(\wedge \)の定義より、\(P\)と\(Q\)の値はともに\(1\)であるため、\(\left( 1\right) \)は成り立ちます。では逆に、\begin{equation}
P\ \Rightarrow \ \left( P\wedge Q\right) \tag{2}
\end{equation}は成り立つでしょうか。\(P\)の値が\(1\)であると仮定します。このとき、\(Q\)の値が\(0\)ならば\(P\wedge Q\)の値は\(0\)であるため、\(\left( 2\right) \)は成り立ちません。

次回は必要十分条件について学びます。

次へ進む 質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
次のページ >

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

命題論理
アカウント
ログイン