Adapted from Dr. Bassam Kahhaleh’ Slides by Prof. Iyad Jafar

Digital Logic

0907231

Chapter 2

Boolean Algebra and

Logic Gates

Outline

• Introduction
• Binary Logic and Logic Operators
• Boolean Algebra
• Dual and Complement of Logic Functions
• Canonical Forms
• Standard Forms
• Nonstandard Forms
• Other Types of Gates

2

Introduction

Introduction

• Digital systems are electronic circuits that implement logic operations to manipulate binary information
• They are composed of transistors, resistors, and interconnect
• Logic circuits that implement basic logic operations are called Gates
• Gates can be connected to build digital circuits

4

Logic Signals

• Binary ‘0’ is represented�by a “low” voltage�(range of voltages)

​

• Binary ‘1’ is represented�by a “high” voltage�(range of voltages)

​

• The “voltage ranges” guard�against noise

5

Binary Logic and Logic Operations

Binary Logic

• Binary logic describes the operational properties of digital circuit in a mathematical notion
• Deals with binary values the may take two values only (0/1, ON/OFF, True/False, High/Low)
• We can define binary variables that may take two values (X,Y, Z, Door, Switch ….)
• Logical operators operate on binary values and binary variables.

7

Logic Operators

• AND
• Notation

​

• Operation

​

​

​

​

​

• Graphical Symbol

8

Z = X AND Y 🡺 Z = X • Y 🡺 Z = XY

Z = X • Y

0 = 0 • 0

0 = 0 • 1

0 = 1 • 0

1 = 1 • 1

Truth Table

2-input AND Gate

We say that Z is a function of X and Y

Z = F(X,Y)

Logic Operators

• OR
• Notation

​

• Operation

​

​

​

​

​

• Graphical Symbol

9

Z = X OR Y 🡺 Z = X + Y

Z = X + Y

0 = 0 + 0

1 = 0 + 1

1 = 1 + 0

1 = 1 + 1

Truth Table

2-input OR Gate

We say that Z is a function of X and Y

Z = F(X,Y)

Logic Operators

• NOT (Complement)
• Notation

​

• Operation

​

​

​

​

• Graphical Symbol

10

Z = X’

1 = 0

Truth Table

0 = 1

NOT Gate (Invertor)

We say that Z is a function of X

Z = F(X)

Logic Operations as Switches

• For inputs:
• logic 1 is switch closed
• logic 0 is switch open
• For outputs:
• logic 1 is light on
• logic 0 is light off.
• NOT uses a switch such

that:

• logic 1 is switch open
• logic 0 is switch closed

​

11

Logic Operators

• Timing Diagram

12

Gate Delay

• In actual physical gates, if one or more input changes causes the output to change, the output change does not occur instantaneously.
• The delay between an input change(s) and the resulting output change is the gate delay denoted by t_G

​

13

t_G

t_G

Input

Output

Time (ns)

0

0

1

1

0

0.5

1

1.5

t_G = 0.3 ns

Gate Delay

• Delay accumulates toward the output!

​

• When designing digital system, we are concerned about the worst case delay!

14

0.3 ns

0.3 ns

0.2 ns

0.2 ns

Logic Gates

• Inputs and Outputs
• Inverter 🡪 one input and one output
• AND / OR 🡪 one output and two or more inputs

15

• Fan-in
• The number of inputs a logic gate can handle
• Fan-Out
• The maximum number of inputs (load) that can be connected to the output of a gate without degrading the normal operation

Real Stuff

• SN74LS08
• QUADRUPLE 2-INPUT AND GATES

16

Real Stuff

• SN74LS32
• Quad Two-input OR gate

17

Real Stuff

• SN74LS04
• HEX Inverters

18

Boolean Algebra

Boolean Algebra

• George Boole (1854)

​

• Deals with binary variables and logic operations

​

• Defines postulates and theorems to manipulate logic expressions algebraically

​

• A binary/Boolean expression/function is formed by binary variables, constants 0 and 1, logic operations, and parenthesis

​

​

​

20

Operator Precedence

• Must know precedence between operators to evaluate binary expressions

Parentheses ( . . . ) • ( . . .)

NOT x’

AND x • y

OR x + y

21

1

2

3

4

Logic Expressions/Function

• Consider the following logic function

F(w,x,y) = w • x + y’

• Truth table representation

​

22

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

1

0

1

0

1

0

1

1

Logic Expressions/Function

• Logic diagram representation

23

F(w,x,y) = w • x + y’

x

y

w

w • x

y’

F(w,x,y)

Example

• Draw the logic diagram and derive the truth table

24

F(A,B,C,D) = A C’ + B’D

D

C

B

F(A,B,C,D)

A

Example

25

F(A,B,C,D) = A C’ + B’D

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

0

1

0

1

0

0

0

0

1

1

0

1

1

1

0

0

Example

• Consider

26

F1(w,x,y) = w’x’ + w

F2(w,x,y) = w+x’

x

w

F1

F2

x

w

??

Logic Expressions/Function

• A logic function may have different expressions, hence different logic diagrams
• However, there is always one truth table!
• Need the simplest expression in order to reduce cost!
• Tools!
• Boolean Algebra!

27

Boolean Algebra

Postulates and Theorems

Boolean Algebra

• Identity elements

x • 1 = x x + 0 = x

x • 0 = 0 x + 1 = 1

• Idempotence

x • x = x x + x = x

​

• Existence of Complement

x • x’ = 0 x + x’ = 1

​

​

29

Boolean Algebra

• Involution

( x’ )’ = x

• Commutative Law

x • y = y • x x + y = y + x

​

• Distributive Law

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

30

Boolean Algebra

• Associative Law

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

31

Boolean Algebra

• DeMorgan’s Theorem

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

​

• Absorption Theorem

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

​

​

​

​

​

32

Proof

Boolean Algebra

• Simplification Theorem

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

​

​

​

33

Proof

Boolean Algebra

• Minimization Theorem

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

​

​

​

34

Proof

Example

• Show that

x’ y’ + x’y+ xy’+ xy = 1

​

​

35

By truth table

By algebra

Example

• Show that

ABC + A’C’+AC’ = AB + C’

​

​

36

Proof

Example

• Show that

wy + wy’ + x’z + w’z = w + z

​

​

37

Proof

Dual and Complement of Logic Functions

Dual of a Function

• Duality
• The dual of a Boolean algebraic expression is obtained by interchanging the AND and the OR operators and replacing the 1’s by 0’s and the 0’s by 1’s.
• x • ( y + z ) = ( x • y ) + ( x • z )
• x + ( y • z ) = ( x + y ) • ( x + z )

​

• x • x = x x + x = x

​

• x • 0 = 0 x + 1 = 1

39

Applied to a valid equation produces a valid equation

Complement of a Function

​

​

​

• In truth table

​

​

​

40

F(w,x,y)

F(w,x,y)

Complement

Complement of a Function

​

​

• Logic Expression

​

​

41

F(w,x,y)

F(w,x,y) = w’ • x’ + w

F(w,x,y)

Complement

F’(w,x,y) = (w’ • x’ + w)’

= (w’ • x’)’ • w’

= (w’’ + x’’ ) • w’

= (w + x ) • w’

= w • w’ + x • w’

= 0 + x • w’

= x • w’

DeMorgan’s Theorem

Duality and Complement

• Duality & Literal Complement

42

Find the Dual of a function

​

Complement individual literals

Example

43

Example

44

• Find the complement

F(A,B,C,D) = A(B’C+A’B) + D

Canonical Forms

Canonical Forms

• Given the truth table for some function, can we find a valid logic expression for it?
• A valid expression should
• Evaluate to ‘1’ for the input combinations for which the function is ‘1’
• Evaluate to ‘0’ for the input combinations for which the function is ‘0’
• Canonical Forms
• Sum of Minterms (SoM)
• Product of Maxterms (PoM)

46

Sum of Minterms (SoM)

• Consider the 1s of the function
• AND the input variables to produce 1

47

0 • 1

1 • 1

1 • 1

x • y

+

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

F(x,y) = m₁ + m₃

F(x,y) = ∑ (1,3)

0

1

2

3

m

m

m

m

Sum of minterms (SOM)

minterm

Product (AND) term that contains all variables

Example

48

1 • 0 • 0

1 • 1 • 0

1 • 1 • 0

0 • 0 • 1

+

+

0

1

2

3

4

5

6

7

F(A,B,C) = A’B’C + AB’C’+ABC’

F(A,B,C) = m₁ + m₄ + m₆

F(A,B,C) = ∑ (1,4,6)

m

m

m

m

m

m

m

m

Example

• Derive the truth table, SoM logic expression and logic diagram of

49

F(x,y,z) = ∑ (0,3,5,6)

F(x,y,z) = x’y’z’+ x’yz + xy’z + xyz’

Example

• Derive the, truth table, SoM logic expression and logic diagram of

50

F(x,y,z) = ∑ (0,3,5,6)

F(x,y,z) = x’y’z’+ x’yz + xy’z + xyz’

Example

• Determine the SoM expression for F and F’

51

Example

• SoM expression

52

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

0

0

0

1

0

1

0

0

1

0

0

0

1

0

0

0

F(A,B,C,D) = A’B’CD+A’BC’D+AB’C’D’+ABC’D’

Example

• If F(x,y,z) = x’yz’ + xy’z + xyz, then

53

• F(x,y,z) = ∑ ( )

• F’(x,y,z) = ∑ ( )

2, 5, 7

0, 1, 3, 4, 6

Using Algebra to find SOM

• Use algebra to write the SOM expression for

F(A,B,C,D) = A(BC + BC’) + A’B’C

54

Product of Maxterms (PoM)

• Consider the 0s of the function
• OR the input variables to produce 0

55

F(x,y) = ∏ (0,2)

0 + 0

0 + 0

x + y

1 + 0

•

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

F(x,y) = M₀ • M₂

0

1

2

3

M

M

M

M

Product of Maxterms (POM)

maxterm

Sum (OR) term that contains all variables

Example

56

0 + 0 + 0

A + B + C

0 + 1 + 0

1 + 0 + 1

0 + 0 + 0

•

•

0

1

2

3

4

5

6

7

F(A,B,C) = (A+B+C)(A+B’+C)(A’+B+C’)

F(A,B,C) = M₀ • M₂ • M₅

F(A,B,C) = ∏(0,2,5)

M

M

M

M

M

M

M

M

Example

• Derive the truth table, PoM logic expression and logic diagram of

57

F(x,y,z) = ∏ (1,7)

F(x,y,z) = (x+y+z’)(x’+y’+z’)

Example

• Derive the, truth table, PoM logic expression and logic diagram of

58

F(x,y,z) = ∏ (1,7)

F(x,y,z) = (x+y+z’)(x’+y’+z’)

Example

• Determine the PoM expression for F and F’

59

Example

• POM expression for F

60

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

1

0

1

1

0

1

1

0

1

1

1

1

1

1

0

1

F(A,B,C,D) =

(A+B+C+D’)(A+B’+C+D)(A+B’+C’+D’)(A’+B’+C’+D)

Example

• If F(w,x,y,z) = ∑ (1,2,4,9,12,13,15), then

61

• F’(w,x,y,z) = ∏ ( )

• F’(w,x,y,z) = ∑ ( )

• F(w,x,y,z) = ∏ ( )

0,3,5,6,7,8,10,11,14

0,3,5,6,7,8,10,11,14

1,2,4,9,12,13,15

Note

• The minterms of F are the maxterms for F’
• The maxterms of F are the minterms for F’

Example

• Use algebra to write the PoM expression for

F(A,B,C) = A+BC’

62

Relationship between Minterms and Maxterms

• Consider F(A,B,C)

​

​

​

​

63

m₃ = A’BC

M₃ = A + B’ + C’

m_j = (M_j)’

(m_j)’ = M_j

Exercise

• Write the logic expression for m₂₂ and M₂₂ for a function of 6 variables F(a,b,c,d,e,f)

64

Why Learn both SoM and PoM?

• Many times, one form can result in a simpler canonical circuit than the other

65

Standard Forms

Standard Forms

• SoM and PoM are expensive to implement!
• Sum of product (SoP)
• ORing (sum) of AND (product) terms not necessarily containing all the variables of the function

​

• Logic diagram is a two-level circuit

67

Standard Forms

• Product of sum (PoS)
• ANDing (product) of OR (sum) terms not necessarily containing all the variables of the function

​

• Logic diagram is a two-level circuit

68

Example

• Sum of Products (SoP)

​

​

​

• Product of Sums (PoS)

69

Example - Write F(A,B,C) into SOP

70

Example – Write F(A,B,C) as PoS

71

Non-standard Forms

Nonstandard Forms

• Mix of PoS and SoP

73

Summary of Forms

74

(A+B+C)(A+B+C)

Other Types of Gates

Logic Operators

• AND

​

​

​

• NAND (Not AND)

76

Logic Operators

• OR

​

​

​

• NOR (Not OR)

77

Logic Operators

• XOR (Exclusive-OR)

​

​

​

• XNOR (Exclusive-NOR)� (Equivalence)

78

Logic Operators

• NOT (Inverter)

​

​

​

• Buffer

79

Real Stuff

• SN74LS00 (Quadruple 2-input NAND)
• SN74LS02 (Quadruple 2-input NOR)
• SN74LS86 (Quadruple 2-input XOR)
• SN74LS7266 (Quadruple 2-input XNOR)

​

​

​

80

Exercises

Suggested Problems (5^th Edition)

• 2-5
• 2-6
• 2-7
• 2-9
• 2-10
• 2-12
• 2-13
• 2-14
• 2-18

82

Exercises

• If F(x,y,z) = xy’+yz +yz’, than show that F can be simplified to x + y.

83

Exercises

84

Exercises

85