## Boolean AlgebrasWe now bring in a concept from outside Laws of Form, namely, the idea of a
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
Let the operations ∧ and ∨ be defined as follows: a ∧ b = ab and let the unit and the zero be defined by 1 = _ Commutativity is immediate; associativity follows from (a ∧ b) ∧ c = abc 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)) = ( 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))
= ( (by distribute again). Finally: a ∧ a' = a (a) = O = 0 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 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 Suppose the subdivided combination of N letters is x = { {a..c} {d...f} ... {h...j} {k...mn} } . By the induction hypothesis (P 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} } Our induction step is proved, therefore P 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) Thus our law of combination is both dissociative and permutable.
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 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 |