Page 1 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
MODULE 1
Principles of Combinational logic
Structure
1.1 Objective
1.2 Introduction
1.3 Review of Boolean Algebra.
1.4 Definition of combinational
1.5 Canonical forms
1.6 Generation of switching equations from truth tables
1.7 Karnaugh maps-3, 4 and 5 variables. Incompletely specified functions (Don’t care terms).
1.8 Simplifying max - term equations.
1.9 Quine -McClusky minimization technique, Quine - McClusky using don’t care terms,
1.10 Reduced Prime Implicant tables,
1.11 Map entered variables.
1.12 Outcome
1.13 Future Readings
1.1 Objevtive
• Student at the end will be able represent a expression from TT or vice versa
• Different types of reducing a expression so that the Boolean expression
obtained will have minimum variables which in tern help in reducing the
component size.
• Advantages and disadvantages od reduction technique.
1.2 Introduction
Logic Circuits are categorized into 2 types (based on whether they contain memory or not):
• Combinational Logic Circuits- Circuits without memory
• Sequential Logic Circuits- Circuits with memory
1.3 Review of Boolean Algebra.
Example 1:
xy+xy+x y = x+y
LHS x(y+y)+ x y using distributive law
1
www.vtuloop.com
Page 2 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
x •1+ x y using y+y = 1 theorem
x(1+ y ) +x y (1+y) =1 theorem
x+ x y + x y using distributive law
x + y(x+ x)
x + y• 1 = x +y RHS
Example 2:
(x+y)(x+z) = xz+xy using distributive law
x x + x z + x y + y z using P5 postulate
x z + x y +(x+x) yz using distributive law
xz+ x y + xyz+xyz using distributive law
xz(1+y) +x y(1+z) using T2 theorem
xz•1 +xy • 1 = xz + xy RHS
PRINCIPLE OF DUALITY
One can transform the given expression by interchanging the operation (+) and (•) as
well as the identity elements 0 and 1 . Then the expression will be referred as dual
of each other. This is known as the principle of duality.
Example x + x = 1 then the dual expression is
x • x = 0
BOOLEAN FORMULAS AND FUNCTIONS
Boolean expressions or formulas are constructed by using Boolean constants and
variables with the Boolean operations like (+) , (•) and ‘not’
Example: (x + y) z
f(x,y.z) = (x +y) z or f = (x +y) z
x y z x y x z x y z f
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
0
0
0
0
1
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
1
Truth table for the above Boolean expression is
2
www.vtuloop.com
Page 3 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
Example 2: Write a truth table for following function
f = x y z + x y + x z
x y z x y x z x y z f
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
0
0
0
0
1
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
1
1.4 Definition of combinational
1. 4.1 COMBINATIONAL NETWORK
The inter connections 0f gates result in a gate network. If the network has the
property that its outputs at any time are determined strictly by the inputs at that time
then the network is said to be a combinational network. Ex. Adders. Multiplexers. etc
Let us consider an set of n signals at any time is called input state or input vector
of the network. While a set of resulting signals appearing at the m output terminals is
called the output state or output vector. The network can be expressed as
z1, z2,......zm as Boolean function then
Zi = fi(x1,x2,....xn) for i= 1,2,...m.
1.4.2. SEQUENTIAL NETWORKS
A second type of logic network is the sequential networks. Sequential network have
memory property, so that the the outputs from these networks are dependent not only
upon the current inputs but upon previous input as well. Feed back path are used in
the sequential circuits. Ex. Counters. Shift registers etc.
3
www.vtuloop.com
Page 4 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
1.4.3 ANALYSIS PROCEDURE
Analysis procedure for a combinational network is as follows
1. Each gate output that is only a function of the input variables is labeled.
2. Boolean algebraic expression for the outputs of each of these gates are then written.
3. Next these gates outputs that are a function of just inputs variables and previously
labeled gate outputs.
4. Then each of the previously defined labels is replaced by the already written
Boolean expression and this process is continued until the output of the network is
labeled and till final expression is obtained.
f(w,x,y,z) = w•(y+z) + wxy
= w•G1 + G2
f(w,x,y,z) = G2 + G3
•General Procedure
NORMAL FORMULAS
• Boolean expression can be represented by
following structures
1. Sum of products ( SOP or disjunctive normal form
2. Product of sum (POS or Conjunctive form
•In SOP normal form is a Boolean formula that is written as a single product term or
as a sum ( also called disjunctive) of product terms is said to be in the sum of
product form or disjunctive normal form.
4
www.vtuloop.com
Page 5 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
Example:
f(w,x,y,z) = x + w y + w y z
In the POS normal form is a Boolean formula which is written as a single sum
term or as a product of sum ( also called conjunctive) terms is said to be in
product of sums form or conjunctive normal form.
Example:
f(w,x,y,z) = z (x + y) (w + y + z)
1.5 Canonical forms
A procedure which will be used to write Boolean expressions form truth table is
known as canonical formula. The canonical formulas are of two types
• Minterm canonical formulas
• Maxterm canonical formulas
1. 5.1 MINTERM CANONICAL FORMULAS
Minterms are product of terms which represents the functional values of the variables
appear either in complemented or un complemented form.
Ex: f(x,y,z) = x y z + x y z + x y z
The Boolean expression which is represented above is also known as SOP or
disjunctive formula
The truth table is
x y z f
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
1
0
1
1
0
0
0
m- NOTATION
To simplify the writing of a minterm in canonical formula for a function is
performed using the symbol mi. Where i stands for the row number for which the
function evaluates to 1.
The m-notation for 3- variable an function Boolean function
f(x,y,z) = x y z + x y z + x y z is written as
f(x,y,z) = m1+ m3 + m4 or
5
www.vtuloop.com
Page 6 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
f(x,y,z) = ∑m(1,3,4)
A three variable m- notation truth variable
x y z
Decimal designator of
row
Minterm m-notation
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
1
2
3
4
5
6
7
x y z
x y z
x y z
x y z
x y z
x y z
x y z
x y z
m0
m1
m2
m3
m4
m5
m6
m7
1.5.2. MAXTERM CANONICAL FORM
Maxterm are sum terms where the variable appear once either in complement or un- complement
forms and these terms corresponds to a functional value representing 0.
Ex. f(x,y,z) = ( x+ y+ z ) ( x+ y+z ) ( x + y + z )
= ∏M( 0, 2, 5)
= M0, M2, M5
M-NOTATION
A maxterm in a canonical form can be represented as Mi. Where i stands for row
number for which the the function evaluates to 0. A product of maxterms are
represented as ΠM.
1.5.3 . MINTERM CANONICAL FORMULA
1. Apply DeMorgan’s law a sufficient no. of times until all the NOT operations appear
only with the single variables.
2. Apply distributive of AND over OR (•) over (+) i.e. x•(y+z) = xy+xz in order to
manipulate the formula into disjunctive normal formula.
3. Remove duplicate literals and turns by idempotent law well as any term that are
identically zero (x•x = 0)
6
www.vtuloop.com
Page 7 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
4. If any product in the disjunctive normal formula does not contain all the variables
of the Boolean function then these missing variables are introduced by ANDing the
terms with logic 1 in the form of xi+xi where xi is the missing variable being
introduced. This process is repeated for each missing variables in each of the product
turns of the disjunctive normal form
5. Apply distributive of ( •) over (+) again so that each variable appears exactly once
in each term.
6. Remove duplicate term if any.
Example : ( x + y) + ( y + x z )( x + y)
1.5.4 . MAXTERM CANONICAL FORMULA
1. Apply DeMorgan’s law until all the NOT operations appear with single variables.
2. Apply distributive law of (+) over (•) i.e. (x+yz) = (x+y)(x+z) and bring the
expressions into its conjugate normal form (POS).
3. The missing variables are introduced into the sum terms by OR ing logic 0’s in the
form xi •xi = 0 where xi is missing variable.
4. Distributive law of (+) over (•) is again applied.
5. Duplicate literals are deleted.
Ex: f(x,y,z) = ( x + y ) + ( y+ x z )( x + y )
1.5.6. COMPEMENTS OF CANONICAL FORMULAS
Even by taking complements minterm expression may result different expressions.
Ex : f(x,y,z) = ∑m(0, 2, 4, 6) its complement expression is
f(x,y,z) = ∑m(1, 3, 5,7)
Similarly
A Maxterm canonical expression may be represented in completed for as follows
Ex : f(x,y,z) = Π M (1, 2, 4, 7) its complement expression is
f(x,y,z) = Π M (0 3, 5,6)
1.6 Generation of switching equations from truth tables,
1.7 Karnaugh maps-3, 4 and 5 variables. Incompletely specified functions (Don’t care
terms).
7
www.vtuloop.com
Page 9 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
0 1 0 f(0,1,0)
0 1 1 f(0,1,1)
1 0 0 f(1,0,0)
1 0 1 f(1,0,1)
1 1 0 f(1,1,0)
1 1 1 f(1,1,1)
FOUR VARIABLE : Four variable needs a map of 24
= 16 cells. The arrangement of cells are as
follows
w x y z f(w,x,y,z) w x y z f(w,x,y,z)
0 0 0 0 f(0,0,0,0) 1 0 1 0 f(1,0,1,0)
0 0 0 1 f(0,0,0,1) 1 0 1 1 f(1,0,1,1)
0 0 1 0 f(0,0,1,0) 1 1 0 0 f(1,1,0,0)
0 0 1 1 f(0,0,1,1) 1 1 0 1 f(1,1,0,1)
0 1 0 0 f(0,1,0,0) 1 1 1 0 f(1,1,10)
0 1 0 1 f(0,1,0,1) 1 1 1 1 f(1,1,1,1)
0 1 1 0 f(0,1,1,0)
0 1 1 1 f(0,1,1,1)
1 0 0 0 f(1,0,0,0)
1 0 0 1 f(1,0,0,1)
0000 0001 0011 0010
0100 0101 0111 1010
1100 1101 1111 1110
1000 1001 1011 1010
Obtain the minterm canonical formula of the three variable problem given below
9
www.vtuloop.com
Page 11 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
1
1 1
1 1 1
1
Typical group of four adjacent subcubes
1 1
1 1
1 1 1 1
Typical group of four adjacent subcubes.
Typical group of Eight adjacent subcubes.
1
1
1
1
1 1
1 1
1 1
1 1
11
www.vtuloop.com
Page 12 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
USING K-MAP TO OBTAIN MINIMAL EXPRESSION FOR COMPLETE BOOLEAN FUNCTIONS :
How to obtain a minimal expression of SOP or POS of given function is discussed.
PRIME IMPLICANTS and K-MAPS :
CONCEPT OF ESSENTIAL PRIME IMPLICANT
00 01 11 10
0 0 0 1
0 0 1 1
f(x,y,z)= xy+ yz
12
www.vtuloop.com
Page 16 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
(1) Incompletely Specified Functions (Don’t Care Terms)
Don’t care: minterms or maxterms that are not used as part of the output
Ex: Binary to EX-3 BCD code conversion
Binary EX-3 BCD
W X Y Z A B C D
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
1
1
1
1
1
X
X
X
X
X
X
0
1
1
1
1
0
0
0
0
1
X
X
X
X
X
X
1
0
0
1
1
0
0
1
1
0
X
X
X
X
X
X
1
0
1
0
1
0
1
0
1
0
X
X
X
X
X
X
16
www.vtuloop.com
Page 20 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
Determination of prime-implicant
Step 1 Step 2 Step 2
A B C D A B C D
0 0 0 0 0 0,1(1) 0,1,2,3(1,2) 0 0 - -
1 0 0 0 1 0,2(2) 0,1,2,3(1,2) 0 0 - -
2 0 0 1 0 1,3(2) 1,3,5,7(2,4) 0 - - 1
3 0 0 1 1 1,5(4) 1,3,5,7(2,4) 0 - - 1
5 0 1 0 1 2,3(1) 3,7,11,15(4,8) - - 1 1
7 0 1 1 1 3,7(4) 3,7,11,15(4,8) - - 1 1
11 1 0 1 1 3,11(8)
15 1 1 1 1 5,7(2)
7,15(8)
11,15(4)
Prime-implicant table
Minterms
1 3 7 11 15
0,1,2,3(00--) X X
1,3,5,7(0--1) X X X
3,7,11,15(--11) X X X X
F = A′B′ + CD or F = A′D +C
Ex.
F A,B,C,D m1, 4,6,7,8,9,10,11,15
Determination of prime-implicant
Step 1 Step 2 Step 2
ABCD A B C D
1 0 0 0 1 1,9(8) 8,9,10,11(1,2) 0 0 - -
4 0 1 0 0 4,6(2) 8,9,10,11(1,2) 0 0 - -
8 1 0 0 0 8,9(1)
6 0 1 1 0 8,10(2)
9 1 0 0 1 6,7(1)
10 1 0 1 0 9,11(2)
7 0 1 1 1 10,11(1)
11 1 0 1 1 7,15(8)
15 1 1 1 1 11,15(4)
Prime-implicant table
Minterms
1 4 6 7 8 9 10 11 15
1,9(-001) X X
4,6(01-0) X X
6,7(011-) X X
7,15(-111) X X
20
www.vtuloop.com
Page 21 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
11,15(1-11) X X
8,9,10,11(10--) X X X X
F BCD ABD BCD AB
1.10 Reduced Prime Implicant tables,
PRIME IMPLICATE: If the implicate does not subsumes any other implicate with fewer
literals of the same function. In other words if we remove prime implicate term from the
expression the remaining sum terms no longer implies the function
Ex. x and (y + z) are prime implicates
x y z f
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
0
0
1
0
1
1
Ex1: Minimize f (A, B, C, D) = Σ (0, 1, 2, 8, 9, 15, 17, 21, 24, 25, 27, 31).
21
www.vtuloop.com
Page 22 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
The prime implicants P5, P7, and P10 are essential. They are included in the solution. They do
not cover all the minterms. So secondary essential prime implicants have to be found by using
the reduced prime implicant chart.
Reduced Prime Implicant Chart (Essential prime implicants removed)
We are not able to find columns with single ‘X’. Now we find the dominance relations.
Column Dominance:
9 > 8
25 > 24
Row Dominance:
P1 > P7
P6 > P4
P2 > P9
P2 > P11
22
www.vtuloop.com
Page 23 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
Prime Implicant Chart Reduction Steps:
All the dominating columns and dominated rows of a prime-implicant chart can be
removed without affecting the table for obtaining a minimal solution.
Dominating column is guaranteed to be covered by the row that covers its dominated
column.
The columns of the dominated row are guaranteed to be covered by its dominating row.
Finding Secondary Essential PIs:
PI Chart after the dominating columns and the dominated rows are deleted:
Final Solution
Minterm 1 can be covered by P2 or P3. If we select P2, we have the solution:
Y = P1 + P2 + P5 + P6 + P8 + P10
1.11 Map entered variables.
In entered variable map one of the input variables is placed inside Karnaugh map. This is done
separately noting how the input variable is related with output. This reduces the Karnaugh map
size by one degree. This technique is particularly useful for mapping problems with more than
four input variables.
Example:
Consider the 3-variable truth table as shown below. The output Y is rewritten in terms of
variable C.
23
www.vtuloop.com
Page 24 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
The 3 – variable truth table reduces to 2 – variable truth table as shown below:
The 2 – variable Karnaugh map is drawn as shown below:
The Karnaugh map is now called an entered variable map. The simplification of entered variable
map is as illustrated next:
The product term representing each group is obtained by including map entered variable in the
group as an additional ANDed term. Group 1 gives B.(C’) and group 2 gives AB.1. Therefore,
the simplified expression is obtained as Y = BC’ + AB.
24
www.vtuloop.com
Page 25 of 25
Digital System Design 17EE35
Dept. EEE, ATMECE, Mysuru
1.12 Outcome
• Representation of Boolean expression in canonical forms.
• Reduce gates with minimum number of variable using different techniques.
1.13 Future Readings
http://nptel.ac.in/courses/117105080/
https://www.youtube.com/watch?v=VnZLRrJYa2I
“Logic Design” by RD Sudhaker Samuel
“Digital Logic Applications and Design” by John M Yarbrough, 2011 edition.
25
www.vtuloop.com