# Is this type of a transformation possible in propositional logic?

Let $$\Phi_1(A,B)$$ be a propositional logic formula consisting only of propositions $$A$$ and $$B$$, similarly we have $$\Phi_2(C,D)$$. Now lets say we have a formula as follows: $$(M \leftrightarrow \Phi_1(A,B)) \land (N \leftrightarrow \Phi_2(C,D))$$

Where $$M$$ and $$N$$ are propositional variables as well. Is there any transformation possible which converts this form into a formula of the following form : $$\Phi_1'(M,N) \land \Phi_2'(A,B,C,D)$$

The transformed formula must be equivalent to the original formula. Where $$\Phi_1'(M,N)$$ consists only of $$M$$ and $$N$$ and similarly for $$\Phi_2'(A,B,C,D)$$. No new propositional variables should be introduced.

Corrections made in the problem, thanks to @Alex Kruckman's comment

• The question as written is really unclear. Are $M$ and $N$ also propositions? Is $\Phi(C,D)$ the same formula as $\Phi(A,B)$, but with $C$ and $D$ substituted for $A$ and $B$? Same question for $\Phi'$ (but one has two "inputs" while the other has four). Did you mean "No new" instead of "Now new" in the last sentence? Most importantly, when you talk about a "transformation converting" a formula, do you mean that the resulting formula should be equivalent to the original one? Feb 26, 2021 at 14:05
• @AlexKruckman thanks for the comment, I hope its clearer now. Feb 26, 2021 at 14:11

No such transformation is possible unless $$\Phi_1$$ and $$\Phi_2$$ are constant. WLoG, let $$A_1, B_1$$ be such truth values that $$\Phi_1(A_1, B_1)$$ is true, and $$A_2, B_2$$ be such truth values that $$\Phi_1(A_2, B_2)$$ is false. Moreover, fix $$N, C, D$$ such that $$N \leftrightarrow \Phi_2(C, D)$$.

Then, the following are true: $$(\top \leftrightarrow \Phi_1(A_1, B_1)) \land (N \leftrightarrow \Phi_2(C, D))$$ $$(\bot \leftrightarrow \Phi_1(A_2, B_2)) \land (N \leftrightarrow \Phi_2(C, D))$$

By the equivalence you're asking for, the following are also true: $$\Phi_1'(\top, N) \land \Phi_2'(A_1, B_1, C, D)$$ $$\Phi_1'(\bot, N) \land \Phi_2'(A_2, B_2, C, D)$$

Thus all of the conjuncts are true and so is: $$\Phi_1'(\bot, N) \land \Phi_2'(A_1, B_1, C, D)$$

By the equivalence again, $$(\bot \leftrightarrow \Phi_1(A_1, B_1)) \land (N \leftrightarrow \Phi_2(C, D))$$

But, by assumption, we have $$\top \leftrightarrow \Phi_1(A_1, B_1)$$, so $$\top \leftrightarrow \bot$$, which is a contradiction.

This is possible if and only if for each $$i \in \{1,2\}$$, $$\Phi_i$$ is a tautology or a contradiction.

Let $$\Theta$$ be the formula $$(M \leftrightarrow \Phi_1(A,B)) \land (N \leftrightarrow \Phi_2(C,D))$$.

Suppose that for each $$i \in \{1,2\}$$, $$\Phi_i$$ is a tautology or a contradiction. Then $$\Theta$$ is equivalent to $$((\lnot)M\land (\lnot) N)\land \top$$, where we put the $$\lnot$$ in front of $$M$$ if $$\Phi_1(A,B)$$ is a contradiction and we put the $$\lnot$$ in front of $$N$$ if $$\Phi_2(C,D)$$ is a contradiction. Here $$\Phi_2'$$ is the tautology $$\top$$ (but if $$\top$$ is not in your language, you could use any tautology involving just $$A,B,C,D$$).

On the other hand, suppose that there is some $$i\in \{1,2\}$$ such that $$\Phi_i$$ is neither a tautology nor a contradiction. Let's assume $$i = 1$$, since the proof in the other case is similar. Assume for contradiction that there is some formula $$\Psi = \Phi_1'(M,N) \land \Phi_2'(A,B,C,D)$$ equivalent to $$\Theta$$. Fix some valuation $$v_0$$ on $$\{N,C,D\}$$ so that $$v_0$$ makes $$(N\leftrightarrow \Phi_2(C,D))$$ true (pick the truth values of $$C$$ and $$D$$ arbitarily, and then pick the truth value of $$N$$ to agree with $$\Phi_2(C,D)$$).

Case 1: There is a valuation $$v_1$$ extending $$v_0$$ and making $$\Phi'_2(A,B,C,D)$$ false. Let $$v_1'$$ be the valuation obtained from $$v_1$$ by changing the truth value of $$M$$ (if necessary) to agree with $$\Phi_1(A,B)$$. Under $$v_1'$$, $$\Phi'_2(A,B,C,D)$$ is still false, so $$\Psi$$ is false, but $$\Theta$$ is true, contradiction.

Case 2: Every valuation extending $$v_0$$ makes $$\Phi'_2(A,B,C,D)$$ true, but there is a valuation $$v_2$$ extending $$v_0$$ and making $$\Psi$$ false. Then $$v_2$$ must make $$\Phi_1'(M,N)$$ false. Since $$\Phi_1(A,B)$$ is neither a tautology or a contradiction, we can make a new valuation $$v_2'$$ by changing the truth values of $$A$$ and $$B$$ (if necessary) to make the truth value of $$\Phi_1(A,B)$$ equal $$v_2(M)$$. Under $$v_2'$$, $$\Phi_1'(M,N)$$ is still false, so $$\Psi$$ is false, but $$\Theta$$ is true, contradiction.

Case 3: Every valuation extending $$v_0$$ makes $$\Psi$$ true. We can pick a valuation extending $$v_0$$ and making $$\Theta$$ false, just by picking the truth values of $$A$$ and $$B$$ arbitrarily and then picking the truth value of $$M$$ to disagree with the truth value of $$\Phi_1(A,B)$$. Contradiction.