3
$\begingroup$

How would I simplify / reduce the following equation using boolean identities/proofs? $$a \vee (a \wedge b) = a$$ So far I've used the distributivity identity and got $$(a\vee a) \wedge (a\vee b)$$ I then used the idempotence law to get $$a \wedge (a\vee b)$$ Now I can't think of what to do next.

$\endgroup$
  • $\begingroup$ Use a truth table. $\endgroup$ – Joel Reyes Noche May 9 '14 at 11:22
  • $\begingroup$ ~@JoelReyesNoche I'll try that out now, thank you. $\endgroup$ – CS Student May 9 '14 at 11:23
  • $\begingroup$ @JoelReyesNoche Yes, sorry about that. $\endgroup$ – CS Student May 9 '14 at 11:25
6
$\begingroup$

You're probably looking for this and not for truth-tables or what I'd written previously:

$$a \lor (a \land b)$$ $$(a \land \top) \lor (a \land b)$$ $$a \land (\top \lor b)$$ $$a \land \top$$ $$a$$

$\endgroup$
  • 2
    $\begingroup$ I think the original equation is also a redundance law :) $\endgroup$ – user35603 May 9 '14 at 11:31
  • 1
    $\begingroup$ @CSStudent Let me know if that's not what you want or if one of the steps you can't use. $\endgroup$ – Hunan Rostomyan May 9 '14 at 11:44
  • 1
    $\begingroup$ @HunanRostomyan I never thought of simply adding a True value into the equation and going from there, thats pretty clever. Could you explain how line 2 turns into line 3? Slightly confused. $\endgroup$ – CS Student May 9 '14 at 12:01
  • 1
    $\begingroup$ @CSStudent Recall that: $\top$ is the $\land$-identity (just like $1$ is the multiplicative identity). As regards the (2)-(3) move, do you remember how this works from high school algebra: $(a \cdot 1)+(a \cdot b) = a \cdot (1 + b)$? You're simply factoring the common $a$ out. It's the same principle. It's the reverse of distributivity. $\endgroup$ – Hunan Rostomyan May 9 '14 at 12:09
  • 1
    $\begingroup$ Another important aspect of this answer is that it holds in all Boolean algebras (in fact, the identities used in the four steps hold in all distributive lattices with maximum element $\top$). $\endgroup$ – Carl Mummert May 9 '14 at 14:40
2
$\begingroup$

$$ \begin{array}{ccc} a & b & a\mathrm{~AND~}b & a\mathrm{~OR~}(a\mathrm{~AND~}b)\\\hline 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1\\ 1 & 1 & 1 & 1\\ \end{array} $$

$\endgroup$
  • 1
    $\begingroup$ I ended up with the same truth table as you, but how can I use this to prove the original equation is equal to just 'a' ? I'm starting to think I've missed something really obvious. $\endgroup$ – CS Student May 9 '14 at 11:30
  • $\begingroup$ Their two columns are exactly the same. Therefore the two expressions are equivalent. $\endgroup$ – Joel Reyes Noche May 9 '14 at 11:31
  • 1
    $\begingroup$ Thanks Joel, that explains it. $\endgroup$ – CS Student May 9 '14 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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