![]() | 5. Rules of Inference | ![]() | Section 6 Exercises | ![]() | Main Logic Page | ![]() | "Real World" Page |
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. To begin with, let us take another look at one of the proofs we went through in Section 5.
In Example 6 of the previous section, we proved the argument:
a![]() |
Premise |
b![]() |
Premise |
![]() |
|
![]() ![]() ![]() |
Conclusion |
Precisely, an argument is a list of premises followed by a conclusion. (We allow the possibility of an empty list of premises, that is, no premises at all, as in Example 5 of Section 5.) The argument
P1 | Premise |
P2 | Premise |
P3 | Premise |
. . . . . | . . . . . |
Pr | Premise |
![]() |
|
![]() |
Conclusion |
is valid if the statement (P1P2
. . .
Pr)
C is a tautology. In other words, validity means that if all the premises are true, then the conclusion must be true. Notice, however, that validity does not guarantee the truth of the premises; a valid argument can easily have false premises.
Now in Example 6 of the previous section we also gave the following proof:
Statement | Reason |
1. a![]() |
Premise |
2. b![]() |
Premise |
3. ~a![]() |
1, Switcheroo |
4. ~b![]() |
2, Switcheroo |
5. (~a![]() ![]() ![]() |
3,4 Rule C |
6. (~a![]() ![]() |
5, Distributive Law |
7. ~(a![]() ![]() |
6, De Morgan |
8. (a![]() ![]() |
7, Switcheroo |
In general, a proof of an argument is a list of statements, each of which is obtained (using statements earlier in the list) by using one of the rules of inference T1, T2, S, C or P, with the last statement of the list being the conclusion of the argument.
According to the definition, all we need to check to see whether the argument
a![]() |
b![]() |
![]() |
![]() ![]() ![]() |
is valid is whether [(aq)
(b
q)]
[(a
b)
q] is a tautology, and this we can check by looking at its truth table. Who needs a proof?
Answer
Quite correct. The approach using a truth table does have the advantage that it's mechanical (so that one could write a computer program to do it, for instance). There are however, several disadvantages:
1. Truth tables can get awfully large. For instance, the truth table for [(aq)
(b
q)]
[(a
b)
q] involves eight rows and nine columns. It gets worse quickly, since each extra variable doubles the number of rows. For example, the truth table for
p![]() |
q![]() |
r![]() |
s![]() |
![]() |
![]() ![]() |
would require 32 rows. The proof, on the other hand, is easy and requires only three lines in addition to the premises.
2. Checking the validity of an argument mechanically is almost completely unenlightening; it tells you nothing about what is going on in the argument. Thus, from the purely intellectual point of view, a proof is far more interesting than a (possibly huge) truth table. By the end of this chapter, you should be able to look at an argument in words or symbols and decide, using your understanding of the rules of inference, whether or not it is valid. Thinking in terms of truth tables is no help towards this goal.
2.While truth tables suffice to check the validity of statements in the propositional calculus, they do not work for the predicate calculus, and hence they do not work for real mathematical arguments. One of our ulterior motives is to show you what mathematicians actually do: they create proofs.
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?
Answer
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 how to find proofs is by practice. This is best accomplished by doing lots of examples. We'll try to give some tips as we go along.
Prove the valid argument
(p![]() ![]() ![]() |
|
p![]() |
|
![]() |
|
![]() ![]() |
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:
A![]() |
|
A | |
![]() |
|
![]() |
we see that this is nothing more than Modus Ponens. Thus we get the following one-step proof:
1. (p![]() ![]() ![]() |
Premise |
2. p![]() |
Premise |
3.r![]() |
1,2 Modus Ponens |
Prove the valid argument
~(r![]() |
(p![]() ![]() ![]() |
![]() |
![]() ![]() |
Solution
Looking at the following symbolic form:
~B |
A![]() |
![]() |
![]() |
we see that this is Modus Tollens. (Do not be put off by the fact that the premises appear to be out of order. The order of the premises is irrelevant.) Thus we get the following one-step proof:
1. ~(r![]() |
Premise |
2. (p![]() ![]() ![]() |
Premise |
3. ~(p![]() |
1,2 Modus Tollens |
Prove the valid argument
p![]() |
p![]() |
![]() |
![]() |
Solution
Checking to see whether there are any rules of inference that will give the conclusion in one step, we are tempted to just quote Modus Ponens again, but it is not quite in the right form. To be able to use this rule, we would need p alone in addition to pr. So how do we get p by itself? Since we are given p
q, we can use Simplification to get p by itself, and then apply Modus Ponens:
1. (p![]() |
Premise |
2. p![]() |
Premise |
3. p | 1,Simplification |
4. r | 2,3 Modus Ponens |
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 have to work from both ends, until they meet somewhere in the middle.
Prove the valid argument
p![]() ![]() |
p |
~r |
![]() |
![]() |
Solution
Let us try to come up with a strategy, starting with 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![]() ![]() |
Premise |
2. p | Premise |
3. ~r | Premise |
4. q![]() |
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 the fact that we needed q; working forwards we saw that we could easily get qr ...
Prove the valid argument
(p![]() ![]() ![]() |
p |
![]() |
![]() |
Solution
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. (p![]() ![]() ![]() |
Premise |
2. p | Premise |
3. p![]() |
2, Addition |
4. s![]() |
1, 3 Modus Ponens |
5. t | 4, Simplification |
Prove the valid argument
a![]() ![]() |
~b |
![]() |
![]() |
Solution
Strategy:
(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,
(2) Thus we require the negation, ~(bc). This is the same as
(3) We are given ~b by itself, so we can use Addition to get
We can now get the proof by going through this sequence of steps backwards:
1. a![]() ![]() |
Premise |
2. ~b | Premise |
3. ~b![]() |
2, Addition |
4. ~(b![]() |
3, De Morgan |
5. ~a | 1,4 Modus Tollens |
Before We Go On ...
This is not by any means the only possible proof. Here is another.
1. a![]() ![]() |
Premise |
2. ~b | Premise |
3. ~(b![]() ![]() |
1, Contrapositive |
4. ~b![]() |
2, Addition |
5. ~(b![]() |
4, De Morgan |
6. ~a | 3,5 Modus Ponens |
There are often many different proofs of a valid argument. You should also notice that the order in which the rules of inference are used depends very much on the particular argument you are trying to prove. Think of it like moves in a chess game: many moves are possible at any given time, and it is up to you to pick a good one.
Prove the valid argument
p![]() |
p![]() |
p | ![]() |
![]() ![]() |
Solution
Strategy:
(1) We can get both a and b individually using Modus Ponens.
(2) To get their conjunction, all we need do is to invoke Rule C:
1. p![]() |
Premise |
2. p![]() |
Premise |
3. p | Premise |
4. a | 1, 3 Modus Ponens |
5. b | 1, 2 Modus Ponens |
6. a![]() |
4, 5 Rule C |
Prove the valid argument
s![]() |
(p![]() ![]() |
~s![]() ![]() |
p |
![]() |
![]() |
Solution
Strategy
(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. s![]() |
Premise |
2. (p![]() ![]() |
Premise |
3. ~s![]() ![]() |
Premise |
4. p | Premise |
5. p![]() |
4, Addition |
6. ~r | 4, 2 Modus Ponens |
7. ~s | 1, 6 Modus Tollens |
8. ~q![]() |
3, 7 Modus Ponens |
9. q | 6, 8 Modus Tollens |
Before We Go On ...
As this example shows, not all proofs can be arrived at by a simple strategy; sometimes we have to fiddle a little to get them. If you are attempting a proof and your line of argument seems to be going nowhere, it is sometimes a good strategy to experiment a little until you see your way clear to a proof. Here are some things that often help:
1. Replace an implication with its contrapositive. 2. Use De Morgan to rewrite a conjunction or a disjunction. 3. Use De Morgan to rewrite a negation. 4. Try using any of the other tautological equivalences to rewrite a statement. 5. Take a coffee break. Above all, be persistent (come back from that coffee break and go back to work)! |
A proof of the following argument appeared in the Exercise set at the end of the last section.
p![]() |
![]() |
![]() |
Prove and comment on this argument
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![]() |
Premise |
2. p | 1, Simplification |
3. ~p | 1, Simplification |
4. p![]() |
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 |
![]() |
![]() |
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 |
![]() |
![]() |
By Rule C, this is really the same as:
p![]() |
![]() |
![]() |
Show that the argument
p![]() |
q |
![]() |
![]() |
is not valid.
Solution
Now we only know how to prove that an argument is valid. If you try to prove this argument, you'll get nowhere. It looks like Modus Ponens, but it's backwards, which is our clue that it's invalid in the first place. We shall demonstrate that the argument is invalid in two different ways.
Method I If this argument were valid, then the statement [(pq)
q]
p would be a tautology. In other words, in its truth table there would be only T's in the [(p
q)
q]
p column. To show that this is not the case, we need find only one F in that column. In other words, we need to find truth values for p and q making [(p
q)
q]
p false.
Now, to make this implication false, we need to make [(pq)
q] true and p false. To make (p
q)
q true, we need both p
q and q true. This will happen if q is true. In other words, if p is false and q is true, then [(p
q)
q]
p is false, showing that it is not a tautology. In symbolic form, here is the counterexample we have just found:
![]() ![]() ![]() |
||
![]() |
![]() |
![]() |
Method II Here is a more intuitive way of doing this. To demonstrate that the argument is invalid, we need to come up with a counterexample, that is, an instance of statements p and q for which the premises are true, but the conclusion p is false. Now, since p must be false, just make up a false statement for p, such as "0 = 1." We want the premises to be true, so we need pq and q to be true, so we pick a true statement for q, such as "the earth is round." Our argument then reads:
If 0 = 1, then the earth is round. | - True |
The earth is round. | - True |
![]() |
|
![]() |
- 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 q
p.
Decide whether the following argument is valid. If it is, then give a proof; if it is not, then give a counterexample.
Heat dissipation accompanies every irreversible chemical reaction. Therefore, if a chemical reaction is reversible, it dissipates no heat.
Solution
In order to analyze the argument, we translate it into symbolic form. The first sentence is an implication in disguise: it is saying that, if the chemical reaction under consideration is irreversible (that is, not reversible) then it dissipates heat. Thus we take p = "this chemical reaction is irreversible," and q = "this chemical reaction dissipates heat." The first sentence then becomes pq. The conclusion is also an implication, and is saying that ~p
~q. The argument thus becomes:
p![]() |
![]() |
![]() ![]() |
Although this reminds us of the Contrapositive rule, it is backwards; the correct conclusion should be ~q~p. Thus we suspect that the argument is invalid, and we look for a counterexample.
Our counterexample should give pq true, but ~p
~q false. Focus on the requirement that ~p
~q is to be false. The only way for an implication to be false is for the antecedent to be true and the consequent to be false. In other words, ~p must be true and ~q must be false. That is, p must be false and q must be true. Thus let us choose p = "0 = 1," and q = "the moon is round." Then the argument becomes:
If 0 = 1, then the mmon is round. | - True |
![]() |
|
![]() ![]() |
- False |
In tabular form, the counterexample is as follows:
![]() ![]() ![]() |
||
![]() |
![]() |
![]() |
Before We Go On ...
The conclusion of the original argument happens to be correct: it is true that reversible chemical reactions dissipate no heat. What is wrong is that the argument used to conclude this fact was invalid. In other words, a true conclusion was arrived at through invalid reasoning. This points up the difference between the truth of a statement and the validity of an argument. If an argument is valid, then you are guaranteed that if all its premises are true, then so is its conclusion. However, you are not guaranteed that the premises are true, nor is anything said about what happens when a premise is false. Likewise, if an argument is invalid, you can conclude nothing from it about the truth of its conclusion; it may still be true or it may be false.
Decide whether the following argument is valid. If it is, then give a proof; if it is not, then give a counterexample.
If the moon is made of green cheese, then pigs can fly and circles are round. The moon is indeed made of green cheese. Therefore pigs can fly.
Solution
Let us translate this into symbolic form: Let p: "the moon is made of green cheese," q: "pigs can fly," and r: "circles are round." The argument is then
p![]() ![]() |
p |
![]() |
![]() |
The premises are just begging to have Modus Ponens applied to them, which would yield qr. From Simplification we can then get q alone. This gives us the following proof, showing that the argument is valid:
1. p![]() ![]() |
Premise |
2. p | Premise |
3. q![]() |
1,2 Modus Ponens |
4. q | 3, Simplification |
Before We Go On ...
This illustrates the fact that a valid argument can have false premises and a false conclusion. (Note: Only one premise is false. Do you see why?) Validity is really about the form of the argument, not the meaning of the statements.
The following example is reminiscent of the kind of question that often appears in aptitude tests (such as the LSAT).
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![]() ![]() |
l![]() |
d![]() |
![]() |
![]() ![]() |
If we look at this argument, we can see the following string of implications:
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![]() ![]() |
Premise |
2. l![]() |
Premise |
3. d![]() |
Premise |
4. l![]() |
2,3 Transitivity |
5. l![]() ![]() |
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 g
d by itself. The only way around this little annoyance is to use some Switcheroo on it:
6. ~l![]() ![]() |
5, Switcheroo | |
7. (~l![]() ![]() ![]() |
6, Distributive Law | |
8. (~l![]() |
7, Simplification! | (Wasn't that clever?) |
9. l![]() |
8, Switcheroo |
![]() | 5. Rules of Inference | ![]() | Section 6 Exercises | ![]() | Main Logic Page | ![]() | "Real World" Page |
![]() | Stefan Waner (matszw@hofstra.edu) | ![]() | Steven R. Costenoble (matsrc@hofstra.edu) |