論理式\(A,B\)に関して同等\(A\leftrightarrow B\)が恒真式であるならば、\(A\)と\(B\)は論理的に同値であると言い、このことを\(A\Leftrightarrow B\)で表します。またこのとき、\(A\)と\(B\)はお互いに一方が他方であるための必要十分条件であると言います。
次のページ >

必要十分条件

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

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

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

表:必要十分条件

つまり、解釈として4通りありますが、任意の解釈において論理式\(P\rightarrow \left( Q\wedge \lnot Q\right) \)と論理式\(\lnot P\)の値は常に一致するため、\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\)を任意に選んだとき、それと恒真式\(\top \)の間には、以下の真理値表が得られます。

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

表:同等の値

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

論理式\(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\)の値が\(1\)であることは、\(A\rightarrow B\)と\(B\rightarrow A\)の値がともに\(1\)であることとして定義することもできます。論理式\(A,B\)について\(A\Rightarrow B\)が成り立つことは、論理式\(A\rightarrow B\)の値が任意の解釈のもとで\(1\)であることと定義されますが、先の考察より、これは\(A\rightarrow B\)と\(B\rightarrow A\)の値がともに任意の解釈のもとで\(1\)であること、すなわち、\(A\Rightarrow B\)と\(B\Rightarrow A\)がともに成り立つことを意味します。

議論の結論をまとめましょう。論理式\(A,B\)が与えられたとき、\(A\Leftrightarrow B\)が成り立つことは、\(A\Rightarrow B\)と\(B\Rightarrow A\)がともに成り立つこととして定義することもできます。つまり、\(A\)が\(B\)であるための必要十分条件であることは、\(A\)が\(B\)であるための必要条件であるとともに十分条件であることを意味します。同様に、\(B\)が\(A\)であるための必要十分条件であることは、\(B\)が\(A\)であるための必要条件であるとともに十分条件であることを意味します。

 

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

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

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

論理式\(A,B\)について\(A\Rightarrow B\)が成り立つことを示すための証明戦略が明らかになりました。また、論理式\(A,B\)について\(A\Leftrightarrow B\)が成り立つことは、\(A\Rightarrow B\)と\(B\Rightarrow A\)がともに成り立つことを意味します。したがって、論理式\(A,B\)について\(A\Rightarrow B\)が成り立つことを示すためには、\(A\Rightarrow B\)と\(B\Rightarrow A\)が成り立つことを、先の証明戦略にもとづいて示せば十分です。

例(必要十分条件であることの証明)
命題変数\(P,Q\)について、\begin{equation}
\lnot \left( P\wedge Q\right) \ \Leftrightarrow \ \lnot P\vee \lnot Q
\tag{1}
\end{equation}は成り立つでしょうか。まずは、\begin{equation}
\lnot \left( P\wedge Q\right) \ \Rightarrow \ \lnot P\vee \lnot Q \tag{2}
\end{equation}が成り立つことを示します。そこで、\(\lnot \left( P\wedge Q\right) \)の値が\(1\)であると仮定します。このとき、\(P\wedge Q\)の値は\(0\)であるため、\(P\)と\(Q\)の値はともに\(0\)です。したがって、\(P\)と\(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) \tag{3}
\end{equation}が成り立つことを示します。そこで、\(\lnot P\vee \lnot Q\)の値が\(1\)であると仮定します。このとき、\(\lnot P\)と\(\lnot Q\)の少なくとも一方の値が\(1\)であるため、\(P\)と\(Q\)の少なくとも一方の値は\(0\)です。したがって\(P\wedge Q\)は偽であるため、\(\lnot \left( P\wedge Q\right) \)の値は\(1\)です。以上より\(\left( 3\right) \)が成り立つことが示されました。\(\left( 2\right) \)と\(\left( 3\right) \)がともに成り立つことが明らかになったため、\(\left( 1\right) \)が成り立ちます。

次回からは同値変形について解説します。

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

プレミアム会員サービス

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

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

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