Section 3.3  Four-Variable K-Map    83
The prime implicants of a function can be obtained from the map by combining all 
possible maximum numbers of squares.  This means that a single 1 on a map represents 
a prime implicant if it is not adjacent to any other 1’s. Two adjacent 1’s form a prime 
implicant, provided that they are not within a group of four adjacent squares. Four 
adjacent 1’s form a prime implicant if they are not within a group of eight adjacent 
squares, and so on. The essential prime implicants are found by looking at each square 
marked with a 1 and checking the number of prime implicants that cover it. The prime 
implicant is essential if it is the only prime implicant that covers the minterm. 
Consider the following four-variable Boolean function: 
F(A, B, C, D) = = ∑(0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15)   
The minterms of the function are marked with 1’s in the maps of  Fig.   3.11   . The partial 
map (Fig. 3.11(a)) shows two essential prime implicants, each formed by collapsing four 
cells into a term having only two literals. One term is essential because there is only one 
way to include minterm    m
0
within four adjacent squares. These four squares define the 
term    BD′.    Similarly, there is only one way that minterm    m
5
can be combined with four 
adjacent squares, and this gives the second term  BD . The two essential prime implicants 
cover eight minterms. The three minterms that were omitted from the partial map 
(   m
3
m
9
,    and    m
11
) must be considered next.  
Figure   3.11   (b) shows all possible ways that the three minterms can be covered with 
prime implicants. Minterm    m
3
can be covered with either prime implicant  CD  or prime 
implicant    BC.    Minterm    m
9
can be covered with either  AD  or    AB′.    Minterm    m
11
is 
covered with any one of the four prime implicants. The simplified expression is obtained 
from the logical sum of the two essential prime implicants and any two prime implicants 
(b) Prime implicants CD,BC,
AD, and AB
00
01
11
10
00
01
11
10
AB
CD
1
1
1
1
1
1
BC
1
1
1
1
1
AB
AD
m
0
m
1
m
3
m
2
m
12
m
13
m
15
m
14
m
8
m
9
m
11
m
10
m
4
m
5
m
7
m
6
C
A
B
CD
Note: ABCD′ + ABCD′= ABD
ABCD′+ ABCD′= ABD
ABD′+ ABD′= BD
(a) Essential prime implicants
BD and BD
1
1
1
1
ABCD
ABCD
ABCD
ABCD
BD
D
D
m
0
m
1
m
3
m
2
m
12
m
13
m
15
m
14
m
8
m
9
m
11
m
10
m
4
m
5
m
7
m
6
00
01
11
10
00
01
11
10
B
C
AB
CD
A
1
1
1
1
FIGURE 3.11 
Simplification using prime implicants       
Convert pdf to ppt online - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
convert pdf file into ppt; convert pdf to powerpoint using
Convert pdf to ppt online - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
and paste pdf to powerpoint; how to add pdf to powerpoint presentation
84    Chapter 3  Gate-Level Minimization
that cover minterms    m
3
m
9
,    and    m
11
.    There are four possible ways that the function can 
be expressed with four product terms of two literals each: 
BD BD′ + CD AD   
BD BD′+ CD AB   
BD BD′ +BAD   
BD BD′ +BAB   
The previous example has demonstrated that the identification of the prime implicants in 
the map helps in determining the alternatives that are available for obtaining a simplified 
expression. 
The procedure for finding the simplified expression from the map requires that we 
first determine all the essential prime implicants. The simplified expression is obtained 
from the logical sum of all the essential prime implicants, plus other prime implicants 
that may be needed to cover any remaining minterms not covered by the essential prime 
implicants. Occasionally, there may be more than one way of combining squares, and 
each combination may produce an equally simplified expression.   
Five-Variable Map 
Maps for more than four variables are not as simple to use as maps for four or fewer 
variables. A five-variable map needs 32 squares and a six-variable map needs 64squares. 
When the number of variables becomes large, the number of squares becomes excessive 
and the geometry for combining adjacent squares becomes more involved.  
Maps for more than four variables are difficult to use and will not be considered here. 
3.4    PRODUCT-OF-SUMS SIMPLIFICATION 
The minimized Boolean functions derived from the map in all previous examples were 
expressed in sum-of-products form. With a minor modification, the product-of-sums 
form can be obtained. 
The procedure for obtaining a minimized function in product-of-sums form follows 
from the basic properties of Boolean functions. The 1’s placed in the squares of the 
map represent the minterms of the function. The minterms not included in the standard 
sum-of-products form of a function denote the complement of the function. From this 
observation, we see that the complement of a function is represented in the map by 
the squares not marked by 1’s. If we mark the empty squares by 0’s and combine them 
into valid adjacent squares, we obtain a simplified sum-of-products expression of the 
complement of the function (i.e., of    F′   ). The complement of    F    gives us back the func-
tion  F  in product-of-sums form (a consequence of DeMorgan’s theorem). Because of 
the generalized DeMorgan’s theorem, the function so obtained is automatically in 
product-of-sums form. The best way to show this is by example. 
Online Convert PowerPoint to PDF file. Best free online export
Online Powerpoint to PDF Converter. Download Free Trial. Convert a PPTX/PPT File to PDF. Just upload your file by clicking on the blue
how to convert pdf to ppt for; how to convert pdf file to powerpoint presentation
How to C#: Convert PDF, Excel, PPT to Word
How to C#: Convert PDF, Excel, PPT to Word. Online C# Tutorial for Converting PDF, MS-Excel, MS-PPT to Word. PDF, MS-Excel, MS-PPT to Word Conversion Overview.
convert pdf file to powerpoint; how to convert pdf into powerpoint presentation
Section 3.4  Product-of-Sums Simplification    85
EXAMPLE3.7 
Simplify the following Boolean function into (a) sum-of-products form and 
(b) product-of-sums form: 
F (ABC, D) = ∑(0, 1, 2, 5, 8, 9, 10)   
The 1’s marked in the map of  Fig.   3.12    represent all the minterms of the function. The 
squares marked with 0’s represent the minterms not included in  F  and therefore denote 
the complement of  F . Combining the squares with 1’s gives the simplified function in 
sum-of-products form: 
(a)      BD′+ BC′+ ACD    
If the squares marked with 0’s are combined, as shown in the diagram, we obtain 
the simplified complemented function: 
F′= AB CD BD   
Applying DeMorgan’s theorem (by taking the dual and complementing each 
literal as described in Section 2.4), we obtain the simplified function in product-
of-sums form:  
(b)      = (A′ + B′) (C′ ′ + D′) (B′+ D)       
The gate-level implementation of the simplified expressions obtained in  Example   3.7    is 
shown in  Fig.   3.13   . The sum-of-products expression is implemented in (a) with a group of 
AND gates, one for each AND term. The outputs of the AND gates are connected to the 
inputs of a single OR gate. The same function is implemented in (b) in its product-of-sums 
1
00
01
11
10
00
01
11
10
B
C
AB
CD
A
1
0
1
1
0
1
1
0
1
D
0
0
0
0
0
0
CD
BCD
AB
BCD
Note: BCD′+ BCD′= BD
m
0
m
1
m
3
m
2
m
6
m
7
m
5
m
4
m
12
m
8
m
13
m
9
m
15
m
14
m
10
m
11
FIGURE 3.12 
Map for  Example   3.7   ,    (A, B, C, D) = ∑(0,1, 2, 5, 8, 9,10)BD′+ BC′ +AC           
(A′+ B′)(C′+ D′)(B′+ D)         
How to C#: Convert Word, Excel and PPT to PDF
How to C#: Convert Word, Excel and PPT to PDF. Online C# Tutorial for Converting MS Office Word, Excel and PowerPoint to PDF. MS Office
how to convert pdf to ppt online; convert pdf to powerpoint presentation
C# PDF Convert: How to Convert MS PPT to Adobe PDF Document
C# PDF Convert: How to Convert MS PPT to Adobe PDF Document. Provide Free Demo Code for PDF Conversion from Microsoft PowerPoint in C# Program.
convert pdf file to powerpoint online; convert pdf slides to powerpoint
86    Chapter 3  Gate-Level Minimization
form with a group of OR gates, one for each OR term. The outputs of the OR gates are 
connected to the inputs of a single AND gate. In each case, it is assumed that the input 
variables are directly available in their complement, so inverters are not needed. The con-
figuration pattern established in  Fig.   3.13    is the general form by which any Boolean function 
is implemented when expressed in one of the standard forms. AND gates are connected 
to a single OR gate when in sum-of-products form; OR gates are connected to a single 
AND gate when in product-of-sums form. Either configuration forms two levels of gates. 
Thus, the implementation of a function in a standard form is said to be a two-level imple-
mentation. The two-level implementation may not be practical, depending on the number 
of inputs to the gates. 
Example   3.7    showed the procedure for obtaining the product-of-sums simplifica-
tion when the function is originally expressed in the sum-of-minterms canonical form. 
The procedure is also valid when the function is originally expressed in the product-
of-maxterms canonical form. Consider, for example, the truth table that defines the 
function  F  in  Table   3.1   . In sum-of-minterms form, this function is expressed as 
F (xy, z) = = ∑(1, 3, 4, 6)   
F
B
D
C
A
D
F
A
B
C
D
D
(a) F = BD′ + BC + ACD
(b) F =(A′ + B′) (C′+ D′) (B′ + D)
FIGURE 3.13 
Gate implementations of the function of  Example   3.7          
Table 3.1 
Truth Table of Function F 
C# TIFF: Learn to Convert MS Word, Excel, and PPT to TIFF Image
PPTXDocument doc = new PPTXDocument(@"demo.pptx"); if (null == doc) throw new Exception("Fail to load PowerPoint Document"); // Convert PPT to Tiff.
convert pdf into ppt; converting pdf to powerpoint slides
VB.NET PowerPoint: Process & Manipulate PPT (.pptx) Slide(s)
This VB.NET online tutorial page can help you processing control add-on can do PPT creating, loading powerful & profession imaging controls, PDF document, image
convert pdf to ppt online without email; how to convert pdf to powerpoint on
Section 3.4  Product-of-Sums Simplification    87
In product-of-maxterms form, it is expressed as 
F (x, y, z) =(0, 2, 5, 7)   
In other words, the 1’s of the function represent the minterms and the 0’s represent 
the maxterms. The map for this function is shown in  Fig.   3.14   . One can start simplify-
ing the function by first marking the 1’s for each minterm that the function is a 1. The 
remaining squares are marked by 0’s. If, instead, the product of maxterms is initially 
given, one can start marking 0’s in those squares listed in the function; the remaining 
squares are then marked by 1’s. Once the 1’s and 0’s are marked, the function can be 
simplified in either one of the standard forms. For the sum of products, we combine 
the 1’s to obtain 
x+xz   
For the product of sums, we combine the 0’s to obtain the simplified complemented 
function 
F′ = xz xz
which shows that the exclusive-OR function is the complement of the equivalence func-
tion (Section 2.6). Taking the complement of    F′,    we obtain the simplified function in 
product-of-sums form: 
= (x′ + z′)(xz)   
To enter a function expressed in product-of-sums form into the map, use the comple-
ment of the function to find the squares that are to be marked by 0’s. For example, the 
function 
=(A′+ B′ + C′)(BD)   
can be entered into the map by first taking its complement, namely, 
F′= ABCBD   
0
1
00
01
11
10
z
y
x
yz
x
1
0
0
1
1
1
0
0
xz
xz
m
0
m
1
m
3
m
2
m
4
m
5
m
7
m
6
FIGURE 3.14 
Map for the function of  Table   3.1          
VB.NET PowerPoint: Convert & Render PPT into PDF Document
VB.NET PowerPoint - Render PPT to PDF in VB.NET. How to Convert PowerPoint Slide to PDF Using VB.NET Code in .NET. Visual C#. VB.NET. Home > .NET Imaging SDK >
pdf to powerpoint converter online; pdf to ppt
VB.NET PowerPoint: Read & Scan Barcode Image from PPT Slide
VB.NET PPT PDF-417 barcode scanning SDK to detect PDF-417 barcode image from PowerPoint slide. VB.NET APIs to detect and decode
convert pdf slides to powerpoint online; pdf to powerpoint conversion
88    Chapter 3  Gate-Level Minimization
and then marking 0’s in the squares representing the minterms of    F′.    The remaining 
squares are marked with 1’s.  
3.5    DON’T-CARE CONDITIONS 
The logical sum of the minterms associated with a Boolean function specifies the con-
ditions under which the function is equal to 1. The function is equal to 0 for the rest of 
the minterms. This pair of conditions assumes that all the combinations of the values 
for the variables of the function are valid. In practice, in some applications the function 
is not specified for certain combinations of the variables. As an example, the four-bit 
binary code for the decimal digits has six combinations that are not used and conse-
quently are considered to be unspecified. Functions that have unspecified outputs for 
some input combinations are called  incompletely specified functions . In most applica-
tions, we simply don’t care what value is assumed by the function for the unspecified 
minterms. For this reason, it is customary to call the unspecified minterms of a function 
don’t-care conditions . These don’t-care conditions can be used on a map to provide 
further simplification of the Boolean expression. 
A don’t-care minterm is a combination of variables whose logical value is not speci-
fied. Such a minterm cannot be marked with a 1 in the map, because it would require 
that the function always be a 1 for such a combination. Likewise, putting a 0 on the 
square requires the function to be 0. To distinguish the don’t-care condition from 1’s and 
0’s, an  X  is used. Thus, an  X  inside a square in the map indicates that we don’t care 
whether the value of 0 or 1 is assigned to  F  for the particular minterm. 
In choosing adjacent squares to simplify the function in a map, the don’t-care min-
terms may be assumed to be either 0 or 1. When simplifying the function, we can choose 
to include each don’t-care minterm with either the 1’s or the 0’s, depending on which 
combination gives the simplest expression. 
EXAMPLE3.8 
Simplify the Boolean function 
F (wxy, z) = = ∑(1, 3, 7, 11, 15)   
which has the don’t-care conditions 
d (wxyz) = = ∑(0, 2, 5)   
The minterms of  F  are the variable combinations that make the function equal to 1. The 
minterms of  d  are the don’t-care minterms that may be assigned either 0 or 1. The map 
simplification is shown in  Fig.   3.15   . The minterms of  F  are marked by 1’s, those of  d  are 
marked by X’s, and the remaining squares are filled with 0’s. To get the simplified expres-
sion in sum-of-products form, we must include all five 1’s in the map, but we may or may 
not include any of the X’s, depending on the way the function is simplified. The term  yz  
covers the four minterms in the third column. The remaining minterm,    m
1
,    can be combined 
Section 3.5  Don’t-Care Conditions    89
with minterm    m
3
to give the three-literal term    wxz.    However, by including one or 
twoadjacent X’s we can combine four adjacent squares to give a two-literal term. In 
Fig.3.15(a), don’t-care minterms 0 and 2 are included with the 1’s, resulting in the simpli-
fied function 
yz wx   
In Fig. 3.15(b), don’t-care minterm 5 is included with the 1’s, and the simplified func-
tion is now 
yzwz   
Either one of the preceding two expressions satisfies the conditions stated for this 
example.  
The previous example has shown that the don’t-care minterms in the map are ini-
tially marked with X’s and are considered as being either 0 or 1. The choice between 0 
and 1 is made depending on the way the incompletely specified function is simplified. 
Once the choice is made, the simplified function obtained will consist of a sum of min-
terms that includes those minterms which were initially unspecified and have been 
chosen to be included with the 1’s. Consider the two simplified expressions obtained 
in  Example   3.8   : 
F (w, xy, z) =yz wx′= ∑(0, 1, 2, 3, 7, 11, 15)
F (wxyz) =yz wz = = ∑(1, 3, 5, 7, 11, 15)   
Both expressions include minterms 1, 3, 7, 11, and 15 that make the function  F  equal 
to 1. The don’t-care minterms 0, 2, and 5 are treated differently in each expression. 
m
0
m
1
m
3
m
2
m
12
m
13
m
15
m
14
m
8
m
9
m
11
m
10
m
4
m
5
m
7
m
6
00
01
11
10
00
01
11
10
x
y
wx
yz
w
1
1
X
0
X
X
1
0
0
0
1
0
0
1
0
0
wz
yz
z
00
01
11
10
00
01
11
10
wx
yz
z
X
1
1
X
0
X
1
0
0
0
1
0
0
1
0
0
wx
yz
x
w
y
m
0
m
1
m
3
m
2
m
12
m
13
m
15
m
14
m
8
m
9
m
11
m
10
m
4
m
5
m
7
m
6
(a)Fyzwx
(b)Fyz+ wz
FIGURE 3.15 
Example with don’t-care conditions       
90    Chapter 3  Gate-Level Minimization
The first expression includes minterms 0 and 2 with the 1’s and leaves minterm 5 with 
the 0’s. The second expression includes minterm 5 with the 1’s and leaves minterms 0 
and 2 with the 0’s. The two expressions represent two functions that are not algebra-
ically equal. Both cover the specified minterms of the function, but each covers dif-
ferent don’t-care minterms. As far as the incompletely specified function is concerned, 
either expression is acceptable because the only difference is in the value of  F  for the 
don’t-care minterms. 
It is also possible to obtain a simplified product-of-sums expression for the function 
of  Fig.   3.15   . In this case, the only way to combine the 0’s is to include don’t-care minterms 
0 and 2 with the 0’s to give a simplified complemented function: 
F′ =z′+ wy   
Taking the complement of    F′    gives the simplified expression in product-of-sums form: 
F (w, x, yz) = z(w′ ′ +y) = = ∑(1, 3, 5, 7, 11, 15)   
In this case, we include minterms 0 and 2 with the 0’s and minterm 5 with the 1’s.  
3.6    NAND AND NOR IMPLEMENTATION 
Digital circuits are frequently constructed with NAND or NOR gates rather than with 
AND and OR gates. NAND and NOR gates are easier to fabricate with electronic 
components and are the basic gates used in all IC digital logic families. Because of the 
prominence of NAND and NOR gates in the design of digital circuits, rules and proce-
dures have been developed for the conversion from Boolean functions given in terms 
of AND, OR, and NOT into equivalent NAND and NOR logic diagrams. 
NAND Circuits 
The NAND gate is said to be a  universal  gate because any logic circuit can be imple-
mented with it. To show that any Boolean function can be implemented with NAND 
gates, we need only show that the logical operations of AND, OR, and complement can 
be obtained with NAND  gates alone. This is indeed shown in  Fig.   3.16   .  The complement 
operation is obtained from a one-input NAND gate that behaves exactly like an inverter. 
The AND operation requires two NAND gates. The first produces the NAND operation 
and the second inverts the logical sense of the signal. The OR operation is achieved 
through a NAND gate with additional inverters in each input. 
A convenient way to implement a Boolean function with NAND gates is to obtain 
the simplified Boolean function in terms of Boolean operators and then convert the 
function to NAND logic.  The conversion of an algebraic expression from AND, OR, and 
complement to NAND can be done by simple circuit manipulation techniques that 
change AND–OR diagrams to NAND diagrams. 
To facilitate the conversion to NAND logic, it is convenient to define an alternative 
graphic symbol for the gate. Two equivalent graphic symbols for the NAND gate are 
shown in  Fig.   3.17   . The AND-invert symbol has been defined previously and consists 
Section 3.6  NAND and NOR Implementation    91
of an AND graphic symbol followed by a small circle negation indicator referred to as 
a bubble. Alternatively, it is possible to represent a NAND gate by an OR graphic 
symbol that is preceded by a bubble in each input. The invert-OR symbol for the 
NAND gate follows DeMorgan’s theorem and the convention that the negation indica-
tor (bubble) denotes complementation. The two graphic symbols’ representations are 
useful in the analysis and design of NAND circuits. When both symbols are mixed in 
the same diagram, the circuit is said to be in mixed notation. 
Two-Level Implementation 
The implementation of Boolean functions with NAND gates requires that the functions 
be in sum-of-products form.  To see the relationship between a sum-of-products expres-
sion and its equivalent NAND implementation, consider the logic diagrams drawn in 
Fig.   3.18   . All three diagrams are equivalent and implement the function 
AB CD   
The function is implemented in Fig. 3.18(a) with AND and OR gates. In Fig. 3.18(b), the 
AND gates are replaced by NAND gates and the OR gate is replaced by a NAND gate 
with an OR-invert graphic symbol. Remember that a bubble denotes complementation 
and two bubbles along the same line represent double complementation, so both can be 
removed. Removing the bubbles on the gates of (b) produces the circuit of (a). Therefore, 
the two diagrams implement the same function and are equivalent. 
(xy′)′ = x+ y
y
x
x
x
y
xy
x
Inverter
AND
OR
FIGURE 3.16 
Logic operations with NAND gates       
x
y
z
(xyz)′
x
y
z
x′ + y′ + z′ = (xyz)′
(a) AND-invert 
(b) Invert-OR
FIGURE 3.17 
Two graphic symbols for a three-input NAND gate       
92    Chapter 3  Gate-Level Minimization
In  Fig.   3.18   (c), the output NAND gate is redrawn with the AND-invert graphic symbol. 
In drawing NAND logic diagrams, the circuit shown in either Fig. 3.18(b) or (c) is accept-
able. The one in Fig. 3.18(b) is in mixed notation and represents a more direct relationship 
to the Boolean expression it implements. The NAND implementation in  Fig.   3.18   (c) can 
beverified algebraically. The function it implements can easily be converted to sum- of-
products form by DeMorgan’s theorem: 
= ((AB)′(CD)′)′= ABCD   
EXAMPLE3.9 
Implement the following Boolean function with NAND gates: 
F (x, yz) = (1, 2, 3, 4, 5, 7)   
The first step is to simplify the function into sum-of-products form. This is done by 
means of the map of  Fig.   3.19   (a), from which the simplified function is obtained: 
xy′+ x+z   
The two-level NAND implementation is shown in  Fig.   3.19   (b) in mixed notation. Note 
that input  z  must have a one-input NAND gate (an inverter) to compensate for the 
bubble in the second-level gate. An alternative way of drawing the logic diagram is given 
in  Fig.  3.19   (c). Here, all the NAND gates are drawn with the same graphic symbol. The 
inverter with input z  has been removed, but the input variable is complemented and 
denoted by    z′.     
(a)
C
D
A
B
F
F
(b)
C
D
A
B
(c)
C
D
A
B
F
FIGURE 3.18 
Three ways to implement  = AB + CD        
Documents you may be interested
Documents you may be interested