Combining relations

You can have more than one relation at the same time and combine them. For example if you also have relations

X ::=    (i == 5 and j == 1)
      or (i == 2 and j == 1)

Y ::= i == 5 and k == 3

then Z ::= X and Y becomes

Z ::= i == 5 and j == 1 and k == 3

The i == 2 alternative of X does not occur in the new relation since Y does not hold for that value of i. Also note that all equalities are preserved from both relations, the j == 1 equality and the k == 3 equality are part of Z even though only one of the input relations stated them. The reason is that if an alternative in a relation does not say anything about a variable, it is assumed it may have any value (the not mentioned variable is independent).

This also works if both relations are a disjunction. For example P ::= X and Q with

X ::=    (i == 5 and j == 1)
      or (i == 2 and j == 1)

Q ::=    (i == 5            and k == 5)
      or (i == 5            and k == 3)
      or (i == 3            and k == 1)
      or (i == 2 and j == 1 and k == 4)


P ::=    (i == 5 and j == 1 and k == 5)
      or (i == 5 and j == 1 and k == 3)
      or (i == 2 and j == 1 and k == 4)

All combined alternatives of X and Q that are not trivially false due to conflicting equalities become part of the result.

From a logical point of view the above is simple Boolean algebra, but if you change your view on what X and Q express you can see the hidden power of decision diagrams.

Instead of X holds when j is equal to 1 and i must be either 2 or 5, read X as a function from i to j, that is, when i equals 2 then j equals 1 or when i equals 5 then j equals 1. Similarly, relation Q can be read as a function from i and j to k, that is, when i equals 5 then k becomes 5 or 3, if i equals 3 then k becomes 1, if i equals 2 and j equals 1 then k equals 4.

If you look at what P contains in the function view, you can see you get the conjunction of both functions. In one X and Q step you computed the combined function for all values of all variables at the same time!

An example of this property is used below, computing the result of an assignment.