Lecture 5-Logic Gates and Ciruits

Course Contents
 Introduction to digital electronics

 Number systems and codes
 Digital arithmetic
 Logic gates and circuits
 Logic arithmetic circuits
 Multiplexers and demultiplexers
 Introduction to sequential circuits
Part 4:Logic gates and circuits
After completing this section, you should

be able to:
 Concept of Positive and Negative Logic
 Truth Table
 Logic gates
 Logic Expressions and circuits
 Implementing Combinational Logic circuit
 Boolean Algebra and Reduction Techniques
 Complex combination circuits design
 Logic Families
LOGIC CIRCUIT
This is a circuit designed to perform logical functions
defined in terms of elementary functions of mathematical
logic.
Positive and Negative Logic
Positive Logic system
Is a logic system in which the higher voltage represent one
(1) and the lower voltage represent zero (0).
Negative Logic systems
Is a logic system in which the higher voltage represents zero
(0) and the lower voltage represent one (1).
Summary
Positive Logic HIGH=1 (i. e +5V)
LOW=0 (i.e. 0V)
Negative Logic HIGH=0 (i. e 0V)
LOW=1 (i.e. +5V)
Negative and positive logic are used Digital but
positive Logic is more common.
BASIC LOGICAL OPERATOR

In arithmetic expressions; the arithmetic
operators such as +, -, ×, ÷ are used but in
Logic expressions we have logic operators;
the basic logical operators are NOT/INVERT,
AND and OR.
NOT/INVERT
This is the inversion operator, it is written as a bar
over its argument.
• It is written “NOT”. Thus the inverse of A
is Ā or NOT A
• Analog representation of not operator
INPUT OUTPUT
Switch open(Low) Lamp ON(High)
Switch close(High) Lamp OFF(Low)
AND Operator
This is an operator denoted by x or. The sign
can be omitted similarly to ordinary algebra;
A x B, A.B or AB has similar meaning. A.B
may be read as A and B. A and B is high if
both A and B is high otherwise LOW.
Analog representation of AND operator
S1 S2 INPUT Output
S1 S2
Open(Low) Open(Low) Lamp OFF(Low)
Close(High) Close(High) Lamp OFF(Low)
Close(High) Close(High) Lamp ON(High)

Logic operator OR
It is written as +, A+B is read as A or B; this is high if either A
or B is high or both are high.
INPUT Output
S1
S1 S2
Open(Low) Close(High) Lamp ON(High)
Close(High) Close(Low) Lamp ON(High)
S2
Close(High) Close(High) Lamp ON(High)

LOGIC GATES
These are basic elements that build up a digital. This is a circuit. This
is a circuit that is able to operate on number of binary inputs in
order to perform particular logic function. Types of gates that are
available are NOT, AND, OR, NAND, NOR, Exclusive-OR and
Exclusive-NOR.
By definition
Gate is a digital circuit with one or more inputs but only one
output.
Inverter
This is agate that forms basic function called inversion or
complementation, a bubble (0) appearing is a symbol for an
inversion. NOT gate is denoted by a bar sign (-), NOT gate is
a gate with one input and one output, and the output is high
only when the input is LOW.
Circuit symbol for NOT gate and its Truth table

AND gate
This is a gate that performs logical multiplication
function. Is a logic gate with two or more input and
one output; the output this gate is high when all
the inputs are high. This gate is denoted by a
period (.), x or combination of inputs without all
those two notation.
Circuit symbol and truth table for two inputs AND gate
The OR Gate
This is a gate with two or more input and only one
output; the output of an OR gate is LOW only when
all of its inputs are LOW. This performs Logical
addition function and it is denoted by (+) sign.
Circuit symbol and truth table for the two inputs OR gate
The NAND Gate

This is a gate with two or more inputs and only one
output; the output is LOW when all the inputs are
high. This gate is the same as AND gate followed by
an inverter.
Equivalent circuit for and followed by an inverter (NAND)
Circuit symbol and truth table for a NAND gate

The NOR gate

This is a gate with two or more inputs and
only one output; the output is high only when
all the inputs are LOW.
Equivalent circuit for OR-NOT implementation of NOR gate
Circuit symbol and truth table for NOR gate

EXCLUSIVE-OR Gate
The Ex-OR is an abbreviation for the Exclusive –OR
gate, In this gate the output is high when there is
odd number of one (1) at the input.
Circuit symbol and truth table for Ex-OR gate

EXCLUSIVE-OR Gate
IC available for Ex-OR gate are those having two
inputs and one output but more than two inputs Ex-
OR can be implemented by using the combination of
other Logic gates. Truth table for 3 input Ex-OR gate
EXCLUSIVE-NOR Gate
Ex-NOR is an abbreviation for Exclusive NOR. The
complemented output of Exclusive OR gate is the output of
Exclusive-NOR gate.
Circuit symbol and truth table for Exclusive NOR gate

Universal Gates
NOR and NAND gates have the property that they
individually can be used to hardware-implement a logic
circuit corresponding to any given Boolean expression. That
is, it is possible to use either only NAND gates or only NOR
gates to implement any Boolean expression. This is so
because a combination of NAND gates or a combination of
NOR gates can be used to perform functions of any of the
basic logic gates. It is for this reason that NAND and NOR
gates are universal gates.
Implementation of NOT, OR and AND gate using

NAND gate
NAND implementation of NOT
NAND implementation of AND

NAND implementation of OR gate

Implementation of NOT, OR and AND gate using NOR

gate
NOR implementation of NOT
NOR implementation of OR gate
NOR implementation of AND gate

INHIBIT GATE
There are many situations in digital circuit design where the
passage of a logic signal needs to be either enabled or inhibited
depending upon certain other control inputs. INHIBIT here means
that the gate produces a certain fixed logic level at the output
irrespective of changes in the input logic level. To illustrate this
behavior take NOR gate with one input tied at logic level one, the
output will always be one irrespective of the other inputs. The
inhibit behavior is available in an integrated circuit of AND gate,
which is an AND gate with one input negated by an inverter. The
negated input acts to inhibit the gate.
INHIBIT GATE
Circuit symbol and truth table of a four-input INHIBIT gate
BOOLEAN ALGEBRA AND SIMPLIFICATION

TECHNIQUES
Simplification of logical expression is
important in digital electronics because it led
to the
• Reduction of circuit cost,
• Reduce Physical size of a circuit
• It reduces Gate failures.
There are different simplification

techniques; the following are those
techniques
•Boolean algebra Laws and Rules
• The Karnaugh map method
• The Quine–McCluskey tabular method
Boolean algebra Laws and Rules

Boolean algebra is the mathematics of logic, it is one of the
tools that are used by the designers in simplification of
complex logical expressions, this is interesting and simple
than a normal algebra. This is composed of set of symbols
and rules to manipulate these symbols.
Variables, Literals and Terms in Boolean

Expressions
Variables
Are the different symbols in a Boolean expression. They may
take on the value ‘0’ or ‘1’.
This Boolean expression has three variables, A, B and C
This Boolean expression has four variable P, Q, R, and S

Literal is the occurrence of a variable or its complement
This has 8 literals
This has 7 literals

A term is the expression formed by literals and operations at one
level.
Has five terms including four AND terms and the OR term that
combines the first-level AND terms.
General rules in Boolean algebra

i. We use capital letters for representing variables and function of
variables.
ii. The complement of variable is represented by a bar over the variable.
Example complementing the variable A is represented by Ā
iii. Logical AND function of two variable is represented by either writing
dot between the two variables such as AB. Many times is omitted and
written as AB
iv. Logical OR function of two variables is represented by the sum +
between the two variable such as A+B
The basic rules of logical addition are
0+0=0, 1+0=1, 0+1=1 and 1+ 1= 1
General rules in Boolean algebra

vi. Multiplication in Boolean algebra
follows the same basic rules
governing binary multiplication
0.0=0, 1.0=0, 0.1=0, 1.1=1
Boolean algebra Laws and Rules

Boolean algebra Laws
Boolean algebra uses many of the same laws as
those of ordinary algebra. Where OR is the (X=A+B)
Boolean addition and AND function is the (X=AB)
Boolean multiplication. The following are three
Laws same for Boolean algebra as their ordinary
algebra
The laws of boolean

 Commutative law of addition: A+B=B+A and multiplication: AB=BA, These
laws mean that the order of ORing or ANDing does not matter.
 Associative law of addition: A + (B + C) = (A + B) + C and multiplication A
(BC) = (AB) C. These laws mean that the grouping of several variables
ORed or ANDed together does not matter.
 Distributive law: A (B+C) =AB+BC and (A + B)(C + D)= AC + AD + BC + BD,
These laws show methods for expanding an equation containing ORs and
ANDs.
 These three laws hold true for any number of variables, For example
commutative law can be applied to X= A+ BC + D to form equivalent
equation X= BC + A +D
Rules of Boolean algebra

Rule 1: Anything ANDed with a 0 is equal to 0 (A.0 = 0).
Rule 2: Anything ANDed with a 1 is equal to itself A.1=A), we can see that, with one input tied to a 1, if the A input is
0, the X output is 0; if A is l, X is 1. Therefore, X is equal to whatever the logic level of A is (X = A).
Rule 3: Anything ORed with a 0 is equal to itself (A + 0= A), because one input is always 0, if and if Therefore, X is
equal to whatever the logic level of A is (X = A). A = 0, X = 0. A = 1, X = 1, (A + 0 = A).
Rule 4: Anything ORed with a 1 is equal to 1, because one input to the OR gate is always 1, the output is always 1,
no matter what A is(X = 1). (A + 1 = 1)
Rules of Boolean algebra

Rule 5: Anything ANDed with itself is equal to itself (A.A=A), because both
inputs to the AND gates are A, if and 1 equals 1, and if and 0 equals 0.
Therefore, X is equal to whatever the logic level of A is (X = A).
Rule 6: Anything ORed with itself is equal to itself (A+A)
Rule 7: Anything ANDed with its own complement equals 0. Because the
inputs are complements of each other, one of them is always 0. With a zero at
the input, the output is always 0 (X = 0).
Rule 8: Anything ORed with its own complement equals 1. Because the inputs
are complements of each other, one of them is always 1. With a 1 at the input,
the output is always 1 (X = 1).
Rule 9: A variable that is complemented twice will return to its original logic
level. When a variable is complemented once, it changes to the opposite logic
level. When it is complemented a second time, it changes back to its original
logic level ( = A).
Rule 10: B=A + B and = + B This rule differs from the others because it
involves two variables. It is useful because, when an equation is in this form,
one or more variables in the second term can be eliminated. The validity of
these two equations is proven in Table below. In each case, equivalence is
demonstrated by showing that the truth table derived from the expression
on the left side of the equation matches.
Proof or rule 10
Summary of rules and Laws

Review questions
1. How many gates are required to implement the following Boolean
equations?
a) X = (A + B)C
b) Y = AC + BC
c) Z = (ABC + CD)E
1. Which Boolean law is used to transform each of the following
equations?
a) B + (D + E) = (B + D) + E
b) CAB = BCA
c) (B + C)(A + D) = BA + BD + CA + CD
De Morgan’s Theorem
De Morgan’s theorem is stated as follows:
For three or more variables

Basically in this theorem:
Basically, to use the theorem, you break the bar over the variables
and either change the AND to an OR or change the OR to an AND. To
prove the theorem let apply it to NAND gate and compare to the truth
table for NAND gate.
The proof of De Morgan’s Theorem for NAND gate

Duality Theorem
Duality theorem state that starting with a Boolean relation, you can
derive another Boolean relation by:
Changing OR sign to and sign Changing AND sign to OR sign
Complementing any zero(0) or one(1) as appearing to the expression
A+0=A
A.1= A
For example distributive Law
A (B+C) = AB+AC
A+ (BC) = (A+B). (A+C)
A+BC= (A+B). (A+C)
STANDARDS FORMS OF BOOLEAN EXPRESSIONS

Boolean expression can be expressed in the following
forms
• Sum of Products form(SOP)
• Product of sums form(POS)
Sum of Products form(SOP)

Product term is any group of literals that are ANded together. Example
ABC,XY
A sum term is any group of literals ORed together such as A+B+C, X+Y
Sum of Products(SOP)
Is a group of product terms ORed together. Some of
examples are
1. ABC +AB̅ C̅
2. XY + XYZ̅ + YZ
3. P̅ Q +QR̅ + PQR
Each of these sum of product expressions consist of two or
more product terms(AND) that are ORed together.
Product of Sum form(POS)

A product of sum is any group of sum terms ANDed
together. Some examples are
1. (A + B)(B + C̅ )
2. (A + B̅ + C)(B + C + D̅)
3. (P + Q)(Q + R̅ + S)
STANDARD SOP AND POS

When the SOP or POS form , all the individual terms do not involve all
the literals is known as non-standard SOP or POS
Example in the expression AB + ABC̅ , in this the sum of product term
does not contain literal C. If each term in a SOP and POS form contains
all the Literals then it is in the standard form (canonical form) SOP and
POS respectively.
For example in the expression
ABC̅ + ABC + AB̅ C + A̅ BC all the literals are present in the product term
Therefore:
Boolean expression is in the standard POS or SOP if each term in the
expression (sum term or product term) contains all the literals.
CONVERSION OF POS AND SOP INTO STANDARD

FORM
Sum of products (SOP)
An expression can be converted into its standard forms by ANDing
the terms in the expression with terms formed by ORing the variable
and its complement which are not present in that term.
Product of sum (POS)
This can be converted to standard product of sums by ORing the
terms in the expression with the terms in the expression with terms
formed by ANDing the variable and its complement which are not
present in that term.
Example
Convert the following into standard forms:

1. Y=AC + AB + BC
2. Y= A+ AB +BC
3. X= (A+B)(B+C)(A+C)
Solution
1. Y=AC + AB + BC
=AC (B + B̅ ) + AB(C+ C̅ ) +BC (A+A̅ ) From rule 8
=ABC +AB̅ C + ABC + ABC̅ + ABC + A̅ BC
=ABC + AB̅ C + ABC̅ + A̅ BC
∴ Y= ABC + AB̅ C + ABC̅ + A̅ BC
2. Y= A+ AB +BC
=A (B + B̅ ) (C+ C̅ ) + AB(C+C̅ ) + BC (A+A̅ )
= (AB + AB̅ ) (C+C̅ ) + ABC + ABC̅ + ABC + A̅ BC
= ABC + ABC̅ + AB̅ C + AB̅ C̅ + ABC + ABC̅ + ABC + A̅ BC
= ABC + ABC̅ + AB̅ C + AB̅ C̅ + ABC + ABC̅ + ABC + A̅ BC
=ABC + ABC̅ + AB̅ C + AB̅ C̅ + A̅ BC
3. X= (A+B)(B+C)(A+C)
= ((A+ B) + CC̅ ) + ((B+C) + AA̅ ) + ((A+C) +
BB̅ )
= (A+B+C) (A+B+C̅ ) (A+B+C) (A̅ +B+C)
(A+B+C) (A+B̅ +C)
= (A+B+C) (A+B+C̅) (A̅+B+C) (A+B̅+C)
MAXTERMS AND MINITERMS

Miniterm
This is product(AND) of variables, in which variables assigned logic one
(1) remain as they are while the variables assigned logic zero (0) are
complemented.
It is denoted by mi, where 0 ≤ i < 2n and n=number of terms
1-minterms = Minterms for which the function F = 1
0-minterms = Minterms for which the function F = 0
Any Boolean expression can be expressed as a sum of 1-miniterm
F (list of variables) = Σ (list of 1-minterm indices)
Truth table
F = x̅ y z + x y̅ z + x y z̅ + x y z
= m3 + m5 + m6 + m7
F (x, y, z) = Σ (3, 5, 6, 7)
The inverse of the function can be expressed as a sum (OR) of its 0-minterms.
F̅ (list of variables) = Σ (list of 0-minterm indices)
F̅ = x̅ y̅ z̅ + x̅ y̅ z + x̅ y z̅ + x y̅ z̅
= m0 + m 1 + m 2 + m 4
Or
F̅ (x, y, z) = Σ (0, 1, 2, 4)
MAXTERM
This is a sum(OR) of variables, in which variables assigned logic
one (0) remain as they are while the variables assigned logic zero
(1) are complemented.
Any Boolean function can be expressed as a product (AND) of its 0-
maxterms.
It is denoted by Mi, where 0 ≤ i < 2n and n=number of terms
1-maxterms = maxterms for which the function F = 1.
0-maxterms = maxterms for which the function F = 0.
F (list of variables) = Π (list of 0-maxterm indices)
Truth table
F = (x+y+z) • (x+y+z̅ ) • (x+y̅ +z) • (x̅ +y+z)

= M0 • M1• M2•M4
Or
F (x, y, z) = Π (0, 1, 2, 4)
F(list of variables) = Π (list of 1-maxterm indices)
F̅ = (x+ y̅ +z̅ ) • (x̅ +y+ z̅ ) • (x̅ +y̅ +z) • (x̅ +y̅ +z̅ )
= M3•M5 •M6 •M7
Or
F̅ (x, y, z) = Π (3, 5, 6, 7)
To convert from one canonical form to its other equivalent
form, interchange the symbols Σ and Π, and list the index
numbers that were excluded from the original form.
KARNOUGH MAP(K-MAP)
Is a graphical tool used to simplify logic equation or to convert truth
table to its corresponding logic circuit in a simple orderly process.
Although this K-map can be used to any number of variable but its
practical usefulness is limited to five or six variables.
Or
Is the graphical tool that shows the output level of boolean equation for
each input variable combination.
Karnough Map Format

Karnough map as truth table shows the
relationship between the output and possible
combination of inputs. This is a truth table graph
which aids in visual simplification of the logical
expression. K map is organized as the array of
cells; number of cell can be obtained from the
formula 2n, where n is the number of variables.
Karnough Map Format

In K-map
• Output level is placed in a separate cell
• K-map is used to simply up to six
variables(practically)
Cell-is a square covered by single miniterm in a
SOP K-map or single maxterm in POS K-map
Determination of cells
= 2n
Terms used in a K-map

Implicant- Is any square or rectangular group of cells that
are in the power of 2(1,2,4,8,16).
Prime implicant- Is the implicant that covers as many 1
value(SOP K-map) or 0 values(POS K-map) as possible but
still but retain the identity of implicant.
(# cells= power of 2,rectangular/square)
Distinguished 1-cell: A single miniterm that can only be
covered by one prime implicant.
Essential prime implicant-Is a prime implicant

that covers one or more distinguished 1-cell.
Cell adjacency-Is a state in which two adjacent
cells have single variable change.
Drawing a K-map(Mapping)
K-map can be drawn from the following
1) Drawing a K-map from SOP
2) Drawing K-map from POS
3) Drawing K-map from Truth
table
K-mapping from sum of Products(SOP)

In order to convert SOP to K-map the first procedure
is to convert into the standard form of SOP if it is in
non-standard form.
Examples
Map the following on a K-Map
1) A̅ B̅ C + A̅ BC̅ + ABC̅ + ABC
2) A̅ BC + AB̅ C + AB̅ C̅
3) A̅ B̅ CD + A̅ BC̅ D̅ + ABC̅ D + ABCD + ABC̅ D̅ + A̅ B̅ C̅ D + A̅ BCD̅
4) A̅ BCD̅ + ABCD̅ + ABC̅ D̅ + ABCD
5) A̅ + AB̅ + ABC̅
6) BC + A̅ C̅
7) B̅ C̅ + AB̅ + ABC̅ + AB̅ CD̅ + A̅ B̅ C̅ D + AB̅ CD

1) A̅ B̅ C + A̅ BC̅ + ABC̅ + ABC 2) A̅ BC + AB̅ C + AB̅ C̅
C C
AB 0 1 AB 0 1
00 0 1 00 0 0
01 1 0 01 0 1
11 1 1 11 0 0
10 0 0 10 1 1
3) A̅ B̅ CD + A̅ BC̅ D̅ + ABC̅ D + ABCD + ABC̅ D̅ + A̅ B̅ C̅ D + A̅ BCD̅
CD
AB 00 01 11 10
00 0 1 1 0
01 1 0 0 1
11 1 1 1 0
10 0 0 0 0
4) A̅ BCD̅ + ABCD̅ + ABC̅ D̅ + ABCD
CD
AB 00 01 11 10
00 0 0 0 0
01 0 0 0 1
11 1 0 1 1
10 0 0 0 0
5) A̅ + AB̅ + ABC̅
This is not in the standard form to convert it to
standard from
A̅ (B + B̅ )(C + C̅ ) +AB̅ (C + C̅ ) + ABC̅
C
= A̅ B̅ C̅ + A̅ B̅ C + A̅ BC + A̅ BC̅ +
AB 0 1
AB̅ C + AB̅ C̅ + ABC̅
00 0 1
01 1 0
11 1 1
10 0 0
6) BC + A̅ C̅
This is in non-standard form so to convert it to standard:
BC(A+A̅ ) + A̅ C̅ (B + B̅ )
C
ABC + A̅ BC + A̅ BC̅ + A̅ B̅ C̅
AB 0 1
00 0 1
01 1 0
11 1 1
10 0 0
7)B̅ C̅ + AB̅ + ABC̅ + AB̅ CD̅ + A̅ B̅ C̅ D + AB̅ CD

B̅ C̅ (A + A̅ )(D+ D̅) + AB̅ (C+ C̅ )(D+D̅) + AB̅ CD̅ + A̅ B̅ C̅ D + AB̅ CD
+ ABC̅ (D+D̅)
A̅ B̅ C̅ D̅ + A̅ B̅ C̅ D + AB̅ C̅ D̅ + AB̅ C̅ D+ AB̅ C̅ D̅ + AB̅ C̅ D + AB̅ CD +
AB̅ CD̅ + ABC̅ D̅ + ABC̅ D + AB̅ CD̅ + A̅ B̅ C̅ D + AB̅ CD
= A̅ B̅ C̅ D̅ + A̅ B̅ C̅ D + AB̅ C̅ D+ AB̅ C̅ D̅ + AB̅ CD + AB̅ CD̅
+ ABC̅ D̅ + ABC̅ D
=A̅ B̅ C̅ D̅ + A̅ B̅ C̅ D + AB̅ C̅ D+ AB̅ C̅ D̅ + AB̅ CD + AB̅ CD̅

+ ABC̅ D̅ + ABC̅ D
CD
AB 00 01 11 10
00 1 1 0 0
01 0 0 0 0
11 1 1 0 0
10 1 1 1 1
K-mapping from POS

In order to convert POS to K-map the first
procedure is to convert into the standard form of
POS if it is in non-standard form.
Examples
Map the following
1) (A̅ + B̅ + C + D) (A̅ + B + C̅ + D̅) (A+ B + C̅ + D) (A̅ + B̅ + C̅ + D̅) (A+ B + C̅
+ D̅)
2) (A+ B̅ + C̅ + D) (A+ B + C + D̅) (A+ B + C + D) (A̅ + B + C̅ + D)
3) (A+ B ) (A+ B̅ + C̅ ) (A+ C )
Solution
1) (A̅ + B̅ + C + D) (A̅ + B + C̅ + D̅) (A+ B + C̅ + D)
(A̅ + B̅ + C̅ + D̅) (A+ B + C̅ + D̅)
CD
AB 00 01 11 10
00 1 1 0 0
01 1 1 1 1
11 0 1 0 1
10 1 1 0 1
2) (A+ B̅ + C̅ + D) (A+ B + C + D̅) (A+ B + C + D) (A̅ +

B + C̅ + D)
CD
AB 00 01 11 10
00 0 0 1 1
01 1 1 1 0
11 1 1 1 1
10 1 1 1 0
3) (A+ B ) (A+ B̅ + C̅ ) (A+ C )

This is not in a non-standard form, convert it to standard
(A+ B+CC̅ ) (A+ B̅ + C̅ ) (A+ C + BB̅ )
= (A+ B+C) (A+ B+C̅ ) (A+ B̅ +C̅ ) (A+ B+C) (A+ B̅ +C)
C
AB 0 1
00 0 0
01 0 0
11 1 0
10 1 1
K-mapping from Truth Table

K-map for two variables
K-map for three variables

K-map for four variables

Looping
Is the process in which the square that contains one are
grouped together
Looping group of two (pairs)
X=A̅ B C̅ +ABC̅ X=A̅ BC̅ + A̅ BC
X=A̅ B̅ C̅ + AB̅ C̅ X=A̅ B̅ CD + A̅ B̅ CD̅ + AB̅ C̅ D̅ + AB̅ CD̅
Looping a pair of adjacent one’s in the K-map eliminates the variable

that appears in complimented and uncomplimented form.
Looping group of four(QUADS)

Looping group of four(QUADS)
Looping a quads of adjacent one’s in the K-map

eliminates two variables that appears in complimented
and uncomplimented form.
Looping group of eight(Octets)

Looping group of eight(Octets)
Looping a octets of adjacent one’s in the K-map

eliminates three variables that appears in
complimented and uncomplimented form.
Simplification process by K-map method

To simplify algebraic expressions by using K-map.
1) Transform an expression into a standard form.
2) Fill cells in a K-map with zero's (POS K-
map)/ones(SOP) K-map.
3) Loop adjacent zeros(POS K-map) /ones(SOP K-
map) in the powers of two.
4) Apply K-map principles to complete
simplification process (naming of loops)
Examples
Use K-map to minimize the following:
1) B̅ C̅ D̅ + A̅ BC̅ D̅ + ABC̅ D̅ + A̅ B̅ CD + AB̅ CD + A̅ B̅ CD̅
+ A̅ BCD̅ + A̅ B̅ C̅ D + AB̅ CD̅
2) A̅ BC̅ D̅ + A̅ BC̅ D + ABC̅ D̅ +ABC̅ D + AB̅ C̅ D + A̅ B̅ CD̅
3) AB̅ C + A̅ B̅ C + A̅ B C + AB̅ C̅ + A̅ B̅ C̅
4) F(A,B,C,D)=∑m(0,1,4,8,9,10)
Solution
1) B̅ C̅ D̅ + A̅ BC̅ D̅ + ABC̅ D̅ + A̅ B̅ CD + AB̅ CD + A̅ B̅ CD̅
+ A̅ BCD̅ + A̅ B̅ C̅ D + AB̅ CD̅
In standard form the expression can be written
as
AB̅ C̅ D̅ + A̅ B̅ C̅ D̅ + A̅ BC̅ D̅ + ABC̅ D̅ + A̅ B̅ CD +AB̅ CD
+ A̅ B̅ CD̅ + A̅ BCD̅ + ABCD̅ + AB̅ CD̅
K-map D̅ B̅ C
CD
AB 00 01 11 10
00 1 0 1 1
01 1 0 0 1
11 1 0 0 1
10 1 0 1 1
=D̅ + B̅ C
2) A̅ BC̅ D̅ + A̅ BC̅ D + ABC̅ D̅ +ABC̅ D + AB̅ C̅ D + A̅ B̅ CD̅

In standard form it can be written as
BC̅ CD A̅ B̅ CD̅
AB 00 01 11 10
00 0 1
01 1 1 0 0
11 1 1 0 0
10 0 1 0
=BC̅ + AC̅ D + A̅ B̅ CD̅ AC̅ D

3) AB̅ C + A̅ B̅ C + A̅ B C + AB̅ C̅ + A̅ B̅ C̅
K-map
C B̅
AB 0 1
00 1 1
01 1
A̅C
11
10 1 1
=B̅ + A̅C
4) F(A,B,C,D)=∑m(0,1,4,8,9,10)
CD
AB 00 01 11 10
00 1 1 0 0
01 1 0 0 0
11 0 0 0
10 1 1 0 1

Lecture 5-Logic Gates and Ciruits

Uploaded by

Copyright:

Available Formats

Lecture 5-Logic Gates and Ciruits

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 5-Logic Gates and Ciruits

Uploaded by

Copyright:

Available Formats

Course Contents

 Introduction to digital electronics

After completing this section, you should

BASIC LOGICAL OPERATOR

Analog representation of AND operator

Close(High) Close(High) Lamp ON(High)

Close(High) Close(High) Lamp ON(High)

Circuit symbol for NOT gate and its Truth table

The NAND Gate

Circuit symbol and truth table for a NAND gate

The NOR gate

Equivalent circuit for OR-NOT implementation of NOR gate

Circuit symbol and truth table for NOR gate

Circuit symbol and truth table for Ex-OR gate

Circuit symbol and truth table for Exclusive NOR gate

Implementation of NOT, OR and AND gate using

NAND implementation of NOT

NAND implementation of AND

NAND implementation of OR gate

Implementation of NOT, OR and AND gate using NOR

NOR implementation of NOT

NOR implementation of OR gate

NOR implementation of AND gate

BOOLEAN ALGEBRA AND SIMPLIFICATION

There are different simplification

Boolean algebra Laws and Rules

Variables, Literals and Terms in Boolean

This Boolean expression has three variables, A, B and C

This Boolean expression has four variable P, Q, R, and S

Literal is the occurrence of a variable or its complement

This has 8 literals

This has 7 literals

General rules in Boolean algebra

General rules in Boolean algebra

Boolean algebra Laws and Rules

The laws of boolean

Rules of Boolean algebra

Rules of Boolean algebra

Rule 6: Anything ORed with itself is equal to itself (A+A)

Summary of rules and Laws

For three or more variables

The proof of De Morgan’s Theorem for NAND gate

STANDARDS FORMS OF BOOLEAN EXPRESSIONS

Sum of Products form(SOP)

Product of Sum form(POS)

STANDARD SOP AND POS

CONVERSION OF POS AND SOP INTO STANDARD

Convert the following into standard forms:

MAXTERMS AND MINITERMS

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

Karnough Map Format

Karnough Map Format

Terms used in a K-map

Essential prime implicant-Is a prime implicant

K-mapping from sum of Products(SOP)

7) B̅ C̅ + AB̅ + ABC̅ + AB̅ CD̅ + A̅ B̅ C̅ D + AB̅ CD

1) A̅ B̅ C + A̅ BC̅ + ABC̅ + ABC 2) A̅ BC + AB̅ C + AB̅ C̅

3) A̅ B̅ CD + A̅ BC̅ D̅ + ABC̅ D + ABCD + ABC̅ D̅ + A̅ B̅ C̅ D + A̅ BCD̅