Interpolation of formula in propositional logic.

120 Views Asked by At

Prove that there exists the such $\phi_n$ that $\phi_n$ contains only $p_1, .., p_n$ and $O(|\phi_n|) = n$.

$$\left((p_1\lor z_1)\land(\lnot z_1\lor p_2\lor z_2)\land(\lnot z_2\lor p_3\lor z_3)\land\ldots\land(\lnot z_{n-2}\lor p_{n-1}\lor z_{n-1})\land(\lnot z_{n-1}\lor p_n)\right)\to\varphi_n$$

$$\varphi_n\to\left[\left((p_1\to x_1)\land((x_1\lor p_2)\to x_2)\land((x_2\lor p_3)\to x_3)\land\ldots\land((x_{n-1}\lor p_{n})\to x_n)\right)\to x_n\right].$$

I guessed that it is $\bigvee_{i = 1..n} p_i$ but I cannot prove it in formal way. Please help.

1

There are 1 best solutions below

2
On BEST ANSWER

Your hunch is correct. Note that your interpolant is the result of existential quantification of the $z$ variables. Therefore it is guaranteed to be implied by the formula from which you derived it. (You can also directly observe that when all the $p_i$'s are false, the LHS formula is false.)

The other implication is also easy to verify because when at least one $p_i$ is true, it reduces to an implication of the form $(\psi \wedge x_n) \rightarrow x_n$. Finally, the interpolant's size is clearly $O(n)$.