Sample Teaching Material

of ELC2310
(Logic Circuits)
 Binary Logic
• Consists of Binary/Boolean variables and logical
operations, that assume logical meaning

• Variables r represented by letters A, B, C, OR x, y, z

• These Variables are having TWO and only TWO

distinct possible values 0 and 1 (Logic 0 & Logic 1), ;

• (OFF & On), (False & True), (Low & High), (No & Yes)

• 0 and 1 doesn’t represent actual number

 0 and 1 represent state of voltage variables, called

(LOGIC LEVELS)

• Logic 0 may be assigned to any voltage range from

0 to 0.8 V ( For TTL) and 0 to 1.5 V (CMOS)

• Logic 1 may be assigned to any voltage range from

2 to 5 V ( For TTL) and 3.5 to 5 V (CMOS)

• Voltages between these 2 range are indeterminate

• Response is indeterminate between these 2 ranges

 LOGIC LEVELS

5V 5V

2V 3.5 V

0.8 V 1.5 V

For TTL Families For CMOS Logic Families

LOGIC LEVELS
 BASIC LOGICAL OPERATIONS:
AND, OR & NOT OPERATIONS

• AND Operation; x=A.B or x = AB

• OR Operation; x=A+B

• NOT Operation; x = A′
TRUTH TABLE is a table of all possible combinations
of variables, showing relation between the values
that variables may take and the result of operation
 BASIC LOGICAL OPERATIONS:
AND OPERATION WITH AND GATES
• AND Operation; x=A.B or x = AB
3 Input AND Gate
Timing Diagram for AND Operation
REALIZATION OF 2 - INPUT A
AND GATE USING DIODES
Assuming B x
Logic 0 = 0 V
Logic 1 = 5 V
5V
 OR OPERATION WITH OR GATES
• OR Operation; x=A+B
3 INPUT OR GATES
TIMING DIAGRAM FOR 2-INPUT
OR OPERATION
TIMING DIAGRAM FOR 3-INPUT
OR OPERATION
REALIZATION OF 2 INPUT
OR GATE USING DIODES A
Assuming
Logic 0 = 0 V B x
Logic 1 = 5 V
NOT OPERATION WITH NOT GATE
• NOT Operation; x = A′
REALIZATION OF A NOT GATE USING
TRANSISTOR
NAND & NOR GATES (UNIVERSAL GATES)
• NAND & NOR gates are used extensively as
standard logic gates, & r more popular than AND &
OR gates
• NAND & NOR gates actually combine the basic
AND, OR, and NOT operations
• NAND & NOR gates are easily constructed with
transistor circuits and digital circuits can be easily
implemented with them
 NAND Operation x = (AB)′

NAND gate operates like an AND gate followed by an Inverter

2 - INPUT NAND GATE

 2-Input
NAND Gate

Inverter
N-Channel Enhancement type MOSFET
TIMING DIAGRAM FOR NAND
OPERATION
x = (AB)′
UNIVERSALITY OF NAND GATES AND
NOR GATES
2- I/P NOR GATE

NOR Operation x = (A + B)′

NOR gate operates like

an OR gate followed by
an Inverter
TIMING DIAGRAM FOR NOR
OPERATION
x = (A + B)′
UNIVERSALITY OF NOR GATES
 EXCLUSIVE-OR (XOR) & EXCLUSIVE-NOR
(XNOR) CIRCUITS
• Two special logic circuits that occur quite often in
digital systems are XOR and XNOR circuits

• XOR circuit produces a HIGH output whenever the

two inputs are at opposite levels

• XNOR produces a HIGH output whenever the two

inputs are at the same level
 XOR OPERATION; XOR GATES
XOR function; x = A ⊕ B = A′ B + A B′

XOR circuit produces a HIGH output whenever

the two inputs are at opposite levels
TIMING DIAGRAM FOR 2-INPUT
XOR OPERATION
 XNOR OPERATION; XNOR GATES
XNOR Function; x = (A ⊕ B)′ = A B + A′ B′

XNOR gate produces a HIGH output whenever

the two inputs are at the same level
 History of Boolean Algebra (Bl Alg)
In 1854, George Boole developed Boolean algebra.
In 1938, Claude E. Shannon introduced a 2‐valued Bln
Algebra, called switching algebra that represented the
properties of bistable electrical switching circuits.

In 1904, E. V. Huntington formulated the postulates

of Boolean algebra.

These postulates of E. V. Huntington are employed

now for the formal definition of Boolean algebra.
 BOOLEAN ALGEBRA
• is an algebraic structure defined by a set of
elements B, together with two binary operators, +
and ., provided that the following (Huntington)
postulates are satisfied:
 UNIT-1: HUNTINGTON POSTULATES
1. (a) Structure is closed with respect to operator +

(b) Structure is closed with respect to the operator .

2. (a) The Element 0 is an identity element w. r. t. +;

that is, x + 0 = 0 + x = x.

(b) Element 1 is an identity element with respect to . ;

that is, x . 1 = 1 . x = x

3. (a) The structure is commutative with respect to +;

that is, x + y = y + x.
(b) Structure is commutative with respect to .
that is, x . y = y . x
4. (a) The operator . is distributive over +
that is, x . (y + z) = (x . y) + (x . z)
(b) The operator + is distributive over .
that is, x + (y . z) = (x + y) . (x + z)
5. For every element x ϵ B, there exists an element x′ϵ
B (and called complement of x)
such that (a) x + x′ = 1 and (b) x . x′ = 0
6. There exist at least two elements x, y ϵ B

such that x ≠ y

Comparing Boolean algebra with arithmetic and

ordinary algebra we note the following differences

1. Huntington postulates don’t include associative law

However, this law holds for Boolean algebra and can be
derived (for both operators) from other postulates

2. Distributive law of + over . i.e, x + (y . z) = (x + y) . (x + z)

is valid for Boolean algebra, but not for ordinary algebra
3. Boolean algebra does not have additive or
multiplicative inverses; therefore, there are no
subtraction or division operations
4. Postulate 5 defines an operator “complement”,
that is not available in ordinary algebra
5. Ordinary algebra deals with the real numbers,
having an infinite set of elements. Boolean
algebra deals with a set of only 2 elements, 0 &
1 (in a two‐valued Boolean algebra of our use)
IN BOOLEAN ALGEBRA, ONE MUST SHOW THAT
1. elements of the set B,
2. rules of operation for 2 binary operators (+,.) &
3. the set of elements, B = {0, 1}, together with 2
operators, satisfy the 6 Huntington postulates.
Here, we deal only with a two‐valued Boolean
algebra (a Boolean algebra with only 2 elements
0 & 1), having application in gate‐type circuits
commonly used in digital devices & computers.
 TWO‐VALUED BOOLEAN ALGEBRA
A two‐valued Boolean algebra is defined on a set of two
elements, B = {0, 1}, with rules for the two binary
operators + and . as shown in the following operator
tables (the rule for the complement operator is for
verification of postulate 5):
BINARY OPERATOR TABLES
Rules are exactly same as of AND, OR, & NOT opns,
We now show that Huntington postulates are valid for
set B = {0, 1} and the two binary operators + and .
1. Structure is closed with respect to 2 operators is
obvious from tables, since the result of each
operation is either 1 or 0 and 1, 0 ϵ B
2. (a) 0 + 0 = 0 0 + 1 = 1 + 0 = 1; From the tables
(b) 1 . 1 = 1 1 . 0 = 0 . 1 = 0. Establishes two
identity elements, 0 for + and 1 for . (Postulate 2)
3.Commutative laws r proved by binary operatr table
4(a) Distributive law x . (y + z) = (x . y) + (x . z) can be
proved by a truth table of all possible values of x, y, z
4(b) Distributive law of + over . [x + (y . z) = (x + y) . (x
+ z)] can also be proved by a truth table like 4 (a)
5. From complement table (Operator Table)
(a) x + x′ = 1, since 0 + 0′ = 0 + 1 = 1
and 1 + 1′ = 1 + 0 = 1
(b) x . x′ = 0,
since 0 . 0′ = 0 . 1 = 0
and 1 . 1′ = 1 . 0 = 0
Thus, postulate 1 is verified
6. Postulate 6 is satisfied because the two‐valued
Boolean algebra has two elements 1 and 0, with 1 ≠ 0
 BASIC THEOREMS & PROPERTIES
OF BOOLEAN ALGEBRA
DUALITY In Huntington postulates, listed in part (a) &
part (b), one part may be obtained from the other if
the binary operators and the identity elements are
interchanged. This important property of Boolean
algebra is called the duality principle and states that
every algebraic expression deducible from the
postulates of Boolean algebra remains valid if the
operators and identity elements are interchanged.
In a two‐valued Boolean algebra, the identity
elements and the elements of the set B are the same:
1 and 0. If the dual of an algebraic expression is
desired, we simply interchange OR & AND operators
and replace 1’s by 0’s and 0’s by 1’s.

Table lists 6 theorems & 4 postulates of Boolean

algebra. The theorems & postulates, are listed in
pairs; each relation is the dual of the one paired with
it.
6 THEOREMS & 4 POSTULATES OF BLN ALGBRA

Postulates are basic axioms of the algebraic structure

and need no proof. Theorems must be proven from
the postulates.
At right, listed postulate justifies the proof
of a particular step
THEOREM 1(a):
 THEOREM1(b):

Theorem 1(b) is dual of Theorem 1(a) as each

step of proof in part (b) is dual of its counterpart in
part (a). Any dual theorem can be similarly derived
from the proof of its corresponding theorem.
THEOREM 2(a):

THEOREM 2(b): x . 0 = 0 by duality

THEOREM 3: (x′)′ = x
From postulate 5, x + x′ = 1 and x . x′ = 0 which
together define the complement of x. The
complement of x′ is x and is also (x′)′.
THEOREM 6(a):

THEOREM 6(b): x(x + y) = x by duality

Theorems of Boolean algebra can be proved by
means of truth tables
THEOREM 6(a):
 Proof of first DE Morgan's theorem (5a) using
Truth table, (x + y)′ = x′y′

THEOREM 5 (a): First DE Morgan's theorem

 BOOLEAN THEOREMS (RULES)
• help us to simplify logic expressions & logic circuits
• Single-variable theorems with visualization
 Multivariable Theorems
• The theorems of more than one variable

(9) x+y=y+x commutative laws

(10) x.y=y.x commutative laws

(11) x + (y + z) = (x + y) + z = x + y + z Associative Law

(12) x(yz) = (xy)z = xyz Associative Laws

(13a) x(y + z) = xy + xz Distributive Laws

(13b) (w + x)(y + z) = wy + xy + wz + xz Distributive Lw

(14) x + xy = x Theorems (14) & (15) don’t
(15a) x + x′ y = x + y have any counterparts in
(15b) x′ + xy = x′ + y ordinary algebra

(14) & (15) can be proved by trying all possible cases

for x and y (Table). (14) can also be proved using
theorems (6) & (2)
x + xy = x (1+y)
= x . 1 [using theorem (6)]
=1 [using theorem (2)]
Simplify the expression y = AB′D + AB′D′
Solution
Factor out common variables AB′ using theorem (13):
y = AB′(D + D′)
Using theorem (8), the term in parentheses is
equivalent to 1. Thus,
y = AB′ . 1
= AB′ [using theorem (2)]
Simplify z = (A′ + B)(A + B)
Solution
z = A′ . A + A′ . B + B . A + B . B
Invoking Theorem (4), the term A’ . A = 0.
Also B . B = B [Theorem (3)]
z = 0 + A′ . B + B . A + B = A′B + AB + B
z = B(A′ + A + 1)
z=B
Simplify x = ACD + A′BCD.
Solution
Factoring out the common variables CD, we have
x = CD(A + A′B)
Using theorem (15a), replacing A + A′B by A + B, so
x = CD(A + B)
= ACD + BCD
 DEMORGAN’S THEOREMS
Two of the most important theorems of Boolean
algebra, extremely useful in simplifying expressions in
which a product or sum of variables is inverted.

Two Theorems are: (16) (x + y)′ = x′ . Y ′

(17) (x . y)′ = x′ + y′

Theorem (16) says that if the OR sum of two variables

is inverted, this is same as inverting each variable
individually and then ANDing these inverted variables.
Theorem (17) says that when the AND product of
two variables is inverted, this is the same as inverting
each variable individually and then ORing them.

These Theorems have been stated in terms of single

variables x & y, they are equally valid for situations
where x and/or y are expressions that contain more
than one variable e.g., (AB′ + C)′ = (AB′)′ . C′

= (A′ + B) . C′ = A′C′ + BC′

Simplify the expression z = [(A′ + C) . (B + D′)]′ to one
having only single variables inverted.
Solution
Using theorem (17), and treating (A′ + C ) as x and
(B + D′) as y, we have
z = (A′ + C)′ + (B + D ′)′
= (A′′. C′) + (B′ . D′′)
= AC′ + B′D
DeMorgan’s theorems are easily extended to more
than two variables e.g., it can be proved that
• (x + y + z)′ = x′ . y′ . z′
• (x . y . z)′ = x′ + y′ + z′
• Also variables can themselves be expressions rather
than single variables e.g.,
• x = [(AB)′ . (CD)′ . (EF)′]′
• = (AB)′′ + (CD)′′ + (EF)′′
• = AB + CD + EF
Alternative symbol for the NOR function

Alternative symbol for the NAND function

Standard Symbols Alternate Symbols
Standard logic
symbols:
(a) Traditional
(b) IEEE/ANSI
IC’S OF AND OR & NAND GATES
 BOOLEAN FUNCTIONS
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 binary variables, function can be equal to
either 1 or 0, e.g., F1 = x + y′z

Boolean fn expresses the logical relationship between

binary variables & is evaluated by determining binary
value of expression for all possible values of variables
F1 = x + y′z
F2 = x′y′z + x′yz + xy′
= x′z(y′+ y) + xy′
F2 = x′z + xy′

Gate implementation of F1
F1 = x + y′z
GATE IMPLEMENTATION OF F2

F2 = x′y′z + x′yz + xy′

F2 = xy′ + x′z
 ALGEBRAIC MANIPULATION
Simplify the following Boolean functions to a
minimum number of literals.
1. x(x′ + y) = xx′ + xy = 0 + xy = xy
2. x + x′y = (x + x′)(x + y)

= 1(x + y) = x + y
3. (x + y)(x + y′) = x + xy + xy′ + yy′

= x(1 + y + y′)

=x
4. xy + x′z + yz

= xy + x′z + yz (x + x′)
= xy + x′z + xyz + x′yz
= xy(1 + z) + x′z(1 + y)
= xy + x′z
5. (x + y)(x′ + z)(y + z) = (x + y)(x′ + z)
by duality from function 4
2.3 Find the complement of functions F1 = x′yz′ + x′y′z
and F2 = x(y′z′ + yz) (Using DeMorgan’s theorems)
F1′ = (x′yz′ + x′y′z)′ = (x′yz′)′(x′y′z)′
= (x + y′ + z)(x + y + z′)
F2′ = [x(y′z′ + yz)]′ = x′ + (y′z′ + yz)′
= x′ + (y′z′)′(yz)′
= x′ + (y + z)(y′ + z′)
= x′ + yz′ + y′z
 CANONICAL & STANDARD FORMS
Minterms: A binary variable may appear either in
normal form (x) or complement form (x′). For 3
binary variables x, y & z, combined with an AND
operation, there will be 23 = 8 possible combinations,
(x′y′z′, x′y′z, x′yz′, x′yz, xy′z′, xy′z, xyz′, & xyz),
These 8 AND terms are called minterms, or
standard products. Similarly n variables can be
combined to form 2n minterms.
Maxterms: For 3 variables x, y & z, combined with
an OR operation, there will be 8 possible combinations

[(x + y + z), (x + y + z′), (x + y′ + z), (x + y′ + z′),

(x′ + y + z), (x′ + y + z′), (x′ + y′ + z), & (x′ + y′ + z′)

These 8 OR terms are called Maxterms, or Standard

Sums. Similarly n variables (with each variable being
primed or unprimed) can be combined to form 2n
maxterms.
In a Minterm each variable is primed if corresponding bit of
the binary number is a 0 and unprimed if bit is 1
In a Maxterm each variable is primed if corresponding bit
of the binary number is a 1 and unprimed if bit is 0
Each maxterm is complement of its corresponding
minterm and vice versa
A Boolean function can be expressed from a truth
table by forming a minterm for each combination of
the variables that produces a 1 in the function and then
taking the OR of all those terms.
f1 = x′y′z + xy′z′ + xyz = m1 + m4 + m7
An important property of Boolean algebra: Any
Boolean fn can be expressed as a sum of minterms
f1 = x′y′z + xy′z′ + xyz = m1 + m4 + m7
f2 = x′yz + xy′z + xyz′ + xyz = m3 + m5 + m6 + m7
 Complement of a Boolean function f1′
It may be read from the truth table by forming a minterm
for each combination that produces a 0 in the function and
then ORing those terms. f1′ is read as

f1′ = x′y′z′ + x′yz′ + x′yz + xy′z + xyz′

If we take complement of f1′, we obtain function f1:

f1 = (x +y +z)(x + y′ + z)(x+y′+z′) (x′ + y + z′)(x′ + y′ + z′)

f1 = M0 . M2 . M3 . M5 . M6
Similarly, it is possible to read the expression for f2
from the table:
f2 = (x + y + z)(x + y + z′)(x + y′ + z)(x′ + y + z)

f2 = M0M1M2M4 IInd property of Boolean algebra:

Any Boolean function can be expressed as a product

of maxterms (“product” means ANDing of terms)

Boolean functions expressed as a sum of minterms

or product of maxterms are said to be in canonical
form
 Sum of Minterms
For n binary variables, one can obtain 2n distinct
minterms & any Boolean fn can be expressed as a sum
of minterms.

Minterms whose sum defines the Boolean function are

those which give the 1’s of the function in a truth table

As the function can be either 1 or 0 for each minterm,

& since there are 2n minterms, one can calculate all the
functions that can be formed with n variables to be 22n
Express Boolean fn F = A + B′C as a sum of minterms
A = A(B + B′) = AB + AB′ = AB(C + C′) + AB′(C +C′)
A = ABC + ABC′ + AB′C + AB′C′
B′C = B′C(A + A′) = AB′C + A′B′C
F = A + B′C = ABC + ABC′ + AB′C + AB′C′ + A′B′C
F = A′B′C + AB′C′+ AB′C+ ABC′+ ABC (Rearanging)
F = m 1 + m4 + m5 + m6 + m7 (Brief notation)
F(A, B, C) = Σ (1, 4, 5, 6, 7) (Σ is for Oring the terms)
Nos following it are indices of minterms of the fn
Alternative procedure for deriving minterms of a fn
is to obtain truth table of the fn directly from algebraic
expression and then read the minterms from truth table

F = A + B′C
F = m 1 + m4 + m5 + m6 + m7
F(A, B, C) = Σ (1, 4, 5, 6, 7)
(Brief notation)
 Product of Maxterms
Each of the 22n functions of n binary variables can
be also expressed as a product of maxterms.

To express a Boolean fn as a product of maxterms, it

must first be brought into a form of OR terms using
distributive law, x + yz = (x + y)(x + z). Then any
missing variable x in each OR term is ORed with xx′
using distributive law
 Example 2.5 Express the Boolean function
F = xy + x′z as a product of maxterms
F = xy + x′z = (xy + x′)(xy + z)
= (x + x′)(y + x′)(x + z)(y + z)
= (x′ + y)(x + z)(y + z)
The fn 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 This function is also expressed as

F(x, y, z) = Π(0, 2, 4, 5)

Product symbol, Π, denotes the ANDing of maxterms;

numbers are indices of maxterms of the function
Conversion between Canonical Forms
F(A, B, C) = Σ (1, 4, 5, 6, 7) Complement of this fn is
F′ (A, B, C) = Σ (0, 2, 3) = m0 + m2 + m3
Now, if we take the complement of F′ by DeMorgan’s
theorem, we obtain F in a different form:
F = (m0 + m2 + m3)′ = m0′. m2′. m3′ = M0M2M3
F = Π (0, 2, 3) Hence,
mj′ = Mj
Maxterm with subscript j is a complement of minterm
with the same subscript j and vice versa.
 General Conversion Procedure
To convert from one canonical form to another,
interchange the symbols Σ & Π and list those numbers
missing from the original form

Boolean fn can be converted from an algebraic

expression to a product of maxterms by means of a
truth table and canonical conversion procedure. Let

F = xy + x′z Derive the truth table of this function

Minterms of fn are read from truth table as1, 3, 6, & 7

Function expressed as a sum of minterms is
F(x, y, z) = Σ (1, 3, 6, 7) missing terms are 0, 2, 4, & 5
Function expressed as a product of maxterms is
F(x, y, z) = Π (0, 2, 4, 5)
Two canonical forms of Boolean algebra are basic

forms obtained from reading a given function from

truth table. These forms are very seldom the ones with

the least number of literals, because each minterm or

maxterm must contain, by definition, all the variables,

either complemented or uncomplemented.

Standard Forms & Nonstandard 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.

Standard Forms

F1 = y′ + xy + x′yz′ SOP Form

F2 = x(y′ + z)(x′ + y + z′) POS Form

F1 = y′ + xy + x′yz′ F2 = x(y′ + z)(x′ + y + z′)
SOP Form POS Form

IMPLIMENTATION
Nonstandard Forms

Boolean fn may be expressed in a nonstandard form

e.g., the fn

F3 = AB + C(D + E) is neither in SOP nor in POS form

It can be changed to a standard form by using the

distributive law to remove the parentheses:

F3 = AB + C(D + E) = AB + CD + CE
 OTHER LOGIC OPERATIONS
When binary operators AND and OR are placed
between two variables, x and y, they form two
Boolean fns, x.y and x + y. There are 22n functions for
n binary variables. Thus, for 2 variables, n = 2, and
the number of possible Boolean functions is 16
Boolean Expressions for 16 Fns of 2 Variables
 SIMPLIFYING LOGIC CIRCUITS
SUM-OF-PRODUCTS FORM (SOP FORM)
• ABC + A′BC′
• AB + A′BC′+ C′D′ + D
• A′B + CD′ + EF + GK + HL′
• (ABC)′ or (RST)′ is not (SOP) FORM

• PRODUCT-OF-SUMS FORM (POS FORM)

• (A + B′)(C′ + D)F
• (A + C)(B + D′)(B′ + C)(A + D′ + E′)
 SIMPLIFYING LOGIC CIRCUITS

 Obtain expression for a logic circuit x = AB(A′+ BC)′

Reduce it to a simpler form containing fewer terms or

fewer variables in one or more terms e.g. x = ABC′
New expression used to implement a ckt, is equivalnt
to original ckt, containing fewer gates & connection
Simplify logic circuit shown in Figure (a)
z = ABC + AB′ . (A′ C′)′

z = ABC + AB′(A′′ + C′′)

= ABC + AB′ (A + C) [cancel double inversions]

= ABC + AB′A + AB′C [multiply out]

= ABC + AB′ + AB′C [A . A = A]

= AC(B + B′) + AB′

= AC(1) + AB′

z = A (C + B′)
Simplify the expression z = AB′C′ + AB′C + ABC
Simplify z = A′C(A′BD)′ + A′BC′D′ + AB′C
z = A′C(A + B′ + D′) + A′BC′D′ + AB′C (Step 1)

z = A′CA + A′CB′ + A′CD′ + A′BC′D′ + AB′C (2)

z = A′B′C + A′CD′ + A′BC′D′ + AB′C (3)

(This is Desired SOP form)

Factoring out common terms B′C and A′D′

z = B′C(A′ + A) + A′D′ (C + BC′) (4)

z = B′C + A′D′(B + C) (5)

2nd Method: factor out C from step 3
z = C(A′B′ + A′D′ + AB′) + A′BC′D′

z = C(B′[A′ + A] + A′D′) + A′BC′D′ [A′ + A] = 1

z = C(B′ + A′D′) + A′BC′D′

z = B′C + A′CD′ + A′BC′D′

z = B′C + A′D′ (C + BC′)

z = B′C + A′D′(B + C) Same result

z = A′BD′ + B′C Also

 Simplify x = (A′+ B)(A + B + D)D′
x = A′AD′ + A′BD′ + A′DD′ + BAD′ + BBD′ + BDD′ (SOP)

Since A′A = DD′ = 0 and BB = B

x = A′AD′ + A′BD′ + A′DD′ + BAD′ + BBD′ + BDD′

x = A′BD′+ ABD′ + BD′

x = BD′(A′ + A + 1)

x = BD′
 Simplify the circuit of Figure
z = (A′ + B)(A + B′)
z = A′A + A′B′ + BA + BB′
Since A′A = BB′ = 0
z = A′B′ + BA

Simplification process
produced equivalent,
but not simpler, circuit
 Simplify x = AB′C + A′BD + C′D′
Solution
You can try, but you will not be able to simplify this
expression any further
DESIGNING COMBINATIONAL LOGIC CKTS
If desired O/P level of a logic circuit is given for all
possible I/P conditions, results can be displayed
in a truth table. Boolean expression for required
circuit can then be derived from truth table
Same approach can be used for other I/P conditions

Fig. AND gate with appropriate I/Ps can be used

to produce a 1 O/P for a specific set of I/P levels
 Truth table for output x is to be 1 for two
different cases

x = A′B + AB′

Each set of I/P conditions that is to produce a

HIGH O/P is implemented by a separate AND
gate. AND outputs are ORed to produce final O/P
Consider truth table for a 3-input circuit

x = A′BC′ + A′BC + ABC

 Complete Design Procedure
1. Interpret problem and set up a truth table to

describe its operation

2. Write AND term for each case where output is 1

3. Write sum-of-products (SOP) expression for output

4. Simplify the output expression if possible

5. Implement the ckt for final, simplified expression

Design a logic circuit with 3 I/Ps, A, B, & C, & whose
O/P will be HIGH only when a majority of I/Ps r HIGH
1. Set up truth table
2. Write AND terms for each

case where O/P is a 1

3. Write SOP form for O/P

x = A′BC + AB′C + ABC′ + ABC

4. Simplify O/P expression

(Add ABC two times in O/P expression )

 x = A′BC + ABC + AB′C + ABC + ABC′ + ABC

x = BC(A′ + A) + AC(B′ + B) + AB(C′ + C)

x = BC + AC + AB

5. Implement the circuit for this final expression x

Refer to Figure a, where an analog-to-digital converter
is monitoring the dc voltage of a 12-V storage battery
on an orbiting spaceship. The converter’s O/P is a 4-
bit binary number, ABCD, corresponding to the
battery voltage in steps of 1 V, with A as MSB.
Converter’s binary O/Ps are fed to a logic circuit that
is to produce a HIGH output as long as the binary
value is greater than 01102 = 610; that is, the battery
voltage is greater than 6 V. Design this logic circuit.
z = A′BCD + AB′C′D′ + AB′C′D
+ AB′CD′ + AB′CD + ABC′D′
+ ABC′D + ABCD′ + ABCD
= A′BCD + AB′C′(D′ + D)
+ AB′C(D′+ D)
+ ABC′(D′+ D)
+ ABC(D′ + D)
= A′BCD + AB′C′
+ AB′C + ABC′ + ABC
z = A′BCD + AB′(C′+ C) + AB(C′ + C)
= A′BCD + AB′ + AB = A′BCD + A(B′ + B)
= A′BCD + A (Simplify, using Theorem x + x′y = x + y)
Take x = A and y = BCD. Thus,
z = A′BCD + A
z = BCD + A Final expression is implemented in Fig C
KARNAUGH MAP (K map) METHOD
K map is a graphical tool used to simplify a logic eqn

or to convert a truth table to its corresponding logic

circuit in a simple, orderly process.

K map Format

K map, like a truth table, is a means for showing

relationship between logic inputs & desired O/Ps

Truth table gives the value of output X for each
combination of input values. The K map gives the
same information in a different format. Each case in
truth table corresponds to a square in K map.

K map method provides a simple, straightforward

procedure for minimizing Boolean functions

K-map method may be regarded as a pictorial form
of a truth table.
K maps and truth tables for 2 & 3 variables

F (A,B,) = Σ (0,3)

X (A, B, C) = Σ (0, 1, 2, 6)
(c) K maps & truth tables for 4 variables

X (A, B, C, D) = Σ (1, 5, 13, 15)

LOOPING: Looping Groups of 2 (Pairs)
Expression for O/P X can be simplified by properly
combining those squares in K map that contain 1s. The
Process for combining these 1s is called looping
Looping pairs of adjacent 1s

F (A,B,C) = Σ (2,6)

X = BC′(A′ + A) F (A,B,C) = Σ (2,3)

= BC′ (1) = BC′
 F(A,B,C,D) = Σ (2,3,8,10)

X (A,B,C) = Σ (0, 4)

Looping a pair of adjacent 1s in K map eliminates variable

that appears in complemented & uncomplemented form
(a) X = A′BC′ + ABC′ = BC′(A′ + A) = BC′ (1) = BC′ (Prooved)
(c) X = A′B′C′ + AB′C′ = B′C′(A′ + A) = B′C′ (1) = B′C′ (..do..)
 Looping Groups of Four 1s (Quads)
K map may contain a group of four 1s, adjacent to
each other. This group is called a quad

When a quad is looped, the resultant term will contain

only the variables that do not change form for all
squares in the quad

X = A′B′C + A′BC + ABC + AB′C

= A′C(B′ + B) + AC(B + B′)

= A′C + AC = C(A′+ A) = C (QED)

Looping Groups of Four 1s (Quads)
 Looping Groups of Four 1s (Quads)

X = AD′ X = B′D′
Looping a quad of adjacent 1s eliminates 2
variables, appearing in both complemented &
uncomplementd form
LOOPING AN OCTET (GROUP OF 8)
of adjacent 1s eliminates 3 variables that appear in
both complemented & uncomplemented form
LOOPING AN OCTET (GROUP OF 8)
of adjacent 1s eliminates 3 variables that appear in
both complemented & uncomplemented form
 COMPLETE SIMPLIFICATION PROCESS
Looping of pairs, quads, and octets on a K map can

be used to obtain a simplified expression

Rule For Loops of Any Size

When a variable appears in both complemented &
uncomplemented form within a loop, that variable
is eliminated from the expression

Variables that are the same for all squares of the

loop must appear in the final expression
Procedure In Using K-map Method For
Simplifying A Boolean Expression
Step 1 Construct the K map and place 1s in those
squares corresponding to the 1s in the truth
table. Place 0s in the other squares

Step 2 Examine the map for adjacent 1s and loop

those 1s that are not adjacent to any other
1s. These are called isolated 1s.
Step 3 Next, look for those 1s that are adjacent to
only one other 1. Loop any pair containing
such a 1
Step 4 Loop any octet even if it contains some 1s that
have already been looped
Step 5 Loop any quad that contains one or more 1s
that have not already been looped, making
sure to use the minimum number of loops.
 Simplify the function
4.10 (a) F(A,B,C,D) = Σ (2,5,7,11,13,15)
 Simplify the function
4.10 (b) F(A,B,C,D) = Σ (3,4,5,6,7,12,13)
 Simplify the function
4.10(c) F(A,B,C,D) = Σ (1,5,6,7,11,12,13,15)
4.13 F(A,B,C,D) = Σ (1,5,6,7,8,9,10,14)
 Filling a K Map from an O/P Expression
When the desired output is presented as a Boolean
expression instead of a truth table, K map can be
filled by using the following steps.

1. Get expression into SOP form.

2. For each product term in SOP expression, place a 1

in each K-map square whose label contains the same
combination of I/P variables. Place a 0 in all other
squares.
Use a K map to simplify y = C′(A′B′D′ + D) + AB′C + D′

Multiply first term to get y Example 4.14 Tocci

y = A′B′C′D′ + C′D + AB′C + D′
This is now in SOP form
Put 1 in squares of K map,
Containing above terms
Do proper looping
Verify that
Y = AB′ + C′ + D′
 Don’t-Care Conditions
Some logic circuits can be designed so that there are
certain input conditions for which there are no
specified output levels, usually because these input
conditions will never occur. In other words, there will
be certain combinations of input levels where we
“don’t care” whether the output is HIGH or LOW.
This is illustrated in the truth table.
 Don’t-Care Conditions

Here the output z is not specified as either 0 or 1 for

the conditions A, B, C = 1, 0, 0 and A, B, C = 0, 1, 1.
Instead, an x is shown for these conditions. The x
represents the don’t-care condition.
Ex 3.8 Mano: Simplify the Boolean
F (w, x, y, z) = Σ (1, 3, 7, 11, 15)
d (w, x, y, z) = Σ (0, 2, 5) don’t-care conditions

F = yz + w′x′ F = yz + w′z
Example 4.15 Tocci
Design a logic circuit that controls an elevator door in
a three-story building. The circuit in Figure has four
inputs. M is a logic signal that indicates when the
elevator is moving (M = 1) or stopped (M = 0). F1, F2,
and F3 are floor indicator signals that are normally
LOW, and they go HIGH only when the elevator is
positioned at the level of that particular floor. For
example, when the elevator is lined up level with the
second floor, F2 = 1 and F1 = F3 = 0. The circuit
output is the OPEN signal, which is normally LOW
and will go HIGH when the elevator door is to be
opened.
Elevator is stopped (M = 0)
Elevator is moving (M = 1)

Example 4.15

F1, F2, and F3 go HIGH

when elevator reaches a
particular floor
 Example 4.15

OPEN = M′ (F1 + F2 + F3)

 Advantages of K-map over algebraic method

K mapping is a more orderly process with well-

defined steps compared with the trial-and-error
process sometimes used in algebraic simplification. K
mapping usually requires fewer steps, especially for
expressions containing many terms, and it always
produces a minimum expression
Example 4.17
Notation x1x0 represents a 2-bit binary number that can
have any value (00, 01, 10, or 11); e.g., when x1 = 1
and x0 = 0, binary number is 10, and so on. Similarly,
y1y0 represents another two-bit binary number. Design
a logic circuit, using x1, x0, y1, and y0 inputs, whose
output will be HIGH only when two binary numbers
x1x0 and y1y0 are equal.
Solution of Ex 4.17
F = m1 + m2 + m3
= x′y + xy′ + xy
F=x+y
Ex 3.1 Mano: Simplify

F (x, y, z) = Σ (2, 3, 4, 5)

F = x′y + xy′
Ex 3.2 Mano: Simplify F (x, y, z) = Σ (3, 4, 6,7)

yz + xz

F (x, y, z) = Σ (3, 4, 6,7) = yz + xz′

Ex 3.3 Mano: Simplify F (x, y, z) = (0, 2, 4, 5, 6)

F = z′ + xy′
F (x, y, z) = (0, 2, 4, 5, 6) = z′ + xy′
Ex 3.4 Mano: For F = A′C + A′B + AB′C + BC
(a) Express this function as a sum of minterms.

(b)Find the minimal sum-of-products expression

F (A, B,C) = Σ (1, 2, 3, 5,7) = A′C + A′B + AB′C + BC

= C + A′B
Ex 3.5 Mano: Simplify the Boolean function
F (w, x, y, z) = Σ (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)

F = y′ + w′z′ + xz′
Ex 3.6 Mano: Simplify the Boolean function
F = A′B′C′ + B′CD′ + A′BCD′ + AB′C′

F = B′D′ +B′C′ + A′CD′

 Prime Implicants
In choosing adjacent squares in a map, ensure that

1. All minterms of fn r covered in combining squares,

2. Number of terms in expression is minimized, and

3. There is No redundant terms (minterms covered by

other terms)

Combining squares in map becomes more systematic

with two special types of terms

(a)Prime implicant (b) Essential prime implicant

A prime implicant is a product term obtained by
combining the maximum possible number of
adjacent squares in the map.
If a minterm in a square is covered by only one prime
implicant, that prime implicant is said to be essential
prime implicant
The Prime implicants of a function can be obtained
from the map by combining all possible maximum
numbers of squares.
Simplify F = Σ (0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15)
Example of Prime Implicants Mano:

Simplification using prime implicants

There are four possible ways that the function can be
expressed with four product terms of two literals each:
F = BD + B′D′ + CD + AD
= BD + B′D′ + CD + AB′

= BD + B′D′ + B′C + AD
= BD + B′D′ + B′C + AB′
Hence, identification of the prime implicants in the map
helps in determining the alternatives that are available for
obtaining a simplified expression.
 Ex 3.7: Simplify Fn into (a) SOP (b) POS form:
F (A, B, C, D) = Σ (0, 1, 2, 5, 8, 9, 10)
Combining squares with 1’s gives simplified fn in SOP
form:
(a) F = B′D + B′C′ + A′C′D
If squares marked with 0’s are combined, as shown the
simplified complemented fn:
F′ = AB + CD + BD′
By DeMorgan’s theorem (by taking the dual and
complementing each literal, simplified fn in POS form
(b) F = (A′ + B′) (C′ + D′) (B′ + D)
Gate implementations of the function of
Example 3.7 in (a) SOP & (b) POS form
NAND & NOR Implementation
NAND Implementation
Implement the Function with NAND gates:
F (x, y, z) = (1, 2, 3, 4, 5, 7)
NOR Implementation
NOR Implementation