Boolean Algebra simplification

Thread Starter

pixel1

Joined Apr 13, 2013
4
Hi all,

I'm trying to work out what working is required to get from this 9 term expression:

A'BC'D + A'BCD' + A'BCD + AB'C'D + ABC'D + AB'CD' + AB'CD + ABCD' + ABCD

to this term:

AC + AD + BC + BD

In my attempts, I have been able to reduce it down to BD + AC + ABCD but I'm not sure how to split up the 4 variable term into AD + BC.

From the start, I cancelled out the 1st term with the 6th, and the 2nd term with the 4th leaving me with: A'BCD + ABC'D + AB'CD + ABCD' + ABCD

In the new expression with 5 terms, I was able to reduce down A'BCD + ABC'D to BD and AB'CD + ABCD' to AC. Unfortunately I'm still left with ABCD at the end so am wondering what rule(s) of algebra I might be missing :rolleyes:

Any help would be greatly appreciated :)
 

screen1988

Joined Mar 7, 2013
310
I think you are wrong here.
From the start, I cancelled out the 1st term with the 6th, and the 2nd term with the 4th leaving me with: A'BCD + ABC'D + AB'CD + ABCD' + ABCD
A'BC'D + AB'CD ≠ 0
A'BCD' + AB'C'D ≠ 0
Therefore, you can't cancel out these terms.
And A'BC'D is not equal to (AB'CD)'
A'BCD' is not equal to (AB'C'D)'

I think you can reduce this expression by using algebra rules but for me I would make a true table and it seems easier to get the result.
 

WBahn

Joined Mar 31, 2012
26,033
Hi all,

I'm trying to work out what working is required to get from this 9 term expression:

A'BC'D + A'BCD' + A'BCD + AB'C'D + ABC'D + AB'CD' + AB'CD + ABCD' + ABCD

to this term:

AC + AD + BC + BD

In my attempts, I have been able to reduce it down to BD + AC + ABCD but I'm not sure how to split up the 4 variable term into AD + BC.

From the start, I cancelled out the 1st term with the 6th, and the 2nd term with the 4th leaving me with: A'BCD + ABC'D + AB'CD + ABCD' + ABCD

In the new expression with 5 terms, I was able to reduce down A'BCD + ABC'D to BD and AB'CD + ABCD' to AC. Unfortunately I'm still left with ABCD at the end so am wondering what rule(s) of algebra I might be missing :rolleyes:

Any help would be greatly appreciated :)
What do you mean by "I cancelled out the 1st term with the 6th"?

1st term: A'BC'D
6th term: AB'CD'

How do these "cancel" in any way?

While the following is wrong, we can use it to illustrate how you can simplify terms:

BD + AC + ABCD

Notice that the second term is completely contained in the third term, so if we factor it out we get

BD + AC(1 + BD)

And since 1 and anything is 1, this reduces to

BD + AC

Aslo note that if two terms share a common factor and if the part they don't share are complements of each other, then the complement can go away. For instance:

AB'C'D + ABC'D

They share the factor AC'D, so factoring that out we have

AC'D(B'+B)

But (B'+B) is 1, so this reduces to just

AC'D

Those two concepts should get you at least most of the way there. Do the best you can and if you don't make it all the way, post your work step by step and we will see if we can help you from there.
 

Thread Starter

pixel1

Joined Apr 13, 2013
4
Thanks for the help so far :)

Ok, so I had thought that terms such as the 1st and 6th cancelled out because they were compliments of each other (A'BC'D + AB'CD') but I'll need to rethink this.

WBahn, hopefully I've used the rule you mentioned correctly for starting to reduce the expression:

A'BC'D + A'BCD' + A'BCD + AB'C'D + ABC'D + AB'CD' + AB'CD + ABCD' + ABCD
(1st)____(2nd)____(3rd)____(4th)____(5th)____(6th)____(7th)____(8th)____(9th)

A'BD(C'+C) + BCD'(A'+A) + AC'D(B+'B) + AB'C(D'+D) + ABCD
(1st & 3rd)___(2nd & 8th)___(4th & 5th)___(6th & 7th)___(9th term)

A'BD + BCD' + AC'D + AB'C + ABCD

I'm hoping I'm on the right track now but I'm still not 100% sure how I'll get this reduced down to AC + AD + BC + BD
 

WBahn

Joined Mar 31, 2012
26,033
Ok, so I had thought that terms such as the 1st and 6th cancelled out because they were compliments of each other (A'BC'D + AB'CD') but I'll need to rethink this.
But they aren't complements of each other. In order to be complements, whenever one is true the other must be false and vice versa. While it is true that if one of them is true that the other must be false, it is also possible for both of them to be false. For instance, what if A=0 and B=0?

WBahn, hopefully I've used the rule you mentioned correctly for starting to reduce the expression:

A'BC'D + A'BCD' + A'BCD + AB'C'D + ABC'D + AB'CD' + AB'CD + ABCD' + ABCD
(1st)____(2nd)____(3rd)____(4th)____(5th)____(6th)____(7th)____(8th)____(9th)

A'BD(C'+C) + BCD'(A'+A) + AC'D(B+'B) + AB'C(D'+D) + ABCD
(1st & 3rd)___(2nd & 8th)___(4th & 5th)___(6th & 7th)___(9th term)

A'BD + BCD' + AC'D + AB'C + ABCD
You are doing fine, so far.

I'm hoping I'm on the right track now but I'm still not 100% sure how I'll get this reduced down to AC + AD + BC + BD
The next steps are a bit less obvious, but are really using the same idea.

First, you need to keep in mind that just because you combine a couple of terms you can still use the original terms again if you need to. This is because A = A + A, so look in the original terms to see which ones can combine with that 9th term. In fact, you will find four of them, so don't just settle for the first one you find. Write down all four. In fact, this goes for all the other terms that you combined as well. Go back and extract all of the three-factor terms that you can. If I'm counting correctly, you have a total of twelve pairs of four-factor terms that have three factors in common. Your simplified expression at this stage consists of the twelve three-factor terms (with any duplicates removed) and any four-factor terms that were not part of any of the pairs (and you shouldn't have any of those because we know we are heading toward a solution that doesn't have any).

So, at this point, you will have an expression consisting of twelve three-factor terms instead of nine four-factor terms. It may seem like you are going the wrong way, but you have actually made a huge amount of progress.

Now simply repeat this cycle and find all of the pairs of three-factor terms that have two factors in command and for which the remaining factors are complements. So group ABC' and AB'C but do not group ABC and ABD.

Again, only those three-factor terms that are not a part of any of the pairs survive as three-factor terms in the next step and, again, there shouldn't be any of those. You should find eight such pairs and once you reduce those to a sum of eight two-factor terms you should find that four of them are duplicates and can be eliminated, leaving you with the four terms in the final answer.
 

Thread Starter

pixel1

Joined Apr 13, 2013
4
Thanks WBahn!!!

That was really helpful, I've been able to work through it now :) I didn't realise how much work was involved, but makes sense and gave the exact answer. This is what I did (typed this out in case it helps others too):

1st term combined with 3rd & 5th = A'BD+BC'D
2nd term combined with 3rd & 8th = A'BC+BCD'
3rd term combined with 1st, 2nd & 9th = A'BD+A'BC+BCD
4th term combined with 5th & 7th = AC'D+AB'D
5th term combined with 1st, 4th & 9th = BC'D+AC'D+ABD
6th term combined with 7th & 8th = AB'C+ACD'
7th term combined with 4th, 6th & 9th = AB'D+AB'C+ACD
8th term combined with 2nd, 6th & 9th = BCD'+ACD'+ABC
9th term combined with 3rd, 5th, 7th & 8th = BCD+ABD+ACD+ABC

With duplicates removed:
A'BD+BC'D+A'BC+BCD'+BCD+AC'D+AB'D+ABD+AB'C+ACD'+ACD+ABC

Reduced down to:
BD + BD + BC + BC + AD + AD + AC + AC
= BD + BC + AD + AC

:)
 

WBahn

Joined Mar 31, 2012
26,033
Very good. About the only thing I would point out is that you can avoid most of the duplicates (all in the first round) by only looking for pairs involving later terms. So you look at all eight of the remaining terms when considering the first term, but when looking at the, say, fifth term you only need to consider the remaining four terms because any pairs that existed involving the first four terms would have been found already.

Note that this approach is very algorithmic, meaning that it would be a pretty straightforward thing to write a program to perform this kind of simplification.
 
Top