previous
Previous: Return to notes

Boolean Algebra

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

One interpretation of Boolean algebra is the collection of subsets of a fixed set X. We take tex2html_wrap_inline22 , tex2html_wrap_inline24 , tex2html_w
rap_inline26 , tex2html_wrap_inline28 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 tex2html_wrap_inline22 , tex2html_wrap_inline24 , tex2html_wrap_inline26 , tex2html_wrap_inline28 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 tex2html_wrap_inline66 while tex2html_wrap_inline68 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.

tabular10





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