Section 2.6  Canonical and Standard Forms    53
truthtable Since the function can be either 1 or 0 for each minterm, and since there are 
2
n
minterms, one can calculate all the functions that can be formed with n variables to 
be    2
2n
.    It is sometimes convenient to express a Boolean function in its sum‐of‐minterms 
form. If the function is not in this form, it can be made so by first expanding the expres-
sion into a sum of AND terms. Each term is then inspected to see if it contains all the 
variables. If it misses one or more variables, it is ANDed with an expression such as 
x′,    where x is one of the missing variables. The next example clarifies this procedure. 
EXAMPLE 2.4 
Express the Boolean function    =BC    as a sum of minterms. The function has 
three variables: AB, and C. The first term A is missing two variables; therefore, 
=A(+B′) = ABAB   
This function is still missing one variable, so 
AAB(C′) + AB′(+C′)
ABC ABC′+ ABABC   
The second term    BC    is missing one variable; hence, 
BBC(+A′) = AB+ABC   
Combining all terms, we have 
ABC
ABC +ABC′+ AB+ABC′+ ABC   
But    ABC    appears twice, and according to theorem    1 (xx),    it is possible to 
remove one of those occurrences. Rearranging the minterms in ascending order, we 
finally obtain 
ABABCABABC′+ ABC
m
1
m
4
m
5
+m
6
m
7
When a Boolean function is in its sum‐of‐minterms form, it is sometimes convenient to 
express the function in the following brief notation: 
F(ABC) = = ∑(1, 4, 5, 6, 7)   
The summation symbol    g    stands for the ORing of terms; the numbers following it are 
the indices of the minterms of the function. The letters in parentheses following F form 
a list of the variables in the order taken when the minterm is converted to an AND term. 
An alternative procedure for deriving the minterms of a Boolean function is to obtain 
the truth table of the function directly from the algebraic expression and then read the 
minterms from the truth table.  Consider the Boolean function given in Example 2.4: 
ABC   
The truth table shown in  Table   2.5    can be derived directly from the algebraic expres-
sion by listing the eight binary combinations under variables AB, and C and inserting 
Convert pdf to editable ppt - 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
adding pdf to powerpoint slide; convert pdf to ppt online without email
Convert pdf to editable ppt - 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
adding pdf to powerpoint; converting pdf to powerpoint online
54    Chapter 2  Boolean Algebra and Logic Gates
1’s under F for those combinations for which    A= 1    and    BC = 01.    From the truth table, 
we can then read the five minterms of the function to be 1, 4, 5, 6, and 7. 
Product of Maxterms 
Each of the    2
2n
functions of n binary variables can be also expressed as a product of 
maxterms.  To express a Boolean function as a product of maxterms, it must first be 
brought into a form of OR terms. This may be done by using the distributive law, 
yz= (y)(xz).    Then any missing variable x in each OR term is ORed with 
xx′.    The procedure is clarified in the following example. 
EXAMPLE 2.5 
Express the Boolean function    xy xz    as a product of maxterms. First, convert 
the function into OR terms by using the distributive law: 
xyx= (xy x′)(xyz)
= (x′)(yx′)(z)(+z)
=(x′+ y)(z)(+z)   
The function has three variables: xy, and z. Each OR term is missing one variable; 
therefore, 
x′+ x′ +zz′= (x′+ +z)(x′+ z′)
++yy′= (yz)(y′ + z)
++xx′= (yz)(x′+ z)   
Combining all the terms and removing those which appear more than once, we finally 
obtain 
= (+z)(y′+ z)(x′+ yz)(x′+ z′)
M
0
M
2
M
4
M
5
Table 2.5
Truth Table for F BC
A
B
C
F
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
Online Convert PDF to Text file. Best free online PDF txt
RasterEdge PDF document conversion SDK provides reliable and effective .NET solution for Visual C# developers to convert PDF document to editable & searchable
convert pdf to powerpoint online no email; pdf to ppt converter online for large
Section 2.6  Canonical and Standard Forms    55
A convenient way to express this function is as follows: 
F(xy, z) = (0, 2, 4, 5)   
The product symbol,    ,    denotes the ANDing of maxterms; the numbers are the indices 
of the maxterms of the function.   
Conversion between Canonical Forms 
The complement of a function expressed as the sum of minterms equals the sum of min-
terms missing from the original function. This is because the original function is expressed 
by those minterms which make the function equal to 1, whereas its complement is a 1 for 
those minterms for which the function is a 0. As an example, consider the function 
F(ABC) = = ∑(1, 4, 5, 6, 7)   
This function has a complement that can be expressed as 
F′(ABC) = ∑(0, 2, 3) ) =m
0
m
2
m
3
Now, if we take the complement of    F′    by DeMorgan’s theorem, we obtain F in a differ-
ent form: 
= (m
0
+m
2
m
3
)′= m
=
0
#
m
=
2
#
m
=
3
M
0
M
2
M
3
=(0, 2, 3)   
The last conversion follows from the definition of minterms and maxterms as shown in 
Table   2.3   . From the table, it is clear that the following relation holds:  
m
=
j
M
j
That is, the maxterm with subscript j is a complement of the minterm with the same 
subscript j and vice versa.  
The last example demonstrates the conversion between a function expressed in sum‐
of‐minterms form and its equivalent in product‐of‐maxterms form. A similar argument 
will show that the conversion between the product of maxterms and the sum of minterms 
is similar. We now state a general conversion procedure: To convert from one canonical 
form to another, interchange the symbols    ∑    and        and list those numbers missing from 
the original form. In order to find the missing terms, one must realize that the total number 
of minterms or maxterms is    2
n
,    where n is the number of binary variables in the function. 
A Boolean function can be converted from an algebraic expression to a product of 
maxterms by means of a truth table and the canonical conversion procedure. Consider, 
for example, the Boolean expression 
xy xz   
First, we derive the truth table of the function, as shown in  Table   2.6   . The 1’s under F in 
the table are determined from the combination of the variables for which    xy= 11    or 
xz =01.    The minterms of the function are read from the truth table to be 1, 3, 6, and 7. 
The function expressed as a sum of minterms is 
F(xy, z) = ∑(1, 3, 6, 7)   
56    Chapter 2  Boolean Algebra and Logic Gates
Since there is a total of eight minterms or maxterms in a function of three variables, we 
determine the missing terms to be 0, 2, 4, and 5. The function expressed as a product of 
maxterms is 
F(xy, z) = (0, 2, 4, 5)   
the same answer as obtained in Example 2.5. 
Standard Forms 
The two canonical forms of Boolean algebra are basic forms that one obtains from read-
ing a given function from the truth table. These forms are very seldom the ones with the 
least number of literals, because each minterm or maxterm must contain, by definition, 
all the variables, either complemented or uncomplemented. 
Another way to express Boolean functions is in standard form. In this configuration, 
the terms that form the function may contain one, two, or any number of literals. There 
are two types of standard forms: the sum of products and products of sums. 
The sum of products is a Boolean expression containing AND terms, called product 
terms, with one or more literals each. The sum denotes the ORing of these terms. An 
example of a function expressed as a sum of products is 
F
1
=y′+ xyxyz   
The expression has three product terms, with one, two, and three literals. Their sum is, 
in effect, an OR operation. 
The logic diagram of a sum‐of‐products expression consists of a group of AND gates 
followed by a single OR gate. This configuration pattern is shown in  Fig.   2.3   (a). Each 
product term requires an AND gate, except for a term with a single literal. The logic sum 
is formed with an OR gate whose inputs are the outputs of the AND gates and the 
single literal. It is assumed that the input variables are directly available in their comple-
ments, so inverters are not included in the diagram. This circuit configuration is referred 
to as a two‐level implementation
Table 2.6
Truth Table for F xy  xz
x
y
z
F
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
Minterms
Maxterms
Section 2.6  Canonical and Standard Forms    57
product of sums is a Boolean expression containing OR terms, called sum terms. 
Each term may have any number of literals. The product denotes the ANDing of these 
terms. An example of a function expressed as a product of sums is 
F
2
x(y′ +z)(x′+ z′)   
This expression has three sum terms, with one, two, and three literals. The product is an 
AND operation. The use of the words product and sum stems from the similarity of the 
AND operation to the arithmetic product (multiplication) and the similarity of the OR 
operation to the arithmetic sum (addition). The gate structure of the product‐of‐sums 
expression consists of a group of OR gates for the sum terms (except for a single literal), 
followed by an AND gate, as shown in  Fig.   2.3   (b).  This standard type of expression 
results in a two‐level structure of gates.  
A Boolean function may be expressed in a nonstandard form. For example, the function 
F
3
AB +C(E)   
is neither in sum‐of‐products nor in product‐of‐sums form. The implementation of this 
expression is shown in  Fig.   2.4   (a) and requires two AND gates and two OR gates. There 
are three levels of gating in this circuit. It can be changed to a standard form by using 
the distributive law to remove the parentheses: 
F
3
=ABC(E) = AB +CD CE   
y
F
1
x
z
y
x
y
F
2
x
y
y
z
z
x
(a) Sum of Products
(b) Product of Sums 
FIGURE 2.3
Two‐level implementation
F
3
A
B
C
D
E
(a) AB + C(D+ E)
(b) AB + CD + CE
A
F
3
B
D
C
C
E
FIGURE 2.4
Three‐ and two‐level implementation
58    Chapter 2  Boolean Algebra and Logic Gates
The sum‐of‐products expression is implemented in  Fig.   2.4   (b). In general, a two‐level 
implementation is preferred because it produces the least amount of delay through the 
gates when the signal propagates from the inputs to the output. However, the number 
of inputs to a given gate might not be practical.   
2.7    OTHER LOGIC OPERATIONS 
When the binary operators AND and OR are placed between two variables, x and y, 
they form two Boolean functions,    x
#
y    and    +y,    respectively. Previously we stated that 
there are    2
2n
functions for n binary variables. Thus, for two variables,    n= 2,    and the 
number of possible Boolean functions is 16. Therefore, the AND and OR functions 
are only 2 of a total of 16 possible functions formed with two binary variables. It would 
be instructive to find the other 14 functions and investigate their properties. 
The truth tables for the 16 functions formed with two binary variables are listed in 
Table   2.7   . Each of the 16 columns,    F
0
to    F
15
,    represents a truth table of one possible func-
tion for the two variables, x and y. Note that the functions are determined from the 
16binary combinations that can be assigned to F. The 16 functions can be expressed 
algebraically by means of Boolean functions, as is shown in the first column of  Table   2.8   . 
TheBoolean expressions listed are simplified to their minimum number of literals. 
Although each function can be expressed in terms of the Boolean operators AND, 
OR, and NOT, there is no reason one cannot assign special operator symbols for express-
ing the other functions. Such operator symbols are listed in the second column of 
Table  2.8   . However, of all the new symbols shown, only the exclusive‐OR symbol,    ,    
is in common use by digital designers. 
Each of the functions in  Table   2.8    is listed with an accompanying name and a com-
ment that explains the function in some way.
1
The 16 functions listed can be subdivided 
into three categories: 
 
1.   Two functions that produce a constant 0 or 1.  
 
2.   Four functions with unary operations: complement and transfer.  
 
3.   Ten functions with binary operators that define eight different operations: AND, 
OR, NAND, NOR, exclusive‐OR, equivalence, inhibition, and implication.   
Table 2.7
Truth Tables for the 16 Functions of Two Binary Variables
x
y
F
0
F
1
F
2
F
3
F
4
F
5
F
6
F
7
F
8
F
9
F
10
F
11
F
12
F
13
F
14
F
15
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
The symbol ˆ is also used to indicate the exclusive or operator, e.g., xˆy. The symbol for the AND function is 
sometimes omitted from the product of two variables, e.g., xy. 
Section 2.7  Other Logic Operations    59
Constants for binary functions can be equal to only 1 or 0. The complement function 
produces the complement of each of the binary variables. A function that is equal to an 
input variable has been given the name transfer, because the variable x or y is transferred 
through the gate that forms the function without changing its value. Of the eight binary 
operators, two (inhibition and implication) are used by logicians, but are seldom used 
in computer logic. The AND and OR operators have been mentioned in conjunction 
with Boolean algebra. The other four functions are used extensively in the design of 
digital systems. 
The NOR function is the complement of the OR function, and its name is an 
abbreviation of notOR. Similarly, NAND is the complement of AND and is an 
abbreviation of notAND. The exclusive‐OR, abbreviated XOR, is similar to OR, but 
excludes the combination of both x and y being equal to 1; it holds only when x andy 
differ in value. (It is sometimes referred to as the binary difference operator.) Equiv-
alence is a function that is 1 when the two binary variables are equal (i.e., when both 
are 0 or both are 1). The exclusive‐OR and equivalence functions are the comple-
ments of each other. This can be easily verified by inspecting  Table   2.7   : The truth 
table for exclusive‐OR is    F
6
and for equivalence is    F
9
,    and these two functions are 
the complements of each other. For this reason, the equivalence function is called 
exclusive‐NOR, abbreviated XNOR. 
Table 2.8
Boolean Expressions for the 16 Functions of Two Variables
Boolean Functions
Operator 
Symbol
Name
Comments
F
0
=0
Null
Binary constant 0
F
1
=xy
x
#
y
AND
x and y
F
2
=xy
x/y
Inhibition
x, but not y
F
3
=x
Transfer
x
F
4
=xy
y/x
Inhibition
y, but not x
F
5
=y
Transfer
y
F
6
=xy′ +xy
xy
Exclusive‐OR
x or y, but not both
F
7
=+y
+y
OR
x or y
F
8
=(+y)′
x T y
NOR
Not‐OR
F
9
=xy +xy
(xy)′
Equivalence
x equals y
F
10
y
y
Complement
Not y
F
11
xy
xy
Implication
If y, then x
F
12
x
x
Complement
Not x
F
13
x′ +y
xy
Implication
If x, then y
F
14
= (xy)′
x c y
NAND
Not‐AND
F
15
= 1
Identity
Binary constant 1
60    Chapter 2  Boolean Algebra and Logic Gates
Boolean algebra, as defined in Section 2.2, has two binary operators, which we have 
called AND and OR, and a unary operator, NOT (complement). From the definitions, 
we have deduced a number of properties of these operators and now have defined other 
binary operators in terms of them. There is nothing unique about this procedure. We 
could have just as well started with the operator NOR    (T),    for example, and later 
defined AND, OR, and NOT in terms of it. There are, nevertheless, good reasons for 
introducing Boolean algebra in the way it has been introduced. The concepts of “and,” 
“or,” and “not” are familiar and are used by people to express everyday logical ideas. 
Moreover, the Huntington postulates reflect the dual nature of the algebra, emphasizing 
the symmetry of    +     and    
#
with respect to each other.  
2.8    DIGITAL LOGIC GATES 
Since Boolean functions are expressed in terms of AND, OR, and NOT operations, it is 
easier to implement a Boolean function with these type of gates. Still, the possibility of 
constructing gates for the other logic operations is of practical interest. Factors to be 
weighed in considering the construction of other types of logic gates are (1) the feasibil-
ity and economy of producing the gate with physical components, (2) the possibility of 
extending the gate to more than two inputs, (3) the basic properties of the binary oper-
ator, such as commutativity and associativity, and (4) the ability of the gate to implement 
Boolean functions alone or in conjunction with other gates. 
Of the 16 functions defined in  Table   2.8   , two are equal to a constant and four are 
repeated. There are only 10 functions left to be considered as candidates for logic gates. 
Two—inhibition and implication—are not commutative or associative and thus are 
impractical to use as standard logic gates. The other eight—complement, transfer, AND, 
OR, NAND, NOR, exclusive‐OR, and equivalence—are used as standard gates in 
digital design. 
The graphic symbols and truth tables of the eight gates are shown in  Fig.   2.5   . Each 
gate has one or two binary input variables, designated by x and y, and one binary output 
variable, designated by F. The AND, OR, and inverter circuits were defined in Fig. 1.6. 
The inverter circuit inverts the logic sense of a binary variable, producing the NOT, or 
complement, function. The small circle in the output of the graphic symbol of an inverter 
(referred to as a bubble) designates the logic complement. The triangle symbol by itself 
designates a buffer circuit. A buffer produces the transfer function, but does not produce 
a logic operation, since the binary value of the output is equal to the binary value of the 
input. This circuit is used for power amplification of the signal and is equivalent to two 
inverters connected in cascade. 
The NAND function is the complement of the AND function, as indicated by a 
graphic symbol that consists of an AND graphic symbol followed by a small circle. The 
NOR function is the complement of the OR function and uses an OR graphic symbol 
followed by a small circle. NAND and NOR gates are used extensively as standard logic 
gates and are in fact far more popular than the AND and OR gates. This is because 
NAND and NOR gates are easily constructed with transistor circuits and because  digital 
circuits can be easily implemented with them. 
Section 2.8  Digital Logic Gates    61
Name
Graphic
symbol
Algebraic
function
Truth
table
AND
OR
Inverter
Buffer
NAND
NOR
Exclusive-OR
(XOR)
Exclusive-NOR
or
equivalence
F=x·y
F=x+y
F
=
(
x
y
)
F=x
F=x
x
y
F
x
y
F
x
y
F
x
y
F
x
y
F
x
y
F
x
F
x
F
F
=
(
x
+
y
)
F
=
x
y
+
x
y
F
=
x
y
+
x
y
F
F
F
x
F
x
F
F
F
F
x
y
x
y
x
y
=x⊕ y
= (x y)′
0
0
1
1
0
1
0
1
0
0
1
1
0
1
0
1
0
1
1
1
0
1
1
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
0
0
0
1
1
0
1
0
1
1
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
0
0
1
1
0
1
0
1
1
0
0
1
0
0
0
1
x
y
x
y
x
y
FIGURE 2.5
Digital logic gates
62    Chapter 2  Boolean Algebra and Logic Gates
The exclusive‐OR gate has a graphic symbol similar to that of the OR gate, except 
for the additional curved line on the input side. The equivalence, or exclusive‐NOR, gate 
is the complement of the exclusive‐OR, as indicated by the small circle on the output 
side of the graphic symbol. 
Extension to Multiple Inputs 
The gates shown in  Fig.   2.5   —except for the inverter and buffer—can be extended to 
have more than two inputs. A gate can be extended to have multiple inputs if the binary 
operation it represents is commutative and associative. The AND and OR operations, 
defined in Boolean algebra, possess these two properties. For the OR function, we have 
y(commutative)   
and 
(xy) + =+ (z) = y(associative)   
which indicates that the gate inputs can be interchanged and that the OR function can 
be extended to three or more variables. 
The NAND and NOR functions are commutative, and their gates can be extended 
to have more than two inputs, provided that the definition of the operation is modified 
slightly. The difficulty is that the NAND and NOR operators are not associative 
(i.e.,   (x 
T
y
T
 x 
T
(y 
T
z)   ), as shown in  Fig.   2.6    and the following equations: 
(x 
T
y
T
= [(y)′ + z]′ = (xy)z′= xz′+ yz
x 
T
(y 
T
z) = [+ (yz)′]′ ′ = x′(yz) = xyxz   
To overcome this difficulty, we define the multiple NOR (or NAND) gate as a 
complemented OR (or AND) gate. Thus, by definition, we have 
x 
T
y 
T
z= (+z)′
x 
c
y 
c
z= (xyz)′   
The graphic symbols for the three‐input gates are shown in  Fig.   2.7   . In writing cascaded 
NOR and NAND operations, one must use the correct parentheses to signify the proper 
sequence of the gates. To demonstrate this principle, consider the circuit of  Fig.  2.7   (c). 
The Boolean function for the circuit must be written as 
= [(ABC)′(DE)′]′ =ABC DE   
The second expression is obtained from one of DeMorgan’s theorems. It also shows that 
an expression in sum‐of‐products form can be implemented with NAND gates. (NAND 
and NOR gates are discussed further in Section 3.7.) 
The exclusive‐OR and equivalence gates are both commutative and associative and 
can be extended to more than two inputs. However, multiple‐input exclusive‐OR gates 
are uncommon from the hardware standpoint. In fact, even a two‐input function is usu-
ally constructed with other types of gates. Moreover, the definition of the function must 
be modified when extended to more than two variables. Exclusive‐OR is an odd  function 
(i.e., it is equal to 1 if the input variables have an odd number of 1’s). The construction 
Documents you may be interested
Documents you may be interested