0
$\begingroup$

I have a Boolean algebra with some elements $a,b,c$. I have to show this:

$(a ∧ b) ∨ (a′ ∧ c) ∨ (b ∧ c) = (a ∧ b) ∨ (a′ ∧ c)$.

Now I have done other such proofs before but this one I got lost in. I see Boolean algebras have a cancellation law, so my guess was I had to cancel the terms that are on both sides, to get:

$b ∧ c = O_B.$

Since this ended up looking more like an equation than an identity - I could use some help. I would especially like to know why the cancellation method fails. Thanks!

$\endgroup$
  • 1
    $\begingroup$ Hint: $b\land c \rightarrow (a \land b)\lor(a' \land c)$ $\endgroup$ – SBareS Jan 4 '15 at 22:03
  • $\begingroup$ How is this derived? $\endgroup$ – Snowflake Jan 4 '15 at 23:42
  • $\begingroup$ Well, if $bc=1$ (meaning that both $b$ and $c$ are equal to $1$), then $ab+\overline{a}c$ will be $1$ anyhow. $\endgroup$ – Shahar Jan 5 '15 at 1:40
  • $\begingroup$ I'm sorry but I don't get the notation... but I believe you just repeated what @SBareS said, I wanted to know what rules are used to derive that since I wouldn't know how to use the distributive law on that. I get it on an intuitive level. $\endgroup$ – Snowflake Jan 5 '15 at 11:35
  • $\begingroup$ @Snowflake You can set $b=c=1$ and then $(a\land 1)\lor(a'\land 1)=a\lor a'= 1$. $\endgroup$ – SBareS Jan 5 '15 at 13:10
0
$\begingroup$

Here's a hint: In a Boolean algebra, $a \vee a = a \vee a \vee a$ for all elements $a$, but that doesn't mean that $O_B = a$ for all $a$. Thus I think you should look back at what kind of cancellation laws are valid.

http://en.wikipedia.org/wiki/Boolean_algebra

$\endgroup$
  • $\begingroup$ What it says in my book is that $a V b = a V c → b = c$, and same thing with ∧. Both this and your example make intuitive sense to me, but since it's hard when the formulas are more complicated I'd need to know what's the substantial difference. $\endgroup$ – Snowflake Jan 4 '15 at 23:45

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.