4
$\begingroup$

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: CNF lattice DNF 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.
$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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