Chapter 5-6

Combinational Logic Circuits

 Binary Logic and Gates
Digital circuits are hardware components that manipulate binary information and
are called integrated circuits.
A basic circuit is called a logic gate. We are only interested in the external logic
properties of the gate and not its internal electronics.
Binary logic system is a mathematical notation used to describe the operation of
gates which is called boolean algebra.
Binary logic:
deals with binary values which can either be 0 or 1.
The three basic logical operations are called:
AND, OR and NOT.
A Truth Table is:
a table of the possible combinations that the variables can take and the values of
the result.
 Binary Logic
AND is represented by:
Z=X.Y or Z=XY
0.0=0 AND
X Y Z = X.Y
0.1=0 0 0 0

1.0=0 0 1 0
1 0 0
1.1=1 1 1 1 or Z = X ∧ Y
OR is represented by:
Z=X+Y 0+0=0 OR
X Y Z=X+Y
0+1=1 0 0 0
0 1 1
1+0=1 1 0 1
1+1=1 1 1 1 or Z = X ∨ Y
NOT is represented by NOT
(called complement
X Z=X
operation):
0 1
1 0
 Logic Gates
Logic gates are electronic circuits that operates on one or more inputs.
Voltage operated circuits accept binary inputs within certain ranges and respond at the output
terminal with binary signal that fall within allowable range.
The intermediate ranges are crossed only when changing from 1 to 0 or from 0 to 1. These are
called transition regions which are crossed during transitions.

AND Gate: X
Z = X.Y
Y X 0 0 1 1
Y 0 1 0 1
Z 0 0 0 1
→ tG ←
Z 0 0 0 1
How about the timing changes of the gates?
Gate delay: the length of time it takes for an input change to result in the corresponding output
change.
 Logic Gates
OR Gate: X
Z=X+Y
Y

X 0 0 1 1
Y 0 1 0 1
Z 0 1 1 1 NOT Gate:
X Z=X

X 0 0 1 1
Z 1 1 0 0
 Boolean Algebra
Boolean Expression is an algebraic expression formed by using binary variables, the constants 0
and 1, the logic operation symbols and parentheses.
Boolean function can be single output or multiple output.

Three input AND Gate:

A
F = ABC
B
C

Six input OR Gate:

A
B
C F = A + B+C+ D+ E + F
D
E
F
 Basic Identities of Boolean Algebra
The first nine identities are about the relationship between a single variable X and its
complement and the binary constants 0 and 1.
X const ?
1) X + 0 = X 0 0 0
1 0 1
Duality nature of Boolean Algebra: The dual nature of an algebraic expression is obtained by
interchanging OR and AND operations and replacing 1s by 0s and 0s by 1s.
X const ?
2) X.1 = X 0 1 0
1 1 1
The dual of an expression is not usually equal to the original expression. An expression can not
be replaced by its dual.

X const ?
3) X +1 = 1 0 1 1 4) X.0 = 0
1 1 1
Basic Identities of Boolean Algebra
X X ?
5) X + X = X 0 0 0 6) X.X = X
1 1 1

X X ?
7) X + X = 1 0 1 1 8) X.X = 0
1 0 1

X X X
9) X = X 0 1 0
1 0 1
 X(Y + Z) XY + XZ
Commutative property X Y Z Y+Z XY XZ
10) X + Y = Y + X 0 0 0 0 0 0 0 0
11) XY = YX 0 0 1 1 0 0 0 0

Associative property 0 1 0 1 0 0 0 0
12) X + (Y + Z) = ( X + Y ) + Z 0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
13) X(YZ) = ( XY )Z
Distributive property 1 0 1 1 1 0 1 1
14) X (Y + Z ) = XY + XZ 1 1 0 1 1 1 0 1
15) X + (YZ ) = ( X + Y )( X + Z ) 1 1 1 1 1 1 1 1

DeMorgan’s theorem
(complement of an expression) X Y X+Y X+Y X Y X.Y
0 0 0 1 1 1 1
16) X + Y = X.Y
0 1 1 0 1 0 0
17) X.Y = X + Y
For three or more variables: 1 0 1 0 0 1 0
X1 + X 2 + ....... + X n = X1X 2 ......X n 1 1 1 0 0 0 0
X1X 2 ......X n = X1 + X 2 + ....... + X n
 Algebraic Manipulation
Boolean algebra is useful for simplifying digital
X
circuits.
Example 2: The Boolean function is
represented by: F = X YZ + X Y Z + XZ
The implementation of this equation by gates Y F
is as shown: Z
The equation has 3 terms and 8 literals.
Can we simplify this equation?
Yes, as follows:

F = X YZ + X Y Z + XZ
= X Y (Z + Z ) + XZ
X
= X Y .1 + XZ
Y
= X Y + XZ F

Two terms instead of three terms equation. Z

The implementation of this equation by gates
is as shown:
The equation has 2 terms and 4 literals.
The following examples use identities of Boolean algebra to simplify equations:

1) X + XY = X .1 + XY = X (1 + Y ) = X .1 = X

2) XY + X Y = X (Y + Y ) = X .1 = X
3) X + X Y = (X + X )( X + Y ) = 1.( X + Y ) = X + Y

Lets take the dual of the above expressions:

4) X ( X + Y ) = X . X + X .Y = X + XY = X (1 + Y ) = X .1 = X
5) ( X + Y )(X + Y ) = X + YY = X +0 = X
6) X (X + Y ) = X X + XY = 0 + XY = XY

The above are six theorems of Boolean Algebra.

Example1: Prove the following consensus theorem:
XY + X Z + YZ = XY + X Z
Solution: We will use the following identity:
(X + X ) = 1
XY + X Z + YZ = XY + X Z + YZ ( X + X )

= XY + X Z + XYZ + X YZ

= XY + XYZ + X Z + X YZ

= XY (1 + Z ) + X Z (1 + Y )

= XY + X Z
Example2: Take the duality of the above equation:
Solution: ( X + Y )(X + Z )(Y + Z ) = ( X + Y )(X + Z )
Example 3: Simplify the following: ( A + B )( A + C )
Solution: ( A + B )(A + C ) = A A + AC + AB + BC
= AC + AB + BC
= AC + AB + BC
Example 4: Find the complement of each of the equations?

F1 = X Y Z + X Y Z F2 = X (Y Z + YZ )

Solution: We will use DeMorgan’s theorem as many times needed.

F1 = X Y Z + X Y Z

= (X Y Z )(
. X YZ )

= (X + Y + Z )(X + Y + Z )

F2 = X (Y Z + YZ )

= X + (Y Z + YZ )

(
= X + Y Z .YZ )
= X + (Y + Z )(Y + Z )
Example 5: Find the complement of each of the equations by using duals?

F1 = X Y Z + X Y Z F2 = X (Y Z + YZ )

Solution: Take the dual of the equation and then complement each literal.

We begin with:

F1 = (X Y Z ) + ( X Y Z )
The dual is: = (X + Y + Z )(X + Y + Z )
By complementing each literal we get:
= (X + Y + Z )( X + Y + Z ) = F1

We do the same for the second equation:

F2 = X ((Y Z ) + (YZ ))

= X + ((Y + Z )(Y + Z ))

= X + (Y + Z )(Y + Z ) = F2
 Standard Forms
A standard form will facilitate the simplification process of Boolean expressions which is favored
in implementing logic circuits.
A standard form contains:
1) Product terms
2) Sum terms
Product term: AND operation
Sum term: OR operation

AND OR
X Y Z = X.Y X Y Z=X+Y
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
 Standard Forms
Minterms
A boolean function is defined using a truth table by taking the sum of product terms.
A product term in which each literal appear exactly once is called a minterm.
Its one combination of all variables in the truth table X Y Z m0
to get a value of 1. 0 0 0 1
X Y Z m0
The four minterms for two variables are:
0 0 1 X YZ m1 0
XY , X Y , X Y , X Y
0 1 0 X Y Z m2 0
The eight minterms for three variables are shown:
We have n=3, so 8 possible combinations and so 8 0 1 1 X YZ m3 0
minterms. 1 0 0 X Y Z m4 0
It is clear that a minterm is a function that is not
1 0 1 X Y Z m5 0
equal to 0 and has the minimum number of 1s in its
truth table. 1 1 0 XY Z m6 0
A boolean function can be represented from this 1 1 1 XYZ m7 0
truth table by taking the sum of all minterms that
produce a 1. This is called sum of minterms.
 Maxterms
A boolean function is defined using a truth table by taking the product of sum terms.
A sum term in which each literal appear exactly once is called a Maxterm.
Its one combination of all variables in the truth table to get a value of 0.
The four Maxterms for two variables are: X + Y , X + Y , X + Y , X + Y
The eight Maxterms for three variables are shown:
We have n=3, so 8 possible combinations and so 8 Maxterms.
It is clear that a Maxterm is a
function that is not equal to 1 X Y Z M0
and has the minimum number 0 0 0 X +Y + Z M0 0
of 0s in its truth table. 0 0 1 1
X +Y + Z M1
A boolean function can be
represented from this truth 0 1 0 X +Y + Z M2 1
table by taking the product of 0 1 1 X +Y + Z M3 1
all Maxterms that produce a 0. 1 0 0 1
X +Y + Z M4
This is called product of
Maxterms. 1 0 1 X +Y + Z M5 1
We find that: M = m 1 1 0 X +Y + Z M6 1
j j
and m j = M j 1 1 1 X +Y + Z M7 1
For: j = 3
M 3 = X + Y + Z = X YZ = m3
Example 6: Find the SOP for the following boolean function:
F = X Y Z + X Y Z + X Y Z + XYZ
Solution: X Y Z F F
The function is equal to 1 for the following combinations: 0 0 0 1 0
000, 010, 101 and 111 which correspond to minterms:
0 0 1 0 1
= m0 + m2 + m5 + m7
This can be abbreviated as follows: 0 1 0 1 0
F ( X , Y , Z ) = ∑ m(0,2,5,7 ) 0 1 1 0 1
1 0 0 0 1
Example 7: Find the POS for the same function:
Solution: 1 0 1 1 0
Now consider the complement of the boolean function: 1 1 0 0 1
F = X Y Z + X YZ + X Y Z + XY Z 1 1 1 1 0
= m1 + m3 + m4 + m6
F ( X , Y , Z ) = ∑ m(1,3,4,6 )
Then:
F = m1 + m3 + m4 + m6
= m1.m3.m4 .m6
= M1.M 3.M 4 .M 6
= (X + Y + Z )(X + Y + Z )(X + Y + Z )( X + Y + Z )
F ( X , Y , Z ) = ∏ M (1,3,4,6)
The most important properties of minterms:

1) There are 2n minterms for n boolean variables.

2) Any boolean function can be expressed as a logical sum of minterms.

3) The complement of a function contains all minterms not included in the function.

4) A function containing all 2n minterms is equal to 1.

The sum of all minterms is equal to 1.

G ( X , Y ) = ∑ m(0,1,2,3) = 1

5) A sum of minterms function can be obtained directly from the truth table.

6) The function contains the maximum number of literals because each term contains all
variables by definition.

7) Once the sum of minterms has been obtained, next we try to simplify the function.
Example 8: Convert following boolean function to a SOP or sum of minterms?
E =Y + XZ
X Y Z E
Solution: 0 0 0 1
The equation is not a sum of minterms because each term doesn’t 0 0 1 1
include the three variables.
0 1 0 1
E ( X , Y , Z ) = ∑ m(0,1,2,4,5) 0 1 1 0

The minterms of the complement are: 1 0 0 1

1 0 1 1
E ( X , Y , Z ) = ∑ m(3,6,7 )
1 1 0 0
1 1 1 0
Example 9: Implement the following Sum of products?
F = Y + X Y Z + XY
Y
Solution: X
A simplified sum of products is the following: Y F
F = Y + X Y Z + XY Z
To implement it with gates, we can see that it
X
consists of AND gates followed by OR gate. Y
This diagram shows two level implementation or
two level circuit.

A
F
B
Example 10: Implement the following equation?
C
F = AB + C ( D + E ) D
Solution: E

F = AB + C ( D + E ) A
Is there another way? B
C F
F = AB + CD + CE D
E
F
Example 11: Implement the following Products of sums?
F = X (Y + Z )(X + Y + Z )
Solution:
X
Y F
Z
X
Y
Is there another way? Z