Binary Logic and Gates

Logic and Computer Design

Fundamentals
Chapter 1 – Digital
Computers and Information
 1. Binary Logic and Gates: Definitions
 Binary literals take on one of two values:
e.g.
(1,0) (T,F)
 Logical operators operate on binary
values and binary literals
 Basic logical operators perform the logic
functions AND, OR and NOT
 Logic gates: Circuits that implement logic
functions
 Boolean Algebra: a useful mathematical
system for specifying and transforming
logic functions
 We will study Boolean algebra as a 2
 Binary literals
 A literal is a binary variable or its
complement and therefore takes only one
of two possible values
 Recall from Unit 1 that these two binary
values have different names:
• True/False
• On/Off
• Yes/No
• 1/0
 We useidentifier
literal 1 and 0 here to denote these two
y
• A, B, y, z, or X1 for
values
examples: A
B
Logic
• RESET,
now START_IT, or ADD1 G
Circui
later t
Input Output
literal literal
3
Logical Operations on Binary literals
 The three basic logical operations are:
• AND
• OR
• NOT
 AND is denoted by a dot (·)
 OR is denoted by a plus (+)
 NOT is denoted by an overbar ( ¯ ), a
single quote mark (') after, or ( or #)
before the literal, e.g. A, ‘A, A, or
#A

4
 Notation Examples
 Example If no ambiguity is caused, we may omit the dot:
Y = AB
Product s:• is read “Y is equal to A
,Intersecti Y =A . B AND B”
(Y is True when Both A & B are
on
Sum,
Unio • True)
z = x + y (Yisisread “z is equal to x
True when either A or B are
n OR y”
Negatio •X = isTrue)
read “X is equal to NOT
n
A A” (Y is True when A is Not
True)
Note that both the “.” (dot) and the “+”
operators also have mathematical
functions of multiplication and addition,
respectively
5
Representation on the Venn Diagram

6
 Definitions of the Basic Logic
Operations
Operations are defined on the values "0"
and "1" for each operator:
AND (.) OR (+) NOT (
)
0·0=0 0+0=0
0·1=0 0+1=1 0=1
1·0=0 1+0=1
1·1=1 1+1=1 1=0
Comparison Multiplication Addition and No
with the and AND give OR give corresponding
corresponding identical results different Math operator
Math Operator Results for for NOT
1+1 7
 Truth Tables
 Truth table - A tabular listing of the values of a
logic function for all possible combinations of
the values of its argument literals
 Example: Truth tables for the basic
logic operations:
AND OR NOT
X Y Z = X·Y X Y Z = X+Y X Z
0 0 0 0 0 0 X
0 1 0 0 1 1 0 1
1 0 0 1 0 1 1 0
1 1 1 1 1 1
8
 Practical Implementation of
the Basic Logic Functions

1. Using Switches
Input/Output Definitions
• Input:
 logic 1 is switch closed
 logic 0 is switch open
• Output:
 logic 1 is lamp on
 logic 0 is lamp off.
 Functions depend on the
definitions! (see Positive and
Negative in Unit 3)
 Avoid ambiguities – What does it
9
 Practical Implementation of Logic
 Functions
Implementing Logic Functions Using Switches
A L = 1 : Lamp
B = 1 : Switch ON L = 0 :
C Closed Lamp OFF
D = 0 : Switch
Open

L(A, B, C, D) = A [D + (B C)] = AD +
ABC

 With A = 1, B = 0, C = 0, D = 1: Is the lamp

on or off?
 10
 Logic Gate Symbols and Behavior
Logic gates have special
symbols:
X X
Z=
5 X· 5 1 X 5
Y Y Z = X+ Z=
AND
Y
OR Y NOT gate X
gate gate or
(a) Graphic inverter
symbols

0 1 1
X 0

Timing Y 1 0 1
diagrams 0
(derived from (AND X ·Y 0 0 1
truth tables) ) 0

1 1 1 1
(OR) X + Y
0
(NOT) 1 0 0
X
Chapter 1 14
 Boolean
 Algebra
The algebra that deals with binary literals and logic
functions
 literals: Denote by letters of the alphabet, e.g. A, B, X, Y, Z
 Basic Logic operations on those literals: AND, OR, NOT
 A Boolean Expression (e.g. X+YZ) is Formed by:
- Binary literals
- Logic operations (operators) on the literals and constants
- Parenthesis
- Constants 0,1

A Boolean Function can be described by a Boolean

Equation of the form: Output =
Boolean Expression (not unique)
 Each equation can be represented as a logic diagram (not
unique)
A Boolean Function can be uniquely expressed as a truth
table showing the mapping between each possible
Chapter 1 15
 Boolean Algebra

Truth
Function

Table
Implementatio (unique)
n

Equation Logic
Diagram

Expression

Literals

Several equivalent implementations

- Use the optimum one to implement the Chapter 1 16
 Boolean Function: Represented by
Equations, Logic Diagrams, and a Truth
Table
Truth Table (Unique) Equations
Inputs

XYZ Output F
000 0
001 1
F  X Y One-to-one
Man correspondence
Corresponding
010 0 y
0
Z
Logic Diagrams
between the
equation and the
011 0 X logic diagram

100 1 0
1 0
101 1 Man Y F
y
110 1 1 0
Z
111 1
Unique truth table  Boolean equations, truth tables and
listing function logic diagrams describe the same logic
output for all function!
possible input  Truth tables are unique; but equations
combinations (23 and logic diagrams are not. They can be
= 8) manipulated to produce simpler
Chapter 1 17
 Boolean Algebra Identities
Dual Comment
s
OR AN 2. X 1 opens OR, 1 opens
1. X +0 = X . 1 =X
AN D X AND
4.
3. X + 1 = 1 D OR 0 =0
. 2 blocks OR, 0 blocks
1 0 6. X =X
.X
AND
Single
literal

5. X + X = X 0 1 is
DuplicatingOrder ofhas
inputs
Complementing
not changed 8. X .X = 0 a literal no
7. X + X = 1 effect is irrelevant
11.
9. XX+=YX= Y + X
10. XY = YX Commutative
Two or more

12. X+Y+Z= (X + Y) + Z = X + (Y + Z) 13. XYZ = (XY) Z = X(Y Z) Associative

15. X + YZ = (X + Y)(X + Z) Distributive
14. X(Y + Z) = XY + XZ
literals

DeMorgan’s
16. X + Y = X . Y 17. X .Y = X + Y

Does not hold in Associativity:

ordinary Algebra: An n-input operation is performed
e.g. 5+(3*4)  as a sequence of 2-input
(5+3)*(5+4) operations in any order, e.g. 3- 1
Chapter 18
Some Properties of Identities & the Algebra
 If the meaning is unambiguous, we leave out the
symbol
“·”
 The
1-4identities
Existence above are organized
of 0 and 1 into pairs.
5-6 Idempotence
These
7-8 Existence of 9 Involution
pairs have names as follows:
complement 10-11 12-13 Associative
Commutative Laws Laws
14-15 Distributive Laws 16-17 DeMorgan’s
 The dual of an algebraic expression
Laws is
obtained by interchanging + and · and
interchanging 0’s and 1’s.
 The identities appear in dual pairs. When there is
only one identity on one line the identity is self-
dual, i. e., the dual expression = the original
expression, e.g. No. 9. 16
 Some Properties of Identities & the Algebra
(Continued)
 Unless it happens to be self-dual, the dual of an
expression does not equal the expression itself.
 Example: F = (A + C) · B + 0
dual F = ((A · C) + B) · 1 = A · C + B
 Example: G = X · Y + (W + When taking the dual,
Z) dual G = (X+Y) . Complementing is
not changed
(WX)
 Example:
dual HH == A · B + .A
(A+B) · C + . (B+C)
(A+C)
B·C
 Are any of these functions self-dual?
Check if truth tables for (F) and (dual F) are identical

17
Boolean Operator Precedence

 The order of evaluation in a

Boolean expression is:
1. Parentheses
2. NOT
3. AND
4. OR
 Consequence: Put parentheses
around OR expressions when they
have to be evaluated first

 Example: F = E + A(B + C)(C + D)

18
 Boolean Algebraic Proofs: Example

---- 1

---- 2
Verify equivalence of 1 Compare costs of 1 and 2
and 2 By comparing the to show Benefit of
truth tables simplification
19
Useful Theorems (in Dual
forms)
Expression Dual

 xyxy  x  y  x  y   Minimization
y x   x  y  Absorption
y
 xx  x yyxx
x Simplificatio
x  y  x  z  y  z  x  y  x  z n Consensus
y x  x  y   x 
  
x  y   x  z  y  z   x  y   x  z 
y
 xyxy xy xy DeMorgan's
Laws

20
 Proof of
Minimization

xyxy  x  y  x  y 
 Consider the LHS form
xy +yx y = y (x + x) =
y
y
1

21
 Proof of Absorption
 A + A·B = A (Absorption Theorem)
i.e. B is irrelevant (redundant, absorbed) in this
expression!
Proof Justification (identity or
Steps A theorem)
+ A·B X=X·1
=A·1+ X · Y + X · Z = X ·(Y + Z)(Distributive
A·B Law) 1 + X = 1
=A·(1 X·1=X
+ B)
 A
= Our· 1primary reason for doing proofs is to
=A • Careful and efficient use of the identities and
learn:
Boolean algebra,
theorems of
and
• How to choose the appropriate identity or theorem
to apply to make forward progress, irrespective of 22
 Proof of Simplification

 Consider the LHS form

x + x y = (x + x) (x + y)
= 1. (x +
y)
= (x + y)

23
Proof of Consensus
AB + AC + BC = AB + AC (Consensus Theorem)
X
Proof Steps Justification (identity # or
theorem)
AB + AC + BC
= AB + AC + 1 · BC 2
= AB +AC + (A + A) · BC 7
= AB +AC + ABC + ABC 11, 14

= AB + ABC +AC + ABC 12

= AB (1+C) + AC (1+B) 14
= AB + AC 3, 2
24
Proof of DeMorgan’s
Laws xyx
y

25
 NAND = OR of
inverts
DeMorgan’s
Laws xyx
Verification by Truth
Tables:
y

26
Boolean Function
Evaluation
x y z F1 F2 F3 F4
F1  xyz 0 0 0 0 0
F2  x  0 0 1 0 1
yz 0 1 0 0 0
F3  xyz  x y z  0 1 1 0 0
xy F4  xy x 1 0 0 0 1
z 1 0 1 0 1
1 1 0 1 1
1 1 1 0 1

27
 Expression Simplification
 An application of Boolean algebra
 Simplify to contain the smallest number of
15 literals,
literals (complemented and 6
uncomplemented variables): gates

Simplification
A B  ACD  A BD  AC
= AB + ABCD + A C D + A C D + A B
D D  A BCD
=
= AB
AB +
+ AB(CD)
AC+AB +A
DC (D + +D)AD)
= B(A + A+AC
BD 5
literals,
= B (A + D) + A C 4
Simpler Expressions  Fewer gates, Fewer gate inputs, and(smaller
gates)
simpler circuits….This improves reliability and reducesChapter 1 31
Complementing Functions
 Use DeMorgan's Theorem to complement a
function:
[Link] AND and OR operators
[Link] each constant value and literal

Example: Complement F = xy z  xyz
F = (x + y + z)(x + y + z)
 Example: Complement G = (a + bc)d +
Note: Here we Verify Result
eused DeMorgan’s Using Truth
3 Gtimes
= [ at two Tables
levels!
29
 Complementing Functions,
Contd.
 Use DeMorgan's Theorem to
complement a function:
 Example: Complement G = (a + bc)d + e
G = [(a + bc)d+ e]’ = [(a + bc)d]’. e’
= [(a’ + bc)’+ d’’]. e’
= [a’’. (bc)’ + d]. e’
= [a. (b’+c’) + d]. e’
= ab’e’ + ac’e’ + de’ Verify Result
Using Truth
Tables 30
Towards a more systematic treatment….
3. Canonical Forms- Overview
 What are Canonical Forms?
 Minterms and Maxterms
 Index Representation of Minterms and
Maxterms
 Sum-of-Minterm (SOM)
Representations
 Product-of-Maxterm (POM)
Representations
 Representation of Complements of
Functions 31
 Canonical Forms

 It is useful to specify a Boolean function in

a form that:
•Has a direct correspondence to the truth table
•Allows comparison for equality
 Two main Canonical Forms in common
use:
•Sum of Minterms (SOM)
•Product of Maxterms (POM)

32
Minterms of n Variables
 Minterms are AND (product) terms (each
consisting of n literals) with every literal present in
either true or complemented form.
 Given that each binary literal may appear as
normal (e.g., x) or complemented (e.g., x), there
are 2n minterms for n variables.
 Example: Two variables (X and Y) produce
22 = 4 combinations (i.e. 4 minterms):
XY (both normal, = 1 only for 11)
XY (X complemented,
(X normal, Y complemented, = 1 only for 10)
Y normal, = 1 only for 01)
XY
XY (both complemented, = 1 only for 00)
Chapter 1 33
Maxterms of n Variables
 Maxterms are OR (sum) terms (each having n literals) with
every literal in either true or complemented form.
 Given that each binary variable may appear as normal
(e.g., x) or complemented (e.g., x), there are 2n maxterms
for n variables.
 Example: Two literals (X and Y) produce
22 = 4 combinations (i.e. 4 maxterms):

X Y (both normal, = 0 only for 00)

X Y (X normal, Y complemented, = 0 only for

01) X Y (X complemented, Y normal, = 0 only for 10)

X Y (both complemented, = 0 only for 11)

Chapter 1 34
 Maxterms and Minterms from the Truth
Table
 Example: minterms and Maxterms for Two Variables
Input Combination A product that gives 1 A
sum that gives 0

Index xy minterm Maxterm

0 00 x y Complementx + y
1 01 xy x+y
2 10 xy x+y
3 xy x+
11 m2 y M2
Index represents the AND that gives 1 OR
Input combination in decimal
Reason for min and Max names? Note: mi is0 the complement of Mi and
that gives

vice versa See slide 40 represented as an OR, e.g. for m2:

Chapter 1 38
Minterm and Maxterm Relationship

 Review: DeMorgan's
Theorem
x · y  x  y and x  y  x  y
 Two-literal example:
M2  x  and m2 
Thus
y M2 is thex·ycomplement of m2 and vice-versa.
 Since DeMorgan's Theorem holds for n literals, the
above holds for terms of n literals
 giving:

Mi 

Thus Mi is the complement of mi.
Mi
m i and mi
Chapter 1 39
 Truth Tables for minterms and
Maxterms for two literals x, y
minterms Maxterms

Index
0
1
2
3

 Verify that mi and Mi are complements of one another

 Observe how to derive the logic function for mi and Mi from
index i expressed in binary, e.g. m2 = m10 = xy, M2 = M10 =
x+y
 Reason for the names min and Max:
• a minterm has a minimum of 1’s in its truth table: Only
Chapter 1 40
 Standard order of variables
 Minterms and maxterms are designated with a
subscript
 The subscript is a decimal number that represents
the binary pattern of input literals in the straight
binary (e.g. 8421) code
 The bits in the pattern represent the complemented
or normal state of each literal listed in a standard
fixed order (MSB…LSB)
 Examples
All literals
ofwill be present
Standard in a3minterm
forms: For variables: or maxterm
a, b, c
and will be listed inbthe
+ c)same
= M010 order
= M2, (usually
• Maxterms:
alphabetically)
(a + (a + b + c) = M101 =
M5 Standard Order
• Minterms: a b c = m110 = m6 , a b c = m001 = m1 LSB
•Examples
Terms: of(anon-standard
+ c), b c, andforms
(a + b)for
dominterms/Maxterms:
not contain all literals
• Terms: (b + a + c), a c b, and b c a NOT in standard order
Chapter 1 41
 Standard
Order
Index Example in Three literals: X, Y, LSB
and Z
 The standard order is: X, then Y, then Z
XYZ
 With Index 5 = 101)2
•As a minterm (AND): Complement literals
corresponding to 0  m5 = XYZ
•As a Maxterm (OR): Complement literals
corresponding to 1  M5 = X+Y+Z

•m = m = ?
2 010

•M = M = ?
3 011

•XYZ = m ?
Chapter 1 42
Index Examples – Four literals
Index Binary Minterm Maxterm
i Pattern mi Mi
1 0000 abcd abc Verify
2 0001 d using
3 0011 abcd ? DeMorgan
5 0101 ’s
? abcd
7 0111
10 1010 abcd a  b  c  d
13 1101 ? abcd
15 1111
abc d a  b  c  d
Chapter 1 43
 Observations from the Truth Tables
 In the function tables:
• Each minterm has one and only one 1 present in the 2 n

terms (a minimum of 1s).

All other entries are 0.
• Each maxterm has one and only one 0 present in the 2n terms.
All other entries are 1 (a maximum of 1s).
 We can implement any function by "ORing" the
minterms corresponding to "1" entries in the
function table. These are called the minterms of the
function- Sum of Minterms (SOM)
 We can implement any function by "ANDing" the
maxterms corresponding to "0" entries in the
function table. These are called the maxterms of
the function- Product of Maxterms (POM)
 This gives us two canonical forms for a Boolean
function:
Chapter 1 44
 Minterm Function Example
or
 Truth Table for the Function F1 = m1 + m4 +
m7 = x y z + x y z + x y
F1 o
r
z
And the truth x y z index m 1 + m4 + m7 = F1
table is: 000 0 0 + 0 + 0 =0
Function is 1 at each 0 0 1 1 1 + 0 + 0 =1
of its specified 010 2 0 + 0 + 0 =0
minterms
So, given a truth, 011 3 0 + 0 + 0 =0
How to determine the
function? 100 4 0 + 1 + 0 =1
 As the sum of all 101 5 0 + 0 + 0 =0
minterms for which
the function is 1 ! 110 6 0 + 0 + 0 =0
…. 111 7 0 + 0 + 1 =1
Chapter 1 45
 Minterm Function Example: 5 literals

 F(A, B, C, D, E) = m2 + m9 + m17 + m23

 5 literals
 F(A, B, C, D, E) =
m00010 + m01001 + m10001+ m10111
 F(A, B, C, D, E) in the SOM canonical form =

ABCDE+ABCDE+ABCDE+ABCDE

Chapter 1 46
 Maxterm Function Example
 Example: Implement F1 in maxterms: an
d
F1 = M0 · M2 · M3 · M5 ·
M6
·(x  y  z)·(x  y  z)
F1  (x  y  z) ·(x  yx y zz)·(x  y  z) i
000 0  1 = F11
M0  M2  M3 0 M
 1 M
5 6
 1 =0
Function
And is 0 at
the truth eachis:
table 001 1 1  1 1  1  1 =1
of its specified 010 2 1 0  1 1  1 =0
maxterms 
So, given a truth,
How to determine the
011 3 1 1  0 1  1 =0

function?
 As the product of 100 4 1 1  1 1  1 =1
all maxterms for 
which the function 101 5 1 1  1  Chapter
0  11 = 470
 Maxterm Function Example: 4 literals

 F(A,B, C, D)  M 3  M8  M11 
M14
 F(A, B,C,D) = M0011. M1000. M1011. M1110

= (A+B+C+D). (A+B+C+D). (A+B+C+D). (A+B+C+D)

Chapter 1 48
 Canonical Sum of Minterms
 Any Boolean function can be expressed as a Sum
of Minterms
• From function table, the minterms used are the terms
corresponding to the 1's of the function (see next
example)
• From expression, expand all terms first to explicitly
include all minterms
 Do this by “ANDing” any term missing variable v with
 Example:  v ) (=1) (Easier way with
a term ( vExpress as sum
K-mapsof later)
minterms
f xx y
First expand terms:
Multiply by a 1
Note: Complement
Then distribute terms: in Minterm  Var is
0
Express as sum of minterms: f = m11 + m10 + m00
= m3 + m2 + m0
Chapter 1 49
 Another SOm Example:
Using the Function Truth Table
 Example: Truth Table for
FAB F
 There are three variables, A, B, A B C Index F
C
and C which we take to be the 0 0 0 0 0
standard order 0 0 1 1 1
 Construct the truth table for the 0 1 0 2 0
function
0 1 1 3 0
 Minterms are the standard terms
1 0 0 4 1
where the function is 1
1 0 1 5 1
 For minterms we complement a
1 1 0 6 1
literal when it is 0
= ABC + ABC + ABC + ABC + 1 1 1 7 1
 F ABC
In(A,B,C) = m1 +
the standard m4 + m5 + m6
shorthand Exercise: Do by including
+ m
form:7 missing variables as on
Standard order –previous slidesame
should get
of input literals Su minter Chapter 1 50
 Canonical Product of
 Maxterms
Any Boolean Function can be expressed as a
Product of Maxterms (POM)
• From function table, the maxterms used are the terms
corresponding to the 0's of the function
• From function expression, Expand all terms to explicitly
maxterms
include all by: 1. Applying the second
distributive law
2. “ORing”
then terms
applying themissing literal
distributive lawv with
againa term equal to v
 Example: Convert to product of maxterms:
v (=0) and Variable z is missing
f (x, y, z)  x  x
Apply the distributive law: in expression

xy x y  (x  x)(x  y)  1 (x  y)  x

y
Add a 0 Not a maxterm
Introduce
(x missing
y ) z literal
 z  z(x
byORing
y  with
z) x z. y
z:
Express as POM: f = M010 · M011 Note: Complement in
Maxterm
= M2 . M3  VarChapter
is 1 1 51
 POM Example:
Using the Function Truth Table
 Example: Truth Table for
FAB F
 There are three variables, A, B, A B C Index F
C
and C which we take to be the 0 0 0 0 0
standard order 0 0 1 1 1
 Construct the truth table for the 0 1 0 2 0
function
0 1 1 3 0
 Maxterms are the standard terms
1 0 0 4 1
where the function is 0
1 0 1 5 1
 For Maxterms we complement a
1 1 0 6 1
literal when it is 1
1 1 1 7 1
 F (A,B,C) = M0 . M2 . M3
In the standard shorthand Exercise: Do by including
= (A+B+C) . (A+B+C) .
form: missing variables as on
(A+B+C)
Standard order –previous slidesame
should get
of input literals Produc Maxterm Chapter 1 52
 Implementing the Complement of a
Function
 For a function (F) expressed as a canonical
sum of minterms, the complement of the
function (F) can be constructed as either:
• A sum of the minterms missing in the given
sum-of- minterms canonical form for F
• A Product of the Maxterms having the same
indices
 Then we have: F is 1 for these
 Example: Given F( x, y, z)   indices
(1, 3,5,7
 Fmis 1 for )
the remaining
indices
F(x, y, z)  m(0,2,4,6)  F is 0 for the these indices

F(x, y, z)  M(1,3,5,7)
Standard order Produc
of input literals Maxterm
t
s Chapter 1 53
 Conversion Between the Two Canonical Forms
 To convert between sum-of-minterms and product-of-
maxterms form (or vice-versa) we follow these steps:
•Find the function complement by swapping terms
in the list with terms not in the list
•Change from products to sums, or vice versa
 Example: Given F as before: F(x, y, z) 
 Form the Complement: m(1,3,5,7)
 Then use the other form with the same indices – this
F(x, y, the
forms the complement again, giving m(0,2,4,6)
z) other form of
the original function:
F(x, y, z) 
M(0,2,4,6) Chapter 1 51
Observations on F and F Conversions

F(x, y, z) 
Compleme
nt
m(1,3,5,7)
Sam Compleme
e nt
Function Form Indices
F(x, y, z)  m(0,2,4,6)
Compleme Othe Same
nt r Indice
Function For s
m
F(x, y, z)
Same M(0,2,4,6)
Othe Compleme
Functio r nt
n For Indices
F(x, y, z) 
m
m(1,3,5,7)
Chapter 1 52
 Standard (as opposed to canonical)
Forms
 Standard Sum-of-Products (SOP) form: equations
are written as an OR of AND terms (not minterms)
 Standard Product-of-Sums (POS) form: equations
are written as an AND of OR terms (not maxterms)
 Examples:
• SOP: BCABC
Standard 2-
level Form
• POS: (A 
B B)· (AB  C)· C
 These “mixed” forms are neither SOP nor POS
• (A B  C) (A  C)
• ABC  AC(A  B)
i.e. these are not in the standard 2-level
Chapter 1 53
 Standard Sum-of-Products (SOP)
 A sum of minterms form for n literals can
be written down directly from a truth table
•Implementation of this form is a two-level
network of gates such that:
•The first level consists of n-input AND gates,
and
•The second level is a single OR gate
(with fewer than 2n inputs).
 This form can often be simplified so that
the corresponding circuit is simpler
Chapter 1 57
 Standard Sum-of-Products (SOP):
Example
 Simplifying a sum of minterms:
 F(A, B, C)  m(1,4,5,6,7)
 Writing the minterm expression:
15
F = A B C + A B C + A B C + ABC + ABC literals,
 6 gates
Simplifying: AB +
F=ABC+ AB =
A
F=A+ABC
3
F = (A + A) (A + B C) = A + B C 2
literals,
(smaller)
 Simplified F contains 3 literals comparedgates
to 15 in
the minterm F Standard or
not?
Canonical (SOm, POM) forms can be costly to implement.
Luckily, they can be greatly simplified into standard
Chapter 1(SOP,
58
AND/OR Two-level Implementation of SOP
Expression
 The two implementations for F are shown
below – it is quite apparent which is simpler!
A
B
A
C F
A B
B C Simplifie
C
d
A Standar
F d SOP F
B
C
A Canonic
B al SOm
C F
A
B
C
Chapter 1 56
SOP and POS Observations
 The previous examples show that:
• Canonical Forms (Sum-of-minterms, Product-
of-Maxterms), or other standard forms (SOP,
POS) differ in complexity
• Boolean algebra can be used to manipulate
equations into simpler forms
• Simpler equations lead to simpler two-level
implementations
 Questions to tackle next in this unit:
• How can we obtain the “simplest”
expression?
• Is there only one minimum cost circuit?
Chapter 1 57
 4. 2-Level Logic Circuit Optimization and K-
maps
 Goal: To obtain the simplest
implementation for a given function
 Optimization is a more formal
approach to simplification.
 It is performed using a specific
systematic procedure or algorithm
as opposed to the
ad hoc approach of algebraic
manipulation
 Optimization requires a distinct cost
criterion to measure the simplicity of a
logic circuit
 Two useful cost criteria we will use: Chapter 1 61
 Boolean Function Optimization
 Minimizing the gate input (or literal) cost of
Boolean equations reduces circuit cost
 We will use the gate input G as the cost
criterion
 Boolean Algebra and graphical techniques are
tools to minimize cost criteria values
 Some important questions:
• When do we stop trying to reduce the cost?
• Do we know when we have a minimum cost?
 Will cover optimum or near-optimum cost
functions for two-level (SOP and POS)
circuits
 Will Introduce a graphical optimization Chapter 1 67
 Karnaugh Maps (K-map)
 A K-map is a collection of cells
• Each cell represents a minterm
• The collection of cells is a graphical
representation of a Boolean function
• Adjacent cells differ in the value of one literal only
• Alternative algebraic expressions for the same
function are derived by recognizing patterns of
cells
 The K-map can be viewed as
• A reorganized version of the truth table
• A topologically-warped Venn diagram as
used to visualize sets in the algebra of
sets
Chapter 1 60
Some Uses of K-Maps

For functions with small numbers of literals,

e.g. up to 5 literals:
• Finding optimum or near optimum
implementations
 SOP and POS standard forms
 Two-level AND/OR and OR/AND logic circuits
• Visualizing concepts related to
manipulating Boolean expressions
• Demonstrating concepts used by
computer-aided design programs to simplify
larger circuits
Chapter 1 61
K-Map for two variables (x,y)

• Minterm m0 and y=0 y=1

minterm m1 are m 0= m 1=
-“adjacent”
They differ in the value of the x y x x
xvariable
=0 y my3 =
x = 1 m2 =
• Similarly, minterm m0 xy xy x
and
minterm m2 differ in the x y y
• Also,
variable
m1 and m3 differ in the x
variable
• Finally, m2 and m3 differ in the
variable y
Chapter 1 62
 K-Map and Truth Tables
 The K-Map is just a different form of the truth table.
 Example – Two literal function:
• For a given function F(x,y), output assumes
values a,b,c and d from the set {0,1}
Function Table
Input Function K-Map
Values Value y=0 y=1
(x,y) F(x,y)
x=0
Correspondin

00 a 3
d
g Function
Minterm

01 b x=1
Output

10 c
s

Enter function output at

11 d the box for the
corresponding minterm
Chapter 1 63
K-Map Function Representation
 Example: F(x,y) = x F=x y=0 y=1

x=0 0 0
x=1 1 1
 For function F(x,y), the two adjacent cells
containing 1’s can be combined using the
Minimization Theorem:
x y x
F(x, y)  x y
 i.e. algebraic
 simplification is achieved
graphically by simply combining “adjacent” cells
as this allows omitting literals with different
values Chapter 1 64
K-Map Function Representation
 Example: G(x,y) = x + y
G = x+y y = 0 y = 1
x=0 0
x
1
y
x=1
 For G(x,y), two pairs of adjacent 1 1
cells containing
1’s can be combined using the Minimization
Theorem:

G(x, y)  x y  x y xy  x y  x  y

Duplicate xy

Chapter 1 65
 Three-literal Maps
 A three-literal K-map:
MSB
MSB yz=00 yz=01 yz=11 yz=10
xyz is the 000 001 011 010
Standard x=0 m0 m1 m3 m2
100 101 111 110
order of the x=1 m4 m5 m7 m6
literals
 The distribution of minterms on the K-map satisfies
logical adjacency (note positions of m3 and m7).
 Note that m2 is adjacent to m0 and that m6 is
adjacent to m4: Wrap-around effect
 Each minterm nts yz=00 yz=01 yz=11 yz=10
represe the x=0 x y z xyz xyz xyz
corresponding
product term: x=1 x y z x y z x y z x y z
Chapter 1 66
 Alternative Map Labeling
 Map use mainly involves:
• Entering function output values into
the map
• Reading off product terms from the
map yz y x
y
 Alternative y mapx labeling:
00 01 11 z
useful
103
x 0 1 3 2
0 0 1 2 yz
log2 (2) + 2
x 4 5 7 6
x 14 5 7 6
=3

z z z y z xy
log2 (# of cells) + # of literals in expression = Total # of z
variables
- Which is the most complex expression? Is it a minterm? How many
literals?, cells? Chapter 1 75
 Function Representation on the K-map
 By convention, we represent the minterms of F by a "1" in the
map and leave the minterms of F blank
 Example:
3
y
F(x, y, z)  m(2,3,4,5) 0 1 12 1
4 5
 Example: 1 1
x 7 6

G(a, b, c)  m(3,4,6,7)
z b
 Learn the locations of
3
the 8 indices based on 0 1 1 2
the literal 4 7 6
order shown (e.g. x, most a 1 5 1 1
significant and z, least
significant) on the c
map boundaries

Chapter 1 68
 Combining cells
 By combining cells, we reduce number of literals in
a product term, reducing the literal cost, thereby
reducing the other two cost criteria
 On a 3-literal K-Map:
• One cell represents a minterm with three literals
• Two “adjacent” cells represent a product term
with two literals
• Four “adjacent” terms represent a product term
with one literal
• Eight “adjacent” terms is the function of all
ones (zero literals – output is not a function of
the inputs)

Chapter 1 69
Example: Combining cells
Graphical Vs Boolean
Simplification
 Example: Let F  y
m(2,3,6,7) 0 1
31 21
x 4 5
1
7
1
6

z
 Applying the Minimization Theorem three
times:
F(x, y, z)  x y z  x y z  x y z 
xyz
 yz  yz
 Thus the fouryterms that form a 2 × 2 cell
correspond to the term "y". Chapter 1 70
 Result should
represent a single
Rules for combining product term
cells
 Combine only “pair-wise
 Size of resulting
rectangle/square should
adjacent” cells be a power of 2 < 23: 1,
 Combine cells only up to a 2, 4
Pair-wise
rectangle/square with a size that adjacency
is a power of 2. For 3 variables,
this means:
•2 0 = 1 cell (3 literals)
•2 1 = 2 cells (2 literals)

•2 2 = 4 cells (1 literal)

 Results can contain cells

that are not directly adjacent,
but are related through pair-
wise
adjacency, e.g. cells 1 (001)
and 4
Chapter 1 71
 Three-literal Maps
 Topological warps of 3-literal
K-maps that show all adjacencies:
 Venn Diagram ■ ■ 2-D Map
Cylinder
0
4 X
6
3 7
5

Y2 1
Z
Standard order:
XYZ
MSB
Chapter 1 72
 Three-literal Maps
 Example Shapes of 2-cell Rectangles:
x xyz
y
0 y001 2
00 011 3 x
0 1
111 z
4 5 6
x 7

z
 Two Ways to read off the product terms for the rectangles
shown:
yz
1. Express the joint area on the map
[Link] product includes each variable that has the same
value in all cells of the rectangle. A variable that is equally
Chapter 1 81
Three-literal Maps
 Example Shapes of 4-cell Rectangles:
y z y
0
1 3
2 z
4 5 6
xx
7

 Read off the product terms for the

rectangles shown z
Chapter 1 74
 Three literal Maps
 K-Maps can be used as a systematic method to
simplify
Boolean functions. Cells are combined to form the
largest possible pair wise adjacent
rectangles/squares
 Example: that
F(x, y, z) 
cover all the “1s” of the function in the map.
Simplify mz(1,2,3,5,7) x
y y
0 1 3 2

1 1 1
4 5 7 6

x 1 1
z
F(x, y, z) zx Chapter 1 75
Three-literal Map
Simplification
 Use a K-map to find an optimum SOP
equation for F(X, Y, Z) 
m(0,1,2,4,6,7)
xy
z

xy

F(x, y, z)  z
Chapter 1 76
 Four-literal Maps
 Map and location of minterms:
YZ Y
00 01 11 10
WX 0 1 3 2
00

01 4 5 7 6

12 13 15 X
literal Order
11
W 11 10
10 8 9 14

Standard order: WXYZ Z

MSB Chapter 1 85
 Four literal Terms

 Four literal maps can have

rectangles corresponding to:

• A single cell = 4 literals, (i.e.

Minterm)
• Two cells = 3 literals,
• Four cells = 2 literals
• Eight cells = 1 literal,
• Sixteen cells = zero literals (i.e.
TotalConstant
# of variables (4) = log2 (# of cells) + # of literals in
"1")
expression

Chapter 1 78
 Four-literal Maps
 Example Shapes of Rectangles:
Y WY

Each rectangles 0 1 3 2 X
should represent a
single product term wxyz Z
 Size of rectangle should 4 01015
0111 7 6
be a power of 2 < 24: 1, 2,
4, 8 12 14 X
110113 111115
W
8 9 11 10

Z
X Z
Chapter 1 79
Four-literal Maps
 Example Shapes of Further Rectangles:
Y
0 1 3

4 5 67
2
X
12 13 15 14
W
8 9 11

10
Z
Chapter 1 80
Four-literal Map Simplification:
Example 1
 F(W, X, Y, Z)  m(0, 2,3,4,5,6,7,8,10,13,15)
Y WY
Canonical,
3
X SOm
0 1 2
1 1 1
4 5 6
Z L=?
7
WX 1 1 1 1
14 X
12 13 15
1 1
W 8 9 11 10
1 1
Z Optimized,
X
Z SOP L=?
F(W, X, Y, Z) = ZX + WY + XZ + WX
Chapter 1 81
 Four-literal Map Simplification:
Example 2
 F(W, X, Y, Z) 
Y WYZ
m(3,4,5,7,9,13,14,15)
0 1 3 2
1
4 5 6
7
WXY 1 1 1
X
12 13 14
1 1 WXY
Best way to W 8 9 11 10
handle this 1 1 15
1?
Z
X
Z
F(W, X, Y, Z) = ZX + WYZ + WXY +
Chapter 1 82
 Systematic Simplification (minimization) of a logic function:
Implicants, Prime Implicants, and Essential Prime Implicants
 An Implicant is any single product term of a function
obtained by combining a number of adjacent “1” cells in
the map into a rectangle with the number of cells a power
of 2 (a minterm is the smallest implicant)
 A Prime Implicant is a single product term obtained by
combining the maximum possible number of adjacent
cells in the map into a rectangle with the number of cells
a power of 2
 A prime implicant is called an Essential Prime Implicant if it
is the only prime implicant that covers (includes) one or
more minterms (cells)
 Prime Implicants and Essential Prime Implicants can be
determined by inspection of a K-Map.
 A set of prime implicants "covers all minterms" if, for each
minterm of the function (i.e. 1’s of the function), atChapter
least 1 one91
Examples of the three types of
Implicants
7 2 1: An implicant
C 1 2-4: Prime Implicants
6 5-6: Essential Prime Implicants
1 1 Note: Any single cell
1 (minterm) is an
5 1 implicant
1 B
1 3 implicant 1 a prime
Give a situation
A 1 implicant
that makes
1 1 1
4 1 Does 7 represent a single product
Is it an implicant?
term?
D Why?
Minterm covered by only one prime
implicant So minterm 5 is ………?
Chapter 1 84
 Example:Find all Prime
Implicants
CD Essential
PIs
C C
BD BD
1 1 1 1 1 1

BD 1 1 BD 1 1
B B
1 1 1 1
A A
1 1 1 1 1 1 1 1
AB
D D
AD Minterms covered by single prime implicant
BC
Chapter 1 85
 Another Example
 Find all possible prime implicants for:
G(A, B, C, D) 
m(0,2,3,4,7,12,13,14,15)
Not just
those • Hint: WYZ
WX There
Z
are seven primeY
implicants!
WYZ
needed to 0 2
cover all 1 1
1
3 1
1’s 4 5 7 6
XYZ 1 1
WYX
14 X
1 12
113 1 15 1 XYZ
W 8 9 11 10

WX
Z
Chapter 1 86
 K-Maps for five or more Variables
 For five literal problems, we use two adjacent K-
maps.
It becomes harder to visualize adjacent minterms
for selecting PIs. You can extend the problem to six
literals by using V =X, Y, Z, V)
V = four K-Maps. F (W,
0 Y 1 Y Adjacent
cells. Only
value of V
change
s

X X

W W

Z Z
Chapter 1 87
 Don't Cares in K-Maps
 Sometimes a function table or map contains
entries for which it is known that:
• The input values for the minterm will never
occur, or
• The output value of the function for that
minterm will not be used
 In such cases, the output value of the function
need not be defined as 1 or 0
 Instead, the output value is specified as a “don't
care”
 By placing “don't cares” (labeled as an “x”
entry) in the function table or map, the cost of
the logic circuit may be reduced
Chapter 1 88
 Don't Cares in K-Maps
 Example: A logic function having the binary
codes for the BCD digits as its inputs. Only the
codes for 0 through 9 are used. The six codes,
1010 through 1111 never occur, so the output
values for these codes are “x” to represent “don’t
cares”
How can this help us minimize our circuits?
 Each “x” entry may take on either a 0 or 1
value in resulting solution to an advantage
• For example, an “x” may take on value “0” in
an SOP solution and value “1” in a POS
solution
• An “x” can be taken as 1 to maximize the size
of a PI Chapter 1 89
 Example: BCD “5 or More” (BCD codes
6,7,8,9)
 The map below gives a function F1(w,x,y,z) which
is defined as "5 or more" over BCD inputs.
With the don't cares used for the 6 non-BCD
input
combinations: Function Output:
y 1 for input= 0 to 4
0 0 0 0 2 for input = 5 to 9
0 1 3 2 X (don’t care) for input =
0 1 1 10-15
4
1 x F1 (w,x,y,z) = w + x z + x y G=7
X X5 X X7
12 13 15 614  This is much lower in cost than F2 where
w 1 1 X X
8 9 11 10 the “don't cares” were treated as "0"
z G = 12
F2(w, x,y, z)  w x z  w x y  wx
y
Chapter 1 90
 Product of Sums Example
 Find the optimum POS solution for F, given:

F(A, B, C, D)  m(3,9,11,12,13,14,15)  Don’t

d
• Hint: Use F and complement it to get the care

(1,4,6)result
F map We get the SOP for F by
Y Constructing PIs containing
1 3 2 its 1s (these are the 0s of F)
0 0
0 X 1
Taken
XZ 6 F = XZ +
41 5 7 X
WX X
Taken
0 0 Taken WX
POS of F is obtained by
0 12
0
14 X
1 1 13 1 15 1 Complementing F using
W 8 9 10
DeMorgan’s
0 1 1
11 0 F=F=( )
= (XZ) . (WX)
Z Chapter 1 91
 Algorithm for Systematic Optimization
1. Find all possible prime implicants (PIs)
2. From these PIs, select:
 All essential PIs and mark all 1’s
covered by them
 A minimum cost set of non-
essential PIs that cover all minterms
not yet covered by the essential PIs
above
• To obtain a good simplified
solution: (not necessarily
optimum), use the Selection
Chapter 1 92
Prime Implicant Selection Rule

 Minimize the overlap among

prime implicants as much as
possible. In particular, in the final
solution, make sure that each
prime implicant selected includes
at least one minterm not included
in any other prime implicant
selected.

Chapter 1 93
 Example
 Simplify F(A, B, C, D) given on the K-map
Selecte
 Essential PIs d
Essential
C
additional
minimum PIs PIs C
overlap
with
1 1 1 1

1 1 1 1 1 1 1 1
B B
1 1
A A
1 1 1
1
Possible D D
additional PIs to Minterms covered by essential prime
cover implicants Notice No overlap amongst additional
all remaining 1’s 102
 Selection Rule Example with Don't Cares

 Simplify F(A, B, C, D) given on the K-map.

Selected Essential
C additionals C
with minimum
overlap
1 x 1 x

1 x x 1 1 x x 1
B B
x x
A A
1 1 x 1 1 x
This don’t
care
Is taken as
Possible D D
0
additional PIs Minterms covered by essential prime implicants

Chapter 1 103
 Multiple-Level Circuits
 Multiple-level circuits are circuits that
are not in the standard two-level (SOP
and POS) format (with or without input
and/or output inverters)
 Multiple-level circuits can have
reduced gate input cost compared to
two-level circuits
 Multiple-level optimization is performed
by applying transformations to circuits
represented by equations while
evaluating cost Chapter 1 104
 Cost Reduction through multi-level
circuits
G = ABC + ABD + E + ACF +
ADF

a. Direct SOP standard (2-level) b. G = AB(C+D) + E + AF(C+D), 3-

Implementation, Gate input cost, G Level G = 13
= 17

d. G = (C+D)(AB+AF)
c. Avoiding the duplication for +E, = A(C+D)(B+F) + E, 3-Level G = 9
(C+D), 3-Level G = 11 (nearly 50% reduction in complexity
Chapter 1and cost
105
Other Gate Types
 Why?
• Feasibility and cost of implementing the gate
circuit
• Potential for implementing complex Boolean
functions, e.g. using a single gate type to
implement any logic function is
advantageous
• Convenient conceptual representation
 Gate classifications
• Primitive gate - a gate that can be described
using a single primitive operation type (AND
or OR) plus optional inversion(s).
• Complex gate - a gate that requires more
Chapter 1 106
Primitive gates

Chapter 1 99
 Buffer
 A buffer is a gate with the function F = X:

X F
 In terms of Boolean function, a buffer is the
same as a direct connection!
 So why use it?
• A buffer is an electronic amplifier used
to improve circuit voltage levels,
increase current drive capability, and
adjust circuit delay

Chapter 1 100
 NAND Gate [NOT (AND)]
 The basic NAND gate has the following
symbol, illustrated for three inputs:
• AND-Invert (NAND)
X
Y
F(X, Y, Z)  X  Y
Z
Z
 NAND represents AND NOT, i. e., the AND
function followed by an inverter (NOT).
The symbol shown is an [Link]
small circle (“bubble”) represents the invert
function.
Chapter 1 101
 NAND Gates (continued)
 Applying DeMorgan's Law gives Invert-OR
(NAND)
Y
X F(X, Y, Z)  X  Y 
Z
Z
 This NAND symbol is called Invert-OR, since inputs are
inverted and then ORed together
 Note the above symbol is still for a NAND
 So a NAND gate can be represented in two different but
equivalent forms:  AND-then-Invert form
 Invert-then-OR form

Chapter 1 102
 Observations on the NAND Gate:
The NAND is not Associative
 NAND usually does not have an operation symbol defined
like the “.” for the AND and the “+” for the OR
 This is because NAND is not associative and we have
difficulty dealing with non-associative mathematics!:
≠

 i.e. the n-input NAND function can not be derived from a

sequence of 2-input NAND operations
 Instead, it is derived directly from the n-input AND function
(which is associative) followed by inversion Chapter 1 111
 Observations on the NAND Gate:
Universality
 Universal gate – is a
gate type that can
implement any or
Boolean function 1
through
implementing the 3
basic logic
operations: (AND,
OR, and NOT)
(advantage)
 The NAND gate is a
universal gate as
shown opposite
 The NAND gate is the
natural
implementation for
the simplest and
fastest electronic
Chapter 1 104
 NOR Gate [NOT (OR)]
 The basic NOR gate has the following
symbol, illustrated for three inputs:
• OR-Invert (NOR)
X
Y
F(X, Y, Z)  X+Y
Z
Z
 NOR represents OR NOT, i. e., the OR function
followed by a NOT. The symbol shown is an
OR- Invert. The small circle
(“bubble”) represents the invert function.

Chapter 1 105
 NOR Gate (continued)
 Applying DeMorgan's Law gives Invert-AND
(NOR) X
Y F(X, Y, Z)  X  Y 
Z
 This NOR symbol is calledZInvert-AND, since inputs
are inverted and then ANDed together.
 Note the above symbol is still for a NOR
 So a NOR gate can be represented in two different but
equivalent forms: OR-then-Invert form and Invert-then-
AND form

OR-Invert Invert-AND
Chapter 1 11 4
 Observations on the NOR Gate:
The NOR gate is not Associative
 NOR usually does not have an operation symbol defined
like the “.” for the AND and the “+” for the OR
 This is because NOR is not associative and we have difficulty
dealing with non-associative mathematics!:
≠

 i.e. the n-input NOR function can not be derived from a

sequence of 2-input NOR operations
 Instead, it is derived directly from the n-input OR
function (associative) through inversion Chapter 1 115
 Observations on the NOR Gate:
Universality
 Universal gate – is a
gate type that can or
implement any 0
Boolean function
through implementing
the 3 basic logic
operations: (AND,
OR, and NOT)
(advantage)
 The NOR gate is a
universal gate as
shown opposite
 The NOR gate is
another natural
implementation for
the simplest and
fastest electronic
circuits Chapter 1 116
 Exclusive OR/ Exclusive NOR
 The eXclusive OR (XOR) function is an important Boolean
function used extensively in logic circuits
 XOR is associative and is represented as the XOR operator
()
 The eXclusive NOR (XNOR) function is the complement of
the XOR function.
 XNOR is not associative
 By our definition, XOR and XNOR gates are complex
gates
 The XOR/XNOR functions may be implemented:
• Directly as an electronic circuit (a true gate) or
• Indirectly by interconnecting other gate types (used as
a convenient representation)
Chapter 1 118
 Definitions of XOR/XNOR as Truth Tables

 XOR XNOR
X Y XY X Y (XY)
or XY
0 0 0 1 for
0 1 for
different
10 1 1 0 0 1 equal
input
inputs
1 21 s
0 1 1 0 1 0
1 31 1 0 1 1 0 0
 The XOR function means: 1 1 1
X OR Y, but NOT BOTH
 XNOR is called the equivalence function, operator ()-
 Why?
From the K-maps:
Proof
 Algebraical
X YXYX X Y XYX ly
 From eqns above, note that  Chapter 1 119
Exclusive OR/ Exclusive NOR
 Uses for the XOR and XNORs gate include:
• Parity generators/checkers
• Adders /subtractors /multipliers
• Counters/incrementers/decrementers
 Functions (see previous slide)
• The XOR function is: X  Y  X Y  X
• The eXclusive NOR (XNOR) function, otherwise
known as equivalence is:Y
 Strictly speaking, XOR andXXNOR
YXYX
gates are
Y For more than two
defined only for two inputs.
inputs, we use the terminology odd and even
functions (considered later) instead
Chapter 1 111
 Symbols For XOR and XNOR
 XOR symbol:

 XNOR symbol:

 The above symbols are valid only for two

inputs

Chapter 1 112
XOR Implementations
 The simple SOP implementation uses the following structure:
X AND
XY
OR
XY  XYXY X Y

XY
AND
Y
Invert-then-
 A NAND only implementation: AND
= NOR
X OR
Output of top AND : AND

 X .( XY )
 X(X  X Y
Y)
 XX  XY Y
AND


 0  XY Chapter 1 122
XOR Identities
Derive from the truth table
; similar to OR

; similar to NAND

; Inputs are always identical

; Inputs are always different

Commutativity:

Associativity: Sequence of 2-input operations:

Yes!

(it is not called Chapter 1 114