論理積と論理和の間には分配律と呼ばれる関係が成り立ちます。

2018年12月2日:公開

分配律

これまで見てきた論理演算の性質はいずれも否定、論理積、論理和などの論理演算がそれぞれ単独で満たす性質でしたが、以降では複数の異なる論理演算の間に成り立つ関係について考えます。

まず、論理積と論理和の間には以下の関係が成り立ちます。これを分配律(distributive law)と呼びます。

命題(分配律)
任意の論理式\(A,B,C\)に対して以下が成り立つ。\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*}
証明を見る(プレミアム会員限定)

分配律に加えて交換律を踏まえると、論理式\(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,D\)について、\begin{equation*}
\left( A\vee B\right) \wedge \left( C\vee D\right) \Leftrightarrow \left( A\wedge C\right) \vee \left( B\wedge C\right) \vee \left( A\wedge D\right) \vee \left( B\wedge D\right)
\end{equation*}が成り立つことを分配律から証明します。便宜的に、\begin{equation*}
E=A\vee B
\end{equation*}とおきます。すると、\begin{eqnarray*}
\left( A\vee B\right) \wedge \left( C\vee D\right) &\Leftrightarrow &E\wedge \left( C\vee D\right) \\
&\Leftrightarrow &\left( E\wedge C\right) \vee \left( E\wedge D\right) \quad \because \text{分配律} \\
&\Leftrightarrow &\left( \left( A\vee B\right) \wedge C\right) \vee \left( \left( A\vee B\right) \wedge D\right) \quad \because E=A\vee B \\
&\Leftrightarrow &\left( A\wedge C\right) \vee \left( B\wedge C\right) \vee \left( A\wedge D\right) \vee \left( B\wedge D\right) \quad \because \text{分配律}
\end{eqnarray*}が成り立つため証明できました。

次回は吸収律について学びます。

次へ進む 演習問題(プレミアム会員限定)

ワイズをさらに活用するための会員サービス

ユーザー名とメールアドレスを入力して一般会員に無料登録すれば、質問やコメントを投稿できるようになります。さらに、有料(500円/月)のプレミアム会員へアップグレードすることにより、プレミアムコンテンツ(命題の証明や演習問題、解答など)にアクセスできます。
会員サービス

ディスカッションに参加しますか?

質問やコメントを投稿するにはログインが必要です。
ログイン

現在地
目次
アカウント
ログイン