分配律
これまで見てきた論理演算の性質はいずれも否定、論理積、論理和などの論理演算がそれぞれ単独で満たす性質でしたが、以降では複数の異なる論理演算の間に成り立つ関係について考えます。
論理式\(A,B,C\)を任意に選んだとき、以下の真理値表が得られます。
$$\begin{array}{ccccc}
\hline
A & B & C & A\wedge (B\vee C) & (A\wedge B)\vee (A\wedge C) \\
\hline
1 & 1 & 1 & 1 & 1 \\ \hline
1 & 1 & 0 & 1 & 1 \\ \hline
1 & 0 & 1 & 1 & 1 \\ \hline
1 & 0 & 0 & 0 & 0 \\ \hline
0 & 1 & 1 & 0 & 0 \\ \hline
0 & 1 & 0 & 0 & 0 \\ \hline
0 & 0 & 1 & 0 & 0 \\ \hline
0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$
つまり、任意の解釈のもとで\(A\wedge (B\vee C)\)と\((A\wedge B)\vee (A\wedge C)\)の値は一致するため、\begin{equation*}
\left( a\right) \ A\wedge (B\vee C)\Leftrightarrow (A\wedge B)\vee (A\wedge
C)
\end{equation*}が成り立ちます。\(\left( a\right) \)において\(\wedge \)と\(\vee \)を置き換えると、\begin{equation*}
\left( b\right) \ A\vee (B\wedge C)\Leftrightarrow (A\vee B)\wedge (A\vee C)
\end{equation*}を得ますが、これが成り立つことも同様にして示されます(演習問題にします)。論理積と論理和の間に成立するこのような性質を分配律(distributive law)と呼びます。
& \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*}
P\wedge \left( Q\vee P\right) &\Leftrightarrow &\left( P\wedge Q\right)
\vee \left( P\wedge P\right) \quad \because \text{分配律}
\\
&\Leftrightarrow &\left( P\wedge Q\right) \vee P\quad \because \text{ベキ等律} \\
&\Leftrightarrow &P\vee \left( Q\wedge P\right) \quad \because \text{交換律}
\end{eqnarray*}が成り立ちます。つまり、\(P\wedge \left( Q\vee P\right) \)において\(\wedge \)と\(\vee \)を入れ替えると新たな論理式\(P\vee \left( Q\wedge P\right) \)を得られますが、これらは論理的に同値です。
\left( P\vee Q\right) \wedge \left( R\vee S\right) \Leftrightarrow \left(
P\wedge R\right) \vee \left( P\wedge S\right) \vee \left( Q\wedge R\right)
\vee \left( Q\wedge S\right)
\end{equation*}が成り立つことを証明します。便宜的に、\begin{equation*}
A=P\vee Q
\end{equation*}とおきます。すると、\begin{eqnarray*}
\left( P\vee Q\right) \wedge \left( R\vee S\right) &\Leftrightarrow
&A\wedge \left( R\vee S\right) \quad \because A=P\vee Q \\
&\Leftrightarrow &\left( A\wedge R\right) \vee \left( A\wedge S\right) \quad
\because \text{分配律} \\
&\Leftrightarrow &\left( \left( P\vee Q\right) \wedge R\right) \vee \left(
\left( P\vee Q\right) \wedge S\right) \quad \because A=P\vee Q \\
&\Leftrightarrow &\left( R\wedge \left( P\vee Q\right) \right) \vee \left(
S\wedge \left( P\vee Q\right) \right) \quad \because \text{交換律} \\
&\Leftrightarrow &\left( P\wedge R\right) \vee \left( P\wedge S\right) \vee
\left( Q\wedge R\right) \vee \left( Q\wedge S\right) \quad \because \text{分配律}
\end{eqnarray*}が成り立つため証明できました。
後ろからの分配
分配律に加えて交換律を踏まえると、任意の論理式\(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*}
次回は吸収律について学びます。
質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定) 次へ進む
プレミアム会員だけが質問やコメントを投稿・閲覧できます。