47 The EXACT functions

We define the functions ${\mathrm{EXACT}}_k^n:\{0,1{\}}^n\to \{0,1\}$ by:

$${\mathrm{EXACT}}_k^n(x_1,\cdots ,x_n)=1⟺\text{precisely }k\text{ of }{x}_1,\cdots ,x_n\text{ are }1$$

Note that these functions satisfy the following recurrence:

$${\mathrm{EXACT}}_k^n(x_1)=\{\begin{array}{l}\neg x_{1}k=0\\ x_{1}k=1\\ x_1\wedge \neg x_1\text{ otherwise}\end{array}$$

${\mathrm{EXACT}}_k^{n+1}(\overrightarrow{x},x_{n_1})=(x_{n+1}\wedge {\mathrm{EXACT}}_{k-1}^n\overrightarrow{(}x)\vee \neg x_{n+1}\wedge {\mathrm{EXACT}}_k^n\overrightarrow{(}x))$