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

  • $\begingroup$ @D.W.: Thanks for writing. No, I did not intend that. $\endgroup$
    – ShyPerson
    Oct 23, 2023 at 17:05
  • $\begingroup$ @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? $\endgroup$
    – ShyPerson
    Oct 24, 2023 at 0:12
  • $\begingroup$ @Someone: I've flagged your comment complete since I've addressed it here. $\endgroup$
    – ShyPerson
    Oct 24, 2023 at 0:28

1 Answer 1


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.

  • $\begingroup$ 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 $\endgroup$
    – ShyPerson
    Oct 24, 2023 at 0:25
  • $\begingroup$ @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}$? $\endgroup$
    – D.W.
    Oct 24, 2023 at 5:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.