必要条件と十分条件

論理式 A,B に関する含意 A→B が恒真式であるとき、つまり、任意の解釈において A→B から得られる命題が真であるならば、B は A であるための必要条件であると言い、A は B であるための必要条件であると言います。
次のページ >

必要条件と十分条件

論理式\(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)
\tag{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)
\tag{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) \tag{1}
\end{equation}について考えます。存在記号\(\exists \)の定義より、上の論理式は、\begin{equation}
P\left( x\right) \rightarrow \bigvee\limits_{x\in X}P\left( x\right)
\tag{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) \)であるための十分条件です。
次回は必要十分条件について学びます。 次へ進む 質問・コメント(プレミアム会員限定 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
次のページ >

プレミアム会員サービス

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

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

述語論理
アカウント
ログイン