-1

I want to write a series of equivalences that reduces

$(A \land \lnot B) \lor (A \land \lnot C) \lor (B \land \lnot A) \lor (B \land C)$

to

$A \lor B$ .

I usually don't struggle with boolean algebra, but this one has me stumped! Thanks in advance.

Archr
  • 1,151
  • 8
  • 20
  • Pulling out A from the two conjunctions it's a part of, and pulling out B from the two conjunctions it's a part of. Unfortunately, I can't see anything to follow those up with. – Archr Sep 11 '17 at 07:42

3 Answers3

2

$ \begin{equation} \phantom{\equiv}(A\land\neg B)\lor(A\land\neg C)\lor(B\land\neg A)\lor(B\land C)\\ \equiv(A\land\neg B)\lor(A\land\neg C)\lor(B\land\neg A)\lor(A\land B\land C)\lor(\neg A\land B\land C)\\ \equiv(A\land (\neg B\lor\neg C\lor (B\land C)))\lor(B\land\neg A)\lor(\neg A\land B\land C)\\ \equiv A\lor(B\land\neg A)\lor(\neg A\land B\land C)\\ \equiv A\lor(B\land\neg A\land\neg C)\lor(\neg A\land B\land C)\\ \equiv A\lor(B\land\neg A)\\ \equiv A\lor B \end{equation} $

trying
  • 4,756
  • 1
  • 13
  • 23
1

It's not pretty, but it's something:

$(A \wedge (B \vee C)) \vee (B \wedge (\neg A \vee C))$ (Distribution)

$(A \wedge B \wedge (\neg A \vee C)) \vee ((\neg B \vee C) \wedge B \wedge (\neg A \vee C))$ (Distribution)

$(A \wedge B \wedge C) \vee (C \wedge B \wedge (\neg A \vee C))$ (Disjunctive Syllogism)

$(A \wedge B \wedge C) \vee (A \wedge B \wedge C) \vee (A \wedge B \wedge C)$ (Distribution)

$A \wedge B \wedge C$ (Tautology)

$A \wedge B$ (Simplification)

$A $ (Simplification)

$A \vee B$ (Addition)

Raute
  • 103
  • ...Took the desire path here and there - let me know if some step isn't clear. – Raute Sep 11 '17 at 08:23
  • 1
    Thanks for the answer, but some of these steps look like implications rather than equivalences. For example, $A \land B \land C$ implies $A \land B$, but those expressions aren't equivalent. It's important that I only use equivalences because I want to show that the initial and final expressions are interchangeable. – Archr Sep 11 '17 at 08:26
  • 2
    Oh, right. Sorry! But Joel Reyes Noche's answer looks good. – Raute Sep 11 '17 at 08:32
1

$(A \land\lnot B)\lor(A\land\lnot C)\lor(\lnot A\land B)\lor(B\land C)$

Expand

$(A \land\lnot B\land C)\lor(A \land\lnot B\land\lnot C)\lor(A\land B\land\lnot C)\lor\color{red}{(A\land\lnot B\land\lnot C)}\lor(\lnot A\land B\land C)\lor(\lnot A\land B\land\lnot C)\lor\color{blue}{(A\land B\land C)}\lor\color{red}{(\lnot A\land B\land C)}$

Move $\color{blue}{\mathrm{a~term}}$, remove $\color{red}{\mathrm{some~terms}}$

$(A \land\lnot B\land C)\lor(A \land\lnot B\land\lnot C)\lor\color{blue}{(A\land B\land C)}\lor(A\land B\land\lnot C)\lor(\lnot A\land B\land C)\lor(\lnot A\land B\land\lnot C)$

Simplify away the $C$'s

$(A \land\lnot B)\lor(A\land B)\lor(\lnot A\land B)$

Can you do the last step?

JRN
  • 6,566
  • 1
    That expansion idea is an interesting way to turn around from a dead end, and I do see how to proceed from your final step. trying's answer was great too, but I will give it to you for the colors! Thanks. – Archr Sep 11 '17 at 08:51
  • You're welcome! – JRN Sep 11 '17 at 13:09