必要十分条件
論理式\(A,B\)を任意に選んだとき、それらに関する同等\begin{equation*}A\leftrightarrow B
\end{equation*}は恒真式であるとは限りません。つまり、論理式\(A,B\)の選び方によっては、\(A\leftrightarrow B\)が偽になるような解釈が存在し得るということです。一方、与えられた論理式\(A,B\)について、同等\(A\leftrightarrow B\)が恒真式である場合には、すなわち、任意の解釈のもとで\(A\leftrightarrow B\)が真になる場合には、そのことを、\begin{equation*}A\Leftrightarrow B
\end{equation*}で表記します。またこのとき、\(A\)と\(B\)は論理的に同値（logically equivalent）であるとか、\(A\)と\(B\)はお互いに必要十分条件（necessary and sufficient condition）であるなどと言います。
\end{equation*}に関して、以下の真理値表が得られます。
$$\begin{array}{cccc}
\hline
P & P\wedge P & P\vee P & P\wedge P\leftrightarrow P\vee P \\ \hline
1 & 1 & 1 & 1 \\ \hline
0 & 0 & 0 & 1 \\ \hline
\end{array}$$
つまり、\(P\wedge P\leftrightarrow P\vee P\)は2通りの解釈が可能ですが、いずれの解釈においても\(P\wedge P\leftrightarrow P\vee P\)の値は\(1\)であるため、\begin{equation*}P\wedge P\Leftrightarrow P\vee P
\end{equation*}が成り立ちます。つまり、\(P\wedge P\)と\(P\vee P\)はお互いに必要十分です。
\lnot P
\end{equation*}に関して、以下の真理値表が得られます。
$$\begin{array}{cccccc}
\hline
P & Q & Q\wedge \lnot Q & P\rightarrow \left( Q\wedge \lnot Q\right)
& \lnot P & \left( P\rightarrow \left( Q\wedge \lnot Q\right) \right) \leftrightarrow \lnot P \\ \hline
1 & 1 & 0 & 0 & 0 & 1 \\ \hline
1 & 0 & 0 & 0 & 0 & 1 \\ \hline
0 & 1 & 0 & 1 & 1 & 1 \\ \hline
0 & 0 & 0 & 1 & 1 & 1 \\ \hline
\end{array}$$
つまり、\(\left( P\rightarrow \left( Q\wedge \lnot Q\right) \right) \leftrightarrow \lnot P\)は4通りの解釈が可能ですが、いずれの解釈においても\(\left( P\rightarrow \left( Q\wedge \lnot Q\right) \right)\leftrightarrow \lnot P\)の値は\(1\)であるため、\begin{equation*}P\rightarrow \left( Q\wedge \lnot Q\right) \Leftrightarrow \lnot P
\end{equation*}が成り立ちます。したがって、\(P\rightarrow \left( Q\wedge \lnot Q\right) \)と\(\lnot P\)はお互いに必要十分です。
論理式\(A,B\)が与えられたとき、\begin{equation*}A\Leftrightarrow B
\end{equation*}は成り立つとは限りません。以下の例より明らかです。
\end{equation*}に関して、以下の真理値表が得られます。
$$\begin{array}{cccc}
\hline
P & Q & P\vee Q & \left( P\vee Q\right) \leftrightarrow P \\ \hline
1 & 1 & 1 & 1 \\ \hline
1 & 0 & 1 & 1 \\ \hline
0 & 1 & 1 & 0 \\ \hline
0 & 0 & 0 & 1 \\ \hline
\end{array}$$
つまり、\(\left( P\vee Q\right) \leftrightarrow P\)が偽になるような解釈が存在するため\(\left(P\vee Q\right) \leftrightarrow P\)は恒真式ではなく、したがって、\begin{equation*}\left( P\vee Q\right) \Leftrightarrow P
\end{equation*}は成り立ちません。
必要十分条件の代替的な定義
論理式\(A,B\)を任意に選んだとき、それと恒真式\(\top \)の関係は以下の真理値表として整理されます。
$$\begin{array}{cccccc}
\hline
& A & B & \top & A\leftrightarrow B & \left( A\leftrightarrow 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 & 0 & 0 \\ \hline
\left( d\right) & 0 & 0 & 1 & 1 & 1 \\ \hline
\end{array}$$
論理式\(A,B\)について\(A\Leftrightarrow B\)が成り立つことは、論理式\(A\leftrightarrow B\)の値が任意の解釈のもとで\(1\)であることと定義されます。したがって、\(A\Leftrightarrow B\)が成り立つ場合には\(\left( b\right) ,\left( c\right) \)のケースは起こり得ません。それ以外の任意のケースにおいて\(\left( A\leftrightarrow B\right) \leftrightarrow \top \)の値は\(1\)であるため、\(A\Leftrightarrow B\)が成り立つことを論理式\(\left( A\leftrightarrow B\right) \leftrightarrow \top \)が恒真式であることとして、すなわち、\begin{equation*}\left( A\leftrightarrow B\right) \Leftrightarrow \top
\end{equation*}が成り立つこととして定義することもできます。
必要十分であることの証明戦略
論理式\(A,B\)について\(A\Leftrightarrow B\)が成り立つことを示すための基本的な証明戦略は、\(A\leftrightarrow B\)に関する真理値表を描き、それが任意の解釈のもとで値\(1\)をとることを示すというものです。ただ、このような方法とは異なる証明戦略も存在します。
論理式\(A,B\)を任意に選んだとき、含意\(\rightarrow \)と同等\(\leftrightarrow \)の定義より、以下の真理値表を得ます。
$$\begin{array}{cccccc}
\hline
A & B & A\rightarrow B & B\rightarrow A & \left( A\rightarrow B\right) \wedge \left( B\rightarrow A\right) & A\leftrightarrow B \\
\hline
1 & 1 & 1 & 1 & 1 & 1 \\ \hline
1 & 0 & 0 & 1 & 0 & 0 \\ \hline
0 & 1 & 1 & 0 & 0 & 0 \\ \hline
0 & 0 & 1 & 1 & 1 & 1 \\ \hline
\end{array}$$
真理値表から明らかであるように、\(A\leftrightarrow B\)と\(\left( A\rightarrow B\right) \wedge \left( B\rightarrow A\right) \)の真理値は常に一致します。つまり、両者は論理的に同値です。したがって、\(A\leftrightarrow B\)が恒真式であることは\(\left( A\rightarrow B\right) \wedge \left(B\rightarrow A\right) \)が恒真式であることを意味しますが、論理積の定義より、さらにこれは\(A\rightarrow B\)と\(B\rightarrow A\)がともに恒真式であることを意味します。したがって、\(A\leftrightarrow B\)が恒真式であることは、\(A\rightarrow B\)と\(B\rightarrow A\)がともに恒真式であることを意味します。つまり、\(A\Leftrightarrow B\)が成り立つことは、\(A\Rightarrow B\)と\(B\Rightarrow A\)がともに成り立つことを意味します。\(A\)と\(B\)がお互いに必要十分であることは、\(A\)が\(B\)であるための必要条件であるとともに十分条件であることを意味するということです。したがって、\(A\Leftrightarrow B\)が成り立つことを示すためには、\(A\Rightarrow B\)と\(B\Rightarrow A\)が成り立つことをそれぞれ示せばよいということになります。
\end{equation}は成り立つでしょうか。まずは、\begin{equation}
\lnot \left( P\wedge Q\right) \Rightarrow \lnot P\vee \lnot Q \quad \cdots (2)
\end{equation}が成り立つことを示します。\(\lnot \left( P\wedge Q\right) \)の値が\(1\)であるもの仮定します。このとき、否定の定義より\(P\wedge Q\)の値は\(0\)であるため、論理積の定義より\(P\)と\(Q\)の少なくとも一方の値は\(0\)です。すると否定の定義より\(\lnot P\)と\(\lnot Q\)の少なくとも一方の値は\(1\)であるため、論理和の定義より\(\lnot P\vee \lnot Q\)の値は\(1\)です。したがって\(\left( 2\right) \)が成り立つことが示されました。続いて、\begin{equation}\lnot P\vee \lnot Q\Rightarrow \lnot \left( P\wedge Q\right) \quad \cdots (3)
\end{equation}が成り立つことを示します。\(\lnot P\vee \lnot Q\)の値が\(1\)であるものと仮定します。このとき、論理和の定義より\(\lnot P\)と\(\lnot Q\)の少なくとも一方の値が\(1\)であるため、否定の定義より\(P\)と\(Q\)の少なくとも一方の値は\(0\)です。すると論理積の定義より\(P\wedge Q\)の値は\(0\)であるため、否定の定義より\(\lnot \left( P\wedge Q\right) \)の値は\(1\)です。したがって\(\left( 3\right) \)が成り立つことが示されました。\(\left( 2\right) \)と\(\left( 3\right) \)がともに成り立つことが明らかになったため、\(\left( 1\right) \)が成り立つことが明らかになりました。
演習問題
B &:&\left( P\wedge Q\right) \vee \left( \lnot P\wedge \lnot Q\right)
\end{eqnarray*}について、\begin{equation*}
A\Leftrightarrow B
\end{equation*}が成り立つことを、真理値表を用いる方法と、\(A\Rightarrow B\)と\(B\Rightarrow A\)をともに示す方法のそれぞれで証明してください。
B &:&\lnot P\vee \lnot Q
\end{eqnarray*}について、\begin{equation*}
A\Leftrightarrow B
\end{equation*}が成り立つことを、真理値表を用いる方法と、\(A\Rightarrow B\)と\(B\Rightarrow A\)をともに示す方法のそれぞれで証明してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】