help me to prove this tautology ( $\models A \leftrightarrow ((p \wedge B) \vee(\neg p \wedge C))$)

Question

My question is this :

For every proposition $A$ and atom $p$ ,show that there exist proposition $B$ and $C$ which $p$ doesn't appear on both of them and $\models A \leftrightarrow ((p \wedge B) \vee(\neg p \wedge C))$ .

I know that I should prove for every interpretation $I$ ,$I(A) = I((p \wedge B) \vee(\neg p \wedge C))$. I don't have any idea how I can make $B$ and $C$ and prove this.Can anyone help me?

Answer 1

Hint

You have to try by induction on the lenght of $A$, assuming for simplicity the complete set of connectives :

$\lnot, \lor, \land$.

Base case

We have that $A$ is $q$ for some atom $q$.

Then, we can check with truth-table that :

$\vDash q \leftrightarrow (p \land q) \lor (\lnot p \land q)$.

Induction step

(i) We have to consider the case where $A$ is $A_1 \land A_2$.

By induction hypotheses :

$\vDash A_1 \leftrightarrow (p \land B_1) \lor (\lnot p \land C_1)$, $\vDash A_2 \leftrightarrow (p \land B_2) \lor (\lnot p \land C_2)$.

We must exploit the fact that : $(a \lor b) \land (c \lor d)$ is equivalent to : $(a \land c) \lor (b \land d)$.

Thus, we have that :

$$(A_1 \land A_2) \leftrightarrow$$

$$[(p \land B_1) \lor (\lnot p \land C_1)] \land [(p \land B_2) \lor (\lnot p \land C_2)] \leftrightarrow$$

$$[(p \land B_1) \land (p \land B_2) ] \lor [(\lnot p \land C_1) \land (\lnot p \land C_2)] \leftrightarrow$$

$$[p \land (B_1 \land B_2)] \lor [\lnot p \land (C_1 \land C_2)].$$

(ii) The same for $\lor$.

(iii) Finally, we have to consider the case where $A$ is $\lnot A_1$ and we assume that : $\vDash A_1 \leftrightarrow (p \land B_1) \lor (\lnot p \land C_1)$.

Thus :

$$\lnot A_1 \leftrightarrow (\lnot p \lor \lnot B_1) \land (p \lor \lnot C_1) \leftrightarrow$$

$$(\lnot p \land \lnot C_1) \lor (p \land \lnot B_1).$$