Duality shows that valid logical laws remain valid under structured symbol changes. Substitution rules explain another powerful idea: a law proved for primitive statements may be applied to compound statements. This is why laws of logic can simplify long expressions without building a new truth table at every step. In this lesson, substitution rules for logical equivalence will justify replacing statement forms inside larger compound statements. :::theorem[First Substitution Rule] Let $P$ be a tautology involving primitive statements $p_1,p_2,\ldots,p_n$. If each $p_i$ is replaced by a statement $s_i$, then the resulting statement is also a tautology. ::: :::proof Given that $P$ is a tautology. To prove that substituting statements for primitive statements in $P$ produces another tautology. Since $P$ is true for every assignment of truth values to its primitive statements, each replaced statement $s_i$ supplies a truth value under every assignment to its own primitive statements. The substituted statement follows the same truth pattern as the original tautology. Therefore, it is true for every truth assignment. Hence, the substituted statement is a tautology. $\square$ ::: :::example[Substitution in De Morgan's Law] Given $$\begin{equation*} \neg(p\lor q)\Leftrightarrow\neg p\land\neg q, \end{equation*}$$ replace $p$ by $r\land s$ and $q$ by $t\to u$. Then $$\begin{equation*} \neg[(r\land s)\lor(t\to u)]\Leftrightarrow\neg(r\land s)\land\neg(t\to u). \end{equation*}$$ Thus, De Morgan's Law remains valid after substitution. ::: :::example[Substitution in a Domination Law] Given the domination law $p\land F_0\Leftrightarrow F_0$, replace $p$ by $(q\lor r)\to s$. Then $$\begin{equation*} [((q\lor r)\to s)\land F_0]\Leftrightarrow F_0. \end{equation*}$$ Hence, the domination law applies to compound statements as well as primitive statements. ::: :::example[Substitution in a Tautology] Given the tautology $[p\land(p\to q)]\to q$, replace $p$ by $r\to s$ and $q$ by $\neg(t\lor u)$. Then $$\begin{equation*} [(r\to s)\land((r\to s)\to\neg(t\lor u))]\to\neg(t\lor u) \end{equation*}$$ is also a tautology. ::: :::theorem[Second Substitution Rule] Let $P$ be a compound statement containing a statement $s$ as a substatement. If $s\Leftrightarrow t$, then replacing one or more occurrences of $s$ in $P$ by $t$ gives a statement logically equivalent to $P$. ::: :::proof Given that $s\Leftrightarrow t$. To prove that replacing one or more occurrences of $s$ by $t$ preserves logical equivalence. Since $s$ and $t$ have the same truth value for every truth assignment, replacing $s$ by $t$ inside any compound statement does not change the truth value contributed by that part of the statement. Therefore, the complete compound statement has the same truth value before and after the replacement. Hence, the new statement is logically equivalent to the original statement. $\square$ ::: :::solved-problem Let $P=((p\to q)\to r)$. Replace the substatement $p\to q$ by an equivalent disjunction. ::: :::solution Given that $P=((p\to q)\to r)$ and $p\to q\Leftrightarrow\neg p\lor q$. To apply the second substitution rule, replace the substatement $p\to q$ in $P$ by $\neg p\lor q$. Then $$\begin{equation*} P_1=((\neg p\lor q)\to r). \end{equation*}$$ Therefore, $$\begin{equation*} ((p\to q)\to r)\Leftrightarrow((\neg p\lor q)\to r). \end{equation*}$$ ::: :::solved-problem Prove that $[p\to(q\lor r)]\Leftrightarrow[(p\land\neg q)\to r]$. ::: :::solution Given that $p$, $q$, and $r$ are primitive statements. Start with $p\to(q\lor r)$. Using implication as disjunction, $$\begin{align*} p\to(q\lor r)&\Leftrightarrow\neg p\lor(q\lor r)\\ &\Leftrightarrow(\neg p\lor q)\lor r. \end{align*}$$ Using De Morgan's Law, $\neg p\lor q\Leftrightarrow\neg(p\land\neg q)$. Therefore, $$\begin{align*} (\neg p\lor q)\lor r&\Leftrightarrow\neg(p\land\neg q)\lor r\\ &\Leftrightarrow(p\land\neg q)\to r. \end{align*}$$ Hence, $[p\to(q\lor r)]\Leftrightarrow[(p\land\neg q)\to r]$. ::: :::exercise Use substitution rules to verify that each statement is a tautology: (1) $[p\lor(q\land r)]\lor\neg[p\lor(q\land r)]$. (2) $[(p\lor q)\to r]\leftrightarrow[\neg r\to\neg(p\lor q)]$. ::: :::answer (1) Substitute $p\lor(q\land r)$ for $p$ in $p\lor\neg p$. (2) The second statement is the contrapositive of the first; an implication is equivalent to its contrapositive. ::: :::faq[Frequently Asked Questions] Q: Can a law proved for $p$ be used for a long statement? A: Yes. The first substitution rule permits replacing primitive statements by compound statements in a tautology. Q: Must every occurrence be replaced? A: No. The second substitution rule allows one or more occurrences to be replaced. Q: Why is substitution safe? A: Equivalent substatements have the same truth value under every assignment. ::: :::call-to-action[Use Substitution in Proofs] subtitle: Practise replacing equivalent substatements before studying negation and duals of conditional statements. button: Next Lesson | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/negation-and-duals-of-conditional-statements button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/duality-in-logical-equivalence :::