TAOCP 7.1.2 Exercise 56

Exercise 56. ▶ [16] [16] Explain why all functions with 14 or more don't-cares in Table 3 have cost 0.

Verified: yes
Solve time: 1m38s

Solution

A 4-variable Boolean function is represented by a truth table of length $16$. A function with $14$ or more don't-cares has at most $2$ specified entries.

Let $f$ be such a partial function. Let the specified inputs be $a, b \in {0,1}^4$, with required values $f(a)$ and $f(b)$ whenever both are specified.

Table 1 shows that the functions of cost $0$ are exactly the $10$ functions consisting of the constants $0,1$ and the literals $x_i, \bar{x}_i$ for $1 \le i \le 4$. Hence it suffices to show that among these $10$ functions there is one that agrees with every specification.

If no input is specified, any constant function $0$ or $1$ extends $f$, so the cost is $0$.

If exactly one input $a$ is specified with value $f(a)=0$, the constant $0$ function is consistent. If $f(a)=1$, then since $a$ is a single point in ${0,1}^4$, some literal $x_i$ or $\bar{x}_i$ takes value $1$ at $a$, so one of the cost-$0$ functions matches the specification at $a$.

Assume two distinct inputs $a \ne b$ are specified. If $f(a)=f(b)$, the constant function with that value satisfies both constraints.

If $f(a) \ne f(b)$, then $a$ and $b$ differ in at least one coordinate, so there exists $i$ with $a_i \ne b_i$. If $a_i=1$ and $b_i=0$, then $x_i$ takes distinct values on $a$ and $b$ and can be chosen so that $x_i(a)=f(a)$ and $x_i(b)=f(b)$ or, if necessary, $\bar{x}_i$ achieves the same assignment. Thus one of the literals $x_i$ or $\bar{x}_i$ matches both specified values.

In all cases a function of cost $0$ extends the given partial specification. Therefore every function with at most $2$ specified entries, equivalently with $14$ or more don't-cares, has cost $0$.

This completes the proof. ∎