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.
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.
Arguments and Validity
An argument is a list of statements called premises followed by a statement called the conclusion.
The argument is said to be valid if the statement
is a tautology. In other words, validity means that if all the premises are true, then the conclusion must be true.
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.
A proof of an argument is a list of statements, each of which is obtained from the preceding statements using one of the rules of inference T1, T2, S, C, or P. The last statement in the proof must be the conclusion of the argument.
As an example, we have the following proof of the argument given above, which we considered in the preceding section:
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.
Prove the valid argument
we see that this is nothing more than Modus Ponens. Thus we get the following one-step proof:
|3. rs||1,2 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.
|3. p||1, Simplification|
|4. ~r||2, 3 Modus Tollens|
Rule C plays an important role in the next proof.
We can get both a and b individually using Modus Ponens. To get their conjunction, all we need do is invoke Rule C.
|4. a||1, 3 Modus Ponens|
|5. b||2, 3 Modus Ponens|
|6. ab||4, 5 Rule C|
(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:
|4. qr||1, 2 Modus Ponens|
|5. q||3, 4 Disjunctive Syllogism|
(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:
|3. pr||2, Addition|
|4. st||1, 3 Modus Ponens|
|5. t||4, Simplification|
(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:
|3. ~b~c||2, Addition|
|4. ~(bc)||3, De Morgan|
|5. ~a||1, 4 Modus Tollens|
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:
|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.
(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:
|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:
General Hints and Suggestions
As a general strategy, try working backwards from the conclusion and forwards from the premises until your paths of reasoning meet somewhere in the middle. Here are some specific techniques for manipulating statements.
2. Use De Morgan's Law to rewrite a conjunction or a disjunction.
3. Use De Morgan to rewrite a negation of a conjunction or a disjunction.
4. Try using any of the other tautological equivalences to rewrite a statement.
5. Take a coffee break to clear your head.
Above all, be persistent (come back from that coffee break and go back to work)!
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.)
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.
|2. p||1, Simplification|
|3. ~p||1, Simplification|
|4. pq||2, Addition|
|5. q||3, 4 Disjunctive Syllogism|
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
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:
By Rule C, this is really the same as:
is not valid.
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|
|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).
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.
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|
Here is the symbolic form of the argument.
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.
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:
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:
|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|