[Math] Boolean Algebra: Prove associate law for products

associativityboolean-algebraproof-writing

I'm working through some old papers for an exam coming up, and I found this question that I cannot seem to answer, and I don't have the memos.

Could someone please help me out?

The question:
Prove the associative law for products: For any elements a, b, and c in a Boolean
algebra,
$$(a ∗ b) ∗ c = a ∗ (b ∗ c).$$
Begin your proof by letting $L = (a ∗ b) ∗ c$ and
$R = a ∗ (b ∗ c)$, and first show that $a + L = a + R$, and then that $a′ + L = a′ + R$.
You may only use the axioms of Definition 1.2, and then also idempotency, boundedness, and absorption.

And Definition 1.2:

Commutativity:
$a+b=b+a$
$a*b=b*a$

Distributivity:
$a + (b ∗ c) = (a + b) ∗ (a + c)$
$a ∗ (b + c) = (a ∗ b) + (a ∗ c)$

Identities:
$a + 0 = a$
$a * 1 = a$

Complements:
$a + a' = 1$
$a *a' = 0$

Any help would be greatly appreciated

Best Answer

Let us calculate those terms:

\begin{align} a + L &= a + ( (a * b) * c )\\ &= (a + (a * b)) * (a + c)\tag{distributivity}\\ &= a * (a + c)\tag{absortion}\\ &= a.\tag{absortion} \end{align}

\begin{align} a + R &= a + ( a * (b*c) )\\ &= a. \tag{absortion} \end{align} Thus, $a+L=a+R$.

\begin{align} a' + R &= a'+ (a * (b*c))\\ &= (a' + a) * (a' + (b*c))\tag{distributivity}\\ &= 1 * ((a' + b) * (a' + c))\tag{distributivity, complement}\\ &= (a' + b) * (a' + c).\tag{identities} \end{align}

\begin{align} a' + L &= a' + ((a*b)*c)\\ &= (a' + (a*b)) * (a' + c)\tag{distributivity}\\ &= ((a' + a) * (a' + b))*(a' + c)\tag{distributivity}\\ &= ( 1 * (a' + b) ) * (a' + c)\tag{complement}\\ &= (a' + b) * (a' + c), \end{align} and so $a' + R = a' +L$.

Now given that $a+L=a+R$ and $a' + R = a' +L$,

\begin{align} L &= (a * a') + L \\ &= (a + L) * (a' + L) \\ &= (a + R) * (a' + R)\\ &= (a * a') + R\\ &= R, \end{align} where by now, I suppose you can justify the above equalities.

Related Question