<p>OK so, more than one year later, here is the answer to this. We'll see Boolean valuations <span class="math-container">$\nu$</span> as the set of variables that are mapped to <span class="math-container">$1$</span>.</p>

<p>We can show that <span class="math-container">$\mu_\text{cnf}(\hat{0},\hat{1}) = (-1)^k \mu_\text{dnf}(\hat{0},\hat{1}) =  \sum_{\nu \models \phi} (-1)^{|\nu|}$</span>.
In the literature, the quantity <span class="math-container">$\sum_{\nu \models \phi} (-1)^{|\nu|}$</span> is also called the <em>Euler characteristic of <span class="math-container">$\phi$</span></em>.</p>

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

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

<p>Define the functions <span class="math-container">$f,g: L_{\text{cnf}} \to \mathbb{N}$</span> by:</p>

<ul>
<li><span class="math-container">$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)$</span>; in other words the total mass of the valuations that do not satisfy <em>exactly</em> the (disjunctive) clauses <span class="math-container">$C_i$</span> for <span class="math-container">$i \in \mathbf{s}$</span>.</li>
<li><span class="math-container">$g(d_\mathbf{s}) = M_w \left( \lnot \bigvee_{i \in \mathbf{s}} C_i \right)$</span>; in other words the total mass of the valuations that do not satisfy <em>at least</em> the clauses <span class="math-container">$C_i$</span> for <span class="math-container">$i \in \mathbf{s}$</span>.</li>
</ul>

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

CC BY-SA 4.0
2019-04-01T20:09:17.830Z
2019-04-01T20:09:17.830Z
M.Monet
<p>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)$).</p>

<p>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$.</p>

<p>We define the <em>CNF lattice</em> $(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$.</p>

<p>We define similarly the <em>DNF lattice</em> $(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.</p>

<p>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 <a href="https://dl.acm.org/citation.cfm?id=2124415" rel="nofollow noreferrer">Enumerative Combinatorics</a> for a definition of that function.</p>

<p><strong>Example:</strong>
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$):</p>

<p>CNF lattice:
<a href="https://i.sstatic.net/xqjy6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xqjy6.png" alt="CNF lattice"></a>
DNF lattice:
<a href="https://i.sstatic.net/6XNx4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6XNx4.png" alt="DNF lattice"></a></p>

<p><strong>QUESTION:</strong> 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.</p>

<p><strong>What I know</strong>:</p>

<ul>
<li>First, I know that it does no matter if we start from minmized expressions or not, thanks to the <em>crosscut theorem</em> (see Corollary 3.9.4 of <a href="https://dl.acm.org/citation.cfm?id=2124415" rel="nofollow noreferrer">Enumerative Combinatorics</a>, for instance);</li>
<li>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;</li>
<li>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.</li>
</ul>

<boolean-functions><combinatorics><lattice>
Möbius values of CNF and DNF lattices of a monotone Boolean function
M.Monet
# Möbius values of CNF and DNF lattices of a monotone Boolean function

(Asked by: username_0 on 2017-12-13)

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](https://dl.acm.org/citation.cfm?id=2124415) 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](https://i.sstatic.net/xqjy6.png)](https://i.sstatic.net/xqjy6.png)
DNF lattice:
[![DNF lattice](https://i.sstatic.net/6XNx4.png)](https://i.sstatic.net/6XNx4.png)

**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](https://dl.acm.org/citation.cfm?id=2124415), 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.

**Tags:** boolean-functions, combinatorics, lattice

---

## 1 answers

### Answer by username_0 on 2019-04-01. Score: 2 | Accepted answer

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


---

