Suppose I have $n$ propositional variables, $\{p_1,\ldots,p_n\}$ over which we truth tables and formulas over the language $\{\neg, \land, \lor, \top\}$. For the sake of this question, we define the depth of a formula by
- $\mathrm{depth}(p) = \mathrm{depth}(\top) = 0$,
- $\mathrm{depth}(\neg \phi) = \mathrm{depth}(\phi)$,
- $\mathrm{depth}(\phi \land \psi) = \mathrm{depth}(\phi \lor \psi) = 1 + \max(\mathrm{depth}(\phi), \mathrm{depth}(\psi))$.
I am interested in the question
What is the least integer $\chi(n)$ such that every truth table over $\{p_1,\ldots,p_n\}$ can be expressed with a formula of depth at most $\chi(n)$?
An easy upper bound is $\chi(n) = 2n - 2$, which we can show by induction. If $n = 1$ then the depth 0 formulas $p_1, \neg p_1, \top, \neg \top$ suffice. Inductively, given a truth table over $\{p_1,\ldots,p_n\}$, we split it in two: the part of the truth table where $p_n = 0$ and the part where $p_n = 1$. These then give us two formulas, $\phi_0, \phi_1$ in the variables $\{p_1,\ldots,p_{n-1}\}$, of depth at most $2n-4$. Then we can give our truth table via $(\phi_0 \land \neg p_n) \lor (\phi_1 \land p_n)$, which has depth $2n-2$.
My question is:
Is there a tighter bound on $\chi(n)$ than $2n-2$?
As a side note, I am also interested in bounding the length of the formula, rather than its depth, but that seems like a significantly more difficult question.
Proof Attempt: (EDIT: OK, so this does not work!!)
Let $mindepth(\varphi)$ be the minimum depth of all expressions able to capture $\varphi$.
Claim: The generalized XOR, i.e. $p_1 \oplus p_2 \oplus ... \oplus p_n$ can be expressed by an expression with a depth of $2n-2$, but not by one with a depth of less than $2n-2$. That is:
$$mindepth(p_1 \oplus p_2 \oplus ... \oplus p_n) = 2n-2$$
Correlary: $$\chi(n)=2n-2$$
Here's a proof by induction to show that $mindepth(p_1 \oplus p_2 \oplus ... \oplus p_n) = 2n-2$
Base: $n=1$. Then $p_1 \oplus p_2 \oplus ... \oplus p_n = p_1$, which can be expressed by $p_1$ itself, having a depth of $0$, and obviously you can't do better.. Check!
All-important observation:
$(p_1 \land \neg p_2) \lor (\neg p1 \lor p_2)$ as well as $(p_1 \lor p_2) \land (\neg p_1 \lor \neg p_2)$ both express $p_1 \oplus p_2$ with a depth of exactly $2$$.
However, you cannot express $p_1 \oplus p_2$ with an expression of depth less than $2$: Obviously neither of the $8$ expressions with a depth of $0$ ($p_1$, $p_2$, $\neg p_1$, $\neg p_2$, $\bot$, $\neg \bot$, $\top$, $\neg \top$) will do, and neither will any of the expressions with a depth of $1$ (there are $64$ expressions combining any of the $8$ 0-depth expressions with any of the $8$ 0-depth expressions using a $\lor$, and another $64$ using an $\land$, but none will capture $\oplus$ (Proof By Exercise Left to Reader!))
Hence: $mindepth(p_1 \oplus p_2) = 2$
What I hope to show is that: To express any $\varphi_1 \oplus \varphi_2$, where $\varphi_1$ and $\varphi_2$ are 'unrelated' will require an expression with a minimum depth of the sum of the minimum depths of $\varphi_1$ and $\varphi_2$ plus $2$. That is, for such $\varphi_1$ and $\varphi_2$: $mindepth(\varphi_1 \oplus \varphi_2) = mindepth(\varphi_1) + mindepth(\varphi_2) + 2$
OK, so let's assume by inductive hypothesis that $p_1 \oplus p_2 \oplus ... \oplus p_n$ can be expressed by an expression with depth $2n-2$, but not by an expression with a depth smaller than $2n-2$. Now let's consider $p_1 \oplus p_2 \oplus ... \oplus p_{n+1}$. Then by the previous observation, $mindepth(p_1 \oplus p_2 \oplus ... \oplus p_{n+1})= mindepth(p_1 \oplus p_2 \oplus ... \oplus p_n) + mindepth(p_{n+1}+2 = 2n-2+0+2=2(n+1)-2$