ENE4146 Logic design
Lec.3 - Boolean Algebra and Logic Simplification
Dr. Ahmed Alwakeel
1
Academic year: Fall 2023/2024
Agenda
1. Boolean Operations and Expressions
2. Laws and Rules of Boolean Algebra
3. DeMorgan’s Theorems
4. Boolean Analysis of Logic Circuits
5. Logic Simplification Using Boolean Algebra
6. Standard Forms of Boolean Expressions
7. Boolean Expressions and Truth Tables
8. The Karnaugh Map
9. Karnaugh Map SOP Minimization
10. Karnaugh Map POS Minimization 2
Introduction
• This chapter covers the laws, rules, and theorems of
Boolean algebra and their application to digital circuits.
• You will learn how to define a given circuit with a
Boolean expression and then evaluate its operation.
• You will also learn how to simplify logic circuits using the
methods of Boolean algebra and Karnaugh maps.
3
1. Boolean Operations and Expressions
• Boolean algebra is the mathematics of digital logic. A basic
knowledge of Boolean algebra is indispensable to the study and
analysis of logic circuits.
• Variable, complement, and literal are terms used in Boolean
algebra.
– 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).
– A literal is a variable or the complement of a variable.
4
1. Boolean Operations and Expressions
Boolean Addition
• Boolean addition is equivalent to the OR operation.
Example
Sol.
5
1. Boolean Operations and Expressions
Boolean Addition
• Boolean addition is equivalent to the OR operation.
Example
Sol.
6
1. Boolean Operations and Expressions
Boolean Multiplication
• Boolean multiplication is equivalent to the AND operation.
Example
Sol.
7
1. Boolean Operations and Expressions
Boolean Multiplication
• Boolean multiplication is equivalent to the AND operation.
Example
Sol.
8
1. Boolean Operations and Expressions
Example
Sol.
Example
Sol.
9
2. Laws and Rules of Boolean Algebra
• There are certain well-developed rules and laws that must be
followed in order to properly apply Boolean algebra.
Laws of Boolean Algebra
• The basic laws of Boolean algebra
– The commutative laws for addition and multiplication,
– The associative laws for addition and multiplication,
– The distributive law—are the same as in ordinary algebra.
• Each of the laws is illustrated with two or three variables, but the
number of variables is not limited to this.
10
2. Laws and Rules of Boolean Algebra
Commutative Laws
• The commutative law of addition for two variables is written as
• The commutative law of multiplication for two variables is
11
2. Laws and Rules of Boolean Algebra
Associative Laws
• The associative law of addition is written as follows for three
variables:
• The associative law of multiplication is written as follows for three
variables:
12
2. Laws and Rules of Boolean Algebra
Distributive Law
13
2. Laws and Rules of Boolean Algebra
Rules of Boolean Algebra
14
2. Laws and Rules of Boolean Algebra
15
2. Laws and Rules of Boolean Algebra
16
2. Laws and Rules of Boolean Algebra
17
2. Laws and Rules of Boolean Algebra
18
19
3. DeMorgan’s Theorems
• DeMorgan, a mathematician who knew Boole, proposed
two theorems that are an important part of Boolean
algebra.
• In practical terms, DeMorgan’s theorems provide
mathematical verification of the equivalency of the NAND
and negative-OR gates and the equivalency of the NOR
and negative-AND gate.
20
3. 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 complement of a sum of variables is equal to the product
of the complements of the variables
• DeMorgan’s theorems also apply to expressions in which there are
more than two variables.
21
3. DeMorgan’s Theorems
22
3. DeMorgan’s Theorems
23
3. DeMorgan’s Theorems
24
3. DeMorgan’s Theorems
Example
Sol.
Example
Sol.
25
3. DeMorgan’s Theorems
Example
Sol.
Example
Sol.
26
3. DeMorgan’s Theorems
• DeMorgan’s theorem can be applied and gives the following result:
27
3. DeMorgan’s Theorems
Applying DeMorgan’s Theorems
28
3. DeMorgan’s Theorems
Example
Sol.
29
3. DeMorgan’s Theorems
Example
Sol.
30
3. DeMorgan’s Theorems
Example
Sol.
31
3. DeMorgan’s Theorems
Example
Sol.
32
3. DeMorgan’s Theorems
Example
Sol.
33
3. DeMorgan’s Theorems
Example
Sol.
34
3. DeMorgan’s Theorems
Example
Sol.
35
3. DeMorgan’s Theorems
Example
Sol.
36
3. DeMorgan’s Theorems
Example
Sol.
37
3. DeMorgan’s Theorems
Example
Sol.
38
4. Boolean Analysis of Logic Circuits
• Boolean algebra provides a concise way to express the
operation of a logic circuit formed by a combination of
logic gates so that the output can be determined for various
combinations of input values.
– Determine the Boolean expression for a combination of gates.
– Evaluate the logic operation of a circuit from the Boolean
expression.
– Construct a truth table.
39
4. Boolean Analysis of Logic Circuits
Boolean Expression for a Logic Circuit
• A combinational logic circuit can be described by a Boolean
equation.
• To derive the Boolean expression for a given combinational logic
circuit, begin at the left-most inputs and work toward the final
output, writing the expression for each gate.
40
41
4. Boolean Analysis of Logic Circuits
Constructing a Truth Table for a Logic Circuit
• Once the Boolean expression for a given logic circuit has been
determined, a truth table that shows the output for all possible
values of the input variables can be developed.
42
4. Boolean Analysis of Logic Circuits
Evaluating the Expression
43
4. Boolean Analysis of Logic Circuits
Putting the Results in Truth Table Format
44
45
46
47
48
49
5. Logic Simplification Using Boolean Algebra
• A logic expression can be reduced to its simplest form or
changed to a more convenient form to implement the
expression most efficiently using Boolean algebra.
• The approach taken in this section is to use the basic laws,
rules, and theorems of Boolean algebra to manipulate and
simplify an expression.
50
5. Logic Simplification Using Boolean Algebra
Example
Sol.
51
5. Logic Simplification Using Boolean Algebra
Example
Sol.
52
5. Logic Simplification Using Boolean Algebra
53
5. Logic Simplification Using Boolean Algebra
Example
Sol.
54
5. Logic Simplification Using Boolean Algebra
Example
Sol.
55
5. Logic Simplification Using Boolean Algebra
Example
Sol.
56
5. Logic Simplification Using Boolean Algebra
Example
Sol.
57
5. Logic Simplification Using Boolean Algebra
Example
Sol.
58
5. Logic Simplification Using Boolean Algebra
Example
Sol.
59
6. Standard Forms of Boolean Expressions
• All Boolean expressions, regardless of their form, 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.
60
6. Standard Forms of Boolean Expressions
The Sum-of-Products (SOP) Form
• An SOP expression can be implemented with one OR gate and two
or more AND gates.
• Some examples are
• In an SOP expression, a single overbar cannot extend over more
than one variable; however, more than one variable in a term can
have an overbar. For example, an SOP expression can have the
term 𝐴𝐵𝐶 but not 𝐴𝐵𝐶. 61
6. Standard Forms of Boolean Expressions
The Sum-of-Products (SOP) Form
• Domain of a Boolean Expression
• AND/OR Implementation of an SOP
Expression
– Implementing an SOP expression simply requires
ORing the outputs of two or more AND gates.
– A product term is produced by an AND operation,
and the sum (addition) of two or more product
terms is produced by an OR operation. 62
6. Standard Forms of Boolean Expressions
The Sum-of-Products (SOP) Form
• NAND/NAND Implementation of an SOP Expression
– NAND gates can be used to implement an SOP expression.
– The NAND and negative-OR inversions cancel and the result is effectively
an AND/OR circuit.
• Conversion of a General Expression to SOP Form
– Any logic expression can be changed into SOP form by applying Boolean
algebra techniques. For example, 63
6. Standard Forms of Boolean Expressions
The Sum-of-Products (SOP) Form
• Example
• Sol.
64
6. Standard Forms of Boolean Expressions
The Sum-of-Products (SOP) Form
• Example
• Sol.
65
6. Standard Forms of Boolean Expressions
The Standard SOP Form
66
6. Standard Forms of Boolean Expressions
Converting Product Terms to Standard SOP
67
6. Standard Forms of Boolean Expressions
Example
Sol.
68
6. Standard Forms of Boolean Expressions
Example
Sol.
69
6. Standard Forms of Boolean Expressions
Binary Representation of a Standard Product Term
70
6. Standard Forms of Boolean Expressions
Example
Sol.
71
6. Standard Forms of Boolean Expressions
Example
Sol.
72
6. Standard Forms of Boolean Expressions
The Product-of-Sums (POS) Form
• When two or more sum terms are multiplied, the resulting
expression is a product-of-sums (POS).
• Some examples are
73
6. Standard Forms of Boolean Expressions
Implementation of a POS Expression
• Implementing a POS expression simply requires ANDing the
outputs of two or more OR gates.
• A sum term is produced by an OR operation, and the product of
two or more sum terms is produced by an AND operation.
74
6. Standard Forms of Boolean Expressions
The Standard POS Form
Converting a Sum Term to Standard POS
75
6. Standard Forms of Boolean Expressions
Example
Sol.
76
6. Standard Forms of Boolean Expressions
Example
Sol.
77
6. Standard Forms of Boolean Expressions
Binary Representation of a Standard Sum Term
78
6. Standard Forms of Boolean Expressions
Example
Sol.
79
6. Standard Forms of Boolean Expressions
Example
Sol.
80
6. Standard Forms of Boolean Expressions
Converting Standard SOP to Standard POS
• To convert from standard SOP to standard POS, the following
steps are taken:
– Step 1: Evaluate each product term in the SOP expression. That is,
determine the binary numbers that represent the product terms.
– Step 2: Determine all of the binary numbers not included in the evaluation
in Step 1.
– Step 3: Write the equivalent sum term for each binary number from Step 2
and express in POS form.
Using a similar procedure, you can go from POS to SOP.
81
6. Standard Forms of Boolean Expressions
Example
Sol.
82
6. Standard Forms of Boolean Expressions
Example
Sol.
83
84
Test
85
86
7. Boolean Expressions and Truth Tables
• All standard Boolean expressions can be easily converted
into truth table format using binary values for each term in
the expression.
• The truth table is a common way of presenting, in a
concise format, the logical operation of a circuit.
• Also, standard SOP or POS expressions can be determined
from a truth table.
87
7. Boolean Expressions and Truth Tables
Converting SOP Expressions to Truth Table Format
• SOP expression is equal to 1 only if at least one of the product
terms is equal to 1.
• A truth table is simply a list of the possible combinations of input
variable values and the corresponding output values (1 or 0).
– The first step in constructing a truth table is to list all possible
combinations of binary values of the variables in the expression.
– Next, convert the SOP expression to standard form if it is not already.
– Finally, place a 1 in the output column (X) for each binary value that
makes the standard SOP expression a 1 and place a 0 for all the remaining
88
binary values.
7. Boolean Expressions and Truth Tables
Example
Sol.
89
7. Boolean Expressions and Truth Tables
Example
Sol.
• The binary values that make the product
terms in the expressions equal to 1 are
• For each of these binary values, place a 1
in the output column as shown in the
table.
• For each of the remaining binary
combinations, place a 0 in the output
90
column.
7. Boolean Expressions and Truth Tables
Converting POS Expressions to Truth Table Format
• POS expression is equal to 0 only if at least one of the sum terms is
equal to 0.
– To construct a truth table from a POS expression, list all the possible
combinations of binary values of the variables just as was done for the SOP
expression.
– Next, convert the POS expression to standard form if it is not already.
– Finally, place a 0 in the output column (X) for each binary value that
makes the expression a 0 and place a 1 for all the remaining binary values.
91
7. Boolean Expressions and Truth Tables
Example
Sol.
92
7. Boolean Expressions and Truth Tables
Example
Sol.
• The binary values that make the
sum terms in the expression equal
to 0 are
• For each of these binary values,
93
place a 0 in the output column.
7. Boolean Expressions and Truth Tables
• Notice that the truth table in this example is the
same as the one in previous example.
• This means that the SOP expression in the previous
example and the POS expression in this example are
equivalent.
94
7. Boolean Expressions and Truth Tables
Determining Standard Expressions from a Truth Table
• To determine the standard SOP expression represented by a truth
table, list the binary values of the input variables for which the
output is 1.
• Convert each binary value to the corresponding product term by
replacing each 1 with the corresponding variable and each 0 with
the corresponding variable complement.
• For example,
95
7. Boolean Expressions and Truth Tables
Determining Standard Expressions from a Truth Table
• To determine the standard POS expression represented by a truth
table, list the binary values for which the output is 0.
• Convert each binary value to the corresponding sum term by
replacing each 1 with the corresponding variable complement and
each 0 with the corresponding variable.
• For example,
96
7. Boolean Expressions and Truth Tables
Example
Sol.
7. Boolean Expressions and Truth Tables
Example
Sol.
98
7. Boolean Expressions and Truth Tables
Example
Sol.
99
