Lecture Notes Unit 2

Contents

(In lazy mode, lowercase letters, except ‘v’, are automatically changed to uppercase.) 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:

AC
A
C

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

Now consider:

AB
BC
CD
A
D

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 AB and A, we can conclude B.
2. Now that we know B and already knew BC, we can conclude C.
3. Once we know C, since we know CD, 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.

Direct Derivation (DD)

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

A → (AB)
A
B

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.)

Our first example would look like this:

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”.

→O
AC
A
C
AC
~C
~A

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 this mode of 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:

AC
~C
~A

We have to plug things in uniformly for “A” and “C” here.

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

Similarly, if “A” 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”.

∨O
AB
~A
B
AB
~B
A

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!

Invalid “pseudo-rules”
(AKA modus morons)
DO NOT USE!
AC
C
A
AC
~A
~C
AB
A
~B
AB
B
~A

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
(PQ) ∨ R
and
~Q
either to ~P or to R!

Rules must be applied to whole lines.

Homework: Exercise Set 5B

Other Direct Derivation Rules

So far we have learned →O and ∨O.

→O
AC
A
C
AC
~C
~A
∨O
AB
~A
B
AB
~B
A

&O
A & B
A
A & B
B
&I
A
B
A & B
↔O
AB
AB
AB
BA
↔I
AB
BA
AB
∨I
A
AB
A
BA
DN
A
~~A
~~A
A

It is worth noting that ∨I, &O, ↔O and DN require only one line for justification, whereas ∨O, →O, &I, and ↔I require two.

The OUT rules are rules for using statements of a certain form (with a certain main 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!

Homework: Exercise Set 5C, Credit Exercises 2.1

Conditional Derivation (CD)

We have both In and Out rules for all our connectives, except for the arrow.

There is no →I rule!

This makes deriving the conclusion of arguments with SHOW lines that contain arrows nearly impossible.

We now introduce a new way of proving if-then statements. It is not simply a new derivation rule, but a new style of proof.

The basic idea of conditional derivation is that in order to prove that AB, i.e., that if A is true, then B is true, we can take the strategy of assuming temporarily that A is true and deriving B from that assumption.

If we can prove that B is true by assuming A, we know that if A were true, B would have to be true as well, and so, that AB.

Conditional derivation will work when (and only when) our problem contains an if-then statement in the SHOW line. Consider:

We can’t prove this only using the other rules. Instead, we write “CD” for conditional derivation, and then, at line 4, we assume that P is true. Finally, we change what we’re trying to prove.

Once we assume P, we introduce a new SHOW line, because now we’re going to try to show R on the basis of that assumption.

This gets set up like this:

(“Ass” for “assumption”.)

Now, we do a little “proof within a proof”. In other words, we try to show R, using line 4 (P) as an assumption. This uses DD rules, so we have written in “DD” for the inner SHOW line.

(Note that because line 5 is a SHOW line; we cannot use it in our derivation.) We end up drawing a little box within a box. With P as an assumption, the mini-derivation of R is quite easy.

We have now shown R in the normal way. So I have crossed off that “SHOW”.

Where are we now?

We have assumed P, and have successfully shown R on the basis of that assumption.

We are now entitled to regard ourselves as having shown PR and can cross off the “SHOW” at line 3.

That’s the way CD works.

The final problem looks like this:

One thing that is important to remember is that, once a new SHOW line is introduced, your task has changed. You should focus on proving what it says to prove at the new SHOW line, and forget for the moment about trying to get the final conclusion.

Sometimes when we introduce a new SHOW line as part of a CD, the new SHOW line will itself be an if-then statement. If so, we may do a conditional derivation within a conditional derivation.

We can use CD whenever we wish to prove a conditional (if-then) statement.

It does not need to be the final conclusion of our argument; we may do it as an intermediate step. However, we do need to have the conditional we wish to prove as a SHOW line.

We are allowed to introduce new SHOW lines whenever we wish.

Once we cross-off the “SHOW” of the newly introduced “SHOW” line we can then use it as though it were a normal line.

However, once a box has been drawn around some lines, we cannot use those lines again in our derivation. Examples:

Here, we used CD in proving the SHOW line at line 3, but the ultimate conclusion, the SHOW line at line 2, was not proven by CD, but by →O, which is DD rule, so we write “DD” at 2, and “CD” at line 3.

This basic procedure allows us to use multiple CDs, combined with ↔I, to prove biconditional (iff) statements.

We first prove the conditional one way, and then the other. Then we put them together.

Lastly, there is a special rule, called “R” for “Repetition”, that we can use if, for some reason, we need to repeat something we already know on a later line—e.g., if needed on a line within a sub-proof.

R
A
A

Example:

This rule is not needed very often.

Homework: Exercise Set 5D

Indirect Derivation (ID)

Indirect derivation, like conditional derivation, is a wholly new way of setting up a proof.

Indirect derivation is used to show that something couldn’t possibly be true, because if it were true, it would lead to something absurd or impossible. (In Latin, the indirect proof technique is called “reductio ad absurdum” (RAA), meaning “reduction to absurdity”.

To do an ID, we first assume that something is true. We then show that this assumption leads to a contradiction, i.e., it leads to something being both true and false.

We then conclude that what we assumed must not be true.

We now introduce a special symbol, “✖”, which we use to signify “the absurd” or the “impossible”.

We then allow ourselves to introduce this in a proof, whenever we get a contradiction, by means of the following rule (✖-In):

✖I
A
~A

The basic structure of an indirect proof is to assume the opposite of what we’re trying to prove, and derive a contradiction. I.e., to show ~A, we assume A, and show ✖.

Consider the following example. We write “ID” for the show-rule. We then assume A and add a new SHOW line to show the absurd (✖).

We’ll get ✖ by DD. We can do this by showing any contradiction. (Any contradiction will do. It need not be the opposite of what we assumed.)

Once we get ✖ on a line by ✖I, we can cross off the inner SHOW line.

Having shown that a contradiction results when we assume A is true, we can safely conclude that A is false, by ID.

Here is the final problem.

Indirect derivation is very powerful. It can be used for almost any type of problem, and even when what we’re trying to prove is complex.

(There are quite often multiple ways of doing these problems. E.g., on this last one, at line 11, we could have used 7 and 10 to get Q instead of 3 and 10 to get ~P. This would also have given us a different contradiction (lines 3 and 11). Either way you do it is fine.)

Homework: Exercise Set 5E

There are, strictly speaking, two forms of indirect proof. The previous examples assume that something is true in order to prove that it is false.

We can also assume that something is false in order to prove that it is true.

This form works almost exactly the same.

We can do indirect derivations within conditional derivations (or, more rarely, vice-versa).

(Remember we can introduce SHOW lines whenever we wish.)

Often, it is helpful to do two indirect derivations in order to prove that a conjunction (and-statment) is true.

✖I has a companion Out rule, which amounts to the result that anything follows from a contradiction.

✖O

A

However, we never need use this rule.

Homework: Exercise Set 5F, Credit Exercises 2.2

Negation Rules

Just using the rules we have already learned, we can demonstrate the validity of any valid argument in sentential logic.

However, if we stick only to what we have so far, some problems require making moves that are rather strange and awkward.

Consider the following problem:

There is no obvious way to do this problem.

The conclusion is not a conditional statement, so it seems to make little sense to do CD.

We could try an ID.

If we assume ~(PR) and try to get a contradiction, however, we get stuck immediately.

It is possible to do this problem with our rules so far, but it requires some very unusual and creative moves:

To make our lives easier, we introduce some special rules dealing with negations of complex statements.

~&O
~(A & B)
A → ~B
~∨O
~(AB)
~A
~(AB)
~B
~↔O
~(AB)
~AB
~→O
~(AC)
A & ~C

With these rules, the above proof simplifies to:

Some other derivations that use these rules.

Strategies and Rules of Thumb

When you begin a derivation, you might be unsure of the best way to go about it. Should you do a CD, ID or just try it by DD? Would you need to do some combination of these? When should you do one technique within another?

The simplest rule is: when in doubt, try an indirect derivation.

This is because all problems can be done with ID. Some problems are shorter if you don’t use ID, but if you can’t see that far ahead, it almost never hurts to try one.

To make things more specific, when it doubt, I recommend constructing a derivation using the following strategies, depending on what kind of statement in your SHOW line:

SHOW lineFormTryAssumeNew SHOW
AtomicPID~P
Negation~AIDA
DisjunctionABID~(AB)
ConditionalABCDAB
SplatDD(none)(none)

For “and” and “iff” statements, break the problem into two parts, and put them together at the end with &I or ↔I.

SHOW lineFormTryAssumeNew SHOW
BiconditionalSHOW: ABDD
first:SHOW: ABCDAB
then:SHOW: BACDBA
ConjunctionSHOW: A & BDD
first:SHOW: A ID~A
then:SHOW: B ID~B

This should tell you how to set up any problem:

• Look at your SHOW line, figure out which kind of derivation works best and then make your assumption and write your new SHOW line.
• Look at your new SHOW line and repeat the procedure until you get SHOW ✖.
• Now, use the DD rules to get a contradiction.

This will work for almost all problems. Examples:

Remember you can use a SHOW line after SHOW has been crossed out.

What to Do when Stuck: “Desperate Measures”

Following the guidelines suggested above will get you through just about any problem. But there is a certain kind of problem where you still might get stuck in the middle, and you’ll have to try something desperate to get out of being stuck.

Here is an example of that kind of problem.

If you follow the guidelines, you’ll begin by starting an ID. A few steps can be done after that.

But, uh oh, now what? There doesn’t seem to be anywhere to go from here.

When you get stuck like this, you need to ask yourself: What would be helpful? What resources do you have that you would like to make use of, but can’t?

Usually this will lead you to one or more lines that are just begging to be used. In this case, it’s line 1, which hasn’t been used so far.

Line 1 is an ∨-statement, which means, if we were going to make use of it, we’d have to make use of the ∨O rule.

To make use of the ∨O rule, we’d have to have that one of the two sides of the or-statement is false. Let’s try to prove just that!

That is, let’s try to prove ~(PR).

Let’s go ahead and write that in as a new SHOW line. Then we can do it by ID.

Lo and behold, it works! Once we have it, we can finish the rest of the derivation.

Basically, when you get stuck, look for a way you can set up either doing a ∨O step (like we did here at line 15), or a →O, by proving either the negation of half of an ∨-statement, or by proving the if-part of a →-statement, or the negation of a then-part of a →-statement.

Introduce a new SHOW line if necessary, so you can do an ID or CD for the thing that you need to set up the desired move.

Here are some more examples of such “desperate measures” strategies.

These strategies together with the rules of thumb considered earlier, and you can any problem you come across!

Review Problems

Here’s a short, interesting problem that involves proving a conclusion without using any premises!

Homework: Unit 2 Practice Exam

That’s all there is to Unit 2. Time to dance.