| |
|
|
|
|
|
| |
|
|
| |
 |
Algebraic Manipulation
|
| |
|
|
| |
|
|
| |
 |
Minterms and Maxterms
|
| |
|
|
|
|
Any boolean expression may be expressed in terms of either minterms or maxterms. To do this we must first define the concept of a literal. A literal is a single variable within a term which may or may not be complemented. For an expression with N variables, minterms and maxterms are defined as follows : |
|
|
- A minterm is the product of N distinct literals where each literal occurs exactly once.
- A maxterm is the sum of N distinct literals where each literal occurs exactly once.
|
|
|
For a two-variable expression, the minterms and maxterms are as follows |
| |
|
|
|
|
|
X
|
Y
|
Minterm
|
Maxterm
|
|
0
|
0
|
X'.Y'
|
X+Y
|
|
0
|
1
|
X'.Y
|
X+Y'
|
|
1
|
0
|
X.Y'
|
X'+Y
|
|
1
|
1
|
X.Y
|
X'+Y'
|
|
| |
|
|
|
|
For a three-variable expression, the minterms and maxterms are as follows |
| |
|
|
|
|
|
X
|
Y
|
Z
|
Minterm
|
Maxterm
|
|
0
|
0
|
0
|
X'.Y'.Z'
|
X+Y+Z
|
|
0
|
0
|
1
|
X'.Y'.Z
|
X+Y+Z'
|
|
0
|
1
|
0
|
X'.Y.Z'
|
X+Y'+Z
|
|
0
|
1
|
1
|
X'.Y.Z
|
X+Y'+Z'
|
|
1
|
0
|
0
|
X.Y'.Z'
|
X'+Y+Z
|
|
1
|
0
|
1
|
X.Y'.Z
|
X'+Y+Z'
|
|
1
|
1
|
0
|
X.Y.Z'
|
X'+Y'+Z
|
|
1
|
1
|
1
|
X.Y.Z
|
X'+Y'+Z'
|
|
| |
|
|
|
|
This allows us to represent expressions in either Sum of Products or Product of Sums forms |
| |
|
|
| |
 |
Sum Of Products (SOP)
|
| |
|
|
|
|
The Sum of Products form represents an expression as a sum of minterms. |
| |
|
|
|
|
F(X, Y, ...) = Sum (ak.mk) |
| |
|
|
|
|
where ak is 0 or 1 and mk is a minterm. |
| |
|
|
|
|
To derive the Sum of Products form from a truth table, OR together all of the minterms which give a value of 1. |
| |
|
|
| |
 |
Example - SOP
|
| |
|
|
|
|
Consider the truth table |
| |
|
|
|
|
|
X
|
Y
|
F
|
Minterm
|
|
0
|
0
|
0
|
X'.Y'
|
|
0
|
1
|
0
|
X'Y
|
|
1
|
0
|
1
|
X.Y'
|
|
1
|
1
|
1
|
X.Y
|
|
|
|
Here SOP is f(X.Y) = X.Y' + X.Y |
| |
|
|
| |
|
Product Of Sum (POS)
|
| |
|
|
|
|
The Product of Sums form represents an expression as a product of maxterms. |
| |
|
|
|
|
F(X, Y, .......) = Product (bk + Mk), where bk is 0 or 1 and Mk is a maxterm. |
| |
|
|
|
|
To derive the Product of Sums form from a truth table, AND together all of the maxterms which give a value of 0. |
| |
|
|
|
|
|
| |
|
|
| |
|
Example - POS
|
| |
|
|
|
|
Consider the truth table from the previous example. |
| |
|
|
|
|
|
X
|
Y
|
F
|
Maxterm
|
|
0
|
0
|
1
|
X+Y
|
|
0
|
1
|
0
|
X+Y'
|
|
1
|
0
|
1
|
X'+Y
|
|
1
|
1
|
1
|
X'+Y'
|
|
|
|
Here POS is F(X,Y) = (X+Y') |
| |
|
|
| |
|
Exercise
|
| |
|
|
|
|
Give the expression represented by the following truth table in both Sum of Products and Product of Sums forms. |
| |
|
|
|
|
|
X
|
Y
|
Z
|
F(X,Y,X)
|
|
0
|
0
|
0
|
1
|
|
0
|
0
|
1
|
0
|
|
0
|
1
|
0
|
0
|
|
0
|
1
|
1
|
1
|
|
1
|
0
|
0
|
0
|
|
1
|
0
|
1
|
1
|
|
1
|
1
|
0
|
1
|
|
1
|
1
|
1
|
0
|
|
| |
|
|
| |
|
Conversion between POS and SOP
|
| |
|
|
|
|
Conversion between the two forms is done by application of DeMorgans Laws. |
| |
|
|
| |
|
Simplification
|
|
|
As with any other form of algebra you have encountered, simplification of expressions can be performed with Boolean algebra. |
| |
|
|
| |
|
Example
|
| |
|
|
|
|
Show that X.Y.Z' + X'.Y.Z' + Y.Z = Y |
| |
|
|
|
|
X.Y.Z' + X'.Y.Z' + Y.Z = Y.Z' + Y.Z = Y |
| |
|
|
| |
|
Example
|
| |
|
|
|
|
Show that (X.Y' + Z).(X + Y).Z = X.Z + Y.Z |
| |
|
|
|
|
(X.Y' + Z).(X + Y).Z |
|
|
= (X.Y' + Z.X + Y'.Z).Z |
|
|
= X.Y'Z + Z.X + Y'.Z |
|
|
= Z.(X.Y' + X + Y') |
|
|
= Z.(X+Y') |
| |
|
|
| |
|
|
| |
|
|
|
|
|
| |
|
|
