Digital Logic Circuit

Abragam Siyon Sing M, AP/EEE, SXCCE

 Unit 2

COMBINATIONAL CIRCUITS

Outcome of this unit

At the end of this unit, you will be able to
Apply K-maps for the implementation of combinational circuits.
 Unit 2 - Syllabus

Combinational logic - representation of logic functions-SOP and POS

forms, K-map representations - minimization using K maps -
simplification and implementation of combinational logic –
multiplexers and de multiplexers - code converters, adders,
subtractors, Encoders and Decoders.
Boolean Algebra
 Boolean algebra is a system of mathematical logic, introduced by a
mathematician George Boole in 1854.
 Boolean algebra is the branch of algebra in which the values of
the variables are the truth values, i.e., true and false, usually
denoted as1 and 0, respectively.
 Boolean algebra differs from ordinary algebra and binary number
system.
 It is a binary algebra defined to perform logical operations.
Terminologies used in boolean Algebra
 Variable – The symbol which represent an arbitrary elements of an
Boolean algebra is known as Boolean variable. In an expression, Y=A+BC,
the variables are A, B, C, which can value either 0 or 1.

 Constant – It is a fixed value. In an expression, Y=A+1, A represents a

variable and 1 is a fixed value, which is termed as a constant.

 Literal – Each occurrence of a variable in Boolean function either in

complemented or normal form is said to be literal. For example, in
Y=A+BC+C’+A
Postulates of Boolean Algebra

Sl.No. Name of the Postulates Postulate Equation

1 Law of Identity A+0 =0+A=A

A.1=1 .A=A

2 Commutative Law (A + B) = (B + A)
(A . B) = (B . A)

3 Distributive Law A . (B + C) = (A . B) + (B . C)
A + (B . C) = (A + B) . (B + C)

4 Associative Law A + (B + C) = (A + B) + C
(A . B) . C = A . (B . C)

5 Complement Law A + A' = 1

A . A' = 0
 Sl.No. Theorem Statement Equations
1 Duality Theorem A boolean relation can be derived from another boolean A + A' = 1 and A . A' = 0 are the
relation by changing OR sign to AND sign and vice versa and dual relations.
complementing the 0s and 1s.

2 DeMorgan's Theorem 1 Complement of a product is equal to the sum of its (A . B)' = A' + B'

Theor 3 DeMorgan's Theorem 2

complement.
Complement of a sum is equal to the product of the (A + B)' = A' . B'
complement.
ems 4 Idempotency Theorem - A+A=A
A.A=A
of 5
6
Involution Theorem
Absorption Theorem
-
-
A'' = A
A + (A . B) = A
Boole 7 Associative Theorem -
A . (A + B) = A
A + (B + C) = (A + B) + C

an
A . (B . C) = (A . B) . C
8 Consensus Theorem - AB + A'C + BC = AB + A'C
(A + B) + (A' + C) + (B + C) = (A
Algeb 9 Uniting Theorem -
+ B) + (A' + C)
AB + AB' = A
ra 10 Other theorem -
(A+B) + (A + B') = A
A+1= 1
A.0= 0
11 Other theorem - A + (A' . B) = A + B
A . (A' + B) = A . B
Examples

 Simplify A . (AB + C)
Examples

 Simplify A + A’B
Examples

 Simplify Y = AB’D + AB’D’

Examples
 Simplify Y = (AB’ (C+BD) + A’B’)C
Sum of Product and Product of Sum Form
 Two forms of boolean expressions :
 Sum of Product and
 Product of Sum Form
 Generally, Boolean expressions are built with constants and variables.
These expressions describe the Boolean function.
 For example, in an expression f = A + (B . C), f is a function of the
variables A, B and C.
 In a Boolean function, the variables may appear either in complemented or
in normal form.
 Each occurrence of a variable either in complemented or in normal form is
called a literal.
Product term
 Eg., f = (A . D) + (B’ . C), In this expression, A, B’, C and D are called the
literals.
 How these literals appear in the expression decides the term. Here, the
literals appear in product term.
 A product term is defined as either a literal or a product(conjunction) of
literals.
 For clear understanding, look at the below expression.

 In the above expression, A, (B . C’) and (A . D) are the product terms.

Sum terms
 a sum term is defined as either a literal or a sum(disjunction) of
literals. Look at the below example,

 In this expression, F is the Boolean function, A, A’, B, C’ and D are

the five literals. A, (B + C’) and (A’ + D) are the sum terms.
Sum of Product(SOP) form
 Sum of Product form is a group of product(AND) terms that are
summed(ORed) together.
 Here, the product and sum are not mathematical operations but are binary
operations.
 The SOP expression may consists of two or more product(AND) terms, all
of which are ORed together.
 The SOP form is also called as disjunctive normal form.
Sum of Product(SOP) form
 Standard or Canonical SOP Form
◦ Minterm representation
 Non-canonical SOP form
 Minimal SOP Form
 Conversion of non-canonical SOP to canonical SOP form
Standard or Canonical SOP Form
 If each term in the SOP form contains all the literals in either
complemented or uncomplemented form, then the SOP is referred
to as Canonical or standard SOP form, where each individual term
is called minterm.
Minterm representation
 Minterms are the short hand notations used to express the product
terms in SOP form.
 That is, each individual term in SOP form is called minterm.
 For a Boolean function having n variables, there will be
2n minterms.

 For example, a Boolean function with 3 variables will have 2 3 = 8

minterms and a Boolean unction with 4 variables will have 2 4 = 16
minterms.
Minterms for 3 variable Boolean function
 The canonical SOP expression F = ABC +
A’B’C + ABC’ + A’BC +A’BC’ can be
written as follows in terms of minterm
notation.

F = m7 +m1 + m6 + m3 + m2
F = ∑m(7, 1, 6, 3, 2),
where ∑ denotes sum of product.

 This implies that the given Boolean function is

logically true for the minterms (m7, m1, m6, m3,
m2).
Non-canonical SOP form
 The non-canonical or normal SOP form is a simplified version of standard or
canonical SOP form.
 The normal form is obtained by doing simplification to the standard form.
 Consider the equation and see how it is simplified to get the non-canonical SOP
form.

 The obtained expression F + AB + A’B + A’B’C is in SOP form but literal C is

missing in 1st and 2nd terms. Hence, it is a non-canonical SOP form.
Minimal SOP Form
 it can be made easy by applying Karnaugh map(K map).

 Let us consider the SOP expression

F = ABC + A’B’C + ABC’ + A’BC +A’BC’.
 Using K map, the given expression can be simplified as.
F = A’C + B.

 Among all the three forms, Minimal SOP Form is preferred because it
reduces the complexity of the circuit, thereby reducing the circuit cost, size
and time to fabricate the circuit.
 Conversion of non-canonical SOP to canonical SOP
form
Below are the steps to convert non canonical SOP to Canonical or standard SOP.

 Find the missing literal in each product term.

 AND each product term to the term having missing literal by ORing the
missing literal and its complement.
 Expand the terms and rearrange the literals in the product terms.
 Reduce the expression by omitting the repeated terms if any(i.e. A+A=A)
Example
 Convert the given expression F(A, B, C) = A + B’C into canonical SOP
form.
Product of Sum(POS) Form
 Product of Sum form is a group of Sum(OR) terms that are
Multiplied(ANDed) together.
 Here also, the product and sum are not mathematical operations but are
binary operations.
 The POS expression may consists of two or more sum(OR) terms, all of
which are ANDed together. The POS form is also called as Conjunctive
normal form.
Standard or Canonical POS Form
Maxterm representation
 The canonical POS expression F =
(A+B+C) . (A’+B’+C) . (A+B+C’) .
(A’+B+C) . (A’+B+C’) can be written as
follows in terms of maxterm notation.

F = M0 +M6 + M1 + M4 + M5

F = ΠM(0, 6, 1, 4, 5),
where Π denotes product of sum.

 This implies that the given Boolean function

is logically true for the maxterms (M0, M6,
M1, M4, M5).
Conversion of non-canonical POS to canonical
POS form
 Find the missing literal in each sum term.
 OR each sum term to the term having missing literal by ANDing
the missing literal and its complement.
 Expand the terms and rearrange the literals in the sum terms.
 Reduce the expression by omitting the repeated terms if any(i.e. A .
A = A)
Example
 Convert the given expression F(A, B, C) = (A+B)(B+C) into canonical
POS form.
Conversion between Canonical SOP and
Canonical POS
 let us consider the SOP expression F = ABC + A’B’C + ABC’ + A’BC
+A’BC’.
 in terms of minterm is given by, F = m7 +m1 + m6 + m3 + m2.
 write the expression in terms of maxterm for the remaining terms in the
above minterm expression.
 We get, F = M0 + M4 + M5

 Thus, the canonical POS expression is, F = (A+B+C) . (A’+B+C) .

(A’+B+C’)
Karnaugh Map
 Karnaugh Map is a systematic approach for simplifying a Boolean
expression.
 It was originally introduced by Allan Marquand in the year 1881,
 rediscovered by Edward Veitch in 1952
 modified by Maurice Karnaugh in 1953
 hence called as Veitch diagram or the Karnaugh map.
Karnaugh Map
 The K map contains boxes called as cells.
 Each cell represents one of the 2n possible terms(either product term or sum
term) that can be formed from the variables.
 For example, for a 2 variable map, there will be 2 2 = 4 cells, for a 3
variable map, there will be 23 = 8 cells and so on.
 For labeling, when we move from one cell to the next cell along any row or
column, only one variable changes to either a complemented form or to an
uncomplemented form.
 In other words, the rows and columns of a K map is labelled by the
gray code sequence as shown below.
 The product terms or sum terms are assigned to each cell corresponding to
the product or sum of rows and columns of the particular cell.
 Each cell is numbered from 0 to 7 for 8 cell K map.
 While doing so, cells in the first row is numbered as 0, 1, 3 and 2(the
number order 2 and 3 are reversed as the labeling follow the gray code
sequence 00, 01, 11 and 10).
 The cells in the second row is numbered as 4, 5, 7 and 6.
 Instead of writing the actual product terms in SOP form, the
corresponding minterm notations can be written in the cell.
 Similarly, instead of labeling the rows and columns with the
variable and its complement, they are marked with the gray codes.
 In the same way, K map can be used for simplification of
product of sum(POS) form.
 Instead of writing the actual sum terms in POS form, the
corresponding maxterm notations can be written in the cell.
Plotting a Karnaugh Map
 A logic function either in a truth table format, SOP expression or POS
expression format can be easily plotted in karnaugh map.
 Let us look at the procedure to plot.
 Here I have shown the plotting of 4 cells K-map and 8 cells K-map for
your understanding purpose.
Grouping cells in Karnaugh map
Grouping two adjacent cells (Pair)
Grouping Four adjacent cells (Quad)
Grouping Eight adjacent cells (Octet)
Illegal Grouping of cells
 The cells in the K-map cannot be grouped in some ways, which is said to
be illegal grouping.
Minimization of SOP Boolean function using K-
map
Follow the below procedure to minimize the SOP expression.
 Select the size of the K-map, based on the number of variables present in the
Boolean function.
 Plot the K-map.
 Check the K-map for isolated 1s, which are not adjacent to any other 1s and encircle
those isolated 1s.
 Check the K-map for pair of 1s, which are adjacent to only one other 1s and group it.
 Check the K-map for quads and octets and group them, even if contain any 1s, that
have been already encircled. But be sure to form minimum number of groups.
 Form the expression from the groups that have been encircled by summing them
Problem1
 Let us minimize the expression Y = AB’C + A’B’C + A’BC + AB’C’ +
A’B’C’
Problem2
 Let us minimize the boolean expression Y = ABC’D + ABC’D’ + ABCD +
A’BCD + ABCD’ + A’BCD’.
Problem 3
 Simplify the boolean expression Y(A, B, C, D) = ∑ m (0, 1, 2, 3, 4, 7, 8, 9,
10, 11, 12, 14)
Minimization of POS Boolean function using K-
map
Follow the below procedure to minimize the POS expression.
 Select the size of the K-map, based on the number of variables present in the
Boolean function.
 Plot the K-map by placing 0s for the given Maxterms and place 1s for the remaining
cells.
 Check the K-map for isolated 0s, which are not adjacent to any other 0s and encircle
those isolated 0s.
 Check the K-map for pair of 0s, which are adjacent to only one other 0s and group it.
 Check the K-map for quads and octets and group them, even if contain any 0s, that
have been already encircled. But be sure to form minimum number of groups.
 Form the expression from the groups that have been encircled by summing them.
Problem
 Let us minimize the boolean function Y = (A’+B’+C+D)(A+B’+C+D)(A+B+C+D’)
(A+B+C’+D’)(A’+B+C+D’)(A+B+C’+D).
Problem
 Simplify the boolean function Y(A, B, C, D) = Π M (2, 3, 8, 9, 11, 13, 15).
Don’t care conditions in K-map
 In logic circuit design, there may be a situation, where certain input and output
conditions can never occur.
 In that case, the output can be either 0 or 1, that is, the output cannot be defined for
such inputs and so they are indicated as ‘x’, which represents don’t care output.
Contd.,
 These don’t care outputs are indicated in the boolean expression using a letter d in
the function., where d indicates don’t care condition.

 For the above truth table, the Boolean function can be written as
F(A, B, C) = ∑ m (1, 2, 4) + d (5, 6, 7).

 From the boolean function, it is observed that, the logic is true for minterms 1, 2, 4
and the output is not defined for minterms 5, 6, 7.

 Similarly the Boolean function in terms of maxterm can be written as

F(A, B, C) = Π M (0, 3) + d (5, 6, 7).
Minimization of Boolean function with don’t care
conditions
 Using K-map, the boolean function with don’t care condition can be
minimized by considering either 0 or 1 for don’t care outputs, depending
on the minterms to get the simplest expression.
Problem
 Simplify the boolean function with don’t care conditions Y(A, B, C, D) =
∑ m (1, 3, 7, 11, 15) + d (0, 2, 5).
Problem
 Simplify the boolean function with don’t care conditions Y(A, B, C, D) =
Π M (4, 5, 6, 7, 8, 12) + d (1, 2, 3, 9, 11, 14).
Work out problems
 Minimize the expression using k map : Y = A’BC’D’ + A’BC’D + ABC’D’
+ ABC’D + AB’C’D + A’B’CD’
 Minimize using k map : Y = A’B’CD’ + ABCD’ + AB’CD’ + AB’CD +
AB’C’D’ + ABC’D’ + A’B’CD + A’B’C’D’
 Simplify the boolean function with don’t care conditions F(A, B, C, D) = ∑
m (0,7,8,9,10,12) + d (2,5,13).
 Simplify the boolean function with don’t care conditions F(A, B, C, D) = ∑
m (0, 2, 4, 5, 6, 8, 10, 15) + d (7,13, 14).
 Simplify the boolean function using K-map, F(A, B, C, D) = ∏ M(0, 2, 3,
8, 9, 12, 13, 15).
Work out problems
 Minimize using k map : Y = A’B’CD’ + ABCD’ + AB’CD’ + AB’CD +
AB’C’D’ + ABC’D’ + A’B’CD + A’B’C’D’
 Simplify the boolean function with don’t care conditions F(A, B, C,
D) = ∑ m (0,7,8,9,10,12) + d (2,5,13).
Work out problems
 Simplify the boolean function with don’t care conditions F(A, B, C, D) = ∑
m (0, 2, 4, 5, 6, 8, 10, 15) + d (7,13, 14).
Work out problems
 Simplify the boolean function using K-map, F(A, B, C, D) = ∏ M(0, 2, 3,
8, 9, 12, 13, 15).