1

I'm trying to prove this equation using Boolean algebra : (it is a digital design problem) $$bc + \bar acd + a \bar bcd + b \bar d + b \bar cd = cd + b$$ What I'm done: $$bc + \bar acd + a \bar bcd + b \bar d + b \bar cd$$ $$=cd(\bar a + a \bar b) + b(c + \bar cd + \bar d)$$

from this I think both $(\bar a + a \bar b)$ and $(c + \bar cd + \bar d)$ must be $1$.

so I tried to multiply this to something equal to $1$ to simplify it:

$$(c + \bar cd + \bar d)$$

$$=(c + \bar cd + \bar d)(c + \bar c)$$

$$=(c + \bar cd + c \bar d + \bar c \bar d)$$

$$=c(1+d) + \bar c(d+ \bar d)$$ $$=(c+ \bar c)$$ $$=1$$

but for the second term I tried the same above with $(a + \bar a)$ , $(b + \bar b)$ but none of them worked. so what is the trick here?

Uncle
  • 23

1 Answers1

1

$$=cd(\bar a + a \bar b) + b(c + \bar cd + \bar d)$$

from this I think both $(\bar a + a \bar b)$ and $(c + \bar cd + \bar d)$ must be $1$.

Given that your goal is $cd + b$ that makes a lot of sense, but it is not true. Indeed, $\bar a + a \bar b \not = 1$

How can that be? Well, all you really have shown is that your original expression simplifies to

$$cd(\bar a + a \bar b) + b(c + \bar cd + \bar d)$$

and that would equal $cd + b$ if it were true that $(\bar a + a \bar b)$ and $(c + \bar cd + \bar d)$ are both $1$

which is not the same as saying that must be true that $(\bar a + a \bar b)$ and $(c + \bar cd + \bar d)$ are both $1$

Indeed, the fact that it is not true that $(\bar a + a \bar b)$ and $(c + \bar cd + \bar d)$ are both $1$ does not mean that $cd(\bar a + a \bar b) + b(c + \bar cd + \bar d)$ does not simplify to $cd + b$. It does simplify to that ... you just need to try a different route.

In sum: Some proof strategies work, others don't. Your particular strategy didn't. So try a different one.

I suggest you use:

Reduction

$p + \bar p q = p + q$

(Proof: $p + \bar p q = (p + \bar p)(p +q) = 1(p+q)=p + q$)

Or even:

Generalized Reduction

$pr + \bar p q r = pr + qr$

(Proof: $pr + \bar p q r = (p+ \bar p q)r = (p + q)r = pr + qr$

And of course:

Absorption

$p + pq = p$

(Proof: $p + pq = p(1+q)=p1=p$)

and:

Adjacency

$pq+p\bar q = p$

(Proof: $pq+p\bar q = p(q + \bar q) = p1 = p$)

With that:

$$bc + \bar acd + a \bar bcd + b \bar d + b \bar cd = \text{ (Gen'd Reduction x 2)}$$

$$bc+ \bar acd + a \bar bcd + b \bar d + b= \text{(Absorption x 2)}$$

$$\bar acd + a \bar bcd + b= \text{(Reduction)}$$

$$\bar acd + a cd + b= \text{(Adjacency)}$$

$$cd + b$$

Community
  • 1
Bram28
  • 100,612
  • 6
  • 70
  • 118
  • so what are other strategies? – Uncle Oct 17 '17 at 20:13
  • Well, you can take the $b$ out as you did, and thus get $b(c + \bar c d + \bar d)$ which, as you showed, simplifies to $b1$ and thus to just $b$. But now you can use that $b$ to reduce $a \bar b c d$ to just $a c d$ : $b + a\bar b c d = (b + a)(b + \bar b) (b + c)(b+d) = (b+a)1(b+c)(b+d)=(b+a)(b+c)(b+d)=b+acd$). And now you can combine that $acd$ with $\bar a cd$ to just get $cd$ – Bram28 Oct 17 '17 at 20:51
  • @Uncle Ugh, that comment didn;t come out very well .. I'll add something to my Answer ... – Bram28 Oct 17 '17 at 20:52