Proof of the replacement property of a propositional logic formula.

Question

I'd like to know if my demonstration is "alright". Sorry for any grammar mistakes, english is not my first language.

I have to show that "if A and B are equivalent formulas, then you can replace A with B without changing any resulting truth value for any possible valuation of a formula φ". For that, I used structural induction:

Let φ and B be formulas and A is a subformula of φ.

Base case: Let A be equivalent to any atomic formula p. In this case, for every valuation v, v(A) = v(p). That is, all rows of the truth table are identical, so we can replace A with p and keep all possible truth values of φ.

Case ¬: Assume A is equivalent to B. We know, by definition, that the negation operator inverts the truth value of a formula. That is, for every valuation v such that v(A) = v(B), we also have v(¬A) = v(¬B). Therefore, we can replace A with B in a formula and keep the truth values for every possible valuation of A.

Case p o q: By the premise, for every possible valuation v, v(A) = v(p o q), for o ∈ {∧, ∨, →}. So, for any possible truth value in a formula, we can keep it by replacing a with p o q.

Answer 1

I'd rather do the structural induction for $\varphi$ (it looks like you are doing it for $A$):

If $A=\varphi$, the claim follows immediately from the equivalence of $A$ and $B$ (as in your proof). So assume from now on that $A\ne \varphi$

• If $\varphi$ is atomic, $A$ cannot be a proper subformula, so no replacement takes place and we are done
• if $\varphi=\neg\psi$, then $A$ can only bea subformula by being a subformula of $\psi$. Thus we have $$v(\varphi(A|B))=v(\neg\psi(B))=\neg v(\psi(A|B))=\neg(v(\psi))=v(\neg\psi)=v(\phi)$$
• if $\varphi=\psi\circ\chi$, then $A$ can only be a subformula of $\varphi$ by being a subformula of $\psi$ and/or $\chi$. Thus we have $$ v\bigl(\varphi(A|B)\bigr)=v\bigl(\psi(A|B)\circ \chi(A|B)\bigr)= v\bigl(\psi(A|B)\bigr)\circ v\bigl(\chi(A|B)\bigr) =v(\psi)\circ v(\chi)=v(\psi\circ \chi)=v(\varphi)$$