Class VII

Propositional Logic:
Natural Deduction IV

Topics discussed:

• Conditional proof
• An example of a proof using the conditional proof rule, with discovery numbers
• Indirect proof
• An example of a proof using both the conditional proof rule and the indirect proof rule, with discovery numbers
• A proof checking program
• Proving Logical Truths

Assignments:

Reading assignments	Homework assignments in Logic Coach
Chapter 7, section 5	Part I, exercises #2,3,6,8,12,14 Part II, exercises #2,3
Chapter 7, section 6	Part I, exercises #2,5,8,11,17 Part II, exercises #2,3
Chapter 7, section 7	Part I, exercises #2,3,5,9

The Conditional Proof Rule

Imagine the following argument:

If the Democrats are elected, then we will have higher taxes, more students will go to college, and Medicare costs will continue to rise. If more students go to college, then incomes will rise. If we have higher taxes, then there will be less money for new businesses. Therefore, if the Democrats are elected, then incomes will rise, there will be less money for new businesses, and Medicare costs will continue to rise.

Notice that if someone were to respond that incomes will not rise because the Republicans will win, the response would be that the argument said that the effects would result if the Democrats win. In other words, let us assume, for the sake of the argument, that the Democrats win. Then certain things will happen: incomes will rise, there will be less money for new businesses, and Medicare costs will continue to rise. But these three things are conditional on the Democrats winning.
We capture this reasoning in the following way:

1. D [ (T C) M] (premise)
2. C I (premise)
3. T L (premise)
4. Assume D (for the sake of the argument)
5. Assuming D, we have (T C) M (from 1 and 4 by MP)
6. Thus (assuming D) we have C from 5 (by Simp after some moving around)
7. Thus (assuming D) we have I (from 2 and 6 by MP)
8. (Assuming D) we also have L (from 3 and the C we get from 5)
9.(Assuming D) we also have M (from 5)
10. Thus (assuming D) we have (I L) M (from 6, 7, and 8)
11. Therefore D [ (I L) M]

You'll notice that 10 and 11 are actually saying the same thing.
The way we capture this in a proof is as follows: (1) We will assume the antecedent of the conclusion, D, as a premise (an assumption for the purposes of conditional proof, ACP). (2) Then we will prove the consequent of the conclusion, while acknowledging that these lines are based on that assumption. (3) Finally we will reach our conclusion by the rule Conditional Proof, CP. The way we indicate that our statements are based on an assumption is to draw a vertical line to the left of the statement. (The line would normally be continuous.) Our proof looks like the following:

The ways to read these lines are as follows:
Line 4: We are assuming D.
Lines 5 through 15: on the assumption of D (and the original premises) we can derive these statements.
Line 16. Since we have derived line 15, (I L) M, on the assumption that D is true, it follows that D [ (I L) M] must be true. The justification reads: On the assumption of 4 we have derived 15. The 4--15 indicates that a derivation took place between 4 and 15.
Anytime you use an assumption (ACP), you must "discharge" that assumption by CP. Otherwise the conclusion that you reach is on the basis of an assumption, not just the original premises.

Conditional proof can also be used more than once, either in sequence, or with one embedded in another. For an example of the latter case look at our rule Exportation: [(p q) r] :: [p ( q r)]. Look at the following proof which normally would use this rule, but in which we will use CP instead:

My strategy was as follows: I need to get the conclusion P ( Q R) . So I should assume its antecendent, P, and try to prove its consequent, Q R, and then use CP. So now my goal is to prove Q R. I do this (again) by assuming its antecendent (Q) and proving its consequent (R), and then using CP.
One further note about CP. The assumption lines must be inside each other. In other words, you must discharge the last assumption first.

The Indirect Proof Rule

The Indirect Proof Rule (IP) is based on the fact that if you can derive a self-contradictory statement from a set of statements, then that set of statements must be inconsistent. If you assume that all the statements in an inconsistent set, except one, are true, then the other one must be false. In other words, if we assume a statement as an assumption, and we can derive a self-contradiction from it (and the other premises) then the assumption must be false (since we are assuming our original premises are true). So our method is this: we will assume the negation of what we are trying to prove. (Say we are trying to prove p; we will assume p). If, on the basis of that assumption we can derive a statement of the form q q, then we can say that p is true.
This method of reasoning is also called "reductio ad absurdum", the "reducing" to an absurdity. If anything leads to an absurdity (and a self-contradiction is the ultimate absurdity), then it must be false.

Look at the following proof using Indirect Proof (IP):

Some comments about this proof: Since I wanted to prove R, I assumed its opposite as an assumption (AIP). On the basis of this assumption (note the assumption line) I derived a self-contradiction: W W. This allowed me to remove the line and assert that the assumption with a tilde in front of it was true. Note that IP tells us to put a tilde on the assumption, not take one off.

Some further notes about indirect proofs:
1. They can be used to prove any statement in a proof, not just the conclusion.
2. The goal in IP is any statement of the form p p, where p may be simple or compound. This means that I don't have a specific p in mind. Thus IP's are often easier than other proofs since often my method is just to derive as many statements as I can (most of the time using the rules which break up statements) keeping my eyes open for any two statements which contradict each other. When I find them, I put them together by Conj to get my self-contradiction p p. In the next proof with discovery numbers you'll notice gaps where I wasn't after anything in particular--I was just looking for two contradictory statements wherever they occurred. You'll also notice that I have used an Indirect Proof inside of a conditional proof. Click here to see this proof.

Logical Truths

Logical truths are statements which are true regardless of any factual considerations. When these are expressed in propositional logic, logical truths are tautologies. Since their truth does not depend upon on fact, they can be derived from no premises at all. For example, look at this logical truth (tautology):

A (A v B)

A proof of it would be

| 1.	A	ACP
| 2.	Av B	1 Add
3.	A (A v B)	1-2 CP

Notice that there are no premises in this proof. The only assumptions are those introduced by a conditional proof. All proofs of logical truths begin with either ACP or AIP.

Look at another proof of A (A v B) by Indirect Proof:

|1.	[A (A v B)]	AIP
|2.	[A v (A v B)]	1 Impl.
|3.	A (A v B)	2 DM
|4.	(A v B)	3 Com, Simp
|5.	A B	4 DM
|6.	A	5 Simp
|7.	A	3 Simp
|8.	A A	6, 7 Conj
9	[A (A v B)]	1-8 IP
10	A (A v B)	9 DN

This proof is not too surprising. If you deny a tautology (all T's), you get a contradiction (all F's).

For help on using Logic Coach click here -->

To send your homework to Dr. Redmon, click here-->