Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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))

share|cite|improve this question
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
up vote 2 down vote accepted

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}$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.