I'm interested in the set $\mathcal{P}_N$ of boolean functions of boolean variables $p_1, p_2, \ldots, p_N$ that can be written as products of operators of 2 variables only:

$$ \phi(p_1, \ldots, p_N) = \bigwedge\limits_{i<j} \phi_{ij}(p_i, p_j).$$

How can this set, or its cardinal, be characterized ?

Obviously $|P_2| = 16$, and a brute-force search gave me $|P_3| = 166$ out of $256$ ternary operators.

Incidentally I'm also interested in the more restricted set of functions $\mathcal{C}_N$ that can be written as a cycle like

$$ \phi(p_1, \ldots, p_N) = \phi_{1}(p_i, p_{i+1}) \wedge \ldots \wedge \phi_{1}(p_{N-1}, p_{N}) \wedge \phi_{N}(p_{N}, p_{1}).$$

  • 1
    $\begingroup$ I asked this question on Mathoverflow and there is an ongoing discussion there. $\endgroup$ – Maxim Feb 27 '15 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.