Boolean Algebras

We now bring in a concept from outside Laws of Form, namely, the idea of a Boolean Algebra or logical field (the term originally used by Huntington). There are several ways, all mutually equivalent, of defining a Boolean Algebra. We choose to work with the following definition:

A Boolean Algebra B consists of a set K with a unary operation ', two binary operations ∧ and ∨, a unit 1 and a zero 0 obeying the following constraints:

It may or may not come as a surprise to the reader that CL-algebras and Boolean algebras are essentially the same thing. We will prove the following

Theorem: Every CL-algebra may be converted into a Boolean Algebra, and vice versa; and performing the two conversions in succession brings you back to where you started.

Proof: First, suppose we are given a CL-algebra. We show that it may be converted into a Boolean Algebra.

Let the operations ∧ and ∨ be defined as follows:

a ∧ b = ab
a ∨ b = ((a)(b)) ;

and let the unit and the zero be defined by

1 = _
   0 = O .

Commutativity is immediate; associativity follows from

(a ∧ b) ∧ c = abc
(a ∨ b) ∨ c = ( ( ((a)(b)) ) (c) ) = ((a)(b)(c)) .

The unit-property is immediate; for the zero-property

a ∨ 0 = ((a)(O)) = ((a)) = a .

For the first of the distributivity properties ('∧ distributive over ∨'):

a ∧ (b ∨ c) = a ((b)(c)) = ((ab)(ac)) = (a ∧ b) ∨ (a ∧ c)

by distribute (a known consequence of the three constraints, so true in all CL-algebras). As for '∨ distributive over ∧':

a ∨ (b ∧ c) = ((a)(bc)) = ( (a)( ((b))((c)) ) ) = ((a)(b)) ((a)(c)) = (a ∨ b) ∧ (a ∨ c)

(by distribute again). Finally:

a ∧ a' = a (a) = O = 0
a ∨ a' = ((a)((a))) = ((a)a) = _ = 1 ,

so the desired properties of complementation are proved. Thus every CL-algebra gives rise to a Boolean Algebra.

The reverse transformation is slightly more difficult. The first task is to show that the associativity and commutativity of the binary operation ∧ imply the existence of a general 'law of combination' (of any number of elements), with dissociativity and permutability, as required for a CL-algebra.

We may define the law of combination recursively, as follows:

{abc...mn} = {abc...m}∧n

together with the 'first step'

{a} = a.

More explicitly,

{abc...mn} = (...((a∧b)∧c)...∧m)∧n .

We show, first, that any 'subdivided combination' such as

{ {ab{cd}} {e{fg{hij}}} {kl{mn}} }

is equal to {abc...mn} as just defined.

We prove this by means of mathematical induction on the number of letters involved. Let P_N stand for the assertion that any subdivided combination of N letters is equal to the standard one. P₁ is definitely true, for there is no way of subdividing the combination; it remains to show that, when N>1, if P_M is true for all M less than N, then P_N is true.

Suppose the subdivided combination of N letters is

x = { {a..c} {d...f} ... {h...j} {k...mn} } .

By the induction hypothesis (P_M true for all M<N), each of the inner combinations may be further subdivided, without making any difference to its value; so WLOG (without loss of generality) we may assume that the subdivision takes the relatively 'shallow' form just given.

Again by the induction hypothesis, all the factors in the above expression except the last may be combined into one factor, so

x = { {abc...j}{k...mn} }
= { {a...j} ({k...m}∧n) }   (by the recursive definition of { })
= {a...j}∧({k...m}∧n)   (by the definition of { } when just two elements
are to be combined)
= ({a...j}∧{k...m}) ∧ n   (by the associative property of ∧)
= {a...jk...m} ∧ n   (by the induction hypothesis)
= {a...mn}   (by the recursive definition of { })

Our induction step is proved, therefore P_N is true for all N: no matter how a combination is subdivided, or broken into stages, the answer comes out the same.

It remains to prove permutability, that is, that

{ ... n ... } = {abc...mn},

no matter which letters are placed before n, and which after. Again we assume that permutability has already been established for smaller combinations. Then

{ ... n ... } = { {...} { n {...} } }   (by dissociativity)
= { {...} ( n∧{...} ) }   (by definition of { } for two elements)
= { {...} ( {...}∧n ) }   (by commutativity of ∧)
= { {...} {...n} }   (by definition of { })
= { {......} n}   (by dissociativity)
= { {abc...m} n}   (by permutability of smaller combinations)
= {abc...mn}    (by definition of { })

Thus our law of combination is both dissociative and permutable.

Digression: I became interested in the following question: given a set K with a binary operation ⋅ that is both associative and commutative, and given a finite subset L of K, there are many ways of 'combining' the elements of L into a single 'product' using ⋅. You have to start by taking two elements of L and combining them with ⋅. But your next step could be either (a) to take a third element and combine it with the product of the first two; or (b) to take a third and a fourth element and ⋅ them together (with a view to combining this new product with the first one at a later stage). There are even more choices at the next step. By what we have just proved, all these different 'combination-schemes' will eventually lead to the same answer; but there are many ways of getting to that final result. The question is, just how many (essentially different) routes to the final answer are there?

The question is further explored here.

Since a∧1 = a, 1 is the element represented by the empty expression in the CL-algebra. Encircling an element turns it into its complement. It remains to show that our circle-and-letter algebra obeys the 'three constraints'. This will be the case, provided we can prove, from the Boolean Algebra axioms, for all a and b:

(a')' = a    wrap
a∧1' = a    delete
a∧b' = a∧(a∧b)'    copy

This is proposed as an exercise for the reader. If the reader gets stuck, he or she may refer to this page.

back to CL-Algebras

on to Finite Boolean Algebras

home | Table of Contents