proving tautologically equivalent

This semester I take Introduction to logic and sets theory and for logic our reference is A Mathematical Introduction to Logic by H.B.Enderton.

I have some problems with this course I mean it is somehow unfamiliar ! our professor teach well and I learn at class but when I want to solve my homework ,I have no idea ,how to solve problems !

I don't have any idea how to prove this :

suppose a and b are tautologically equivalent, where A is wff and a is used in A and B is another wff that b is used in; prove that A and B are tautologically equivalent.

Any one can help me ?

You want to prove that if $A$ and $B$ are two formulas, and $C_A$ is a formula containing $A$ and $C_B$ comes from $C_A$ by replacing that part by $B$, we have :

Replacement theorem. If $\vDash_{TAUT} A \equiv B$, then $\vDash_{TAUT} C_A \equiv C_B$.

We assume that $A$ and $B$ are tautologically equivalent when $\vDash_{TAUT} A \equiv B$.

We can prove it in two ways :

(i) by truth-tables [see Stephen Cole Kleene, Mathematical Logic (1967), page 19].

If $\vDash_{TAUT} A \equiv B$, then the truth-table for $A$ and $B$ are identical, i.e. in each row, if $A$ evaluates to true (false), also $B$ evaluates to true (false).

Hence if, in the computation of a given line of the table for $C_A$, we replace the computation of the specified part $A$ by a computation of $B$ instead, the outcome will be unchanged. Thus $C_B$ has the same table of $C_A$; so $\vDash_{TAUT} C_A \equiv C_B$.

(ii) by induction on the depth of the occurrence of $A$ in $C_A$ [see Stephen Cole Kleene, Introduction to Metamathematics (1952), page 116].

The formula $C_A$ can be built up form $A$ with repeated applications of the rules for the use of connectives (like: from $P$ and $Q$, construct $P \lor Q$).

The number of steps in this construction of $C_A$ from $A$, we call the depth of an occurrence of $A$ in $C_A$. In other words, the depth of the part $A$ in $C_A$ is the number of connectives within the scopes of which it lies.

The proof is by induction on the depth of $A$ in $C_A$, taking the $A$ and $B$ fixed for the induction.

Basis: $A$ is at depth $0$ in $C_A$. Then $C_A$ is simply $A$ and $C_B$ must be $B$. So the theorem is simply : if $\vDash_{TAUT} A \equiv B$, then $\vDash_{TAUT} A \equiv B$.

Induction step: $A$ is at depth $d+1$ in $C_A$ and we assume as induction hypothesis that the result holds for depth $d$.

According to the rules for formation of formulas (for simplicity we assume that we are using only the $\lnot$ and $\lor$ connectives), we have that $C_A$ must have one of the following forms : $N \lor M_A$, $M_A \lor N$, $\lnot M_A$, where $M_A$ is the part of $C_A$ (and $C_B$ will be : $N \lor M_B$, $M_B \lor N$, $\lnot M_B$, respectively) where the specified occurrence of $A$ lies at depth $d$.

The induction hypothesis amount to assuming that if $\vDash_{TAUT} A \equiv B$, then $\vDash_{TAUT} M_A \equiv M_B$, because $M_A$ (and so $M_B$) have depth $d$.

In order to complete the proof, we need some simple lemmas :

if $\vDash_{TAUT} A \equiv B$, then $\vDash_{TAUT} \lnot A \equiv \lnot B$

if $\vDash_{TAUT} A \equiv B$, then $\vDash_{TAUT} A \lor C \equiv B \lor C$

if $\vDash_{TAUT} A \equiv B$, then $\vDash_{TAUT} C \lor A \equiv C \lor B$.

Then, applying the above lemmas (with $M_A$ as the $A$, $M_B$ as the $B$ and $N$ as the $C$), we have :

if $\vDash_{TAUT} M_A \equiv M_B$, then $\vDash_{TAUT} C_A \equiv C_B$.

Therefore, "connecting" the last result with the induction hypothesis above :

if $\vDash_{TAUT} A \equiv B$, then $\vDash_{TAUT} C_A \equiv C_B$.