Boolean Algebra Proof Statement

[cyenko]

Homework Statement

Prove the identity of the following Boolean equation using algebraic manipulation:
AD' + A'B + C'D + B'C = (A' + B' + C' + D')(A + B + C + D)

Homework Equations

DeMorgan's Theorem: (A + B)' = A'B'

The Attempt at a Solution

I tried simplifying the equation to the following:
AD' + A'B + C'D + B'C = A'D + A'B + C'D+ B'C + (A'C + A'D + B'A + B'D + C'A + C'B + D'B + D'C)

However, this doesn't appear to be going anywhere. What kills me is the fact that I have no way of knowing whether or not the path I'm following will turn out or not.

My TA mentioned that the left hand side should be modified with OR statements (+), however I'm not sure where to begin. Any help would be greatly appreciated.

 

[phinds]

Interesting. I can easily see w/ a Kmap that the statement is true, but like you, I draw a blank when trying to prove it algebraically. DeMorgan doesn't seem to help and I don't know what else to try. There's probably something simple that we're both forgetting or overlooking.

 

[cyenko]

I'm glad I'm not the only one who would have difficulty solving this proof. The problem is still open, for anyone who is willing to help me!

 

[cyenko]

Bumping for help.

 

[Joffan]

Well, from the K-map they are both equal to (ABCD + A'B'C'D)', which we know immediately anyway from applying DeMorgan a couple of times to the RHS.

The K-map shows us there is plenty of overlap in the RHS, so we could try to unravel that...
(A'+B'+C'+D')(A+B+C+D) = A'B + A'C + A'D + B'A + B'C + B'D + C'A + C'B + C'D + D'A + D'B + D'C

What we might do is show that (for example) B'A is covered by AD' + C'D + B'C. So:
AD' + C'D + B'C
= AD' + AB'D' + C'D + AB'C'D + B'C + AB'CD
= AD' + C'D + B'C + AB'(D' + C'D + CD)
= AD' + C'D + B'C + AB'(D'+D)
= AD' + C'D + B'C + AB'

And we can similarly conjure the other terms required out of the LHS. But it's a long, long way round to do them all explicitly; there probably is a better method. Perhaps you could do this with some kind of general analysis of PQ'.

 

[NascentOxygen]

Homework Statement

Prove the identity of the following Boolean equation using algebraic manipulation:
AD' + A'B + C'D + B'C = (A' + B' + C' + D')(A + B + C + D)

Focus on the left side, AD' + A'B + C'D + B'C

♦ Replace each AND with OR, you'll need to bring in some brackets

♦ Replace each red OR with AND

♦ Remove the brackets (i.e., "multiply it out") and tidy up, and you'll be left with the OR of two simple terms

You should see your way to be able to finish now.

 

[phinds]

Focus on the left side, AD' + A'B + C'D + B'C

♦ Replace each AND with OR, you'll need to bring in some brackets

♦ Replace each red OR with AND

♦ Remove the brackets (i.e., "multiply it out") and tidy up, and you'll be left with the OR of two simple terms

You should see your way to be able to finish now.

I'm confused. If you have the term

A AND NOT B

How, in terms of just the variables A and B, can you create an equivalent with no AND but any number of ORs ?

 

[Joffan]

Focus on the left side, AD' + A'B + C'D + B'C

♦ Replace each AND with OR, you'll need to bring in some brackets

♦ Replace each red OR with AND

♦ Remove the brackets (i.e., "multiply it out") and tidy up, and you'll be left with the OR of two simple terms

You should see your way to be able to finish now.

Neat. I like it, 6 lines or so.

I'm confused. If you have the term

A AND NOT B

How, in terms of just the variables A and B, can you create an equivalent with no AND but any number of ORs ?

by using DeMorgan's rule: AB' = (A'+B)'
A and not-B = not-(not-A or B)

 

[phinds]

Neat. I like it, 6 lines or so.



by using DeMorgan's rule: AB' = (A'+B)'
A and not-B = not-(not-A or B)

well, yeah, but there is then a NOT over the whole thing, so you haven't quite separated out the terms individually. That's what I meant. As I said in my original post, I don't see how DeMorgan helps, but apparently I'm missing something.

 

[Joffan]

There is indeed a NOT over the whole thing - but no ANDs, which is all that was promised.

Here's the first step of NascentOxygen's method, for enlightenment:
AD' + A'B + C'D + B'C = (A' + D)' + (A + B')' + (B + C')' + (C + D')'