3
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ Feb 26, 2021 at 14:05
  • $\begingroup$ @AlexKruckman thanks for the comment, I hope its clearer now. $\endgroup$
    – SagarM
    Feb 26, 2021 at 14:11

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .