WIIS

述語論理

述語論理における必要条件と十分条件

目次

Mailで保存
Xで共有

必要条件と十分条件

論理式\(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) \)であるための十分条件です。
例(必要条件と十分条件)
変数\(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) \)であるための十分条件です。
例(必要条件と十分条件)
変数\(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) \)であるための十分条件です。
次回は必要十分条件について学びます。

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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