# Boolean Algebra

A Boolean algebra is a set with two binary operations, and , that are commutative, associative and each distributes over the other, plus a unary operation . Also required are identity elements and U for the binary operations that satisfy , , and for all elements A in the set.

One interpretation of Boolean algebra is the collection of subsets of a fixed set X. We take , , , and U to be set union, set intersection, complementation, the empty set and the set X respectively. Equality here means the usual equality of sets.

Another interpretation is the calculus of propositions in symbolic logic. Here we take , , , and U to be disjunction, conjunction, negation, a fixed contradiction and a fixed tautology respectively. In this setting equality means logical equivalence.

It is not surprising then that we find analogous properties and rules appearing in these two areas. For example, the axiom of the distributive properties says that for sets we have while is a familiar equivalence in logic.

From the axioms above one can prove DeMorgan's Laws (in some axiom sets this is included as an axiom). The following table contains just a few rules that hold in a Boolean algebra, written in both set and logic notation. Rows 3 and 4 are DeMorgan's Laws. Note that the two versions of these rules are identical in structure, differing only in the choice of symbols.

Dan Rinne
Tue Aug 6 18:32:03 PDT 1996