Return to Question

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

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

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

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

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

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

Question: Can we then conclude that any formula logically equivalent to $\phi$ must be of exponential length, that is, $|\phi| = \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$.

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

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