Exhaustive Case Analysis

and the Standard Form of an Expression

In the last chapter (The 'Case Analysis' Lemma) we found that any E can be transformed into the form

E = (x(Ex))    ((x)(E(x))),

in which the 'derived' expressions Ex and E(x) do not contain the letter x. Supposing that Ex and/or E(x) contain a second letter, y, we can treat them in the same way. Thus

Ex = (y(Exy))    ((y)(Ex(y))) ;


(x(Ex)) = ( x ( (y(Exy))    ((y)(Ex(y))) ) )
= (xy(Exy))    (x(y)(Ex(y)))

by distribute. Similarly, the second factor

((x)(E(x))) = ( (x) ( (y(E(x)y))    ((y)(E(x)(y))) ) )
= ((x)y(E(x)y))    ((x)(y)(E(x)(y))) .

Thus E as a whole is equivalent to the product of four factors:

(xy(Exy))     (x(y)(Ex(y)))   ((x)y(E(x)y))     ((x)(y)(E(x)(y))).

If there is a third letter z:

E = (xyz(Exyz)) (xy(z)(Exy(z))) (x(y)z(Ex(y)z)) (x(y)(z)(Ex(y)(z)))
((x)yz(E(x)yz)) ((x)y(z)(E(x)y(z))) ((x)(y)z(E(x)(y)z)) ((x)(y)(z)(E(x)(y)(z))).

Now suppose E contains N different letters altogether. Then E is equivalent to a product of 2N factors, like


and similar expressions in which some of the letters are circled. But by this stage E has had all its letters sucked out of it. Each of the 'derived' expressions Exyz..k, and so forth, is letter-free; in other words, is an arithmetic expression, and, as such, can be reduced either to _ or to O . If it is equivalent to the void, then the corresponding factor vanishes; while if it is equivalent to O, then the factor becomes (xyz..k); or a similar expression with some of the letters encircled. This we call the standard form of E; and the fact that E is equivalent to such a standard form we will refer to as the Standard Form Lemma.

Our notation is becoming a bit unwieldy here: there is an advantage in going to a higher (more abstract) level of description. So here goes.

Given N letters x, y, z ..k, consider the following set of expressions, constructed out of those letters, together with circles as required. The set has 2N members and we will call it B (for 'basic'). The first few 'basic expressions' are

x y z .. j k,
x y z .. j (k),
x y z .. (j) k,
x y z .. (j) (k),

carrying on, in the pattern of the sequence of integers in binary notation, up to

(x)(y)(z) .. (j)(k) .

Given an expression B, belonging to B, and given an expression E involving the same letters as B, the expression BE may be transformed into BEB where EB is the arithmetic expression obtained by uncopying the letters, or circled letters, appearing in B, out of E. For example, if

B = x (y) z .. k


EB = Ex(y)z..k .

We may now re-state the result of exhaustive case analysis applied to E. We have

E = Product over B in B of ( B (EB) ) .

In every case EB, being purely algebraic, is equivalent to either _ or O . In the former case, the factor (B(EB)) equates to _ and drops out, in the latter case it equates to (B). We may introduce a new set of expressions ME, a subset of B, defined as follows:

ME = { B in B such that EB = O }

Then we may write the standard form of E as follows:

E = Product over B in ME of ( B ) .

It is perhaps time for an example. Suppose we are considering expressions constructed with just two letters, x and y. Suppose that

E = xy.


ME = { (x)y, x(y), (x)(y) }

and the standard form of E is

E = ((x)y) (x(y)) ((x)(y)).

We may check this as follows:

E = ((x)y)     (x(y)) ((x)(y))
= ((x)y) y   [each way]
= ((x)) y    [uncopy]
= x y.

Alternatively, using the equivalence form:

E = ((x)y) (x(y))     ((x)(y))
= [x|y] ((x)(y))    [definition of [|] ]
= [x|y] ((y)(y))    [property of [|] ]
= [x|y] ((y))
= [x|y] y
= [x| ] y    [uncopy]
= x y    [property of [|] ] .

Complementary Standard Form

Applying the standardization procedure to (E) rather than E we obtain:

(E) = Product over B in B of ( B ((E)B) ) .


(E)B = (EB) ;


(E) = Product over B in B of ( B EB ) .

If we define

ME = { B in B such that EB = _ }

then ME is what is called 'the complement of ME in B'; that is to say, ME is the subset of B whose members are precisely those members of B which are not in ME. We may now write

(E) = Product over B in ME of ( B ) .

Circling each side of the equation, we obtain:

E = ( Product over B in ME of ( B ) ).

This is the complementary standard form of E. Returning to the example used above, namely E = xy, we find that the complementary from of E is

E = ((x y)),

which, in this particular case, is considerably simpler than the standard form. Clearly, in general, which is simpler will depend on whether ME or ME is the smaller set.

Exercise for the reader: we note, from the above, that

E(E) = Product over B in B of ( B ) .

(Because the union of ME and ME is B.) Check that the product of all 2N factors is the empty mark O .

Dominance revisited

The necessary and sufficient condition for E to dominate F may be written:

E ( F ) = O .

In terms of standard forms:

Product over B in ME of (B) × Product over B in MF of (B) = O

in other words:

Product over B in MEMF of (B) = O .

But O itself has the standard form

O = Product over B in B of (B) ,

so the equation will be satisfied if and only if


in other words, if and only if

MF is a subset of ME.