吸収律
論理式\(A,B\)を任意に選んだとき、以下の恒真式\begin{align*}& \left( a\right) \ A\wedge (A\vee B)\Leftrightarrow A \\
& \left( b\right) \ A\vee (A\wedge B)\Leftrightarrow A
\end{align*}が成り立ちます。論理積と論理和の間に成立する以上の性質を吸収律（absorption law）と呼びます。
論理式\(A\)が与えられたとき、それと任意の論理式\(B\)との論理和\(A\vee B\)をとります。さらに、この論理和ともとの論理式\(A\)の論理積\(A\wedge(A\vee B)\)をとると先の論理式\(A\vee B\)は吸収されて\(A\)に戻ってしまうというのが\(\left( a\right) \)の主張です。
論理式\(A\)が与えられたとき、それと任意の論理式\(B\)との論理積\(A\wedge B\)をとります。さらに、この論理積ともとの論理式\(A\)の論理和\(A\vee(A\wedge B)\)をとると先の論理式\(A\wedge B\)は吸収されて\(A\)に戻ってしまうというのが\(\left( b\right) \)の主張です。
& \left( b\right) \ A\vee (A\wedge B)\Leftrightarrow A
\end{align*}が成り立つ。
吸収律と\(\Leftrightarrow \)の推移律より、任意の論理式\(A,B\)に対して、\begin{equation*}A\wedge (A\vee B)\Leftrightarrow A\vee (A\wedge B)
\end{equation*}という関係もまた成立します。
& \left( b\right) \ P\vee (P\wedge Q)\Leftrightarrow P
\end{align*}がともに成り立ちます。
Q &\rightarrow &R
\end{eqnarray*}はともに論理式であるため、吸収律より、\begin{align*}
& \left( a\right) \ \left( P\rightarrow Q\right) \wedge (\left( P\rightarrow
Q\right) \vee \left( Q\rightarrow R\right) )\Leftrightarrow \left(
P\rightarrow Q\right) \\
& \left( b\right) \ \left( P\rightarrow Q\right) \vee (\left( P\rightarrow
Q\right) \wedge \left( Q\rightarrow R\right) )\Leftrightarrow \left(
P\rightarrow Q\right)
\end{align*}がともに成り立ちます。
&A\wedge \left( B\wedge \left( C\vee B\right) \right) \quad \because \text{結合律} \\
&\Leftrightarrow &A\wedge \left( B\wedge \left( B\vee C\right) \right) \quad
\because \text{交換律} \\
&\Leftrightarrow &A\wedge B\quad \because \text{吸収律}
\end{eqnarray*}が成り立ちます。
\text{「私はご飯とパンが両方好きです。」}
\quad \cdots (1)
\end{equation}と言った場合、この人がご飯が好きであると判定できるでしょうか。命題変数\(P,Q\)を、\begin{eqnarray*}P &:&\text{ご飯が好き} \\
Q &:&\text{パンが好き}
\end{eqnarray*}定義します。発言\(\left(1\right) \)より\(P\)と\(Q\)はともに真であるため、論理積の定義より\(P\wedge Q\)は真です。さて、以下の恒真式\begin{equation*}P\wedge Q\Rightarrow P
\end{equation*}が成り立つ（確認してください）ため、\(P\wedge Q\)が真である場合には\(P\)もまた真であることが確定します。したがって、この人はご飯が好きであると判定できます。では、\begin{equation}\text{「私はご飯とパンが好きです。またはパンが好きです。」}
\quad \cdots (2)
\end{equation}と言った場合、この人がご飯が好きであると判定できるでしょうか。先の命題変数\(P,Q\)を引き続き採用します。発言\(\left( 2\right) \)より\(\left( P\wedge Q\right) \vee Q\)は真です。さて、吸収律より以下の恒真式\begin{equation*}\left( P\wedge Q\right) \vee Q\Leftrightarrow Q
\end{equation*}が成り立つため、\(\left(P\wedge Q\right) \vee Q\)が真であることは\(Q\)が真であることを意味します。つまり、発言\(\left( 2\right) \)は「私はパンが好きです」という主張と実質的に等しいということです。パン好きであるという情報だけからはご飯好きであるどうかは判定できないため、発言\(\left( 2\right) \)からは、この人がご飯好きであると判定できません。実際、ご飯とパンの両方が好きな場合と、ご飯が好きではなくパンが好きな場合の両方のケースにおいて「私はご飯とパンが好きです。またはパンが好きです。」という主張は真になります。
吸収律の一般化
3つの論理式\(A,B,C\)が任意に与えられたとき、\begin{eqnarray*}A\wedge \left( A\vee B\vee C\right) &\Leftrightarrow &A\wedge \left( A\vee
\left( B\vee C\right) \right) \quad \because \text{結合律}
\\
&\Leftrightarrow &A\quad \because \text{吸収律}
\end{eqnarray*}すなわち、\begin{equation*}
A\wedge \left( A\vee B\vee C\right) \Leftrightarrow A
\end{equation*}を得ます。論理積と論理和の立場を逆にした場合にも、\begin{eqnarray*}
A\vee \left( A\wedge B\wedge C\right) &\Leftrightarrow &A\vee \left(
A\wedge \left( B\wedge C\right) \right) \quad \because \text{結合律} \\
&\Leftrightarrow &A\quad \because \text{吸収律}
\end{eqnarray*}すなわち、\begin{equation*}
A\vee \left( A\wedge B\wedge C\right) \Leftrightarrow A
\end{equation*}を得ます。
論理式の個数を増やした場合にも同様の議論が成立します。つまり、有限\(n+1\)個の論理式\(A,B_{1},\cdots ,B_{n}\)に関して、\begin{eqnarray*}\left( a\right) \ A\wedge \left( A\vee B_{1}\vee \cdots \vee B_{n}\right)
&\Leftrightarrow &A \\
\left( b\right) \ A\vee \left( A\wedge B_{1}\wedge \cdots \wedge
B_{n}\right) &\Leftrightarrow &A
\end{eqnarray*}すなわち、\begin{eqnarray*}
\left( a\right) \ A\wedge \left( A\vee \bigvee\limits_{i=1}^{n}B_{i}\right)
&\Leftrightarrow &A \\
\left( b\right) \ A\vee \left( A\wedge
\bigwedge\limits_{i=1}^{n}B_{i}\right) &\Leftrightarrow &A
\end{eqnarray*}がともに成り立つということです。
有限\(n+1\)個の論理式\(A,B_{1},\cdots,B_{n}\)を任意に選んだとき、\begin{eqnarray*}\left( a\right) \ A\wedge \left( A\vee \bigvee\limits_{i=1}^{n}B_{i}\right)
&\Leftrightarrow &A \\
\left( b\right) \ A\vee \left( A\wedge
\bigwedge\limits_{i=1}^{n}B_{i}\right) &\Leftrightarrow &A
\end{eqnarray*}が成り立つ。
&\Leftrightarrow &P \\
\left( b\right) \ P\vee \left( P\wedge
\bigwedge\limits_{i=1}^{n}Q_{i}\right) &\Leftrightarrow &P
\end{eqnarray*}が成り立ちます。
吸収律の有用性
論理式\(A,B\)に関する論理式\begin{equation*}A\wedge (A\vee B)
\end{equation*}が与えられている状況を想定します。論理回路を想定しても構いません。\(B\)がどれほど複雑な論理式であったとしても、吸収律より、先の論理式は、\begin{equation*}A
\end{equation*}と必要十分であるため、先の論理式を\(A\)に置き換えることができます。先の命題は、\begin{equation*}B=\bigvee\limits_{i=1}^{n}B_{i}
\end{equation*}である状況を想定したものですが、実際には、同様の議論は任意の論理式\(B\)について成り立ちます。以上の事実を利用することにより、与えられた論理式を大幅に簡略化できます。論理回路であれば、吸収律を利用することにより、処理を最適化できるということです。もう一方の吸収律\begin{equation*}A\vee (A\wedge B)\Leftrightarrow A
\end{equation*}についても同様の議論が成り立ちます。
演習問題
\end{equation*}が成り立つことを証明してください。
\vee \left( B\wedge C\right) \Leftrightarrow \left( A\vee C\right) \wedge B
\end{equation*}が成り立つことを証明してください。
C\right) \right) \Leftrightarrow A\vee \left( B\vee C\right)
\end{equation*}が成り立つことを証明してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】