論理式 A,B について A→B が恒真式であるならば、すなわち、任意の解釈のもとで A→B の値が 1 であるならば、B は A であるための必要条件であると言い、A は B であるための十分条件であると言います。

2019年1月27日:公開

必要条件と十分条件

論理式\(A,B\)に関して含意\(A\rightarrow B\)が恒真式であるならば、つまり、任意の解釈のもとで\(A\rightarrow B\)の値が\(1\)になるならば、このことを\(A\Rightarrow B\)で表します。またこのとき、\(B\)は\(A\)であるための必要条件(necessary condition)と言い、\(A\)は\(B\)であるための十分条件(sufficient condition)と言います。

恒真式について復習する

 
$$\begin{array}{ccccc}
\hline
A & B & T & A\rightarrow B & \left( A\rightarrow B\right) \leftrightarrow T \\ \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,B\)はそれぞれ\(1\)または\(0\)を取り得るため、起こり得るすべての場合を記した真理値表は上のようになります。\(A\Rightarrow B\)の場合には真理値表の 2 行目の場合は起こり得ません。さらに、\(A\rightarrow B\)と\(\left( A\rightarrow B\right) \leftrightarrow T\)の値は任意の解釈のもとで等しいため、\(A\Rightarrow B\)が成り立つことは\(\left( A\rightarrow B\right) \Leftrightarrow T\)が成り立つことと同義です。

例(必要条件と十分条件)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)を部分論理式として持つ論理式\begin{equation*}
\exists x\in X\ \left( \lnot P\left( x\right) \right) \rightarrow \lnot \left( \exists x\in X\ P\left( x\right) \right)
\end{equation*}について考えます。存在記号\(\exists \)の定義より、上の論理式は、\begin{equation*}
\bigvee\nolimits_{x\in X}\lnot P\left( x\right) \rightarrow \lnot \left( \bigwedge\nolimits_{x\in X}P\left( x\right) \right)
\end{equation*}と言い換えられます。さらに、ド・モルガンの法則を用いて\(\rightarrow \)の左側の論理式を変形すると、\begin{equation*}
\lnot \left( \bigwedge\nolimits_{x\in X}P\left( x\right) \right) \rightarrow \lnot \left( \bigwedge\nolimits_{x\in X}P\left( x\right) \right)
\end{equation*}となります。任意の解釈のもとでこの論理式は真であるため、\begin{equation*}
\exists x\in X\ \left( \lnot P\left( x\right) \right) \Rightarrow \lnot \left( \exists x\in X\ P\left( x\right) \right)
\end{equation*}が成り立ちます。つまり、\(\lnot \left( \exists x\in X\ P\left( x\right) \right) \)は\(\exists x\in X\ \left( \lnot P\left( x\right) \right) \)であるための必要条件であり、\(\exists x\in X\ \left( \lnot P\left( x\right) \right) \)は\(\lnot \left( \exists x\in X\ P\left( x\right) \right) \)であるための十分条件です。
例(必要条件と十分条件)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)を要素として持つ論理式\begin{equation*}
P\left( x\right) \ \wedge Q\left( x\right) \ \rightarrow \ P\left( x\right)
\end{equation*}について考えます。\(P\left( x\right) \)と\(Q\left( x\right) \)の解釈の組み合わせは以下の 4 通りです。\begin{eqnarray*}
&&\left( a\right) \ P\left( \bar{x}\right) \text{と}Q\left( \bar{x}\right) \text{がともに真の場合} \\
&&\left( b\right) \ P\left( \bar{x}\right) \text{が真で}Q\left( \bar{x}\right) \text{が偽の場合} \\
&&\left( c\right) \ P\left( \bar{x}\right) \text{が偽で}Q\left( \bar{x}\right) \text{が真の場合} \\
&&\left( d\right) \ P\left( \bar{x}\right) \text{と}Q\left( \bar{x}\right) \text{がともに偽の場合}
\end{eqnarray*}それぞれの解釈のもとでの真理値表を書くと、

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

表:論理式の値

となります。つまり、\begin{equation*}
P\left( x\right) \ \wedge Q\left( x\right) \ \Rightarrow \ P\left( x\right)
\end{equation*}が成り立つため、\(P\left( x\right) \)は\(P\left( x\right) \wedge Q\left( x\right) \)であるための必要条件であり、\(P\left( x\right) \wedge Q\left( x\right) \)は\(P\left( x\right) \)であるための十分条件です。

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

次へ進む 演習問題(プレミアム会員限定)