## 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)

gives

    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.