After learning individual rules and indirect proof, we now combine them in longer chains. Proofs using several rules of inference are written as sequences in which each line is either a premise or follows from earlier lines by a valid rule. This is the beginning of formal proof construction in discrete mathematics. In this lesson, proofs using several rules of inference will show how conditional conclusions, symbolic arguments, and verbal arguments are handled systematically. :::remark Many arguments require more than one rule of inference. A proof of validity is written as a sequence of statements. Each statement is either a premise or follows from earlier statements by a valid rule of inference. The reason for every non-premise step should be stated so that the proof can be checked line by line. ::: :::definition[Main Rules of Inference] The following rules are used frequently in multi-step proofs: $$\begin{align*} &p,\ p\to q\ \therefore\ q &&\text{Modus Ponens},\\ &p\to q,\ q\to r\ \therefore\ p\to r &&\text{Law of the Syllogism},\\ &p\to q,\ \neg q\ \therefore\ \neg p &&\text{Modus Tollens},\\ &p,\ q\ \therefore\ p\land q &&\text{Rule of Conjunction},\\ &p\lor q,\ \neg p\ \therefore\ q &&\text{Disjunctive Syllogism},\\ &\neg p\to F_0\ \therefore\ p &&\text{Rule of Contradiction},\\ &p\land q\ \therefore\ p &&\text{Conjunctive Simplification},\\ &p\ \therefore\ p\lor q &&\text{Disjunctive Amplification}. \end{align*}$$ ::: :::definition[Dilemma Rules] The constructive and destructive dilemma rules are $$\begin{align*} &p\to q,\ r\to s,\ p\lor r\ \therefore\ q\lor s &&\text{Constructive Dilemma},\\ &p\to q,\ r\to s,\ \neg q\lor\neg s\ \therefore\ \neg p\lor\neg r &&\text{Destructive Dilemma}. \end{align*}$$ These are used when a proof divides into two conditional alternatives. ::: :::solved-problem Establish the validity of the argument $p\to r,\ \neg p\to q,\ q\to s\ \therefore\ \neg r\to s$. ::: :::solution Let $p\to r$, $\neg p\to q$, and $q\to s$ be true premises. To prove $\neg r\to s$, assume $\neg r$. From $p\to r$ and $\neg r$, Modus Tollens gives $\neg p$. From $\neg p\to q$ and $\neg p$, Modus Ponens gives $q$. From $q\to s$ and $q$, Modus Ponens gives $s$. Therefore, assuming $\neg r$ leads to $s$. Hence $\neg r\to s$. ::: :::solved-problem Establish the validity of the argument $p\to q,\ q\to(r\land s),\ \neg r\lor(\neg t\lor u),\ p\land t\ \therefore\ u$. ::: :::solution Let all premises be true. From $p\land t$, Conjunctive Simplification gives $p$ and $t$. From $p\to q$ and $p$, Modus Ponens gives $q$. From $q\to(r\land s)$ and $q$, Modus Ponens gives $r\land s$. From $r\land s$, Conjunctive Simplification gives $r$. Since $r$ is true, $\neg r$ is false. From $\neg r\lor(\neg t\lor u)$ and $r$, Disjunctive Syllogism gives $\neg t\lor u$. Since $t$ is true, $\neg t$ is false. From $\neg t\lor u$ and $t$, Disjunctive Syllogism gives $u$. Hence, the conclusion follows. ::: :::solved-problem Show that the following verbal argument is valid. If the band could not play rock music or the refreshments were not delivered on time, then the New Year’s party would have been canceled and Alicia would have been angry. If the party was canceled, then refunds would have had to be made. No refunds were made. Therefore, the band could play rock music. ::: :::solution Let $p$ mean “The band could play rock music,” $q$ mean “The refreshments were delivered on time,” $r$ mean “The New Year’s party was canceled,” $s$ mean “Alicia was angry,” and $t$ mean “Refunds had to be made.” The premises are $$\begin{equation*} (\neg p\lor\neg q)\to(r\land s),\quad r\to t,\quad \neg t. \end{equation*}$$ From $r\to t$ and $\neg t$, Modus Tollens gives $\neg r$. From $(\neg p\lor\neg q)\to(r\land s)$, the conclusion $r\land s$ would imply $r$, so the conditional supports $(\neg p\lor\neg q)\to r$. From $(\neg p\lor\neg q)\to r$ and $\neg r$, Modus Tollens gives $\neg(\neg p\lor\neg q)$. By De Morgan’s law, $$\begin{equation*} \neg(\neg p\lor\neg q)\Leftrightarrow p\land q. \end{equation*}$$ Therefore $p\land q$. By Conjunctive Simplification, $p$. Hence, the band could play rock music. ::: :::definition[Conditional Proof by Corresponding Argument] Let $p_1,p_2,\ldots,p_n$ be premises. To prove $$\begin{equation*} p_1,\ p_2,\ldots,p_n\ \therefore\ q\to r, \end{equation*}$$ it is enough to prove the corresponding argument $$\begin{equation*} p_1,\ p_2,\ldots,p_n,\ q\ \therefore\ r. \end{equation*}$$ ::: :::solved-problem Establish the validity of the argument $u\to r,\ (r\land s)\to(p\lor t),\ q\to(u\land s),\ \neg t\ \therefore\ q\to p$. ::: :::solution Let $u\to r$, $(r\land s)\to(p\lor t)$, $q\to(u\land s)$, and $\neg t$ be true premises. To prove $q\to p$, assume $q$. From $q\to(u\land s)$ and $q$, Modus Ponens gives $u\land s$. From $u\land s$, Conjunctive Simplification gives $u$ and $s$. From $u\to r$ and $u$, Modus Ponens gives $r$. From $r$ and $s$, the Rule of Conjunction gives $r\land s$. From $(r\land s)\to(p\lor t)$ and $r\land s$, Modus Ponens gives $p\lor t$. Since $\neg t$ is true, Disjunctive Syllogism gives $p$. Therefore, assuming $q$ leads to $p$. Hence $q\to p$. ::: :::solved-problem Give reasons for the proof steps showing that $[p\land(p\to q)\land(s\lor r)\land(r\to\neg q)]\to(s\lor t)$ is valid. ::: :::solution Let $p$, $p\to q$, $s\lor r$, and $r\to\neg q$ be true. From $p$ and $p\to q$, Modus Ponens gives $q$. From $r\to\neg q$, the contrapositive gives $q\to\neg r$. From $q$ and $q\to\neg r$, Modus Ponens gives $\neg r$. From $s\lor r$ and $\neg r$, Disjunctive Syllogism gives $s$. From $s$, Disjunctive Amplification gives $s\lor t$. Hence, the argument is valid. ::: A multi-step proof is readable only when each line has the correct reason. Use the checker to match proof steps with the rules that justify them. The calculator focuses on the exercise pattern in this lesson, so the choices are limited to the relevant rules. Correct reasons show how a long proof is built from small valid moves. :::calculator[Proof Step Reason Checker] ::: :::exercise Give reasons for the steps needed to show that $[p\land(p\to q)\land(s\lor r)\land(r\to\neg q)]\to(s\lor t)$ is valid. Steps: $p$, $p\to q$, $q$, $r\to\neg q$, $q\to\neg r$, $\neg r$, $s\lor r$, $s$, $s\lor t$. ::: :::answer (1) Premise. (2) Premise. (3) Modus Ponens. (4) Premise. (5) Contrapositive. (6) Modus Ponens. (7) Premise. (8) Disjunctive Syllogism. (9) Disjunctive Amplification. ::: :::faq[Frequently Asked Questions] Q: Why should every proof step have a reason? A: A stated reason shows that the step follows from earlier statements by a valid rule. Q: How do we prove a conditional conclusion? A: Assume its hypothesis temporarily and derive its conclusion from the premises. Q: Can verbal arguments be treated symbolically? A: Yes. First define symbols for the basic statements, then translate the premises and conclusion. ::: :::call-to-action[Write Multi-Step Proofs] subtitle: Practise naming each inference step before learning how counterexamples expose invalid arguments. button: Next Lesson | /discrete-mathematics/mathematical-logic/logical-implication-and-rules-of-inference/invalid-arguments-and-counterexamples button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/logical-implication-and-rules-of-inference/contradiction-and-indirect-proof :::