Digital Fundamentals

Thomas L. Floyd

Logic Gates /
Boolean Algebra and Logic Simplification
Chapter 4
Ch.4 Summary

Boolean Variables

variable : 0 or 1.

complement : inverse of a variable

complement of A is A.

literal : variable or its complement

Ch.4 Summary

Boolean Addition

Addition (Sum) : OR operation

Sum = 0 iff all of literals are 0
Sum = 1 iff any of literal is 1

Determine A, B, and C that satisfies A + B + C = 0

Each literal must equal 0; therefore A = 1, B = 0 and
C = 1.
Ch.4 Summary

Boolean Multiplication

Multiplication : AND operation

Multiplication = 0 iff any of literal is 0
Multiplication = 1 iff all of literals are 1

Determine A, B and C if the product term of A.B.C = 1?

Each literal must = 1; therefore A = 0, B = 0 and C = 1.
Ch.4 Summary

Commutative Laws
The commutative laws apply to both addition and
multiplication
In terms of the result, the order in which variables are
ORed makes no difference.

A+B=B+A

For multiplication, the commutative law states:

In terms of the result, the order in which variables
are ANDed makes no difference.
AB = BA
Ch.4 Summary

Associative Laws
The associative laws also apply to both addition and
multiplication. For addition,
When ORing more than two variables, the result is the
same regardless of the grouping of the variables.

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

For multiplication
When ANDing more than two variables, the result is the
same regardless of the grouping of the variables.
A(BC) = (AB)C
How about NAND?
Ch.4 Summary

Distributive Law
The distributive law is the factoring law

AB + AC = A(B+ C)

The distributive law can be illustrated with equivalent

circuits:

A(B+ C) AB + AC
Ch.4 Summary

Rules of Boolean Algebra

1. A + 0 = A 7. A . A = A
2. A + 1 = 1 8. A . A = 0
=
3. A . 0 = 0 9. A = A
4. A . 1 = A 10. A + AB = A
5. A + A = A 11. A + AB = A + B
6. A + A = 1 12. (A + B)(A + C) = A + BC
Ch.4 Summary

Rules of Boolean Algebra

Rule 1: A + 0 = A

When A = 1, the input causes the output to go to X = 1.

When A = 0, the 0 inputs cause the output to go to X = 0.
In either case, the value of X equals the value of A.
Ch.4 Summary

Rules of Boolean Algebra

Rule 2: A + 1 = 1

When A = 1, the inputs cause the output to go to X = 1.

When A = 0, the 1 input caused the output to go to X = 1.
In either case, the value of X equals one (1).
Ch.4 Summary

Rules of Boolean Algebra

Rule 3: A • 0 = 0

When either input to an AND gate equals 0, the output

from the gate has a value of X = 0, regardless of the value
at the other input.
Ch.4 Summary

Rules of Boolean Algebra

Rule 4: A • 1 = A

When one input to an AND gate equals 1, the output

from the gate has a value of X = A. As shown, X = 1
when A = 1 and X = 0 when A = 0.
Ch.4 Summary

Rules of Boolean Algebra

Rule 5: A + A = A

When the inputs to an OR gate are equal, the output

equals the value at the inputs. When both inputs equal 1,
the gate output is X = 1. When both inputs equal 0, the
gate output is X = 0.
Ch.4 Summary

Rules of Boolean Algebra

Rule 6: A + A = 1
When the inputs to an OR gate are unequal (complements),
one of the two always equals 1. When either input equals 1,
the gate output is X = 1. Therefore, the output from the OR
gate equals 1 whenever the inputs are unequal
(complementary).
Ch.4 Summary

Rules of Boolean Algebra

Rule 7: A • A = A

When the inputs to an AND gate are equal, the gate

output also equals that value. Thus, X = 1 when both
inputs equal 1 and X = 0 when both inputs equal 0.
Ch.4 Summary

Rules of Boolean Algebra

Rule 8: A • A = 0
When the inputs to an AND gate are unequal
(complements), one of the two always equals 0.
When either input equals 0, the gate output is X = 0.
Therefore, the output from the AND gate equals 0
whenever the inputs are unequal (complementary).
Ch.4 Summary

Rules of Boolean Algebra

Rule 9: A = A
When a value is inverted, it is the complement of the
original value. When inverted a second time, it
returns to its original value. Thus, A = 0 inverted
twice equals 0 and A = 1 inverted twice equals 1.
Ch.4 Summary

Rules of Boolean Algebra

Rule 10: A + AB = A
The circuit and truth table (below) can be used to
demonstrate this rule. The truth table shows the outputs
from the circuit for every possible combination of A and B.
In each case, the output from the OR gate equals the
value of A. Thus, A + AB always equals the value of A.
Ch.4 Summary

Rules of Boolean Algebra

Rule 11: A + AB = A + B
The circuits and truth table (below) demonstrate this rule.
The truth table shows the outputs from the two circuits are
equal for every possible combination of A and B. As such,
the two functions (A + AB) and (A + B) are equal.
Ch.4 Summary

Rules of Boolean Algebra

Rule 12: (A + B)(A + C) = A + BC
The circuits and truth table (below) demonstrate this rule. The
truth table shows the outputs from the two circuits are equal for
every possible combination of A and B. As such, the two
functions (A + B)(A + C) and (A + BC) are equal.
Ch.4 Summary

DeMorgan’s Theorem
The complement of two or more ANDed variables equals
the OR of the individual variable complements.

XY= X +Y
Ch.4 Summary

DeMorgan’s Theorem
The complement of two or more ORed variables equals
the AND of the individual variable complements.

X +Y = X  Y
Ch.4 Summary

DeMorgan’s Theorem
The complement of two or more ORed variables equals
the AND of the individual variable complements.

X +Y + Z = X  Y  Z

X  Y  Z = X +Y + Z
Ch.4 Summary

DeMorgan’s Theorem: Application

A BC+D(E+ F )=?

( AB+C )( A +BC )= ?
Ch.4 Summary

Boolean Expression for a Logic Circuit

Derive Boolean expression for a given combinatorial logic

circuit.
Ch.4 Summary

Constructing a Truth Table

Ch.4 Summary

Logic Simplification

AB+ A ( B+C )+B ( B +C )= B +AC

Ch.4 Summary

Logic Simplification

( Ā +B )C + ABC= ?
Ch.4 Summary

Sum-of-Products (SOP) Form

Two or more product terms are summed by Boolean

addition

AB+ BCD + AC 
Ā B+ Ā B C̄+ AC 
Ā B+ ABC + AC 
Ch.4 Summary

Sum-of-Products (SOP) Form

AB+ BCD + AC
Ch.4 Summary

Sum-of-Products (SOP) Form

AB+ BCD + AC
Ch.4 Summary

Standard SOP

AB C  A B  ABC D
↓
A B CD + A B C D + A B CD
 A B C D + A B C D + A B C D + AB C D
Ch.4 Summary

Binary Representation

SOP expression is equal to 1 only if one or more of the

product terms in the expression is equal to 1

ABCD  1 1 1 1
ABC D 1 0  0 1
ABC D  0  0  0  0
Ch.4 Summary

SOP to Truth Table

Ch.4 Summary

Product-of-Sums (POS) Form

Two or more product terms are summed by Boolean

addition

( Ā +B )( A+ B̄+C ) 
( A +B )( A+ B̄+C )( Ā +C ) 
( A +B )( A+B+C )( Ā +C ) 
Ch.4 Summary

Product-of-Sums (POS) Form

( A +B )( B+C +D )( A +C )
Ch.4 Summary

Standard POS

( A + B̄+C )( A +B+ D̄ )
↓
(A+ B+C+ D)(A+ B +C + D)
(A+ B +C + D)(A+ B +C + D)
Ch.4 Summary

Binary Representation

POS expression is equal to 0 only if one or more of the

sum terms in the expression is equal to 0

A+ B+ C + D →0+ 0+0 +0

A+ B̄+ C̄+ D →0+ 1̄+ 1̄+ 0

Ā+ B̄+ C̄+ D̄ →1̄+ 1̄+ 1̄+ 1̄
Ch.4 Summary

POS to Truth Table

Ch.4 Summary

SOP to Truth Table

Ch.4 Summary

Karnaugh Map

Karnough map provides a systematic method for

simplifying Boolean expressions.
Karnough map is similar to a truth table.
Ch.4 Summary

4-Variable Karnaugh Map

Ch.4 Summary

4-Variable Karnaugh Map

Ch.4 Summary

Mapping a Standard SOP

Ch.4 Summary

Mapping a Standard SOP

A B C  A B C  AB C  ABC
Ch.4 Summary

Mapping from Truth Table

Ch.4 Summary

Mapping a SOP

A  AB  ABC
Ch.4 Summary

Mapping a SOP
B C  A B  AB C  A B C D  A B C D  A B CD
Ch.4 Summary

Karnough Map Simplification

1. Group must contain 1, 2, 4, 8, 16 cells

2. Each cell in a group must be adjacent to each other
3. Always include the largest possible number of 1s
Ch.4 Summary

Karnough Map Simplification

Ch.4 Summary

Karnough Map Simplification

Ch.4 Summary

Karnough Map Example

A B̄ C+ Ā BC + Ā B̄C + Ā B̄ C̄ + A B̄ C̄
↓
B̄+ Ā C
Ch.4 Summary

Karnough Map Example

B C D  A BC D  ABC D  A B CD  AB CD
 A B CD  A BCD  ABCD  AB CD

D  BC
Ch.4 Summary

Don’t Care Terms

Ch.4 Summary

7-Segment Display

a  A B C D  A B CD  A B CD  A BC D
 A BCD  A BCD  AB C D  AB C D
Ch.4 Summary

7-Segment Display
a  A B C D  A B CD  A B CD  A BC D
 A BCD  A BCD  AB C D  AB C D
Ch.4 Summary

Mapping a Standard POS

Ch.4 Summary

Mapping a Standard POS

(A  B C  D)(A  BC  D)(A BC  D)
(A  B C  D)(A BC  D)
Ch.4 Summary

Simplification of POS
(A+ B +C)(A+ B +C )(A+ B +C)
(A+ B +C)(A + B +C)
Ch.4 Summary

Simplification of POS
(B + C + D)(A + B + C +D)(A + B + C + D )
(A + B + C + D)(A + B + C + D)
Ch.4 Summary

Convert between SOP and POS

(A + B + C + D)(A+ B+C + D)(A+ B + C + D )
(A + B + C + D )(A + B + C + D )(A + B + C + D)
Ch.4 Summary

Convert between SOP and POS

(A + B + C + D)(A+ B+C + D)(A+ B + C + D )
(A + B + C + D )(A + B + C + D )(A + B + C + D)
Ch.4 Summary

Convert between SOP and POS

(A + B + C + D)(A+ B+C + D)(A+ B + C + D )
(A + B + C + D )(A + B + C + D )(A + B + C + D)
Ch.4 Summary

Quine-McCluskey Method
Ch.4 Summary

Quine-McCluskey Method
Ch.4 Summary

Quine-McCluskey Method
Ch.4 Summary

Quine-McCluskey Method
Ch.4 Summary

Quine-McCluskey Method
Ch.4 Summary

7-Segment Display
Ch.4 Summary

7-Segment Display

1. Display the type of Vitamin (A, b, C, d, E)

2. F is not used as an Input
Ch.4 Summary

7-Segment Display