Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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. –  0alpha0 Nov 5 '11 at 15:23
add comment

1 Answer

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|improve this answer
    
Thanks a lot for this answer ! Still, I don't understand why line (2) is algebraically equivalent to line (3). –  0alpha0 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) ... –  0alpha0 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 ! –  0alpha0 Nov 5 '11 at 15:21
add comment

Your Answer

 
discard

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.