Rational Mathematics

by G. P. Jelliss

Boolean Algebras

A Boolean algebra is a terminate distributive lattice.

A complement in a terminate lattice is an operator * that determines for an element x an element x*, such that x n x* = o and x u x* = i.

Theorem: In a Boolean algebra every element x has unique complement. Proof: Suppose there were two complements x* and x' then x n x* = x n x' (since both are equal to o) and x u x* = x u x' (since both are equal to i) but in a distributive lattice these equalities imply x* = x'.

Theorem: For any x we have x** = x. And o* = i, i* = o. And x = y if and only if x* = y*. Proof: These follow from the symmetry of the definition of complement, and from the properties of o and i that; o n i = o, o u i = i. And the uniqueness of the complement.

Theorem (DeMorgan's Laws): In a Boolean algebra (x n y)* = x* u y* and (x u y)* = x* n y*. Proof: (x n y) u (x* u y*) = (x u x* u y*) n (y u x* u y*) = (i u y*) n (i u x*) = i n i = i and (x n y) n (x* u y*) = (x n y n x*) u (x n y n y*) = (o n y) u (o n x) = o u o = o. This proves x n y and x* u y* are complements. The proof for x u y and x* n y* follows by duality.

Theorem: x =< y if and only if x* >= y*. Proof: by De Morgan's laws: x =< y means x u y = y means (x u y)* = y* means x* n y* = y* means x* >= y*.

Important examples of Boolean algebras are provided by the algebras of all the subsets of a given set.