教材一覧
教材検索
PROPOSITIONAL LOGIC

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

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

必要条件と十分条件

論理式\(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}{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\)の値の組み合わせは4通り存在しますが、それぞれの場合における\(A\rightarrow B\)の値が上の真理値表に記されています。\(A\Rightarrow B\)の場合には\(A\rightarrow B\)の値は\(0\)になり得ないため\(\left( b\right) \)のケースは起こり得ず、残りの3通りのケースだけが議論の対象になります。その中でも\(A\)が真であるケースは\(\left( a\right) \)に限定されるため、\(A\)が真であることを保証するためには\(B\)は真である必要があります。したがって、「\(A\)が真であるためには、\(B\)は真である必要がある」のです。以上が必要条件の直感的な意味です。なお、\(A\)が真であるためには\(B\)は真である必要がありますが、\(B\)が偽の場合にも\(A\)が真になる可能性はあります。\(\left( c\right) \)のケースが起こり得るからです。
論理式\(A,B\)に関して\(A\Rightarrow B\)が成り立つ場合、\(A\)のことを「\(B\)であるための十分条件」と呼びますが、これを「\(B\)が真であるためには、\(A\)が真であれば十分である」と解釈すればその理由を納得できます。繰り返しになりますが、\(A\Rightarrow B\)の場合には、\(A\)が真であるケースは\(\left( a\right) \)に限定されるため、この場合には\(B\)は真です。したがって、「\(B\)が真であるためには、\(A\)が真であれば十分」なのです。以上が十分条件の直感的な意味です。なお、\(B\)が真であるためには\(A\)が真であれば十分ですが、\(A\)が偽の場合も\(B\)が真になる可能性はあります。\(\left( c\right) \)のケースが起こり得るからです。
必要条件と十分条件を意味から理解するのではなく暗記するためには、記号\(\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\)を示したことになります。

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

 

演習問題

問題(必要条件・十分条件)
命題変数\(P,Q\)に関する以下の2つの論理式\begin{eqnarray*}A &:&P\wedge \lnot Q\rightarrow P\wedge Q \\
B &:&\lnot P
\end{eqnarray*}について、以下のどれが成り立つか、理由とともに答えてください。

  1. \(A\)は\(B\)であるための必要条件だが、\(A\)は\(B\)であるための十分条件ではない。
  2. \(A\)は\(B\)であるための十分条件だが、\(A\)は\(B\)であるための必要条件ではない。
  3. \(A\)は\(B\)であるための必要条件かつ十分条件である。
  4. \(A\)は\(B\)であるための必要条件や十分条件ではない。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(必要条件・十分条件)
命題変数\(P,Q\)に関する以下の2つの論理式\begin{eqnarray*}A &:&P\rightarrow \left( Q\wedge \lnot Q\right) \\
B &:&\lnot P
\end{eqnarray*}について、以下のどれが成り立つか、理由とともに答えてください。

  1. \(A\)は\(B\)であるための必要条件だが、\(A\)は\(B\)であるための十分条件ではない。
  2. \(A\)は\(B\)であるための十分条件だが、\(A\)は\(B\)であるための必要条件ではない。
  3. \(A\)は\(B\)であるための必要条件かつ十分条件である。
  4. \(A\)は\(B\)であるための必要条件や十分条件ではない。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

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

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE
十分条件

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

論理式 A,B に関して同等 A↔B が恒真式であるならば、A と B は論理的に同値であると言います。またこのとき、A と B はお互いに一方が他方であるための必要十分条件であると言います。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

命題論理