Previous:
Feasible Computations
Next:
A proof of Boole's Elimination Theorem
Up: Supplementary Text
A proof of Boole's Expansion Theorem
[Theorem 1.4.3 of LMCS]
Given classes
we say K
is an
-constituent
if it is a constituent for the classes
.
Boole used the following theorem to
expand
a given expression
into its constituents.
It says basically that
F is a union of
-constituents, and a given
-constituent
K is a constituent of this expansion of F if and
only if
, where
is the unique sequence
of 1's and 0's that make
. The following gives the
for the constituents belonging to the three classes A,B,C:
Note that if K,L are both
constituents then
Theorem [Expansion Theorem]
Let
be given. Then
or, more briefly,
where K ranges over the
-constituents.
Proof
By using the fundamental identities on page 11 one sees
that it is possible to express F as a union of constituents.
So we write
where each constant
is either 0 or 1.
We can write this more briefly as follows (using the fact that there
are
constituents for n variables)
where the
are the various
-constituents.
Now one observes that for
being the unique sequence of 1's and 0's
that gives
, i.e.,
, we have
as desired.
Previous:
Feasible Computations
Next: A proof of Boole's Elimination Theorem
Up: Supplementary Text
Stan Burris
Fri Jan 31 17:59:12 EST 1997