TAOCP 7.1.1 Exercise 98
Working
Exercise 98. [M25] Prove that any self-dual threshold function can be expressed in the form
$$f(x_1, x_2, \ldots, x_n) = [v_1 y_1 + \cdots + v_n y_n > 0],$$
where each $y_i$ is either $x_i$ or $\bar{x}_i$. For example, $2x_1 + 3x_2 + 5x_3 + 7x_4 + 11x_5 + 13x_6 \ge 21$ if and only if $2x_1 + 3x_2 + 5x_3 + 7x_4 + 11x_5 - 13\bar{x}_6 > 0$.
Verified: no
Solve time: 4m09s
Working