必要条件と十分条件
論理式\(A,B\)を任意に選んだとき、それらに関する含意\(A\rightarrow B\)は恒真式であるとは限りません。つまり、解釈によっては\(A\rightarrow B\)から得られる命題が偽になる可能性があります。一方、含意\(A\rightarrow B\)が恒真式である場合には、すなわち、任意の解釈において\(A\rightarrow B\)から得られる命題が真であるならば、このことを、\begin{equation*}
A\Rightarrow B
\end{equation*}と表記します。またこのとき、\(B\)は\(A\)であるための必要条件（necessary condition）と言い、\(A\)は\(B\)であるための十分条件（sufficient condition）と言います。
例（必要条件と十分条件）
変数\(x\in X\)を持つ命題関数\(P\left( x\right) \)に関する以下の論理式\begin{equation}
P\left( x\right) \wedge \lnot P\left( x\right) \rightarrow P\left( x\right)
\quad\cdots (1)
\end{equation}について考えます。解釈を任意に選んだ上で、そのときに\(P\left( x\right) \)から得られる命題を\(P\left( \overline{x}\right) \)で表記すると、\(\left( 1\right) \)から得られる命題は、\begin{equation*}
P\left( \overline{x}\right) \wedge \lnot P\left( \overline{x}\right)
\rightarrow P\left( \overline{x}\right)
\end{equation*}となります。これを同値変形すると、\begin{eqnarray*}
P\left( \overline{x}\right) \wedge \lnot P\left( \overline{x}\right)
\rightarrow P\left( \overline{x}\right) &\Leftrightarrow &\lnot \left(
P\left( \overline{x}\right) \wedge \lnot P\left( \overline{x}\right) \right)
\vee P\left( \overline{x}\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\left( \overline{x}\right) \vee \lnot \lnot
P\left( \overline{x}\right) \right) \vee P\left( \overline{x}\right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \lnot P\left( \overline{x}\right) \vee P\left(
\overline{x}\right) \right) \vee P\left( \overline{x}\right) \quad \because
\text{二重否定} \\
&\Leftrightarrow &\top \vee P\left( \overline{x}\right) \quad \because \text{排中律} \\
&\Leftrightarrow &\top \quad \because \text{恒真式}\top
\text{の性質}
\end{eqnarray*}すなわち恒真式\(\top \)となります。任意の解釈のもとで同様の議論が成り立つため、\(\left( 1\right) \)が恒真式であることが明らかになりました。したがって、\(P\left( x\right) \)は\(P\left( x\right) \wedge \lnot P\left( x\right) \)であるための必要条件であり、逆に、\(P\left( x\right) \wedge \lnot P\left( x\right) \)は\(P\left( x\right) \)であるための十分条件です。
P\left( x\right) \wedge \lnot P\left( x\right) \rightarrow P\left( x\right)
\quad\cdots (1)
\end{equation}について考えます。解釈を任意に選んだ上で、そのときに\(P\left( x\right) \)から得られる命題を\(P\left( \overline{x}\right) \)で表記すると、\(\left( 1\right) \)から得られる命題は、\begin{equation*}
P\left( \overline{x}\right) \wedge \lnot P\left( \overline{x}\right)
\rightarrow P\left( \overline{x}\right)
\end{equation*}となります。これを同値変形すると、\begin{eqnarray*}
P\left( \overline{x}\right) \wedge \lnot P\left( \overline{x}\right)
\rightarrow P\left( \overline{x}\right) &\Leftrightarrow &\lnot \left(
P\left( \overline{x}\right) \wedge \lnot P\left( \overline{x}\right) \right)
\vee P\left( \overline{x}\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\left( \overline{x}\right) \vee \lnot \lnot
P\left( \overline{x}\right) \right) \vee P\left( \overline{x}\right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \lnot P\left( \overline{x}\right) \vee P\left(
\overline{x}\right) \right) \vee P\left( \overline{x}\right) \quad \because
\text{二重否定} \\
&\Leftrightarrow &\top \vee P\left( \overline{x}\right) \quad \because \text{排中律} \\
&\Leftrightarrow &\top \quad \because \text{恒真式}\top
\text{の性質}
\end{eqnarray*}すなわち恒真式\(\top \)となります。任意の解釈のもとで同様の議論が成り立つため、\(\left( 1\right) \)が恒真式であることが明らかになりました。したがって、\(P\left( x\right) \)は\(P\left( x\right) \wedge \lnot P\left( x\right) \)であるための必要条件であり、逆に、\(P\left( x\right) \wedge \lnot P\left( x\right) \)は\(P\left( x\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)
\quad\cdots (1)
\end{equation}について考えます。解釈を任意に選んだ上で、そのときに\(P\left( x\right) \)から得られる命題を\(P\left( \overline{x}\right) \)で、\(Q\left( x\right) \)から得られる命題を\(Q\left( \overline{x}\right) \)で表記すると、\(\left( 1\right) \)から得られる命題は、\begin{equation*}
P\left( \overline{x}\right) \wedge Q\left( \overline{x}\right) \rightarrow
P\left( \overline{x}\right)
\end{equation*}となります。これを同値変形すると、\begin{eqnarray*}
P\left( \overline{x}\right) \wedge Q\left( \overline{x}\right) \rightarrow
P\left( \overline{x}\right) &\Leftrightarrow &\lnot \left( P\left(
\overline{x}\right) \wedge Q\left( \overline{x}\right) \right) \vee P\left(
\overline{x}\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\left( \overline{x}\right) \vee \lnot
Q\left( \overline{x}\right) \right) \vee P\left( \overline{x}\right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( P\left( \overline{x}\right) \vee \lnot P\left(
\overline{x}\right) \right) \vee \lnot Q\left( \overline{x}\right) \quad
\because \text{交換律と結合律} \\
&\Leftrightarrow &\top \vee \lnot Q\left( \overline{x}\right) \quad \because
\text{排中律} \\
&\Leftrightarrow &\top \quad \because \text{恒真式}\top
\text{の性質}
\end{eqnarray*}すなわち恒真式\(\top \)となります。任意の解釈のもとで同様の議論が成り立つため、\(\left( 1\right) \)が恒真式であることが明らかになりました。したがって、\(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) \)であるための十分条件です。
P\left( x\right) \wedge Q\left( x\right) \rightarrow P\left( x\right)
\quad\cdots (1)
\end{equation}について考えます。解釈を任意に選んだ上で、そのときに\(P\left( x\right) \)から得られる命題を\(P\left( \overline{x}\right) \)で、\(Q\left( x\right) \)から得られる命題を\(Q\left( \overline{x}\right) \)で表記すると、\(\left( 1\right) \)から得られる命題は、\begin{equation*}
P\left( \overline{x}\right) \wedge Q\left( \overline{x}\right) \rightarrow
P\left( \overline{x}\right)
\end{equation*}となります。これを同値変形すると、\begin{eqnarray*}
P\left( \overline{x}\right) \wedge Q\left( \overline{x}\right) \rightarrow
P\left( \overline{x}\right) &\Leftrightarrow &\lnot \left( P\left(
\overline{x}\right) \wedge Q\left( \overline{x}\right) \right) \vee P\left(
\overline{x}\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\left( \overline{x}\right) \vee \lnot
Q\left( \overline{x}\right) \right) \vee P\left( \overline{x}\right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( P\left( \overline{x}\right) \vee \lnot P\left(
\overline{x}\right) \right) \vee \lnot Q\left( \overline{x}\right) \quad
\because \text{交換律と結合律} \\
&\Leftrightarrow &\top \vee \lnot Q\left( \overline{x}\right) \quad \because
\text{排中律} \\
&\Leftrightarrow &\top \quad \because \text{恒真式}\top
\text{の性質}
\end{eqnarray*}すなわち恒真式\(\top \)となります。任意の解釈のもとで同様の議論が成り立つため、\(\left( 1\right) \)が恒真式であることが明らかになりました。したがって、\(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) \)であるための十分条件です。
例（必要条件と十分条件）
変数\(x\in X\)を持つ命題関数\(P\left( x\right) \)に関する以下の論理式\begin{equation}
P\left( x\right) \rightarrow \exists x\in X\ P\left( x\right) \quad\cdots (1)
\end{equation}について考えます。存在記号\(\exists \)の定義より、上の論理式は、\begin{equation}
P\left( x\right) \rightarrow \bigvee\limits_{x\in X}P\left( x\right)
\quad\cdots (2)
\end{equation}と言い換えられます。解釈を任意に選んだ上で、そのときに\(P\left( x\right) \)から得られる命題を\(P\left( \overline{x}\right) \)で表記すると、\(\left( 2\right) \)から得られる命題は、\begin{equation*}
P\left( \overline{x}\right) \rightarrow \bigvee\limits_{x\in X}P\left(
x\right)
\end{equation*}となります。これを同値変形すると、\begin{eqnarray*}
P\left( \overline{x}\right) \rightarrow \bigvee\limits_{x\in X}P\left(
x\right) &\Leftrightarrow &\lnot P\left( \overline{x}\right) \vee \left(
\bigvee\limits_{x\in X}P\left( x\right) \right) \quad \because \rightarrow
\text{の言い換え} \\
&\Leftrightarrow &\lnot P\left( \overline{x}\right) \vee \left( P\left(
\overline{x}\right) \vee \left( \bigvee\limits_{x\in X\backslash \left\{
\overline{x}\right\} }P\left( x\right) \right) \right) \quad \because
\overline{x}\in X \\
&\Leftrightarrow &\left( \lnot P\left( \overline{x}\right) \vee P\left(
\overline{x}\right) \right) \vee \left( \bigvee\limits_{x\in X\backslash
\left\{ \overline{x}\right\} }P\left( x\right) \right) \quad \because \text{結合律} \\
&\Leftrightarrow &\top \vee \left( \bigvee\limits_{x\in X\backslash \left\{
\overline{x}\right\} }P\left( x\right) \right) \quad \because \text{排中律} \\
&\Leftrightarrow &\top \quad \because \text{恒真式}\top
\text{の性質}
\end{eqnarray*}すなわち恒真式\(\top \)となります。任意の解釈のもとで同様の議論が成り立つため、\(\left( 2\right) \)や\(\left( 1\right) \)が恒真式であることが明らかになりました。したがって、\(\exists x\in X\ P\left( x\right) \)は\(P\left( x\right) \)であるための必要条件であり、逆に、\(P\left( x\right) \)は\(\exists x\in X\ P\left( x\right) \)であるための十分条件です。
P\left( x\right) \rightarrow \exists x\in X\ P\left( x\right) \quad\cdots (1)
\end{equation}について考えます。存在記号\(\exists \)の定義より、上の論理式は、\begin{equation}
P\left( x\right) \rightarrow \bigvee\limits_{x\in X}P\left( x\right)
\quad\cdots (2)
\end{equation}と言い換えられます。解釈を任意に選んだ上で、そのときに\(P\left( x\right) \)から得られる命題を\(P\left( \overline{x}\right) \)で表記すると、\(\left( 2\right) \)から得られる命題は、\begin{equation*}
P\left( \overline{x}\right) \rightarrow \bigvee\limits_{x\in X}P\left(
x\right)
\end{equation*}となります。これを同値変形すると、\begin{eqnarray*}
P\left( \overline{x}\right) \rightarrow \bigvee\limits_{x\in X}P\left(
x\right) &\Leftrightarrow &\lnot P\left( \overline{x}\right) \vee \left(
\bigvee\limits_{x\in X}P\left( x\right) \right) \quad \because \rightarrow
\text{の言い換え} \\
&\Leftrightarrow &\lnot P\left( \overline{x}\right) \vee \left( P\left(
\overline{x}\right) \vee \left( \bigvee\limits_{x\in X\backslash \left\{
\overline{x}\right\} }P\left( x\right) \right) \right) \quad \because
\overline{x}\in X \\
&\Leftrightarrow &\left( \lnot P\left( \overline{x}\right) \vee P\left(
\overline{x}\right) \right) \vee \left( \bigvee\limits_{x\in X\backslash
\left\{ \overline{x}\right\} }P\left( x\right) \right) \quad \because \text{結合律} \\
&\Leftrightarrow &\top \vee \left( \bigvee\limits_{x\in X\backslash \left\{
\overline{x}\right\} }P\left( x\right) \right) \quad \because \text{排中律} \\
&\Leftrightarrow &\top \quad \because \text{恒真式}\top
\text{の性質}
\end{eqnarray*}すなわち恒真式\(\top \)となります。任意の解釈のもとで同様の議論が成り立つため、\(\left( 2\right) \)や\(\left( 1\right) \)が恒真式であることが明らかになりました。したがって、\(\exists x\in X\ P\left( x\right) \)は\(P\left( x\right) \)であるための必要条件であり、逆に、\(P\left( x\right) \)は\(\exists x\in X\ P\left( x\right) \)であるための十分条件です。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】