6
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ $\mathcal P_N$ should be $1$ (for the constant $0$ function) plus the number of transitive implication graphs (en.wikipedia.org/wiki/Implication_graph) with no directed cycle containing a literal and its negation. See en.wikipedia.org/wiki/2-satisfiability for more background information. $\endgroup$ Feb 26, 2015 at 16:15
  • 2
    $\begingroup$ That’s not quite right: the correct description is that such functions correspond to transitive implication graphs with the property that if there is an edge from a literal $\ell$ to its negation, then there are edges from $\ell$ to all nodes. On an unrelated note, a characterization I don’t see mentioned on the WP page is that $\phi(x_1,\dots,x_N)$ can be written in this way iff the ternary majority function is a polymorphism of the relation $\phi^{-1}(1)\subseteq\{0,1\}^N$. $\endgroup$ Feb 26, 2015 at 17:09
  • 2
    $\begingroup$ oeis.org/A109457 $\endgroup$ Feb 26, 2015 at 20:03

3 Answers 3

3
$\begingroup$

$\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:

  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: 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 ) 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.

$\endgroup$
1
  • $\begingroup$ Great references and explanations, thanks! Regarding the smaller class of functions, @GerhardPaseman answer gave a nice suggestion for a recurrence, I'll try this idea. $\endgroup$
    – Maxim
    Mar 2, 2015 at 12:01
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Of course, there is also an obvious lower bound of $2^{4j}$, where $j$ is floor of $n/2$. However, this class may yield to an exact enumeration, if not a closed form for $C_n$. Gerhard "Good Lower Bounds Often Hard" Paseman, 2015.02.27 $\endgroup$ Feb 27, 2015 at 18:48
  • $\begingroup$ I've just realized that the above counts nonzero such functions; the representation ignores the identically zero boolean function $(x_1 \wedge \neg x_1)$. Of course, this only adds 1 to the count, but care should be taken by the reader to see that no other details or functions are missing from the analysis. Gerhard "And Thanks For The Upvote" Paseman, 2015.03.02 $\endgroup$ Mar 2, 2015 at 19:49
0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ I am not as familiar as I should be with the enumeration problems of circuits. You are counting circuits with $n$ inputs and a specific layout: an AND of $n \choose 2$ specific gates. It is possible that this has been counted and is present in the computer science or electrical engineering literature. "switching circuit enumeration" might be a useful search phrase for you. Gerhard "Using A Programmable Logic Device" Paseman, 2015.02.26 $\endgroup$ Feb 26, 2015 at 19:07
  • $\begingroup$ The order of growth is $2^{n^2/4+O(n\log n)}$. This follows from similar known bounds on the number of partial orders. $\endgroup$ Feb 26, 2015 at 20:12
  • $\begingroup$ Good! Are the known bounds on the number of partial orders easy to demonstrate? Gerhard "Likes Things Easy To Order" Paseman, 2015.02.26 $\endgroup$ Feb 26, 2015 at 20:15
  • $\begingroup$ As far as I can see, a $2^{n^2/4}$ lower bound, and an $n!2^{n^2/2}$ upper bound, are trivial. See e.g. people.fas.harvard.edu/~sfinch/csolve/posets.pdf for better bounds; I don’t know how difficult it is to prove at least a weak form (say, $2^{(1/4+o(1))n^2}$) of the Kleitman and Rothschild upper bound. $\endgroup$ Feb 26, 2015 at 20:45
  • $\begingroup$ Hmm. But I messed up the reduction from Krom functions to partial orders, so the bound above doesn’t apply to the original problem. It is actually something between $2^{n^2/2}$ and $2^{n^2}$ (ignoring lower order terms). $\endgroup$ Feb 26, 2015 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.