TAOCP 7.1.4 Exercise 236
Let $U = e_1 \sqcup e_2 \sqcup \cdots$, and let $C$ denote complement with respect to $U$.
Section 7.1.4: Binary Decision Diagrams
Exercise 236. ▶ [M25] [M25] Many extensions to the family algebra of exercise 203 suggest themselves when ZDDs are applied to combinatorial problems, including the following five opera- tions on families of sets: • The maximal elements f ↑= {α ∈f | β ∈f and α ⊆β implies α = β}; • The minimal elements f ↓= {α ∈f | β ∈f and α ⊇β implies α = β}; • The nonsubsets f ↗g = {α ∈f | β ∈g implies α ̸⊆β}; • The nonsupersets f ↘g = {α ∈f | β ∈g implies α ̸⊇β}; • The minimal hitting sets f ♯= {α | β ∈f implies α ∩β ̸= ∅}↓. For example, when f and g are the families of exercise 203(a) we have f ↑= e1⊔(e2∪e3), f ↓= ϵ, f ♯= ∅, g↑= g↓= g, g♯= (e1∪e2)⊔e3, f↗g = e1⊔e3, f ↘g = ϵ, g↗f = g↘f = ∅. a) Prove that f ↗g = f \ (f ⊓g), and give a similar formula for f ↘g. b) Let f C = {α | α ∈f} = f U, where U = e1 ⊔e2 ⊔· · · is the “universal set.” Clearly f CC = f, (f ∪g)C = f C∪gC, (f ∩g)C = f C∩gC, (f \g)C = f C\gC. Show that we also have the duality laws f ↑C = f C↓, f ↓C = f C↑; (f ⊔g)C = f C ⊓gC, (f ⊓g)C = f C ⊔gC; (f ↗g)C = f C ↘gC, (f ↘g)C = f C↗gC; f ♯= (℘↗f C)↓. c) True or false? (i) x↓ 1 = e1; (ii) x↑ 1 = e1; (iii) x♯ 1 = e1; (iv) (x1 ∨x2)↓= e1 ∪e2; (v) (x1 ∧x2)↓= e1 ⊔e2. d) Which of the following formulas hold for all families f, g, and h? (i) f ↑↑= f ↑; (ii) f ↑↓= f ↓; (iii) f ↑↓= f ↑; (iv) f ↓↑= f ↓; (v) f ♯↓= f ♯; (vi) f ♯↑= f ♯; (vii) f ↓♯= f ♯; (viii) f ↑♯= f ♯; (ix) f ♯♯= f ♯; (x) f ↗(g ∪h) = (f ↗g) ∩(f ↗h); (xi) f ↘(g∪h) = (f ↘g)∩(f ↘h); (xii) f ↘(g∪h) = (f ↘g)↘h; (xiii) f ↗g↑= f ↗g; (xiv) f ↘g↑= f ↘g; (xv) (f ⊔g)♯= (f ♯∪g♯)↓; (xvi) (f ∪g)♯= (f ♯⊔g♯)↓. e) Suppose g = u−−v(eu ⊔ev) is the family of all edges in a graph, and let f be the family of all the independent sets. Using the operations of extended family algebra, find simple formulas that express (i) f in terms of g; (ii) g in terms of f.
7.1.4 BINARY DECISION DIAGRAMS 277
Verified: no
Solve time: 4m40s
Let $U = e_1 \sqcup e_2 \sqcup \cdots$, and let $C$ denote complement with respect to $U$.
a) Identities for $f \↗ g$ and $f \↘ g$
By definition,
$$ f \↗ g = {\alpha \in f \mid \forall \beta \in g,\ \alpha \not\subseteq \beta}. $$
Define
$$ f \sqcap g = {\alpha \in f \mid \exists \beta \in g \text{ such that } \alpha \subseteq \beta}. $$
For every $\alpha \in f$, exactly one of the following holds:
- $\exists \beta \in g$ with $\alpha \subseteq \beta$, or
- $\forall \beta \in g$, $\alpha \not\subseteq \beta$.
Hence the two parts partition $f$, and
$$ f \↗ g = f \setminus (f \sqcap g). $$
Similarly,
$$ f \↘ g = {\alpha \in f \mid \forall \beta \in g,\ \alpha \not\supseteq \beta}. $$
Define
$$ f \sqcap' g = {\alpha \in f \mid \exists \beta \in g \text{ such that } \beta \subseteq \alpha}. $$
Then again $f$ splits into $f \sqcap' g$ and its complement inside $f$, so
$$ f \↘ g = f \setminus (f \sqcap' g). $$
b) Duality laws
Complement reverses inclusion:
$$ \alpha \subseteq \beta \iff \beta^C \subseteq \alpha^C. $$
Maximal and minimal elements
If $\alpha$ is maximal in $f$, then $\alpha^C$ is minimal in $f^C$. Hence:
$$ (f^\uparrow)^C = (f^C)^\downarrow,\qquad (f^\downarrow)^C = (f^C)^\uparrow. $$
Union and intersection (family algebra)
Complement swaps union and intersection:
$$ (f \sqcup g)^C = f^C \sqcap g^C,\qquad (f \sqcap g)^C = f^C \sqcup g^C. $$
Nonsubset / nonsuperset operators
Using definitions from (a):
$$ (f \↗ g)^C = f^C \↘ g^C,\qquad (f \↘ g)^C = f^C \↗ g^C. $$
This follows directly by replacing $\subseteq$ with $\supseteq$ under complement.
Minimal hitting sets
A set $\alpha$ is a hitting set of $f$ iff:
$$ \forall \beta \in f,\ \alpha \cap \beta \neq \emptyset \iff \forall \beta \in f,\ \beta^C \not\subseteq \alpha^C. $$
Thus $\alpha^C$ is a set in $\mathcal{P}(U)$ that avoids being a superset of any element of $f^C$, i.e. lies in $\mathcal{P}(U) \↗ f^C$.
Taking complements back and then minimal elements:
$$ f^\sharp = (\mathcal{P}(U) \↗ f^C)^\downarrow. $$
c) Truth values
Let $x_1 = {{1}}$, $x_2 = {{2}}$.
(i) $x_1^\downarrow$
$x_1$ has one element which is minimal, hence:
$$ x_1^\downarrow = x_1 \quad \Rightarrow \text{True}. $$
(ii) $x_1^\uparrow$
The single element is also maximal:
$$ x_1^\uparrow = x_1 \quad \Rightarrow \text{True}. $$
(iii) $x_1^\sharp$
Hitting sets of ${{1}}$ are all sets containing 1; minimal such family is ${{1}}$:
$$ x_1^\sharp = x_1 \quad \Rightarrow \text{True}. $$
(iv) $(x_1 \vee x_2)^\downarrow$
$$ x_1 \vee x_2 = {{1}, {2}}. $$
Both are minimal already, so:
$$ (x_1 \vee x_2)^\downarrow = {{1}, {2}} = e_1 \cup e_2 \quad \Rightarrow \text{True}. $$
(v) $(x_1 \wedge x_2)^\downarrow$
$$ x_1 \wedge x_2 = {{1}} \cap {{2}} = \emptyset. $$
Thus:
$$ (x_1 \wedge x_2)^\downarrow = \emptyset \neq {{1,2}}. $$
So:
$$ \text{False}. $$
d) Which identities hold?
Key facts:
- $f^\uparrow$ and $f^\downarrow$ produce antichains.
- On antichains, both operators act as identity.
- $f^\sharp$ (minimal hitting sets) is always an antichain.
(i) $f^\uparrow{}^\uparrow = f^\uparrow$
True (idempotence of maximal operator).
(ii) $f^\uparrow{}^\downarrow = f^\uparrow$
True: $f^\uparrow$ is an antichain, so applying $\downarrow$ does not change it.
(iii) $f^\uparrow{}^\downarrow = f^\downarrow$
False in general; LHS depends on maximal elements, RHS on minimal elements.
(iv) $f^\downarrow{}^\uparrow = f^\downarrow$
True: $f^\downarrow$ is an antichain.
(v) $f^\sharp{}^\downarrow = f^\sharp$
True: $f^\sharp$ is already minimal.
(vi) $f^\sharp{}^\uparrow = f^\sharp$
True: $f^\sharp$ is an antichain.
(vii) $f^\downarrow{}^\sharp = f^\sharp$
False: taking minimal elements before hitting-set dual changes the hypergraph structure.
(viii) $f^\uparrow{}^\sharp = f^\sharp$
False for the same reason.
(ix) $f^\sharp{}^\sharp = f^\sharp$
True: minimal transversal (hitting set) dualization is involutive for simple families.
Distributive laws
(x)
$$ f \↗ (g \cup h) = (f \↗ g) \cap (f \↗ h) $$
True, since the condition “no subset of any element in $g \cup h$” splits into both conditions.
(xi)
$$ f \↘ (g \cup h) = (f \↘ g) \cap (f \↘ h) $$
True by the same decomposition with $\supseteq$.
(xii)
$$ f \↘ (g \cup h) = (f \↘ g) \↘ h $$
False: the right-hand side imposes nested constraints that are not equivalent to a single union constraint.
(xiii)
$$ f \↗ g^\uparrow = f \↗ g $$
True: replacing $g$ by its maximal elements does not change existence of supersets.
(xiv)
$$ f \↘ g^\uparrow = f \↘ g $$
True by dual reasoning.
(xv)
$$ (f \sqcup g)^\sharp = (f^\sharp \cup g^\sharp)^\downarrow $$
True: hitting sets of a union correspond to minimal hitting sets combining both families.
(xvi)
$$ (f \cup g)^\sharp = (f^\sharp \sqcup g^\sharp)^\downarrow $$
True by symmetry of union and family-algebra sum.
e) Independent sets and edges
Let $g$ be the family of edges of a graph on universe $U$.
(i) Express $f$ in terms of $g$
Independent sets are those containing no edge:
$$ f = {\alpha \subseteq U \mid \forall \beta \in g,\ \beta \not\subseteq \alpha}. $$
This is exactly the definition of nonsupersets:
$$ f = \mathcal{P}(U) \↘ g. $$
(ii) Express $g$ in terms of $f$
A set is non-independent iff it contains an edge. Thus $U\setminus f$ consists of all supersets of edges. The minimal non-independent sets are exactly the edges themselves.
Hence:
$$ g = ( \mathcal{P}(U) \setminus f )^\downarrow. $$
Summary of corrections
- Fixed incorrect evaluation in (c)(v).
- Corrected operator direction in (e)(i): independent sets correspond to $\↘$, not $\↗$.
- Re-derived dualities using inclusion reversal.
- Identified which identities in (d) follow from antichain stability and which fail structurally.
- Expressed edges as minimal non-independent sets in family algebra form.