Question 1191166: Simplify the following functions using a K-map
a. F(X,Y, Z) = π ( 0, 2, 5,7)
b. F(X, Y, Z) = XY’Z + X’ + Z + Y’Z’
c. F(W, X, Y, Z) = X’ Y’Z’ + XYZ’ + WXY + W’X’Y’ + WZ
d. F(W, X, Y, Z) = X’ + XZ’ + WX’Y + W’Y’ + WZ
Can you also explain me this second homework step-by-step please? Thank you!
Answer by math_tutor2020(3817)   (Show Source):
You can put this solution on YOUR website!
I'll do part A to get you started.
If you still need help with the others, then please make a new post.
Please post one problem at a time.
The solution page tends to get a bit cluttered when there are multiple problems per post.
Though to be fair, my responses get a bit lengthy/wordy sometimes. I apologize in advance.
========================================================================================================
Part A
Maxterms (3 variables)
| Maxterms | | X | Y | Z | Term | Designation | | 0 | 0 | 0 | X+Y+Z | M0 | | 0 | 0 | 1 | X+Y+Z' | M1 | | 0 | 1 | 0 | X+Y'+Z | M2 | | 0 | 1 | 1 | X+Y'+Z' | M3 | | 1 | 0 | 0 | X'+Y+Z | M4 | | 1 | 0 | 1 | X'+Y+Z' | M5 | | 1 | 1 | 0 | X'+Y'+Z | M6 | | 1 | 1 | 1 | X'+Y'+Z' | M7 |
F(X, Y, Z) = π ( 0, 2, 5,7) ..... product pi function of those listed maxterms
F(X, Y, Z) = M0 * M2 * M5 * M7 .... another way to state the product
F(X, Y, Z) = (M0) * (M2) * (M5) * (M7)
F(X, Y, Z) = (X+Y+Z) * (X+Y'+Z) * (X'+Y+Z') * (X'+Y'+Z') .... use the table above
Let's set up the K-map, more formally known as the Karnaugh Map, but I'll refer to it as K-map from now on.
We have n = 3 literals X,Y,Z.
This yields 2^n = 2^3 = 8 different inner cells of the K-map.
This particular K-map is going to be a table with 2 rows and 4 columns to produce the 2*4 = 8 cells needed.
Along the left side, we'll have 0 and 1 to represent the idea of either X or X' in that order.
This applies to maxterms only.
With minterms, the order would be swapped (0 goes with X' and 1 goes with X).
Along the top we have these values: 00, 01, 11, 10
The order is important.
The first slot is the Y position, and the second slot is the Z position.
0 in the 1st slot means Y, 1 in the 1st slot means Y'
0 in the 2nd slot means Z, 1 in the 2nd slot means Z'
You might be thinking "wait a minute, isn't 11 supposed to be AFTER 10 in binary?".
You'd be correct in thinking that, but I'm instead using Gray Code notation.
More on that is provided at the following links for further reading.
https://www.tutorialspoint.com/what-is-gray-code
https://www.learnabout-electronics.org/Digital/dig16.php#gray
Also, this link
https://www.learnabout-electronics.org/Digital/dig24.php
makes a mention of a gray code sequence as well.
Basically when going from 01 to 11, we only change one binary digit.
Namely, we change the left digit from 0 to 1. Then going from 11 to 10 we flip the right-most bit.
Once again, we change one digit at a time.
Notice that when conventionally counting in binary we have 01 turn into 10 where both bits flip, which is what we don't want.
I'm probably not explaining this very well, but hopefully those links will do a better job to clear up any confusion.
To summarize the table so far, we have:- 0 and 1 as a column on the left most side to represent either X or X' in that order.
- 00, 01, 11, 10 along the top to represent The combos of Y, Y', Z, Z'.
Figure 1 shows what we have so far.
Only the left and top headers are filled in. The actual inner stuff is blank for now.
Now to fill in this table with an intermediate set of expressions. Those expressions being M0 through M7.
We'll combine the headers we made to pinpoint the location of each maxterm.
In the top left corner we have X = 0 and YZ = 00. They combine to XYZ = 000. I'm not multiplying these items. I'm doing string concatenation. My use of notation here is probably a bit unconventional but hopefully you get the idea of what I mean.
Refer to the maxterms chart above to see that (X,Y,Z) = (0,0,0) refers to M0.
As another example, the bottom right corner has X = 1 and YZ = 10 to produce XYZ = 110. This binary number 110 corresponds to M6.
The other M values will follow the same idea.
Once all the M0 through M7 values are in place, you should get what you see in Figure 2 as shown above.
Next we replace the M values with either 0's or 1's.
More specifically we replace the following M terms {M0,M2,M5,M7} with 0s. Everything else gets a 1.
Check out Figure 3 to see what the K-map should look like once it is filled out completely (minus any groupings just yet).
Then in figure 4, I've color-coded the groups as described by the rules/steps mentioned in these links
https://www.learnabout-electronics.org/Digital/dig24.php
https://www.javatpoint.com/simplification-of-boolean-expressions-using-karnaugh-map
There are a few rules to keep in mind, but the idea is to group up the 0s together (this applies to maxterms only).
Each group of zeros has a count of either 1, 2, 4, 8, 16, ... ie some power of 2.
We can only group to the immediate adjacent neighbor but not along any diagonal.
We can span off the edge and end up on the other side to form a group that way, which is how I formed group A.
The first link goes into more detail why we can join up the edges. The link shows a cylinder shape in one of their diagrams to illustrate what's going on.
The goal of simplification is of course to have as few groups as possible.
Now to figure out what to do with the groups (you'll have to pretend that the very bottom of figure 4 didn't spoil the punchline).
In group A, we have X = 0 and Z = 0. This produces the sum X+Z. We use zeros for maxterms for the original literal.
In group B, we have X = 1 and Z = 1. This produces the sum X'+Z'. Ones indicate complements of the original literal.
Therefore, the product of these groups is F(X, Y, Z) = (X + Z)(X' + Z') which is the final answer.
So we can say F(X, Y, Z) = π( 0, 2, 5, 7) = (X + Z)(X' + Z')
Or more thoroughly,
π( 0, 2, 5, 7) = (X+Y+Z) * (X+Y'+Z) * (X'+Y+Z') * (X'+Y'+Z') = (X + Z)(X' + Z')
Notice how Y is nowhere to be found in the simplified product-of-sums answer.
This is because neither the presence of Y nor Y' affect the final outcome based on what the K-map shows.
In the first pink cell of group A (on the left) we have Y = 0; in the right pink cell we have Y = 1.
For both cells mentioned, the result is 0. Hence this is the reason the literal Y doesn't matter, so it can be eliminated.
For similar reasoning, group B doesn't have Y either. The Y is entirely redundant.
If your teacher has introduced circuit analysis, try to draw a circuit diagram so you can spot the visual reason/proof the variable Y is not needed. This is an exercise left to the reader, but feel free to ask if you get stuck.
Here is a useful K-map calculator to check your work.
https://www.charlie-coleman.com/experiments/kmap/
Try not to rely solely on the calculator without having to do any (home)work or thinking beforehand.
Rather, you should only use it when to check your work or perhaps use it when you get stuck somehow.
There are other handy free online calculators as well you can search out, if you prefer.
It appears that calculator only accepts minterms (well the index number of them anyway). So you'll have to keep that in mind for maxterm problems.
Instead of typing in the list of maxterms 0,2,5,7 you would type in the minterms 1,3,4,6.
The calculator has a nice feature to swap between Product-of-Sums and Sum-of-Products formats.
It displays the algebraic notation, as well as of course the Karnaugh Map itself when you scroll down to the bottom of the page.
The map also shows how the terms group up (one marked in pink, the other in light blue).
As you swap between Product-of-Sums and Sum-of-Products formats, the groupings will change but the numbers themselves will stay fixed.
This in my opinion is a very nice way to tie minterms and maxterms together in a visual sense.
------------------------------------------------------------------------------------------------------------------
Here's how you could simplify without the use of a K-map. This is an optional section.
First we'll need a handy reference of Boolean Algebra laws (unless you've memorized them and don't need the table)
| Name | AND form | OR form | | Identity Law | 1*A = A | A+0 = A | | Null Law | 0*A = 0 | A+1 = 1 | | Idempotent Law | A*A = A | A+A = A | | Inverse Law | A*A' = 0 | A+A' = 1 | | Commutative Law | A*B = B*A | A+B = B+A | | Associative Law | A*(B*C) = (A*B)*C | A+(B+C) = (A+B)+C | | Distributive Law | A+B*C = (A+B)*(A+C) | A*(B+C) = A*B+A*C | | Absorption Law | A*(A+B) = A | A+A*B = A | | De Morgan's Law | (A*B)' = A' + B' | (A+B)' = A'*B' |
The star or asterisk symbol is sometimes omitted.
Overhead horizontal bars are sometimes used in place of tickmarks to mean complements.
I'll also be using this standard list of minterms (3 variables)
| Minterms | | X | Y | Z | Term | Designation | | 0 | 0 | 0 | X'Y'Z' | m0 | | 0 | 0 | 1 | X'Y'Z | m1 | | 0 | 1 | 0 | X'YZ' | m2 | | 0 | 1 | 1 | X'YZ | m3 | | 1 | 0 | 0 | XY'Z' | m4 | | 1 | 0 | 1 | XY'Z | m5 | | 1 | 1 | 0 | XYZ' | m6 | | 1 | 1 | 1 | XYZ | m7 |
From there we can say this:
F(X, Y, Z) = π ( 0, 2, 5, 7) ............... product of given maxterms
F(X, Y, Z) = ∑ ( 1, 3, 4, 6) ................ sum of minterms not previously listed
F(X, Y, Z) = m1 + m3 + m4 + m6 ............. translate from sigma form to an actual sum of minterms
F(X, Y, Z) = X'Y'Z + X'YZ + XY'Z' + XYZ' ..... replace each minterm using the table above
F(X, Y, Z) = X'(Y'Z + YZ) + X(Y'Z' + YZ') ....... Distributive Law
F(X, Y, Z) = X'((Y'+Y)Z) + X((Y'+Y)Z') ....... Distributive Law
F(X, Y, Z) = X'((1)Z) + X((1)Z') ....... Inverse Law
F(X, Y, Z) = X'Z + XZ' ....... Identity Law.
F(X, Y, Z) = XZ' + X'Z ....... Commutative Law
F(X, Y, Z) = 0+X*Z'+Z*X'+0 ....... Identity Law
F(X, Y, Z) = X*X'+X*Z'+Z*X'+Z*Z' ....... Inverse Law
F(X, Y, Z) = X(X'+Z')+Z(X'+Z') ....... Distributive Law
F(X, Y, Z) = (X + Z)(X' + Z') ....... Distributive Law
In step 2, I converted to a sum of products because I think that's the easier route to take.
Though of course you might find the product-of-sums method easier.
Product-of-Sums answer format:
F(X, Y, Z) = (X + Z)(X' + Z')
Sum-of-Products answer format:
F(X, Y, Z) = X'Z + XZ'
Since you started with the product pi function, it probably makes sense to stick with the product-of-sums answer format.
Though it's beneficial to know how to go back and forth between each form.
Here is the verification boolean table (which may be optional based on your teacher's requirements).
https://docs.google.com/spreadsheets/d/1dfZ5jU_fWKpOaWb1WYjyAU2I1ykmDqZTiyj81yLNlVo/edit?usp=sharing
You don't need to have a google account to be able to view the page.
Answer to part A is F(X, Y, Z) = (X + Z)(X' + Z')
|
|
|
