Transcript Chapter4_TeacherRevisedAs2July2008

Chapter 4
Boolean Algebra and
Logic Simplification
By Taweesak Reungpeerakul
241-208 CH4
1
Contents







241-208 CH4
Boolean Operations & Expressions
Rules of Boolean Algebra
DeMorgan’s Theorems
Simplification Using Boolean Algebra
Standard Forms of Boolean Algebra
Karnaugh Map
Five-variable Karnaugh Map
2
4.1 Boolean Operations &
Expressions

241-208 CH4
Boolean Addition is
equivalent to the OR
operation.
0+0 = 0
0+1 = 1
1+0 = 1
1+1 = 1

Boolean multiplication
is equivalent to the
AND operation.
0·0 = 0
0·1 = 0
1·0 = 0
1·1 = 1
3
4.2 Laws&Rules of Boolean
Algebra
Laws (CAD)
Commutative, Associative, and Distributive
A+B = B+A
AB = BA
A+ (B+C) = (A+B)+C
A(BC) = (AB)C
A(B+C) = AB+AC
241-208 CH4
(C for addition)
(C for multiplication)
(A for addition)
(A for multiplication)
(distributive)
4
4.2 Laws&Rules of Boolean
Algebra (cont.)
1)
2)
3)
4)
5)
6)
7)
8)
9)
241-208 CH4
A+0=A 10) A·A=A
A+1=1 11) A·A=0
A·0=0 12) A=A
A·1=1
A+A=A Rules of Boolean Algebra
A+A=1
A+AB=A
A+AB=A+B
(A+B)(A+C)=A+BC
5
4.3 DeMorgan’s Theorems


The complement of a product of variables is equal to the
sum of the complements of the variables.
XY = X + Y
The complement of a sum of variables is equal to the
product of complements of the variables.
X + Y = X ·Y
241-208 CH4
6
Examples of DeMorgan’s
Theorems

Ex#1: (AB+C)(BC)

Ex# 2: AB + CDE
= (AB+C) +(BC)
= (AB) · (CDE)
= (AB)C +(B+C)
= (A+B) · (CD+E)
= (A+B)C + B+C
= (A+B) · (CD+E)
Question: (A+B)C D
Question: A+B+C+ DE
Ans: (A ·B)+C+D
Ans: A B C+D+E
241-208 CH4
7
4.4 Boolean Analysis of Logic Circuits
You should be able to:
241-208 CH4
•
Determine the Boolean expression for a
combination logic gates.
•
Evaluate the logic operation of a circuit
from the Boolean expression
•
Construct a truth table
8
4.4 Boolean Analysis of Logic Circuits
(cont.)
A
B
AB
AB+C
C
D
(AB+C)D
Cause 1 when D and (AB+C) = 1
If AB = 0, C = 1
If AB = 1, C = 0 or 1
AB = 1 when both A = B = 1
241-208 CH4
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
Truth Table
D
(AB+C)D
0
0
1
0
0
0
1
1
0
0
1
0
0
0
1
1
0
0
1
0
0
0
1
1
0
0
1
1
0
0
1
1
9
4.5 Simplification using Boolean
Algebra

EX#1: AB+A(B+C)+B(B+C)
Use distributive law A(B+C) = AB+AC
= AB+AB+AC+BB+BC
Use rule #5, A+A = A then A+A = A
= AB + AC + B + BC
Use distributive law A(B+C) = AB+AC
= AB+AC+B(1+C)
Use rule #2 (1+A) = 1
241-208 CH4
10
4.5 Simplification using Boolean
Algebra (cont.)
= AB+AC+B
Use commutative law A+B = B+A
= AB+B+AC
Use commutative law A+B = B+A, AB = BA
= B+BA+AC
Use distributive law A(B+C) = AB+AC
= B(1+A)+AC
Use rule #2 (1+A) = 1
= B+AC
241-208 CH4
Answer
11
4.5 Simplification using Boolean
Algebra (cont.)
Can u follow up this example by yourself ?
EX#2:
A B C+A B C+A B C+A B C+A B C

= B C+A B C+A B C+A B C
= B C+ B C+A B C
= BC+B(C+AC)
Use rule #11 A+AB = A+B
= BC+B(C+A)
= BC+B C+AB
241-208 CH4
Answer
How about trying more questions, for example :
Some questions in pp. 179 !!!!
12
4.6 Standard Forms of Boolean
Expressions

Sum-of-Products (SOP):
2 or more product terms are summed by Boolean addition
such as
AB+ABC+AC
Watch out ! each bar if any must denote on only a single
literal (variable) (in brief watch out the NAND), for example
AB+ABC+AC is not SOP
Ex# 1: convert (A+B)(C+D) into SOP form
apply distributive law, hence = AC+AD+BC+BD
241-208 CH4
13
4.6 Standard Forms of Boolean
Expressions (cont.)
Ex# 2:
(A + B) + C
= (A+B)C
DeMorgan’s
= (A+B)C
Distributive
= AC+BC
Domain is the set of literals (or variables) contained in the
Boolean expression !!
241-208 CH4
14
4.6 Standard Forms of Boolean
Expressions (cont.)

Standard SOP Form:
All variables in the domain appear in each product
term such as
ABC+ABC+ABC
Convert SOP to SSOP
Step 1: Consider domain of SOP
Step 2: Multiply each nonstandard term by
(L+L)
Step3 : Repeat step 2 until no nonstandard term left.
241-208 CH4
15
4.6 Standard Forms of Boolean
Expressions (cont.)
Ex# 1: AB+ABC  standard SOP
= AB(C+C)+ABC = ABC+ABC+ABC
Ex# 2: B+ABC
= B(A+A)+ABC = AB+AB+ABC
= AB(C+C)+AB(C+C)+ABC
= ABC+ABC+ABC+ABC+ABC
241-208 CH4
16
Standard Forms (cont.)

Product-of-Sum (POS):
2 or more sum terms are multiplied
such as (A+B)(A+B+C)

Standard POS:
all variables in the domain appear in
each sum term such as
(A+B+C)(A+B+C)
Watch out the NOR term !!
Ex# 1: (A+C)(A+B+C)
 standard POS
= (A+C+BB)(A+B+C)
=(A+B+C) (A+B+C) (A+B+C)
Question: (A+C)(A+B)  std. POS
Ans: (A+B+C) (A+B+C) (A+B+C)(A+B+C)
241-208 CH4
17
Std. SOP to std. POS
Example: ABC+ABC+ABC+ABC+ABC
101 011 100 001 000
3 variables
23 = 8 possible combinations
Remained terms: 111, 110, 010
Std. POS = (A+B+C)(A+B+C)(A+B+C)
241-208 CH4
18
4.7 Boolean Expressions and
Truth Tables
What u should know: Be able to convert SOP and POS expressions to truth tables
and vice versa !!
Convert SOP to truth table
FACT
SSOP is equal to 1 if at least one
of the product term is 1.
Step I : construct truth table for all
possible inputs.
Step II: convert SOP to SSOP
Step III: Place “1” in the output column
that makes the SSOP
expression a “1”
Step IV: Place “0” for all the remaining
apart from Step III
241-208 CH4
EX: ABC+ABC+ABC+ABC
000 010 101 110 out=1
A
B
C
Out
0
0
0
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0
19
4.7 Boolean Expressions and
Truth Tables (cont.)
Convert POS to truth table
FACT
SPOS is equal to 0 if at least one
of the sum term is 0.
Step I : construct truth table for all
possible inputs.
Step II: convert POS to SPOS
Step III: Place “0” in the output column
that makes the SPOS
expression a “0”
Step IV: Place “1” for all the remaining
apart from Step III
241-208 CH4
EX: (A+B+C)(A+B+C)(A+B+C)
100
010
011 out=0
A
B
C
Out
0
0
0
1
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
20
4.7 Boolean Expressions and
Truth Tables (cont.)
Convert truth table to SSOP
Step
Step
Step
Step
1:
2:
3:
4:
Consider only output “1”
Convert each binary value to the corresponding product term
Repeat step 1&2 to get other product terms
Write all product terms in a summation expression
Convert truth table to SPOS
Step 1: Consider only output “0”
Step 2: Convert each binary value to the corresponding sum term
(1-> complement literal and 0-> for literal)
Step 3: Repeat step 1&2 to get other sum terms
Step 4: Write all product terms in a product expression
241-208 CH4
Check this out: Example 4-20, pp. 187
21
4.8 The Karnaugh Map



The Karnaugh map is an array of cells in which each cell
represents a binary value of the input variables.
Can facilitate to produce the simplest SOP or POS expression
The number of cells is 2n, n is number of variables
C
AB
0
1
00
3 variables
so 8 cells
ABC
ABC
ABC
ABC
ABC
ABC
ABC
ABC
Each cell differs from an adjacent
cell by only one variable
241-208 CH4
Gray
code
01
11
10
The numbers are entered in gray code,
to force adjacent cells to be different
by only one variable.
22
4.8 The Karnaugh Map (cont.)
CC
AB
AB ABC
CC
ABC
AB
AB ABC
ABC ABC
AB
AB ABC
C 0
1
AB
00 ABC ABC
01 ABC ABC
ABC
11 ABC ABC
AB ABC
AB
ABC
ABC
10 ABC ABC
How to read !!
Full representation for 3 variables.
(in fact it is n-Dimension truth table)
Question : What about the map for 4 variables ?
241-208 CH4
23
4.9 Karnaugh Map SOP Minimization
Aim: You should be able to utilise K-Map to simplify Boolean expression to their
minimum form.
Convert SSOP to K-Map
What we know is each product term in SSOP relates to “1” in corresponding
truth table, but K-Map is, in deed, a form of n-dims truth table.
C 0
1
AB
Hence the way to convert
00
1
1
SSOP to K-map is similar
to the way to convert SSOP
to truth table !!
01
ABC+ABC+ABC+ABC
241-208 CH4
11
1
10
1
24
4.9 Karnaugh Map SOP Minimization
(cont.)
Convert non-standard SOP to K-Map
Assume that the domain of Boolean is {A,B,C} and the expression we consider
is A
convert A (non-SOP) to SSOP as follows:A = A(B+B)(C+C)
= (AB+AB)(C+C)
= ABC+ABC+ABC+ABC
Observe that A is related to all cells related to the
binary “1” of A
241-208 CH4
C 0
1
11
1
1
10
1
1
AB
00
01
25
4.9 Karnaugh Map SOP Minimization
(cont.)
How to minimize SOP expression ?

Grouping 1s
- Each group must contain 1,2,4,8,or 16 cells
- Each cell in a group must be adjacent to one or more cells in
that same group, but all cells in the group do not have to be
adjacent to each other.
- Always include the largest possible number of 1s in a group
- Each 1 on the map must be included in at least one group.
The 1s already in a group can be included in another group as
long as the overlapping groups include non-common 1s.
241-208 CH4
26
4.9 Karnaugh Map SOP Minimization
(cont.)
B changes
across this
boundary
C
AB
00
0
01
1
1
1
1
11
10
C changes
across this
boundary
1. Group the 1’s into two overlapping
groups as indicated.
2. Read each group by eliminating any
variable that changes across a
boundary.
3. The vertical group is read AC.
4. The horizontal group is read AB.
X = AC +AB
241-208 CH4
27
4.9 Karnaugh Map SOP Minimization
(cont.)
C changes across
outer boundary
CD
00
AB
00 1
01
11
10
1
B changes
01
1
1
11
1
1
10
1
1
B changes
C changes
X
241-208 CH4
1. Group the 1’s into two separate
groups as indicated.
2. Read each group by eliminating
any variable that changes across a
boundary.
3. The upper (yellow) group is read as
AD.
4. The lower (green) group is read as
AD.
X = AD +AD
28
4.9 Karnaugh Map SOP Minimization
(cont.)
ABC
A
BC 00
0
AC
01
1
BC 00 A B 01
A
0
1
1
1
BC
10
CD
1
1
1
11
BC
AB
00
1
AB
11
1
C
10
00
01
11
1
D
10
1
01
1
1
1
11
1
1
1
10
1
1
1
ABC
1
1
1
Some examples of grouping
241-208 CH4
29
4.9 Karnaugh Map SOP Minimization
(cont.)
Ex1: Map and minimize the following std. SOP expression on a
Karnaugh map: A B C+ABC+ABC+A B C
000 001 110 100
AB
BC 00
A
0
1
1
1
01
11
10
1
1
A
BC 00
0
1
1
1
01
11
10
1
1
AC
Answer: A B+AC
241-208 CH4
30
4.9 Karnaugh Map SOP Minimization
(cont.)
Ex2: Map and minimize the following SOP expression on a
Karnaugh map: A B +ABC+A B C
110 111 010 011
BC 00
11
10
0
1
1
1
1
1
A
01
A
B
BC 00
01
11
10
0
1
1
1
1
1
Answer: B
241-208 CH4
31
4.9 Karnaugh Map SOP Minimization
(cont.)
Mapping Directly from a Truth Table
A
0
0
0
0
1
1
1
1
241-208 CH4
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
Out
1
0
0
0
1
0
1
x
AB
00
C 0
1
1
01
11
1
10
1
x
Out = AB+BC
32
4.10 Karnaugh Map POS Minimization
Ex1: Map and minimize the following std. POS expression on a
Karnaugh map:
(A+B+C)(A+B+C)(A+B+C)(A+B+C)
000
001
111
110
A+B
A+C
BC 00
A
0
1
0
01
11
0
0
10
A
BC 00
0
0
1
0
01
11
0
0
10
0
A+B+C
Answer: (A+B)(A+C)(A+B+C)
241-208 CH4
33
4.10 Karnaugh Map POS Minimization
(cont.)
Ex2: Map and minimize the following POS expression on a
Karnaugh map:
(A+B)(A+B+C)(A+B+C)
A
000 001 010 011
BC 00
A
0
1
0
01
11
10
0
0
0
A
BC 00
0
0
01
11
0
0
10
0
1
Answer: A
241-208 CH4
34
4.10 Karnaugh Map POS Minimization
(cont.)
(B+C+D)(A+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D)
0000 1000 0010 0110
1011
CD
AB
00
1001
1010
(B+D)
00
01
11
0
10
(A+C+D)
0
0
01
(A+B)
11
10
0
0
0
0
Answer: (B+D)(A+B)(A+C+D)
241-208 CH4
35
Converting Between POS and SOP Using
Karnaugh Map
(B+C+D)(A+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D)
0000 1000 0010 0110
CD
AB
00
(B+D)
00
01
11
0
01
10
(A+C+D)
0
0
AD
BC
00
01
11
10
0
1
1
0
0
01
1
1
1
0
11
1
1
1
1
10
0
0
0
0
0
Min POS: (B+D)(A+B)(A+C+D)
241-208 CH4
CD
1010
0
(A+B)
0
1001
AB
00
11
10
1011
Min SOP: AB+BC+AD
AB
36
7-segment decoding Logic
Digit
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
241-208 CH4
D
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
C
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
A
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
a b c d e f g
1
0
1
1
0
1
1
1
1
1
x
x
x
x
x
x
1
1
1
1
1
0
0
1
1
1
x
x
x
x
x
x
1
1
0
1
1
1
1
1
1
1
x
x
x
x
x
x
1
0
1
1
0
1
1
0
1
1
x
x
x
x
x
x
1
0
1
0
0
0
1
0
1
0
x
x
x
x
x
x
1
0
0
0
1
1
1
0
1
1
x
x
x
x
x
x
0
0
1
1
1
1
1
0
1
1
x
x
x
x
x
x
7-segment
decoding logic
A
Binary coded B
decimal input C
D
a
b
c
d
e
f
g
7-segment display
a
f
e
g
d
b
c
37
Karnaugh Map Minimization of the
Segment Logic
SOP for segment a:
DC BA+DCBA+DCBA+ DCBA+DCBA+DCBA+DC BA+DCBA
BA
DC
00
CA
00
1
CA
01
D
01
11
10
1
1
1
1
1
11
x
x
x
x
10
1
1
x
x
B
Minimum SOP expression: D+B+CA+CA
241-208 CH4
38