Möbius values of CNF and DNF lattices of a monotone Boolean function

Question

Let $\phi$ be a monotone Boolean function on a set of variables $\langle k \rangle := \{0,\ldots,k\}$ such that $\phi$ depends on all the variables in $\langle k \rangle$ (that is, for every variable $x \in \langle k \rangle$, there is a valuation $\nu: \langle k \rangle \setminus \{x\} \to \{\top,\bot \}$ such that $\phi(\nu \cup x \mapsto \top) \neq \phi(\nu \cup x \mapsto \bot)$).

Let $F_{\text{cnf}} = C_0 \land \ldots \land C_n$ be the (unique) minimized CNF representing $\phi$, where we see each clause simply as the set of variables that it contains. For $\mathbf{s} \subseteq \langle n \rangle$, define $d_{\mathbf{s}} := \bigcup\limits_{i \in \mathbf{s}} C_i$. Note that we can have $d_\mathbf{s} = d_\mathbf{s'}$ for $\mathbf{s} \neq \mathbf{s'}$. Further notice that $d_\emptyset = \emptyset$.

We define the CNF lattice $(L_{\text{cnf}},\leq)$ of $\phi$ as the lattice with underlying set $L_\text{cnf} = \{ d_\mathbf{s} \mid \mathbf{s} \subseteq \langle n \rangle \}$, and where $\leq$ is reversed set inclusion (i.e, $d_\mathbf{s} \leq d_\mathbf{s'}$ iff $d_\mathbf{s'} \subseteq d_\mathbf{s}$). The top element $\hat{1}$ of that lattice is then $\emptyset$, while its bottom element $\hat{0}$ is $\langle k \rangle$.

We define similarly the DNF lattice $(L_{\text{dnf}},\leq)$ of $\phi$, where instead of $F_{\text{cnf}}$ we use $F_{\text{dnf}} = D_0 \lor \ldots \lor D_m$, the unique minimized DNF representing $\phi$. Observe that we have again $\emptyset$ as the top element and $\langle k \rangle$ as the bottom element.

Now, let $\mu_\text{cnf}: L_{\text{cnf}} \times L_{\text{cnf}} \to \mathbb{Z}$ be the Möbius function of the CNF lattice of $\phi$ (resp., $\mu_\text{dnf}$ the Möbius function of its DNF lattice). See, for instance, 3.7 of Enumerative Combinatorics for a definition of that function.

Example: Let $\phi$ be the monotone Boolean function on variables $\langle 4 \rangle$ defined by the CNF $F_\text{cnf} = (3 \lor 4) \land (0 \lor 4) \land (0 \lor 1 \lor 2)$. You can check that its corresponding DNF is $F_\text{dnf} = (0 \land 3) \lor (0 \land 4) \lor (2 \land 4) \lor (1 \land 4)$. The Hasse diagrams of the CNF and DNF lattices of $\phi$, together with the values $\mu(e,\hat{1})$ for each element $e$ of the lattices, are drawn below (where, e.g., "034: 1" means that it is element $e=\{0,3,4\}$ and we have $\mu(e,\hat{1})=1$):

CNF lattice: DNF lattice:

QUESTION: Is it always the case that $\mu_\text{cnf}(\hat{0},\hat{1})=0$ if and only if $\mu_\text{dnf}(\hat{0},\hat{1})=0$? I know a proof of this conditionally to FP $\neq$ #P (which is beyond our scope here), but I would like to prove it unconditionally.

What I know:

• First, I know that it does no matter if we start from minmized expressions or not, thanks to the crosscut theorem (see Corollary 3.9.4 of Enumerative Combinatorics, for instance);
• Second, using the Möbius inversion formula on the lattices to count the number of satisfying valuations $\#\phi$ of $\phi$, I can easily show that $\#\phi$ is even iff $\mu_\text{cnf}(\hat{0},\hat{1})$ and $\mu_\text{dnf}(\hat{0},\hat{1})$ are both even, so that they have the same parity;
• Third, I coded a little something to generate all monotone functions that depend on all their variables $\langle k \rangle$, up to $k=5$ (and there are a lot of them!) and tested my question. I found out that in fact I always had $|\mu_\text{cnf}(\hat{0},\hat{1})| = |mu_\text{dnf}(\hat{0},\hat{1})|$. Moreover I have cases where the signs are the same, and cases where they are opposite.

Answer 1

OK so, more than one year later, here is the answer to this. We'll see Boolean valuations $\nu$ as the set of variables that are mapped to $1$.

We can show that $\mu_\text{cnf}(\hat{0},\hat{1}) = (-1)^k \mu_\text{dnf}(\hat{0},\hat{1}) = \sum_{\nu \models \phi} (-1)^{|\nu|}$. In the literature, the quantity $\sum_{\nu \models \phi} (-1)^{|\nu|}$ is also called the Euler characteristic of $\phi$.

I'll only show that $\mu_\text{cnf}(\hat{0},\hat{1}) = \sum_{\nu \models \phi} (-1)^{|\nu|}$, because the proof is similar for $\mu_\text{dnf}(\hat{0},\hat{1}) = (-1)^k \sum_{\nu \models \phi} (-1)^{|\nu|}$.

Let $w \in \mathbb{R}$ be a weight. Define the mass of a valuation $\nu$ under $w$ as $m_w(\nu) = w^{|\nu|} (1-w)^{|\langle k \rangle \setminus \nu|}$, and the mass of $\phi$ under $w$ as $M_w(\phi) = \sum_{\nu \models \phi} m_w(\nu)$. (when $w \in [0,1]$ this can be seen as a probability.)

Define the functions $f,g: L_{\text{cnf}} \to \mathbb{N}$ by:

• $f(d_\mathbf{s}) = M_w \left( (\lnot \bigvee_{i \in \mathbf{s}} C_i) \land \bigwedge_{i \in \langle k \rangle \setminus \mathbf{s}} C_i \right)$; in other words the total mass of the valuations that do not satisfy exactly the (disjunctive) clauses $C_i$ for $i \in \mathbf{s}$.
• $g(d_\mathbf{s}) = M_w \left( \lnot \bigvee_{i \in \mathbf{s}} C_i \right)$; in other words the total mass of the valuations that do not satisfy at least the clauses $C_i$ for $i \in \mathbf{s}$.

We have $g(x) = \sum_{u \leq x} f(u)$ for all $x \in L_{\text{cnf}}$. So by Möbius inversion formula $f(x) = \sum_{u \leq x} \mu_\text{cnf}(u,x) g(u)$. Moreover, for $u = d_\mathbf{s} \in L_\text{cnf}^\phi$, we have that $g(u) = (1 - w)^{|d_\mathbf{s}|}$. Now, since $M_w(\phi) = f(\hat{1})$ are the same polynomials in $w$, by identifying the coefficients of $w^{k+1}$ we get that $\mu_\text{cnf}(\hat{0},\hat{1}) = \sum_{\nu \models \phi} (-1)^{|\nu|}$.