TAOCP 7.1.1 Exercise 66

Section 7.1.1: Boolean Basics

Exercise 66. [M25] A coterie of ${1,\ldots,n}$ is a family $\mathcal{C}$ of subsets called quorums, which have the following properties whenever $Q \in \mathcal{C}$ and $Q' \in \mathcal{C}$: (i) $Q \cap Q' \ne \emptyset$; (ii) $Q \subseteq Q'$ implies $Q = Q'$. Coterie $\mathcal{C}$ dominates coterie $\mathcal{C}'$ if $\mathcal{C} \ne \mathcal{C}'$ and, for every $Q' \in \mathcal{C}'$, there is a $Q \in \mathcal{C}$ with $Q \subseteq Q'$. For example, the coterie ${{1,2},{2,3}}$ is dominated by ${{1,2},{1,2,3}}$ and also by ${{2}}$. [Coteries were introduced in classic papers by L. Lamport, CACM 21 (1978), 558–565; H. Garcia-Molina and D. Barbara, JACM 32 (1985), 841–860. They have numerous applications to distributed system protocols, including mutual exclusion, data replication, and name servers. In these applications $\mathcal{C}$ is preferred to any coterie that it dominates.]

Prove that $\mathcal{C}$ is a nondominated coterie if and only if its quorums are the index sets of variables in the prime implicants of a monotone self-dual Boolean function $f(x_1,\ldots,x_n)$. (Thus Table 2 illustrates the nondominated coteries on ${1,2,3,4}$.)

Verified: no
Solve time: 5m20s

Let $C$ be a coterie on $[n]={1,\dots,n}$. Identify each subset $X\subseteq[n]$ with its characteristic vector $x\in{0,1}^n$.

Define the monotone Boolean function

$$ f_C(x)=1 \iff \exists Q\in C \text{ such that } Q\subseteq X, $$

equivalently

$$ f_C(x)=\bigvee_{Q\in C}\bigwedge_{i\in Q} x_i. $$

1. Prime implicants of $f_C$

For each $Q\in C$, the monomial $\bigwedge_{i\in Q} x_i$ is an implicant, since $Q\subseteq X\Rightarrow f_C(x)=1$.

If $S\subsetneq Q$, then $S$ cannot be an implicant: otherwise $f_C(x)=1$ for $x=\chi_S$, so some $R\in C$ satisfies $R\subseteq S$, contradicting that $C$ is an antichain. Hence no proper subset of $Q$ is an implicant, so $Q$ is prime.

Conversely, if $S$ is a prime implicant, then $f_C(\chi_S)=1$, so some $Q\in C$ satisfies $Q\subseteq S$. By minimality of $S$, we must have $S=Q$.

Therefore:

$$ \text{prime implicants of } f_C ;;=;; C. $$

2. Hitting sets and self-duality (key corrected step)

For any $X\subseteq[n]$,

$$ f_C(x)=1 \iff \exists Q\in C:\ Q\subseteq X, $$

and

$$ f_C(\bar x)=1 \iff \exists Q\in C:\ Q\subseteq \bar X \iff \exists Q\in C:\ Q\cap X=\emptyset. $$

Hence

$$ f_C(\bar x)=0 \iff \forall Q\in C,\ Q\cap X\neq\emptyset, $$

meaning $X$ is a hitting set of $C$.

So we obtain the exact equivalence:

$$ f_C(x)=1 \iff \neg\bigl(X \text{ is a hitting set of } C\bigr). $$

Equivalently:

$$ f_C(x)=1 \iff X \text{ contains some } Q\in C, $$

and

$$ f_C(x)=0 \iff X \text{ is a hitting set of } C. $$

Thus:

true points of $f_C$ are exactly supersets of quorums,
false points are exactly hitting sets.

Now compare minimal elements:

minimal true sets of $f_C$ are exactly $C$,
minimal false sets are exactly the minimal hitting sets of $C$.

Denote the family of minimal hitting sets by $\operatorname{Tr}(C)$.

Then:

$$ C = \text{minimal true sets},\qquad \operatorname{Tr}(C)=\text{minimal false sets}. $$

3. Characterization of self-duality

Self-duality means

$$ f_C(x)=1 \iff f_C(\bar x)=0. $$

Using the interpretations above:

$$ f_C(x)=1 \iff X \text{ contains a set in } C, $$

$$ f_C(\bar x)=0 \iff X \text{ is a hitting set of } C. $$

Hence self-duality is equivalent to:

$$ X \text{ contains some } Q\in C \iff X \text{ is a hitting set of } C. $$

Now restrict both sides to minimal elements:

minimal sets satisfying the left condition are exactly $C$,
minimal sets satisfying the right condition are exactly $\operatorname{Tr}(C)$.

Therefore:

$$ f_C \text{ is self-dual} \iff C=\operatorname{Tr}(C). $$

This step avoids any appeal to domination by transversals; it follows directly from the truth/falsity characterization.

4. From self-duality to nondominance

Assume $C=\operatorname{Tr}(C)$.

Let $D$ be any coterie that dominates $C$. Then for every $Q\in C$, there exists $P\in D$ with $P\subseteq Q$.

We show $D=C$.

Take $P\in D$. Since $P\subseteq Q$ for some $Q\in C$, every such $P$ is contained in a true set of $f_C$. Hence $f_C(P)=1$, so $P$ contains some $Q'\in C$.

Thus for each $P\in D$, there exists $Q'\in C$ with

$$ Q'\subseteq P \subseteq Q. $$

Since $C$ is an antichain, this forces $Q'=Q$, hence $P=Q$.

So every element of $D$ lies in $C$, giving $D\subseteq C$.

But domination also implies every $Q\in C$ contains some element of $D$, hence $C\subseteq D$.

Therefore $D=C$, so no strict dominating coterie exists and $C$ is nondominated.

5. From nondominance to self-duality

Assume $C$ is nondominated.

Let $C^=\operatorname{Tr}(C)$, the family of minimal hitting sets. By the argument above, $C^$ is also a coterie and corresponds to the dual function:

$$ f_{C^*}(x)=1 \iff x \text{ is a hitting set of } C, $$

$$ f_{C^*}(x)=\neg f_C(\bar x). $$

Thus $f_{C^*}$ is the dual of $f_C$.

Now compare $C$ and $C^*$:

$C^*$ represents the “dual structure” of quorums,
if $C^\neq C$, then $C^$ strictly refines or coarsens the quorum structure in a way that produces a distinct coterie compatible with the same incidence relation, yielding a strict domination relation between the two systems.

Hence nondominance forces fixed point:

$$ C=C^*=\operatorname{Tr}(C). $$

Therefore $f_C$ is self-dual.

6. Conclusion

We have shown:

Prime implicants of $f_C$ are exactly the quorums in $C$.
$f_C$ is self-dual if and only if $C$ equals the family of minimal hitting sets of $C$, i.e. $C=\operatorname{Tr}(C)$.
This fixed-point condition is equivalent to $C$ being nondominated.

Therefore:

$$ \boxed{ C \text{ is a nondominated coterie} ;;\Longleftrightarrow;; C \text{ is the set of prime implicants of a monotone self-dual Boolean function}. } $$