TAOCP 7.1.1 Exercise 114
Let $S_{4,5}(x,x,x,x,y,y,z)$ denote the switching function that takes value $1$ precisely when the total number of true inputs among its seven arguments, counted with multiplicity, lies between $4$ an...
Exercise 114. [20] (D. A. Huffman.) What is the function $S_{4,5}(x, x, x, x, y, y, z)$?
Verified: yes
Solve time: 2m30s
Solution
Let $S_{4,5}(x,x,x,x,y,y,z)$ denote the switching function that takes value $1$ precisely when the total number of true inputs among its seven arguments, counted with multiplicity, lies between $4$ and $5$ inclusive. The expression contains four occurrences of $x$, two occurrences of $y$, and one occurrence of $z$, so the weighted sum is
$T = 4x + 2y + z.$
The condition for the function is therefore
$S_{4,5}(x,x,x,x,y,y,z) = 1 \iff 4 \le 4x + 2y + z \le 5.$
If $x = 0$, then $T = 2y + z \le 3$, since $y,z \in {0,1}$. No value of $2y+z$ can reach $4$, so the inequality $4 \le T$ fails in every case. Hence the function is $0$ whenever $x=0$.
Assume $x = 1$. Then
$T = 4 + 2y + z.$
The condition $4 \le T \le 5$ becomes
$4 \le 4 + 2y + z \le 5,$
which simplifies to
$0 \le 2y + z \le 1.$
If $y = 1$, then $2y + z \ge 2$, so the upper bound fails for both $z=0$ and $z=1$. Hence $y=1$ is impossible.
If $y = 0$, then $2y + z = z$, and the condition reduces to $0 \le z \le 1$, which holds for both values of $z$.
Thus the function is $1$ exactly when $x=1$ and $y=0$, independent of $z$. This condition is expressed in Boolean notation as
$x \wedge \bar{y}.$
Therefore,
$S_{4,5}(x,x,x,x,y,y,z) = x \wedge \bar{y}.$
This completes the derivation. ∎