分配律
論理式\(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*}が成り立ちます。論理積と論理和の間に成立する以上の性質を分配律（distributive law）と呼びます。
論理式\(A\)が与えられたとき、それと論理和\(B\vee C\)との論理積をとる場合には、\(B,C\)それぞれとの論理積をとった上で、得られた論理式どうしの論理和をとってもよいことを\(\left( a\right) \)は保証します。逆もまた成立します。
論理式\(A\)が与えられたとき、それと論理積\(B\wedge C\)との論理和をとる場合には、\(B,C\)それぞれとの論理和をとった上で、得られた論理式どうしの論理積をとってもよいことを\(\left( b\right) \)は保証します。逆もまた成立します。
(A\wedge C) \\
& \left( b\right) \ A\vee (B\wedge C)\Leftrightarrow (A\vee B)\wedge (A\vee
C)
\end{align*}が成り立つ。
(P\wedge R) \\
& \left( b\right) \ P\vee (Q\wedge R)\Leftrightarrow (P\vee Q)\wedge (P\vee
R)
\end{align*}がともに成り立ちます。
Q &\rightarrow &R \\
R &\rightarrow &S
\end{eqnarray*}はいずれも論理式であるため、分配律より、\begin{align*}
& \left( a\right) \ \left( P\rightarrow Q\right) \wedge (\left( Q\rightarrow
R\right) \vee \left( R\rightarrow S\right) )\Leftrightarrow (\left(
P\rightarrow Q\right) \wedge \left( Q\rightarrow R\right) )\vee (\left(
P\rightarrow Q\right) \wedge \left( R\rightarrow S\right) ) \\
& \left( b\right) \ \left( P\rightarrow Q\right) \vee (\left( Q\rightarrow
R\right) \wedge \left( R\rightarrow S\right) )\Leftrightarrow (\left(
P\rightarrow Q\right) \vee \left( Q\rightarrow R\right) )\wedge (\left(
P\rightarrow Q\right) \vee \left( R\rightarrow S\right) )
\end{align*}がともに成り立ちます。
\vee \left( A\wedge A\right) \quad \because \text{分配律}
\\
&\Leftrightarrow &\left( A\wedge B\right) \vee A\quad \because \text{ベキ等律} \\
&\Leftrightarrow &A\vee \left( B\wedge A\right) \quad \because \text{交換律}
\end{eqnarray*}が成り立ちます。つまり、\(A\wedge \left( B\vee A\right) \)において\(\wedge \)と\(\vee \)を入れ替えると新たな論理式\(A\vee \left( B\wedge A\right) \)を得られますが、これらは論理的に同値です。
後ろからの分配
論理式\(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{align*}
\left( A\wedge B\right) \vee C& \Leftrightarrow C\vee \left( A\wedge
B\right) \quad \because \text{交換律} \\
& \Leftrightarrow \left( C\vee A\right) \wedge \left( C\vee B\right) \quad
\because \text{分配律} \\
& \Leftrightarrow \left( A\vee C\right) \wedge \left( B\vee C\right) \quad
\because \text{交換律}
\end{align*}すなわち、\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*}が成り立つ。
P\wedge R\right) \vee \left( Q\wedge R\right) \\
& \left( b\right) \ \left( P\wedge Q\right) \vee R\Leftrightarrow \left(
P\vee R\right) \wedge \left( Q\vee R\right)
\end{align*}がともに成り立ちます。
分配律の一般化
4つの論理式\(A,B,C,D\)が与えられたとき、\begin{eqnarray*}A\wedge \left( B\vee C\vee D\right) &\Leftrightarrow &A\wedge \left( \left(
B\vee C\right) \vee D\right) \quad \because \text{結合律}
\\
&\Leftrightarrow &\left( A\wedge \left( B\vee C\right) \right) \vee \left(
A\wedge D\right) \quad \because \text{分配律} \\
&\Leftrightarrow &\left( A\wedge B\right) \vee \left( A\wedge C\right) \vee
\left( A\wedge D\right) \quad \because \text{分配律}
\end{eqnarray*}すなわち、\begin{equation*}
A\wedge \left( B\vee C\vee D\right) \Leftrightarrow \left( A\wedge B\right)
\vee \left( A\wedge C\right) \vee \left( A\wedge D\right)
\end{equation*}を得ます。論理積と論理和の立場を逆にした場合にも、\begin{eqnarray*}
A\vee \left( B\wedge C\wedge D\right) &\Leftrightarrow &A\vee \left( \left(
B\wedge C\right) \wedge D\right) \quad \because \text{結合律} \\
&\Leftrightarrow &\left( A\vee \left( B\wedge C\right) \right) \wedge \left(
A\vee D\right) \quad \because \text{分配律} \\
&\Leftrightarrow &\left( A\vee B\right) \wedge \left( A\vee C\right) \wedge
\left( A\vee D\right) \quad \because \text{分配律}
\end{eqnarray*}すなわち、\begin{equation*}
A\vee \left( B\wedge C\wedge D\right) \Leftrightarrow \left( A\vee B\right)
\wedge \left( A\vee C\right) \wedge \left( A\vee D\right)
\end{equation*}を得ます。
論理式の個数を増やした場合にも同様の議論が成立します。つまり、有限\(n+1\)個の論理式\(A,B_{1},\cdots ,B_{n}\)に関して、\begin{eqnarray*}\left( a\right) \ A\wedge \left( B_{1}\vee \cdots \vee B_{n}\right)
&\Leftrightarrow &\left( A\wedge B_{1}\right) \vee \cdots \vee \left(
A\wedge B_{n}\right) \\
\left( b\right) \ A\vee \left( B_{1}\wedge \cdots \wedge B_{n}\right)
&\Leftrightarrow &\left( A\vee B_{1}\right) \wedge \cdots \wedge \left(
A\vee B_{n}\right)
\end{eqnarray*}すなわち、\begin{eqnarray*}
\left( a\right) \ A\wedge \left( \bigvee\limits_{i=1}^{n}B_{i}\right)
&\Leftrightarrow &\bigvee\limits_{i=1}^{n}\left( A\wedge B_{i}\right) \\
\left( b\right) \ A\vee \left( \bigwedge\limits_{i=1}^{n}B_{i}\right)
&\Leftrightarrow &\bigwedge\limits_{i=1}^{n}\left( A\vee B_{i}\right)
\end{eqnarray*}がともに成り立つということです。
有限\(n+1\)個の論理式\(A,B_{1},\cdots,B_{n}\)を任意に選んだとき、\begin{eqnarray*}\left( a\right) \ A\wedge \left( \bigvee\limits_{i=1}^{n}B_{i}\right)
&\Leftrightarrow &\bigvee\limits_{i=1}^{n}\left( A\wedge B_{i}\right) \\
\left( b\right) \ A\vee \left( \bigwedge\limits_{i=1}^{n}B_{i}\right)
&\Leftrightarrow &\bigwedge\limits_{i=1}^{n}\left( A\vee B_{i}\right)
\end{eqnarray*}が成り立つ。
&\Leftrightarrow &\bigvee\limits_{i=1}^{n}\left( P\wedge Q_{i}\right) \\
\left( b\right) \ P\vee \left( \bigwedge\limits_{i=1}^{n}Q_{i}\right)
&\Leftrightarrow &\bigwedge\limits_{i=1}^{n}\left( P\vee Q_{i}\right)
\end{eqnarray*}が成り立ちます。
演習問題
A\vee C\right) \wedge \left( A\vee D\right) \wedge \left( B\vee C\right)
\wedge \left( B\vee D\right)
\end{equation*}が成り立つことを証明してください。
(A\wedge C) \\
& \left( b\right) \ A\veebar (B\wedge C)\Leftrightarrow (A\veebar B)\wedge
(A\veebar C)
\end{align*}などは成り立ちますか。議論してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】