必要十分条件
論理式\(A,B\)を任意に選んだとき、それらに関する同等\(A\leftrightarrow B\)は恒真式であるとは限りません。つまり、解釈によっては\(A\leftrightarrow B\)から得られる命題が偽になる可能性があります。一方、同等\(A\leftrightarrow B\)が恒真式である場合には、すなわち、任意の解釈において\(A\leftrightarrow B\)から得られる命題が真であるならば、そのことを、\begin{equation*} A\Leftrightarrow B
\end{equation*}と表記します。またこのとき、\(A\)と\(B\)は論理的に同値（logically equivalent）であるとか、\(A\)と\(B\)はお互いに一方が他方であるための必要十分条件（necessary and sufficient condition）であると言います。
x\right) \right) \quad \cdots (1)
\end{equation}について考えます。これは開論理式であるため、値を確定するために変数\(x\)の定義域\(\overline{X}\)と命題関数が表す条件\(\overline{P}\left( x\right) \)および変数に代入する値\(\overline{x}\)を任意に選びます。その解釈のもとで命題\begin{equation} \overline{P}\left( \overline{x}\right) \leftrightarrow \left( \overline{P}\left( \overline{x}\right) \wedge \overline{P}\left( \overline{x}\right)
\right) \quad \cdots (2)
\end{equation}が得られるため、命題論理を用いて値を判定できます。実際、命題論理におけるベキ等律より\(\left( 2\right) \)は真です。任意の解釈のもとで同様の議論が成り立つため\(\left( 1\right) \)は恒真式であり、したがって、\begin{equation*} P\left( x\right) \Leftrightarrow \left( P\left( x\right) \wedge P\left(
x\right) \right)
\end{equation*}が成り立ちます。
\left( \forall x\in X:P\left( x\right) \right) \quad \cdots (1)
\end{equation}について考えます。これは閉論理式であるため、値を確定するために変数\(x\)の定義域\(\overline{X}\)と命題関数が表す条件\(\overline{P}\left( x\right) \)を任意に選びます。その解釈のもとで得られる以下の命題\begin{equation} \exists x\in \overline{X}:\lnot \overline{P}\left( x\right) \quad \cdots (2)
\end{equation}が真であることは、少なくとも1つの値\(\overline{x}\in \overline{X}\)について\(\lnot \overline{P}\left( \overline{x}\right) \)が真であること、すなわち\(\overline{P}\left( \overline{x}\right) \)が偽であることを意味します。一方、同じ解釈のもとで得られる以下の命題\begin{equation} \lnot \left( \forall x\in \overline{X}:\overline{P}\left( x\right) \right)
\quad \cdots (3)
\end{equation}が真であることは、「すべての値\(\overline{x}\in \overline{X} \)について\(\overline{P}\left( \overline{x}\right) \)が真である」ことが偽であること、すなわち、少なくとも1つの値\(\overline{x}\in \overline{X}\)について\(\overline{P}\left( \overline{x}\right) \)が偽であることを意味します。したがって\(\left( 2\right) \)と\(\left( 3\right) \)は同じ値をとります。任意の解釈のもとで同様の議論が成り立つため\(\left( 1\right) \)は恒真式であり、したがって、\begin{equation*} \left( \exists x\in X:\lnot P\left( x\right) \right) \Leftrightarrow \lnot
\left( \forall x\in X:P\left( x\right) \right)
\end{equation*}が成り立ちます。
必要十分であることの証明戦略
論理式\(A,B\)について\(A\Leftrightarrow B\)が成り立つことを示すための基本方針は、任意の解釈のもとで\(A\leftrightarrow B\)が真であることを示すというものです。ただし、次のような方針を採用することもできます。
解釈を任意に選び、その解釈のもとで\(A,B\)から得られる命題を\(\overline{A},\overline{B}\)で表記します。命題論理における\(\leftrightarrow \)と\(\rightarrow \)の関係より、\begin{equation*} \overline{A}\leftrightarrow \overline{B}
\end{equation*}が真であることは、\begin{equation*}
\left( \overline{A}\rightarrow \overline{B}\right) \wedge \left( \overline{B}\rightarrow \overline{A}\right)
\end{equation*}が真であることと必要十分です。さらに、論理積の定義より、これは、\begin{eqnarray*}
\overline{A} &\rightarrow &\overline{B} \\
\overline{B} &\rightarrow &\overline{A}
\end{eqnarray*}がともに真であることと必要十分です。
任意の解釈のもとで同様の議論が成り立つため、\begin{equation*}
A\leftrightarrow B
\end{equation*}が恒真式であることは、\begin{eqnarray*}
A &\rightarrow &B \\
B &\rightarrow &A
\end{eqnarray*}がともに恒真式であることと必要十分です。したがって、\begin{equation*}
A\Leftrightarrow B
\end{equation*}が成り立つことと、\begin{eqnarray*}
A &\Rightarrow &B \\
B &\Rightarrow &A
\end{eqnarray*}がともに成り立つことは必要十分です。
したがって、\(A\Leftrightarrow B\)が成り立つことを示す代わりに、\(A\Rightarrow B\)と\(B\Rightarrow A\)がともに成り立つことを示せば十分です。言い換えると、\(A\)が\(B\)であるための必要十分条件であることは、\(A\)が\(B\)であるための必要条件であるとともに、十分条件でもあることを意味します。
\exists x\in X:\lnot P\left( x\right) \right)
\end{equation*}が成り立つことを示します。まずは\(\Rightarrow \)の証明です。そこで、\begin{equation*} \forall x\in X:P\left( x\right)
\end{equation*}が真であるような解釈を任意に選びます。このとき、すべての\(x\in X\)について\(P\left( x\right) \)は真です。したがって、\(\lnot P\left( x\right) \)が真となる\(x\in X\)は存在しないため、\begin{equation*} \exists x\in X:\lnot P\left( x\right)
\end{equation*}は偽であり、ゆえに、\begin{equation*}
\lnot \left( \exists x\in X:\lnot P\left( x\right) \right)
\end{equation*}は真です。任意の解釈のもとで同様の議論が成り立つため、\begin{equation*}
\left( \forall x\in X:P\left( x\right) \right) \Rightarrow \lnot \left(
\exists x\in X:\lnot P\left( x\right) \right)
\end{equation*}の証明が完了しました。次に\(\Leftarrow \)の証明です。そこで、\begin{equation*} \lnot \left( \exists x\in X:\lnot P\left( x\right) \right)
\end{equation*}が真であるような解釈を任意に選びます。このとき、\begin{equation*}
\exists x\in X:\lnot P\left( x\right)
\end{equation*}は偽です。したがって\(\lnot P\left( x\right) \)が真となる\(x\in X\)は存在しません。つまり、すべての\(x\in X\)について\(\lnot P\left( x\right) \)は偽であり、したがって、すべての\(x\in X\)について\(P\left( x\right) \)は真です。ゆえに、\begin{equation*} \forall x\in X:P\left( x\right)
\end{equation*}は真です。任意の解釈のもとで同様の議論が成り立つため、\begin{equation*}
\lnot \left( \exists x\in X:\lnot P\left( x\right) \right) \Rightarrow
\left( \forall x\in X:P\left( x\right) \right)
\end{equation*}の証明が完了しました。\(\Rightarrow \)と\(\Leftarrow \)がともに成り立つことが示されたため、\begin{equation*} \left( \forall x\in X:P\left( x\right) \right) \Leftrightarrow \lnot \left(
\exists x\in X:\lnot P\left( x\right) \right)
\end{equation*}であることが明らかになりました。
演習問題
\lnot \left( \exists x\in X:P\left( x\right) \right) \Leftrightarrow \left(
\forall x\in X:\lnot P\left( x\right) \right)
\end{equation*}が成り立つことを、\(\Rightarrow \)と\(\Leftarrow \)をそれぞれ示すことによって証明してください。
\left( \forall x\in X:P\left( x\right) \wedge Q\left( x\right) \right)
\Leftrightarrow \left[ \left( \forall x\in X:P\left( x\right) \right) \wedge
\left( \forall x\in X:Q\left( x\right) \right) \right] \end{equation*}が成り立つことを証明してください。
\left(\exists x\in X:P\left(x\right)\vee Q\left(x\right)\right)
\Leftrightarrow \left[ \left(\exists x\in X:P\left(x\right)\right) \vee
\left(\exists x\in X:Q\left(x\right)\right) \right] \end{equation*}が成り立つことを証明してください。
\begin{equation*}
\left(\exists x\in X:P\left(x\right)\wedge Q\left(x\right)\right)
\Leftrightarrow \left[ \left(\exists x\in X:P\left(x\right)\right) \wedge
\left(\exists x\in X:Q\left(x\right)\right) \right] \end{equation*}これが成り立たないことを示す解釈を1つ与えてください。
A&\Leftrightarrow&B \\
B&\Leftrightarrow&C
\end{eqnarray*}が成り立つものとします。このとき、
\begin{equation*}
A\Leftrightarrow C
\end{equation*}が成り立つことを証明してください。
