Converse, inverse, and contrapositive forms show that conditional statements have structure. Nested conditionals add another layer: one implication may appear inside another. These forms occur naturally in program logic, where one condition may be tested only after another condition is satisfied. In this lesson, nested conditionals and program logic will connect the equivalence $(p\land q)\to r$ with the nested form $p\to(q\to r)$. :::theorem[Nested Conditional Equivalence] Let $p$, $q$, and $r$ be primitive statements. Then $$\begin{equation*} (p\land q)\to r\Leftrightarrow p\to(q\to r). \end{equation*}$$ ::: :::proof Given that $p$, $q$, and $r$ are primitive statements. To prove that $(p\land q)\to r\Leftrightarrow p\to(q\to r)$. Using implication as disjunction, $$\begin{align*} (p\land q)\to r&\Leftrightarrow\neg(p\land q)\lor r\\ &\Leftrightarrow(\neg p\lor\neg q)\lor r\\ &\Leftrightarrow\neg p\lor(\neg q\lor r). \end{align*}$$ Since $\neg q\lor r\Leftrightarrow q\to r$, we get $$\begin{align*} \neg p\lor(\neg q\lor r)&\Leftrightarrow\neg p\lor(q\to r)\\ &\Leftrightarrow p\to(q\to r). \end{align*}$$ Hence, $(p\land q)\to r\Leftrightarrow p\to(q\to r)$. $\square$ ::: :::example[Program Logic Interpretation] Let $p$, $q$, and $r$ be conditions in a program. The statement $(p\land q)\to r$ means that if both $p$ and $q$ are true, then $r$ must be true. The statement $p\to(q\to r)$ means that if $p$ is true, then if $q$ is true, $r$ must be true. The two statements have the same truth value under every assignment. ::: Use the explorer to compare a combined conditional with its nested form. Choose values for $p$, $q$, and $r$, then compare $(p\land q)\to r$ with $p\to(q\to r)$. The truth values always agree, but the nested reading also shows when a program could skip a later test. This separates logical equivalence from identical evaluation behavior. :::scientific-preview[Nested Conditional Flow Explorer] ::: Logical equivalence does not always mean identical computational behavior. Two program conditions may have the same truth value for every input, but one program may test fewer conditions because of the order in which conditions are checked. A nested condition may skip a later test when an earlier condition fails. :::example[Pascal Program Conditions] Let $p:x>0$, $q:y>0$, and $r:x+y>0$. A compound test may use $(x>0)\land(y>0)$. A nested test may first test $x>0$ and then test $y>0$ only if the first test is true. Both forms may be based on logically equivalent statements, but they can require different numbers of comparisons. ::: :::solved-problem Explain why $(p\land q)\to r$ and $p\to(q\to r)$ are logically equivalent but may not require the same number of comparisons in a program. ::: :::solution Given that $p$, $q$, and $r$ are program conditions. The nested conditional equivalence gives $$\begin{equation*} (p\land q)\to r\Leftrightarrow p\to(q\to r). \end{equation*}$$ Thus, the two statement forms have the same truth value under every assignment. However, if a nested program tests $p$ first and finds $p=0$, it may not need to test $q$. Another program that forms $p\land q$ first may test both $p$ and $q$. Therefore, the logical result is the same, but the number of comparisons may differ. ::: :::solved-problem Find a form of the contrapositive of $p\to(q\to r)$ with only one occurrence of $\to$. ::: :::solution Given that the statement is $p\to(q\to r)$. Using nested conditional equivalence, $$\begin{equation*} p\to(q\to r)\Leftrightarrow(p\land q)\to r. \end{equation*}$$ The contrapositive of $(p\land q)\to r$ is $$\begin{equation*} \neg r\to\neg(p\land q). \end{equation*}$$ Using De Morgan's Law, $\neg(p\land q)\Leftrightarrow\neg p\lor\neg q$. Hence, a contrapositive form with one implication is $$\begin{equation*} \neg r\to(\neg p\lor\neg q). \end{equation*}$$ ::: :::exercise Rewrite each statement as a nested conditional or as a single implication with a conjunctive hypothesis: (1) $(p\land q)\to r$. (2) $p\to(q\to r)$. (3) $(p\land\neg q)\to r$. ::: :::answer (1) $p\to(q\to r)$. (2) $(p\land q)\to r$. (3) $p\to(\neg q\to r)$. ::: :::faq[Frequently Asked Questions] Q: Are $(p\land q)\to r$ and $p\to(q\to r)$ always equivalent? A: Yes. They have the same truth value for every truth assignment. Q: Does logical equivalence imply equal program speed? A: No. A program may skip some tests depending on evaluation order. Q: Why are nested conditionals useful? A: They model decisions where a second condition is tested only after a first condition holds. ::: :::call-to-action[Analyse Nested Decisions] subtitle: Practise rewriting nested conditionals before simplifying longer compound statements. button: Next Lesson | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/simplification-of-compound-statements button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/converse-inverse-and-contrapositive :::