Lecture Notes 5: Direct Derivations

Introduction to Derivations

Problems with Truth Tables

Truth tables are great. They can tell us almost anything we’d wish to know about a statement or argument in propositional logic.

But they have two problems.

1. They grow in size exponentially. (Six atomics means 64 rows.)
2. They’re alien to the way we ordinarily think.

Our new unit focuses on a new way of establishing the validity of an argument without these flaws.

Step by Step Reasoning

Consider the following form:

This is an obviously valid form close to how we in fact reason. This form is called modus ponens.

(The fancy script letters 𝒜, ℬ, 𝒞 are placeholders for any formulas, simple or complex.)

Now consider:

This argument is not, strictly speaking, of the same form as the one above, and it is not quite as obviously valid.

It is valid, nevertheless, and we can prove that by showing how the conclusion follows from a chain of smaller arguments similar to our first example.

To put it roughly:

1. Since A → B and A, we can conclude B.
2. Now that we know B and already knew B → C, we can conclude C.
3. Once we know C, since we know C → D, we can finally arrive at our conclusion, D.

What we have done is broken up this argument into a number of smaller arguments. We have shown that, by means of a number of small, obviously valid, steps in reasoning, we know that the conclusion must be true if the premises are true. That is, we have proven that the argument is valid.

This method of proving an argument to be valid is just that: a proof.

In this class, we set up these proofs in a very specific format, and we call them derivations, because, through a chain of reasoning, we derive the conclusion from the premises.

The Direct Derivation Method (DD)

Suppose we wanted to construct a derivation for the validity of the following argument:

To construct a formal proof, begin by numbering the premises and writing them out.

We also write the abbreviation “Pr” on the right to remind us that these are the premises with which we began.

We then introduce a new line for the conclusion. However, we write the word “SHOW” before it, to indicate that this is what we are trying to derive, and not something we are already taking as true.

On the right of the SHOW line we will write “DD” for the “show-rule” called Direct Derivation. Eventually we will learn other show-rules.

Underneath this we will construct our step-by-step derivation.

The derivation should always be indented slightly, as we will draw a box around the derivation when we finish. (Online we represent the box we will eventually draw with a light dotted line.)

The first step of this derivation looks like this:

What we have written at line 4 follows from the first two premises by modus ponens.

We had an if-then statement at line 1, and the if-part of that statement at line 2, so we concluded the then-part at line 4.

On the right we wrote “1, 2” to indicate that the justification of this new line comes from lines 1 and 2.

The “→O” means that we arrived at this line by means of modus ponens. We’ll learn abbreviations for a number of different derivation steps as we go along.

We still have not gotten to our conclusion.

Now that we have line 4, and keeping in mind what we had in line 2, we can perform another modus ponens.

Again we write “→O” on the right because this was another modus ponens, but notice now we made use of lines 2 and 4 in our reasoning instead of 1 and 2.

In doing a derivation, every new line we introduce should be “justified” by some of the earlier lines. However, we can never make use of SHOW lines in justifying a new line.

In this case, it was OK for us to appeal to 1 and 2, and to appeal to 4 once we had shown it, but we couldn’t have appealed to line 3, since that is what we were trying to prove!

What we have at 5, B, is what we were trying to show at line 3. (QED, or “Quod erat demonstrandum” as they say in Latin.)

Therefore, we have done what we were trying to do. In finishing, we draw a box around our derivation (lines 4 and 5), cross off “SHOW” since we have shown it.

You do not need to draw the entire box, but can draw any portion of it that includes the left side. (The book usually only draws the left side.)

On the computer, clicking the word “SHOW” will cross it off, and draw the box. (Clicking it again will undo this.)

Try our first example for yourself:

When a derivation’s box is open for the online exercises, you’ll see buttons at the bottom. The first can be used for inserting a new line. The last is an alternative way of closing the box and crossing off the show line. On the right, you’ll see a button for performing other changes to that line, or above or below it. We’ll talk about the other button later.

You’ll also notice buttons at the bottom for giving hints and checking the derivation, etc. In the lecture notes, and in the warm up problems, there’s a gray-ed out button that toggles on and off auto-checking each line as you go.

The rule of modus ponens is a very natural and powerful rule. You will be using it more than any other inference rule.

It is worth noting that it applies not only when the if-parts and then-parts (“antecedents” and “consequents” in logical terminology) of if-then statements are simple, but also when they are complex.

Yes, it’s OK to use the same premise twice.

This eleven-step derivation may seem very long and complicated. However, compare it to having to do a truth table for the same argument.

For these five premises and one conclusion, the table would have 128 rows and 28 columns, for a total of 3584 T’s and F’s!!

The Simplest Inference Rules

We will begin by learning the four simplest valid inference or derivation rules.

The first two involve two ways of using or “breaking up” an if-then statement, and they are both abbreviated as “→O” for “Arrow Out”.

The first one is the famous modus ponens, which we’ve already been using.

The other is called modus tollens in Latin.

An example of an English argument that uses modus tollens reasoning is:

Example. If Macavity stole the diamonds, then Macavity’s hair was left at the scene of the crime. Macavity’s hair was not left at the scene of the crime. Therefore, Macavity did not steal the diamonds.

Simply put, if an if-then statement is true, but the then-part is false, the if-part must be false as well.

Modus ponens is Latin for “affirming mode”.

Modus tollens is Latin for “denying mode”.

Here are some derivations that make use of this form of “→O”.

Here are some that use both forms of “→O”.

This last example shows that our rules are very strict. Modus tollens takes the form:

We have to plug things in uniformly for “𝒜 ” and “𝒞 ” here.

If 𝒞  already begins with a negation, then we need a double negation to apply the rule.

Similarly, if 𝒜  already begins with a negation, the thing we get in the end will be a double negation.

We can’t simply drop these off. We need a separate rule for that, which we will learn later.

The next two rules are rules for using or breaking up an Or-statement, and they are abbreviated as “∨O” for “Wedge Out”.

Simply put, if we know an Or-statement is true, and we know that one of the two sides (“disjuncts”) is false, we know the other side (the other disjunct) must be true.

Here’s an example in English.

Example. Either the US team will win the gold medal or the Canadian team will win the gold medal. The US team will not win the gold medal. Therefore, the Canadian team will win the gold medal.

The ∨O rule is also sometimes called “disjunctive syllogism” or (in Latin) “modus tollendo ponens”.

Here are some derivations that make use of these rules.

Here are some derivations that make use of all the rules covered so far.

Pitfalls to Avoid

The following argument forms are invalid and must never be used!

These may appear superficially similar to the real rules, but a little reflection shows that the slight differences matter.

The first two are not cases of “→O” and the latter two are not cases of “∨O”.

Another problem that must be avoided is applying the rules to parts of lines.

These rules only apply when the whole statement is of the right form.

“→O” cannot be used if the main connective of a statement is not the arrow.

One cannot go from
(P → Q) ∨ R
and
~Q
either to ~P or to R!

Rules must be applied to whole lines.

Other Direct Derivation Rules

So far we have learned →O and ∨O.

To these we now add:

It is worth noting that ∨I, &O, ↔O and DN require only one line for justification, whereas ∨O, →O, &I, and ↔I require two. This always matches the number of statements above the line in the form for the rule.

The OUT rules are rules for using statements of a certain form (with a certain main operator). These rules “break up” a statement with that main operator and yield something without (or with at least one fewer occurrence of) that operator.

The IN rules are rules for deriving or getting statements of a certain form.

With all of these rules in place, we can prove the validity of a wide variety of different arguments.

Here are some sample derivations.

These next examples show that DN is often used to set up →O or ∨O:

Step 6 cannot be done without DN first!