# How big is a formula equivalent to a wff over $n$ variables with $2^n$ subformulas?

Definitions: Let $$n \in \mathbb{N}$$. If $$\alpha$$ and $$\beta$$ are propositional formulas, then we'll call $$\alpha$$ and $$\beta$$ independent if neither implies the other, or more formally, if $$\lnot (\alpha \rightarrow \beta)$$ and $$\lnot(\beta \rightarrow \alpha)$$ are each satisfiable, perhaps under different variable assignments. The notation $$|\phi|$$ refers to the length of $$\phi$$ in characters.

We saw in the answer to a previous question that if a formula $$\phi$$ has $$2^n$$ independently varying propositional variables, then any formula logically equivalent to $$\phi$$ must be of length at least $$2^n$$. I'll call this answer $$A$$.

We now attempt to generalize that result from independent variables to independent formulas. We are constrained to consider only those wffs $$\phi$$ that contain $$2^n$$ pairwise independent formulas over $$n$$ variables. Syntactically, these formulas $$\alpha_i$$ are constrained to occur at the leaf level of $$\phi$$, so that if a variable were substituted for the formula, it would occur at the syntactic leaf level of $$\phi$$. No other formula may occur at the leaf level of $$\phi$$. Neither $$\phi$$ nor any of the $$\alpha_i$$ is allowed to be identically true or false.

Question: Can we then conclude that any formula $$\varphi$$ logically equivalent to $$\phi$$ must be of exponential length, that is, if $$\varphi \leftrightarrow \phi$$, then $$|\varphi| = \Omega(2^n)$$?

Argument: We create $$2^n$$ new propositional variables

$$p_1,\ldots, p_{2^n}$$

and then define $$2^n$$ equivalences $$p_i \leftrightarrow \alpha_i$$ for each of the independent $$n$$-place formulas $$\alpha_i$$. At this point, we can just substitute the variable for the corresponding formula and reduce the problem to the one solved in answer $$A$$.

• @D.W.: Thanks for writing. No, I did not intend that. Commented Oct 23, 2023 at 17:05
• @Someone: Thanks for your interest in my question. Were there specific terms you had in mind, or were you looking for a more general treatment? Commented Oct 24, 2023 at 0:12
• @Someone: I've flagged your comment complete since I've addressed it here. Commented Oct 24, 2023 at 0:28

No. Consider the formula

$$\phi = \alpha_1 \lor \alpha_2 \lor \dots \lor \alpha_{2^n} \lor \text{True},$$

where the $$\alpha_i$$ are pairwise independent according to your definition.

$$\phi$$ meets the requirements of your question ($$\phi$$ contains $$2^n$$ pairwise independent formulas $$\alpha_i$$, all $$\alpha_i$$'s occur at the leaf level of $$\phi$$).

However $$\phi$$ is equivalent to $$\psi = \text{True}$$, which does not have exponential length.

• Thanks for working on my question. I’ve edited the question to exclude situations I hadn't intended. Also, $\lnot(\alpha \rightarrow \text{True}) \equiv \text{False}$. Please let me know if I have made any mistake in marking the comments complete. Thanks Commented Oct 24, 2023 at 0:25
• @ShyPerson, changing the question after you receive an answer, in a way that invalidates that existing answer, is generally frowned upon. Instead, it's better to be very careful to state the question accurately the first time; and if you fail, to ask a new question. I believe if you put a little thought into it, you should be able to find a way to modify my example with your updated requirements. Hint: try a logical-or of two formulas, over variables. Can you make the "or" be equivalent to $\text{True}$?
– D.W.
Commented Oct 24, 2023 at 5:15