3.

1 Simplify the following Boolean functions, using three-variable maps:

(a) F(x, y, z) = ∑(0, 1, 6, 7)

0 1 3 2
1 1
4 5 7 6
1 1

F = x’y’ + xy

(b) F(x, y, z) = ∑(0, 1, 3, 4, 5)

0 1 3 2
1 1 1
4 5 7 6
1 1

F = y’ + x’z
(c) F(x, y, z) = ∑(1, 3, 5, 7)

0 1 3 2
1 1
4 5 7 6
1 1

F=z
(d) F(x, y, z) = ∑(1, 4, 5, 6, 7)

0 1 3 2
1
4 5 7 6
1 1 1 1

F = x + y’z
(e) F(x, y, z) = xy + x’y’z’ + x’yz’
11 000 010

0 1 3 2
1 1

4 5 7 6
1 1

F = xy + x’z’

(f) F(x, y, z) = x’y’ + yz + x’yz’

00 11 010

0 1 3 2
1 1 1 1
4 5 7 6
1

F = x’ + yz

(g) F(x, y, z) = x’y + yz’ + y’z’

0 1 10 00

0 1 3 2
1 1 1
4 5 7 6
1 1

F = z’ + x’y
(h) F(x, y, z) = xyz + x’y’z + xyz’
111 001 110

0 1 3 2
1
4 5 7 6
1 1

F = xy + x’y’z

3.2 Simplify the following Boolean functions, using four-variable maps:

(a) F(A, B, C, D) =∑(1, 5, 9, 10, 11, 14, 15)

0 1 3 2
1
4 5 7 6
1
12 13 15 14
1 1
8 9 11 10
1 1 1

F = AC + AB’D + A’C’D

(b) F (A, B, C, D) =∑(0, 1, 4, 5, 6, 7, 8, 9)

0 1 3 2
1 1
4 5 7 6
1 1 1 1
12 13 15 14

8 9 11 10
1 1
3.3 Simplify the following Boolean functions, using four-variable maps:
(a) A'B'C'D' + A'CD' + AB'D' + ABCD + A'BD
0 0 0 0 010 100 1111 011

0 1 3 2
1 1
4 5 7 6
1 1 1
12 13 15 14
1
8 9 11 10
1 1

F = A’BD + BCD + A’CD’ + B’D’

(b) A'B'C'D' + AB’C + B'CD' + ABCD’ + BC'D

0 0 0 0 1 0 1 0 1 0 1110 101

0 1 3 2
1 1
4 5 7 6
1
12 13 15 14
1 1
8 9 11 10
1 1

F = AB’C + ACD’ + BC’D + A’B’D’

(c) AB'C + B'C'D' + BCD + ACD' + A'B'C + A'BC'D
1 0 1 000 111 11 0 001 0101

0 1 3 2
1 1 1
4 5 7 6
1 1
12 13 15 14
1 1
8 9 11 10
1 1 1

F = CD + A’BD + AC + B’D’

(d) xyz + wy + wxy’ + x’y

111 11 110 01

0 1 3 2
1 1
4 5 7 6
1
12 13 15 14
1 1 1 1
8 9 11 10
1 1

F = wx + yz + x’y
3.4 Find all the prime implicants for the following Boolean functions, and
determine which are essential:

(a) F (w, x, y, z) =∑(0, 2, 4, 5, 6, 7, 8, 10, 13, 15)

0 1 3 2
1 1
4 5 7 6
1 1 1 1
12 13 15 14
1 1
8 9 11 10
1 1

Essential Prime: x’z’, xz

Prime Implicants : x’z’ , xz , w’x , w’z’

(b) F (A, B, C, D) =∑(0, 2, 3, 5, 7, 8, 10, 11, 14, 15)

0 1 3 2
1 1 1
4 5 7 6
1 1
12 13 15 14
1 1
8 9 11 10
1 1 1

Essential Prime : A’BD , B’D’

Prime Implicants : AC , CD , B’D’ , A’BD
(c) F (A, B, C, D) =∑(1, 3, 4, 5, 10, 11, 12, 13, 14, 15)
0 1 3 2
1 1
4 5 7 6
1 1
12 13 15 14
1 1 1 1
8 9 11 10
1 1

Essential Prime : A’B’D , AC , BC’

Prime Implicants : AC , AB , BC’ , A’B’D

(d) F (w,x,y,z) =∑(1, 3, 6, 7, 8, 9, 12, 13, 14, 15)

0 1 3 2
1 1
4 5 7 6
1 1
12 13 15 14
1 1 1 1
8 9 11 10
1 1

Essential Prime : w’x’z , xy , wy’

Prime Implicants : wx , wy’ , xy , w’x’z
(e) F (A, B, C, D) =∑(0, 2, 3, 5, 7, 8, 10, 11, 13, 15)
0 1 3 2
1 1 1
4 5 7 6
1 1
12 13 15 14
1 1
8 9 11 10
1 1 1

Essential Prime : B’D’ , BD , CD

Prime Implicants : B’D’ , BD , CD , B’C’D’

(f) F (w,x,y,z) =∑(0, 2, 7, 8, 9, 10, 12, 13, 14, 15)

0 1 3 2
1 1
4 5 7 6
1
12 13 15 14
1 1 1 1
8 9 11 10
1 1 1

Essential Prime : x’z’ , xyz , wy’

Prime Implicants : wx , x’z’ , xyz , wy’
3.5 Simplify the following Boolean function F, together with the don’t-care
conditions d, and then express the simplified function in sum-of-minterms
form: a) F(x, y, z) = ∑(0, 1, 3, 5, 7) , d(x, y, z) = ∑(2, 4, 6)

0 1 3 2
1 1 1 X
4 5 7 6
X 1 1 X

b) F(A,B,C,D) = ∑(0, 4, 8, 10, 14) , d(A,B,C,D) = ∑(2, 6, 12)

0 1 3 2
1 X
4 5 7 6
1 X
12 13 15 14
X 1
8 9 11 10
1 1

c) F(A,B,C,D) = ∑(5, 6, 7, 11, 14, 15) , d(A,B,C,D) = ∑(3, 9, 13)

0 1 3 2
X
4 5 7 6
1 1 1
12 13 15 14
X 1 1
8 9 11 10
X 1
d) F(A,B,C,D) = ∑(2, 4, 7, 10, 12, 14) , d(A,B,C,D) = ∑(0, 3, 6, 8, 13)

0 1 3 2
X X 1
4 5 7 6
1 1 X
12 13 15 14
1 X 1
8 9 11 10
X 1

3.6 Simplify the following functions and implement them with two-level
NAND gate circuits:
(a) F(A, B, C, D) = A’B’C + AC’ + ACD + ACD’ + A’B’D’
0 0 1 10 111 11 0 000

0 1 3 2
1 1 1
4 5 7 6

12 13 15 14
1 1 1 1
8 9 11 10
1 1 1 1

F = A + B’D’ + B’C
(b) F(A, B, C, D) = AB + A’BC + A’B’C’D
11 011 0 0 0 1

0 1 3 2
1
4 5 7 6
1 1
12 13 15 14
1 1 1 1
8 9 11 10

F = BC + AB + A’B’C’D

3.7 Draw a logic diagram using only two-input NOR gates to implement the
following function : 𝐹(𝐴, 𝐵, 𝐶,𝐷) = (𝐴⨁𝐵) ′ (𝐶⨁𝐷)
(𝐴⨁𝐵) ′ (𝐶⨁𝐷) = ( AB + A’B’ ) ( CD’ + C’D )
= ABCD’ + ABC’D + A’B’CD’+ A’B’C’D
1110 1101 0010 0001

F = ∑ (1, 2, 13, 14)

F' = w'x + wx' + y'z' + yz = [(w +x')(w' + x)(y + z)(y' + z')]'
F = (w +x')' + (w' + x)' + (y + z)' + (y' + z')
3.8 Draw the multi-level NOR and multi- level NAND circuits for the
following expression: (𝐴𝐵 ′ + 𝐶𝐷 ′ )𝐸 + 𝐵𝐶(𝐴 + 𝐵)
Multi-level NOR: F = (AB' + CD')E + BC(A + B)
F' = [(AB' + CD')E + BC(A + B)]'
F' = [ [(AB' + CD')' + E']' + [ (BC)' + (A + B)']' ]'
F' = [ [((A' + B)' + (C' + D)')' + E']' + [ (B' + C')' + (A + B)']' ]'

Multi-level NAND: F = (AB' + CD')E + BC(A + B)

F' = [ (AB' + CD')E]' [BC(A + B)]'
F' = [ ( (AB')'( CD')' )'E]' [BC(A'B')']'

3.12 Simplify the following Boolean functions to a product of sum

(a) F(w, x, y, z) = ∑(0, 1, 2, 5, 8, 10, 13)
F = π( 3, 4, 6, 7, 9, 11, 12, 14, 15 )

0 1 3 2
0
4 5 7 6
0 0 0
12 13 15 14
0 0 0
8 9 11 10
0 0

F’ = xz’ + yz + wx’z
F = ( x’+ z ) ( y’ + z’ ) ( w’ + x + z’ )
(b) F(A, B, C, D) = π( 1, 3, 5, 7, 13, 15 )

0 1 3 2
0 0
4 5 7 6
0 0
12 13 15 14
0 0
8 9 11 10

(c) F(A, B, C, D) = π( 1, 3, 6, 9, 11, 12, 14 )

0 1 3 2
0 0
4 5 7 6
0
12 13 15 14
0 0
8 9 11 10
0 0

3.13 Simplify the following Boolean functions to sum of products ( SOP ) and
product of sums ( POS )
(a) x’z’ + y’z’ + yz’ + xy
00 0 0 10 11

0 1 3 2
1 1
4 5 7 6
1 1 1
(b) ACD’ + C’D + AB’ + ABCD
110 0 1 10 1111

0 1 3 2 0 1 3 2
1 0 0 0
4 5 7 6 4 5 7 6
1 0 0 0
12 13 15 14 12 13 15 14
1 1 1 0
8 9 11 10 8 9 11 10
1 1 1 1

F’ = A’C + BCD’ + A’D’

F = C’D + AC’ + AD + AB’C F = ( A + C’ ) ( B’ + C’ + D ) ( A + D )

(c) ( A + C’ + D’ ) ( A’ + B’ + D’ ) ( A’ + B + D’ ) ( A’ + B + C’ )

0 1 3 2 0 1 3 2
1 1 1 0
4 5 7 6 4 5 7 6
1 1 1 0
12 13 15 14 12 13 15 14
1 1 0 0
8 9 11 10 8 9 11 10
1 0 0 0

F’ = CD + AD + AB’C
F = A’C’ + C’D’ + A’D’ + BD’ F = ( C’ + D’ ) ( A’ + D’ ) ( A’ + B + C’ )
(d) ABC’ + AB’D + BCD
1 1 0 1 0 1 1 1 1

0 1 3 2 0 1 3 2
0 0 0 0
4 5 7 6 4 5 7 6
1 0 0 0
12 13 15 14 12 13 15 14
1 1 1 0
8 9 11 10 8 9 11 10
1 1 0 0

F’ = CD’ + A’B’ + A’C’ + B’C’D’

F = AD + ABC’ + BCD F = ( C’+D ) ( A+B ) ( A +C ) ( B+C +D )

By : N.Y