** Previous:**
A proof of Boole's Expansion Theorem

**Next:** Clones

**Up:** Supplementary Text

# A proof of Boole's Elimination Theorem

### [Theorem 1.4.7. of LMCS]

This theorem is stated on page 24 of **LMCS**.
Boole's proofs, as explained in the historical remarks,
were pretty `wild'. Here is a modern version.

**Theorem ** [Elimination Theorem]
The most general equation that follows from
is obtained by setting

or, more briefly,

where ranges over sequences of 1's and 0's.

**Proof.**
First we show , for the stated choice of *F*.
By expanding *E* about (see Problem 4.4 on page 25)
we have

where . Then from
follows

and thus

Taking the union of these two gives

and thus

Now repeat the above steps, except this time expand about ,
using the last equation which has the
form , to obtain

where . Continuing one arrives at the desired
conclusion that , as defined above, is 0.

For the converse suppose follows from
. Let be any
-constituent of *H*. Then for any
-constituent
we have is an
-constituent
of *H*. But then, by Theorem 4.5, *LK* must be an
-constituent
of *E* as follows from .
Then has *K* as a -constituent,
i.e., .
So *K* is a -constituent of *F* as *F* is
defined to be the intersection over the *L*'s of
the 's.

So every -constituent of *H* is also
a -constituent of *F*. This means,
by Theorem 4.5, that
follows from , so
is a more general conclusion than
.

** Previous:**
A proof of Boole's Expansion Theorem

**Next:** Clones

**Up:** Supplementary Text

*Stan Burris *

Fri Jan 31 17:43:51 EST 1997