Digital Logic Gates

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.

DIGITAL LOGIC DESIGN Page no. 26

 Properties of XOR Gates

• XOR (also ) : the “not-equal” function

• XOR(X,Y) = X  Y = X’Y + XY’
• Identities:
– X 0=X
– X  1 = X’
– X X=0
– X  X’ = 1
• Properties:
– X  Y= Y X
– (X  Y)  W = X  ( Y  W)

Universal Logic Gates

NAND and NOR gates are called Universal gates. All fundamental gates (NOT, AND, OR) can be
realized by using either only NAND or only NOR gate. A universal gate provides flexibility and
offers enormous advantage to logic designers.

NAND as a Universal Gate

NAND Known as a “universal” gate because ANY digital circuit can be implemented with NAND
gates alone.
To prove the above, it suffices to show that AND, OR, and NOT can be implemented using
NAND gates only.

DIGITAL LOGIC DESIGN Page no. 27

 Boolean Algebra: In 1854, George Boole developed an algebraic system now called Boolean algebra. In
1938, Claude E. Shannon introduced a two‐valued Boolean algebra called switching algebra that
represented the properties of bistable electrical switching circuits. For the formal definition of Boolean
algebra, we shall employ the postulates formulated by E. V. Huntington in 1904.

Boolean algebra is a system of mathematical logic. It is an algebraic system consisting of the set of
elements (0, 1), two binary operators called OR, AND, and one unary operator NOT. It is the basic
mathematical tool in the analysis and synthesis of switching circuits. It is a way to express logic functions
algebraically.

Boolean algebra, like any other deductive mathematical system, may be defined with aset of elements, a
set of operators, and a number of unproved axioms or postulates. A set of elements is anycollection of
objects having a common property. If S is a set and x and y are certain objects, then x Î Sdenotes that x is
a member of the set S, and y ÏS denotes that y is not an element of S. A set with adenumerable number of
elements is specified by braces: A = {1,2,3,4}, i.e. the elements of set A are thenumbers 1, 2, 3, and 4. A
binary operator defined on a set S of elements is a rule that assigns to each pair ofelements from S a
unique element from S._ Example: In a*b=c, we say that * is a binary operator if it specifies a rule for
finding c from the pair (a,b)and also if a, b, c Î S.

Axioms and laws of Boolean algebra

Axioms or Postulates of Boolean algebra are a set of logical expressions that we accept without proof and
upon which we can build a set of useful theorems.

AND Operation OR Operation NOT Operation

Axiom1 : 0.0=0 0+0=0 0=1
Axiom2: 0.1=0 0+1=1 1=0
Axiom3: 1.0=0 1+0=1
Axiom4: 1.1=1 1+1=1

AND Law OR Law

Law1: A.0=0 (Null law) Law1: A+0=A
Law2: A.1=A (Identity law) Law2: A+1=1
Law3: A.A=A (Impotence law) Law3: A+A=A (Impotence law)

CLOSURE: The Boolean system is closed with respect to a binary operator if for every pair of
Boolean values,it produces a Boolean result. For example, logical AND is closed in the Boolean
system because it accepts only Boolean operands and produces only Boolean results.
_ A set S is closed with respect to a binary operator if, for every pair of elements of S, the binary
operator specifies a rule for obtaining a unique element of S.
_ For example, the set of natural numbers N = {1, 2, 3, 4, … 9} is closed with respect to the
binary operator plus (+) by the rule of arithmetic addition, since for any a, b Î N we obtain a
unique c Î N by the operation a + b = c.
DIGITAL LOGIC DESIGN Page no. 28
 ASSOCIATIVE LAW:

A binary operator * on a set S is said to be associative whenever (x * y) * z = x * (y * z) for all x, y, z Î S,

forall Boolean values x, y and z.
COMMUTATIVE LAW:

A binary operator * on a set S is said to be commutative whenever x * y = y * x for all x, y, z є S

IDENTITY ELEMENT:
A set S is said to have an identity element with respect to a binary operation * on S if there exists an element
e є S with the property e * x = x * e = x for every x є S

BASIC IDENTITIES OF BOOLEAN ALGEBRA

• Postulate 1(Definition): A Boolean algebra is a closed algebraic system containing a set K of two or more
elements and the two operators · and + which refer to logical AND and logical OR •x + 0 = x
• x ·0=0
• x+1=1
• x·1=1
• x+x=x
• x·x=x
• x + x’ = x
• x · x’ = 0
• x+y=y+x

• xy = yx

• x + ( y + z ) = (x + y) +z

• x (yz) = (xy) z

• x ( y + z ) = xy + xz

• x + yz = ( x + y )( x + z)

• ( x + y )’ = x’ y’

• ( xy )’ = x’ + y’
DIGITAL LOGIC DESIGN Page no. 29
 • (x’)’ = x

DeMorgan's Theorem

(a) (a + b)' = a'b'

(b) (ab)' = a' + b'

Generalized DeMorgan's Theorem

(a) (a + b + … z)' = a'b' … z'
(b) (a.b … z)' = a' + b' + … z‘

Basic Theorems and Properties of Boolean algebra Commutative law

Law1: A+B=B+A Law2: A.B=B.A

Associative law

Law1: A + (B +C) = (A +B) +C Law2: A(B.C) = (A.B)C

Distributive law

Law1: A.(B + C) = AB+ AC Law2: A + BC = (A + B).(A +C)

Absorption law

Law1: A +AB =A Law2: A(A +B) = A

Solution: A(1+B) Solution: A.A+A.B

A A+A.B
A(1+B)
A
Consensus Theorem

Theorem1. AB+ A’C + BC = AB + A’C Theorem2. (A+B). (A’+C).(B+C) =(A+B).( A’+C)

The BC term is called the consensus term and is redundant. The consensus term is formed from a
PAIR OF TERMS in which a variable (A) and its complement (A’) are present; the consensus
term is formed by multiplying the two terms and leaving out the selected variable and its
complement
Consensus Theorem1 Proof:

AB+A’C+BC=AB+A’C+(A+A’)BC
=AB+A’C+ABC+A’BC
DIGITAL LOGIC DESIGN Page no. 30
 =AB(1+C)+A’C(1+B)
= AB+ A’C

Principle of Duality

Each postulate consists of two expressions statement one expression is transformed into the
other by interchanging the operations (+) and (⋅) as well as the identity elements 0 and 1.
Such expressions are known as duals of each other.
If some equivalence is proved, then its dual is also immediately true.
If we prove: (x.x)+(x’+x’)=1, then we have by duality: (x+x)⋅(x’.x’)=0

The Huntington postulates were listed in pairs and designated by part (a) and part (b) in below
table.
Table for Postulates and Theorems of Boolean algebra
Part-A Part-B
A+0=A A.0=0
A+1=1 A.1=A
A+A=A (Impotence law) A.A=A (Impotence law)
̅=1
A+ A ̅=0
A. A
̅=A (double inversion law)
A --
Commutative law: A+B=B+A A.B=B.A
Associative law: A + (B +C) = (A +B) +C A(B.C) = (A.B)C
Distributive law: A.(B + C) = AB+ AC A + BC = (A + B).(A +C)
Absorption law: A +AB =A A(A +B) = A
DeMorgan Theorem:
̅ .B
̅ ̅ +B
(A.B) = = A ̅
(A+B) = A
Redundant Literal Rule: A+ A̅. B=A+B ̅A+B)=AB
A.(A
Consensus Theorem: AB+ A’C + BC = AB + A’C (A+B). (A’+C).(B+C) =(A+B).( A’+C)

Boolean Function
Boolean algebra is an algebra that deals with binary variables and logic operations.
A Boolean function described by an algebraic expression consists of binary variables, the
constants 0 and 1, and the logic operation symbols.
For a given value of the binary variables, the function can be equal to either 1 or 0.
F(vars) = expression

Set of binary Variables Operators (+, •, ‘)

Constants (0, 1)
Groupings (parenthesis)
Variables
Consider an example for the Boolean function
F1 = x + y’z
DIGITAL LOGIC DESIGN Page no. 31
 The function F1 is equal to 1 if x is equal to 1 or if both y’ and z are equal to 1. F1 is equal to 0
otherwise. The complement operation dictates that when y’ = 1, y = 0. Therefore, F1 = 1 if x = 1
or if y = 0 and z = 1.
A Boolean function expresses the logical relationship between binary variables and is evaluated
by determining the binary value of the expression for all possible values of the variables.
A Boolean function can be represented in a truth table. The number of rows in the truth
table is 2n, where n is the number of variables in the function. The binary combinations for the
truth table are obtained from the binary numbers by counting from 0 through 2 n - 1.

Truth Table for F1

x y z F1
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 Gate Implementation of F1 = x + y’z
1 1 0
1 1 1 1

Note:
Q: Let a function F() depend on n variables. How many rows are there in the truth table of F() ?
A: 2n rows, since there are 2n possible binary patterns/combinations for the n variables.

Truth Tables

• Enumerates all possible combinations of variable values and the corresponding function
value
• Truth tables for some arbitrary functions
F1(x,y,z), F2(x,y,z), and F3(x,y,z) are shown to the below.

x y z F1 F2 F3
0 0 0 0 1 1
0 0 1 0 0 1

DIGITAL LOGIC DESIGN Page no. 32

 0 1 0 0 0 1
0 1 1 0 1 1
1 0 0 0 1 0
1 0 1 0 1 0
1 1 0 0 0 0
1 1 1 1 0 1

• Truth table: a unique representation of a Boolean function

• If two functions have identical truth tables, the functions are equivalent (and vice-
versa).
• Truth tables can be used to prove equality theorems.
• However, the size of a truth table grows exponentially with the number of variables
involved, hence unwieldy. This motivates the use of Boolean Algebra.
Boolean expressions-NOT unique
Unlike truth tables, expressions epresenting
x y z F G
a Boolean function are NOT unique.
• Example: 0 0 0 1 1
– F(x,y,z) = x’•y’•z’ + x’•y•z’ +
0 0 1 0 0
x•y•z’
– G(x,y,z) = x’•y’•z’ + y•z’ 0 1 0 1 1
• The corresponding truth tables for
F() and G() are to the right. They are 0 1 1 0 0
identical. 1 0 0 0 0
• Thus, F() = G()
1 0 1 0 0
1 1 0 1 1
1 1 1 0 0

Algebraic Manipulation (Minimization of Boolean function)

• Boolean algebra is a useful tool for simplifying digital circuits.
• Why do it? Simpler can mean cheaper, smaller, faster.
• Example: Simplify F = x’yz + x’yz’ + xz.
F= x’yz + x’yz’ + xz
= x’y(z+z’) + xz
= x’y•1 + xz
DIGITAL LOGIC DESIGN Page no. 33
 = x’y + xz

• Example: Prove
x’y’z’ + x’yz’ + xyz’ = x’z’ + yz’
• Proof:
x’y’z’+ x’yz’+ xyz’
= x’y’z’ + x’yz’ + x’yz’ + xyz’
= x’z’(y’+y) + yz’(x’+x)
= x’z’•1 + yz’•1
= x’z’ + yz’

Complement of a Function
• The complement of a function is derived by interchanging (• and +), and (1 and 0), and
complementing each variable.
• Otherwise, interchange 1s to 0s in the truth table column showing F.
• The complement of a function IS NOT THE SAME as the dual of a function.
Example
• Find G(x,y,z), the complement of F(x,y,z) = xy’z’ + x’yz
Ans: G = F’ = (xy’z’ + x’yz)’
= (xy’z’)’ • (x’yz)’ DeMorgan
= (x’+y+z) • (x+y’+z’) DeMorgan again
Note: The complement of a function can also be derived by finding the function’s dual, and
then complementing all of the literals

Canonical and Standard Forms

We need to consider formal techniques for the simplification of Boolean functions.

Identical functions will have exactly the same canonical form.
• Minterms and Maxterms
• Sum-of-Minterms and Product-of- Maxterms
• Product and Sum terms
• Sum-of-Products (SOP) and Product-of-Sums (POS)

Definitions
Literal: A variable or its complement
Product term: literals connected by •
Sum term: literals connected by +
Minterm: a product term in which all the variables appear exactly once, either complemented or
uncomplemented.
DIGITAL LOGIC DESIGN Page no. 34
Maxterm: a sum term in which all the variables appear exactly once, either complemented or
uncomplemented.
Canonical form: Boolean functions expressed as a sum of Minterms or product of Maxterms are said to be
in canonical form.

Minterm
• Represents exactly one combination in the truth table.
• Denoted by mj, where j is the decimal equivalent of the minterm’s corresponding binary
combination (bj).
• A variable in mj is complemented if its value in bj is 0, otherwise is uncomplemented.

Example: Assume 3 variables (A, B, C), and j=3. Then, bj = 011 and its corresponding minterm is denoted
by mj = A’BC

Maxterm

• Represents exactly one combination in the truth table.

• Denoted by Mj, where j is the decimal equivalent of the maxterm’s corresponding binary
combination (bj).
• A variable in Mj is complemented if its value in bj is 1, otherwise is uncomplemented.

Example: Assume 3 variables (A, B, C), and j=3. Then, bj = 011 and its corresponding maxterm is denoted
by Mj = A+B’+C’
Truth Table notation for Minterms and Maxterms
• Minterms and Maxterms are easy to denote using a truth table.
Example: Assume 3 variables x,y,z (order is fixed)

x y z Minterm Maxterm
0 0 0 x’y’z’ = m0 x+y+z = M0
0 0 1 x’y’z = m1 x+y+z’ = M1
0 1 0 x’yz’ = m2 x+y’+z = M2
0 1 1 x’yz = m3 x+y’+z’= M3
1 0 0 xy’z’ = m4 x’+y+z = M4
1 0 1 xy’z = m5 x’+y+z’ = M5
1 1 0 xyz’ = m6 x’+y’+z = M6
1 1 1 xyz = m7 x’+y’+z’ = M7

Canonical Forms
DIGITAL LOGIC DESIGN Page no. 35
 • Every function F() has two canonical forms:
– Canonical Sum-Of-Products (sum of minterms)
– Canonical Product-Of-Sums (product of maxterms)
Canonical Sum-Of-Products:
The minterms included are those mj such that F( ) = 1 in row j of the truth table for F( ).
Canonical Product-Of-Sums:
The maxterms included are those Mj such that F( ) = 0 in row j of the truth table for F( ).

Example a b c f1
Consider a Truth table for f1(a,b,c) at right 0 0 0 0
The canonical sum-of-products form for f1 is
0 0 1 1
f1(a,b,c) = m1 + m2 + m4 + m6
= a’b’c + a’bc’ + ab’c’ + abc’ 0 1 0 1
The canonical product-of-sums form for f1 is 0 1 1 0
f1(a,b,c) = M0 • M3 • M5 • M7
1 0 0 1
= (a+b+c)•(a+b’+c’)• (a’+b+c’)•(a’+b’+c’).
1 0 1 0
• Observe that: mj = Mj’ 1 1 0 1
1 1 1 0

DIGITAL LOGIC DESIGN Page no. 36

Shorthand: ∑ and ∏
• f1(a,b,c) = ∑ m(1,2,4,6), where ∑ indicates that this is a sum-of-products form, and m(1,2,4,6)
indicates that the minterms to be included are m1, m2, m4, and m6.
• f1(a,b,c) = ∏ M(0,3,5,7), where ∏ indicates that this is a product-of-sums form, and M(0,3,5,7)
indicates that the maxterms to be included are M0, M3, M5, and M7.
• Since mj = Mj’ for any j,
∑ m(1,2,4,6) = ∏ M(0,3,5,7) = f1(a,b,c)
•
Conversion between Canonical Forms
• Replace ∑ with ∏ (or vice versa) and replace those j’s that appeared in the original form with those
that do not.
• Example:
f1(a,b,c)= a’b’c + a’bc’ + ab’c’ + abc’
= m1 + m2 + m4 + m6
= ∑(1,2,4,6)
= ∏(0,3,5,7)
= (a+b+c)•(a+b’+c’)•(a’+b+c’)•(a’+b’+c’)
Standard Forms

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
F1 = y’ + xy + x’yz’
The expression has three product terms, with one, two, and three literals. Their sum is, in effect, an OR
operation.
A 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
F2 = x(y’ + z)(x’ + y + z’)
This expression has three sum terms, with one, two, and three literals. The product is an AND operation.

DIGITAL LOGIC DESIGN Page no. 37

Conversion of SOP from standard to canonical form
Example-1.
Express the Boolean function F = A + B’C as a sum of minterms.
Solution: The function has three variables: A, B, and C. The first term A is missing two variables; therefore,
A = A(B + B’) = AB + AB’
This function is still missing one variable, so
A = AB(C + C’) + AB’ (C + C’)
= ABC + ABC’ + AB’C + AB’C’
The second term B’C is missing one variable; hence,
B’C = B’C(A + A’) = AB’C + A’B’C
Combining all terms, we have
F = A + B’C
= ABC + ABC’ + AB’C + AB’C’+ A’B’C
But AB’C appears twice, and according to theorem (x + x = x), it is possible to remove one of those
occurrences. Rearranging the minterms in ascending order, we finally obtain
F = A’B’C + AB’C + AB’C + ABC’ + ABC
= m1 + m4 + m5 + m6 + m7
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(A, B, C) = ∑m (1, 4, 5, 6, 7)

Example-2.
Express the Boolean function F = xy + x’z as a product of maxterms.
Solution: First, convert the function into OR terms by using the distributive law:
F = xy + x’z = (xy + x’)(xy + z)
= (x + x’)(y + x’)(x + z)(y + z)
= (x’+ y)(x + z)(y + z)
The function has three variables: x, y, and z. Each OR term is missing one variable; therefore,
x’+ y = x’ + y + zz’ = (x’ + y + z)(x’ + y + z’)
x + z = x + z + yy’ = (x + y + z)(x + y’ + z)
y + z = y + z + xx’ = (x + y + z)(x’ + y + z)
Combining all the terms and removing those which appear more than once, we finally obtain
F = (x + y + z)(x + y’ + z)(x’ + y + z)(x’ + y + z)
F= M0M2M4M5
A convenient way to express this function is as
follows: F(x, y, z) = πM(0, 2, 4, 5)
The product symbol, π, denotes the ANDing of maxterms; the numbers are the indices of the maxterms of
the function.

DIGITAL LOGIC DESIGN Page no. 38

 Unit-II

Minimization Techniques

Two-variable k-map:

A two-variable k-map can have 22=4 possible combinations of the input variables A and
B
. Each of these combinations, , B,A ,AB(in the SOP form) is called a minterm.
The minterm may be represented in terms of their decimal designations – m0 for , m1 for
B,m2 for A and m3 for AB, assuming that A represents the MSB. The letter m stands for
minterm and the subscript represents the decimal designation of the minterm. The presence or
absence of a minterm in the expression indicates that the output of the logic circuit assumes logic
1 or logic 0 level for that combination of input variables.

The expression f= ,+ B+A +AB , it can be expressed using min

term as F= m0+m2+m3=∑m(0,2,3)

Using Truth Table:

Minterm Inputs Output

A B F
0 0 0 1
1 0 1 0
2 1 0 1
3 1 1 1
A 1 in the output contains that particular minterm in its sum and a 0 in that column indicates that
the particular mintermdoes not appear in the expression for output . this information can also be
indicated by a two-variable k-map.

Mapping of SOP Expresions:

A two-variable k-map has 22=4 squares .These squares are called cells. Each square on the k-
map represents a unique minterm. The minterm designation of the squares are placed in any
square, indicates that the corresponding minterm does output expressions. And a 0 or no entry in
any square indicates that the corresponding minterm does not appear in the expression for output.

The minterms of a two-variable k-map

DIGITAL LOGIC DESIGN Page no. 39
 The mapping of the expressions =∑m(0,2,3)is

k-map of ∑m(0,2,3)

EX: Map the expressions f= B+A

F= m1+m2=∑m(1,2)The k-map is

Minimizations of SOP expressions:

To minimize Boolean expressions given in the SOP form by using the k-map, look for
adjacent adjacent squares having 1‘s minterms adjacent to each other, and combine them to form
larger squares to eliminate some variables. Two squares are said to be adjacent to each other, if
their minterms differ in only one variable. (i.e, B & A differ only in one variable. so they may
be combined to form a 2-square to eliminate the variable [Link] all other.

The necessary condition for adjacency of minterms is that their decimal designations must
differ by a power of 2. A minterm can be combined with any number of minterms adjacent to it
to form larger squares. Two minterms which are adjacent to each other can be combined to form
a bigger square called a 2-square or a pair. This eliminates one variable – the variable that is not
common to both the minterms. For EX:

m0 and m1 can be combined to yield,

f1 = m0+m1= + B= (B+

)= m0 and m2 can be combined to yield,

f2 = m0+m2= + = ( + )=

m1 and m3 can be combined to yield,

DIGITAL LOGIC DESIGN Page no. 40

 f3= m1+m3= B+AB=B( + )=B

m2 and m3 can be combined to yield,

f4 = m2+m3=A +AB=A(B+ )=A

m0 ,m1 ,m2 and m3 can be combined to yield,

= + +A +AB

= (B+ ) +A(B+ )

= +A

=1

f1= f2= f3=B f4=A f5=1

The possible minterm groupings in a two-variable k-map.

Two 2-squares adjacent to each other can be combined to form a 4-square. A 4-square
eliminates 2 variables. A 4-square is called a quad. To read the squares on the map after
minimization, consider only those variables which remain constant through the square, and
ignore the variables which are varying. Write the non complemented variable if the variable is
remaining constant as a 1, and the complemented variable if the variable is remaining constant as
a 0, and write the variables as a product term. In the above figure f1 read as , because, along the
square , A remains constant as a 0, that is , as , where as B is changing from 0 to 1.

EX: Reduce the minterm f= +A +AB using mapping Expressed in terms of minterms, the
given expression is F=m0+m1+m2+ m3=m∑(0,1,3)& the figure shows the k-map for f and its
reduction . In one 2-square, A is constant as a 0 but B varies from a 0 to a 1, and in the other 2-
square, B is constant as a 1 but A varies from a 0 to a 1. So, the reduced expressions is +B.

It requires two gate inputs for realization as

f= +B (k-map in SOP form, and logic diagram.)

DIGITAL LOGIC DESIGN Page no. 41

 The main criterion in the design of a digital circuit is that its cost should be as low as
possible. For that the expression used to realize that circuit must be [Link] the cost is
proportional to number of gate inputs in the circuit in the circuit, an expression is considered
minimal only if it corresponds to the least possible number of gate inputs. & there is no
guarantee for that k-map in SOP is the real minimal. To obtain real minimal expression, obtain
the minimal expression both in SOP & POS form form by using k-maps and take the minimal of
these two minimals.

The 1‘s on the k-map indicate the presence of minterms in the output expressions, where
as the 0s indicate the absence of minterms .Since the absence of a minterm in the SOP expression
means the presense of the corresponding maxterm in the POS expression of the same .when a
SOP expression is plotted on the k-map, 0s or no entries on the k-map represent the maxterms.
To obtain the minimal expression in the POS form, consider the 0s on the k-map and follow the
procedure used for combining 1s. Also, since the absence of a maxterm in the POS expression
means the presence of the corresponding minterm in the SOP expression of the same , when a
POS expression is plotted on the k-map, 1s or no entries on the k-map represent the minterms.

Mapping of POS expressions:

Each sum term in the standard POS expression is called a maxterm. A function in two
variables (A, B) has four possible maxterms, A+B,A+ , +B, +

. They are represented as M0, M1, M2, and M3respectively. The uppercase letter M stands for
maxterm and its subscript denotes the decimal designation of that maxterm obtained by treating
the non-complemented variable as a 0 and the complemented variable as a 1 and putting them
side by side for reading the decimal equivalent of the binary number so formed.

For mapping a POS expression on to the k-map, 0s are placed in the squares
corresponding to the maxterms which are presented in the expression an d1s are placed in the
squares corresponding to the maxterm which are not present in the expression. The decimal
designation of the squares of the squares for maxterms is the same as that for the minterms. A
two-variable k-map & the associated maxterms are asthe maxterms of a two-variable k-map

The possible maxterm groupings in a two-variable k-map

DIGITAL LOGIC DESIGN Page no. 42

18CS33 Analog & Digital Electronics

Two Variable K-Map

The number of cells in 2 variable K-map is four (22), since the number of variables is two. The following figure
shows 2 variable K-map and location of minterms on a 2 variable K-map.

Example: Convert following truth table into K map.

Y = F(A, B) = Σ m (2, 3)

Three Variable K-Map

The number of cells in 3 variable K-map is eight (23), since the number of variables is 3. The following figure
shows 3 variable K-map and location of minterms on a 3 variable K-map.

OR

Example: Convert following truth table into K map.

Y = F(A, B, C) = Σ m (2,6,7)

Prepared by Anupama V & Dhananjaya B, Dept. of CSE, CEC 9

18CS33 Analog & Digital Electronics

2.3 Four-Variable Karnaugh Maps

The number of cells in 4 variable K-map is sixteen (24), since the number of variables is 4. The following figure
shows 4 variable K-map and location of minterms on a 4 variable K-map.

Example: Convert following truth table into K map.

Y = F(A, B, C, D) = Σ m(1,6,7)

Pairs, Quads, and Octets

Two adjacent 1s in the K-map is called a pair and it eliminate the variable that changes form.
Sample of pair

Prepared by Anupama V & Dhananjaya B, Dept. of CSE, CEC 10

18CS33 Analog & Digital Electronics

A quad is a group of four ls that are horizontally or vertically adjacent and a quad eliminates two variables and
their complements.

Prepared by Anupama V & Dhananjaya B, Dept. of CSE, CEC 11

18CS33 Analog & Digital Electronics

An octet is a group of 8 ls that are horizontally or vertically adjacent and an octet eliminates three variables and
their complements.

Overlapping of groups: We are allowed to use the same 1 more than once.

Rolling of Map: Groups may wrap around the table. The leftmost cell in a row may be grouped with the rightmost
cell and the top cell in a column may be grouped with the bottom cell. Roll and overlap to get largest group.

Prepared by Anupama V & Dhananjaya B, Dept. of CSE, CEC 12

18CS33 Analog & Digital Electronics

Eliminating redundant group: A groups of 1s or 0s whose all members are overlapped by other groups is called
redundant group. After encircling all possible group, eliminate any redundant group if any. We don’t consider
this group while writing the simplified equations from the K-map.

2.4 Determination of Minimum Expressions using Essential Prime Implicants

Any single 1 or any group of 1’s which can be combined together on a map of the function F represents a product
term which is called an implicant of F. Several implicants of F may be possible. A product term implicant is
called a prime implicant if it cannot be combined with another term to eliminate a variable.

The following procedure can then be used to obtain a minimum sum of products from a Karnaugh map:

1) Choose a minterm (a 1) which has not yet been covered.

2) Find all 1’s and X’s adjacent to that minterm. (Check the n adjacent squares on an n-variable map.)
3) If a single term covers the minterm and all of the adjacent 1’s and X’s, then that term is an essential prime
implicant, so select that term. (don’t-care terms are treated like 1’s in steps 2 and 3 but not in step 1.)
4) Repeat steps 1, 2, and 3 until all essential prime implicants have been chosen.
5) Find a minimum set of prime implicants which cover the remaining 1’s on the map. (If there is more than
one such set, choose a set with a minimum number of literals.)

The following figure shows the flowchart for determining a minimum sum of products using a Karnaugh map
with an example.

Prepared by Anupama V & Dhananjaya B, Dept. of CSE, CEC 13

18CS33 Analog & Digital Electronics

Solve S(A,B,C)=Σm(1,3,5) using K map and implement using basic gates.

Solve S= F(A,B,C)=Σ m(0, 1, 3, 5, 6, 7, 11, 12, 14) using Kmap and implement uisng basic, nand only and norly
gates.

Prepared by Anupama V & Dhananjaya B, Dept. of CSE, CEC 14

18CS33 Analog & Digital Electronics

OR

Circuit diagram for

Solve S=F(A,B,C,D)=Σ m(0,1, 2, 4, 5,6, 8,9,10,12,13) using Kmap and implement uisng basic, nand only and norly
gates.

Solve S= F(A,B,C,D)=Σm(7,9,10,11,12,13,14,15) using K map to get minimum SOP expression.

Prepared by Anupama V & Dhananjaya B, Dept. of CSE, CEC 15

18CS33 Analog & Digital Electronics

Solve S=F(A,B,C,D)=Σm(1,2,3,6,8,9,10,12,13,14) using K map to get minimum SOP expression.

Solve S=F(A,B,C,D)=Σm(7)+d(10,11,12,13,14,15) using K map to get minimum SOP expression.

Solve S =F(A,B,C,D)=Σm(2,3,5,7,10,12)+d(11,15) using K map to get minimum SOP expression.

Prepared by Anupama V & Dhananjaya B, Dept. of CSE, CEC 16

18CS33 Analog & Digital Electronics

Solve S=F(A,B,C,D)=Σm(6,7,9,10,13)+d(1,4,5,11) using K map to get minimum SOP expression.

Solve S= F(A,B,C,D)=Σm(0,1,2,4,5,12,14)+d(8,10) using K map to get minimum SOP expression.

Solve S= F(A,B,C,D)=Σm(0,1,4,8,9,10)+d(2,11) using K map to get minimum SOP expression.

Solve S=F(A,B,C,D)=ΠM(0,1,3,4,7) using K map to get minimum POS expression.

Prepared by Anupama V & Dhananjaya B, Dept. of CSE, CEC 17

18CS33 Analog & Digital Electronics

Solve S=F(A,B,C,D)=ΠM(0,6,7,8,12,13,14,15) using K map to get minimum POS expression and implement uisng
basic, nand only and norly gates.

Solve F(A,B,C,D)=ΠM(0,3,4,7,810,12,14).ΠD(2,6) using K map to get minimum POS expression and implement
uisng basic, nand only and norly gates.

Prepared by Anupama V & Dhananjaya B, Dept. of CSE, CEC 18