Introduction to Logic

We have already had a taste of proofs in Section 5. In this section, we make more precise what we were doing there, and get some practice in coming up with proofs.

In Example 5 in the preceding section we saw the following argument.

aq

bq

(ab)q

Precisely, an argument is a list of statements called premises followed by a statement called the conclusion. (We allow the list of premises to be empty, as in Example 3 in the preceding section.) We say that an argument is valid if the conjunction of its premises implies its conclusion. In other words, validity means that if all the premises are true, then so is the conclusion. Validity of an argument does not guarantee the truth of its premises, so does not guarantee the truth of its conclusion. It only guarantees that the conclusion will be true if the premises are.

Question

To show the validity of an argument like

aq

bq

(ab)q

what we need to do is check that the statement [(aq) (bq)][(ab)q] is a tautology. So to show that an argument is valid we need to construct a truth table, right?

Answer

Well, that would work, but there are a couple of problems. First, the truth table can get quite large. The truth table for [(aq) (bq)][(ab)q] has eight rows and nine columns. It gets worse quickly, since each extra variable doubles the number of rows.

Second, checking the validity of an argument mechanically by constructing a truth table is almost completely unenlightening; it gives you no good idea why an argument is valid. We'll concentrate on an alternative way of showing that an argument is valid, called a proof, that is far more interesting and tells you much more about what is going on in the argument.

Lastly, while truth tables suffice to check the validity of statements in the propositional calculus, they do not work for the predicate calculus we will begin to discuss in the following section. Hence, they do not work for real mathematical arguments. One of our ulterior motives is to show you what mathematicians really do: They create proofs.

Question

OK, so what is a proof?

Answer

Informally, a proof is a way of convincing you that the conclusion follows from the premises, or that the conclusion must be true if the premises are. Formally, a proof is a list of statements, usually beginning with the premises, in which each statement that is not a premise must be true if the statements preceding it are true. In particular, the truth of the last statement, the conclusion, must follow from the truth of the first statements, the premises. How do we know that each statement follows from the preceding ones? We cite a rule of inference that guarantees that it is so.

Question

I'm convinced that proofs may be a good thing, but I'm still a little skeptical. What does a proof actually have to do with the validity of an argument?

Answere

On the one hand, a proof establishes the validity of an argument. The reason is that, in a proof, every line must be true if the preceding lines are true. In particular, the truth of the first lines, the premises, implies the truth of the last line, the conclusion. Hence a proof does show that an argument is valid. Much less obvious, but reassuring, is the fact that every valid argument in propositional calculus has a proof.  In other words, an argument is valid if and only if there is a proof of it.

The only way to learn to find proofs is by looking at lots of examples and doing lots of practice. In the following examples we'll try to give you some tips as we go along.

Example 1 Modus Ponens

Prove the valid argument

(pq)(rs)
pq
rs

Solution

First check to see whether there are any rules of inference that will give you the conclusion in one step. If we look at the argument as having the form:

AB
A
B

we see that this is nothing more than Modus Ponens. Thus we get the following one-step proof:

1. (pq)(rs)	Premise
2. pq	Premise
3. rs	1,2 Modus Ponens

Before we go on...

Here is a case in which a proof is much shorter than a truth table. Since there are four variables, the truth table would have 16 rows. Also, the proof shows you that the argument is just an elaborate version of Modus Ponens.

Modus Ponens and Modus Tollens are, perhaps, the most commonly used rules of inference. You should get used to looking for places you can apply them.

Example 2 Modus Tollens

Prove the following valid argument.

pq

r(~p)

~r

Solution

Looking at the second premise and the conclusion, it looks like we should use Modus Tollens. However, to do that we would need to know that p is true, since Modus Tollens tells us that p and r(~p) together give us ~r. How do we get p by itself? Since we are given pq, we can use Simplification. Thus, we get the following proof.

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

Before we go on...

Notice that, when thinking about how to do the proof, we worked backwards from what we wanted. This is an enormously useful technique. Sometimes you need to work forward from what you are given and also backwards from what you want, until the two meet in the middle.

Example 2P Practice with Modus Ponens and Modus Tollens

Try to come up with a strategy to complete the proof below without looking at the options in the invidual steps. Then select the correct steps and justifications. (They might not correspond exactly to the proof you have in mind, but having a strategy will help you make the correct choices.)

1. ~(rs)		Premise
2. (~p)(rs)		Premise
3. Select one (~r) OR (~s) (~r) AND (~s) p ~p s		Select one 1, De Morgan 1, Simplification 1, 2 Modus Ponens 1, 2 Modus Tollens 2, Addition
4. pq		Select one 2, 3 Modus Ponens 2, 3 Modus Tollens 3, Addition 3, Simplification 1, 3 Rule C

Rule C plays an important role in the next proof.

Example 3 Rule C Invoked

Prove following valid argument.

pa

pb

p

ab

Solution

We can get both a and b individually using Modus Ponens. To get their conjunction, all we need do is invoke Rule C.

1. pa	Premise
2. pb	Premise
3. p	Premise
4. a	1, 3 Modus Ponens
5. b	2, 3 Modus Ponens
6. ab	4, 5 Rule C

Example 4 Strategy

Prove the valid argument

p(qr)

p

~r

q

Solution

Let us think of a strategy for finding a proof. We first examine what we need.

(1) We need q. The only place q occurs is in the first line as part of the consequent. We can get qr using the first two lines and Modus Ponens.

(2) Now we know we can get qr. To get q alone, we will need to exclude r. This is made possible by the premise ~r, and Disjunctive Syllogism.

Thus we get the following proof:

1. p(qr)	Premise
2. p	Premise
3. ~r	Premise
4. qr	1, 2 Modus Ponens
5. q	3, 4 Disjunctive Syllogism

Before we go on...

Again, notice the back-and-forth thought process: We started to work backwards from q; working forwards we saw that we could easily get qr . Working backwards from q again, we noticed that Disjunctive Syllogism would make the ends meet.

Example 5 More Strategy

Prove the valid argument

(pr)(st)

p

t

Solution

Here is a strategy.

(1) We need t. This occurs in the consequent of the first premise. We could get this by Modus Ponens if we knew that pr were true.

(2) All we know is that p is true from the second premise. But the Addition rule will give us pr.

(3) Combining (1) and (2) will give us the consequent, st. To get t on its own, we can then use simplification:

1. (pr)(st)	Premise
2. p	Premise
3. pr	2, Addition
4. st	1, 3 Modus Ponens
5. t	4, Simplification

Example 5P Practice with Strategy

Try to come up with a strategy to complete the proof below without looking at the options in the invidual steps. (Hint: try working backwards from q.) Then select the correct steps and justifications. (They might not correspond exactly to the proof you have in mind, but having a strategy will help you make the correct choices.)

1. ~(rs)		Premise
2. (~p)s		Premise
3. pq		Premise
4. Select one (~r) OR (~s) (~r) AND (~s) r AND s p IMPLIES s (~s) OR p		Select one 1, De Morgan 1, Simplification 2, 3 Transitivity 1, 2 Modus Tollens 2, Switcheroo
5. Select one r s ~r ~s p IMPLIES s		Select one 2, De Morgan 1, Simplification 2, 3 Rule C 2, 4 Modus Ponens 4, Simplification
6. Select one p ~p ~r s p AND ~p		Select one 2, 5 Modus Tollens 1, Simplification 2, 5 Modus Ponens 3, 5 Modus Ponens 4, Simplification
7. q		Select one 2, 5 Modus Tollens 4, Simplification 2, 6 Modus Ponens 3, 6 Modus Ponens 5, 6 Rule C

Example 6 Working Backwards

Prove the valid argument

a(bc)

~b

~a

Solution

(1) We need ~a, which occurs as the negation of the antecedent in the first premise. We could get this by using Modus Tollens, provided we knew that the conclusion, bc, is false.

(2) Thus, we have a new goal: Show ~(bc). This is the same as ~b~c by De Morgan.

(3) Now we recognize that we can use Addition to get ~b~c. from ~p.

We can now get the proof by going through this sequence of steps backwards:

1. a(bc)	Premise
2. ~b	Premise
3. ~b~c	2, Addition
4. ~(bc)	3, De Morgan
5. ~a	1, 4 Modus Tollens

Before we go on...

This time we worked almost entirely backwards. However, we must write the proof forwards. This is a common complaint when students first start to do proofs in symbolic logic or in mathematics. The proof does not follow the train of thought that went into finding it. Often, the thought process is exactly the reverse of what the proof suggests.

Another point to keep in mind is that there are often many different proofs of a given valid argument. Here is another proof of the argument above:

1. a(bc)	Premise
2. ~b	Premise
3. ~(bc)(~a)	1, Contrapositive
4. ~b~c	2, Addition
5. ~(bc)	4, De Morgan
6. ~a	3,5 Modus Ponens

Constructing a proof is a little like playing a game of chess. You need to pick the right moves, out of all that are possible, to get you to your goal.

Example 7 Working Forwards

Prove the following valid argument.

sr

(pq)~r

(~s)(~qr)

p

q

Solution

(1) We need q, which occurs in both the second and the third premises. It is not at all clear at this point which one to focus on, so let's go back to the beginning and see what we can get.

(2) The simplest statement is the last, which says that p is true.

(3) The second premise now says, after we use Addition to get pq, that ~r is true.

(4) The first premise now says, by Modus Tollens, that ~s is true.

(5) This fits neatly into the third premise, which says that (~qr) is true.

(6) But we already know from (3) that ~r is true. Therefore, by modus Tollens, ~(~q) ≡ q is true!

Going through these steps gives the following proof:

1. sr	Premise
2. (pq)~r	Premise
3. ~s(~qr)	Premise
4. p	Premise
5. pq	4, Addition
6. ~r	4, 2 Modus Ponens
7. ~s	1, 6 Modus Tollens
8. ~qr	3, 7 Modus Ponens
9. q	6, 8 Modus Tollens

As the preceding example shows, not all proofs are easy to find. Sometimes you have to fiddle a bit to get one. If the line of argument you're trying doesn't pan out, experiment with something else. Here are some things to try that often help:

Example 7P Practice with Arguments

It is possible to come up with two different proofs by making the correct choices. See if you can find both of them.

1. (pq)(rs)		Premise
2. ~r		Premise
3. Select one (~r) OR (~s) (~r) AND (~s) p IMPLIES (r AND s) p IMPLIES r p IMPLIES (p OR q)		Select one 1, De Morgan 1, Simplification Addition 1, Switcheroo 2, Addition
4. Select one (r AND s) IMPLIES r r AND s ~(r AND s) ~s q IMPLIES s		Select one 3, De Morgan Simplification 2, 3 Rule C 1, 2 Modus Tollens 3, Simplification
5. Select one p ~(p OR q) ~r p IMPLIES (r AND s) p AND ~p		Select one 1, 3 Transitivity 1, Simplification 1, 2 Buckle my Shoe 3, 4 Knock at the Door 1, 4, Modus Tollens
6. Select one p IMPLIES r ~(p OR q) ~r p IMPLIES (r AND s) (~p) AND (~q)		Select one 4, 5 Transitivity 5, De Morgan 1, 2 Buckle my Shoe 3, 4 Knock at the Door 1, 4, Modus Tollens
7. ~p		Select one 2, 6 Modus Tollens 4, Simplification 2, 6 Modus Ponens 3, 6 Transitivity 6, Simplification

The next argument basically asserts that if we permit a single contradiction in an argument, then anything is possible. (A proof appeared in the exercise set at the end of the last section, but it is interesting enough to warrant further inspection.)

Example 8 Slippery Argument

Prove and comment on the argument

p(~p)

q

Solution

Notice that the premise p(~p) is a contradiction. If you write out the truth table for [p(~p)]q, you can see why this is a valid argument. But let us try to come up with a proof.

(1) The easiest way to begin is to use simplification to "break up" the statement p(~p) into the two separate statements p and ~p.

(2) Notice that q does not occur anywhere among the premises. One way we can get it out of thin air is to use Addition, so let's try adding it to p to get pq.

(3) Now the statement ~p that we got from (1) tells us that p is false, so that this, combined with pq, gives us q, by Disjunctive Syllogism.

1. p(~p)	Premise
2. p	1, Simplification
3. ~p	1, Simplification
4. pq	2, Addition
5. q	3, 4 Disjunctive Syllogism

Before we go on...

Notice that this proof is one step shorter than the one you saw in the exercises. This illustrates again the fact that there may be several different proofs of the same argument. The simplest proof (which usually means the shortest one) is considered the most elegant.

We were also asked to comment on the argument. Look at the premise: it is making the contradictory claim that both p and ~p are true. What the argument now says is that, once you allow a contradiction into an argument, anything is true. Notice that the conclusion, q, has nothing to do with the premise.

This is related to the fact that a false antecedent implies any consequent, true or not. Here is an example: "If 0 = 1, then I am the King of England" is a true statement no matter who says it. To write this as an argument, let us take p to be the statement "0 = 1" and q to be the statement "I am the King of England." Then our statement is equivalent to the argument

p

q

But that's not all! As mathematicians, we happen to know that the statement p is false, so that ~p is a true statement. Thus we are really arguing that:

p

~p

q

By Rule C, this is really the same as:

p(~p)

q

which we know is valid. 

Example 9 An Invalid Argument

Show that the argument

pq

q

p

is not valid.

Solution

Proofs can only be used to show that an argument is valid. If you try to prove this argument, you'll get nowhere. It looks sort of like Modus Ponens, except that it's backwards. It looks sort of like Modus Tollens, but the negations are missing. It just looks wrong, and it is.

To show that an argument is invalid we need to find a counterexample. This is an assignment of truth values to the variables that makes the premises true but the conclusion false, thus showing that the conclusion does not follow from the premises.

In this case, for the conclusion to be false we need p to be F. For the premises to be true we certainly need q to be T. All we need to do is check that both premises are then true: The first premise is pq, which is true when p is F and q is T. This is our counterexample.

A counterexample is more vivid if we illustrate it with concrete statements. For p, which must be F, let us take the statement "0 = 1." For q, which must be T, let us take the statement "The earth is round." Our argument then has the following, patently ridiculous, form:

If 0 = 1, then the earth is round.	- True
The earth is round.	- True
0 = 1	- False

Before we go on...

This argument is a common fallacy known as the fallacy of affirming the consequent, or the fallacy of the converse, since it seems to come from a confusion of pq with its converse qp. (If the first premise were qp, then the argument would be an example of the valid Modus Ponens.) Here is an illustration, adapted from Logic: An Invalid Approach by David Marans, of this invalid argument used to conlcude something that happens to be true:

If Miami is in Florida, it is in the USA.

But Miami is in the USA.

Miami is in Florida.

Although the conclusion is true, the argument remains invalid (basically because we can use the same agument to deduce false conclusions from true premises as we saw in the counterexample).

For an informative and enjoyable discussion of invalid arguments of many different types, please visit David Marans' logic page. In fact, this link is a must for those who might feel uncomfortable with the notion that the conclusion in a logically invalid argument can be true (and that the conclusion in a logically valid argument can be false).

Example 10 Valid or Invalid?

Decide whether the following arguments are valid. If an argument is valid, then give a proof; if it is not, then give a counterexample.
(a) Every irreversible chemical reaction dissipates heat. Therefore, if a chemical reaction is reversible, it dissipates no heat.
(b) The moon is made of blue cheese. If the moon is made of blue cheese, it must be gorgonzola. Therefore, the moon is made of gorgonzola.

Solution

To analyze any argument given in words we first translate it into symbolic form.

(a) The first sentence discusses two aspects of a chemical reaction, whether it is irreversible and whether is dissipates heat. Let p: "this chemical reaction is irreversible" and q: "this chemical reaction dissipates heat." Then the first statement is pq. The conclusion is the implication (~p)(~q). Therefore, the argument is, in symbolic form, the following.

pq

(~p)(~q)

This argument may remind us of the Contrapositive rule. However, the conclusion is backwards, since the contrapositive of pq is (~q)'(~p). This suggests that the argument is invalid, so let us try to find a counterexample.

Our counterexample should make the premise true but the conclusion false. The only way to make an implication false is for the antecedent to be true and the consequent false, so we must have ~p true and ~q false. In other words, p should be false and q true. Fortunately, this makes the premise true, so we have found our counterexample. In terms of the meanings we assigned to p and q, a counterexample would be given by a chemical reaction that was reversible but dissipated heat.

If we want to express the counterexample in a more immediately understandable way, we could let p: "this creature is a horse" and q: "this creature is a mammal." A counterexample would then be given by any creature who was not a horse but was a mammal, say a dog. Alterrnatively, let us choose p = "0 = 1," and q = "the moon is round." Then the argument becomes:

If 0 = 1, then the moon is round.	- True
If 01, then the moon is not round.	- False

(b) Let us take p: "The moon is made of blue cheese." q: "The moon is made of gorgonzola." Then the argument takes the following form.

p

pq

q

We see that this is just an application of modus ponens, so the argument is valid (even though the conclusion is false!)

Before we go on...

In (a), the conclusion of the original argument is in fact true: Reversible chemical reactions dissipate no heat. However, the argument used to arrive at this conclusion was invalid.   In part (b), a premise and the conclusion are false (one of the premises happens to be true. Do you see which one?) and yet the argument used to arrive at the false conclusion is valid. This points up the difference between truth and validity. The validity of an argument depends solely on its form. Validity assures you that if the premises happen to be true for some interpretation of the variables then the conclusion will also be true. Validity tells you nothing about whether the premises are true, nor does it tell you what happens when a premise is false. Likewise, if an argument is invalid it does not necessarily mean that the conclusion is false, just that its truth does not follow from the truth of the premises.

Example 10P Practice with Counterexamples

The following argument is invalid.
If the moon is made of green cheese, then pigs can fly or circles are round. Pigs cannot fly. Therefore the moon is not made of green cheese.

Here is the symbolic form of the argument.

p(qr)

~q

~p

Now choose alternate statements represented by p, q, and r to demonstrate that the argument is false. (There may be more than one set of correct choices.) I need a hint.

p:	Select one All cows are kangaroos. Some cows are kangaroos. No cows are kangaroos. Mars is the fifth planet from the sun. Mars is the sixth planet from the sun.
q:	Select one Humans have brains. Pigs can fly. Planes can fly. We live in Andromeda. We live in the Milky Way.
r:	Select one There are 4 days in a week. Pigs cannot fly. Planes cannot fly. Squares are round. Circles are square.

The following example is reminiscent of the kind of question that often appears in aptitude tests (such as the LSAT).

Example 11 Logical Reasoning

Decide whether the following argument is valid. If it is, then give a proof; if it is not, then give a counterexample.

When Alexis attends math class, her sorority sisters Guppy and Desmorelda also attend. Since Desmorelda is in love with Luke, Luke's attendance at class is a sufficient condition for her to attend as well. On the other hand, for Desmorelda to attend class it is necessary that Alexis also be there (as she needs someone to talk to during the boring portions of the class). Therefore, Luke won't attend class unless Guppy also attends.

Solution

The only way to make head or tail out of all this is to translate it into symbols. To make life easy, let us choose the first letter of a person's name to symbolize their attendance at math class. Thus, for instance, a: "Alexis attends math class." We can now translate the argument as follows:

a(gd)

ld

da

lg

If we look at this argument, we can see the following string of implications:

lda(gd),

so it looks as though l does imply g; in other words, the argument is valid. Further, this string of implications is telling us that most of the proof is based on the Transitive rule:

1. a(gd)	Premise
2. ld	Premise
3. da	Premise
4. la	2,3 Transitivity
5. l(gd)	1,4 Transitivity

Now, we want to get lg by itself, and we are tempted to try the Simplification rule, but that only works if we have gd by itself. The only way around this little annoyance is to use some Switcheroo on it:

6. ~l(gd)	5, Switcheroo
7. (~lg)(~ld)	6, Distributive Law
8. (~lg)	7, Simplification!	(Wasn't that clever?)
9. lg	8, Switcheroo