Let $P,Q'$ be propositions and $Q$ a subformula of $P$ ($Q\in sub(P)$). Prove that if we get the formula $P'$ from $P$ by replacing the occurrence of the formula $Q$ with the formula $Q'$, then
$$(Q\leftrightarrow Q')\rightarrow (P\leftrightarrow P') $$
is a tautology.
I am having a hard time understanding the problem so I can't really get started on it. I just tried to do some truth table business, but it didn't really go anywhere. Maybe because I didn't know how to factor in the assumption that $Q\in sub(P)$. Help would be appreciated.
Best Answer
What does the implication $(Q\leftrightarrow Q')\rightarrow (P\leftrightarrow P')$ say: if Q and Q' have same truth value then P and P' have same truth value. Now, it should be obvious why this implication holds.
If you are still not convinced, lets try to take it slowly. How we should prove an implication? Well, we should conjecture antecedent and then derive consequent. So, lets assume that $Q\leftrightarrow Q'$ holds. Then, if we replace every occurrence of $Q$ with $Q'$ in $P$ we will get formula $P'$. But this formula has same truth value as $P'$ because $Q$ has same truth value as $Q'$. So, it is true that $P\leftrightarrow P'$. Thus, we proved the implication $(Q\leftrightarrow Q')\rightarrow (P\leftrightarrow P')$.
In other words, formulas $P$ and $P'$ are semantically equivalent even if they are potentially different formulas (takan as sequences of symbols). For example, formulas $\neg(p\land q)$ and $\neg p \lor \neg q$ are different but they have same truth tables (check this). So we can exchange them in other formulas without altering truth values of those formulas.
Formally, this statement is proved by induction on subformulas of $P$.