Chapter 3: Derivations

Suppose we wish to know whether the argument

P → Q, Q → R, R → S, S → T ⊢ P → T

is valid. The notation here is very easy---the premises to the argument are to the left of the turnstile "therefore" symbol (namely "⊢") and are separated from one another by commas. The conclusion is to the right of the "therefore" symbol. We might reason like this. We do know that the simpler argument

P → Q, Q → R ⊢ P → R

is formally valid. The formal validity of this argument means that we know that when P → Q and Q → R are true, then P → R must be true as well (call this "Fact 1"). And because the argument is formally valid, we know that other arguments of the same form are also deductively valid. For example, R → S, S → T ⊢ R → T is deductively valid (call this "Fact 2"). So, we know that when R → S and S → T are true, R → T is true. We also know, on the same basis, that when P → R and R → T are true, then P → T is true (call this "Fact 3").

Why the blizzard of letters? What is the value of all this? Here is how this helps us. In a situation where the premises P → Q, Q → R, R → S, S → T are all true, we know that P → R must be true (by Fact 1). And, we also know that R → T must be true (by Fact 2). So, we know that P → T must be true (by Fact 3). Graphically, you can think of what's happening in this way:

When the premises on the top are all true, our knowledge of valid arguments tells us that the premises on the second row must be true. But our knowledge of valid arguments also tells us that when the premises on the second row are all true, the conclusion at the bottom must be true.

That means that when the premises at the top are all true, the conclusion at the bottom must be true. And that is just to say that the argument

P → Q, Q → R, R → S, S → T ⊢ P → T

(the one we were wondering about) is valid. Truth flows through the argument like water flowing through pipes, or electricity through wires.

This type of object---a series of arguments linked together---is called a direct derivation. We'll introduce some special sorts of direct derivations later on, so for now, let's just talk about the "simple" direct derivations.

Direct Derivation: A (simple) Direct Derivation is a sequence of assertions, each of which is justified, either because it is a premise or because it is the conclusion of a valid and recognized argument whose premises are assertions that have already occured in the derivation.

In this section, we will learn a little bit about how to make use of direct derivations. We will need to do two things. First, we need to decide which valid arguments we will "recognize" in direct derivations. We need to decide on some small set so that other people, who might not know the same arguments as us, will be able to see the correctness of our derivations. Second, we need to decide how to organize our derivations so that they will be readable and easy to check for correctness.

Let's begin by deciding on which arguments we will "recognize" in direct derivations.

Rules of Direct Inference

Let's call the forms of argument that we will recognize in direct derivations rules of direct inference.

Rules of Direct Inference: A rule of direct inference is an argument form that we recognize as valid for purposes of constructing derivations

The fact that we're qualifying our rules by calling them "direct" might suggest that there are some "indirect" rules too. Indeed there are. We will encounter some eventually, but we begin with the direct rules, which are simpler.

Two good argument forms to start with are Modus Ponens, and Modus Tollens. They are about as simple as it is possible for an argument form to be.

Modus Ponens and Modus Tollens

Modus Ponens (abbreviated MP), the argument form
ϕ → ψ, ϕ ⊢ ψ
is a rule of direct inference.
Modus Tollens (abbreviated MT), the argument form
ϕ → ψ, ¬ψ ⊢ ¬ϕ
is a rule of direct inference.

Notice that we are using a different kind of symbol here, to describe argument forms. The letters ϕ and ψ are from the Greek alphabet. We use them because the modus ponens and modus tollens argument forms do not have anything to do with any particular sentence letters. Rather, they are logical forms that particular arguments may have. Any argument that you get by substituting actual sentences for ϕ and ψ in the form ϕ → ψ, ϕ ⊢ ψ is deductively valid, and is an example of a modus ponens argument.

The following arguments are all examples of the modus ponens argument form:

P → Q, P ⊢ Q
Q → P, Q ⊢ P
(Q∧R) → P, (Q∧R) ⊢ P
Q → (P∧R), Q ⊢ (P∧R)

The following arguments are all examples of the modus tollens argument form:

P → Q, ¬Q ⊢ ¬P
Q → P, ¬P ⊢ ¬Q
(Q∧R) → P, ¬P ⊢ ¬(Q∧R)
Q → (P∧R), ¬(P∧R) ⊢ ¬Q

We will also begin with two other rules of direct inference.

Double Negation

Double Negation Introduction (abbreviated DNI), the argument form
ϕ ⊢ ¬¬ϕ
is a rule of direct inference.
Double Negation Elimination (abbreviated DNE), the argument form
¬¬ϕ ⊢ ϕ
is a rule of direct inference.

These will be all of our initial rules of direct inference. More rules will be introduced as we proceed.

Direct Derivations

In order to use a direct derivation to show something we will need to keep track of a couple of things. First of all, we will need to keep track of what we are trying to show, so that others can know what we are intending to do. Second of all, we will need to keep track of what we have already shown, since each new step must be based on previous steps or premises. Third, we will need to keep track of the justification for each step that we are making, so that we, and others, can easily verify the correctness of each step in our reasoning.

Suppose we are given an argument, with some premises and a conclusion. Let us keep track of what we intend to show by writing "Show", followed by the conclusion that we are aiming to show follows from the premises. We can call this line the show line

We then need to give the list of reasoning steps. Let's indent these a little to keep them apart from the show line. To further organize them, let's give each assertion a number. Finally, to keep track of the justification for each step we are making, let's write an abbreviated explanation to the right of the assertion, preceded by a colon (too keep it apart from the assertion). This explanation can be either "PR", meaning that the assertion is one of the premises of the argument, or it can be the name of a rule, followed by numbers of the previous lines which when taken as premises of the rule, justify the assertion.

Finally, when we have finished and managed to produce the assertion which we are trying to show, let's write down the number of the line where we produced this final assertion, and the abbreviation "DD", meaning "I have produced this assertion by direct derivation". To make it easy to see that this goes with the show line, let's give it the same amount of indentation as the show line.

The result will look like this:

1. Show: φ
2.    Assertion1 :Justification1
3.    Assertion2 :Justification2
4.    Assertion3 :Justification3
5.    φ          :Justification3
6. :DD 5

Though, of course, the number of lines is unimportant, and we'd have real assertions and justifications in place of the words "assertion" and "justification.

For example, suppose we are trying to use a direct derivation to show that the argument P, P → Q, Q → R ⊢ R is valid.

We begin with a show line, saying that we want to show R. We then write down the premises P, P → Q, Q → R on lines 2-4. Finally we use modus ponens (MP) to get Q on line 5 from the premises P and P → Q---so we write Q on line 5, and a justification (MP) to the right, with the line numbers of the premises P (line 2) and P → Q (line 3). We do the same thing, on the basis of premises Q and Q → R to assert R on line 6. We then label that we have found R on the basis of a direct derivation, by writing DD 6. The result looks like this:

1. Show: R
2.     P    :PR
3.     P->Q :PR
4.     Q->R :PR
5.     Q    :MP 2,3
6.     R    :MP 4,5
7. :DD 6

Here is another example. Suppose we are trying to use a direct derivation to show that the argument P → Q, ¬P → R, ¬Q ⊢ R is valid. We begin with a show line. We then write down the premises P → Q, ¬P → R and ¬Q on lines 2-4. Using Modus Tollens, we can infer ¬P from ¬Q and P → Q. So we do this, writing down ¬P on line 5, and indicating that we are using modus tollens (MT) on lines 2, 4 to get this result. But using ¬P, and ¬P → R, we can get R using Modus Ponens. So we write down R on line 6, and indicate the justification for this assertion beside it. The result looks like this:

1. Show: R
2.     P->Q  :PR
3.     ~P->R :PR
4.     ~Q    :PR
5.     ~P    :MT 2,4
6.     R     :MP 5,3
7. :DD 6

One more example. Suppose we are trying to use a direct derivation to show that the argument ¬P → Q, ¬Q ⊢ P is valid. We begin with a show line. We then write down the premises ¬P → Q and ¬Q on lines 2-3. We can use modus tollens with these premises to write down ¬¬P on line 4. Then, on line 5, we can write down P, using the assertion on line 4, plus the rule of double negation elimination (which we may cite as DNE). The derivation looks like this:

1. Show:P
2.     ~P->Q :PR
3.     ~Q    :PR
4.     ~~P   :MT 2,3
5.     P     :DNE 4
6. :DD 5

Problem Set 4

Construct derivations to show the validity of the listed arguments.

Abbreviations are the same as in previous chapters. When the argument turns a light green color, then you can press the "submit" button to submit your work.

4.1

4.2

4.3

4.4

4.5