Product of binary Boolean operators I asked this question a day ago on math.stackoverflow but figured it could have an interest here.
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).$$
Take for example the case $N=3$.
$$ \phi(p_1, p_2, p_3) = \phi_{12}(p_1, p_2)\wedge\phi_{23}(p_2, p_3)\wedge\phi_{13}(p_1, p_3).$$
There are $16$ choices for each of the three binary operators on the right, but these choices are redundant. Moreover some ternary operators cannot be written this way; for instance if $\phi(p_1,p_2,p_3)=0$ then one can see that necessarily $\phi(\overline{p_1},p_2,p_3)$ or $\phi(p_1,\overline{p_2},p_3)$ or $\phi(p_1,p_2,\overline{p_3})$ should also be $0$ in such a parametrization.
A brute-force search gave me the cardinal of $|\mathcal{P}_3| = 166$ out of $256$ ternary operators and I'm wondering if there is a way to characterize $\mathcal{P_N}$ or compute its cardinal.
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_1, p_2) \wedge \ldots \wedge \phi_{N-1}(p_{N-1}, p_{N}) \wedge \phi_{N}(p_{N}, p_{1}).$$
 A: $\let\ET\bigwedge$I’ll summarize basic facts about the first question already mentioned in the comments, and add some bounds.
First, if we can write $\phi$ as $\ET_{i<j}\phi_{i,j}(x_i,x_j)$, can can expand each $\phi_{i,j}$ as a conjunction of 2-clauses (i.e., disjunctions of two literals $A,B$, which are variables or negated variables), hence boolean functions that can be written in this way are exactly those expressible by 2-CNF, aka Krom formulas. This class of formulas has attracted a lot of attention due to the fact that its satisfiability problem is efficiently solvable (in fact, NL-complete).
In order to identify formulas that express the same function, note that every Krom function $\phi\colon\{0,1\}^n\to\{0,1\}$ can be uniquely written as the conjunction of the set $C_\phi$ of all 2-clauses implied by $\phi(x_1,\dots,x_n)$. This set has the following closure properties:


*

*(resolution) if $C_\phi$ contains $A\lor x_i$ and $B\lor\neg x_i$ for some literals $A,B$, then it also contains $A\lor B$;

*(weakening) if $C_\phi$ contains $A\lor A$ (that is, $A$) for some literal $A$, it also contains $A\lor B$ for every literal $B$;

*(axioms) $C_\phi$ contains all the clauses $x_i\lor\neg x_i$.
(We consider 2-clauses as unordered: $A\lor B$ is the same clause as $B\lor A$.)
Conversely, every set $C$ of 2-clauses with the three closure properties above is of the form $C_\phi$ for some Krom function $\phi$. This follows from the implicational completeness of the resolution proof system with weakening and axioms (which is even true for arbitrary clauses, not just 2-clauses).
A 2-CNF can be represented by its implication graph: a directed graph $(V,E)$ whose vertices are the literals $\{x_1,\dots,x_n,\neg x_1,\dots,\neg x_n\}$, and with a pair of edges $\neg A\to B$ and $\neg B\to A$ for every 2-clause $A\lor B$ from the 2-CNF. A graph is an implication graph of a 2-CNF iff it is skew-symmetric: $A\to B$ is an edge iff $\neg B\to\neg A$ is an edge.
The closure conditions above translate to the following conditions on the implication graph $G=(V,E)$:


*

*$G$ is transitive;

*if there is an edge from a literal $A$ to its negation, there are edges from $A$ to every vertex;

*all self-loops are in the graph.
Thus, Krom functions are in 1–1 correspondence with skew-symmetric graphs with these properties. Note that conditions 1 and 3 together say that the edge relation is a preorder.

For a different characterization, we can identify a boolean function $\phi\colon\{0,1\}^n\to\{0,1\}$ with the boolean relation $\phi^{-1}(1)\subseteq\{0,1\}$. Then $\phi$ is a Krom function if and only if it has the ternary majority function
$$M(x,y,z)=(x\land y)\lor(x\land z)\lor(y\land z)$$
as a polymorphism: that is,
$$\phi(a^i_1,\dots,a^i_n)=1\text{ for $i=1,2,3$}\implies
\phi(M(a^1_1,a^2_1,a^3_1),\dots,M(a^1_n,a^2_n,a^3_n))=1.$$

As for enumeration, it is clear from the description by implication graphs that $|\mathcal P_n|$ (tabulated in OEIS: A109457 ) is related to the number of partial orders (or rather, preorders) on $n$ elements, which is
$$2^{n^2/4+O(n)}$$
by a result of Kleitman and Rothschild (their actual bound is more precise; see here for an overview).
For a lower bound, for any set of pairs $E\subseteq\binom{[n]}2$, we can form the 2-CNF
$$\phi_E(x_1,\dots,x_n)=\ET_{\{i,j\}\in E}(x_i\lor x_j)\land\ET_{i\notin\bigcup E}x_i,$$
and it is easy to see that these formulas define pairwise distinct functions. The purpose of the last conjunct is to make the function depend on all variables; that way, each $\phi_E$ gives rise to $2^n$ different functions by negating some of the variables. Thus,
$$|\mathcal P_n|\ge2^{\binom n2+n}=2^{n^2/2+n/2}.$$
For an upper bound, we need to count the number of skew-symmetric preorders $\le$ on $V=\{x_1,\dots,x_n,\neg x_1,\dots,\neg x_n\}$. I’m ignoring here condition 2, and will only use its consequence that with one exception (${\le}=V\times V$), it is not possible to have $x_i\le\neg x_i\le x_i$ for some $i$.
The standard proof that every finite partial order extends to a linear order can be easily adapted to show that every skew-symmetric partial order extends to a skew-symmetric linear order. For preorders $\le$ as above, this yields that there is a skew-symmetric linear order $\preceq$ such that


*

*the equivalence classes of ${\approx}={\le}\cap{\le}^{-1}$ are $\preceq$-convex,

*the strict order ${\le}\smallsetminus{\le}^{-1}$ is included in $\prec$.
Up to an extra factor of $2^n$, we can assume that $x_i\preceq\neg x_i$ for every $i$, thus $\preceq$ is given by a linear order on $V_0=\{x_1,\dots,x_n\}$, sitting below its reversed copy on $V_1=\{\neg x_1,\dots,\neg x_n\}$. Then, $\le$ is determined by


*

*a preorder ${\le}_0={\le}\restriction V_0$ related to $\preceq$ as above, and

*a skew-symmetric bipartite graph ${\le_1}={\le}\cap(V_0\times V_1)$, which can be identified with an undirected graph (possibly with self-loops) on $V_0$.
There are $2^n-1$ equivalence relations with $\preceq$-convex classes, and $2^{\binom n2}$ subrelations of ${\prec}\restriction V_0$, hence we obtain an elementary bound
$$|\mathcal P_n|\le2^nn!(2^n-1)2^{\binom n2}2^{\binom{n+1}2}=2^{n^2+O(n\log n)}.$$
(One could save a bit on the $2^n$ factors, but there is not much point.) If we count $\le_0$ better using the Kleitman–Rothschild bound, we obtain
$$|\mathcal P_n|\le2^{\frac34n^2+O(n)}.$$
These estimates are wasteful as a they ignore the interaction between $\le_0$ and $\le_1$, i.e., ${\le}_0\circ{\le}_1\subseteq{\le}_1$.
I have every reason to believe the correct exponent is $2^{n^2/2+\dots}$, matching the lower bound. (For example, such a bound holds when the transitive reduction of $\le_0$ is bipartite, which is true for almost all partial orders as also shown by K&R.) However, proving this seems to require an adaptation of the Kleitman&Rothschild proof, which involves an unsightly case analysis.
A: Pending an approved edit, I am thinking of the cardinality of your smaller class of functions,
which cardinality I will call $C_n$.  These are Boolean functions of the form (I think)
$$ \phi(p_1, \ldots, p_N) = \phi_{1}(p_1, p_2) \wedge \ldots \wedge \phi_{N-1}(p_{N-1}, p_{N}) \wedge \phi_{N}(p_{N}, p_{1}).$$
It is clear that $C_2=P_2$ (see other answer) and $C_3=P_3$.  $C_4$ and $C_5$ are a little more challenging, but an upper bound of $2^{4n}$ is obvious, and I suggest a method for
approximating $C_{3k}$ which should give a bead on $C_{3k+i}$.
The idea is to rewrite the function as a conjunction of $k$ groups which partitions the variables into groups of 3, with $k$ additional conjuncts $\phi_{3j}(x_{3j},x_{3j+1})$ which members do not share any variables. $\phi_{3j+1}(x_{3j+1},x_{3j+2}) \wedge \phi_{3j+2}(x_{3j+2},x_{3j+3})$ has 81 possible values as a function of three variables by the analysis in the other post, and so there are an upper bound of $(81*16)^k$ which refines the obvious upper bound by more than $(1/3)^k$.  Since the conjunct of the groups of 3 provably has $81^k$ different values and the conjunct of the remainder has provably $16^k$ different values, it suggests that the upper bound is not far from the true value of $C_n$.  For $n$ not a multiple of 3, multiply by 16 or 81 as needed.
Gerhard "What Comes Around, Goes Around" Paseman, 2015.02.27
A: I will be surprised if you can find a closed form for the cardinality of your set of functions; I will write this cardinality as $P_n$.
However, there is a quick upper bound which may be a good estimate of the order of growth of $P_n$.  Order the variables (as you have done), fix $x_n$ and consider the conjunction over $i \lt n$ of $\phi(x_i,x_n)$.  This conjunction can be written as $(x_n \wedge \phi_1) \vee (\neg x_n \wedge \phi_2)$, where $\phi_1$ and $\phi_2$ are identically 0 or 1 or else a conjunction of a subset of the literals, with some of them possibly negated.  This gives a count of $3^{2(n-1)}$ on the number of functions that can be represented in this form.  Your full expression is a conjunction of $n$ of these expressions, which has a rough upper bound of $3^{n(n-1)}$.
I don't have a lower bound better than $3^{2(n-1)}$ at present, but I suspect the growth is exponential in $n^2$.
Gerhard "Likes Doing Easy Counting Problems" Paseman, 2015.02.26
