TAOCP 7.1.1 Exercise 95
**Answer: True.
Exercise 95. [M25] [M25] True or false: The set of all outputs produced by a comparator-inverter network, when the inputs range over all possible bit strings, is always a median set.
Verified: yes
Solve time: 2m30s
Answer: True.
Let $f : {0,1}^n \to {0,1}^m$ be the function computed by a comparator-inverter network, and let $X = f({0,1}^n)$.
We show that $X$ is closed under the median (majority) operation
$$ \mu(a,b,c)_i = (a_i \wedge b_i)\ \vee\ (b_i \wedge c_i)\ \vee\ (c_i \wedge a_i), $$
applied coordinatewise.
1. Median algebra structure on ${0,1}^k$
On ${0,1}^k$, the operation $\mu$ is defined coordinatewise from the Boolean majority operation. It is a standard fact that ${0,1}$, equipped with $\mu$, forms a median algebra, and products ${0,1}^k$ inherit this structure coordinatewise.
A map is a median homomorphism if it preserves $\mu$:
$$ g(\mu(x,y,z)) = \mu(g(x),g(y),g(z)). $$
2. Each gate preserves the median operation
We check the two types of gates.
(a) Comparator gate
A comparator sends $(x,y)$ to $(x \wedge y, x \vee y)$.
Both $\wedge$ and $\vee$ are lattice operations on ${0,1}$. In a distributive lattice, the median operation satisfies
$$ \mu(a,b,c) = (a \wedge b)\ \vee\ (b \wedge c)\ \vee\ (c \wedge a), $$
so any lattice term operation preserves $\mu$. Since $\wedge$ and $\vee$ are term operations in the distributive lattice ${0,1}$, each coordinate function of the comparator preserves $\mu$, hence the whole comparator gate preserves $\mu$.
(b) Inverter gate
Let $\neg x = 1-x$. We verify directly:
$$ \mu(\neg a,\neg b,\neg c) = (\neg a \wedge \neg b)\ \vee\ (\neg b \wedge \neg c)\ \vee\ (\neg c \wedge \neg a). $$
Using De Morgan laws,
$$ \neg a \wedge \neg b = \neg(a \vee b), $$
so
$$ \mu(\neg a,\neg b,\neg c) = \neg(a \vee b)\ \vee\ \neg(b \vee c)\ \vee\ \neg(c \vee a). $$
Taking complements and using symmetry of majority, this simplifies to
$$ \mu(\neg a,\neg b,\neg c) = \neg\big((a \wedge b)\ \vee\ (b \wedge c)\ \vee\ (c \wedge a)\big) = \neg \mu(a,b,c). $$
Hence
$$ \neg \mu(a,b,c) = \mu(\neg a,\neg b,\neg c), $$
so negation is a median homomorphism.
Thus both comparator and inverter gates preserve the median operation.
3. Closure under composition
Since each gate is a median homomorphism, any composition of such gates is also a median homomorphism. Therefore the network function $f$ satisfies
$$ f(\mu(x,y,z)) = \mu(f(x),f(y),f(z)) \quad \text{for all } x,y,z \in {0,1}^n. $$
4. Image is a median set
Let $u,v,w \in X$. Then there exist $a,b,c \in {0,1}^n$ such that
$$ f(a)=u,\quad f(b)=v,\quad f(c)=w. $$
Using the homomorphism property,
$$ \mu(u,v,w) = \mu(f(a),f(b),f(c)) = f(\mu(a,b,c)) \in X. $$
Thus $X$ is closed under $\mu$.
Conclusion
The set of all outputs of a comparator-inverter network is closed under the median operation. Therefore it is always a median set.
$$ \boxed{\text{True}} $$