TAOCP 7.1.4 Exercise 203
Given f=\{\emptyset,\{1,2\},\{1,3\}\}, \quad g=\{\{1,2\},\{3\}\}.
Section 7.1.4: Binary Decision Diagrams
Exercise 203. ▶ [M24] [M24] (Family algebra.) The following algebraic conventions are useful for deal- ing with finite families of finite subsets of positive integers, and with their representation as ZDDs. The simplest such families are the empty family, denoted by ∅and represented by ⊥; the unit family {∅}, denoted by ϵ and represented by ⊤; and the elementary families {{j}} for j ≥1, denoted by ej and represented by a branch node j j with LO = ⊥and HI = ⊤. (Exercise 186 illustrates the ZDD for e3.) Two families f and g can be combined with the usual set operations: • The union f ∪g = {α | α ∈f or α ∈g} is implemented by OR(f, g); • The intersection f ∩g = {α | α ∈f and α ∈g} is implemented by AND(f, g); • The difference f \ g = {α | α ∈f and α /∈g} is implemented by BUTNOT(f, g); • The symmetric difference f ⊕g = (f \ g) ∪(g \ f) is implemented by XOR(f, g). And we also define three new ways to construct families of subsets: • The join f ⊔g = {α ∪β | α ∈f and β ∈g}, sometimes written just fg; • The meet f ⊓g = {α ∩β | α ∈f and β ∈g}; • The delta f g = {α ⊕β | α ∈f and β ∈g}. All three are commutative and associative: f ⊔g = g ⊔f, f ⊔(g ⊔h) = (f ⊔g) ⊔h, etc. a) Suppose f = {∅, {1, 2}, {1, 3}} = ϵ ∪(e1 ⊔(e2 ∪e3)) and g = {{1, 2}, {3}} = (e1 ⊔e2) ∪e3. What are f ⊔g and (f ⊓g) \ (f e1)? b) Any family f can also be regarded as a Boolean function f(x1, x2, . . . ), where α ∈f ⇐⇒f([1 ∈α], [2 ∈α], . . . ) = 1. Describe the operations ⊔, ⊓, and in terms of Boolean logical formulas. c) Which of the following formulas hold for all families f, g, and h? (i) f ⊔(g ∪h) = (f ⊔g)∪(f ⊔h); (ii) f ⊓(g∪h) = (f ⊓g)∪(f ⊓h); (iii) f ⊔(g⊓h) = (f ⊔g)⊓(f ⊔h); (iv) f ∪(g ⊔h) = (f ∪g) ⊔(f ∪h); (v) f ∅= ∅⊓g = h ⊔∅; (vi) f ⊓ϵ = ϵ. d) We say that f and g are orthogonal, written f ⊥g, if α ∩β = ∅for all α ∈f and all β ∈g. Which of the following statements is true for all families f and g? (i) f ⊥g ⇐⇒f ⊓g = ϵ; (ii) f ⊥g =⇒|f ⊔g| = |f||g|; (iii) |f ⊔g| = |f||g| =⇒ f ⊥g; (iv) f ⊥g ⇐⇒f ⊔g = f g. e) Describe all families f for which the following statements hold: (i) f ∪g = g for all g; (ii) f ⊔g = g for all g; (iii) f ⊓g = g for all g; (iv) f ⊔(e1 ⊔e2) = f; (v) f ⊔(e1 ∪e2) = f; (vi) f ((e1 ⊔e2) ∪e3) = f; (vii) f f = ϵ; (viii) f ⊓f = f.
Verified: no
Solve time: 6m09s
Corrected Solution
(a)
Given
$$ f={\emptyset,{1,2},{1,3}}, \quad g={{1,2},{3}}. $$
Join $f \sqcup g$
All unions $\alpha \cup \beta$:
- $\emptyset\cup{1,2}={1,2}$, $\emptyset\cup{3}={3}$
- ${1,2}\cup{1,2}={1,2}$, ${1,2}\cup{3}={1,2,3}$
- ${1,3}\cup{1,2}={1,2,3}$, ${1,3}\cup{3}={1,3}$
Hence
$$ f \sqcup g={{1,2},{3},{1,3},{1,2,3}}. $$
Meet $f \sqcap g$
All intersections:
- with $\emptyset$: always $\emptyset$
- ${1,2}\cap{1,2}={1,2}$, ${1,2}\cap{3}=\emptyset$
- ${1,3}\cap{1,2}={1}$, ${1,3}\cap{3}={3}$
Thus
$$ f \sqcap g={\emptyset,{1,2},{1},{3}}. $$
$f \oplus e_1$
Since $e_1={{1}}$:
$$ \emptyset\oplus{1}={1},\quad {1,2}\oplus{1}={2},\quad {1,3}\oplus{1}={3}. $$
So
$$ f \oplus e_1={{1},{2},{3}}. $$
Difference
$$ (f \sqcap g)\setminus (f \oplus e_1)={\emptyset,{1,2}}. $$
(b) (Boolean interpretation)
Identify $f$ with its characteristic function:
$$ f(x_1,x_2,\dots)=1 \iff {i:x_i=1}\in f. $$
Then:
Join
$$ (f\sqcup g)(x)=1 \iff \exists y,z ;[f(y)\land g(z)\land x_i=y_i\lor z_i]. $$
Meet
$$ (f\sqcap g)(x)=1 \iff \exists y,z ;[f(y)\land g(z)\land x_i=y_i\land z_i]. $$
Delta
$$ (f\oplus g)(x)=1 \iff \exists y,z ;[f(y)\land g(z)\land x_i=y_i\oplus z_i]. $$
(c) (validity of identities)
(i)
$$ f \sqcup (g \cup h) = (f \sqcup g)\cup(f \sqcup h) $$
True. Distribution over union holds by splitting cases for $\beta\in g\cup h$.
(ii)
$$ f \sqcap (g \cup h) = (f \sqcap g)\cup(f \sqcap h) $$
True. Same reasoning using distributivity of intersection over union.
(iii)
$$ f \sqcup (g \sqcap h) = (f \sqcup g)\sqcap(f \sqcup h) $$
True. Elementwise distributivity:
$$ \alpha\cup(\beta\cap\gamma)=(\alpha\cup\beta)\cap(\alpha\cup\gamma), $$
lifted over all pairs.
(iv)
$$ f \cup (g \sqcup h) = (f \cup g)\sqcup(f \cup h) $$
False.
Counterexample:
$$ f={\emptyset},\quad g={{1}},\quad h={{2}}. $$
Left side contains $\emptyset$, while right side does not, so equality fails.
(v)
$$ f \sqcup \emptyset = \emptyset,\quad \emptyset \sqcap g=\emptyset,\quad h \sqcup \emptyset=\emptyset $$
True. No pairs exist in any construction involving the empty family.
(vi)
$$ f \oplus ((e_1 \sqcup e_2)\cup e_3)=f $$
False. Symmetric difference with a fixed nonempty family cannot leave all elements unchanged; it alters every element by XOR with at least one nonempty set.
(d) Orthogonality
Recall: $f\perp g$ iff every $\alpha\in f$, $\beta\in g$ satisfy $\alpha\cap\beta=\emptyset$.
(i)
$$ f\perp g \iff f\sqcap g=\epsilon $$
True. The only possible intersection is $\emptyset$, and this occurs exactly under orthogonality.
(ii)
$$ f\perp g \Rightarrow |f\sqcup g|=|f||g| $$
True. Disjointness makes $(\alpha,\beta)\mapsto \alpha\cup\beta$ injective.
(iii)
$$ |f\sqcup g|=|f||g| \Rightarrow f\perp g $$
False. Cardinality equality does not force disjoint unions; collisions may be avoided without disjointness.
(iv)
$$ f\perp g \iff f\sqcup g = f \oplus g $$
True. Disjoint union implies $\alpha\cup\beta=\alpha\oplus\beta$, and conversely.
(e) Characterizations of families $f$
(i) $f\cup g=g\ \forall g$
Only possible when
$$ f=\emptyset. $$
(ii) $f\sqcup g=g\ \forall g$
The only identity element for join is:
$$ f=\epsilon={\emptyset}. $$
(iii) $f\sqcap g=g\ \forall g$
Impossible: no family acts as identity for all intersections.
No such $f$.
(iv) $f\sqcup (e_1\sqcup e_2)=f$
Since $e_1\sqcup e_2={{1,2}}$, this requires:
$$ \alpha\cup{1,2}=\alpha ;;\forall \alpha\in f, $$
so every set in $f$ contains ${1,2}$.
(v) $f\sqcup (e_1\cup e_2)=f$
Since $e_1\cup e_2={{1},{2}}$, closure requires:
$$ \alpha\cup{1}=\alpha \text{ and } \alpha\cup{2}=\alpha, $$
so every $\alpha\in f$ contains both 1 and 2.
(vi)
$$ f \oplus ((e_1\sqcup e_2)\cup e_3)=f $$
Let $S=(e_1\sqcup e_2)\cup e_3\neq\emptyset$.
Then:
$$ f\oplus S=f \iff S=\emptyset, $$
which is false. Hence:
No solution $f$.
(vii)
$$ f\oplus f=\epsilon $$
We have:
- If $f=\emptyset$, result is $\emptyset\neq\epsilon$.
- If $f\neq\emptyset$, every $\alpha\oplus\alpha=\emptyset$, so result is ${\emptyset}=\epsilon$.
Hence:
$$ f\neq\emptyset. $$
(viii)
$$ f\sqcap f=f $$
We always have:
- $\alpha\cap\alpha=\alpha$, so $f\subseteq f\sqcap f$,
- but extra elements $\alpha\cap\beta$ may appear.
Thus equality holds iff:
$$ f \text{ is closed under intersection.} $$
Final Summary of Corrections
- Distributive laws (c): (i)(ii)(iii)(v) true, (iv)(vi) false
- Symmetric difference identity (e vii): all nonempty families work
- Meet idempotence (e viii): requires intersection-closure, not automatic
- Several identity-element claims corrected accordingly