TAOCP 7.1.4 Exercise 222
The universe consists of the 130 elementary variables $a_1,b_1,\ldots,z_5$, where $\ell_j$ denotes the event “letter $\ell$ occurs in position $j$ of a five-letter word.
Section 7.1.4: Binary Decision Diagrams
Exercise 222. ▶ [27] [27] When family algebra is applied to five-letter words as in (131), the 130 variables are called a1, b1, . . . , z5 instead of x1, x2, . . . , x130; and the corresponding elementary families are denoted by the symbols a1, b1, . . . , z5 instead of e1, e2, . . . , e130. Thus the family F = WORDS(5757) can be constructed by synthesizing the formula F = (w1 ⊔h2 ⊔i3 ⊔c4 ⊔h5) ∪· · · ∪(f1 ⊔u2 ⊔n3 ⊔n4 ⊔y5) ∪· · · ∪(p1 ⊔u2 ⊔p3 ⊔a4 ⊔l5). a) Let ℘denote the universal family of all subsets of {a1, . . . , z5}, also called the “power set.” What does the formula F ⊓℘signify? b) Let X = X1 ⊔· · ·⊔X5, where Xj = {aj, bj, . . . , zj}. Interpret the formula F ⊓X. c) Find a simple formula for all words of F that match the pattern tuh. d) Find a formula for all SGB words that contain exactly k vowels, for 0 ≤k ≤5 (considering only a, e, i, o, and u to be vowels). Let Vj = aj ∪ej ∪ij ∪oj ∪uj. e) How many patterns in which exactly three letters are specified are matched by at least one SGB word? (For example, mtc is such a pattern.) Give a formula. f) How many of those patterns are matched at least twice (e.g., atc)? g) Express all words that remain words when a ‘b’ is changed to ‘o’. h) What’s the significance of the formula F/V2? i) Contrast (X1 ⊔V2 ⊔V3 ⊔V4 ⊔X5) ∩F with (X1 ⊔X5) \ ((℘\F)/(V2 ⊔V3 ⊔V4)).
Verified: no
Solve time: 2m11s
Setup
The universe consists of the 130 elementary variables $a_1,b_1,\ldots,z_5$, where $\ell_j$ denotes the event “letter $\ell$ occurs in position $j$ of a five-letter word.” Each SGB word corresponds to a 5-element set selecting exactly one variable from each block $X_j={a_j,b_j,\ldots,z_j}$.
The family $F=\mathrm{WORDS}(5757)$ is the set of 5757 such 5-element selections that correspond to valid dictionary words.
The family algebra operations follow Knuth’s ZDD semantics: $X\cup Y$ is union of families, $X\sqcup Y$ is the combinatorial product selecting one element from each operand family, $X\sqcap Y$ filters a family by retaining only elements that belong to $Y$, and $X/Y$ removes the contribution of variables in $Y$ by existential projection on those coordinates.
The universal family $\mathcal P$ is the family of all subsets of ${a_1,\ldots,z_5}$.
Solution
(a)
The expression $F \sqcap \mathcal P$ retains exactly those members of $F$ that are elements of the universal family $\mathcal P$. Since every element constructed from the alphabet variables is already a subset of ${a_1,\ldots,z_5}$, every word encoded in $F$ lies in $\mathcal P$. The filtering operation therefore does not remove any element.
Hence $F \sqcap \mathcal P = F$.
(b)
Each $X_j = {a_j,b_j,\ldots,z_j}$ is the family of all possible letters in position $j$. The expression
$X = X_1 \sqcup X_2 \sqcup X_3 \sqcup X_4 \sqcup X_5$
constructs all 5-letter strings over the alphabet ${a,\ldots,z}$, because the $\sqcup$ operation selects exactly one letter-variable from each position.
Thus $X$ is the family of all possible 5-letter words, and $F \subseteq X$ by construction of SGB words.
The filtering operation $F \sqcap X$ retains those elements of $F$ that lie in $X$. Since every element of $F$ already lies in $X$, the result is unchanged.
Hence $F \sqcap X = F$.
(c)
The pattern $t_u_h$ fixes positions $1,3,5$ and leaves positions $2,4$ free. The corresponding family is formed by selecting $t_1$, $u_3$, $h_5$ and arbitrary elements from $X_2$ and $X_4$:
$P = t_1 \sqcup X_2 \sqcup u_3 \sqcup X_4 \sqcup h_5.$
To restrict to valid SGB words, we intersect with $F$:
$P \sqcap F = (t_1 \sqcup X_2 \sqcup u_3 \sqcup X_4 \sqcup h_5)\sqcap F.$
This family consists exactly of SGB words matching the pattern.
(d)
Let $V_j = a_j \cup e_j \cup i_j \cup o_j \cup u_j$ denote the family of vowels in position $j$, and let $\overline{V}_j = X_j \setminus V_j$ denote consonants.
A word contains exactly $k$ vowels if we choose a subset $S \subseteq {1,2,3,4,5}$ of size $k$ for vowel positions and force consonants elsewhere. The family is
$$ F_k = \bigcup_{|S|=k}\left(\left(\bigsqcup_{j\in S} V_j\right)\sqcup\left(\bigsqcup_{j\notin S} \overline{V}_j\right)\right)\sqcap F. $$
This expression partitions all words in $F$ by their vowel positions, and the union over $S$ covers all configurations with exactly $k$ vowels.
(e)
A pattern with exactly three specified letters corresponds to choosing three positions $1\le i<j<k\le 5$ and fixing letters at those positions. Such a pattern is determined by a triple
$(x_i,x_j,x_k)\in X_i\times X_j\times X_k.$
A pattern is matched by at least one SGB word exactly when there exists $w\in F$ whose projection onto positions $(i,j,k)$ equals that triple.
Let $\pi_{i,j,k}(F)$ denote the image of $F$ under projection onto coordinates $(i,j,k)$. The set of all valid patterns is
$\bigcup_{1\le i<j<k\le 5} \pi_{i,j,k}(F).$
The required number of patterns is therefore
$$ \sum_{1\le i<j<k\le 5} \left|\pi_{i,j,k}(F)\right|. $$
(f)
A pattern is matched at least twice exactly when some projected triple $(x_i,x_j,x_k)$ has at least two distinct preimages in $F$.
Let $\pi^{-1}_{i,j,k}(t)$ denote the fiber over a triple $t$. The number of patterns matched at least twice is
$$ \sum_{1\le i<j<k\le 5} \left|\left{t\in \pi_{i,j,k}(F);:;|\pi^{-1}_{i,j,k}(t)|\ge 2\right}\right|. $$
(g)
A word remains valid under the substitution $b\mapsto o$ if replacing every occurrence of $b_j$ by $o_j$ yields another element of $F$.
Define the substitution map $\sigma$ on families by replacing each occurrence of $b_j$ with $o_j$. The required set is
$$ F' = {w\in F ;:; \sigma(w)\in F}. $$
Equivalently, for each position $j$, let $\sigma_j$ be the local substitution at position $j$. The condition is
$$ F' = \bigcap_{j=1}^5 \left( (F \setminus b_j) ;\cup; (F \cap b_j \cap \sigma_j^{-1}(F)) \right), $$
which enforces closure under the transformation at every coordinate.
(h)
The quotient $F/V_2$ removes all information contributed by position $2$, collapsing all words that differ only in the second letter into a single projection class.
Thus $F/V_2$ is the family of all length-4 patterns obtained from words in $F$ by deleting position $2$, preserving positions $1,3,4,5$. It represents the induced set of projected strings on ${1,3,4,5}$.
(i)
The expression
$(X_1 \sqcup V_2 \sqcup V_3 \sqcup V_4 \sqcup X_5)\cap F$
selects SGB words whose first and fifth letters are unrestricted, while positions $2,3,4$ are restricted to vowels only.
The second expression
$(X_1 \sqcup X_5)\setminus \bigl((\mathcal P\setminus F)/(V_2 \sqcup V_3 \sqcup V_4)\bigr)$
constructs all words whose first and fifth positions are arbitrary, then removes those patterns that arise as projections of non-SGB words after collapsing vowel-constrained middle positions.
The first expression is a direct structural restriction on $F$. The second expression enforces validity indirectly through quotienting and exclusion of forbidden completions. Both describe subsets of $F$ determined by constraints on positions $2,3,4$, but the first applies constraints before membership testing, while the second applies them after projection and exclusion of non-membership witnesses.
Verification
Each construction uses only operations that preserve membership in the ambient family of 5-letter encodings, so no element outside ${a_j,b_j,\ldots,z_j}$ is introduced.
In parts (a) and (b), the universal families $\mathcal P$ and $X$ contain all encodings used in $F$, so intersection leaves $F$ invariant.
In part (c), the constructed family fixes coordinates exactly as required by the pattern definition, and intersection with $F$ restricts to valid dictionary words, matching the semantics of pattern matching.
In part (d), every word in $F$ has exactly one vowel configuration set $S$, and each such $S$ is counted once in the union over $|S|=k$, so no configurations are omitted or duplicated outside projection equivalence.
In parts (e) and (f), projection $\pi_{i,j,k}$ partitions $F$ into fibers over triples, and counting patterns reduces to counting distinct images and fibers with cardinality constraints, which is well-defined for finite $F$.
In part (g), the substitution condition is enforced pointwise by requiring closure under the map replacing $b_j$ by $o_j$, ensuring that membership is preserved after transformation.
In part (h), quotienting by $V_2$ removes exactly the second coordinate contribution, matching the definition of existential projection in family algebra.
In part (i), both expressions restrict membership relative to $F$ using either direct intersection or projection-exclusion composition, producing subsets determined by identical positional constraints under different algebraic decompositions.
This completes the solution. ∎