# Section 1.2: Problem 8 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
(Substitution) Consider a sequence $\alpha_{1},\alpha_{2},\ldots$ of wffs. For each wff $\phi$ let $\phi^{∗}$ be the result of replacing the sentence symbol $A_{n}$ by $\alpha_{n}$ , for each $n$ .
(a) Let $v$ be a truth assignment for the set of all sentence symbols; define $u$ to be the truth assignment for which $u(A_{n})=\overline{v}(\alpha_{n})$ . Show that $\overline{u}(\phi)=\overline{v}(\phi^{∗})$ . Use the induction principle.
(b) Show that if $\phi$ is a tautology, then so is $\phi^{∗}$ . (For example, one of our selected tautologies is $((A\wedge B)\leftrightarrow(B\wedge A))$ . From this we can conclude, by substitution, that $((\alpha\wedge\beta)\leftrightarrow(\beta\wedge\alpha))$ is a tautology, for any wffs $\alpha$ and $\beta$ .)
(a) Let $S$ be the set of all sentence symbols. Let $B\subseteq\overline{S}$ be the set of all wffs $\alpha$ such that $\overline{u}(\alpha)=\overline{v}(\alpha^{*})$ . Then, by assumption, all sentence symbols are in $B$ (here we assume that if there is a sentence symbol $A$ different from all $A_{n}$ , then $\overline{u}(A)=u(A)=v(A)=\overline{v}(A)=\overline{v}(A^{*})$ , though, I think, what is meant here is that $A_{n}$ ’s form the set of all sentence symbols, as was defined earlier in the text). Now, if $\alpha,\beta\in B$ , then $\overline{u}((\neg\alpha))=\neg\overline{u}(\alpha)=\neg\overline{v}(\alpha^{*})=\overline{v}((\neg\alpha^{*}))=\overline{v}((\neg\alpha)^{*})$ , where, by definition, $\neg T=F$ and $\neg F=T$ , and, similarly, $\overline{u}(\alpha\square\beta)=\overline{u}(\alpha)\square\overline{u}(\beta)=\overline{v}(\alpha^{*})\square\overline{v}(\beta^{*})=\overline{v}((\alpha^{*}\square\beta^{*}))=\overline{v}((\alpha\square\beta)^{*})$ , where, by definition, $T\square F$ is valuated according to the truth tables. One thing to mention here is that we used equalities $(\neg\alpha^{*})=(\neg\alpha)^{*}$ and $(\alpha^{*}\square\beta^{*})=(\alpha\square\beta)^{*}$ which simply mean that the substitution in a formula is equivalent to the substitution in its components, which is easy to accept or show using induction. Finally, by the induction principle, we conclude that $B=\overline{S}$ , and $\phi\in B$ .
(b) ($\phi$ is a tautology) iff (every truth assignment $u$ on $S$ implies $\overline{u}(\phi)=T$ ) THEN (here is where iff does not work) (every truth assignment $v$ on $S$ implies $\overline{v}(\phi^{*})=\overline{u}(\phi)=T$ , where $u$ is defined as in (a)) iff ($\phi^{*}$ is a tautology). To see that the other direction does not work, consider, for example, the wff $\phi=(A_{1}\vee(\neg A_{2}))$ , which is not a tautology, together with the substitution $\alpha_{n}=A_{1}$ . Then, $\phi^{*}=(A_{1}\vee(\neg A_{1}))$ , which is a tautology.