Canonical Form
Once we know that all Boolean functions can be expressed as a sum of
product terms, it will be meaningful to introduce the concept of
canonical representation so that each function will have a unique
canonical form.
Let (S,+, 
, 
, 0,1) be a Boolean algebra and x, y and
z be any variables taking values in S, then
-
- literals
are individual variables or their complements, e.g. x,
x', y, y'
-
- product terms are expressions made of literals and the
binary operation ''''
although the symbol ''''
is optional, e.g. x, x', x y'z, x
y x'y z
-
- Boolean expression is a sum of product terms, e.g. x +
x' y (z + y')
-
- standard product term of an expression is a product in
which each variable appears in the product exactly once, e.g.
xy' is a standard product of xy' + x + x'y', but is not
a standard product of xy' + xyz because variable z is
missing from the product.
-
- a Boolean expression is canonical if it is a sum of
distinct standard product terms, e.g. xy + x'y' is canonical,
but xy + x'y + z is not canonical.
Two Boolean expressions are equivalent if they either
-
- have the same truth table, or
-
- can be transformed from one another through the use of the axioms
B1 -- B5 in the previous lecture, and their induced properties such as
the De Morgan's Laws, or
-
- have the same canonical form.
Example
- Show Boolean expressions x and xy + xy' are
equivalent.
- (a)
- By truth table
- (b)
- By properties of Boolean algebra
- (c)
- By canonical form
