<p>Observe that if a <span class="math-container">$k$</span>-CNF <span class="math-container">$\Phi$</span> is equivalent to an <span class="math-container">$l$</span>-DNF <span class="math-container">$\Psi$</span>, then every term of <span class="math-container">$\Psi$</span> implies every clause of <span class="math-container">$\Phi$</span>, i.e., they share a literal.</p>
<p>If the Boolean function is not constant, pick a clause <span class="math-container">$C$</span> in <span class="math-container">$\Phi$</span> and query all its variables. This is a decision tree of depth at most <span class="math-container">$k$</span>. For each branch, restrict <span class="math-container">$\Phi$</span> and <span class="math-container">$\Psi$</span> by the partial assignment determined by the branch.</p>
<p>Each such restriction turns <span class="math-container">$\Psi$</span> into an <span class="math-container">$(l-1)$</span>-DNF: if <span class="math-container">$D$</span> is any term of <span class="math-container">$\Psi$</span>, let <span class="math-container">$x$</span> be a literal shared by <span class="math-container">$C$</span> and <span class="math-container">$D$</span>; if <span class="math-container">$x$</span> is false, then <span class="math-container">$D$</span> is falsified, otherwise it is shortened by at least one literal.</p>
<p>Thus, the function becomes constant on each branch after at most <span class="math-container">$l$</span> iterations of this process.</p>

CC BY-SA 4.0
2023-03-23T11:34:30.537Z
2023-03-23T11:34:30.537Z
Emil Jeřábek
<p>I have seen it stated that if boolean function <span class="math-container">$f$</span> is computable by a <span class="math-container">$k$</span>-CNF and an <span class="math-container">$l$</span>-DNF then it can be computed by a decision tree of depth at most <span class="math-container">$kl$</span>. However, I am not able to see why this is the case.</p>

<boolean-functions><boolean-formulas><decision-trees>
If boolean function $f$ is computable by a k-CNF and an l-DNF then it can be computed by a decision tree of depth at most kl
TheCollegeStudent
# If boolean function $f$ is computable by a k-CNF and an l-DNF then it can be computed by a decision tree of depth at most kl

(Asked by: username_0 on 2023-03-22)

I have seen it stated that if boolean function $f$ is computable by a $k$-CNF and an $l$-DNF then it can be computed by a decision tree of depth at most $kl$. However, I am not able to see why this is the case.

**Tags:** boolean-functions, boolean-formulas, decision-trees


---

## 1 answers

### Answer by username_1 on 2023-03-23. Score: 1 | Accepted answer

Observe that if a $k$-CNF $\Phi$ is equivalent to an $l$-DNF $\Psi$, then every term of $\Psi$ implies every clause of $\Phi$, i.e., they share a literal.

If the Boolean function is not constant, pick a clause $C$ in $\Phi$ and query all its variables. This is a decision tree of depth at most $k$. For each branch, restrict $\Phi$ and $\Psi$ by the partial assignment determined by the branch.

Each such restriction turns $\Psi$ into an $(l-1)$-DNF: if $D$ is any term of $\Psi$, let $x$ be a literal shared by $C$ and $D$; if $x$ is false, then $D$ is falsified, otherwise it is shortened by at least one literal.

Thus, the function becomes constant on each branch after at most $l$ iterations of this process.


---

