CEG-2136: Solution Tutorial-2
Problem: 1-8. Simplify the following Boolean functions using three-variable maps.
a. F(x, y,z) = ∑(0, 1, 5, 7)
To simplify the Boolean function F(x, y, z) = Σ(0, 1, 5, 7) using a Karnaugh map (K-map)
for three variables, we'll construct and fill in the map according to the specified
minterms. Each minterm represents a combination of the variables x, y, and z.
Constructing the K-map:
We organize the K-map using x for the rows and yz for the columns.
x yz
y’z’(00) y’z (01) yz (11) yz’(10)
x’ (0) 1 1 0 0
x(1) 0 1 1 0
Minterm Analysis
1. 0 corresponds to xyz = 000 (x'y'z')
2. 1 corresponds to xyz = 001 (x'y'z)
3. 5 corresponds to xyz = 101 (xy'z)
4. 7 corresponds to xyz = 111 (xyz)
Grouping the 1s:
In the K-map, we aim to group the 1s in rectangles of sizes that are powers of two (1, 2,
4, etc.).
1. Group of Two (0 and 1):
x' y' z' (Minterm 0) ,
x' y' z (Minterm 1)
can be grouped to simplify to x' y' because z is the only changing variable.
So, the simplification would be x'y'.
2. Group of Two (5 and 7):
Similarly,
x y' z (Minterm 5) ,
x y z (Minterm 7)
can be grouped to simplify to x z because y is the only changing variable.
So, the simplification would be xz.
Simplified Expression
Combining the groups: F(x, y, z) = x'y' + xz
d. F(A,B,C) =∑ (0, 2, 3, 4, 6)
Similar to the previous solution the K-map for the given problem is as followings.
Constructing the K-map:
We organize the K-map using A for the rows and BC for the columns.
A \ BC B’C’(00) B’C (01) BC (11) BC’(10)
A’ (0) 1 0 1 1
A(1) 1 0 0 1
Minterm Analysis
1. 0 corresponds to ABC = 000 (A'B'C')
2. 2 corresponds to ABC = 010 (A'BC’)
3. 3 corresponds to ABC = 011 (A'BC)
4. 4 corresponds to ABC = 100 (AB'C')
5. 6 corresponds to ABC = 110 (ABC’)
Grouping the 1s:
1. Group of Four (0, 2, 4, 6):
This group simplifies to C', covering the entire C' column regardless of A or B.
2. Vertical Group of Two (2, 3):
This group simplifies to A'B, covering the instances where A is 0 and only B changes.
Simplified Expression
Combining the groups:
F(A, B, C) = C' + A'B
Problem 1-9. Simplify the following Boolean functions using four-variable maps
c) F(A,B,C,D) = ∑ (0, 1, 2, 4, 5, 7, 11, 15)
Minterm Analysis
0 corresponds to ABCD = 0000 - A′B′C′D′
1 corresponds to ABCD = 0001 - A′B′C′D
2 corresponds to ABCD = 0010 - A′B′CD′
4 corresponds to ABCD = 0100 - A′BC′D′
5 corresponds to ABCD = 0101 - A′BC′D
7 corresponds to ABCD = 0111 - A′BCD
11 corresponds to ABCD = 1011 - AB′CD
15 corresponds to ABCD = 1111 – ABCD
Constructing the K-map:
We organize the K-map using AB for the rows and CD for the columns.
AB \ CD C'D' (00) C'D (01) CD (11) CD' (10)
A'B' (00) 1 1 0 1
A'B (01) 1 1 1 0
AB (11) 0 0 1 0
AB’ (10) 0 0 1 0
Combined Simplified Expression:
F = A'C' + A' B' D'+ ACD+ A'BD or
F= A'C' + A' B' D'+ ACD+ BCD if you take group of CD with A’B and AB
d. F(A,B,C,D) = ∑ (0, 2, 4, 5, 6, 7, 8, 10, 13, 15)
Minterm Analysis:
Here are the minterms and their binary representations:
1. 0 corresponds to ABCD = 0000 - A′B′C′D′
2. 2 corresponds to ABCD = 0010 - A′B′CD′
3. 4 corresponds to ABCD = 0100 - A′BC′D′
4. 5 corresponds to ABCD = 0101 - A′BC′D
5. 6 corresponds to ABCD = 0110 - A′BCD′
6. 7 corresponds to ABCD = 0111 - A′BCD
7. 8 corresponds to ABCD = 1000 - AB′C′D′
8. 10 corresponds to ABCD = 1010 - AB′CD′
9. 13 corresponds to ABCD = 1101 - ABC′D
10. 15 corresponds to ABCD = 1111 – ABCD
Constructing the K-map:
We organize the K-map using AB for the rows and CD for the columns.
AB \ CD C'D' (00) C'D (01) CD (11) CD' (10)
A'B' (00) 1 0 0 1
A'B (01) 1 1 1 1
AB (11) 0 1 1 0
AB’ (10) 1 0 1 1
Grouping the 1s:
• Group 1: minterm 5,7, 13, 15 forms a group and only B and D does not change-
>BD
• Group 2: minterm 0, 2,4,6 forms a group and only A’ and D’ don’t change-> A′D′
• Group 3: minterm 0, 2, 8, and 10 forms a group and only B’ and D’ don’t
change-> B′D′
Simplified Boolean Expression:
F=BD+A′D′+B′D′
1-11. Simplify the following Boolean function in sum-of-products form by means of a
fourvariable map. Draw the logic diagram with (a) AND-OR_gates; (b) NAND gates.
F(A,B,C,D) = ∑ (0, 2, 8, 9, 10, 11, 14, 15)
K-Map:
AB \ CD C'D' (00) C'D (01) CD (11) CD' (10)
A'B' (00) 1 0 0 1
A'B (01) 1 1 1 1
AB (11) 0 1 1 0
AB’ (10) 1 0 1 1
Grouping the 1s:
Group 1: (0, 2, 8, 10) - Forms a group of 4.
Group 2: (9, 11, 14, 15) - Forms a group of 4.
Simplified Expression:
The simplified sum-of-products expression is:
F(A,B,C,D) = B'D' + AC
Logic Diagrams: Next page->
1-13. Simplify the Boolean function F together with the don't-care condition d in (1) sum
of-products form and (2) product-of-sums form. F(w,x,y,z) =∑ (0, 1, 2, 3, 7, 8, 10) , d(w, x,
y, z) = ∑ (5, 6, 11, 15)
Given:
• Function F: F(w,x,y,z) = ∑(0,1,2,3,7,8,10)
• Don't-care d: d(w,x,y,z) = ∑(5,6,11,15)
Karnaugh Map:
y′z′ (00) y′z (01) yz (11) yz′ (10)
w′x′ (00) 1 1 1 1
w′x (01) 1 1 X X
wx (11) 0 0 1 X
wx′ (10) 1 0 0 X
-The minterms (0, 1, 2, 3, 7, 8, 10) are represented by "1" in the map, as these are the
terms we want the function to be true for.
-The don't care conditions (5, 6, 11, 15) are represented by "X" in the map. These are
the minterms where the function's output doesn't matter (it could be 0 or 1).
-We use these "X"s to our advantage during simplification. In SOP, we include them with
"1"s to create larger groups. In POS, we include them with "0"s.
1. Sum-of-Products (SOP) Form
• Prime Implicants (using don't-cares to make larger groups of 1s):
o w' (covers minterms 0, 1, 2, 3)
o w'y'z (covers minterms 0, 8)
o w'xz (covers minterms 3, 7)
o wx'y'z' (covers minterms 8, 10)
• Simplified SOP expression:
F(w,x,y,z) = w' + w'y'z + w'xz + wx'y'z'---Group expanded with X=1
2. Product-of-Sums (POS) Form
• K-Map (same as above):
The maxterms for this problem, based on the K-
map and the way we grouped the zeros, are:
• ∑(4, 9, 12, 13, 14)
Let's break down how we got this:
• Minterms: We were given minterms ∑(0, 1, 2, 3, 7, 8, 10)
• Total Possible Minterms: For 4 variables, there are 2^4 = 16 possible minterms (0
to 15)
• Finding Maxterms: To find the maxterms, we list all the minterms from 0 to 15 a
nd identify the ones not in the original minterm list:
This gives us the maxterms ∑(4, 9, 12, 13, 14)
• Prime Implicants (using don't-cares to make larger groups of 0s):
o y'z' (covers maxterms 12, 13, 14, 15)
o w'z' (covers maxterms 12, 13, 8, 9) -- Group expanded with X=0
• Simplified POS expression:
F(w,x,y,z) = (y' + z')(w' + z')
Important Takeaways:
• Don't cares are useful for simplifying both SOP and POS expressions.
• In SOP, we convert Xs to 1s to make larger groups of 1s.
• In POS, we convert Xs to 0s to make larger groups of 0s.
• Always choose the conversion strategy that leads to the simplest expression for t
he chosen form (SOP or POS).