** 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