Chapter 6: Natural Deduction^[1]

I. Introduction

In the last chapter, we learned how to translate English language sentences into a system of symbolic logic. In this chapter, we will learn a system called “natural deduction,” a formal method of proving Predicate Logic (PL) arguments valid. Although you cannot construct a proof to show that an argument is invalid, you can construct proofs to show that an argument is valid. Learning natural deduction will teach you several valid reasoning patterns. It will also help you follow and create complex chains of reasoning. And, proofs are an efficient way to show an argument is indeed valid.

Here’s how we’ll proceed. The valid forms of inference you will learn are the rules you’ll use in your proofs. Each line of the proof will be justified by citing one of these rules, with the last line of the proof being the conclusion that we are trying to ultimately establish. I will introduce eight valid forms of inference in groups.

II. The First Four Valid Forms

After learning these four forms, we’ll begin constructing proofs using just these, before we introduce more rules. The first three rules involve conditionals, and the fourth is a disjunction rule.

1. Modus Ponens

The first form of inference is “modus ponens” which is Latin for “way that affirms.” Modus ponens has the following form:

The three dots before the q is a symbol that means “therefore.” It’s the conclusion indicator we will use in this chapter. What this form says, in words, is that if we have asserted a conditional statement and we have also asserted the antecedent of that conditional statement, then we are entitled to infer the consequent of that conditional statement. For example, if I asserted the conditional, “if it is raining, then the ground is wet,” and I also asserted, “it is raining” (the antecedent of that conditional), then I (or anyone else, for that matter) am entitled to assert the consequent of the conditional, “the ground is wet.”

The lowercase p and q are sentence variables; they stand for any sentence, simple or compound. Thus, any argument that has this same form is valid. For example, the following argument also has this same form (modus ponens):

In this argument we can assert C according to the rule, modus ponens. This is so even though the antecedent of the conditional is itself complex (i.e., it is a conjunction). That doesn’t matter. The first premise is still a conditional statement (since the horseshoe is the main operator) and the second premise is the antecedent of that conditional statement. Modus ponens says that if we have matched the antecedent of the conditional, we are entitled to infer the consequent.

Here's another example of modus ponens:

Notice that the first line is a conditional statement (its main operator is a horseshoe), and the second line is the antecedent of that conditional statement. This allows us to infer the consequent of the conditional. In this case, the consequent is itself a compound statement, so my conclusion should be the entire consequent, not just part of it. However, I can (and should) drop the parentheses. They’re needed in our first conditional, so we can see which horseshoe is the main connective. Our conclusion only has one connective, so it doesn’t need the parentheses to tell us what the main connective is.

So, modus ponens tells us that if we have a conditional, and we have matched the antecedent exactly, then we get exactly whatever the consequent is.

2. Modus Tollens

The next form of inference is called “modus tollens,” which is Latin for “the way that denies.” Modus tollens has the following form:

What this form says, in words, is that if we have asserted a conditional statement and we have also asserted the negated consequent of that conditional, then we are entitled to infer the negated antecedent of that conditional statement. For example, if I asserted the conditional, “if it is raining, then the ground is wet,” and I also asserted, “the ground is not wet” (the negated consequent of that conditional), then I am entitled to assert the negated antecedent of the conditional, “it is not raining.”

It is important to see that any argument that has this same form is a valid argument. For example, the following argument is also an argument with this same form:

In this argument we can assert not-C according to the rule, modus tollens. This is so even though the consequent of the conditional is itself complex (i.e., it is a disjunction). That doesn’t matter. The first premise is still a conditional statement (since the horseshoe is the main operator) and the second premise is the negated consequent of that conditional statement. The rule modus tollens says that if we have that much, we are entitled to infer the negated antecedent of the conditional. Here’s another example of modus tollens:

Both the antecedent and consequent are compound here. That’s ok, it still follows the form. As long as we have the negation of the consequent, we can infer the negation of the antecedent. Notice this time we need to keep the parentheses, because we’re adding a negation. We want to make sure we negate the entire compound statement, so the parentheses need to remain.

With modus ponens, make sure you match the antecedent and infer the consequent. With modus tollens, make sure you negate the consequent and infer the negation of the antecedent. Trying to do this in another order will lead you to do something invalid.

3. Hypothetical Syllogism

The next form of inference is called “hypothetical syllogism.^[2]” This is what ancient philosophers called “the chain argument” and it should be obvious why in a moment. Here is the form of the rule:

If p leads to q and q leads to r, we are allowed to infer that p will lead to r. The “link” in this chain argument must be on opposite sides of the horseshoe—the matching term must be the antecedent of one conditional and the consequent of the other.

We could construct a longer chain, if r led to s and s led to t and so on, and it would be a valid argument, but the rule that we will cite in our proofs only connects two different conditional statements together. As before, it is important to realize that any argument with this same form is a valid argument. For example,

Notice that the consequent of the first premise and the antecedent of the second premise are exactly the same term. That is what allows us to “link” the antecedent of the first premise and the consequent of the second premise together in a “chain” to infer the conclusion. Being able to recognize the forms of these inferences is an important skill that you will have to become proficient at in order to do proofs.

4. Disjunctive Syllogism

The next form of inference we will introduce is called “disjunctive syllogism” and it has the following form:

In words, this rule states that if we have asserted a disjunction and we have asserted the negation of one of the disjuncts, then we are entitled to assert the other disjunct. Once you think about it, this inference should be pretty obvious. If we are taking for granted the truth of the premises—that either p or q is true; and that p is not true—then it has to follow that q is true in order for the original disjunction to be true. (Remember that we must assume the premises are true when evaluating whether an argument is valid). If it is true that either Bob or Linda stole the diamond, and we find out that Bob did not steal the diamond, then it has to follow that Linda did. That is a disjunctive syllogism. As before, any argument that has this same form is a valid argument. For example:

This is a valid inference because it has the same form as disjunctive syllogism. The first premise is a disjunction (since the wedge is the main operator), the second premise is simply the negation of the left disjunct, and the conclusion is the right disjunct of the original disjunction. Notice that the second premise contains a double negation. Your English teacher may tell you never to use double negatives, but as far as logic is concerned, there is absolutely nothing wrong with a double negation. In this case, our left disjunct in premise 1 is itself a negation, while premise 2 is simply a negation of that negation.

Here's one more example of disjunctive syllogism:

We can perform disjunctive syllogism here because we have a sentence where the main connective is a wedge, and we have the negation of one of the disjuncts. That lets us conclude that the other disjunct must be true. Notice that again we can drop the parentheses here when we draw our conclusion. The negation of the first disjunct had to keep the parentheses, however, to make sure that tilde negates the whole sentence.

III. Constructing proofs

We now have enough rules to start proving some arguments. I want to start with a longer chain argument:

If hypothetical syllogism is valid (and it is), this should be too, right? A leads to B, B leads to C, and C leads to D. So if we start with A, it should lead to D. I can’t call this an instance of hypothetical syllogism, though. Hypothetical syllogism has exactly two premises and then tells us what conclusion we get; this has three premises. However, I can use hypothetical syllogism to prove this is also valid.

Think of natural deduction like a game. The rules tell us how we can move. The goal of the game is to start with the premises, and apply our valid rules one at a time until we’re able to generate the conclusion. Not every proof requires you to use every rule, and you can use the same rule more than once. You may use any of the rules—as along as your use of the rule is correct. Like most games, people can be better or worse at the “game” of constructing proofs. Better players will be able to a) make fewer mistakes, b) construct the proofs more quickly, and c) construct the proofs more efficiently. And, like most games, you get better with practice!

Let’s set up our game board. First, I want to number my premises. I’m going to move the conclusion—I want to put it on the same line as the last premise. I don’t want to put the conclusion on a numbered line at this point (assuming your conclusion as a premise is a fallacy called “begging the question”) but I do want to keep my goal in view. The gameboard looks like this:

Now, I look at my premises to see if any of them can be used as input for any of my rules. I see that I have two places where I could use hypothetical syllogism. Lines 1 and 2 are both conditionals, and they have that matching, overlapping link: B. We can say the same thing about 2 and 3, they share the term C. I’m going to apply the rule to lines 1 and 2, though. I write the result of applying the rule on the next numbered line, and then I need to write down which rule I used and which lines I applied it to, like this:

Here’s the cool part—the new line is now a new ingredient I can use. I want to see if I can combine it with any of the other lines as input for one of my rules. I see that line 4 has that matching, overlapping term (in this case C). Get rid of the link, and hook the remaining antecedent and consequent together. Put the result on the next line:

Notice that the last line of the proof is the conclusion that we are supposed to derive, and that each statement that I have derived (i.e., lines 4 and 5) has a rule to the right. The rule, plus the numbers of the lines I applied the line to, are called “justification.” The premises do not need justification, because we’re assuming they’re true. Every line I add to the proof after the premises, though, needs justification. Once I derive the conclusion I was going for, I’ve succeeded. This is what is called a proof. A proof is a series of statements, starting with the premises and ending with the conclusion, where each additional statement after the premises is derived from some previous line(s) of the proof using one of the valid forms of inference. Let’s look at another one.

The first step is to look at our premises, and see if any two of them can be used with any of the rules we know so far. We can only work with the main operators, though. Any other connective cannot be worked with until you can get it as the main operators on a further line. Looking at lines 1 and 3, I recognize the modus ponens we saw earlier in the chapter. Line 1 has a horseshoe as the main connective, and line 3 matches the antecedent of that conditional exactly. That allows me to write the consequent of the conditional on the next line. Don’t forget to record what rule you used, and which lines you applied it to.

My new line gives me a new ingredient. Its main connective is a horseshoe, and on line 2, I have the negation of its consequent. This allows me to use modus tollens to put the negation of its antecedent on the next line.

The last line is the conclusion we were trying to derive. That means we have succeeded in proving our argument valid. We won the game!

Here is some general advice for approaching your proofs.

• At any stage of your proof, you can use any two lines that form suitable ingredients for the rule you wish to apply. The lines do not have to be in order, they do not have to be next to each other, and you can use a line more than once if it comes in handy later in your proof as well. Any two lines—as long as they fit the form of one of our rules.
• Right now you only have four rules. A good strategy when you’re starting is to just pick two lines and see if they fit the form of one of our rules. Every time you see you cannot use a rule, ask yourself “why not?” This will help you learn how to apply the rules.
• Every time you use a rule to derive a new line, look specifically to see if you can use that line with another line and one of the rules.
• Don’t give up. You may not see the general strategy of your proof, but you don’t have to. Every time you successfully apply a rule, you generate a new line you can use, that might give you inspiration.

IV Four More Rules

The next four forms of inference we will introduce utilize conjunction, disjunction and negation in different ways. In the exercises at the end of this section, you’ll use all eight rules in your proofs.

5. Simplification

We will start this section with the rule called “simplification,” which has the following form:

What this rule says, in words, is that if we have asserted a conjunction, then we are entitled to infer either one of the conjuncts. It is a pretty “obvious” rule—a conjunction is an and-type statement, and it means that both conjuncts are true. This rule lets us break apart a conjunction so we can use each conjunct separately in our proofs.

As before, it is important to realize that any inference that has the same form as simplification is a valid inference. For example (and now I’m going to put these applications of rules into the form of a proof):

is a valid inference because it has the same form as simplification. That is, line 1 is a conjunction (since the dot is the main operator of the sentence) and line 2 is inferring one of the conjuncts.

6. Conjunction

The next rule we will introduce is called “conjunction” and is almost the reverse of simplification. Simplification is how we get rid of a conjunction, and the rule conjunction is how we introduce one into our proof. Conjunction has the following form:

What this rule says, in words, is that if you have asserted two different propositions, then you are entitled to assert the conjunction of those two propositions. If you know p is true, and you know q is true, then you know ‘p and q’ is also a true sentence. As before, it is important to realize that any inference that has the same form as conjunction is a valid inference. For example,

is a valid inference because it has the same form as conjunction. We are simply conjoining two propositions together; it doesn’t matter whether those propositions are simple or compound. In this case, of course, the propositions we are conjoining together are complex, but as long as those propositions have already been asserted as premises in the argument, or derived by some other valid form of inference, we can conjoin them together. Notice, though, that before we combine them with a dot, we have to collect each compound sentence in parentheses, to make sure the dot we just added is the main connection of the proposition on that line.

7. Addition

The next rule we’ll introduce is called “addition.” It is not quite as “obvious” a rule as the ones we’ve introduced above. However, once you understand the conditions under which a disjunction is true, then you should be able to understand why this form of inference is valid. Addition has the following form:

What this rule says, in words, is that that if we have asserted some proposition, p, then we are entitled to assert the disjunction of that proposition p and any other proposition q we wish. Here’s the simple justification of the rule. If we know that p is true, and a disjunction is true if at least one of the disjuncts is true, then we know that ‘p or q’ is true even if we don’t know whether q is true or false. Why? Because it doesn’t matter whether q is true or false, since we already know that p is true. I only need one true disjunct to make the whole disjunction true.

Another way to think about it is to compare it with the conjunction rule you just learned. If I want to prove an ‘and’ statement, I have to prove both sides. Conjunction means ‘both of these things are true,’ so I need to prove both things before I can put a dot between them. Disjunctions, on the other hand, mean ‘at least one of these things is true.’ So, to prove an ‘or’ statement, I only have to prove one side of the disjunction before I can introduce a wedge. The cool thing about this rule is that you can introduce anything you want to as your second disjunct. It doesn’t even have to be anything that already occurs in the proof. You’ll want to make sure you introduce whatever you need to finish your proof.

As before, is it important to realize that any argument that has this same form, is a valid argument. For example,

is a valid inference because it has the same form as addition. The first premise asserts a statement (which in this case is compound—a disjunction) and the conclusion is a disjunction of that statement and some other statement. In this case, that other statement is itself compound (also a disjunction). But an argument or inference can have the same form, regardless of whether the components of those sentences are simple or compound.

As with conjunction, if the disjuncts are compound, you need to use parentheses to group them together, so the wedge you introduced is the main connective of your new line.

8. Constructive Dilemma

The eighth valid form of inference is called “constructive dilemma” and is the most complicated of them all. It may be most helpful to introduce it using an example. Suppose I reasoned thus:

The killer is either in the attic or the basement. If the killer is in the attic, then he is above me. If the killer is in the basement, then he is below me. Therefore, the killer is either above me or below me.

That this argument is valid should be obvious (can you imagine a scenario where all the premises are true and yet the conclusion is false?). What might not be as obvious is the form that this argument has. However, you should be able to identify that form if you utilize the tools that you have learned so far. The first premise is a disjunction. The second premise is a conditional statement whose antecedent is the left disjunct of the disjunction in the first premise. And the third premise is a conditional statement whose antecedent is the right disjunct of the disjunction in the first premise. The conclusion is the disjunction of the consequents of the conditionals in premises 2 and 3. Here is this form of inference using symbols:

Constructive dilemma is almost like a double modus ponens. I have two conditionals, and I know that at least one of the antecedents is true (even though I don’t know which one), so I can derive that at least one of the consequents is true (even though I don’t know which one). Constructive dilemmas are often used in decision-making reasoning. Suppose I need to decide between p and q. I know p leads to r, and q leads to s, so I know I will end up with either r or s as a consequence of my decision. Now all I need to do is figure out which outcome looks more appealing to me.

We have now introduced eight forms of inference. In the next section I will walk you through some basic proofs that utilize these eight rules.

V. More help in how to construct proofs

The introduction of rules 5 through 8 complicate proof construction. With just rules 1 through 4, you can just apply any rule you have the ingredients for, and you will usually get to the conclusion eventually. With all eight rules, it often helps to work out a strategy, so here are a few tips on that process.

In order to construct proofs, it is imperative that you internalize the eight valid forms of inference. By “internalize” I mean that you have memorized them so well that you can see those forms manifest in various sentences almost without even thinking about it. If you internalize the rules in this way, constructing proofs will be a pleasant diversion, rather than a frustrating activity. In addition to memorizing your rules, there are a couple of different strategies that can help when you’re stuck and can’t figure out what to do next. The first is the strategy of working backwards. When we work backwards in a proof, we ask ourselves what rule we can use to derive the sentence(s) we need to derive. Here is an example:

The conclusion, which is to the right of the second premise and follows the ‘therefore’, symbol, is a conjunction (since the dot is the main operator). If we are trying to “work backwards,” the relevant question to ask is: What rule can we use to derive a conjunction? If you know the rules, you should know the answer to that question. There is only one rule that allows us to introduce a conjunction; that rule is called “conjunction.” The form of the rule conjunction says that in order to derive a conjunction, we need to have each conjunct on a separate line. We already have the second conjunct on its own line, so the only other thing we need to derive is first conjunct. Once we have that on a separate line, then we can use the rule conjunction to connect those two sentences with a dot to get the conclusion.

The next question we have to ask is: How can I derive the sentence “T v L”? Again, if we are working backwards, the relevant question to ask here is: What rule allows me to introduce a disjunction? There are only two: constructive dilemma and addition. However, we know that we won’t be using constructive dilemma since none of the premises are conditional statements, and constructive dilemma requires conditional statements as premises. That leaves addition. Addition allows us to disjoin any statement we like to an existing statement. Since we have “T” as the second premise, the rule addition allows us to disjoin “L” to that statement. The first new line of the proof should thus look like this:

The next step of the proof should be clear since we have already talked through it above. All we have to do now is go directly to the conclusion, since the conclusion is a conjunction and we now have (on separate lines of the proof) each conjunct. Thus, the final line of this (quite simple) proof should look like this:

The order in which you cite the lines doesn’t matter, as along as you have cited the correct lines (that is, I could have equally well have written, “Conjunction, lines 3 and 1” as the justification). The complete proof should look like this:

The last line of the proof is the conclusion to be derived: check. Each line of the proof follows by the rule and the line(s) cited: check. Since both of those requirements check out, our proof is complete and correct.

I have just walked you through a simple proof using the strategy of working backwards. This strategy works well as long as the conclusion we are trying to derive is complex—that is, if it’s a compound statement. However, sometimes our conclusion will be a simple statement—a single letter with no connectives. In that case, we will not as easily be able to utilize the strategy of working backwards. So, you can use the strategy we learned with the first four rules: working forward. To remind you of how this strategy works, we ask ourselves what rules we can apply to the existing premises to derive something, even if it isn’t the conclusion we are ultimately trying to derive. We look to see if any of our lines are good ingredients for any of our rules. As a part of this strategy, here are some suggestions:

1. If you see a conjunction as the main connective, break it apart using simplification.
2. If you see a disjunction, see if you can find the negation of one of its disjunct.
3. If you see a conditional, see if you can find the antecedent on a separate line for modus ponens, or the negation of the consequent for modus tollens.
4. If you see two conditionals, see if they have an overlapping term, for hypothetical syllogism, or a disjunction on another line for constructive dilemma.
5. If you see a negation as the main connective, look to see if you can do a modus tollens or a disjunctive syllogism.

Here is an example of a proof where we should utilize the strategy of working forward:

Notice that since the conclusion is a simple statement, it doesn’t give us any clues to help us work backward. So, we’ll work forward. The first line is a conjunction: every time you see a dot as the main connective, you should use the rule simplification to break it apart. If you can see which conjunct you need, just take that one. If you’re not sure, apply simplification twice, so you’ll have both conjuncts as new ingredients in your proof, like this:

The first two lines of the proof are the result of breaking down the conjunction in line 1, where line 3 is the left conjunct and line 4 is the right conjunct. We then ask the question, do any of these four lines look like ingredients for one of my rules? I have a conditional on line 2 (and it’s the only conditional, so I won’t be using hypothetical syllogism or constructive dilemma), so following the third tip in my list above, you want to look for its antecedent or the negation of its consequent on a different line. We now have that antecedent on line 4, and that that means we can apply the rule modus ponens:

The line that we have just derived is in fact the conclusion of the argument. So, our proof is finished.

Some proofs you’ll want to work backwards, some proofs you’ll want to work forwards. With some longer proofs, you might work both backwards and forwards and meet somewhere in the middle—see what ingredients you can use, but also look for what ingredients you’re going to need, based on your conclusion. Remember: any proof, long or short, is the same process and utilizes the same strategy. It’s just a matter of keeping track of where you are in the proof and what you’re ultimately trying to derive. So here is a bit more complex proof:

Before you read any further, take a minute and try this proof on your own, then come back and compare yours to mine. Your proof might not be exactly like mine—it could be longer, shorter, or do the steps in a different order—but as long as you’ve used all of the rules correctly, and your last line is the conclusion you wanted, you’ve done your proof correctly.

Using the strategy of working backwards, we see the conclusion is a conjunction, so we know that if we can get each of those conjuncts on a separate line, then we can use the rule conjunction to derive the conclusion. This is our long-term strategy. However, we cannot see how to get there from here at this point, so we’ll begin working forward. The first thing we’ll do is simplify the conjunction on line 5, putting each conjunct on a separate line:

Look at lines 2 and 6: they are both negated simple propositions, so I want to see if I can use them with other lines, to do a modus tollens or disjunctive syllogism. Looking at lines 2 and 3, I see the ingredients for a modus tollens. That will be our next step:

The next step of this proof can be a bit tricky. There are a couple different ways we could go. One would be to utilize the rule “addition.” Can you see how we might helpfully utilize this rule using either line 6 or 8? If not, I’ll give you a hint: what if we were to use addition on line 8, adding a wedge B? We’d end up with the antecedent of the conditional in line 1, so we could then use modus ponens to derive the consequent. Thus, let’s try starting with the addition on line 8:

Next, we’ll utilize line 9 and line 1 with modus ponens to derive the next line:

Notice at this point that what we have derived on line 10 is “L,” and this is very close to one of the conjuncts I wanted to derive for my conclusion. The first conjunct in the conclusion is a disjunction, and I now have one of those disjuncts—I can use “addition” again to add the other. That will be the next line of the proof:

We have one conjunct of our conclusion. At this point, our strategy should be to try to derive the other conjunct, not-R. Notice that it’s contained within the sentence on line 4, but it is embedded. How can we “get it free”? Line 4 has a horseshoe as its main operator; I first want to get rid of the antecedent and the horseshoe. I’ve matched the antecedent on line 10, so I can do a modus ponens, and write the consequent on the next line:

This is a disjunction, so I’ll want to get rid of the wedge and the D. Looking at line 6, and combining it with our new line 12, I see I have the ingredients for a disjunctive syllogism:

The final step is simply to conjoin lines 11 and 13 to get the conclusion (make sure you gather line 11 in parentheses, so the new dot ends up being the main connective):

Here is the completed proof:

Constructing proofs is a skill that takes practice. Don’t give up, just keep trying.

1. This chapter is based on Introduction to Logic and Critical Thinking, by Matthew J. Van Cleave. ↑

2. Strictly speaking, any two premise deductive argument that uses a conditional to get its conclusion is a hypothetical syllogism; so, modus ponens and modus tollens are also hypothetical syllogisms. In this chapter, however, we’ll reserve the term “hypothetical syllogism” just for this chain-argument rule. ↑