8.3: More Rules of Implication
- Page ID
- 223904
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Let’s introduce the rest of the rules of implication:
(a ‘Dilemma’ is a situation where one must choose between two (“di”) options (“lemmae”))
If I find a conjunctive premise that is a conjunction between two conditionals and a disjunctive premise that is a disjunction between both antecedents of those conditionals, then I can write a disjunctive conclusion that is a disjunction between both consequents. I justify this by writing “CD.”
\[\begin{align*}{} & (F \rightarrow G) \wedge P \rightarrow Q) \\ & \underline{(F \vee P) \ \ \ \ \ \ }\\ & (G \vee Q) \end{align*}\]
This is the most complex rule we’ll learn, but conceptually speaking it’s not all that complicated. It’s just two Modus Ponenses right next to one another. See how the “F\(\rightarrow\)G” from the first line and the “F” from the second line make a modus ponens with the “G” in the conclusion? Same for the letters on the right half of each line. The trick in recognizing this one, though, is getting the symbols straight. It’s always:
- a conjunction between two conditionals
- a disjunction between the antecedents
- a disjunction between the consequents
There’s a lot to say about this, but for now it suffices to say that it’s called dilemma for a reason: it’s the form of a dilemma that you might find in real life: If we go this way, this consequence will follow; but if we go this other way, this other consequence will follow. These are our only two ways of going, so we’re stuck with either of the two consequents.
(It’s the simplest rule there is!)
If I find a conjunction, I can put either conjunct on a line by itself. I justify this move by writing “simp”.
\[\begin{align*}{} & \underline{(P \wedge Q) }\\ & P \end{align*}\] | \[\begin{align*}{} & \underline{(P \wedge Q) }\\ & Q \end{align*}\] |
Pretty simple right? Need I say more? Just remember that you actually have to use this rule. Even though intuitively you should be able to use anything in a conjunction, you must bring it down to its own line using simp before you use it. For instance, this is not yet Modus Tollens:
1. ~D \(\wedge\) G
2. T \(\rightarrow\) D
Okay, moving on to the next rule:
(‘Conjunction’ is Latin for “a joining together”)
I’m allowed to join any two lines by a conjunction on a new line. I justify this move by writing “conj”.
\[\begin{align*}{} & P \\ & \underline{Q \ \ \ \ \ }\\ & (P \wedge Q) \end{align*}\] | \[\begin{align*}{} & P \\ & \underline{Q \ \ \ \ \ }\\ & (Q \wedge P) \end{align*}\] |
Pretty simple, still, right? It’s just the opposite of Simplification. Just take whatever two lines you like and stick them together with a conjunction. Think about it intuitively: if I tell you that Obama was president in 2012 and I tell you that he was president in 2009, then I’ve told you that Obama was president in 2012 and in 2009.
Here’s the next rule, but real quick: don’t confuse this with conjunction. One uses a conjunction (can you guess which one?) and the other uses a disjunction.
I can add whatever I like after a disjunction to any premise I like and write the result on a new line. I justify this move by writing “add”.
\[\begin{align*}{} & \underline{P \ \ \ \ \ }\\ & (P \vee Q) \end{align*}\]
Wait, what?!?!?! I knew I was right to call you a Wacky Fool.
I’m no wacky fool and I’m not lying to you here. I promise.
But you can’t just add whatever you want wherever you want it. This isn’t art class, there are rules! Right?
Yes, of course there are rules, silly. This just happens to be one of them! (And there are rules in art class, too)
It’s okay to add whatever you want, because when you add a disjunction, you weaken the formula. The worry we always have in logic is getting stronger propositions from weaker ones for free. There’s no free lunch in logic and there is no magic whereby you can get out of a deductive argument more than you put in. That’s what Induction (scientific reasoning, for example) is for.
So, when we weaken a proposition when moving from the premise to a new version of that proposition in the conclusion, we’re all good by the lights of logic.
For example, if I was to tell you that Tiger Woods is a fantastic golf player then you’d be warranted in inferring that either Tiger Woods is a fantastic golf player or the moon is made of cheese. If we already know that one disjunct is true, then there’s no worry about the disjunction as a whole being false (all it takes for a disjunction to be true is for at least one disjunct to be true). Similarly, if I tell you I teach logic, then you’re allowed to conclude that I either teach logic or music. Yes it’s true that I either teach logic or music, I teach logic!
Now we have all 8 rules of Implication on the table. I can’t emphasize enough the importance of having all of the rules in front of you while you’re trying to figure natural deduction problems out. These are the simplified forms of the rules:
8 Rules of Implication:
Table \(\PageIndex{1}\): 8 rules of implication.
Modus Ponens MP |
\[\begin{align*}{} & P \rightarrow Q \\ & \underline{P \ \ \ \ \ }\\ & Q \end{align*}\] |
Constructive Dilemma CD |
\[\begin{align*}{} & (F \rightarrow G) \wedge (P \rightarrow Q) \\ & \underline{(F \vee P) \ \ \ \ \ }\\ & (G \vee Q) \end{align*}\] |
Modus Tollens MT |
\[\begin{align*}{} & P \rightarrow Q \\ & \underline{\neg Q \ \ \ \ \ }\\ & \neg P \end{align*}\] |
Simplification simp |
\[\begin{align*}{} & \underline{P \wedge Q \ \ }\\ & P \end{align*}\] |
Disjunctive Syllogism DS |
\[\begin{align*}{} & P \vee Q \\ & \underline{\neg Q \ \ \ \ \ }\\ & P \end{align*}\] |
Conjunction conj |
\[\begin{align*}{} & P \\ & \underline{Q \ \ \ \ \ }\\ & (P \wedge Q) \end{align*}\] |
Hypothetical Syllogism HS |
\[\begin{align*}{} & P \rightarrow Q \\ & \underline{Q \rightarrow R \ \ \ }\\ & P \rightarrow R \end{align*}\] |
Addition add |
\[\begin{align*}{} & \underline{P \ \ \ \ \ }\\ & (P \vee Q) \end{align*}\] |
Let’s work through a problem or two that involves all 8 rules of Implication together.
1. (P \(\supset\) R) \(\supset\) (M \(\supset\) P)
2. (P \(\vee\) M) \(\supset\) (P \(\supset\) R)
3. P \(\vee\) M / R \(\vee\) P
R and P are on the right sides of two horseshoe formulas. Given that, it feels like we might use Modus Ponens at some point to get one or both of those on their own. We might also use Addition since our conclusion is a disjunction. The problem with both of these strategies is that it doesn’t look possible to get a P by itself, so it doesn’t seem possible to do that Modus Ponens. Without the Modus Ponens, we also won’t be able to get our conclusion via Addition. Consequently, it looks like we have many of the basic ingredients of a Constructive Dilemma, so maybe we should start heading in that direction.
An alternative strategy for getting through this problem is identifying the rules we can apply and then applying them as we find we’re able. That way we don’t need to do a lot of strategizing ahead of time and instead can simply trip our way to the solution—a bit easier than having to work through it all in your head.
Right away we see, looking at lines 1-3, that we could do a Hypothetical Syllogism with 1 and 2. We at least have an inkling, though, that we’re headed towards a Constructive Dilemma, and that HS doesn’t seem like it will get us closer to our goal. So let’s skip it.
The other move that is open to us right away is to do an MP with 2 and 3. Let’s go ahead an do that, throwing caution to the wind!
4. P \(\supset\) R 2, 3, MP
What now? It turns out we’ve opened up another MP by deriving the antecedent of 1:
5. M \(\supset\) P 1, 4, MP
Okay now we have P implies R and M implies P. Our conclusion is R or P. This is a perfect set up for Constructive Dilemma. We just need to look at the rule for constructive dilemma to help us determine how to construct the premises of the rule.
\[\begin{align*}{} & (F \rightarrow G) \wedge (P \rightarrow Q) \\ & \underline{(F \vee P) \ \ \ \ \ }\\ & (G \vee Q) \end{align*}\]
It looks like we need the implication (arrow/horseshow) formulas to be joined via conjunction (it’s an “\(\wedge\)” above). How can we do that? Well, we just learned a simple rules for making a conjunction: find both conjuncts on their own separate lines and then use the rule “Conjunction” to stick ‘em together with a \(\wedge\) or a \(\bullet\) (they both mean the same thing: conjuinction).
6. (P \(\supset\) R) \(\bullet\) (M \(\supset\) P) 4, 5, Conj
Great, now we have the first line of Constructive Dilemma above. Where’s the second line (F \(\vee\) P)? Well, in this case, it shoulw be (P \(\vee\) M). Do we have (P \(\vee\) M)?
Yeppers, Mr. Teacher Man. That’s just line 3 as it is! So we can do CD with 3 and 6!
7. R \(\vee\) P 3, 6, CD
Double check that your conclusion and your last derived line are identical and if they are, call it a day!
How about we go again?
1. (L \(\vee\) T) \(\supset\) (B \(\bullet\) G)
2. L \(\bullet\) (K \(\equiv\) R) / L \(\bullet\) B
It’s easy enough to get the L by itself, right? Do you know which rule we’ll use?
Yeah, that’s pretty clear. Use Simplification to break the L off of that conjunction in 2.
You got it. So smart.
3. L 2, Simp
So the last step will be to use which rule? Conjunction? Yep! We’ll take that L in 3 right above and conjoin it together with a B. Where’s B?
Up there in Line 1 on the consequent side.
Cool, and it’s in a conjunction, so we know we can simplify again once we break that consequent out of the horseshoe in 1. How are we going to get that consequent by itself?
To take the right side out of an arrow/horseshoe, you use....... Modus Ponens!
Perfecto. So we have to build (L \(\vee\) T). How do we get that?
Dunno dude, we only have an L.
Maybe if we could...Add to that L?
Oh yeah! Duh. Addition.
4. L \(\vee\) T 3, Add
Yep. It’s a bit counterintuitive, but since (L \(\vee\) T) is weaker than L—claiming that either I’m going to be president or I’m going to order a salad for lunch is obviously not as strong a claim as to claim that I’m going to be president!—this is logically valid.
Okay, now that I’ve got the left side of 1, I can do...Modus Ponens!
5. B \(\bullet\) G 1, 4, MP
And I wanted that B. That’s the reason we’ve been doing all of this Addition and Modus Ponens nonsense. Just simplify.
6. B 5, Simp
And then, as we decided earlier, I can use Conjunction to stick ‘em together and get my conclusion. Double check: is it the same as the conclusion after the slash above?
7. L \(\bullet\) B 3, 6, Conj