next up previous
Next: g_distrib Up: g_distrib Previous: g_distrib

3. Canonical form

By using the distributive law for meets of joins, any lattice expression can be reduced to a join of meets (some of which may be a meet of one variable, i.e., just that variable). Further simplification can be done by deleting any meet-expression that is $ \leq $ another, making the whole join-expression ``irredundant''. The irredundant form is unique (see Problem G-[*]). This is the canonical form of the original expression.

For example, $ (x \vee y) \wedge (z \vee (w \wedge x)) = ((x \vee y)
\wedge z) \vee ((x \vee y) \wedge (w \wedge x))$ $ = $ $ (x \wedge z)
\vee (y \wedge z) \vee (x \wedge w \wedge x) \vee (y \wedge w \wedge x)$ $ = $ $ (x \wedge z) \vee (y \wedge z) \vee (x \wedge w) \vee (x \wedge
y \wedge w)$ $ = (x \wedge z) \vee (y \wedge z) \vee (x \wedge w)$.





Kirby A. Baker 2003-01-10