WIIS

述語論理

述語論理における交換律

目次

Mailで保存
Xで共有

交換律

論理式\(A,B\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)でそれぞれ表記します。すると命題論理における交換律より、\begin{align*}& \left( a\right) \ \overline{A}\wedge \overline{B}\Leftrightarrow \overline{B}\wedge \overline{A} \\
& \left( b\right) \ \overline{A}\vee \overline{B}\Leftrightarrow \overline{B}\vee \overline{A}
\end{align*}を得ます。任意の解釈において同様の議論が成立するため、\begin{align*}
& \left( a\right) \ A\wedge B\Leftrightarrow B\wedge A \\
& \left( b\right) \ A\vee B\Leftrightarrow B\vee A
\end{align*}がともに成り立つことが示されました。つまり、述語論理においても論理積や論理和について交換律(commutative law)が成り立つということです。

命題(交換律)
任意の論理式\(A,B\)に対して、\begin{align*}& \left( a\right) \ A\wedge B\Leftrightarrow B\wedge A \\
& \left( b\right) \ A\vee B\Leftrightarrow B\vee A
\end{align*}が成り立つ。

例(交換律)
命題関数\(P\left( x\right) ,Q\left( x\right) \)をそれぞれ任意に選んだとき、交換律より、\begin{eqnarray*}P\left( x\right) \wedge Q\left( x\right) &\Leftrightarrow &Q\left( x\right)
\wedge P\left( x\right) \\
P\left( x\right) \vee Q\left( x\right) &\Leftrightarrow &Q\left( x\right)
\vee P\left( x\right)
\end{eqnarray*}がともに成り立ちます。

例(交換律)
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)と\(R\left( x\right) \)をそれぞれ任意に選んだとき、\begin{eqnarray*}P\left( x\right) \vee \left( Q\left( x\right) \vee R\left( x\right) \right)
&\Leftrightarrow &P\left( x\right) \vee \left( R\left( x\right) \vee Q\left(
x\right) \right) \quad \because \text{交換律} \\
&\Leftrightarrow &\left( R\left( x\right) \vee Q\left( x\right) \right) \vee
P\left( x\right) \quad \because \text{交換律} \\
&\Leftrightarrow &\left( Q\left( x\right) \vee R\left( x\right) \right) \vee
P\left( x\right) \quad \because \text{交換律}
\end{eqnarray*}などが成り立ちます。

例(交換律)
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)と\(R\left( x\right) \)をそれぞれ任意に選んだとき、\begin{eqnarray*}P\left( x\right) \wedge \left( Q\left( x\right) \vee R\left( x\right)
\right) &\Leftrightarrow &P\left( x\right) \wedge \left( R\left( x\right)
\vee Q\left( x\right) \right) \quad \because \text{交換律}
\\
&\Leftrightarrow &\left( R\left( x\right) \vee Q\left( x\right) \right)
\wedge P\left( x\right) \quad \because \text{交換律} \\
&\Leftrightarrow &\left( Q\left( x\right) \vee R\left( x\right) \right)
\wedge P\left( x\right) \quad \because \text{交換律}
\end{eqnarray*}などが成り立ちます。

例(交換律)
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)をそれぞれ任意に選んだとき、交換律より、\begin{equation*}\left( \forall x\in X:P\left( x\right) \right) \wedge \left( \exists x\in
X:Q\left( x\right) \right) \Leftrightarrow \left( \exists x\in X:Q\left(
x\right) \right) \wedge \left( \forall x\in X:P\left( x\right) \right)
\end{equation*}が成り立ちます。

例(交換律)
変数\(x\)の定義域\(X\)はすべての整数からなる集合であるものとします。論理式\begin{equation*}x\text{は偶数であり、なおかつ}y\text{は奇数である}
\end{equation*}が与えられたとき、交換律より、これは以下の論理式\begin{equation*}
y\text{は奇数であり、なおかつ}x\text{は偶数である}
\end{equation*}と論理的に同値です。

 

量化と交換律

交換律を踏まえると、全称命題や存在命題に関して以下が成り立ちます。

命題(量化と交換律)
任意の論理式\(A,B\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( A\wedge B\right) \Leftrightarrow
\forall x\in X:\left( B\wedge A\right) \\
&&\left( b\right) \ \forall x\in X:\left( A\vee B\right) \Leftrightarrow
\forall x\in X:\left( B\vee A\right) \\
&&\left( c\right) \ \exists x\in X:\left( A\wedge B\right) \Leftrightarrow
\exists x\in X:\left( B\wedge A\right) \\
&&\left( d\right) \ \exists x\in X:\left( A\vee B\right) \Leftrightarrow
\exists x\in X:\left( B\vee A\right)
\end{eqnarray*}が成り立つ。

証明

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

例(量化と交換律)
命題関数\(P\left( x\right) ,Q\left( x\right) \)をそれぞれ任意に選んだとき、交換律より、\begin{eqnarray*}\forall x &\in &X:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Leftrightarrow \forall x\in X:\left( Q\left( x\right) \wedge P\left(
x\right) \right) \\
\forall x &\in &X:\left( P\left( x\right) \vee Q\left( x\right) \right)
\Leftrightarrow \forall x\in X:\left( Q\left( x\right) \vee P\left( x\right)
\right) \\
\exists x &\in &X:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Leftrightarrow \exists x\in X:\left( Q\left( x\right) \wedge P\left(
x\right) \right) \\
\exists x &\in &X:\left( P\left( x\right) \vee Q\left( x\right) \right)
\Leftrightarrow \exists x\in X:\left( Q\left( x\right) \vee P\left( x\right)
\right)
\end{eqnarray*}がいずれも成り立ちます。

例(量化と交換律)
「任意の整数は奇数または偶数である」という主張を論理式として表現すると、\begin{equation*}
\forall x\in \mathbb{Z} :\left( x\text{は奇数}\vee x\text{は偶数}\right)
\end{equation*}となります。ただし、\(\mathbb{Z} \)はすべての整数からなる集合です。交換律より、これは、\begin{equation*}\forall x\in \mathbb{Z} :\left( x\text{は偶数}\vee 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*}がともに成り立つことが示されます。つまり、全称記号どうしは入れ替え可能であり、存在記号どうしは入れ替え可能です。

命題(量化と交換律)
任意の論理式\(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*}が成り立つ。

証明

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

例(量化と交換律)
命題関数\(P\left( x,y\right) \)を任意に選んだとき、先の命題より、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X,\ \forall y\in Y:P\left( x,y\right)
\Leftrightarrow \forall y\in Y,\ \forall x\in X:P\left( x,y\right) \\
&&\left( b\right) \ \exists x\in X,\ \exists y\in Y:P\left( x,y\right)
\Leftrightarrow \exists y\in Y,\ \exists x\in X:P\left( x,y\right)
\end{eqnarray*}がともに成り立ちます。

例(量化と交換律)
すべての実数からなる集合\(\mathbb{R} \)を定義域とする変数\(x,y\)に関する以下の2つの命題\begin{eqnarray*}\left( a\right) \ \forall x &\in &\mathbb{R} \ \forall y\in \mathbb{R} :x<y \\
\left( b\right) \ \forall y &\in &\mathbb{R} ,\ \forall x\in \mathbb{R} :x<y
\end{eqnarray*}に注目します。\(\left( a\right) \)は「実数\(x\)を任意に選んだとき、それに対して任意の実数\(y\)は\(x<y\)を満たす」という主張であり、\(\left( b\right) \)は「実数\(y\)を任意に選んだとき、それに対して任意の実数\(x\)は\(x<y\)を満たす」という主張です。先の命題より\(\left(a\right) \)と\(\left( b\right) \)は論理的に同値です。ちなみに、\(\left( x,y\right) =\left( 2,1\right) \)に注目すると\(\left( a\right) \)より\(2<1\)を得ますが、これは偽です。したがって\(\left(a\right) \)は偽であり、\(\left( x,y\right)=\left( 2,1\right) \)は反例になっています。\(\left( a\right) \)と論理的に同値な\(\left( b\right) \)も偽です。

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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