Boolean Algebra and Some Combinational Circuits Notes | EduRev

Created by: Atul Jain

: Boolean Algebra and Some Combinational Circuits Notes | EduRev

 Page 1


 
Chapter 3 – Boolean Algebra and Some Combinational Circuits 
 
Chapter Overview 
This chapter discusses combinational circuits that are basic to the functioning of a digital 
computer.  With one exception, these circuits either directly implement the basic Boolean 
functions or are built from basic gates that directly implement these functions.  For that 
reason, we review the fundamentals of Boolean algebra. 
 
Chapter Assumptions 
The intended audience for this chapter (and the rest of the course) will have a basic 
understanding of Boolean algebra and some understanding of electrical circuitry.  The 
student should have sufficient familiarity with each of these subjects to allow him or her to 
follow their use in the lecture material. 
 
One of the prerequisites for this course is CPSC 2105 – Introduction to Computer 
Organization.  Topics covered in that course include the basic Boolean functions; their 
representation in standard forms, including POS (Product of Sums) and SOP (Sum of 
Products); and the basic postulates and theorems underlying the algebra.  Due to the 
centrality of Boolean algebra to the combinational circuits used in computer design, this 
subject will be reviewed in this chapter. 
 
Another topic that forms a prerequisite for this course is a rudimentary familiarity with 
electrical circuits and their components.  This course will focus on the use of TTL 
(Transistor–Transistor Logic) components as basic units of a computer.  While it is sufficient 
for this course for the student to remember “TTL” as the name of a technology used to 
implement digital components, it would be preferable if the student were comfortable with 
the idea of “transistor” and what it does. 
 
Another assumption for this chapter is that the student has an intuitive feeling for the ideas of 
voltage and current in an electrical circuit.  An understanding of Ohm’s law (V = I •R) would 
be helpful here, but is not required.  More advanced topics, such as Kickoff’s laws will not 
even be mentioned in this discussion, although they are very useful in circuit design.  It is 
sufficient for the student to be able to grasp statements such as the remark that in active-high 
TTL components, logic 1 is represented by +5 volts and logic 0 by 0 volts. 
 
Boolean Algebra 
We begin this course in computer architecture with a review of topics from the prerequisite 
course.  It is assumed that the student is familiar with the basics of Boolean algebra and two’s 
complement arithmetic, but it never hurts to review. 
 
Boolean algebra is the algebra of variables that can assume two values: True and False.  
Conventionally we associate these as follows: True = 1 and False = 0.  This association will 
become important when we consider the use of Boolean components to synthesize arithmetic 
circuits, such as a binary adder. 
 
Page 92 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
Page 2


 
Chapter 3 – Boolean Algebra and Some Combinational Circuits 
 
Chapter Overview 
This chapter discusses combinational circuits that are basic to the functioning of a digital 
computer.  With one exception, these circuits either directly implement the basic Boolean 
functions or are built from basic gates that directly implement these functions.  For that 
reason, we review the fundamentals of Boolean algebra. 
 
Chapter Assumptions 
The intended audience for this chapter (and the rest of the course) will have a basic 
understanding of Boolean algebra and some understanding of electrical circuitry.  The 
student should have sufficient familiarity with each of these subjects to allow him or her to 
follow their use in the lecture material. 
 
One of the prerequisites for this course is CPSC 2105 – Introduction to Computer 
Organization.  Topics covered in that course include the basic Boolean functions; their 
representation in standard forms, including POS (Product of Sums) and SOP (Sum of 
Products); and the basic postulates and theorems underlying the algebra.  Due to the 
centrality of Boolean algebra to the combinational circuits used in computer design, this 
subject will be reviewed in this chapter. 
 
Another topic that forms a prerequisite for this course is a rudimentary familiarity with 
electrical circuits and their components.  This course will focus on the use of TTL 
(Transistor–Transistor Logic) components as basic units of a computer.  While it is sufficient 
for this course for the student to remember “TTL” as the name of a technology used to 
implement digital components, it would be preferable if the student were comfortable with 
the idea of “transistor” and what it does. 
 
Another assumption for this chapter is that the student has an intuitive feeling for the ideas of 
voltage and current in an electrical circuit.  An understanding of Ohm’s law (V = I •R) would 
be helpful here, but is not required.  More advanced topics, such as Kickoff’s laws will not 
even be mentioned in this discussion, although they are very useful in circuit design.  It is 
sufficient for the student to be able to grasp statements such as the remark that in active-high 
TTL components, logic 1 is represented by +5 volts and logic 0 by 0 volts. 
 
Boolean Algebra 
We begin this course in computer architecture with a review of topics from the prerequisite 
course.  It is assumed that the student is familiar with the basics of Boolean algebra and two’s 
complement arithmetic, but it never hurts to review. 
 
Boolean algebra is the algebra of variables that can assume two values: True and False.  
Conventionally we associate these as follows: True = 1 and False = 0.  This association will 
become important when we consider the use of Boolean components to synthesize arithmetic 
circuits, such as a binary adder. 
 
Page 92 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
 Chapter 3 – Boolean Algebra and Combinational Logic 
Formally, Boolean algebra is defined over a set of elements {0, 1}, two binary operators 
{AND, OR}, and a single unary operator NOT.  These operators are conventionally 
represented as follows: • for AND 
    + for OR 
    ’ for NOT, thus X’ is Not(X). 
The Boolean operators are completely defined by Truth Tables. 
 
AND 0•0 = 0 OR 0+0 = 0 NOT 0’ = 1 
 0•1 = 0  0+1 = 1  1’ = 0 
 1•0 = 0  1+0 = 1 
 1•1 = 1  1+1 = 1 
 
Note that the use of “+” for the OR operation is restricted to those cases in which addition is 
not being discussed.  When addition is also important, we use different symbols for the 
binary Boolean operators, the most common being ? for AND, and ? for OR. 
 
There is another notation for the complement (NOT) function that is preferable.  If X is a 
Boolean variable, then X is its complement, so that 0 = 1 and 1 = 0.  The only reason that 
this author uses X’ to denote X is that the former notation is easier to create in MS-Word. 
 
There is another very handy function, called the XOR (Exclusive OR) function.  Although it 
is not basic to Boolean algebra, it comes in quite handy in circuit design.  The symbol for the 
Exclusive OR function is ?.  Here is its complete definition using a truth table. 
 0 ? 0 = 0  0 ? 1 = 1 
 1 ? 0 = 1  1 ? 1 = 0 
 
Truth Tables 
A truth table for a function of N Boolean variables depends on the fact that there are only 2
N 
different combinations of the values of these N Boolean variables.  For small values of N, 
this allows one to list every possible value of the function. 
 
Consider a Boolean function of two Boolean variables X and Y.  The only possibilities for 
the values of the variables are: 
 X = 0 and Y = 0 
 X = 0 and Y = 1 
 X = 1 and Y = 0 
 X = 1 and Y = 1 
 
Similarly, there are eight possible combinations of the three variables X, Y, and Z, beginning 
with X = 0, Y = 0, Z = 0 and going through X = 1, Y = 1, Z = 1.  Here they are. 
 X = 0, Y = 0, Z = 0 X = 0, Y = 0, Z = 1 X = 0, Y = 1, Z = 0 X = 0, Y = 1, Z = 1 
 X = 1, Y = 0, Z = 0 X = 1, Y = 0, Z = 1 X = 1, Y = 1, Z = 0 X = 1, Y = 1, Z = 1 
 
As we shall see, we prefer truth tables for functions of not too many variables. 
 
Page 93 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
Page 3


 
Chapter 3 – Boolean Algebra and Some Combinational Circuits 
 
Chapter Overview 
This chapter discusses combinational circuits that are basic to the functioning of a digital 
computer.  With one exception, these circuits either directly implement the basic Boolean 
functions or are built from basic gates that directly implement these functions.  For that 
reason, we review the fundamentals of Boolean algebra. 
 
Chapter Assumptions 
The intended audience for this chapter (and the rest of the course) will have a basic 
understanding of Boolean algebra and some understanding of electrical circuitry.  The 
student should have sufficient familiarity with each of these subjects to allow him or her to 
follow their use in the lecture material. 
 
One of the prerequisites for this course is CPSC 2105 – Introduction to Computer 
Organization.  Topics covered in that course include the basic Boolean functions; their 
representation in standard forms, including POS (Product of Sums) and SOP (Sum of 
Products); and the basic postulates and theorems underlying the algebra.  Due to the 
centrality of Boolean algebra to the combinational circuits used in computer design, this 
subject will be reviewed in this chapter. 
 
Another topic that forms a prerequisite for this course is a rudimentary familiarity with 
electrical circuits and their components.  This course will focus on the use of TTL 
(Transistor–Transistor Logic) components as basic units of a computer.  While it is sufficient 
for this course for the student to remember “TTL” as the name of a technology used to 
implement digital components, it would be preferable if the student were comfortable with 
the idea of “transistor” and what it does. 
 
Another assumption for this chapter is that the student has an intuitive feeling for the ideas of 
voltage and current in an electrical circuit.  An understanding of Ohm’s law (V = I •R) would 
be helpful here, but is not required.  More advanced topics, such as Kickoff’s laws will not 
even be mentioned in this discussion, although they are very useful in circuit design.  It is 
sufficient for the student to be able to grasp statements such as the remark that in active-high 
TTL components, logic 1 is represented by +5 volts and logic 0 by 0 volts. 
 
Boolean Algebra 
We begin this course in computer architecture with a review of topics from the prerequisite 
course.  It is assumed that the student is familiar with the basics of Boolean algebra and two’s 
complement arithmetic, but it never hurts to review. 
 
Boolean algebra is the algebra of variables that can assume two values: True and False.  
Conventionally we associate these as follows: True = 1 and False = 0.  This association will 
become important when we consider the use of Boolean components to synthesize arithmetic 
circuits, such as a binary adder. 
 
Page 92 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
 Chapter 3 – Boolean Algebra and Combinational Logic 
Formally, Boolean algebra is defined over a set of elements {0, 1}, two binary operators 
{AND, OR}, and a single unary operator NOT.  These operators are conventionally 
represented as follows: • for AND 
    + for OR 
    ’ for NOT, thus X’ is Not(X). 
The Boolean operators are completely defined by Truth Tables. 
 
AND 0•0 = 0 OR 0+0 = 0 NOT 0’ = 1 
 0•1 = 0  0+1 = 1  1’ = 0 
 1•0 = 0  1+0 = 1 
 1•1 = 1  1+1 = 1 
 
Note that the use of “+” for the OR operation is restricted to those cases in which addition is 
not being discussed.  When addition is also important, we use different symbols for the 
binary Boolean operators, the most common being ? for AND, and ? for OR. 
 
There is another notation for the complement (NOT) function that is preferable.  If X is a 
Boolean variable, then X is its complement, so that 0 = 1 and 1 = 0.  The only reason that 
this author uses X’ to denote X is that the former notation is easier to create in MS-Word. 
 
There is another very handy function, called the XOR (Exclusive OR) function.  Although it 
is not basic to Boolean algebra, it comes in quite handy in circuit design.  The symbol for the 
Exclusive OR function is ?.  Here is its complete definition using a truth table. 
 0 ? 0 = 0  0 ? 1 = 1 
 1 ? 0 = 1  1 ? 1 = 0 
 
Truth Tables 
A truth table for a function of N Boolean variables depends on the fact that there are only 2
N 
different combinations of the values of these N Boolean variables.  For small values of N, 
this allows one to list every possible value of the function. 
 
Consider a Boolean function of two Boolean variables X and Y.  The only possibilities for 
the values of the variables are: 
 X = 0 and Y = 0 
 X = 0 and Y = 1 
 X = 1 and Y = 0 
 X = 1 and Y = 1 
 
Similarly, there are eight possible combinations of the three variables X, Y, and Z, beginning 
with X = 0, Y = 0, Z = 0 and going through X = 1, Y = 1, Z = 1.  Here they are. 
 X = 0, Y = 0, Z = 0 X = 0, Y = 0, Z = 1 X = 0, Y = 1, Z = 0 X = 0, Y = 1, Z = 1 
 X = 1, Y = 0, Z = 0 X = 1, Y = 0, Z = 1 X = 1, Y = 1, Z = 0 X = 1, Y = 1, Z = 1 
 
As we shall see, we prefer truth tables for functions of not too many variables. 
 
Page 93 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
 Chapter 3 – Boolean Algebra and Combinational Logic 
The figure at left is a truth table for a two-variable function.  Note that 
we have four rows in the truth table, corresponding to the four possible 
combinations of values for X and Y.  Note also the standard order in 
which the values are written: 00, 01, 10, and 11.  Other orders can be 
used when needed (it is done below), but one must list all combinations. 
X Y F(X, Y) 
0 0 1 
0 1 0 
1 0 0 
1 1 1 
 
For another example of truth tables, we consider the figure at 
the right, which shows two Boolean functions of three Boolean 
variables.  Truth tables can be used to define more than one 
function at a time, although they become hard to read if either 
the number of variables or the number of functions is too large.  
Here we use the standard shorthand of F1 for F1(X, Y, Z) and 
F2 for F2(X, Y, Z).  Also note the standard ordering of the 
rows, beginning with 0 0 0 and ending with 1 1 1.  This causes 
less confusion than other ordering schemes, which may be used 
when there is a good reason for them. 
X Y Z F1 F2 
0 0 0 0 0 
0 0 1 1 0 
0 1 0 1 0 
0 1 1 0 1 
1 0 0 1 0 
1 0 1 0 1 
1 1 0 0 1 
1 1 1 1 1 
 
As an example of a truth table in which non-standard ordering might be useful, consider the 
following table for two variables.  As expected, it has four rows. 
 
A truth table in this non-standard ordering would be used to 
prove the standard Boolean axioms: 
 X • 0 = 0 for all X  X + 0 = X for all X 
X Y X • Y X + Y 
0 0 0 0 
1 0 0 1 
0 1 0 1 
1 1 1 1 
 X • 1 = X for all X  X + 1 = 1 for all X 
 
 
In future lectures we shall use truth tables to specify functions without needing to consider 
their algebraic representations.  Because 2
N
 is such a fast growing function, we give truth 
tables for functions of 2, 3, and 4 variables only, with 4, 8, and 16 rows, respectively.  Truth 
tables for 4 variables, having 16 rows, are almost too big.  For five or more variables, truth 
tables become unusable, having 32 or more rows. 
 
Labeling Rows in Truth Tables 
We now discuss a notation that is commonly used to identify rows in truth tables.  The exact 
identity of the rows is given by the values for each of the variables, but we find it convenient 
to label the rows with the integer equivalent of the binary values.  We noted above that for N 
variables, the truth table has 2
N
 rows.  These are conventionally numbered from 0 through  
2
N
 – 1 inclusive to give us a handy way to reference the rows.  Thus a two variable truth table 
would have four rows numbered 0, 1, 2, and 3.  Here is a truth-table with labeled rows. 
 
   We can see that G(A, B) = A ? B, but 
0  = 0 •2 + 0•1  this value has nothing to do with the 
1  = 0 •2 + 1•1  row numberings, which are just the 
2  = 1 •2 + 0•1  decimal equivalents of the values in  
3  = 1 •2 + 1•1  the A & B columns as binary. 
Row A B G(A, B) 
0 0 0 0 
1 0 1 1 
2 1 0 1 
3 1 1 0 
Page 94 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
Page 4


 
Chapter 3 – Boolean Algebra and Some Combinational Circuits 
 
Chapter Overview 
This chapter discusses combinational circuits that are basic to the functioning of a digital 
computer.  With one exception, these circuits either directly implement the basic Boolean 
functions or are built from basic gates that directly implement these functions.  For that 
reason, we review the fundamentals of Boolean algebra. 
 
Chapter Assumptions 
The intended audience for this chapter (and the rest of the course) will have a basic 
understanding of Boolean algebra and some understanding of electrical circuitry.  The 
student should have sufficient familiarity with each of these subjects to allow him or her to 
follow their use in the lecture material. 
 
One of the prerequisites for this course is CPSC 2105 – Introduction to Computer 
Organization.  Topics covered in that course include the basic Boolean functions; their 
representation in standard forms, including POS (Product of Sums) and SOP (Sum of 
Products); and the basic postulates and theorems underlying the algebra.  Due to the 
centrality of Boolean algebra to the combinational circuits used in computer design, this 
subject will be reviewed in this chapter. 
 
Another topic that forms a prerequisite for this course is a rudimentary familiarity with 
electrical circuits and their components.  This course will focus on the use of TTL 
(Transistor–Transistor Logic) components as basic units of a computer.  While it is sufficient 
for this course for the student to remember “TTL” as the name of a technology used to 
implement digital components, it would be preferable if the student were comfortable with 
the idea of “transistor” and what it does. 
 
Another assumption for this chapter is that the student has an intuitive feeling for the ideas of 
voltage and current in an electrical circuit.  An understanding of Ohm’s law (V = I •R) would 
be helpful here, but is not required.  More advanced topics, such as Kickoff’s laws will not 
even be mentioned in this discussion, although they are very useful in circuit design.  It is 
sufficient for the student to be able to grasp statements such as the remark that in active-high 
TTL components, logic 1 is represented by +5 volts and logic 0 by 0 volts. 
 
Boolean Algebra 
We begin this course in computer architecture with a review of topics from the prerequisite 
course.  It is assumed that the student is familiar with the basics of Boolean algebra and two’s 
complement arithmetic, but it never hurts to review. 
 
Boolean algebra is the algebra of variables that can assume two values: True and False.  
Conventionally we associate these as follows: True = 1 and False = 0.  This association will 
become important when we consider the use of Boolean components to synthesize arithmetic 
circuits, such as a binary adder. 
 
Page 92 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
 Chapter 3 – Boolean Algebra and Combinational Logic 
Formally, Boolean algebra is defined over a set of elements {0, 1}, two binary operators 
{AND, OR}, and a single unary operator NOT.  These operators are conventionally 
represented as follows: • for AND 
    + for OR 
    ’ for NOT, thus X’ is Not(X). 
The Boolean operators are completely defined by Truth Tables. 
 
AND 0•0 = 0 OR 0+0 = 0 NOT 0’ = 1 
 0•1 = 0  0+1 = 1  1’ = 0 
 1•0 = 0  1+0 = 1 
 1•1 = 1  1+1 = 1 
 
Note that the use of “+” for the OR operation is restricted to those cases in which addition is 
not being discussed.  When addition is also important, we use different symbols for the 
binary Boolean operators, the most common being ? for AND, and ? for OR. 
 
There is another notation for the complement (NOT) function that is preferable.  If X is a 
Boolean variable, then X is its complement, so that 0 = 1 and 1 = 0.  The only reason that 
this author uses X’ to denote X is that the former notation is easier to create in MS-Word. 
 
There is another very handy function, called the XOR (Exclusive OR) function.  Although it 
is not basic to Boolean algebra, it comes in quite handy in circuit design.  The symbol for the 
Exclusive OR function is ?.  Here is its complete definition using a truth table. 
 0 ? 0 = 0  0 ? 1 = 1 
 1 ? 0 = 1  1 ? 1 = 0 
 
Truth Tables 
A truth table for a function of N Boolean variables depends on the fact that there are only 2
N 
different combinations of the values of these N Boolean variables.  For small values of N, 
this allows one to list every possible value of the function. 
 
Consider a Boolean function of two Boolean variables X and Y.  The only possibilities for 
the values of the variables are: 
 X = 0 and Y = 0 
 X = 0 and Y = 1 
 X = 1 and Y = 0 
 X = 1 and Y = 1 
 
Similarly, there are eight possible combinations of the three variables X, Y, and Z, beginning 
with X = 0, Y = 0, Z = 0 and going through X = 1, Y = 1, Z = 1.  Here they are. 
 X = 0, Y = 0, Z = 0 X = 0, Y = 0, Z = 1 X = 0, Y = 1, Z = 0 X = 0, Y = 1, Z = 1 
 X = 1, Y = 0, Z = 0 X = 1, Y = 0, Z = 1 X = 1, Y = 1, Z = 0 X = 1, Y = 1, Z = 1 
 
As we shall see, we prefer truth tables for functions of not too many variables. 
 
Page 93 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
 Chapter 3 – Boolean Algebra and Combinational Logic 
The figure at left is a truth table for a two-variable function.  Note that 
we have four rows in the truth table, corresponding to the four possible 
combinations of values for X and Y.  Note also the standard order in 
which the values are written: 00, 01, 10, and 11.  Other orders can be 
used when needed (it is done below), but one must list all combinations. 
X Y F(X, Y) 
0 0 1 
0 1 0 
1 0 0 
1 1 1 
 
For another example of truth tables, we consider the figure at 
the right, which shows two Boolean functions of three Boolean 
variables.  Truth tables can be used to define more than one 
function at a time, although they become hard to read if either 
the number of variables or the number of functions is too large.  
Here we use the standard shorthand of F1 for F1(X, Y, Z) and 
F2 for F2(X, Y, Z).  Also note the standard ordering of the 
rows, beginning with 0 0 0 and ending with 1 1 1.  This causes 
less confusion than other ordering schemes, which may be used 
when there is a good reason for them. 
X Y Z F1 F2 
0 0 0 0 0 
0 0 1 1 0 
0 1 0 1 0 
0 1 1 0 1 
1 0 0 1 0 
1 0 1 0 1 
1 1 0 0 1 
1 1 1 1 1 
 
As an example of a truth table in which non-standard ordering might be useful, consider the 
following table for two variables.  As expected, it has four rows. 
 
A truth table in this non-standard ordering would be used to 
prove the standard Boolean axioms: 
 X • 0 = 0 for all X  X + 0 = X for all X 
X Y X • Y X + Y 
0 0 0 0 
1 0 0 1 
0 1 0 1 
1 1 1 1 
 X • 1 = X for all X  X + 1 = 1 for all X 
 
 
In future lectures we shall use truth tables to specify functions without needing to consider 
their algebraic representations.  Because 2
N
 is such a fast growing function, we give truth 
tables for functions of 2, 3, and 4 variables only, with 4, 8, and 16 rows, respectively.  Truth 
tables for 4 variables, having 16 rows, are almost too big.  For five or more variables, truth 
tables become unusable, having 32 or more rows. 
 
Labeling Rows in Truth Tables 
We now discuss a notation that is commonly used to identify rows in truth tables.  The exact 
identity of the rows is given by the values for each of the variables, but we find it convenient 
to label the rows with the integer equivalent of the binary values.  We noted above that for N 
variables, the truth table has 2
N
 rows.  These are conventionally numbered from 0 through  
2
N
 – 1 inclusive to give us a handy way to reference the rows.  Thus a two variable truth table 
would have four rows numbered 0, 1, 2, and 3.  Here is a truth-table with labeled rows. 
 
   We can see that G(A, B) = A ? B, but 
0  = 0 •2 + 0•1  this value has nothing to do with the 
1  = 0 •2 + 1•1  row numberings, which are just the 
2  = 1 •2 + 0•1  decimal equivalents of the values in  
3  = 1 •2 + 1•1  the A & B columns as binary. 
Row A B G(A, B) 
0 0 0 0 
1 0 1 1 
2 1 0 1 
3 1 1 0 
Page 94 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
 Chapter 3 – Boolean Algebra and Combinational Logic 
A three variable truth table would have eight rows, numbered 0, 1, 2, 3, 4, 5, 6, and 7.  Here 
is a three variable truth table for a function F(X, Y, Z) with the rows numbered. 
 
Note that the row numbers correspond to the 
decimal value of the three bit binary, thus 
 0 = 0•4 + 0•2 + 0•1 
 1 = 0•4 + 0•2 + 1•1 
 2 = 0•4 + 1•2 + 0•1 
 3 = 0•4 + 1•2 + 1•1 
 4 = 1•4 + 0•2 + 0•1 
 5 = 1•4 + 0•2 + 1•1 
 6 = 1•4 + 1•2 + 0•1 
 7 = 1•4 + 1•2 + 1•1 
Row 
Number 
X Y Z F(X, Y, Z) 
0 0 0 0 1 
1 0 0 1 1 
2 0 1 0 0 
3 0 1 1 1 
4 1 0 0 1 
5 1 0 1 0 
6 1 1 0 1 
7 1 1 1 1 
 
Truth tables are purely Boolean tables in which decimal numbers, such as the row numbers 
above do not really play a part.  However, we find that the ability to label a row with a 
decimal number to be very convenient and so we use this.  The row numberings can be quite 
important for the standard algebraic forms used in representing Boolean functions. 
 
 
Question: Where to Put the Ones and Zeroes 
Every truth table corresponds to a Boolean expression.  For some truth tables, we begin with 
a Boolean expression and evaluate that expression in order to find where to place the 0’s and 
1’s.  For other tables, we just place a bunch of 0’s and 1’s and then ask what Boolean 
expression we have created.  The truth table just above was devised by selecting an 
interesting pattern of 0’s and 1’s.  The author of these notes had no particular pattern in mind 
when creating it.  Other truth tables are more deliberately generated. 
 
Let’s consider the construction of a truth table for the Boolean expression. 
F(X, Y, Z) = Z Y X Z Y Y X • • + • + • 
 
Let’s evaluate this function for all eight possible values of X, Y, Z. 
 X = 0 Y = 0 Z = 0 F(X, Y, Z) = 0 •0 + 0•0 + 0•1•0 = 0 + 0 + 0 = 0 
 X = 0 Y = 0 Z = 1 F(X, Y, Z) = 0 •0 + 0•1 + 0•1•1 = 0 + 0 + 0 = 0 
 X = 0 Y = 1 Z = 0 F(X, Y, Z) = 0 •1 + 1•0 + 0•0•0 = 0 + 0 + 0 = 0 
 X = 0 Y = 1 Z = 1 F(X, Y, Z) = 0 •1 + 1•1 + 0•0•1 = 0 + 1 + 0 = 1 
 X = 1 Y = 0 Z = 0 F(X, Y, Z) = 1 •0 + 0•0 + 1•1•0 = 0 + 0 + 0 = 0 
 X = 1 Y = 0 Z = 1 F(X, Y, Z) = 1 •0 + 0•1 + 1•1•1 = 0 + 0 + 1 = 1 
 X = 1 Y = 1 Z = 0 F(X, Y, Z) = 1 •1 + 1•0 + 1•0•0 = 1 + 0 + 0 = 1 
 X = 1 Y = 1 Z = 1 F(X, Y, Z) = 1 •1 + 1•1 + 1•0•1 = 1 + 1 + 0 = 1 
 
Page 95 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
Page 5


 
Chapter 3 – Boolean Algebra and Some Combinational Circuits 
 
Chapter Overview 
This chapter discusses combinational circuits that are basic to the functioning of a digital 
computer.  With one exception, these circuits either directly implement the basic Boolean 
functions or are built from basic gates that directly implement these functions.  For that 
reason, we review the fundamentals of Boolean algebra. 
 
Chapter Assumptions 
The intended audience for this chapter (and the rest of the course) will have a basic 
understanding of Boolean algebra and some understanding of electrical circuitry.  The 
student should have sufficient familiarity with each of these subjects to allow him or her to 
follow their use in the lecture material. 
 
One of the prerequisites for this course is CPSC 2105 – Introduction to Computer 
Organization.  Topics covered in that course include the basic Boolean functions; their 
representation in standard forms, including POS (Product of Sums) and SOP (Sum of 
Products); and the basic postulates and theorems underlying the algebra.  Due to the 
centrality of Boolean algebra to the combinational circuits used in computer design, this 
subject will be reviewed in this chapter. 
 
Another topic that forms a prerequisite for this course is a rudimentary familiarity with 
electrical circuits and their components.  This course will focus on the use of TTL 
(Transistor–Transistor Logic) components as basic units of a computer.  While it is sufficient 
for this course for the student to remember “TTL” as the name of a technology used to 
implement digital components, it would be preferable if the student were comfortable with 
the idea of “transistor” and what it does. 
 
Another assumption for this chapter is that the student has an intuitive feeling for the ideas of 
voltage and current in an electrical circuit.  An understanding of Ohm’s law (V = I •R) would 
be helpful here, but is not required.  More advanced topics, such as Kickoff’s laws will not 
even be mentioned in this discussion, although they are very useful in circuit design.  It is 
sufficient for the student to be able to grasp statements such as the remark that in active-high 
TTL components, logic 1 is represented by +5 volts and logic 0 by 0 volts. 
 
Boolean Algebra 
We begin this course in computer architecture with a review of topics from the prerequisite 
course.  It is assumed that the student is familiar with the basics of Boolean algebra and two’s 
complement arithmetic, but it never hurts to review. 
 
Boolean algebra is the algebra of variables that can assume two values: True and False.  
Conventionally we associate these as follows: True = 1 and False = 0.  This association will 
become important when we consider the use of Boolean components to synthesize arithmetic 
circuits, such as a binary adder. 
 
Page 92 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
 Chapter 3 – Boolean Algebra and Combinational Logic 
Formally, Boolean algebra is defined over a set of elements {0, 1}, two binary operators 
{AND, OR}, and a single unary operator NOT.  These operators are conventionally 
represented as follows: • for AND 
    + for OR 
    ’ for NOT, thus X’ is Not(X). 
The Boolean operators are completely defined by Truth Tables. 
 
AND 0•0 = 0 OR 0+0 = 0 NOT 0’ = 1 
 0•1 = 0  0+1 = 1  1’ = 0 
 1•0 = 0  1+0 = 1 
 1•1 = 1  1+1 = 1 
 
Note that the use of “+” for the OR operation is restricted to those cases in which addition is 
not being discussed.  When addition is also important, we use different symbols for the 
binary Boolean operators, the most common being ? for AND, and ? for OR. 
 
There is another notation for the complement (NOT) function that is preferable.  If X is a 
Boolean variable, then X is its complement, so that 0 = 1 and 1 = 0.  The only reason that 
this author uses X’ to denote X is that the former notation is easier to create in MS-Word. 
 
There is another very handy function, called the XOR (Exclusive OR) function.  Although it 
is not basic to Boolean algebra, it comes in quite handy in circuit design.  The symbol for the 
Exclusive OR function is ?.  Here is its complete definition using a truth table. 
 0 ? 0 = 0  0 ? 1 = 1 
 1 ? 0 = 1  1 ? 1 = 0 
 
Truth Tables 
A truth table for a function of N Boolean variables depends on the fact that there are only 2
N 
different combinations of the values of these N Boolean variables.  For small values of N, 
this allows one to list every possible value of the function. 
 
Consider a Boolean function of two Boolean variables X and Y.  The only possibilities for 
the values of the variables are: 
 X = 0 and Y = 0 
 X = 0 and Y = 1 
 X = 1 and Y = 0 
 X = 1 and Y = 1 
 
Similarly, there are eight possible combinations of the three variables X, Y, and Z, beginning 
with X = 0, Y = 0, Z = 0 and going through X = 1, Y = 1, Z = 1.  Here they are. 
 X = 0, Y = 0, Z = 0 X = 0, Y = 0, Z = 1 X = 0, Y = 1, Z = 0 X = 0, Y = 1, Z = 1 
 X = 1, Y = 0, Z = 0 X = 1, Y = 0, Z = 1 X = 1, Y = 1, Z = 0 X = 1, Y = 1, Z = 1 
 
As we shall see, we prefer truth tables for functions of not too many variables. 
 
Page 93 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
 Chapter 3 – Boolean Algebra and Combinational Logic 
The figure at left is a truth table for a two-variable function.  Note that 
we have four rows in the truth table, corresponding to the four possible 
combinations of values for X and Y.  Note also the standard order in 
which the values are written: 00, 01, 10, and 11.  Other orders can be 
used when needed (it is done below), but one must list all combinations. 
X Y F(X, Y) 
0 0 1 
0 1 0 
1 0 0 
1 1 1 
 
For another example of truth tables, we consider the figure at 
the right, which shows two Boolean functions of three Boolean 
variables.  Truth tables can be used to define more than one 
function at a time, although they become hard to read if either 
the number of variables or the number of functions is too large.  
Here we use the standard shorthand of F1 for F1(X, Y, Z) and 
F2 for F2(X, Y, Z).  Also note the standard ordering of the 
rows, beginning with 0 0 0 and ending with 1 1 1.  This causes 
less confusion than other ordering schemes, which may be used 
when there is a good reason for them. 
X Y Z F1 F2 
0 0 0 0 0 
0 0 1 1 0 
0 1 0 1 0 
0 1 1 0 1 
1 0 0 1 0 
1 0 1 0 1 
1 1 0 0 1 
1 1 1 1 1 
 
As an example of a truth table in which non-standard ordering might be useful, consider the 
following table for two variables.  As expected, it has four rows. 
 
A truth table in this non-standard ordering would be used to 
prove the standard Boolean axioms: 
 X • 0 = 0 for all X  X + 0 = X for all X 
X Y X • Y X + Y 
0 0 0 0 
1 0 0 1 
0 1 0 1 
1 1 1 1 
 X • 1 = X for all X  X + 1 = 1 for all X 
 
 
In future lectures we shall use truth tables to specify functions without needing to consider 
their algebraic representations.  Because 2
N
 is such a fast growing function, we give truth 
tables for functions of 2, 3, and 4 variables only, with 4, 8, and 16 rows, respectively.  Truth 
tables for 4 variables, having 16 rows, are almost too big.  For five or more variables, truth 
tables become unusable, having 32 or more rows. 
 
Labeling Rows in Truth Tables 
We now discuss a notation that is commonly used to identify rows in truth tables.  The exact 
identity of the rows is given by the values for each of the variables, but we find it convenient 
to label the rows with the integer equivalent of the binary values.  We noted above that for N 
variables, the truth table has 2
N
 rows.  These are conventionally numbered from 0 through  
2
N
 – 1 inclusive to give us a handy way to reference the rows.  Thus a two variable truth table 
would have four rows numbered 0, 1, 2, and 3.  Here is a truth-table with labeled rows. 
 
   We can see that G(A, B) = A ? B, but 
0  = 0 •2 + 0•1  this value has nothing to do with the 
1  = 0 •2 + 1•1  row numberings, which are just the 
2  = 1 •2 + 0•1  decimal equivalents of the values in  
3  = 1 •2 + 1•1  the A & B columns as binary. 
Row A B G(A, B) 
0 0 0 0 
1 0 1 1 
2 1 0 1 
3 1 1 0 
Page 94 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
 Chapter 3 – Boolean Algebra and Combinational Logic 
A three variable truth table would have eight rows, numbered 0, 1, 2, 3, 4, 5, 6, and 7.  Here 
is a three variable truth table for a function F(X, Y, Z) with the rows numbered. 
 
Note that the row numbers correspond to the 
decimal value of the three bit binary, thus 
 0 = 0•4 + 0•2 + 0•1 
 1 = 0•4 + 0•2 + 1•1 
 2 = 0•4 + 1•2 + 0•1 
 3 = 0•4 + 1•2 + 1•1 
 4 = 1•4 + 0•2 + 0•1 
 5 = 1•4 + 0•2 + 1•1 
 6 = 1•4 + 1•2 + 0•1 
 7 = 1•4 + 1•2 + 1•1 
Row 
Number 
X Y Z F(X, Y, Z) 
0 0 0 0 1 
1 0 0 1 1 
2 0 1 0 0 
3 0 1 1 1 
4 1 0 0 1 
5 1 0 1 0 
6 1 1 0 1 
7 1 1 1 1 
 
Truth tables are purely Boolean tables in which decimal numbers, such as the row numbers 
above do not really play a part.  However, we find that the ability to label a row with a 
decimal number to be very convenient and so we use this.  The row numberings can be quite 
important for the standard algebraic forms used in representing Boolean functions. 
 
 
Question: Where to Put the Ones and Zeroes 
Every truth table corresponds to a Boolean expression.  For some truth tables, we begin with 
a Boolean expression and evaluate that expression in order to find where to place the 0’s and 
1’s.  For other tables, we just place a bunch of 0’s and 1’s and then ask what Boolean 
expression we have created.  The truth table just above was devised by selecting an 
interesting pattern of 0’s and 1’s.  The author of these notes had no particular pattern in mind 
when creating it.  Other truth tables are more deliberately generated. 
 
Let’s consider the construction of a truth table for the Boolean expression. 
F(X, Y, Z) = Z Y X Z Y Y X • • + • + • 
 
Let’s evaluate this function for all eight possible values of X, Y, Z. 
 X = 0 Y = 0 Z = 0 F(X, Y, Z) = 0 •0 + 0•0 + 0•1•0 = 0 + 0 + 0 = 0 
 X = 0 Y = 0 Z = 1 F(X, Y, Z) = 0 •0 + 0•1 + 0•1•1 = 0 + 0 + 0 = 0 
 X = 0 Y = 1 Z = 0 F(X, Y, Z) = 0 •1 + 1•0 + 0•0•0 = 0 + 0 + 0 = 0 
 X = 0 Y = 1 Z = 1 F(X, Y, Z) = 0 •1 + 1•1 + 0•0•1 = 0 + 1 + 0 = 1 
 X = 1 Y = 0 Z = 0 F(X, Y, Z) = 1 •0 + 0•0 + 1•1•0 = 0 + 0 + 0 = 0 
 X = 1 Y = 0 Z = 1 F(X, Y, Z) = 1 •0 + 0•1 + 1•1•1 = 0 + 0 + 1 = 1 
 X = 1 Y = 1 Z = 0 F(X, Y, Z) = 1 •1 + 1•0 + 1•0•0 = 1 + 0 + 0 = 1 
 X = 1 Y = 1 Z = 1 F(X, Y, Z) = 1 •1 + 1•1 + 1•0•1 = 1 + 1 + 0 = 1 
 
Page 95 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
 Chapter 3 – Boolean Algebra and Combinational Logic 
From the above, we create the truth table for the function.  Here it is. 
 
X Y Z F(X, Y, Z) 
0 0 0 0 
0 0 1 0 
0 1 0 0 
0 1 1 1 
1 0 0 0 
1 0 1 1 
1 1 0 1 
1 1 1 1 
 
A bit later we shall study how to derive Boolean expressions from a truth table.  Truth tables 
used as examples for this part of the course do not appear to be associated with a specific 
Boolean function.  Often the truth tables are associated with well-known functions, but the 
point is to derive that function starting only with 0’s and 1’s. 
 
Consider the truth table given below, with no explanation of the method used to generate the 
values of F1 and F2 for each row. 
 
Row X Y Z F1 F2 
0 0 0 0 0 0 
1 0 0 1 1 0 
2 0 1 0 1 0 
3 0 1 1 0 1 
4 1 0 0 1 0 
5 1 0 1 0 1 
6 1 1 0 0 1 
7 1 1 1 1 1 
Figure: Our Sample Functions F1 and F2 
 
Students occasionally ask how the author knew where to place the 0’s and 1’s in the above 
table.  There are two answers to this, both equally valid.  We reiterate the statement that a 
Boolean function is completely specified by its truth table.  Thus, one can just make an 
arbitrary list of 2
N
 0’s and 1’s and then decide what function of N Boolean variables has been 
represented.  In that view, the function F2 is that function specified by the sequence 
(0, 0, 0, 1, 0, 1, 1, 1) and nothing more.  We can use methods described below to assign it a 
functional representation.  Note that F2 is 1 if and only if two of X, Y, and Z are 1.  Given 
this, we can give a functional description of the function as F2 = X •Y + X •Z + Y •Z. 
 
As the student might suspect, neither the pattern of 0’s and 1’s for F1 nor that for F2 were 
arbitrarily selected.  The real answer is that the instructor derived the truth table from a set of 
known Boolean expressions, one for F1 and one for F2.  The student is invited to compute 
the value of F2 = X •Y + X •Z + Y •Z for all possible values of X, Y, and Z; this will verify 
the numbers as shown in the truth table. 
Page 96 CPSC 5155 Last Revised On September 3, 2008 
 Copyright © 2008 by Ed Bosworth 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!