Introduction to Logic

In the last section, we wrote out all our tautologies in what we called "argument form." For instance, Modus Ponens [(pq)p]q was represented as

pq

p

q

We think of the statements above the line, the premises, as statements given to us as true, and the statement below the line, the conclusion, as a statement that must then also be true.

Our convention has been that small letters like p stand for atomic statements. But, there is no reason to restrict Modus Ponens to such statements. For example, we would like to be able to make the following argument:

If roses are red and violets are blue, then sugar is sweet and so are you.

Roses are red and violets are blue.

Therefore, sugar is sweet and so are you.

In symbols, this is

(pq)(rs)

pq

rs

So, we really should write Modus Ponens in the following more general and hence usable form:

AB

A

B

where, as our convention has it, A and B can be any statements, atomic or compound.

In this form, Modus Ponens is our first rule of inference. We shall use rules of inference to assemble lists of true statements, called proofs. A proof is a way of showing how a conclusion follows from a collection of premises. Modus Ponens, in particular, allows us to say that, if AB and A both appear as statements in a proof, then we are justified in adding B as another statement in the proof. (We shall say more about proofs in Section 6.)

Example 1 Applying Modus Ponens

Apply Modus Ponens to statements 1 and 3 in the following list of premises (that is, statements that we take to be true).

1. (pq)(r~s)

2. ~rs

3. pq

Solution

Notice that all the statements are compound statements, and that they have the following patterns:

1. AB

2. C

3. A.

Statement A appears twice; in lines (1) and (3). Looking at Modus Ponens, we see that we can deduce B = r~s from these lines. (Line (2) is not going to be used at all; it just goes along for the ride.) Thus, we can enlarge our list as follows:

1. (pq)(r~s)	Premise
2. ~rs	Premise
3. pq	Premise
4. r(~s)	1,3 Modus Ponens

On the right we have given the justification for each line: lines (1) through (3) were given as premises, and line (4) follows by an application of Modus Ponens to lines (1) and (3); hence the justification "1,3 Modus Ponens."

Before we go on...

The above list of four statements consitutes a proof that Statement 4 follows from premises 1-3, and we refer to it as a proof of the argument

(pq)(r~s)	Premise
~rs	Premise
pq	Premise
r(~s)	Conclusion

Example 1P Practice with Applying Modus Ponens

Fill in the missing statement. To enter the statement, use "AND" for , "OR" for , and "IMPLIES" for . For instance, you could enter (pq) (~r)     as     (p AND q) IMPLIES ~r

 

1. (rs)t	Premise
2. (rs)(qr)	Premise
3. r~s	Premise
4. rs	Premise
5.	2, 4 Modus Ponens

In general, a rule of inference is just an instruction for obtaining additional true statements from a list of true statements. If you were studying logic as a mathematics or philosophy major, this might be the only rule of inference you would be given to work with. You would then have to justify the use of the other rules of inference from these. We are not going to be quite so demanding. We'll give you lots of rules of inference to work with from the beginning. Think of them as tools for constructing new statements from old ones; the more tools you have at your disposal, the easier your task becomes. In fact, we are going to allow you to use any of the tautologies listed at the end of Section 4 as rules of inference. (That is why we listed the "argument form" for all of them.)

Example 2 Using T1

Apply Modus Tollens to the following premises:

1. (pq)(r~s)

2. ~(r~s)

3. (pq)p

Solution

Looking at the given premises, we see the pattern:

1. AB

2. ~B

3. AC

As a rule of inference, Modus Tollens has the following form:

AB

~B



~A

(In words, if AB appears on the list, and if ~B also appears on the list, we can add ~A to the list of true statements.)

This matches the first two premises, so we can apply Modus Tollens to get the following.

1. (pq)(r~s)	Premise
2. ~(r~s)	Premise
3. (pq)p	Premise
4. ~(pq)	1,2 Modus Tollens

Before We Go On ...

We used AC to represent the statement (pq)p, although we could just as well have represented it by D. Since we're not using this statement at all, it doesn't matter how we represent it. On the other hand, in order to be able to use Modus Tollens on lines (1) and (2), it was imperative that we represented line (1) by AB, and not by the single letter A. If you look at the argument form of Modus Tollens, you will see that it requires a statement of the form AB (as well as ~B, of course). Part of learning to apply the rules of inference is learning how to analyze the structure of statements at the right level of detail.

Example 2P Practice with T1

We shall extend the list in Example 2 by first applying De Morgan's Law to line (4), and then applying Simplification, to obtain ~p. You must fill in the missing statement. . To enter the statement, use "AND" for , "OR" for ., and "IMPLIES" for . For instance, you could enter (pq) (~r)     as     (p AND q) IMPLIES ~r

1. (pq)(r~s)	Premise
2. ~(r~s)	Premise
3. (pq)p	Premise
4. ~(pq)	1,2 Modus Tollens
5.	4 De Morgan
6. ~p	5 Simplification

Before we go on...

Note that we have just proved the argument

(pq)(r~s)

~(r~s)

(pq)p

~p

We shall say more about proofs in Section 6.

So far, all the rules of inference that we have been permitted to use come from our list of tautologies. These are not the only kinds of rules of inference we shall allow. Here are two more kinds:

Example 3 Using T2

Justify each step in the following.

1. p~(~p)

2. ~(~p)p

3. pp

Solution

Each of the first two steps is an application of rule of inference T2. Recall that p~(~p) is a tautology, called Double Negation. We permit ourselves to break a tautological equivalence into its two tautological implications and write down either one. In this case, we wrote down both. The third step is an application of rule of inference T1, using Transitivity. Thus, we can write our justifications like this:

1. p~(~p)	Double Negative
2. ~(~p)p	Double Negative
3. pp	1,2 Transitivity

Before we go on...

What we have just written down is a proof of the following argument, in which there are no premises:

-

pp

Note that we are permitting ourselves to break up a tautological implication of the form AB into two statements: AB and BA. In other words, each tautological equivalence is really giving us two tautological implications for the price of one. That is why we listed two argument forms for most of the equivalences.

Example 3P Practice with T2

Select the correct answers in the following argument.

1. q	Premise
2. p(p~q)	Addition	T1 T2
3.~p(p~q)	Switcheroo	T1 T2
4.(~pp) ~q	Associativity	T1 T2
5.~pp	Disjunctive Syllogism	T1 T2

Rules T1 and T2 are the two we shall use most often. The next two are used less often, but are sometimes necessary.

For instance, we can replace the statement p[~(qr)] with p[(~q)(~r)] by using De Morgan's law, since ~(qr)(~q)(~r).

As with T2, we rely on our list at the end of the preceding section to decide what statements are tautologically equivalent. Notice that this is the same as the mathematical rule of substitution: in any equation, if part of an expression is equal to something else, then we can replace it by that something else.

Example 4 Using Substitution

Justify the third and fourth steps in the following proof.

1. ~(~p)q	Premise
2. p	Premise
3. pq
4. q

Solution

The third line resembles the first except that ~(~p) has been replaced by p. But, that replacement can be justified by the substitution rule because the Double Negation tautology tells us that p is tautologically equivalent to ~(~p). To get the fourth line we simply apply Modus Ponens to the second and third lines. Thus, we can fill in the following justifications.

1. ~(~p)q	Premise
2. p	Premise
3. pq	1, Substitution
4. q	2, 3 Modus Ponens

This is just the obvious fact that, if we already know A and B to be true, then we know that AB is true.

Q Are we done yet?
A Not quite. What we are doing is giving rules for what lines can be written in the proof of a given argument. We have already been using one rule without saying so, and we should write it down:

Of course, this does not entitle us to make up premises as we go along; we will always be told what the premises are before we start, and Rule P applies only to those. It is traditional, but not necessary, to write down all of the premises as the first lines of a proof. On the other hand, some people like to write them down only as they are needed.

To summarize, Here are all the rules of inference we shall be using.

In the following rather tricky proof, we start with two premises, and shall manage to use every single rule of inference except for T2:

Example 5 Using the Rules of Inference

Below is a proof of the argument This proves shows the validity of the following argument:

aq

bq

(ab)q

In words, if a and b each imply q, then either a or b implies q. Although this seems intuitively obvious, its proof is not!

Here is the proof. Supply the missing justifications.

1. aq	Premise
2. bq	Premise
3. ~aq
4. ~bq
5. (~aq)(~bq)
6. (~a~b)q
7. ~(ab)q
8. (ab)q

Solution

Here are the justifications, with the type of rule of inference noted after each:

1. aq	Premise (P)
2. bq	Premise (P)
3. ~aq	1, Switcheroo (T1)
4. ~bq	2, Switcheroo (T1)
5. (~aq)(~bq)	3,4 Conjunction (C)
6. (~a~b)q	5, Distributive Law   (T1)
7. ~(ab)q	6, De Morgan (S)
8. (ab)q	7, Switcheroo (T1)