分配律
論理式\(A,B,C\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)で、\(C\)から得られる命題を\(\overline{C}\)でそれぞれ表記します。すると命題論理における\(\wedge \)と\(\vee \)に関する分配律より、\begin{eqnarray*}&&\left( a\right) \ \overline{A}\wedge (\overline{B}\vee \overline{C})\Leftrightarrow (\overline{A}\wedge \overline{B})\vee (\overline{A}\wedge
\overline{C}) \\
&&\left( b\right) \ \overline{A}\vee (\overline{B}\wedge \overline{C})\Leftrightarrow (\overline{A}\vee \overline{B})\wedge (\overline{A}\vee
\overline{C})
\end{eqnarray*}が成り立ちます。任意の解釈において同様の議論が成立するため、\begin{align*}
& \left( a\right) \ A\wedge (B\vee C)\Leftrightarrow (A\wedge B)\vee
(A\wedge C) \\
& \left( b\right) \ A\vee (B\wedge C)\Leftrightarrow (A\vee B)\wedge (A\vee
C)
\end{align*}が成り立つことが示されました。つまり、述語論理においても論理積と論理和の間に分配律（distributive law）が成り立つということです。
(A\wedge C) \\
& \left( b\right) \ A\vee (B\wedge C)\Leftrightarrow (A\vee B)\wedge (A\vee
C)
\end{align*}が成り立つ。
\right) \Leftrightarrow \left( P\left( x\right) \wedge Q\left( x,y\right)
\right) \vee \left( P\left( x\right) \wedge R\left( y\right) \right)
\end{equation*}が成り立ちます。
\right) &\Leftrightarrow &\left( P\left( x\right) \wedge Q\left( x,y\right)
\right) \vee \left( P\left( x\right) \wedge P\left( x\right) \right) \quad
\because \text{分配律} \\
&\Leftrightarrow &\left( P\left( x\right) \wedge Q\left( x,y\right) \right)
\vee P\left( x\right) \quad \because \text{ベキ等律}
\\
&\Leftrightarrow &P\left( x\right) \vee \left( Q\left( x,y\right) \wedge
P\left( x\right) \right) \quad \because \text{交換律}
\end{eqnarray*}が成り立ちます。つまり、\(P\left( x\right) \wedge \left( Q\left( x,y\right)\vee P\left( x\right) \right) \)において\(\wedge \)と\(\vee \)を入れ替えると新たな論理式\(P\left( x\right) \vee\left( Q\left( x,y\right) \wedge P\left( x\right) \right) \)を得られますが、これらは論理的に同値です。
後ろからの分配
分配律に加えて交換律を踏まえると、任意の論理式\(A,B,C\)に対して、\begin{align*}\left( A\vee B\right) \wedge C& \Leftrightarrow C\wedge \left( A\vee
B\right) \quad \because \text{交換律} \\
& \Leftrightarrow \left( C\wedge A\right) \vee \left( C\wedge B\right) \quad
\because \text{分配律} \\
& \Leftrightarrow \left( A\wedge C\right) \vee \left( B\wedge C\right) \quad
\because \text{交換律}
\end{align*}が成り立ちます。つまり、\begin{equation*}
\left( A\vee B\right) \wedge C\Leftrightarrow \left( A\wedge C\right) \vee
\left( B\wedge C\right)
\end{equation*}という形で、後ろからの分配が可能になります。同様に、\begin{equation*}
\left( A\wedge B\right) \vee C\Leftrightarrow \left( A\vee C\right) \wedge
\left( B\vee C\right)
\end{equation*}もまた成り立ちます。
任意の論理式\(A,B,C\)に対して、\begin{align*}& \left( a\right) \ \left( A\vee B\right) \wedge C\Leftrightarrow \left(
A\wedge C\right) \vee \left( B\wedge C\right) \\
& \left( b\right) \ \left( A\wedge B\right) \vee C\Leftrightarrow \left(
A\vee C\right) \wedge \left( B\vee C\right)
\end{align*}が成り立つ。
量化と分配律
分配律を踏まえると、全称命題や存在命題に関して以下が成り立ちます。
\right) \Leftrightarrow \forall x\in X:\left( \left( A\wedge B\right) \vee
\left( A\wedge C\right) \right) \\
&&\left( b\right) \ \forall x\in X:\left( A\vee \left( B\wedge C\right)
\right) \Leftrightarrow \forall x\in X:\left( \left( A\wedge B\right) \wedge
\left( A\vee C\right) \right) \\
&&\left( c\right) \ \exists x\in X:\left( A\wedge \left( B\vee C\right)
\right) \Leftrightarrow \exists x\in X:\left( \left( A\wedge B\right) \vee
\left( A\wedge C\right) \right) \\
&&\left( d\right) \ \exists x\in X:\left( A\vee \left( B\wedge C\right)
\right) \Leftrightarrow \exists x\in X:\left( \left( A\wedge B\right) \wedge
\left( A\vee C\right) \right)
\end{eqnarray*}が成り立つ。
復習になりますが、論理式\(A,B\)と変数\(x\in X\)をそれぞれ任意に選んだときに、\begin{eqnarray*}&&\left( a_{1}\right) \ \forall x\in X:\left( A\wedge B\right)
\Leftrightarrow \left( \forall x\in X:A\right) \wedge \left( \forall x\in
X:B\right) \\
&&\left( b_{1}\right) \ \exists x\in X:\left( A\vee B\right) \Leftrightarrow
\left( \exists x\in X:A\right) \vee \left( \exists x\in X:B\right)
\end{eqnarray*}がともに成り立つことが結合律より導かれます。上の主張において全称記号\(\forall \)と存在記号\(\exists \)を入れ替えると、\begin{eqnarray*}&&\left( a_{2}\right) \ \exists x\in X:\left( A\wedge B\right)
\Leftrightarrow \left( \exists x\in X:A\right) \wedge \left( \exists x\in
X:B\right) \\
&&\left( b_{2}\right) \ \forall x\in X:\left( A\vee B\right) \Leftrightarrow
\left( \forall x\in X:A\right) \vee \left( \forall x\in X:B\right)
\end{eqnarray*}となりますが、これらもまた成り立つでしょうか。\(\left( a_{2}\right) \)に関しては\(\Rightarrow \)が、\(\left(b_{2}\right) \)に関しては\(\Leftarrow \)が成り立つことは分配律から導かれます。
\left( \exists x\in X:A\right) \wedge \left( \exists x\in X:B\right) \\
&&\left( b\right) \ \left( \forall x\in X:A\right) \vee \left( \forall x\in
X:B\right) \Rightarrow \forall x\in X:\left( A\vee B\right)
\end{eqnarray*}が成り立つ。
x\right) \right) \Rightarrow \left( \exists x\in X:P\left( x\right) \right)
\wedge \left( \exists x\in X:Q\left( x\right) \right) \\
&&\left( b\right) \ \left( \forall x\in X:P\left( x\right) \right) \vee
\left( \forall x\in X:Q\left( x\right) \right) \Rightarrow \forall x\in
X:\left( P\left( x\right) \vee Q\left( x\right) \right)
\end{eqnarray*}などが成り立ちます。
x,y\right) \right) \Rightarrow \left( \exists x\in X:P\left( x,y\right)
\right) \wedge \left( \exists x\in X:Q\left( x,y\right) \right) \\
&&\left( b\right) \ \exists y\in Y:\left( P\left( x,y\right) \wedge Q\left(
x,y\right) \right) \Rightarrow \left( \exists y\in Y:P\left( x,y\right)
\right) \wedge \left( \exists x\in X:Q\left( x,y\right) \right) \\
&&\left( c\right) \ \left( \forall x\in X:P\left( x,y\right) \right) \vee
\left( \forall x\in X:Q\left( x,y\right) \right) \Rightarrow \forall x\in
X:\left( P\left( x,y\right) \vee Q\left( x,y\right) \right) \\
&&\left( d\right) \ \left( \forall y\in Y:P\left( x,y\right) \right) \vee
\left( \forall x\in X:Q\left( x,y\right) \right) \Rightarrow \forall y\in
Y:\left( P\left( x,y\right) \vee Q\left( x,y\right) \right)
\end{eqnarray*}などが成り立ちます。
\Rightarrow \left( \exists y\in Y:P\left( x\right) \right) \wedge \left(
\exists y\in Y:Q\left( x\right) \right)
\end{equation*}がともに成り立つはずです。実際、存在命題の定義より、\begin{eqnarray}
\exists y &\in &Y:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Leftrightarrow P\left( x\right) \wedge Q\left( x\right) \quad \cdots (1) \\
\exists y &\in &Y:P\left( x\right) \Leftrightarrow P\left( x\right)
\quad \cdots (2) \\
\exists y &\in &Y:Q\left( x\right) \Leftrightarrow Q\left( x\right)
\quad \cdots (3)
\end{eqnarray}がいずれも成り立つことを踏まえると、\begin{eqnarray*}
\exists y\in Y:\left( P\left( x\right) \wedge Q\left( x\right) \right)
&\Leftrightarrow &P\left( x\right) \wedge Q\left( x\right) \quad \because
\left( 1\right) \\
&\Leftrightarrow &\left( \exists y\in Y:P\left( x\right) \right) \wedge
\left( \exists y\in Y:Q\left( x\right) \right) \quad \because \left(
2\right) ,\left( 3\right)
\end{eqnarray*}となるため証明が完了しました。
\end{equation*}となりますが、これは真です。実際、例えば実数\(2\)は条件を満たします。すると先の命題より、このとき、\begin{equation*}\left( \exists x\in \mathbb{R} :x^{2}\not=-1\right) \wedge \left( \exists x\in \mathbb{R} :x^{2}\geq 0\right)
\end{equation*}もまた真です。つまり、\(x^{2}\not=-1\)を満たす実数\(x\)と\(x^{2}\geq 0\)を満たす実数\(x\)がともに存在するということです。
\end{equation*}となりますが、これは真です。実際、任意の実数\(x\)について\(x^{2}\geq 0\)が成り立つからです。すると先の命題より、このとき、\begin{equation*}\forall x\in \mathbb{R} :\left( x^{2}\geq 0\vee x^{3}\geq 0\right)
\end{equation*}もまた真です。つまり、任意の実数\(x\)について\(x^{2}\geq 0\)と\(x^{3}\geq 0\)の少なくとも一方が成り立つということです。
先の命題の逆は成り立つとは限りません。つまり、論理式\(A,B\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \left( \exists x\in X:A\right) \wedge \left( \exists
x\in X:B\right) \Rightarrow \exists x\in X:\left( A\wedge B\right) \\
&&\left( b\right) \ \forall x\in X:\left( A\vee B\right) \Rightarrow \left(
\forall x\in X:A\right) \vee \left( \forall x\in X:B\right)
\end{eqnarray*}はいずれも成り立つとは限りません。以下の例より明らかです。
&&\left( a\right) \ \exists x\in \mathbb{Z} :x\text{は偶数} \\
&&\left( b\right) \ \exists x\in \mathbb{Z} :x\text{は奇数}
\end{eqnarray*}について考えます。ただし、\(\mathbb{Z} \)はすべての整数からなる集合です。つまり、\(\left( a\right) \)は偶数であるような整数が存在するという主張であり、\(\left( b\right) \)は奇数であるような整数が存在するという主張です。\(\left( a\right) \)と\(\left( b\right) \)は明らかに真であるため、以下の主張\begin{equation*}\left( \exists x\in \mathbb{Z} :x\text{は偶数}\right) \wedge \left( \exists x\in \mathbb{Z} :x\text{は奇数}\right)
\end{equation*}もまた真です。その一方で、以下の主張\begin{equation*}
\left( c\right) \ \exists x\in \mathbb{Z} :x\text{は偶数かつ奇数}
\end{equation*}は偽です。なぜなら、偶数かつ奇数であるような整数は存在しないからです。
\left( a\right) \ \forall x\in \mathbb{Z} :x\text{は偶数または奇数}
\end{equation*}について考えます。ただし、\(\mathbb{Z} \)はすべての整数からなる集合です。つまり、\(\left( a\right) \)は任意の整数は偶数または奇数であるという主張であり、これは真です。その一方で、以下の主張\begin{eqnarray*}&&\left( b\right) \ \forall x\in \mathbb{Z} :x\text{は偶数} \\
&&\left( c\right) \ \forall x\in \mathbb{Z} :x\text{は奇数}
\end{eqnarray*}はともに偽であるため、以下の主張\begin{equation*}
\left( \forall x\in \mathbb{Z} :x\text{は偶数}\right) \vee \left( \forall x\in \mathbb{Z} :x\text{は奇数}\right)
\end{equation*}もまた偽です。
全称記号と存在記号の置換
復習になりますが、論理式\(A\)と変数\(x\in X\)および\(y\in Y\)をそれぞれ任意に選んだときに、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X,\ \forall y\in Y:A\Leftrightarrow \forall
y\in Y,\ \forall x\in X:A \\
&&\left( b\right) \ \exists x\in X,\ \exists y\in Y:A\Leftrightarrow \exists
y\in Y,\ \exists x\in X:A
\end{eqnarray*}がともに成り立つことが交換律より導かれます。つまり、同じ種類の量化記号どうしは入れ替え可能であるということです。では、異なる種類の量化記号どうしの入れ替えは可能でしょうか。つまり、\begin{equation*}
\forall x\in X,\ \exists y\in Y:A\Leftrightarrow \exists y\in Y,\ \forall
x\in X:A
\end{equation*}という関係もまた成り立つのでしょうか。\(\Leftarrow \)が成り立つことは分配律から導かれます。
Y:A
\end{equation*}が成り立つ。
X,\ \exists y\in Y:P\left( x,y\right)
\end{equation*}が成り立ちます。
先の命題の逆は成り立つとは限りません。つまり、論理式\(A\)と変数\(x\in X\)および\(y\in Y\)に対して、\begin{equation*}\forall x\in X,\ \exists y\in Y:A\Rightarrow \exists y\in Y,\ \forall x\in
X:A
\end{equation*}は成り立つとは限りません。以下の例より明らかです。
&&\left( a\right) \ \forall x\in \mathbb{N} ,\ \exists y\in \mathbb{N} :x<y \\
&&\left( b\right) \ \exists x\in \mathbb{N} ,\ \forall y\in \mathbb{N} :x<y
\end{eqnarray*}について考えます。ただし、\(\mathbb{N} \)はすべての自然数からなる集合です。つまり、\(\left( a\right) \)は任意の自然数よりも大きい自然数が存在するという主張であり、\(\left(b\right) \)はある自然数が任意の自然数よりも小さいという主張です。\(\left( a\right) \)は真である一方で\(\left( b\right) \)は偽です。実際、自然数\(1\)よりも小さい自然数は存在しないからです。したがって、含意の定義より、\begin{equation*}\left( a\right) \Rightarrow \left( b\right)
\end{equation*}すなわち、\begin{equation*}
\forall x\in \mathbb{N} ,\ \exists y\in \mathbb{N} :x<y\Rightarrow \exists x\in \mathbb{N} ,\ \forall y\in \mathbb{N} :x<y
\end{equation*}は偽です。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】