交換律
論理式\(A,B\)を任意に選んだとき、論理積\(\wedge \)と論理和\(\vee \)に関して以下の恒真式\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）と呼びます。
& \left( b\right) \ A\vee B\Leftrightarrow B\vee A
\end{align*}が成り立つ。
& \left( b\right) \ P\vee Q\Leftrightarrow Q\vee P
\end{align*}がともに成り立ちます。
Q &\rightarrow &R
\end{eqnarray*}はともに論理式であるため、交換律より、\begin{align*}
& \left( a\right) \ \left( P\rightarrow Q\right) \wedge \left( Q\rightarrow
R\right) \Leftrightarrow \left( Q\rightarrow R\right) \wedge \left(
P\rightarrow Q\right) \\
& \left( b\right) \ \left( P\rightarrow Q\right) \vee \left( Q\rightarrow
R\right) \Leftrightarrow \left( Q\rightarrow R\right) \vee \left(
P\rightarrow Q\right)
\end{align*}がともに成り立ちます。
&&\lnot R
\end{eqnarray*}はともに論理式であるため、交換律より、\begin{align*}
& \left( a\right) \ \left( P\leftrightarrow Q\right) \wedge \lnot
R\Leftrightarrow \lnot R\wedge \left( P\leftrightarrow Q\right) \\
& \left( b\right) \ \left( P\leftrightarrow Q\right) \vee \lnot
R\Leftrightarrow \lnot R\vee \left( P\leftrightarrow Q\right)
\end{align*}がともに成り立ちます。
交換律の一般化
3つの論理式\(A,B,C\)が任意に与えられたとき、\(\wedge \)に関する交換律を繰り返し適用することにより、\begin{eqnarray*}\left( A\wedge B\right) \wedge C &\Leftrightarrow &\left( B\wedge A\right)
\wedge C\quad \because \text{交換律} \\
&\Leftrightarrow &C\wedge \left( B\wedge A\right) \quad \because \text{交換律} \\
&\Leftrightarrow &C\wedge \left( A\wedge B\right) \quad \because \text{交換律}
\end{eqnarray*}を得ます。つまり、3つの論理式\(A,B,C\)の論理積をとる場合、括弧が指定するように、\(A\)と\(B\)に優先的に論理積を作用させる形で同値変形を行う限りにおいて、論理式の順序を自由に入れ替えても論理式の値は変わりません。同様に、\begin{eqnarray*}A\wedge \left( B\wedge C\right) &\Leftrightarrow &A\wedge \left( C\wedge
B\right) \quad \because \text{交換律} \\
&\Leftrightarrow &\left( C\wedge B\right) \wedge A\quad \because \text{交換律} \\
&\Leftrightarrow &\left( B\wedge C\right) \wedge A\quad \because \text{交換律}
\end{eqnarray*}を得ます。つまり、3つの論理式\(A,B,C\)の論理積をとる場合、括弧が指定するように、\(B\)と\(C\)に優先的に論理積を作用させる形で同値変形を行う限りにおいて、論理式の順序を自由に入れ替えても論理式の値は変わりません。ちなみに、後ほど示す結合律と呼ばれる性質を踏まえると、\begin{equation*}\left( A\wedge B\right) \wedge C\Leftrightarrow A\wedge \left( B\wedge
C\right)
\end{equation*}を得るため、以上の8つの論理式がすべて論理的に同値であることもまた保証されます。
論理和についても同様に考えます。また、4つ以上の論理式についても同様に考えます。
有限\(n\)個の論理式\(A_{1},\cdots,A_{n}\)の論理積\(A\)が与えられているものとする。このとき、その論理式\(A\)に含まれる\(n-1\)個の論理積演算子\(\wedge \)のそれぞれについて、左右の論理式を交換するかどうかを任意に選んで得られる\(2^{n-1}\)通りの論理式はいずれも、もとの論理式\(A\)と論理的に同値である。また、論理和についても同様の主張が成り立つ。
\end{equation*}が与えられているものとします。この論理式の中には3個の演算子\(\wedge \)のそれぞれについて、左右の論理式を交換するかどうかを任意に選んで得られる\(2^{3}=8\)通りの論理式は以下の通りです。ただし、\(○ \)は該当する\(\wedge \)の左右を入れ替えることを意味し、\(\times \)は入れ替えないことを意味します。
$$\begin{array}{cccc}
\hline
内側 & 中央 & 外側 & 論理式 \\ \hline
\times & \times & \times & \left( \left( A\wedge B\right) \wedge C\right) \wedge D \\ \hline
○ & \times & \times & \left( \left( B\wedge A\right) \wedge C\right) \wedge D \\ \hline
\times & ○ & \times & \left( C\wedge \left( A\wedge B\right) \right) \wedge D \\ \hline
\times & \times & ○ & D\wedge \left( \left( A\wedge B\right) \wedge C\right) \\ \hline
○ & ○ & \times & \left( C\wedge \left( B\wedge A\right) \right) \wedge D \\ \hline
○ & \times & ○ & D\wedge \left( \left( B\wedge A\right) \wedge C\right) \\ \hline
\times & ○ & ○ & D\wedge \left( C\wedge \left( A\wedge B\right) \right) \\ \hline
○ & ○ & ○ & D\wedge \left( C\wedge \left( B\wedge A\right) \right) \\ \hline
\end{array}$$
先の命題より、これらの論理式は同値です。
演習問題
\end{equation*}と表現できますが、これは成り立つでしょうか。理由とともに答えてください。
\end{equation*}と表現できますが、これは成り立つでしょうか。理由とともに答えてください。
\end{equation*}と表現できますが、これは成り立つでしょうか。理由とともに答えてください。
\end{equation*}が与えられているものとします。交換律を認める場合、どのような結論を導き出せるでしょうか。議論してください。
ログイン
会員向けコンテンツです。
まだ会員登録がお済みでない方は、会員登録ページよりアカウントを作成してください。