Summing Out A Variable |
Suppose we are eliminating Y, and we have absorbed all of the confactors that contain Y into the confactors for Y. Then any two confactors in R that contain Y have incompatible contexts. The contexts for the confactors that contain Y in the table are disjoint from the contexts of the confactors that contain Y in the body.
Summing out Y from a confactor that contains Y in the table proceeds as before. We can use a similar trick to absorption to avoid any more splitting when adding confactors that contain Y in the body.
Suppose Y has domain {v_{1},...,v_{s}}. The contexts of the confactors with Y=v_{i} in the body are exclusive and the disjunct is logically equivalent to the disjunct of confactors with Y=v_{j} in the body for any other value v_{j}.
For each 1 <= i <= s, let R_{i} = {<b,t>: <b&Y=v_{i},t> in R^{+} }. Thus R_{i} is the confactor for Y=v_{i} in the context, but with Y=v_{i} omitted from the context. We will combine the R_{i}'s using a binary operation:
where +_{t} is an addition operation defined on tables that is identical to the product ×_{t} of Definition * except that it adds the values instead of multiplying them.
R_{1} +_{g} R_{2}={<c_{1} union c_{2},set(t_{1},c_{2})+_{t}set(t_{2},c_{1})>: <c_{1},t_{1}> in R_{1}, <c_{2},t_{2}> in R_{2}, compatible(c_{1},c_{2})}
Then R_{1} +_{g} R_{2} +_{g}...+_{g} R_{s} is the result from summing out Y from the confactors with Y in the body.
Summing Out A Variable |