Maggie
JohnsonΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ Handout
#9
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ CS103A
Boolean Algebra
Key Topics
α
Introduction
α
Boolean
Operators
α
Boolean
Expressions and Functions
α
Boolean
Identities
α
More on
Boolean Functions
α
Functional
Completeness
α
Simplification
of Boolean Functions
α
Karnaugh
Maps
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ
Introduction
The
circuits in computers have inputs (0 or 1) and produce outputs (0 or 1).Κ Circuits can be constructed using any basic
unit that has two different states, one for the 0 input/output, and one for the
1 input/output.Κ Typically, such units
are in the form of switches that can be either on or off.
In
1938, Claude Shannon showed how the rules of propositional logic could be used
to design circuits (in his Master's thesis at MIT).Κ These rules form the basis for Boolean algebra.Κ A Boolean
algebra is just the operations and rules used for working with the set {0,1}
where 0 and 1 can take on different meanings.Κ
Propositional Logic (which he have been studying) is a Boolean algebra.
Boolean Operators
The
main Boolean operators we will use are complement,
sum and product.Κ The complement of
an element (which always has a value of 0 or 1) is denoted with a single quote:
0' = 1 and 1' = 0.Κ The Boolean sum
denoted by + or OR has the following values:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1
+ 1 = 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1
+ 0 = 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0
+ 1 = 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0
+ 0 = 0
The
Boolean product denoted by π or by AND has the following values:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1
π 1 = 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1
π 0 = 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0
π 1 = 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0
π 0 = 0
Typically,
the π is dropped so x π y = xy.Κ The
rules of precedence for these operators are: complement, product, sum.Κ Therefore, the value of
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1 π 0 + (0 +
1)'Κ ΚΚΚΚΚΚΚΚΚΚ =Κ 1 π 0 + 1'
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ =Κ 1 π 0 + 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ =Κ 0 + 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ =Κ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ
Boolean Expressions and
Functions
x
is a Boolean variable if it can only
assume the value of either 0 or 1.Κ A Boolean function is a function whose
domain is a set of n-tuples of 0's and 1's, and whose range is an element of
the basic Boolean set {0,1}.Κ We always
display the values of a Boolean function in a truth table. A Boolean expression on the Boolean
variables {x1, x2, ..., xn} is an expression
using those variables and the operations of a boolean algebra.Κ
Every
Boolean expression defines a Boolean function.Κ
The values of this function are obtained by substituting 0 and 1 for the
variables in the expression.Κ For
example, we can define a Boolean expressionΚ
xy + xy' by a Boolean function F(x,y) = xy + xy'.Κ The values of this function are displayed in
the table below - all we did was substitute all possible values for the
variables.
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xΚΚΚΚΚΚΚΚΚ yΚΚΚΚΚΚΚΚΚ xyΚΚΚΚΚΚΚΚ xy'ΚΚΚΚΚΚΚ F(x,y)
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1
The
domain in this function is the 2-tuple which represents the values of x and
y.Κ The range is {0,1} in the last
column.Κ The n-tuple of a Boolean
function is just the possible values of the variables. Two Boolean expressions
are equivalent if they represent the
same function (i.e., have the same truth table).
Boolean Identities
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ IdentityΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ NameΚΚΚΚΚΚΚΚΚΚΚΚΚΚ
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ (x')' = xΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ Involution
Law
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x + x' = 1ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ Complementarity
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x π x' = 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x + x = xΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ Idempotent Laws
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x π x = x
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x + 0 = xΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ Identity Laws
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x π 1 = x
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x + 1 = 1ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ Dominance Laws
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x π 0 = 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x + y = y + xΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ Commutative Laws
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xy = yx
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x + (y + z) = (x + y) +
zΚΚΚΚΚΚΚΚΚΚΚ Associative Laws
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x(yz) = (xy)z
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x + yz = (x + y)(x + z)Κ Distributive Laws
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x(y + z) = xy + xzΚΚΚΚΚΚΚΚ
ΚΚΚΚΚΚΚΚΚΚΚ
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ (xy)' = x' + y'ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ DeMorgans Laws
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ (x + y)' = x'y'
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x + (xy) = xΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ Absorption Laws
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x(x + y) = x
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x + x'y = x + yΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ Redundancy Laws
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x(x' + y) = xy
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xy + x'z + yz = xy + x'z Consensus Laws
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ (x+y)(x'+z)(y+z) =
(x+y)(x'+z)
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ
There
is a duality principle which applies to all Boolean algebras.Κ In the definition of the identities above,
we always include two parts that represents the dual identities.Κ The only different is we interchange π and
+, and 0 and 1.Κ Any proven theorem is
automatically true for the dual of the theorem.
In
Boolean algebra, we can prove the identities using truth tables or using other
identities.Κ So, for example the
distributive law is proven true by the last two columns of the following table:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xΚΚΚΚΚΚΚΚΚ yΚΚΚΚΚΚΚΚΚ zΚΚΚΚΚΚΚΚΚΚ y+zΚΚΚΚΚΚ xyΚΚΚΚΚΚΚΚ xzΚΚΚΚΚΚΚΚ x(y+z)ΚΚΚΚΚΚΚΚΚΚΚΚΚ xy+xz
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0
A
proof of the absorption lawΚ x(x + y) =
xΚΚ using identities:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x(x + y) ΚΚΚΚΚΚΚΚΚΚ = (x + 0)(x + y)ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ identity law
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ =
x + 0 π yΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ distributive
law
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ =
x + y π 0ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ commutative
law
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ =
x + 0ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ dominance
law
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ =
xΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ identity
law
More on Boolean Functions
In
preparation for using all the above information to build circuits, we need to
be able to solve two basic problems:
ΚΚΚΚΚΚΚΚΚΚΚ 1) Given a table of values for a
Boolean function, how do we derive the
ΚΚΚΚΚΚΚΚΚΚΚ corresponding Boolean expression?
ΚΚΚΚΚΚΚΚΚΚΚ 2) Is there a smaller set of
operators that can be used to represent a Boolean
ΚΚΚΚΚΚΚΚΚΚΚ function?
First,
question 1.Κ Given the following table,
how do we figure out the corresponding Boolean expression?
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xΚΚΚΚΚΚΚΚΚ yΚΚΚΚΚΚΚΚΚ zΚΚΚΚΚΚΚΚΚΚ FΚΚΚΚΚΚΚΚΚ G
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0
Notice
that the only time that F is 1 is when x = z = 1 and y = 0.Κ This translates to xy'z meaning that the
expression xy'z has the value 1 if and only if x = y' = z = 1.Κ G is 1 in two cases: x = y = 1 and z = 0,
and x = z = 0 and y = 1.Κ When we have
to deal with two or more cases, we represent the sum of the two products:Κ xyz' + x'yz'.Κ This is the Boolean expression for G.
This
illustrates a basic method for constructing an expression from the values of a
Boolean function.Κ A minterm of the Boolean variables x1, x2,
..., xn is a Boolean product y1y2...yn
where yi = xi or yi = xi'.Κ A minterm has a value of 1 if and only if
all the values of its variables are 1.Κ
So, if x = y = 1 and z = 0 then xyz' is the minterm that equals 1.
By
taking Boolean sums of minterms, we can build up a Boolean expression that
represents the values of a function represented by a table.Κ The minterms in this sum correspond to those
combinations of the values for which the function has a value of 1.Κ This Boolean sum is sometimes called a sum of products expansion or disjunctive normal form.Κ
There
is an dual entity called a maxterm
which is a product of sums expansion
(conjunctive normal form).Κ The table below shows the duality:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 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'yz'ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x+y'+z
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ x'yzΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x+y'+z'
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ xy'z'ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x'+y+z
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ xy'zΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x'+y+z'
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ xyz'ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x'+y'+z
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ xyzΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x'+y'+z'
For
the following Boolean functionΚ F(x,y,z)
= (x+z) y
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xΚΚΚΚΚΚΚΚΚ yΚΚΚΚΚΚΚΚΚ zΚΚΚΚΚΚΚΚΚΚ x+zΚΚΚΚΚΚ (x+z)
y
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1
xyz
+ xyz' + x'yz is the minterm expression;
(x+y+z)(x+y+z')(x+y'+z)(x'+y+z)(x'+y+z') is the maxterm expression.Κ Every Boolean function has both a minterm
and maxterm expansion.
Functional Completeness
The
other question posed in the previous section was: Do we need all three
operators to express Boolean functions?Κ
As shown above, it's easy with {' + π} - since every Boolean function
can be expressed with these three operators, we say the set is functionally complete.Κ Is there a smaller set of functionally
complete operators?Κ There is a smaller
set if one of the three operators can be expressed in terms of the other two.Κ For example:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x
+ y = (x'y')'
which
means we can get rid of the + operatorΚ
(this is an application of DeMorgan's Law).Κ So, the set of {' π} is functionally complete.Κ In a similar way we can eliminate Boolean
products:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xy
= (x' + y')'
Is
the set {+ π} functionally complete?Κ
There is no way to represent the Boolean function F(x) = x' using these
two operators, so this set is not functionally complete.Κ
Finally,
is there a set of one operator that is functionally complete?Κ Only if we define a new operator.Κ We could define a NAND operator "|" as follows:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xΚΚΚΚΚΚΚΚΚ yΚΚΚΚΚΚΚΚΚ x
| y
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0
This
set is functionally complete.Κ To prove
this, we know that the set {π '} is functionally complete so all we have to do
is show that these two operators can be expressed using |:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ x'
= x | x
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xy
= (x | y) | (x | y)
A
similar operator that is functionally complete is the NOR operator: ?
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xΚΚΚΚΚΚΚΚΚ yΚΚΚΚΚΚΚΚΚ x
? y
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0
Simplification
of Boolean Functions
We
know that any Boolean function can be built from ANDs, ORs, and NOTs using
minterm expansion.Κ However, a
practicing computer engineer will very rarely be satisfied with a minterm
expansion, because as a rule, it requires more gates than necessary. The laws
and identities of Boolean algebra will almost always allow us to simplify a
minterm expansion. For example, the minterm expansion for a Boolean function f
of three variables might be represented as follows (taking the values directly
from the truth table):
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ f = x'y'z' +
x'y'z + x'yz' + x'yz + xyz' + xyz
This
would require a circuit with maximum gates: 12 ANDs, 5 ORs and 9 NOTs.Κ Using the identities of Boolean algebra,
this minterm expansion can be simplified considerably:
ΚΚΚΚΚΚΚΚΚΚΚ f ΚΚΚΚΚΚΚΚΚ =
x'y'z' + x'y'z + x'yz' + x'yz + xyz' + xyz
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ = x'y'(z' + z) + x'y(z'
+ z) + xy(z' + z)ΚΚΚ distributive law
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ = x'y' + x'y + xyΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ complementarity
& identity
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ = x'(y' + y) + xyΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ distributive
law
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ = x' + xyΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ complementarity
& identity
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ = x' + yΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ redundancy
So,
that big long minterm reduces down to x' + y which can be built with 1 OR and 1
NOT.Κ This is an important point, but
reducing minterms can require a lot of luck knowing which identities to apply
when.Κ Therefore, we will look at a very
simple technique that usually leads to a significant simplification of minterms.Κ It won't always produce the simplest form,
but it's close enough for most engineers considering the difficulty of the
alternative method.
Karnaugh Maps
Karnaugh maps were invented by Maurice Karnaugh, a
telecommunications engineer.Κ He
developed them at Bell Labs in 1953 while studying the application of digital
logic to the design of telephone circuits.Κ
This method is typically used on Boolean functions of two, three or four
variables - past that, it gets quite cumbersome and other techniques are frequently
used.
A
Karnaugh map is a 2-dim representation of the truth table for a Boolean
function.Κ For example:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ xΚΚΚΚΚΚΚΚΚ yΚΚΚΚΚΚΚΚΚ zΚΚΚΚΚΚΚΚΚΚ f(x,y,z)
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 0ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ 1ΚΚΚΚΚΚΚΚΚ
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 
Each
of the eight cells in the map corresponds toΚ
one of the eight possible combinations of x, y, & z.Κ The templates for 2 and 4 variable Karnaugh
maps are given below.
ΚΚΚΚΚΚΚΚΚΚΚ 
Once
we have placed the 1's in the map, there is a simple procedure that we
apply.Κ Before doing that though, it is
necessary to understand the basis for the procedure.Κ The reason Karnaugh maps are useful is because certain simple
Boolean functions have simple Karnaugh maps.Κ
These simple functions are called product
functions;Κ they are products of
some or all of the variables and their
complements.Κ For example, x1,
x2'x4 and xyz are all product functions but x1
+ x2' and xy + zw are not.
Take
the product function f(x,y,z) = xz.Κ
This function accepts two inputs 101 and 111.Κ Its Karnaugh map:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 
Notice
that the 1's lie in a 1x2Κ rectangular
block.Κ Another example is g(x,y,z) =
y'.Κ This function accepts
000,001,100,101 (since for all the other possibilities y = 1 and therefore y' =
0).Κ Its Karnaugh map:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 
The
minterms for this one lie in a 2x2 rectangular block.Κ It turns out that every product function has a Karnaugh map whose
minterms are confined to a block whose sides are 1, 2 or 4 cells long.Κ Thus, it becomes important to recognize what
product function is represented by a particular Karnaugh map.
To
do this, first write down the truth set (the set of combinations with a value
of 1 from the map).Κ For example:
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 
The
truth set is {011, 111}.Κ Next, we
analyze the values of the truth set.Κ If
the variables are x, y, and z, we notice that x can be 0 or 1; while y and z can
be only 1.Κ We characterize this
analysis as follows: {*11} where the "*" is a wildcard.Κ If the unknown product function involved x,
it would only accept inputs for which x assumed some particular value.Κ Since x can be either 0 or 1, we conclude
that x is not involved.Κ y, on the other
hand, must be involved since y = 1 for all inputs.Κ So y must be a term (not y'); the same is true for z.Κ The product function is yz.
Just
for practice, what are the product functions associated with the following Karnaugh
maps?
1)
truth set: {011, 010, 111, 110} = {*1*}.Κ
The product function never includes wildcard variables; the function is:
y.
2)
truth set: {010} so the function is x'yz'.
3)
truth set: {000, 100, 010, 110} = {**0} = z'.Κ
Notice that the rectangular block wraps around.
Finally,
try some 2 and 4 variable maps:
ΚΚΚΚΚΚΚΚΚΚΚ 
1)
truth set = {00, 10} = {*0} = y'
2)
(variables are wxyz): truth set = {0001, 0011, 1001, 1011} = {*0*1} =Κ x'z.
The
reason this is all so important is any Boolean function with the same Karnaugh
map as, for example, the ones above, can be represented by the same
expression.Κ Another expression with the
same Karnaugh map as the two-variable one above: x'y' + xy' + x'yxy; therefore,
we can represent this as y' and build a circuit as such.
Unfortunately,
not all expressions work out to be equivalent to product function Karnaugh
maps. The first example we looked at did not break down into a 1, 2, or 4 cell
rectangular block.
ΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚΚ 
We
can handle these too by decomposing the blocks into a union of two product
blocks, one representing the varialbe x'Κ
(the ones across the top indicate a 0 value for x) and one representing
y (the two ones on the bottom indicate a 1 value for y).Κ The function is x' + y, which is exactly the
conclusion we came to earlier.Κ All we
are doing is ORing the two product functions together.Κ We did not bother to show the truth sets for
these two blocks ({000, 001, 011, 010} = {0**} = x') - you will reach the same
conclusion.
This
technique can be applied to any Boolean function.Κ The idea is to cover the terms using as few product blocks as
possible.ΚΚ Then, write the function as
a sum of these product blocks.Κ It's
important that the blocks are as large as possible or you may not end up with
the simplest expression.Κ For example,
in the map above, we could have used three blocks: one horizantal for the first
two ones in the top row, and then two vertical blocks.Κ This would give the expression: x'y' + yz +
yz'.Κ This is equivalent, but inferior.
What
if you block off the first two ones in the first row and then the four ones
across the two rows?Κ The expression is:
x'y' + y; again it's equivalent but not as simple as the first.Κ (An application of the redundancy law will
simplify this further).Κ It's important
to carefully pick the blocks or you may not end up with the simplest
expression.
The
product blocks that make up a representation for an expression are called implicants.Κ x'y' , yz and yz' are all implicants the expressionΚ x'y' + yz + yz'.Κ Implicants that cover as many cells of the map as possible are
called prime implicants.Κ The rule of the game, therefore, is cover the minterms with as few prime
implicants as possible.
As
additional practice, simplify the following functions represented by Karnaugh
maps:
ΚΚΚΚΚΚΚΚΚΚΚ 
1)
x'z' + yz'
2)
w'x + xyz' + wx'z x'y'z'
Notice
that you can overlap the blocks if ncessary:
ΚΚΚΚΚΚΚΚΚΚΚ 
Karnaugh
maps are certainly easier to deal with than using identities to simpify Boolean
functions.Κ However, the trick is
finding the right set of blocks to get the simplest expression.Κ This takes practice; there is no simple rule
that tells how it should be done.
Bibliography and Historical
Notes
*
The study of deduction in logic dates back to Aristotle.Κ Boole developed the algebra of propositions,
and it is from this work that Boolean algebra comes.
G.
Boole, An Investigation of the Laws of
Thought, 1854, reprinted by New York: Dover ΚΚ Press, 1958.
*
For more on Boolean algebra:
S.
Epp, Discrete Mathematics with
Applications, Belmont, CA: Wadsworth, 1990.
R.
Grimaldi, Discrete and Combinatorial
Mathematics, 2nd ed., Reading, MA: Addison-Wesley, 1989.
F.E.
Hohn, Applied Boolean Algebra, 2nd ed.,
New York: Macmillan, 1966.
Z.
Kohavi, Switching and Finite Automata
Theory, 2nd ed., New York: McGraw-Hill, 1978.
K.
Rosen, Discrete Mathematics and its
Applications 4nd Ed., New York: McGraw-Hill, ΚΚΚ 1999.
*
Karnaugh maps were introduced in:
M.
Karnaugh, "The Map Method for Synthesis of Combinatorial Logic
Circuits," ΚΚΚΚΚΚΚΚΚ Transactions of the AIEE, 72 (1953),
593-599.