WIIS

教材一覧
教材一覧
教材検索
PROPOSITIONAL LOGIC

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

目次

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

必要十分条件

論理式\(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\leftrightarrow B\)と\(\left( A\leftrightarrow B\right) \leftrightarrow\top \)の真理値は常に一致します。つまり、両者は論理的に同値です。したがって、\(A\leftrightarrow B\)が恒真式であることは、\(\left( A\leftrightarrow B\right)\leftrightarrow \top \)が恒真式であることを意味します。つまり、\(A\Leftrightarrow B\)が成り立つことを、\begin{equation*}\left( A\leftrightarrow B\right) \Leftrightarrow \top
\end{equation*}が成り立つこととして定義できるということです。\(A\)と\(B\)が論理的に同値であることは、同等\(A\leftrightarrow B\)が恒真式であることを意味するということです。
論理式\(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,B\)について\(A\Leftrightarrow B\)が成り立つことを示すための基本的な証明戦略は、論理式\(A\leftrightarrow B\)の真理値表を描き、それが任意の解釈のもとで値\(1\)をとることを示すというものです。ただ、このような方法とは異なる証明戦略も存在します。
繰り返しになりますが、論理式\(A,B\)について\(A\Leftrightarrow B\)が成り立つことは、\(A\Rightarrow B\)と\(B\Rightarrow A\)がともに成り立つことを意味します。したがって、\(A\Leftrightarrow B\)が成り立つことを示すためには、\(A\Rightarrow B\)と\(B\Rightarrow A\)が成り立つことをそれぞれ示せばよいということになります。

例(必要十分条件であることの証明)
命題変数\(P,Q\)について、\begin{equation}\lnot \left( P\wedge Q\right) \Leftrightarrow \lnot P\vee \lnot Q \quad \cdots (1)
\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) \)が成り立つことが明らかになりました。

 

演習問題

問題(必要十分条件)
命題変数\(P,Q\)に関する以下の2つの論理式\begin{eqnarray*}A &:&P\leftrightarrow Q \\
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\)をともに示す方法のそれぞれで証明してください。
証明

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

問題(必要十分条件)
命題変数\(P,Q\)に関する以下の2つの論理式\begin{eqnarray*}A &:&\lnot \left( P\wedge Q\right) \\
B &:&\lnot P\vee \lnot Q
\end{eqnarray*}について、\begin{equation*}
A\Leftrightarrow B
\end{equation*}が成り立つことを、真理値表を用いる方法と、\(A\Rightarrow B\)と\(B\Rightarrow A\)をともに示す方法のそれぞれで証明してください。
証明

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

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

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

関連知識

必要十分条件
命題論理における恒真式・恒偽式・事実式

論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 1 であるならば、その論理式を恒真式やトートロジーなどと呼びます。また、論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 0 であるならば、その論理式を恒偽式や矛盾式などと呼びます。恒真式や恒偽式ではない論理式を事実式と呼びます。

DISCUSSION

質問とコメント

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

命題論理