# Product of binary Boolean operators

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}).$$

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