Appendix 5. Manipulating Boolean formulae

Boolean expressions in SPAN are manipulated primarily by transposition and by expansion as described below. To carry out these operations, basic set algebraic rules for reducing regular Boolean expressions are invoked. For example, using XX to mean X∩X:

XXW = XW and (XW)∪X = X

for any attribute X and non-null set W (which may be a combination of attributes e.g W =X₂X₃X₄).

Repeated application of these rules is generally sufficient to simplify regular Boolean expressions generated in a search. They may not, however, simplify very complex Boolean expressions involving attributes and their complements or attributes that are somehow nested. These can generally be accomplished with the Full Boolean reduction option (see A5.4).

In order that subgroups, as defined in reference 2, are determined, it is necessary to obtain both A and A- in normal disjunctive form. For example, consider the p₁,...,p_q = 3,3,2 partition

A = (X₁X₂X₃)∪(X₁X₃X₄)∪(X₂X₅)

Then

A^- = (X₁^- ∪X₂^- ∪X₃^-)∩(X₁^- ∪X₃^- ∪X₄^-)∩(X₂^- ∪X₅^-)

but we need to re-express A- in disjunctive form and to do this it is it is necessary to "transpose" the above expression by "cross-multiplying" the expression and carrying out simplifications. If you cross multiply this expression, there will be 3×3×2 = 18 terms, each with the intersection of three X_i^--'s. For example, the first is X₁-X₁-X₂-, the next X₁-X₁-X₅-, and so on. The first term simplifies to X₁-X₂- and later terms such as X₁-X₃- X₂- become absorbed by it. The 18, three element, terms finally simplify to five terms, each with two elements:

A^- = (X₁^- X₂^-)∪(X₁^- X₅^-)∪(X₂^- X₃^-)∪(X₂^- X₄^-)∪(X₃^- X₅^-)

This process is fairly simple to computerise and can be made efficient by iterative "partial transpositions" followed by simplification. Details are omitted.

The process of transposition is done for every partition that is generated by a search, so that, as mentioned above (A4.1), the Boolean manipulations may slow the search somewhat whenp₁,...,p_q becomes large.

Another operation that is required by SPAN is to expand out partitions in which there is an added attribute. For example suppose

B = (X₁X₂)∪(X₃X₄)

is an added attribute and that a partition is generated with

A = (BX₃)∪(X₄)

Then, substituting for B gives

A = (X₁X₂X₃)∪(X₃X₄X₃)∪(X₄) = (X₁X₂X₃)∪(X₄)

Again, computerising this process is fairly straightforward, with the above reduction rules for simplifying Boolean expressions.

Note that if an attribute is created from the Y menu option Transform SPAN does not attempt to expand out the attribute or perform any simplifications of it. For example, suppose an attribute is lbw=0 is formed by dichotomising a birth weight variable BWT at 2.5 kg. Then the partition A =(lbw=0 & BWT <=2.5) is not simplified at all. Once lbw is formed it becomes a primitive attribute, in the sense described in 10.2.

One facility of the Option Menu is Full Boolean reduction (see 17.3). This procedure utilises information about the data from which attributes are derived. The procedure will only reduce Boolean expressions, beyond those reductions done automatically by applying the two rules in A5.1, when attributes in expressions are created from the same underlying variable.

For this type of Boolean reduction, additional reduction rules are invoked which take account of whether attributes are subsetted or are complements of each other.

For example, the reduction rule

X ∪(X^- W) = X∪W

is invoked. Also the rule

(X W Z)∪(X^- Y Z)∪(W Y Z V) = (X W Z)∪(X^- Y Z )

The option also takes account of attributes formed from different cuts of a variable. For example, if X₁ = { x £ 1 } and X₂ = { x £ 2 } are attributes derived from x by cutpoints 1 and 2, then X₁ is a subset of X₂ and X_1∩X₂ = X₁.

Multiple attributes derived from nominal variables are more difficult to deal with since the intersection or union of attributes so formed depends on how the attributes are defined. Consider, for example, a nominal variable x with possible categories 1,2,3 and 4. If you include the control file attribute creating lines:

X n1234 12

X n1234 34

you will effectively create attributes X₁ = { x = 1,2 } and X₂ = { x = 3,4 } . Here X₁X₂ is null, whatever the state space of x, while X₁∪X₂ is the universal set since the state space is defined by 1234. If the universe 1234 is omitted, SPAN assumes it to be the set of integers 0123456789 (see 9.3.1) in which case X_1∪X₂ is not the universal set

As mentioned in 9.9, a null attribute is automatically created by SPAN. Its purpose is to recognise Boolean expressions that are null. For example, referring to the above, the expression A = X1∩X2 is null, the empty set, and would be represented in SPAN by A=(.=null)with complement A-=(^=null).

[Back to table of contents]