chap 4

Chapter 4
Boolean Algebra and

Logic Simplification
Prepared by
MIR MUNTASIR HOSSAIN
Lecturer, EEE
Northern University Bangladesh
Chapter Outline
 Boolean Operations and Expressions
 Laws of Boolean Algebra
 Rules of Boolean Algebra
 DeMorgan’s Theorems
 Logic Simplification Using Boolean Algebra
 Standard Forms of Boolean Expressions
 The Karnaugh Map
 “Don’t Care” Conditions
2
Mir Muntasir Hossain
Boolean Operations and Expressions
 Boolean algebra is the mathematics of digital logic.
 A variable is a symbol used to represent an action, a condition, or data. Any
single variable can have only a 1 or a 0 value.
 The complement is the inverse of a variable and is indicated by a bar over the
variable (overbar). For example, the complement of the variable A is A. If A =
1, then A = 0. If A = 0, then A = 1.
3
Boolean Addition:
Boolean addition is equivalent to the OR operation.
4
Boolean Multiplication
Boolean multiplication is equivalent to the AND operation.
5
Laws of Boolean Algebra
Commutative Laws:
 The commutative law of addition for two variables is written as A + B = B + A
 The commutative law of multiplication for two variables is AB = BA
Associative Laws:
 The associative law of addition is written as follows for three variables:
A + (B + C) = (A + B) + C
6
 The associative law of multiplication is written as follows for three variables:
A(BC) = (AB)C
Distributive Law:
The distributive law is written for three variables as follows:
A(B + C) = AB + AC
7
Rules of Boolean Algebra
8
DeMorgan’s Theorems
 DeMorgan’s first theorem is stated as follows:
The complement of a product of variables is equal to the sum of the
complements of the variables.
The formula for expressing this theorem for two variables is
𝐗𝐘 = 𝐗+𝐘
9
 DeMorgan’s second theorem is stated as follows:
The complement of a sum of variables is equal to the product of the
complements of the variables.
The formula for expressing this theorem for two variables is
𝐗 + 𝐘 =𝐗 𝐘
10
11
12
13
14
15
Logic Simplification Using Boolean Algebra
16
17
18
19
20
21
22
Standard Forms of Boolean Expressions
 All Boolean expressions can be converted into either of two standard forms:
the sum-of-products form or the product-of-sums form.
 Standardization makes the evaluation, simplification, and implementation of
Boolean expressions much more systematic and easier.
 When two or more product terms are summed by Boolean addition, the
resulting expression is a sum-of-products (SOP). Example: AB + ABC + CD
 When two or more sum terms are multiplied, the resulting expression is a
product-of-sums (POS). Example: (A + B + C)(C + D + E)(B + C + D)
23
The Standard SOP Form
A standard SOP expression is one in which all the variables in the domain appear
in each product term in the expression. For example:
Converting product terms to standard SOP

Step 1: Multiply each nonstandard product term by a term made up of the sum
of a missing variable and its complement. This results in two product terms. As
you know, you can multiply anything by 1 without changing its value.
Step 2: Repeat Step 1 until all resulting product terms contain all variables in the
domain in either complemented or uncomplemented form. In converting a
product term to standard form, the number of product terms is doubled for each
missing variable.
24
25
The Standard POS Form
A standard POS expression is one in which all the variables in the domain appear
in each sum term in the expression. For example,
Converting a sum term to standard POS

Step 1: Add to each nonstandard product term a term made up of the product of
the missing variable and its complement. This results in two sum terms. As you
know, you can add 0 to anything without changing its value.
Step 2: Apply rule 12: A + BC = (A + B)(A + C)
Step 3: Repeat Step 1 until all resulting sum terms contain all variables in the
domain in either complemented or uncomplemented form.
26
27
The Karnaugh Map
 A Karnaugh map provides a systematic method for simplifying Boolean expressions and, if
properly used, will produce the simplest SOP or POS expression possible, known as the
minimum expression.
 A Karnaugh map is similar to a truth table because it presents all of the possible values of
input variables and the resulting output for each value. Instead of being organized into
columns and rows like a truth table, the Karnaugh map is an array of cells in which each cell
represents a binary value of the input variables.
The 4-Variable Karnaugh Map
28
Mapping a Standard SOP Expression
29
30
Karnaugh Map Simplification of SOP Expressions
The process that results in an expression containing the fewest possible terms with the
fewest possible variables is called minimization. After an SOP expression has been
mapped, a minimum SOP expression is obtained by grouping the 1s and determining the
minimum SOP expression from the map.
Grouping the 1s
The goal is to maximize the size of the groups and to minimize
the number of groups.
1. A group must contain either 1, 2, 4, 8, or 16 cells, which are all powers of two. In the
case of a 4-variable map, 24 = 16 cells is the maximum group.
2. 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.
3. Always include the largest possible number of 1s in a group in accordance with rule
1.
4. 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
noncommon 1s.
31
32
Determining the minimum SOP expression from the map
For a 4-variable map:
(1) A 1-cell group yields a 4-variable product term
(4) An 8-cell group yields a 1-variable term
(5) A 16-cell group yields a value of 1 for the expression
33
34
35
36
“Don’t Care” Conditions
 Sometimes a situation arises in which some input variable combinations are not
allowed. For example, in the BCD code covered, there are six invalid
combinations: 1010, 1011, 1100, 1101, 1110, and 1111. Since these unallowed
states will never occur in an application involving the BCD code, they can be
treated as “don’t care” terms with respect to their effect on the output. That is,
for these “don’t care” terms either a 1 or a 0 may be assigned to the output; it
really does not matter since they will never occur.
 The “don’t care” terms can be used to advantage on the Karnaugh map.
 For each “don’t care” term, an X is placed in the cell. When grouping the 1s, the
Xs can be treated as 1s to make a larger grouping or as 0s if they cannot be used
to advantage. The larger a group, the simpler the resulting term will be.
37
38
39
40
Reference Book
Digital Fundamentals, 11th Edition
Thomas L. Floyd
©2015 |Pearson |
41

chap 4

Uploaded by

Copyright:

Available Formats

chap 4

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

chap 4

Uploaded by

Copyright:

Available Formats

Chapter 4

Boolean Algebra and

 The commutative law of multiplication for two variables is AB = BA

Converting product terms to standard SOP

Converting a sum term to standard POS

You might also like