After separating valid conditional rules from invalid conditional reasoning, we now use the connectives $\land$ and $\lor$ as inference tools. Conjunction and disjunction rules explain when statements may be joined, separated, enlarged, or handled by cases. These rules appear constantly in proofs because many mathematical hypotheses are written with “and” or “or.” In this lesson, conjunction and disjunction rules will be stated, proved, and applied to short symbolic arguments. :::theorem[Rule of Conjunction] Let $p$ and $q$ be statements. If $p$ is true and $q$ is true, then $p\land q$ is true: $$\begin{equation*} \begin{array}{c} p,\ q\\ \hline p\land q \end{array} \end{equation*}$$ ::: :::proof Given that $p$ is true and $q$ is true. To prove that $p\land q$ is true. By the definition of conjunction, $p\land q$ is true exactly when both $p$ and $q$ are true. Since both $p$ and $q$ are true, $p\land q$ is true. Hence the Rule of Conjunction is valid. $\square$ ::: :::theorem[Rule of Disjunctive Syllogism] Let $p$ and $q$ be statements. If $p\lor q$ is true and $\neg p$ is true, then $q$ is true: $$\begin{equation*} \begin{array}{c} p\lor q,\ \neg p\\ \hline q \end{array} \end{equation*}$$ ::: :::proof Given that $p\lor q$ is true and $\neg p$ is true. To prove that $q$ is true. Since $\neg p$ is true, $p$ is false. Since $p\lor q$ is true and $p$ is false, the truth of the disjunction must come from $q$. Therefore $q$ is true. Hence Disjunctive Syllogism is valid. $\square$ ::: :::definition[Logical Form of Disjunctive Syllogism] The implication corresponding to Disjunctive Syllogism is $$\begin{equation*} [(p\lor q)\land\neg p]\to q. \end{equation*}$$ ::: :::example[Wallet Argument] Let $p$ mean “Bart’s wallet is in his back pocket,” and let $q$ mean “Bart’s wallet is on his desk.” If $p\lor q$ is true and $\neg p$ is true, then by Disjunctive Syllogism, $q$ is true. Hence, Bart’s wallet is on his desk. ::: :::theorem[Rule of Conjunctive Simplification] Let $p$ and $q$ be statements. If $p\land q$ is true, then $p$ is true: $$\begin{equation*} \begin{array}{c} p\land q\\ \hline p \end{array} \end{equation*}$$ ::: :::proof Given that $p\land q$ is true. To prove that $p$ is true. By the definition of conjunction, $p\land q$ is true only when both $p$ and $q$ are true. Therefore $p$ is true. Hence the Rule of Conjunctive Simplification is valid. $\square$ ::: :::theorem[Rule of Disjunctive Amplification] Let $p$ and $q$ be statements. If $p$ is true, then $p\lor q$ is true: $$\begin{equation*} \begin{array}{c} p\\ \hline p\lor q \end{array} \end{equation*}$$ ::: :::proof Given that $p$ is true. To prove that $p\lor q$ is true. By the definition of disjunction, $p\lor q$ is true when at least one of $p$ and $q$ is true. Since $p$ is true, $p\lor q$ is true. Hence the Rule of Disjunctive Amplification is valid. $\square$ ::: :::theorem[Rule for Proof by Cases] Let $p$, $q$, and $r$ be statements. If $p\to r$ is true and $q\to r$ is true, then $(p\lor q)\to r$ is true: $$\begin{equation*} \begin{array}{c} p\to r,\ q\to r\\ \hline (p\lor q)\to r \end{array} \end{equation*}$$ ::: :::proof Given that $p\to r$ and $q\to r$ are true. To prove that $(p\lor q)\to r$ is true. Assume that $p\lor q$ is true. Then at least one of $p$ and $q$ is true. If $p$ is true, then $r$ is true because $p\to r$ is true. If $q$ is true, then $r$ is true because $q\to r$ is true. Therefore, in every possible case, $r$ is true. Hence $(p\lor q)\to r$ is true. $\square$ ::: :::theorem[Constructive Dilemma] Let $p$, $q$, $r$, and $s$ be statements. If $p\to q$, $r\to s$, and $p\lor r$ are true, then $q\lor s$ is true: $$\begin{equation*} \begin{array}{c} p\to q,\ r\to s,\ p\lor r\\ \hline q\lor s \end{array} \end{equation*}$$ ::: :::proof Given that $p\to q$, $r\to s$, and $p\lor r$ are true. To prove that $q\lor s$ is true. Since $p\lor r$ is true, at least one of $p$ and $r$ is true. If $p$ is true, then $q$ is true because $p\to q$ is true. If $r$ is true, then $s$ is true because $r\to s$ is true. Therefore, at least one of $q$ and $s$ is true. Hence $q\lor s$ is true. $\square$ ::: :::theorem[Destructive Dilemma] Let $p$, $q$, $r$, and $s$ be statements. If $p\to q$, $r\to s$, and $\neg q\lor\neg s$ are true, then $\neg p\lor\neg r$ is true: $$\begin{equation*} \begin{array}{c} p\to q,\ r\to s,\ \neg q\lor\neg s\\ \hline \neg p\lor\neg r \end{array} \end{equation*}$$ ::: Conjunction and disjunction rules depend on whether a statement is built with “and” or “or.” Use the truth values to test how each rule behaves in one row. The explorer reports when the premises of a rule are satisfied and what conclusion the rule gives. This makes the difference between joining, simplifying, amplifying, and reasoning by cases more visible. :::scientific-preview[And Or Rule Explorer] ::: :::proof Given that $p\to q$, $r\to s$, and $\neg q\lor\neg s$ are true. To prove that $\neg p\lor\neg r$ is true. Since $\neg q\lor\neg s$ is true, either $\neg q$ is true or $\neg s$ is true. If $\neg q$ is true, then from $p\to q$ and $\neg q$, Modus Tollens gives $\neg p$. If $\neg s$ is true, then from $r\to s$ and $\neg s$, Modus Tollens gives $\neg r$. Therefore, at least one of $\neg p$ and $\neg r$ is true. Hence $\neg p\lor\neg r$ is true. $\square$ ::: :::solved-problem Show that the following argument is valid: $p\to q,\ r\to s,\ p\lor r\ \therefore\ q\lor s$. ::: :::solution Let $p\to q$, $r\to s$, and $p\lor r$ be true. Since $p\lor r$ is true, either $p$ is true or $r$ is true. If $p$ is true, then $q$ follows from $p\to q$. If $r$ is true, then $s$ follows from $r\to s$. Therefore, either $q$ is true or $s$ is true. Hence $q\lor s$ follows, so the argument is valid. ::: :::exercise Identify the rule used in each inference: (1) From $p$ and $q$, infer $p\land q$. (2) From $p\lor q$ and $\neg p$, infer $q$. (3) From $p\land q$, infer $p$. (4) From $p$, infer $p\lor q$. (5) From $p\to r$ and $q\to r$, infer $(p\lor q)\to r$. ::: :::answer (1) Rule of Conjunction. (2) Disjunctive Syllogism. (3) Conjunctive Simplification. (4) Disjunctive Amplification. (5) Proof by Cases. ::: :::faq[Frequently Asked Questions] Q: Why does Conjunctive Simplification allow only one part? A: If $p\land q$ is true, then both parts are true, so either part may be inferred. Q: Does Disjunctive Amplification add information? A: It creates a true disjunction from a true statement, but it does not prove the new alternative. Q: Why is Proof by Cases useful? A: It proves one conclusion from separate alternatives when every possible case leads to the same result. ::: :::call-to-action[Practise And-Or Inference] subtitle: Use conjunction and disjunction rules carefully before learning how contradiction supports indirect proof. button: Next Lesson | /discrete-mathematics/mathematical-logic/logical-implication-and-rules-of-inference/contradiction-and-indirect-proof button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/logical-implication-and-rules-of-inference/invalid-conditional-reasoning :::