I asked this question a day ago on [math.stackoverflow](https://math.stackexchange.com/q/1165234/172301) 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}).$$



Product of binary Boolean operators
$\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](https://en.wikipedia.org/wiki/2-satisfiability), aka Krom formulas. This class of formulas has attracted a lot of attention due to the fact that its satisfiability problem is [efficiently solvable](https://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem) (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:


1. (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$;
2. (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$;
3. (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](https://en.wikipedia.org/wiki/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)$:


1. $G$ is transitive;
2. if there is an edge from a literal $A$ to its negation, there are edges from $A$ to every vertex;
3. 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](https://oeis.org/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](http://www.people.fas.harvard.edu/~sfinch/csolve/posets.pdf) 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.


