TAOCP 7.1.1 Exercise 100
Let f(x_1,\ldots,x_n) = [w_1 x_1 + \cdots + w_n x_n \ge t] be a threshold function, where $x_i \in {0,1}$ and $w_i, t \in \mathbb{R}$.
Exercise 100. [20] True or false: If $f(x_1, \ldots, x_n)$ is a threshold function, so are the functions $f(x_1, \ldots, x_n) \wedge x_{n+1}$ and $f(x_1, \ldots, x_n) \vee x_{n+1}$.
Verified: yes
Solve time: 2m
Solution
Let
$$ f(x_1,\ldots,x_n) = [w_1 x_1 + \cdots + w_n x_n \ge t] $$
be a threshold function, where $x_i \in {0,1}$ and $w_i, t \in \mathbb{R}$. Define
$$ W(x) = \sum_{i=1}^n w_i x_i. $$
Since each $x_i \in {0,1}$, the values of $W(x)$ lie in a finite set. Set
$$ S^+ = \sum_{i=1}^n \max(w_i,0), \qquad S^- = \sum_{i=1}^n \min(w_i,0). $$
Then $S^- \le W(x) \le S^+$ for all $x \in {0,1}^n$.
1. The function $f(x_1,\ldots,x_n) \wedge x_{n+1}$
Define $g(x_1,\ldots,x_{n+1}) = f(x_1,\ldots,x_n) \wedge x_{n+1}$. Construct weights
$$ w_i' = w_i \quad (1 \le i \le n), \qquad w_{n+1}' = B, $$
and threshold
$$ t' = S^+ + 1, $$
where
$$ B = S^+ - t + 1. $$
Consider the linear form
$$ W'(x,x_{n+1}) = W(x) + B x_{n+1}. $$
If $x_{n+1} = 0$, then $W'(x,x_{n+1}) = W(x) \le S^+ < S^+ + 1 = t'$, hence $g=0$.
If $x_{n+1} = 1$, then
$$ W'(x,1) \ge t' \iff W(x) + B \ge S^+ + 1 \iff W(x) \ge t. $$
This is equivalent to $f(x_1,\ldots,x_n)=1$, hence equivalent to $g=1$.
Therefore
$$ g(x_1,\ldots,x_{n+1}) = [W'(x,x_{n+1}) \ge t'] $$
is a threshold function.
2. The function $f(x_1,\ldots,x_n) \vee x_{n+1}$
Define $h(x_1,\ldots,x_{n+1}) = f(x_1,\ldots,x_n) \vee x_{n+1}$. Construct weights
$$ w_i' = w_i \quad (1 \le i \le n), \qquad w_{n+1}' = B, $$
and threshold
$$ t' = t, $$
where
$$ B = t - S^-. $$
For $x_{n+1} = 0$, one has $W'(x,0) = W(x)$, hence
$$ h(x,0) = 1 \iff W(x) \ge t, $$
which equals $f(x)$.
For $x_{n+1} = 1$, one has
$$ W'(x,1) = W(x) + B \ge S^- + (t - S^-) = t. $$
Thus $h(x,1)=1$ for all $x$.
Hence
$$ h(x_1,\ldots,x_{n+1}) = [W'(x,x_{n+1}) \ge t'] $$
is a threshold function.
This completes the proof. ∎