Lecture 2 – 1

EE272 Digital Systems Fall 2019

Instructor: Dr. Aashir Waleed

Chapter 2
Boolean Algebra & Logic Gates
 Lecture 2 – 2

Lecture Overview
 Boolean Algebra
 Boolean Functions
 Logic Gates
 Implementing Boolean Functions using Logic Gates
 Canonical and Standard Forms
 Inside logic gates
 TTL and CMOS logic
 Electrical characteristics: Signal levels, Noise margins,
Fan- out, Speed
 Reading assignment: Chapter 2.1 to 2.8
 Lecture 2 – 3

Logic function
 Digital system works on binary number which has only
two elements, ‘0’, and ‘ 1 ’
 Need circuits to manipulate 1’s and 0’s, they are called
logic function
A
F Y
B

C
 A,B, C,Y – logic variables (binary
signals)
 A, B,C – inputs
 Y – output
 Logic function:Y = F(A,B,C)
 Lecture 2 – 4

Truth Table
 Tabulate all possible input combinations of the variables
 Showing the relation between the values that the
variables may take and the result of the
operation A B C Y
 E.g. 0 0 0 1
0 0 1 1
0 1 0 0 How can we design a
0 1 1 1 circuit that implement a
1 0 0 0
certain function specified
1 0 1 1
1 1 0 1
by a truth table?
1 1 1 0
 Lecture 2 – 5

Boolean Algebra
 In 1854, a mathematician, George Boole, in a book
called “An Investigation of the Laws of Thought, on
Which are Founded the Mathematical Theories of
Logic an Probabilities” developed an algebraic system
to handle only two variables,TRUE and FALSE
 Lecture 2 – 6

Structure of Boolean
Algebra
 a set of elements B
 Two binary {AND, OR}  { ,
operations +}
One unary
Axioms
  operation Postulates)
(Huntington {NOT}  { ' }

 1. Set B contains at least two elements, a, b, such that a

 b
 consider a two valued Boolean algebra, i.e. B = {0,1}
 2. Closure (with respect to the Binary operator +, •):
 (i) a + b is in B (ii) a • b is in
B
 3. Commutative Laws:
 (i) a + a0+= ba= b + a (ii) a •(ii)
1 =a • b = b •
a 5. Distributive
 a
 4. Identity
Laws: elements with respect to the(ii)
Binary operator:
a • (b + c) = 0,
a 1• b + a
in B (i) a + (b • •c
c) = (a + b) • (a + (ii) a • a' =
c) 0
 6. Complement:
 Lecture 2 – 7

Laws of Boolean Algebra

 Duality:
 A dual of a Boolean expression is derived by interchanging OR and
A N D operations, and 0s and 1s (literals are left unchanged)
 Any law that is true for an expression is also true for its dual.
 Theorems of Boolean Algebra derived from postulates
 Operations with 0 and 1:
 x+ 1= 1 x0=
 Idempotent: 0
 x+ x= x x x=
 Involution: x
 (x’)’ = x
 De Morgan:
 (x + y)’ = x’ y’ (x y)’ = x’ +
 Absorption: y’
 x + xy = x x (x + y) =
 Associative: x
 (x + y) + z = x + (y + (x y) z = x (y
z) z)
 Lecture 2 – 8
Proving Theorems via axioms of Boolean
Algebra
 Theorems can be proved (derived) by axioms

 Example 1: prove the simplification theorem: x y + x

y’ =x yx + x y ’ = x (y + y’) distributive law
 x (y + y’) = x (1) complementary law
 x (1) =x identity

 Example 2: prove the Simplification theorem: x + x y =

x
 x+ x y = x1+ xy identity
 x1+ xy = x (1 + y) distributive
law
 x (1 + y) = x (1) identity
 x (1) =x identity
 In theory, simplification should be done by these laws
 In practice, graphic method is used for convenience
 How does these Boolean Algebra relate to digital
design?
 Lecture 2 – 9

Laws of Boolean Algebra (Cont.)

 Distributive Laws:
 x (y + z) = (x y) + (x z) x +(y z) = (x + y)(x + z)
 “Simplification” Theorems:
 x y + x y’ = x (x + y) (x + y’) = x
 x (y + y’) = x 1 = x x x + x y’ + yx + yy’ = x (1 + y’ + y) = x
 Since y + y’ = 1 Since x x = x and yy’ = 0 also 1 + y’ + y =
 x+ xy= x 1
 x(1 + y) = x x (x + y) = x
 Since 1 + y = 1 x x + x y = x (1 + y) = x
 (x + y’) y = x y
 xy + y’y = xy since y’y = 0 (x y’) + y = x + y
 DeMorgan’s Law: (x + y ) (y’ + y) = x + y since y’ + y =1
 (x + y + z + … ) ’ = x ’ y ’
z’ (x y z … ) ’ = x ’ + y ’ + z ’ + …
 Lecture 2 – 10

More example on DeMorgan’s Law

 Complement of a Function
 F= (A+B+C)’ = (A+x)’ where x = B+C
 => F = A ’ x ’
 => F= A’(B+C)’
 => F = A ’ ( B ’ C ’ ) = A ’ B ’ C ’
 We can generalize F = ( A + B + C + … + Z ) ’ = A ’ B ’ C ’ …
Z’
 Similarly
 F=(ABC)’=(Ax)’ where x = BC
 =>F=A’+x’
 =>F = A’+(BC)’
 =>F = A ’ + B ’ + C ’
 And we have F = (ABC…Z)’ = A ’ + B ’ + C ’ + … + Z ’
 Lecture 2 – 11

 Theorems for Multiplying and

Factoring:
 (x + y) (x’ + z) = x z + x ’ y
 x x’ + x z + y x’ + y z = x z + x’ y
 x z + y x’ + y z = x z + x’ y since x x’ = 0
 x z + y x’ + y z ( x + x’) = x z + x’ y since x + x’ = 1 and y z 1 = y z
 x z + y x’ + y z x + y z x’ = x z + x’ y
 x z (1 + y) + y x ‘ (1 + z ) = x z + x’ y
 x z 1 + y x’ 1 = x z + x’ y since 1 + y = 1 and 1 + z = 1

 x y + x ’ z = (x + z) (x’ + y)
 (x y + x’ ) (x y + z) = (x + z) (x’ + y)
 (x + x’)(y + x’)(x + z)(y + z) = (x + z)(x’ + y)
 (y + x’)(x + z)(y + z + x x’) = (x + z)(x’ + y) since x + x’ = 1 and x x’ =
0
 (y + x’)(x + z)(y + z + x)(y + z + x’) = (x + z)(x’ + y)
 [(y + x’)(y + x’) + z (y + x’)][(x + z)(x + z) + (x + z) y ] = (x + z)(x’ + y)
 [(y + x’)(1 + z)][(x + z)(1 + y)] = (x + z)(x’ + y) since 1 + z = 1 and 1 + y
=1
 Lecture 2 – 12

 Consensus
Theorem:
 x y + y z + x’ z = x y + x’
z
 Proof?

 (x + y) (y + z) (x’ + z) = (x + y) (x’ +
z)
 Proof?
 Lecture 2 – 13

Digital Logic Circuits

 In 1938, Claude Shannon (father of
information theory) showed (in his
Master’s thesis!) how to map Boolean
Algebra to digital circuits (using
electromechanical relays)
 to optimize arrangements of telephone routing switches
using laws of Boolean Algebra
 to use arrangements of switches to solve logic problems
 Today we use the same principles, but
replace electromechanical relays with logic
gates (made of transistors).
Two-valued Boolean Algebra and Basic Logic
gates
 B = {0,1}
 Two binary operators + (OR), .
(AND)
 Complementary operator (‘)
Not gate AND OR
(inverter) Agate
B Y=A.B Agate
B Y=A+B
A Y = A’ 0 0 0 0 0 0
0 1 0 0 1 1
0 1
1 0 0 1 0 1
1 0
1 1 1 1 1 1

INVERT ER OR
AND
 Lecture 2 – 15

Example: three-input function

 Logic Function: F = x.(y+z)
 Truth table Circuits (Schematic
diagram)
x y z (y+z) F=x.(y+z)
0 0 0 0 0
y
0 0 1 1 0
0 1 0 1 0
z F
0 1 1 1 0
x
1 0 0 0 0
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1
Literal – a single variable within a term (complemented or
un- complemented). For example: x, y, z are all literals
 Lecture 2 – 16

Generalization to any function (gate)

A N Y gate Y0, Y1, Y2, Y3 assumes either 0 or 1
A B Y =?
0 0 Y0 • To generalize, we define “minterms” and “maxterms”
0 1 Y1
• Minterms are PRODUCT terms
1 0 Y2
1 1 Y3 • Maxterms are SUM terms

A B Y Minterms A B Y Maxterms
0 0 Y0 A’ B’ 0 0 Y0 A +B
0 1 Y1 A’ B 0 1 Y1 A + B’
1 0 Y2 A B’ 1 0 Y2 A’ + B
1 1 Y3 A B 1 1 Y3 A’ + B’
 Lecture 2 – 17

Generalization by using MINTERMS

A B Y Minterms Y = Y0A’B’ + Y1A’B + Y2AB’ + Y3AB
0 0 Y0 A’ B’
This is also known as the SUM of PRODUCTS
0 1 Y1 A’ B
(SOP) form of the function Y
1 0 Y2 A B’
1 1 Y3 A B Let’s put to test on AND and OR gates

AND Y = 0 A’B’ + 0 A’B + 0 AB’ + 1 AB =

Agate
B Y=A.B AB
0 0 0 OR Y = 0 A’B’ + 1 A’B + 1 AB’ + 1
0 1 0 Agate
B Y=A+B AB
0 0 0 Does
= this
A’Blook like+OR
+ AB’ ABgate?
1 0 0
How about after further simplification:
1 1 1 0 1 1
= A’B + AB’ + AB + AB
1 0 1
= B (A’ + A) + A (B’ + B)
1 1 1 =A+B
 Lecture 2 – 18

Further notation on MINTERMS (Σm):

A B Y Minterms Y = Y0A’B’ + Y1A’B + Y2AB’ + Y3AB
0 0 Y0 m0=A’ B’
This is also known as the SUM of PRODUCTS
0 1 Y1 m1=A’ B
(SOP) form of the function Y
1 0 Y2 m2=A B’
1 1 Y3 m3=A B Let’s put to test on AND and OR gates

AND Y = AB =Σm(3) = m3
Agate
B Y=A.B
0 0 0 OR Y = A’B + AB’ + AB
0 1 0 Agate
B Y=A+B = Σm(1,2,3) = m1 + m2 + m3
1 0 0 0 0 0 Does this look like OR gate?
0 1 1 How about after further simplification:
1 1 1
1 0 1 = A’B + AB’ + AB + AB
1 1 1
= B (A’ + A) + A (B’ + B)
=A+B
 Lecture 2 – 19

Generalization by using MAXTERMS

A B Y Maxterms Y = (Y0+A+B)(Y1+A+B’)(Y2+A’+B)(Y3+A’+B’)
0 0 Y0 A +B
This is also known as the PRODUCT of SUMS
0 1 Y1 A + B’ (POS) form of the function Y
1 0 Y2 A’ + B
1 1 Y3 A’ + B’ Let’s put to test on AND and OR gates

OR Y = (0+A+B)(1+A+B’)(1+A’+B)(1+A’+B’) = A + B
A gate
B Y=A+B = (0+A+B)(0+A+B’)(0+A’+B)(1+A’+B’)
A N D gate Y
0 0 0 A B Y=A.B = (A + B)(A + B’)(A’ + B)
0 1 1 Does this look like OR gate?
0 0 0 How about after further simplification:
1 0 1 0 1 0 =(AA + AB’ + BA + BB’)(A’ + B)
1 1 1 1 0 0 =A(1 + B’ + B)(A’ + B) since AA = A and
1 1 1 BB’=0
=AA’+AB since AA’ = 0
=AB
 Lecture 2 – 20

Further notation on MAXTERMS

(AΠBM):Y Maxterms Y = (Y0+A+B)(Y1+A+B’)(Y2+A’+B)(Y3+A’+B’)
0 0 Y0 M 0 =A + B
This is also known as the PRODUCT of SUMS
0 1 Y1 M 1 =A + B’ (POS) form of the function Y
1 0 Y2 M 2 = A’ + B
1 1 Y3 M 3 = A’ + B’ Let’s put to test on AND and OR gates

OR Y = A + B = ΠM(0) =
A gate
B Y=A+B M0 = (A + B)(A + B’)(A’ + B)
A N D gate Y
0 0 0 A B Y=A.B = ΠM(0,1,2) = M0 M1 M2
0 1 1 0 0 0 Does this look like OR gate?
1 0 1 How about after further simplification:
0 1 0
1 1 1 =(AA + AB’ + BA + BB’)(A’ + B)
1 0 0
=A(1 + B’ + B)(A’ + B) since AA = A and
1 1 1 BB’=0
=AA’+AB since AA’ = 0
=AB
 Apply to previous Example: F = x (y + z)
 SOP: F = Σ m(5,6,7) = m5 + m6 + m7 = x y’ z + x y z’ + x
yz
 POS:= F(x=+ Π
y +M(0,1,2,3,4) = M+0 M
z)(x + y + z’)(x y’1 +Mz)(x
2 M 3 +My’
4 + z’)(x’ + y +
z)
x y z (y+z) F = x.(y+z) Minterms Maxterms
0 0 0 0 0 m0 = x’ y’ z’ M0 = x + y + z
0 0 1 1 0 m1 = x’ y’ z M 1 = x + y + z’
0 1 0 1 0 m2 = x’ y z’ M 2 = x + y’ + z
0 1 1 1 0 m3 = x’ y z M 3 = x + y’ + z’
1 0 0 0 0 m4 = x y’ z’ M 4 = x’ + y + z
1 0 1 1 1 m5 = x y’ z M 5 = x’ + y + z’
1 1 0 1 1 m6 = x y z’ M 6 = x’ + y’ + z
1 1 1 1 1 m7 = x y z M 7 = x’ + y’ + z’
 Apply to previous Example: F = x (y + z)
 SOP: F = Σ m(5,6,7) = m5 + m6 + m7 = x y’ z + x y z’ + x
yz
 Show that if you simplify SOP you get x (y + z)???
 ….

 POS: F = Π M(0,1,2,3,4) = M0 M1 M2 M3 M4
 = (x + y + z)(x + y + z’)(x + y’ + z)(x + y’ + z’)(x’ + y +
z) if you simplify POS, you get x (y +
Show that
z)???
…
 Lecture 2 – 23

Minterms/Maxterms complement each other

x y z Minterms Maxterms
0 0 0 m0 = x’ y’ z’ M0 = x + y + z
0 0 1 m1 = x’ y’ z M 1 = x + y + z’
0 1 0 m2 = x’ y z’ M 2 = x + y’ + z
0 1 1 m3 = x’ y z M 3 = x + y’ + z’
1 0 0 m4 = x y’ z’ M 4 = x’ + y + z
1 0 1 m5 = x y’ z M 5 = x’ + y + z’
1 1 0 m6 = x y z’ M 6 = x’ + y’ + z
1 1 1 m7 = x y z M 7 = x’ + y’ + z’

•One can be derived from the other by applying DeMorgan’s Law

Example:
m5 = x y’ z  M5 = m 5 ’ = [x y‘z]’= x’+ y + z ’
M2 = x + y’+ z  m2 = M 2 ’ = [x + y’+ z]’= x’ y z ’
How to go from specification (truth table) to
circuits?
 Get the truth table and SOP or POS from truth
table
 Carry out logic minimization
 We will look into how we can do it systematically
 Then map the logic expression with gate.
 Lecture 2 – 25

Sum of Product (Minterm expansion)

Example
F(A,B,C)  m(3,4,5,6,7)  m3  m4  m5  m6 
m7
 Lecture 2 – 26

SOP minimization and gate implementation

 A function might have many alternative Boolean
expressions
 But only one minimized Boolean expression

F = A’BC + AB’C’ + AB’C + ABC’ + ABC

= A B' (C + C') + A' B C + A B (C' + C)
= A B'
(B' + +B)A'+ BA'C B+C A B B
= A + A' B C
F
=A + BC C

A
 Lecture 2 – 27

Product of Sum (Maxterm expansion)

F(A, B, C)   M (0,1, 2)  (A  B  C)(A  B  C ')(A 

B ' C)
Then POS minimization and gate implementation
Show that the minimized form: F = (A+B) (A+C)
 Lecture 2 – 28

Summary
 Four Alternative Implementations of F =m(3,4,5,6,7)
: A
Canonical Sum of Minterms
B F1 = A' B C + A B' C' +
F A B' C
C + A B C' + A
1
B C of Minterms
Minimized Sum
F2 = A + BC

F Canonical Products of
2 Maxterms
F F3 = (A+B+C) (A+B+C')
3
(A+B'+C)

F Minimized Products of
4
Maxterms F4 = (A+B) (A+C)
 Lecture 2 – 29

Summary
 Truth table and Boolean expression
 Truth table is the unique signature of a Boolean function
 Many alternative expressions (gate realizations) may have the same truth
table
 Canonical form: Standard form for a Boolean expression
 Provides a unique algebraic signature because it derives from the truth
table
 Either presented in SOP or POS form
 All the terms in SOP or POS must contain all the literals that the
function depends on (because it’s Canonical)
 Leads to a two-level gate implementation (see the previous slide)
 Sum of Product (AND first, OR last)
 also known as minterm expansion
 Product of Sum (OR first,AND last)
 Also known as maxterm expansion
 Lecture 2 – 30

Two-Level Canonical Forms (SOP or POS)


Minterms


Maxterms
 Lecture 2 – 31

Two-Level Canonical Forms (Cont’d)

 From Maxterm to Minterms
 Express Complementary of F in Maxterms
 F' = (A + B' + C') (A' + B + C) (A' + B + C') (A' + B' + C) (A' + B' + C')
 Apply DeMorgan's Law to obtain F
 (F')' = {(A + B' + C') (A' + B + C) (A' + B + C') (A' + B' + C) (A' + B' +
C')}’
 F = A' B C + A B' C' + A B' C + A B C' + A B C

 From Minterm to Maxterms

 Express Complementary of F in Minterms
 F' = A' B' C' + A' B' C + A' B C’
 Apply DeMorgan's Law to obtain F
 (F')' = (A' B' C' + A' B' C + A' B C')’
 F = (A + B + C) (A + B + C') (A + B' + C)
 Lecture 2 – 32

Logic circuits and Boolean expression

 Same function can have different Boolean expression
and hence different gate implementation
 Example: F = AB+C(D+E) = AB + C D +DE
 Same function F, but different expression and hence
different gate implementation
F3 = AB + CD + DE
F3 = AB + C(D +E)

D
 Lecture 2 – 33

About Boolean Algebra

 Boolean algebra provides a mathematical foundation for
manipulating Boolean expressions. With Boolean algebra,
we are able to simplify (or minimize or optimize) a
Boolean expression, which leads to a simplified (or
minimized or optimized) circuit
 In practice, we rarely do it by manual algebraic
manipulation, but use other methods for simplifying
Boolean expressions (next week!). For simple
combinational logic, the most common method for
simplifying Boolean expression is a Karnaugh Map (K-Map).
For more complex and multi-level combinational logic,
computer-aided-design (CAD) algorithms are used, e.g. Quine-
McCluskey, Espresso, etc. Different applications use different
algorithms.
 Lecture 2 – 34

Incompletely Specified Functions

 A n-input functions have 2n input combinations
 But for a given function, not all input combinations are specified
 Example, Binary Coded Decimal Digit Increment by 1
 BCD digits encode the decimal digits 0 - 9 in the bit patterns of 0000
- 1001
 6 out of 16 possible are not Off-set of
defined
0 0 0 0 0 0 0 1 W
A
0 0 B0 C1 D 0 W0 X 1 Y0 Z
0 0 1 0 0 0 1 1 On-set of W
0 0 1 1 0 1 0 0
0 1 0 0 0 1 0 1
0 1 0 1 0 1 1 0
0 1 1 0 0 1 1 1 Don't care (DC) set of W
0 1 1 1 1 0 0 0
1 0 0 0 1 0 0 1
1 0 0 1 0 0 0 0
1 0 1 0 X X X X
1 0 1 1 X X X X These input patterns should never
1 1 0 0 X X X X
1 1 0 1 X X X X
1 1 1 0 X X X X be encountered in practice
1 1 1 1 X X X X
associated output values are "Don't
Cares"
 Lecture 2 – 35

Incompletely Specified Functions

 Canonical Representations of the BCD Increment by
1 Function:
 Minterms
 Z = m0 + m2 + m4 + m6 + m8 + d10 + d11 + d12 + d13 +
d14 + d15
 Z = m(0, 2, 4, 6, 8) + d(10, 11, 12 ,13, 14, 15)
 W = m(7, 8) + d(10, 11, 12 ,13, 14, 15)
 X = m(3, 4, 5, 6) + d(10, 11, 12 ,13, 14, 15)
 Y = m(1, 2, 5, 6) + d(10, 11, 12 ,13, 14, 15)
 Maxterms
 Z = M1 • M3 • M5 • M7 • M9 • D10 • D11 • D12 • D13 •
D14 • D15
 Z = M(1, 3, 5, 7, 9) • D(10, 11, 12, 13, 14 ,15)
 W =
 X =
 Y=
 Lecture 2 – 36
More Logic Functions
For a 2-input function, there are 22 = 4 input
combinations
and 24 = 16 output functions
162 Boolean
variables functions
X,Y of two variables
 2 0,
identities
 4 primitive functions 1X',Y', X•Y, (AND, OR,
X+Y
 2 CMOS building blocks (X+Y)’, NOT) (NAND,
 2 equality/inequality (X•Y)’ XY, NOR) (XOR,
gates
 4 inhibition and implication (XY)’ XNOR)
(for comparison,
function too)
X Y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

0 X Y X+Y (XY)’ X’ (X • Y)’

1
X•Y X Y (X+Y)’
Y’
 Lecture 2 – 37

Logic Functions: XOR, XNOR

• X O R Gate: • X N O R Gate:
– Z=1 if X  Y (inequality – Z=1 if X = Y (equality
gate) gate)
– Z=1 if only X or Y = 1 – Z=1 if none or both
» odd function X,Y=1
• Gate symbol » even function
X
• Gate symbol
X Z
Y Z
X Y Z • Truth table X Y Z
Y 0 0 1
0 0 0
0 1 1 0 1 0
• Truth 1 0 0
1 0 1
table 1 1 0 1 1 1
• Boolean expression • Boolean expression
– X  Y = X Y' + – (X  Y)’ = X Y +
X' X' Y’
Y
 Lecture 2 – 38

Common 2-input Logic Gates

 Lecture 2 – 39

2-input and 3-input Logic Gates

• 3-input OR gates could be made by 2 2-input OR
gates
– By associate law x + y + z = (x+y) + z = x + (y+z)
– output equals to 1 if any input is 1


z

• Could 3-input N O R gate be made by 2 2-input N O R

gates?
– Associate law applies to primitive gates, but not to N O R gates
– [(x+y)’+z]’ = (x+y)  z’ = xz’ + yz’  (x+y+z)’
– output equals to 0 if any input is 1


z
Sequence of designing a digital circuit given
the logic function
 Design
Sequence:
 1.Truth Table
(input and output
relations)
 Derive truth
table from project
specifications
 2. Boolean
Expressions
 Derived from the
truth table
 3.Logic
Minimization
 Use Laws of Boolean Algebra to reduce the complexity of Boolean
expressions while maintaining the same function
 2’ Graphic Method (K-Map) (Chapter 3)
 Re-express the truth table in graphs (K-Map)
 3’ Logic Minimization
 READ the simplified Boolean expressions from the graphs
 Lecture 2 – 41

Reading assignment
 Chapter 2.1 to 2.8 of
textbook