## Exhaustive Case Analysis## and the Standard Form of an ExpressionIn the last chapter (The 'Case Analysis' Lemma) we found that any E can be transformed into the form E = (x(E in which the 'derived' expressions E E therefore (x(E by distribute. Similarly, the second factor ((x)(E Thus E as a whole is equivalent to the product of four factors: (xy(E If there is a third letter z: E = (xyz(E Now suppose E contains N different letters altogether. Then E is equivalent to a product of 2 (xyz..k(E 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
E 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 2 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 BE B = x (y) z .. k then E We may now re-state the result of exhaustive case analysis applied to E. We have E = Product over B in B of ( B (E In every case E M Then we may write the standard form of E as follows: E = Product over B in M It is perhaps time for an example. Suppose we are considering expressions constructed with just two letters, x and y. Suppose that E = xy. Then M 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)) Alternatively, using the equivalence form: E = ((x)y) (x(y)) ((x)(y)) ## Complementary Standard FormApplying the standardization procedure to (E) rather than E we obtain: (E) = Product over B in B of ( B ((E) but (E) therefore (E) = Product over B in B of ( B E If we define M then M (E) = Product over B in M Circling each side of the equation, we obtain: E = ( Product over B in M 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 M
E(E) = Product over B in B of ( B ) . (Because the union of M ## Dominance revisitedThe necessary and sufficient condition for E to dominate F may be written: E ( F ) = O . In terms of standard forms: Product over B in M in other words: Product over B in M 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 M in other words, if and only if M back to The 'Case Analysis' Lemma |