# BOOL algebra : simplifications

I have this expression : (A && B) || (A && C) || (B && C)

I don't understand which steps I need to to to get this expression :

(A && B) || (C && (A XOR B))

-
You sure it's not just (C && (A||B)), using OR instead of XOR? –  Unreasonable Sin Nov 3 '11 at 18:25
Yes, I am sure. –  jlink Nov 5 '11 at 15:23

## 1 Answer

The simplest approach for an example as small as this is just to construct and compare the truth tables.

Algebraically, however, we can do \begin{align}&(A\land B)\lor(A\land C)\lor(B\land C)\\ \Leftrightarrow&(A\land B)\lor\big((A\lor B)\land C\big)\\ \Leftrightarrow&(A\land B)\lor\big(\neg(A\land B)\land ((A\lor B)\land C\big))\\ \Leftrightarrow&(A\land B)\lor\big((\neg(A\land B)\land (A\lor B))\land C\big)\\ \Leftrightarrow&(A\land B)\lor\big((A\oplus B)\land C\big) \\ \Leftrightarrow&(A\land B)\lor\big(C\land(A\oplus B)) \end{align} where the second step used the general law \begin{align}&P\lor Q\\ \Leftrightarrow&P\lor (1\land Q)\\ \Leftrightarrow&P\lor ((P\lor\neg P)\land Q)\\ \Leftrightarrow&P\lor ((P\land Q) \lor (\neg P\land Q))\\ \Leftrightarrow&(P\lor (P\land Q)) \lor (\neg P\land Q)\\ \Leftrightarrow&P \lor (\neg P\land Q) \end{align}

-
Thanks a lot for this answer ! Still, I don't understand why line (2) is algebraically equivalent to line (3). –  jlink Nov 5 '11 at 0:19
I've added the appropriate lemma. –  Henning Makholm Nov 5 '11 at 0:28
I must be stupid but I don't get it. I understand the development of the general law but I can't make the relation with the development above. I have : A∨B = ... = A∨(¬A∧B) which is not equals to ¬(A∧B)∧(A∨B) ... –  jlink Nov 5 '11 at 11:33
It's just $P=(A\land B)$ and $Q=((A\lor B)\land C)$. –  Henning Makholm Nov 5 '11 at 12:49
Now it makes sense ! Thanks again ! –  jlink Nov 5 '11 at 15:21