Subsection 3.1.2 A Proof Is an Argument
A proof is an argument that applies one or more:
sound reasoning methods
to a collection of:
facts and definitions
to produce a conclusion that must be true whenever the facts are true.
The facts and definitions that we’ll use are usually domain-specific. They capture what we know about the particular problem that we are trying to solve.
The reasoning methods, on the other hand, are general. We’ll be able to describe them once and then exploit them to discover new things about everyday events, computer circuits, and mathematics. The goal of this course is for you to learn about these reasoning methods so that you can apply them to whatever problems you later encounter
Activity 3.1.1. Wet Sidewalks.
Let’s do a simple example. We’ll give names to the following statements:
\(R\) : It’s raining.
\(W\) : The sidewalks are wet.
\(S\) : The sidewalks are slippery.
\(C\) : It is important to be careful.
Suppose that we have the following facts:
[1] \(R \rightarrow W \) If it’s raining then the sidewalks will be wet.
[2] \(W \rightarrow S \) If the sidewalks are wet, they will be slippery.
[3] \(S \rightarrow C \) If the sidewalks are slippery then it is important to be careful.
At this point, we have no idea whether or not it’s important to be careful. But suppose we add one more fact:
[4] \(R\) It’s raining.
Now, using the kind of reasoning that we do every day, we can say:
If it’s raining then the sidewalks will be wet. But it is raining. So the sidewalks will be wet.
If the sidewalks are wet, they will be slippery. But they are wet. So they are slippery.
If the sidewalks are slippery then it is important to be careful. But they are slippery. So it is important to be careful.
We’ve just constructed a proof that, given what we already knew, it’s important to be careful
We will soon give a name to the inference rule that we just used (three times). It’s called modus ponens . It tells us that if we know p → q and we know p , then we can conclude q .
We’ll be successful at producing proofs when we start out with enough information to enable us to derive useful conclusions. Interestingly, however, our ideas about proofs may help us to solve problems even when we can’t actually produce a proof.
Activity 3.1.2. Eradicate Ucklufery.
Let’s give names to the following statements:
\(V\text{:}\) Ucklufery (a very nasty tropical disease) is caused by a virus.
\(E\text{:}\) We might be able to eradicate ucklufery by developing a vaccine against it.
Suppose that we have the following fact:
\(V \rightarrow E\) If ucklufery is caused by a virus, we might be able to eradicate it by developing a vaccine against it.
We know one useful thing about ucklufery. But we’re stuck if we try to use it. We don’t know enough to reason to any conclusion about whether we should work on a vaccine. But the one thing we do know is a starting point: If we could show that a virus is the culprit, then we would know that we should work on a vaccine. So we actually do know what we should perhaps do next: Attempt to prove that V is true. If it is, then we can apply modus ponens to [1] and V to conclude that we should look for a vaccine.
By now you’re probably thinking something like, “Okay, I get the proof idea. I’ve been doing it for years. So what comes next in this course?” The answer is that we are going to formalize the notion of proof so that we’ll be sure that we use it correctly. In other words, when we say we have a proof, we’ll be sure that the conclusions that we’ve derived really must follow from the facts that we have assumed.
Problems 3.1.3.
(a)
Suppose that we have the following facts:
If the fruit stand sells bananas then they also sell at least one of strawberries or raspberries.
The fruit stand doesn’t sell strawberries.
Which of the following claims must be true:
The fruit stand doesn’t sell bananas.
The fruit stand sells raspberries.
The fruit stand doesn’t sell bananas or does sell raspberries.
The fruit stand sells bananas.
(b)
Suppose that we have the following facts:
If it’s Friday or Saturday, the pub will be crowded.
If the pub is crowded, Riley won’t go.
Riley is at the pub.
For each of the following claims, indicate whether it must be true, must be false, or could be either true or false:
It is Friday.
It is Saturday.
The pub is crowded.