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

Question

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.

Answer 1

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.