WIIS

命題論理

命題論理における交換律

目次

Mailで保存
Xで共有

交換律

論理式\(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)と呼びます。

命題(交換律)
任意の論理式\(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,Q\)を任意に選んだとき、命題変数は論理式であるため、交換律より、\begin{align*}& \left( a\right) \ P\wedge Q\Leftrightarrow Q\wedge P \\
& \left( b\right) \ P\vee Q\Leftrightarrow Q\vee P
\end{align*}がともに成り立ちます。

例(交換律)
命題変数\(P,Q,R\)を任意に選んだとき、これらの含意\begin{eqnarray*}P &\rightarrow &Q \\
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*}がともに成り立ちます。

例(交換律)
命題変数\(P,Q,R\)を任意に選んだとき、\begin{eqnarray*}&&P\leftrightarrow Q \\
&&\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_{1},\cdots ,A_{n}\)の順番を自由に入れ替えても論理式の値は変わらない。また、有限\(n\)個の論理式\(A_{1},\cdots ,A_{n}\)の論理和が与えられた場合、その論理式において括弧が指定する順番で論理和を作用させる限りにおいて、論理式\(A_{1},\cdots ,A_{n}\)の順番を自由に入れ替えても論理式の値は変わらない。

証明

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

 

演習問題

問題(排他的論理和に関する交換律)
論理式\(A,B\)を任意に選んだとき、排他的論理和\(\veebar \)に関する交換律は、\begin{equation*}A\veebar B\Leftrightarrow B\veebar A
\end{equation*}と表現できますが、これは成り立つでしょうか。理由とともに答えてください。

解答を見る

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

問題(含意に関する交換律)
論理式\(A,B\)を任意に選んだとき、含意\(\rightarrow \)に関する交換律は、\begin{equation*}A\rightarrow B\Leftrightarrow B\rightarrow A
\end{equation*}と表現できますが、これは成り立つでしょうか。理由とともに答えてください。

解答を見る

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

問題(同等に関する交換律)
論理式\(A,B\)を任意に選んだとき、同等\(\leftrightarrow \)に関する交換律は、\begin{equation*}A\leftrightarrow B\Leftrightarrow B\leftrightarrow A
\end{equation*}と表現できますが、これは成り立つでしょうか。理由とともに答えてください。

解答を見る

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

問題(4つの論理式に関する交換律)
4つの論理式\(A,B,C,D\)に関する論理式\begin{equation*}\left( \left( A\wedge B\right) \wedge C\right) \wedge D
\end{equation*}が与えられているものとします。交換律を認める場合、どのような結論を導き出せるでしょうか。議論してください。

解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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