# Karnaugh Map Simplification Justification

Discussion in 'Homework Help' started by theavi, Feb 3, 2010.

1. ### theavi Thread Starter New Member

Dec 19, 2009
9
0
I'm enrolled at a local technical college and am currently studying digital electronics. We have covered karnaugh maps and how to simplify them with grouping. We recently were tested on it and I got back my test and noticed that the teacher was in error about marking one of my questions wrong. Upon, pointing this out he proceeded to defend his point of view but I KNOW I'm correct. I have input the information in various karnaugh map simplification softwares and even found a neat javascript online simplifier but I don't think that is going to be good enough for him so can someone help me find some resources explaining why simplifying the way I did is correct? I have tried and I'm hoping people here can help me.

Here is the karnaugh map:

The simplified answer I got was: A + B' = X
I'll write it out in case anyone is unfamiliar with how I wrote it just now: A OR NOT B = X

I did this by grouping in this way:

In other words I grouped the bottom four and then took the bottom two and wrapped up to the top two for another group of four. My teacher claims that this is not possible and the top two should be grouped by themselves. I know it is possible however I don't have any sources to back it up as my logic and understanding of this is simply not justification enough for him even after I explained and demonstrated that software gives the same answer as me.

Can anyone help me please find some resources backing up my claim. At this point it isn't about points on my test (I get an A+ in the class either way). Its about teaching the proper way of simplifying karnaugh maps for the benefit of others who don't understand.

Thanks very much All About Circuits. I look forward to your responses and eagerly await them!

Sincerely,
Allen

PS the book we use is Digital Electronics: Principles and Applications sixth edition by Roger L Tokheim. I would have emailed Mr. Tokheim himself had I known his email address but no luck. If by some off chance he browses this forum it would be great for him to get in touch with me and somehow verify for me his identity. Thanks.

2. ### thyristor Active Member

Dec 27, 2009
94
0
You're correct. Imagine if the AB' line were moved to the top of the matrix. Then you have a straightforward green rectangle and then the red rectangle would be split. But even your teacher knows that the red rectangle is correct. Ergo, you have proved your point.

Last edited: Feb 3, 2010
3. ### theavi Thread Starter New Member

Dec 19, 2009
9
0
I know I'm correct, the problem is the teacher disagrees with me and of course he does he has a bachelors degree in adult education and has been doing electronics more than 20 years, so my opinion and explanation (especially given that I've only learned this within the last month) is not justification enough for him. He wants sources outside of myself and I'm having trouble finding three variable karnaugh maps with two overlapping groups of four and explanations as to why this is okay.

As I said before I've got an A in the class either way its for the people who don't and don't realize they did better than they did as well as all the future students in his class not to mention the teachers own benefit.

Dec 27, 2009
94
0
5. ### thyristor Active Member

Dec 27, 2009
94
0
Here's a 3 variable wrap around (about 2/3rds of the way down the page) where it says "Groups may wrap around the table. The leftmost cell in a row may be grouped with the rightmost cell and the top cell in a column may be grouped with the bottom cell".

http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karrules.html

This from a University of Surrey webpage in England

6. ### theavi Thread Starter New Member

Dec 19, 2009
9
0
Wow, I knew you guys could help. I'll print these out and see how it goes. If anyone can find anything else that would be great. The more the merrier in this case. I'll be sure to post if he agrees or not. Unfortunately, at my tech school there aren't many electronics teachers so its somewhat tough to find one that has a complete grasp on digital electronics and karnaugh maps as my teacher is the one who is responsible for teaching this course.

EDIT:

The conclusion to this was I presented him with the evidence including the proof using boolean algebra below and he basically told me that it wouldn't make a letters grade difference to anyone in the class so the point was moot (read: he didn't really seem to care that what was being taught was incorrect). I think it's a shame that there are instructors out there that are like that and it just further proves that even with education you get what you pay for (my tech school isn't exactly ivy league if you know what I'm saying) though I'm sure there is a point of diminishing return as far as money put into your degree versus the quality of education received goes.

Anyhow here is the boolean algebra proof for why I was right for anyone who has this problem in the future:

Using boolean logic to further simplify A+A'B'

In boolean Algebra:
AB is known as conjunction or A∧ B
A+B is known as disjunction or A∨ B
-A is known as negation or complementation or ¬A

Using the rule known as the "Distributivity of ∨ over ∧":
A+A'B' = (A+A')(A+B')
or in Boolean Algebra terms
A∨ (¬A ∧¬B) = (A∨¬A)(A∨¬B)

From here using the "∨ Complementation Rule" or Disjunction Complementation Rule we can simplify further:
The complementation rule simply states that (A+A') = 1
or in Boolean Algebra terms (A∨¬A) = 1

Thus (A+A')(A+B') = 1 (A+B')
or in Boolean Algebra terms (A∨¬A)(A∨¬B) = 1 (A∨¬B)

Finally, using the rule "Identity for ∧" or Identity Rule of Conjunction we will reach our simplest form:
The Identity for ∧ states that 1 (X) = (X) or in our case 1 (A+B') = (A+B')
or in Boolean Algebra terms 1 (A∨¬B) = (A∨¬B)

I will re-write the simplification proof here without the explanation and in electronics terms for clarity:

A+A'B' = (A+A')(A+B') [Distributivity of Disjunction over Conjunction]
(A+A')(A+B') = 1 (A+B') [Dijunction Complementation]
1 (A+B') = (A+B') [Identity Rule of Conjunction]

This is the best explanation I could come up with without relying on anything but pure and simple mathematic laws. A+A'B' is not wrong its just not the MOST simplified version which is what the question asked for. Keep in mind I've never taken a formal Boolean Algebra course but Im certain this is correct. Thanks for everything guys!

Last edited: Feb 3, 2010
7. ### ELECTRONERD AAC Fanatic!

May 26, 2009
1,146
16
I hope your teacher accepts the unquivocal evidence that you are correct; that would be absolutely terrible if he didn't!

All The Best,

Austin

8. ### Fraser_Integration Member

Nov 28, 2009
142
6
That's my Uni!

9. ### StayatHomeElectronics AAC Fanatic!

Sep 25, 2008
1,020
71
There are any number of ways you could have set up the Karnaugh map. And, as long as only one variable is changed at a time, they should yield the same result.

If you use the following setup down the left column instead of the one that you display, there is no wrapping that is needed.

B'A'
B'A
BA
BA'

10. ### thyristor Active Member

Dec 27, 2009
94
0

Your teacher should be complimenting you and accepting that his knowledge went awry. He needs instruction in leadership as well as Karnaugh maps. You not only showed merit in the mathematics but also for not being persuaded by "Group Think" and not just going along with the herd. Instead you showed rugged determination and the courage of your convictions. Great stuff.

11. ### hitmen Active Member

Sep 21, 2008
159
0
Yeah. In college we are taught that the circle must be as big as possible so that more terms are eliminated.