What is the Simplification of a Boolean Function Using Karnaugh Maps?

[Femme_physics]

Homework Statement

Given the function:


http://img26.imageshack.us/img26/9718/elel0.jpg

A) Write the truth table of the function F (A, B, C, D)

B) Present the function F (A, B, C, D) via Karnaugh Map

C) Express the function F as the sum of multiplications with minimum literals

D) Realize the minimized function F via logic gates

The Attempt at a Solution

I just want to see if I got it right :)
http://img84.imageshack.us/img84/1940/elel1.jpg

http://img577.imageshack.us/img577/1851/elel2.jpg

 

[NascentOxygen]

See your gate arrangement--you have used two NOT gates to twice produce B'. This is unnecessary duplication.

I can't say much about your Karnaugh map, I need to revise that topic myself. :( But I can see that your equation F= AB + B'C + B'C'D' does not match your truth table. Isn't it supposed to??

 

[NascentOxygen]

let's take as correct, your equation F= AB + B'C + B'C'D'

take out as a factor B' --> F = AB + B'(C + C'D')

consider that last term, B'(C + C'D')

when C is true, the bracketed term evaluates as true
when C is false, the bracketed term evaluates as D

so I think there should be some algebra reduction that allows you to make this

F = AB + B'(C + D')

 

[NascentOxygen]

Here's how to go about demonstrating this. After you've been shown once, you'll probably be able to figure it out for yourself thereafter.

let's focus on the term in brackets,
C + ¬C¬D

EDITED:
Consider two basic logic relations:
you can OR anything with TRUE and it's still TRUE
you can AND anything with TRUE and it doesn't change its value
= C ( 1 + ¬D) + ¬C¬D

remove the brackets
= C + C¬D + ¬C¬D

take out a common factor ¬D
= C + ¬D (C + ¬C)

what's in brackets evaluates as always TRUE, so simplifies to
= C + ¬D

 

[Femme_physics]

you can OR anything with TRUE and it's still TRUE
= C ( 1 + ¬D) + ¬C¬D

remove the brackets
= C + C¬D + ¬C¬D

I never heard this "Or everything" rule in our Boolean algebra. Could our teacher only want us to use the basic list he gave us?

See your gate arrangement--you have used two NOT gates to twice produce B'. This is unnecessary duplication.

Point taken.

I can't say much about your Karnaugh map, I need to revise that topic myself. :( But I can see that your equation F= AB + B'C + B'C'D' does not match your truth table. Isn't it supposed to??

I don't know how to relate truth tables to functions, only functions to Karnaugh Maps and Karnaugh Maps to truth tables. Is it even possible?

 

[I like Serena]

But I can see that your equation F= AB + B'C + B'C'D' does not match your truth table. Isn't it supposed to??

I believe that expression does match the truth table.
Your truth table is fine, your Karnaugh table is fine, your function is fine and your circuit is fine. Btw, you can construct a truth table from a function.
Just start with every combination of A, B, C, and D, which you already have in your current truth table.
If you want, introduce a couple of intermediary results.
Then calculate the result of the function for each combination of A, B, C, and D.

I never heard this "Or everything" rule in our Boolean algebra. Could our teacher only want us to use the basic list he gave us?

Which basic list did he give you?
It should include that (1 + a) is always true, that is, it is equal to 1.
Btw, can't you put in a drawing of something? Anything? A beetle would do.

 

[NascentOxygen]

I never heard this "Or everything" rule

Oops, oops, oops! I left out half the explanation in that step.

I meant to also add:
You can AND anything with TRUE and you don't change its value.

Sorry for the oversight.

 

[I like Serena]

Oops, oops, oops!

I meant to type AND. You can AND anything with TRUE and you don't change its value.

Sorry, now you are going to have to go through the process of unlearning from my typo! I hate that.

Uhh :uhh:... where's the typo?

 

[NascentOxygen]

where's the typo?

Fixed now.

 

[NascentOxygen]

I overlooked the distinction between Ø and O so was just a little puzzled. Now I recognize you used Ø for your "don't care" states. So all is correct.

F = AB + B'(C + D')
⇔ F = AB + B'C + B'D'

 

[Femme_physics]

I overlooked the distinction between Ø and O so was just a little puzzled. Now I recognize you used Ø for your "don't care" states. So all is correct.

F = AB + B'(C + D')
⇔ F = AB + B'C + B'D'

:) Thank you!

 

[Ninty64]

The simplification in the equation could have also been obtained by grouping the four corners on the Karnaugh map instead of just boxes 0 and 8.

I didn't see anyone else mention it, so I thought I would throw that out there