Boolean Algebra PDF

Preview

Summary

Boolean Algebra...

Description

Announcements ECE 2300! Digital Logic & Computer Organization Fall 2020

• HW 1 posted on Canvas tonight – Due Friday, September 18, at 11:00pm

• Enroll on Piazza if you have not already • I will be switching in and out of presentation mode to annotate the slides

Boolean Algebra

– Annotations in presentation mode are not saved – Annotated slides posted after class

Lecture 2: 1

Lecture 2: 2

For Those Joining Remotely

Lecture Outline

• Use the Raise Hand feature to ask a question – After I pause to take questions from the in-class participants, Alisha (TA) will inform me about questions from online participants – When I call on you, you should unmute, and ask your question – Don’t forget to re-mute and drop your hand afterwards

Lecture 2: 3

• Boolean Algebra definitions • Boolean Algebra axioms and theorems • More definitions – Minterms and maxterms – Canonical sum and product

• • • • •

Algebraic simplification Sum-of-products and product-of-sums circuits De Morgan’s Law NAND and NOR Sum-of-products using NAND and product-ofsums using NOR Lecture 2: 4

Boolean Algebra

Boolean Equations

• Mathematical foundation for analyzing and simplifying digital logic circuits

• Describe digital functions • variable = expression

• Boolean algebra (George Boole, 1854) – Two-valued algebraic system – Used to formulate true or false postulations

• Variables are either 1 or 0 – True or False – On or Off – Set or Reset

• Switching algebra (Claude Shannon, 1938) – Adopted Boolean algebra for digital circuits – Terms “Boolean algebra” and “switching algebra” ! are used interchangeably

• Basic operators are NOT, AND, and OR

Lecture 2: 5

Lecture 2: 6

Review: NOT, AND, and OR

Definitions • Literal: variable or its complement

A

Y

NOT Gate

A B

Y

A B

Y

AND Gate

OR Gate

A

Y

A B

Y

A B

Y

0

1

0 0

0

0 0

0

1

0

0 1

0

0 1

1

1 0

0

1 0

1

1 1

1

1 1

1

Lecture 2: 7

– X’, Y

• Product term: AND of literals – X’•Y

• Sum term: OR of literals – X+Y+Z’

Lecture 2: 8

Operator Precedence

Axioms of Boolean Algebra

• What does W•X’+Y•Z mean?

• Definitions that are assumed true

• Operator precedence rules

• Obey the principle of duality

1. NOT 2. AND 3. OR

– Still correct if interchange AND and OR, 1’s and 0’s – Axioms come in pairs

Lecture 2: 9

Lecture 2:10

Axioms of Boolean Algebra

Intuition Behind Duality of AND and OR, 1’s and 0’s

• Binary

• AND

(A1)

– 1 only if all inputs are 1 – 0 if any input is 0

X = 0 if X ≠ 1

(A1’)

X = 1 if X ≠ 0

(A2’)

If X = 1, then X’ = 0

• OR – 0 only if all inputs are 0 – 1 if any input is 1

• Complement (A2)

If X = 0, then X’ = 1

Other complement symbols: ~X, /X, X

Lecture 2:11

Lecture 2:12

Axioms of Boolean Algebra

Single Variable Theorems

• AND and OR (A3) 0•0=0 (A4) 1•1=1 (A5) 0•1=1•0=0

• • • • •

(A3’) 1+1=1 (A4’) 0+0=0 (A5’) 1+0=0+1=1

• A1-A5 completely define Boolean algebra

Identity: Null Element: Idempotency: Involution: Complements:

(T1) (T2) (T3) (T4) (T5)

X•1=X X•0=0 X•X=X (X’)’=X X•X’=0

(T1’) X+0=X (T2’) X+1=1 (T3’) X+X=X (T5’) X+X’=1

• Can prove by perfect induction

– Everything else derived from these axioms

– Show that all possible inputs meet the theorem

Lecture 2:13

Proof by Perfect Induction (T3) X•X=X

Lecture 2:14

Two and Three Variable Theorems • Commutativity

(T3’) X+X=X

(T6) X=0 è 0•0=0 X=1 è 1•1=1

X=0 è 0+0=0 X=1 è 1+1=1

X•Y = Y•X

(T6’) X+Y = Y+X

• Associativity (T7)

(X•Y)•Z = X•(Y•Z)

(T7’) (X+Y)+Z = X+(Y+Z)

• Distributivity (T8)

X•Y+X•Z = X•(Y+Z)

AND distributes over OR

Lecture 2:15

(T8’) (X+Y)•(X+Z) = X+(Y•Z) OR distributes over AND

Lecture 2:16

Two and Three Variable Theorems

Duality • An’ is the dual of An, Tn’ is the dual of Tn

• Covering (T9) X•(X+Y) = X

(T9’) X+X•Y = X

• Deriving the dual • Combining (T10) X•Y+X•Y’ = X

(T10’) (X+Y)•(X+Y’) = X

– Use parentheses to denote operator precedence – Swap AND and OR, 0’s and 1’s

• Consensus (T11)

X•Y+X’•Z+Y•Z = X•Y+X’•Z

(T11’)

(X+Y)•(X’+Z)•(Y+Z) = (X+Y)•(X’+Z) Lecture 2:17

Lecture 2:18

Duality Derivation Examples

Recall These Definitions

• Derive T9’ from T9 X+X•Y = X

• Literal: variable or its complement – X’, Y

(T9)

X+(X•Y) = X

(precedence)

X•(X+Y) = X

(T9’)

• Product term: AND of literals – X’•Y

• Derive T11’ from T11 X•Y+X’•Z+Y•Z = X•Y+X’•Z

• Sum term: OR of literals

(T11)

(X•Y)+(X’•Z)+(Y•Z) = (X•Y)+(X’•Z) (precedence) (X+Y)•(X’+Z)•(Y+Z) = (X+Y)•(X’+Z) (T11’)

Lecture 2:19

– X+Y+Z’

Lecture 2:20

More Definitions

Minterms & Maxterms for 3 Variables

• Normal term: Product or sum term in which each literal appears once

X Y Z minterm

– Normal product example: X•Y’•Z – Normal sum example: X’+Y+Z’

000 001 010 011 100 101 110 111

• Minterm: Normal product that results in a 1 ! for the given input values (otherwise 0) – X=0 Y=0 Z=1 – X’•Y’•Z

• Maxterm: Normal sum that results in a 0 ! for the given input values (otherwise 1) – X=0 Y=0 Z=1 – X+Y+Z’

X’Y’Z’ X’Y’Z X’YZ’ X’YZ XY’Z’ XY’Z XYZ’ XYZ

minterm! name m0! m1! m2! m3! m4! m5! m6! m7!

maxterm! name X+Y+Z M0! X+Y+Z’ M1! X+Y’+Z M2! X+Y’+Z’ M3! X’+Y+Z M4! X’+Y+Z’ M5! X’+Y’+Z M6! X’+Y’+Z’ M7! maxterm

Lecture 2:21

Two Ways to Express a Logic Function • Canonical sum: The sum (OR) ! of minterms (ANDs) for which F=1

XYZ 000 – Also called sum-of-products 001 – F = X’•Y’•Z’ + X’•Y•Z + X•Y’•Z’ + X•Y•Z 010 = ΣX,Y,Z(0,3,4,7) 011 • Canonical product: The product (AND) ! 100 of maxterms (ORs) for which F=0 101 – Also called product-of-sums 110 – F = (X+Y+Z’)•(X+Y’+Z)•(X’+Y+Z’)•(X’+Y’+Z) 111

Lecture 2:22

5 Minute Break

F 1 0 0 1 1 0 0 1

= ΠX,Y,Z(1,2,5,6)

• F = ΣX,Y,Z(0,3,4,7) = ΠX,Y,Z(1,2,5,6)

Lecture 2:23

Lecture 2:24

Algebraic Simplification

Algebraic Simplification Example • 1-bit binary adder

• Apply theorems to canonical sum/product ! to reduce

– inputs: A, B, Carry-in – outputs: Sum, Carry-out

– The number of terms, and – The number of literals in each term

A B Cin (inputs)

S Cout (outputs)

• Truth Table à Canonical sum • More compact expression leads to a smaller, faster, and lower power digital logic circuit – Fewer logic gates – Smaller gates (fewer inputs)

Lecture 2:25

Idempotency and Combining Theorems

A 0 0 0 0 1 1 1 1

B Cin Cout 0 0 0 0 Cout = A'•B•Cin + A•B'•Cin + A•B•Cin' + A•B•Cin 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 Lecture 2:26

Algebraic Simplification Example Cout = A'•B•Cin + A•B'•Cin + A•B•Cin' + A•B•Cin

• Idempotency: X = X+X • Combining: X•Y+X•Y’ = X • Important for understanding Karnaugh Maps (next time)

Lecture 2:27

= A'•B•Cin + A•B'•Cin + A•B•Cin' + A•B•Cin + A•B•Cin

(idempotency)

= B•Cin + A•B'•Cin + A•B•Cin' + A•B•Cin

(combining)

= B•Cin + A•B'•Cin + A•B•Cin' + A•B•Cin + A•B•Cin

(idempotency)

= B•Cin + A•Cin + A•B•Cin' + A•B•Cin

(combining)

= B•Cin + A•Cin + A•B

(combining)

Lecture 2:28

Smaller, Faster, Lower Power Circuit

Example: Prime Number Detector xyz 000 001 • Step 1: Create truth table 010 011 100 • Step 2: Derive canonical forms 101 – F = ∑x,y,z(2,3,5,7) = x’yz’ + x’yz + xy’z + xyz 110 111 – F = ∏x,y,z(0,1,4,6) = (x+y+z)(x+y+z’)(x’+y+z)(x’+y’+z)

• F = 1 if number xyz is prime (in decimal) Cout = A'•B•Cin + A•B'•Cin + A•B•Cin' + A•B•Cin = B•Cin + A•Cin + A•B

4 three-input ANDs 1 four-input OR

à

3 two-input ANDs 1 three-input OR

F 0 0 1 1 0 1 0 1

• Step 3: Simplify expression – Algebraic simplification – Systematic minimization (next time) Lecture 2:29

Lecture 2:30

Algebraic Simplification

Sum-of-products • OR of AND terms

• F = ∑x,y,z(2,3,5,7)

– X•Y + Y’•Z’ + X’•Y•Z

= x’yz’ + x’yz + xy’z + xyz = x’y + xy’z + xyz

[combining]

= x’y + xz

[combining]

• Circuits look like this (also NOT for some inputs) wire output

inputs

AND-OR Lecture 2:31

Lecture 2:32

Product-of-sums

De Morgan’s Theorem

• AND of OR terms

• So important, known as De Morgan’s Law

– (Y+Z’) • (X+Z’) • (X+Y+Z’) (T12)

(X1•X2•…•Xn)’ = X1’+X2’+…+Xn’

(T12’)

(X1+X2+…+Xn)’ = X1’•X2’•…•Xn’

• Circuits look like this (also NOT for some inputs) wire output

inputs

OR-AND Digital logic functions can be expressed as SOP or POS Lecture 2:33

Lecture 2:34

De Morgan Example

NAND Logic Gate

• By DeMorgan’s Law (X•Y•Z)’ = X’+Y’+Z’

• Proof by perfect induction

XYZ (X•Y•Z)’ X’+Y’+Z’ 000 001 010 011 100 101 110 111

1 1 1 1 1 1 1 0

1 1 1 1 1 1 1 0

Lecture 2:35

(X•Y)’

X Y

= NAND

Using De Morgan’s Law: (X•Y)’ = X’+Y’ X

X’

Y

Y’

X’+Y’

= Also a NAND

Lecture 2:36

Sum-of-products Revisited

NOR Logic Gate X Y

X+Y

(X+Y)’

= NOR

Using De Morgan’s Law: (X+Y)’ = X’•Y’ AND-OR

X

X’ X’•Y’

Y

=

Y’

Also a NOR

NAND-NAND Lecture 2:37

Lecture 2:38

Product-of-sums Revisited

Before Next Class • H&H 2.4-2.7

Next Time OR-AND Combinational Logic Minimization NOR-NOR Lecture 2:39

Lecture 2:40...