Lower bound of DNF terms count for some symmetric boolean function

85 Views Asked by At

Consider boolean function $s_n^{[r,\,n - r]}\colon \{0,1\}^n\rightarrow\{0,1\}$ defined as follows:

$$ s_n^{[r,\,n - r]}(x_1, ..., x_n) = 1 \iff |\{x_i: x_i = 1\}| \in [r,\,n - r] $$

(in other words, $\small s_n^{[r,\,n - r]}(x) = 1$ iff $\small r \leq x_1 + \cdots + x_n \leq n - r$)

The question is how to find a minimal possible count of terms (conjunctions, $\vee$) in disjunctive normal form (DNF) of $s_n^{[r,\,n - r]}$ for particular $n$ and $r$.


My own thoughts on it:

  1. This function is obviously symmetric, i.e. any permutation of its input arguments $x_i$ don't change the value of function.

  2. I've found DNF for $s_n^{[r,\,n - r]}$ with exactly $\binom {n}{2r}\binom {2r}{r}$ terms in it:

    $$\large s_n^{[r,\,n - r]} = \bigvee_{\substack{1 \leqslant i_1 < \,\cdots\, < i_{2r} \leqslant n \\ \sigma_1 + \,\cdots\, + \sigma_{2r} =r }} x_{i_1}^{\sigma_1} \cdots x_{i_{2r}}^{\sigma_{2r}}. $$

    (Here $x^\sigma$ notation means $x$ if $\sigma = 1$ and $\overline{x}$ if $\sigma = 0$)

    But this DNF obviously don't provide a lower bound for the count of terms.

    For example, for $s_3^{[1,2]}$ (i.e. $\small n = 3, r = 1$) this formula yields DNF with 6 terms:

    $$s_3^{[1,2]} = x_1 \overline{x_2} \vee x_1 \overline{x_3} \vee x_2 \overline{x_3} \vee \overline{x_1} x_2 \vee \overline{x_1} x_3 \vee \overline{x_2} x_3.$$

    But there are DNFs for $s_3^{[1,2]}$ consisting of the lesser count of terms (3 terms): $$ s_3^{[1,2]} = x_1 \overline{x_2} \vee x_2 \overline{x_3} \vee \overline{x_1} x_3,\quad s_3^{[1,2]} = x_1 \overline{x_3} \vee x_1 \overline{x_2} \vee \overline{x_2} x_3. $$