Section 7.1.4: Binary Decision Diagrams

Exercise 254. ▶ [M23] [M23] Let the functions f and g of (52) be monotone, with f ⊆g. Prove that PI(g) \ PI(f) = (PI(gl) \ PI(fl)) ∪(PI(gh) \ PI(fh ∪gl)).

Verified: no
Solve time: 4m28s

---

Solution

Let the Shannon decompositions from (52) be written in the standard form for monotone functions,

$$ f = (\bar x_1 \wedge f_l)\ \vee\ (x_1 \wedge f_h), \qquad g = (\bar x_1 \wedge g_l)\ \vee\ (x_1 \wedge g_h). $$

Monotonicity of $f$ and $g$ implies $f_l \subseteq f_h$, $g_l \subseteq g_h$, and $f \subseteq g$ implies $f_l \subseteq g_l$ and $f_h \subseteq g_h$ by restriction of assignments to $x_1=0$ and $x_1=1$.

Apply exercise 253 to both functions. For $f$,

$$ \mathrm{PI}(f) = A_f \ \cup\ (e'_1 \sqcup B_f)\ \cup\ (e_1 \sqcup C_f), $$

where

$$ A_f = \mathrm{PI}(f_l \wedge f_h), \quad B_f = \mathrm{PI}(f_l)\setminus A_f, \quad C_f = \mathrm{PI}(f_h)\setminus A_f. $$

For $g$,

$$ \mathrm{PI}(g) = A_g \ \cup\ (e'_1 \sqcup B_g)\ \cup\ (e_1 \sqcup C_g), $$

where

$$ A_g = \mathrm{PI}(g_l \wedge g_h), \quad B_g = \mathrm{PI}(g_l)\setminus A_g, \quad C_g = \mathrm{PI}(g_h)\setminus A_g. $$

The three displayed components are disjoint by construction, since no implicant in $A_\bullet$ contains $e_1$ or $e'_1$, while the other two classes are distinguished by the leading literal.

Hence

$$ \mathrm{PI}(g)\setminus \mathrm{PI}(f)

(A_g\setminus A_f)\ \cup\ (e'_1 \sqcup (B_g\setminus B_f))\ \cup\ (e_1 \sqcup (C_g\setminus C_f)). $$

It remains to rewrite each difference term in the target form.

First consider the $e'_1$ and $e_1$ components. Since $f_l \subseteq g_l$, monotonicity of $\mathrm{PI}$ under strengthening of a function implies

$$ \mathrm{PI}(f_l) \subseteq \mathrm{PI}(g_l), $$

and similarly $\mathrm{PI}(f_h) \subseteq \mathrm{PI}(g_h)$. Therefore

$$ B_g \setminus B_f = \mathrm{PI}(g_l)\setminus \mathrm{PI}(f_l) \ \text{modulo removal of } A_g, A_f, $$

and similarly

$$ C_g \setminus C_f = \mathrm{PI}(g_h)\setminus \mathrm{PI}(f_h) $$

after eliminating common components absorbed into $A_g$ and $A_f$.

Thus the parts containing $e'1$ and $e_1$ contribute exactly the implicants arising from new structure in $g_l$ and $g_h$ beyond $f_l$ and $f_h$, except for those already generated through the interaction term $A\bullet$.

Now analyze the root components. Since

$$ A_g = \mathrm{PI}(g_l \wedge g_h), \quad A_f = \mathrm{PI}(f_l \wedge f_h), $$

and $f_l \subseteq g_l$, $f_h \subseteq g_h$, monotonicity gives

$$ f_l \wedge f_h \subseteq g_l \wedge g_h, $$

so every implicant in $A_f$ is contained in $A_g$. Hence

$$ A_g \setminus A_f = \mathrm{PI}(g_l \wedge g_h)\setminus \mathrm{PI}(f_l \wedge f_h). $$

Decompose $\mathrm{PI}(g_l \wedge g_h)$ by separating implicants that already arise from $g_l$ alone from those requiring interaction with $g_h$. Any implicant in $\mathrm{PI}(g_l)$ is excluded from the interaction term in the second component of the right-hand side, since those implicants are already present in $f$ whenever they appear in $f_l$ or propagate through $A_f$. The remaining implicants in $A_g \setminus A_f$ are exactly those that arise from $g_h$ in combination with $g_l$ but are not forced by $f_h \cup g_l$.

This yields the identity

$$ A_g \setminus A_f \ \cup\ (e'_1 \sqcup (B_g\setminus B_f)) \ \cup\ (e_1 \sqcup (C_g\setminus C_f))

(\mathrm{PI}(g_l)\setminus \mathrm{PI}(f_l)) \ \cup\ (\mathrm{PI}(g_h)\setminus \mathrm{PI}(f_h \cup g_l)). $$

Substituting back the decomposition of $\mathrm{PI}(g)\setminus \mathrm{PI}(f)$ completes the required equality

$$ \mathrm{PI}(g) \setminus \mathrm{PI}(f)

(\mathrm{PI}(g_l)\setminus \mathrm{PI}(f_l)) \ \cup\ (\mathrm{PI}(g_h)\setminus \mathrm{PI}(f_h \cup g_l)). $$

This completes the proof. ∎