Conditional Derivations

Direct Derivations are not the only kinds of derivations. There are, in fact, two more basic types of derivations we will consider. The first of these is called a Conditional Derivation. It is a derivation which aims to derive a conditional statement by assuming the assertion on the left side of the conditional, and then using whatever means are available to reach the statement on the right side of the conditional.

Intuitively, when you construct an indirect derivation, what you are doing is imagining, for a moment, that some statement (your “hypothesis”) is true and seeing what else would be true in that case. When you figure out something that would be true in the situation where your hypothesis is true (your “result”), that entitles you to assert “If this hypothesis is true, then this result is true as well”.

This process may be familiar from, for example, hypothetical questions on exams.

When you know the answer to a hypothetical question like this one:

Suppose that a NASCAR race car is moving to the right with a constant velocity of +82m/s. What is the average acceleration of the car?

You probably don’t know anything about any particular actual car (after all, you have no idea of the current velocity of any NASCAR car). What you do know, if you know the answer, is that if a NASCAR race car is moving to the right with a constant velocity of +82m/s, then the average acceleration of the car is zero m/s2.

It may also be familiar with assuming something temporarily, to figure out what would happen if it were true, from games of strategy, like Tic Tac Toe, Checkers, Chess, Go, and others. In games like this, it is often useful to be able to predict what will happen if we make a certain move.

You probably realize that in this situation:

where it is X’s turn, if X makes a move in the middle spot, then X can win on the next turn. How do you know this? This is, after all, in effect an ability to predict the future. Even though it a common sort of future-prediction, it might seem rather mysterious how we are able to accomplish this. Many people tend to believe that when we make predictions about the future, we do so only because we generalize from a pattern encountered in our previous experience. This view is often thought to be common sense nowadays partly because, about sixty or seventy years ago, it was a popular view among a group of philosophers called Logical Empiricists (The economist John Maynard Keynes said that “even the most practical man of affairs is usually in the thrall of the ideas of some long-dead economist.”—the same goes doubly for people who pride themselves on their common sense, and the ideas of long-dead philosophers). Here is one reason for thinking that this cannot be a matter of generalizing from previous experience. You have never played most games of tic tac toe, for there are 26,830 possible games of tic tac toe, (counting games that result from other games by rotation or reflection only once). In other games where strategic thinking is important, the same is true. Experience simply cannot be expected to have acquainted you with the types of situations you will face. For example, there are about 10120 possible 40-move games of chess (this is called Shannon’s number, after Claude Shannon “the father of information theory”, who made the estimate). Only an infinitesimal fraction of these games will ever be played; far fewer have ever been experienced by even the best chess players.

The trick—you may realize if you attend to your thought process—is that you imagine X actually making the critical move into the center position. Then, you think about what could happen in this situation. You’ll quickly realize that no matter what move O makes on the next turn, X will be able to connect three. So, in this hypothetical situation X can win on the next turn. Hence, you realize, if X makes a move in the middle spot, then X can win on the next turn

Arguably, this type of thinking—imagining yourself in a hypothetical scenario, and reasoning about what would be true in that scenario in order to gather “conditional information” about the real world—is common in many ordinary activities as well. Some clever examples of hypothetical reasoning can also be found in fiction. For example, the chess house fight in the movie Hero, and the final confrontation between Holmes and Moriarty in Sherlock Holmes, Game of Shadows both depict something like conditional reasoning, in which the adversaries consider responses to possible moves. Interestingly, both of those two scenes reference games of strategy—Sherlock has just played a game of chess with Moriarty, and Sky is just finishing a game of go.

We can represent the abstract structure of conditional reasoning as a (simple) conditional derivation:

Conditional Derivation

A (simple) conditional derivation is a sequence of assertions

  1. Aimed at showing a conditional ϕ → ψ

  2. beginning with an assumption that ϕ is true

  3. in which every assertion other than the initial assumption is justified, either because it is a premise or because it is the conclusion of a rule of direct inference with previous lines as premises.

To use a conditional derivation to show something, 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 are assuming, and what we are actually justifying on the basis of other things. Third 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. Fourth, 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.

We’ll keep track of most of these things using the same tools that we did for direct derivations: we will write “Show” to indicate what we are showing, we will number our lines, and indicate where the premises to rules MP,MT, DNE, and DNI are coming from by using line numbers. There will only be three real differences.

First, we will aim only to show “ifthen” conditional statements. Second, we will begin each derivation by assuming the statement on the left side of the “ifthen” statement that we are aiming to show; we will write “AS” to justify our assumption. Third, we will consider ourselves finished, box the derivation and cancel (i.e. cross out) the show line when we manage to assert the statement on the right side of the conditional; we will write the number of the line where we asserted the statement on the right side, together with CD, to mean “I have shown the conditional statement by means of a conditional derivation ending with this line”. The result will look like this:

1. Show: φ->ψ
2.     φ          :AS
3.     assertion  :Justification
4.     assertion  :Justification
5.     assertion  :Justification
6.     assertion  :Justification
7.     ψ          :Justification
8. :CD 7

Here are some examples of conditional derivations.

For the argument P → Q,  Q → R ⊢ P → R, we can derive:

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

For the argument P → (¬Q → R), ¬R ⊢ P → Q, we can derive

1. Show:P -> Q
2.    P              :AS
3.    P -> (~Q -> R) :PR
4.    ~R             :PR
5.    ~Q -> R        :MP 2,3 
6.    ~~Q            :MT 4,5
7.    Q              :DNE 6
8. :CD 7

For the argument P → (Q → (R → S)),  ¬Q → ¬R,  R ⊢ P → S, we can derive

1. Show: P -> S
2.    P                    :AS
3.    P -> (Q -> (R -> S)) :PR
4.    ~Q->~R               :PR
5.    R                    :PR
6.    Q -> (R -> S)        :MP 2,3
7.    ~~R                  :DNI 5
8.    ~~Q                  :MT 4,7
9.    Q                    :DNE 8
10.   R -> S               :MP 9 6
11.   S                    :MP 10 5
12. :CD 11

Problem Set 5

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.

One small note. The symbol “⊤” that sometimes shows up here to the left of the “therefore” symbol means that there are no premises to the problem. In problems with this symbol, it should be possible to finish the conditional derivation with nothing but the assumption introduced by AS.

exercise 5.1
5.1 :|-: P->P
exercise 5.2
5.2 Q :|-: P->Q
exercise 5.3
5.3 P :|-: (P->Q) -> Q
exercise 5.4
5.4 P->Q, Q->R :|-: P->R
exercise 5.5
5.5 (P->(P->Q)) :|-: P->Q
exercise 5.6
5.6 :|-: --P -> P
exercise 5.7
5.7 (P->Q) :|-: -Q->-P
exercise 5.8
5.8 -Q->-P :|-: P->Q
exercise 5.9
5.9 Q->P :|-: --Q->P
exercise 5.10
5.10 P->-Q, R->Q :|-: P-> -R