0
$\begingroup$

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

  • 0
    You sure it's not just (C && (A||B)), using OR instead of XOR?2011-11-03
  • 0
    Yes, I am sure.2011-11-05

1 Answers 1

2

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

  • 0
    Thanks a lot for this answer ! Still, I don't understand why line (2) is algebraically equivalent to line (3).2011-11-05
  • 0
    I've added the appropriate lemma.2011-11-05
  • 0
    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) ...2011-11-05
  • 0
    It's just $P=(A\land B)$ and $Q=((A\lor B)\land C)$.2011-11-05
  • 0
    Now it makes sense ! Thanks again !2011-11-05