教材一覧
教材一覧
教材検索
PREDICATE LOGIC

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

目次

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

必要条件と十分条件

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

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

質問とコメント

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

RELATED KNOWLEDGE

関連知識

含意
命題論理における含意

含意 → は入力された論理式 A,B に対して、A と B の値がともに 1 である場合には 1 を値としてとり、A の値が 0 の場合には B の値によらず常に 1 を値としてとる論理式 A→B を出力する論理演算です。

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

論理式 A,B について A↔B が恒真式であるならば、すなわち、任意の解釈のもとで A↔B の値が 1 であるならば、A と B はお互いに一方が他方であるための必要十分条件であると言います。

述語論理