Introduction: a contrived analogy

As mentioned at the end of the previous section, this is where things start to get interesting. Yes, it will require the memorization of a bunch of more rules - but the payoff will be worth it. We will say goodbye to cumbersome truth tables and instead test validity by setting up a chain of reasoning (often called a derivation). This is quite similar to how you would reason in a debate, but in a strictly deductive format. Let me paint a contrived picture of how we will view the proof method: 

You and your friend, Daniel, mysteriously find yourselves at the top of a giant staircase. The thin, chilly air makes you shiver; your head hurts, and you have a freshly sutured wound on your lower abdomen. You reach into your pocket and find a mysterious note reading “Scatman’s World.” You hear the distant cry of an eagle (“bi-bap-bap-bada-bom!”). What’s going on here? Where are you? All you know is that you and Daniel need to reach the bottom to find some answers. But Daniel confesses that he’s never walked down a flight of stairs before. “I don’t know how,” he says. Your goal is to go down the stairs to find the answer to your present circumstances and to bring Daniel with you. But, in order to bring Daniel along, you will have to trace each step down the stairs.

So yes, that’s the proof method. In this part, I will show you some inference rules. This will be our method of tracing our steps for Daniel to gather courage and follow along. So come along with me, let’s reach rock bottom together.

Cast of Characters

Terminology Recap

Before we begin defining and using the inference rules, let’s just remind ourselves of some terminology related to the Boolean operators. This will streamline the language used when defining the inference rules.

• Antecedent = the constant or variable that comes before the conditional arrow (i.e. p in “if p then q)

• Consequent = the constant or variable that comes after the conditional arrow (i.e. q in “if p then q)

• Conjunct = a constant or variable bound by a conjunction (i.e. p, q are the conjuncts in “p and q”)

• Disjunct = a constant or variable bound by a disjunction (i.e. p, q are the disjuncts in “p or q”)

8 inference rules

We’re going to learn 8 inference rules. These will form the method with which we trace our steps in our derivation. Two things to note here. First, these rules are unwavering and true in our logic. If you doubt me, feel free to construct truth tables for them. Otherwise, just memorize them. Second, you’re never required to use any one of the rules; it’s just that (when the right conditions are met) you can use them. There’s a lot of creativity in deriving proofs: oftentimes there are many ways to derive a proof - meaning you can use different inference rules to arrive at the same conclusion. Anyways, here are the rules: 

1. Modus ponens (M.P.)

2. Modus tollens (M.T.)

3. Conjunction (Conj.)

4. Disjunctive syllogism (D.S.)

5. Addition (Add.)

6. Hypothetical syllogism (H.S)

7. Simplification (Simp.)

8. Dilemma (Dil.)

Notice the abbreviation in brackets for each rule. This will be our shorthand for noting which inference rules we apply once we derive proofs (more on that later). 

down the stairs: Examples of Proofs

Let’s try our hand at a couple examples. I’m going to handwrite these, because I’m lazy. Maybe I’ll come back to this and make it prettier.

Example 1

Here’s an example with 5 terms - X, Y, Z, D and F. Proving the validity with the truth table method would be an absolute pain (we would need 32 rows in our table). As you can tell, each premise is annotated with “Pr.” (for, you guessed it, “Premise”), and we have the conclusion on to the right of the last premise. This is the reasoning behind the writing convention: we write the conclusion to the right of the last premise because we will utilize the space below the premise. After all, we have yet to prove the conclusion, and there is going to be a number of steps required for us to get there. The “Pr.” annotation is there because we want to make sure what information we are allowed to start with. These proofs can become long, so it’s good to be clear on what tools you have from the get-go. A final note on the annotation: once we start applying the rules, we will annotate these in the same way as the premises are annotated, but with the abbreviation of the rule and the steps the rule is referencing. So, for example: if we wanted to use modus tollens on Premise 2 and (some hitherto unknown) Step 5 at Step x, we would write “M.T. 2,5” to the right of Step x (same place where the “Pr.” is). Don’t worry, you’ll see what I mean once we start working on the proof.

Hot Tip #1: Gain intuition by thinking backward

A good starting strategy is to look at the conclusion first in order to get a sense of what the steps might be. What is it comprised of? In this case, we have a disjunction. This is good news: thanks to the Addition Rule, we only need to derive one of those terms (either D or not-Y). The other term we get for free because using addition allows us to disjoin whatever else we want (hint, the other term). Nice. Now we have an idea of what the last step of the derivation will be. Now we need to think about how we will get there.

Hot Tip #2: Find hot singles in your area

When in doubt, see whether there are any single terms in the premises, or if there are any ways to easily derive single terms from the premises. A good indication of the latter is if you have a conjunction. If you do, you can use the Simplification rule. Of course, if the conjunction is a complex statement with subformulas on either side of the conjunction, you can only simp to derive the subformulas. But that’s fine, because that may still get you somewhere. The trick is to derive as many smaller components from the premises as possible. Because this way you will create opportunities to use more inference rules. As we learned before, there are often many ways to derive a proof. The benefit of individuating the premises as much as possible is that you maximize the possible inference rules you could use, which is very useful if you reach a dead end. The same applies in an informal discussion where you’re trying to prove something: if the thing you want to prove/persuade your friend about is very complex, then you’re often better off breaking it down into its basic components, verifying these with your friend, and then building it back up. 

Anyways, let’s look at what we have. Premise 4 is a conjunction between not-D and not-Z. Great, let’s simp premise 4 twice to derive each of these terms.

Nice, now we have some more stuff to work with. Let’s look at what else we have in the premises. We have 3 conditionals. So, chances are we’re going to have to use one or more of the rules related to conditionals. One such rule comes to mind: Modus Tollens. Because we diligently simped our way to step 6, we now have 1) the negated consequent to Premise 2; and 2) we have the negated consequent to Premise 3. That’s exactly what we need to apply modus tollens on both of these. You are perfectly welcome to do that: in fact, when in doubt derive as much as possible (as mentioned in Hot Tip 2). Redundancy in proofs is fine. Redundancy in proofs is fine. Redundancy in proofs is fine.

But, because I know the answer already, I know that applying modus tollens on premise 3 is not gonna get us anywhere: we will get not-D, which is the opposite of what we need in the conclusion. So, no use doing that. Let’s just apply the rule on Premise 2, in order to get not-X. Then take stock of where we are. Remember to reference the steps used by the rules. For instance, in the case of Premise 2, we’re applying modus tollens using steps 2 (of course) and 5.

Now we’ve gained not-X in our derivation. Looking at our premises, there’s only one place where not-x (or x) occurs - which is in Premise 1. Here we have not-X as the antecedent in a conditional. This is great news for us because that means we can use premise 1 and newly derived not-x via modus ponens. This will yield not-Y. “Hey, that’s one of the things in the conclusion!” you exclaim in pure ecstasy. You’re darn tootin’ it is. This means we’re just about done.

Now there’s only one last thing to do. Because the conclusion is a disjunction, and we have now derived one of the disjuncts, we just add the other disjunct out of thin air. No big deal.

In just 9 lines we were able to derive a proof for this thing. It sure beats constructing a 32-row truth table to do the same thing.

Example 2

This one is a bit more complicated: lots of stuff going on in these 6 premises. But hey, feel free to use the truth table method - you’ll only need 2048 rows... THAT’S WHAT I THOUGHT. I’m going to speed things up a little bit by explaining a few steps at a time instead of one at a time.

Let’s apply the same initial strategies as in Example 1: the conclusion is a conjunction between a simple term and a negated term. Because there’s no place where this conjunction appears in the premises, we will have to derive both these individually in the proof and in the final step use the conjunction rule.

Also, it looks like we can find 2 hot singles in our area by simping premise 6 twice. We’re off to a good start.

Now we’ll take a look at where we could use either of these new terms. Doesn’t look like we can use not-Y anywhere, but that’s fine*. It looks like we can use not-Z on Premise 5 via modus tollens to yield the negation of not-Φ, i.e. NOT-not-Φ (more about double negation in Part Five). Once we have that we can use the disjunctive syllogism on Premise 4 to derive not-(E or G).

* Using the backward thinking strategy again: we only need to derive B and conjoin it to our not-Y in order to have the conclusion (since we already have not-Y)

VEERY NICE (hehe, like in that movie, “Boris”). Anyways, let’s see if we can do anything with step 10. By now we wouldn’t know how to individuate that compound sentence (we will learn a way to do that in Part Five), so no use looking for hot singles in our area. BUT, it seems like we’re in luck: Premise 3 is a conjunction where the consequent is the disjunction (E or G). We have the negation of that! So, let’s apply modus tollens on 3 to derive not-K.

Not-K appears as part of a disjunction in Premise 2. This disjunction is the antecedent of the conditional. If we can get the other disjunct (not-M) we could apply modus ponens to yield the consequent (A and C). But wait, we can just use addition here. Let’s just add not-M to Not-K (Step 11). Then we’ll just use modus ponens on Premise 2 (via Step 12). Because the consequent is a conjunction (A and C), we can simp twice to find hot singles in our area. We’ve now worked up to Step 15.

Now that we have both A and C on their own, let’s see where they are used. Aside from Premise 2 (from which we derived A and C in the first place), only Premise 2 uses either of these (in this case both). But this is good news because it uses A as a standalone antecedent, meaning we can derive the big consequent via modus ponens. We’re getting very close to finishing because we’re able to work on the premise containing B - the single term we need to conjoin to our already derived not-Y in order to finish this thing.

This is where C comes to the rescue. Because Step 16 is a conditional with the disjunction (C or θ), and we already have C, we can just use the addition rule by adding the θ to C. At that point, we have the full antecedent. So we’ll use modus ponens to FINALLY derive B! Then, the icing on the cake: take our not-Y (all the way from Step 8) and conjoin it to our newly derived B, to yield the conclusion. Done!

Part Four Wrap-Up

What we have learned

We have learned 8 basic inference rules and how to construct proofs as an alternative method to truth tables. The rules are:

1. Modus ponens (M.P.)

2. Modus tollens (M.T.)

3. Conjunction (Conj.)

4. Disjunctive syllogism (D.S.)

5. Addition (Add.)

6. Hypothetical syllogism (H.S)

7. Simplification (Simp.)

8. Dilemma (Dil.)

We used some of these rules (Simp., M.T., M.P., Conj., D.S. and Add.) in two examples.

Where we are going next

In the next part, we’re going to look at an additional set of rules - Replacement Rules. The function of these is mainly to assist in the application of the inference rules you just learned. But anyway, as has been the theme for the last little bit, you need to practice doing proofs and memorize the inference rules. Otherwise things are going to get really difficult.