CHAPTER 7
Natural Deduction in Propositional Logic
Click here to skip this pep-talk and go right to the the discussion of lesson 26.
Click here to skip all discussion and go right to the assignments for lesson 26.
Now we will begin doing proofs. Please be assured that if you take things step by step, and you have confidence in your ability to do this, you will be able to fully grasp this final chapter. Don't try to understand too much at first. As mentioned earlier, it is possible to begin learning how to do these proofs without fully understanding why they work that way. Typically you will develop an understanding of why from the actual practice of how. Obviously an eventual understanding of both is the most beneficial.
To do well on this chapter there is one main secret step, and I'll just tell it to you up front. I won't make you scratch off any silver paint to reveal it. (I probably would, though, if I had the technology, so don't thank me yet...)
We have all probably learned to play a card game at one time or another, where certain things were allowed and others were not. This chapter is not all that different. And if you approach it as you would a game, as something you want to do (instead of something you dread), then you will be much more likely to master it.
Besides, it is fun, once you get rolling. Soon you'll be a natural deduction junkie, and you can't get natural deduction problems anywhere but logic class. (When you are done with PHI 320, Advanced Symbolic Logic, you will be in trouble. You'll have to go to grad school) (!)
Each lesson will present to you several new rules which you will then apply to doing proofs, but once you understand the basic process of working a proof, that won't change.
Spend some time becoming familiar with the rules, try to understand them if you can, and start to memorize them. All 18 rules are listed inside the back cover of the Hurley text. (and therefore aren't in the glossary) Either copy this list or create your own list as you go. Either way, you should have one sheet where all the rules are simply listed. You will have this sheet by you all the time you are working proofs. Some of the earlier rules will be used so frequently, that you will automatically memorize them. You do not need to memorize all the rules, but the more you do, the easier it will be to work through the proofs.
Working proofs means that you have one or more premises as given (as already known to be true). You are also given a conclusion that you must prove to be true. (It is--you just have to prove it) What you have to work with are the given premises and the rules. There is usually more than one way to do a proof.
STEPS:
1) All the lines are numbered. Your conclusion is placed after a slash (/) across from your last given premise to keep it in sight, but out of the way.
2) Then, you number the next line and see what you are able to derive, using given premises and rules. Out to the right of the line you must give a justification of that line. A justification consists in the listing of the rule used (abbreviated) and the line number(s) you used the rule on.
TIP! Be sure that the line number(s) of the justification does not include the number of the line you are justifying. For some reason this is a common mistake. e.g.,
IMPORTANT: Any justification must be from lines that are already proven (either given or themselves previously justified), which will be lines above the one you are working on, however, other than that, these lines may appear in any order in the proof. A line may be used as many times as you like in working your proof.
As the proofs become more difficult, you will find yourself thinking about them from two directions. On the one hand, you will simply do what ever you see that you can do. (This is the normal, top ê down way). On the other hand, you will on scratch paper begin to work from the bottom é up starting with the conclusion and figuring out what you would need to have to get your conclusion. Hopefully, one way or the other (or both) you will solve the proof.
3) Once you have derived and justified a line which is identical to your given conclusion you are done. If you want to be fancy you can write Q. E. D. below the last line. This stands for "it is proven" (or something like that) in Latin
Here is a step by step example:
1. ~C É (A É C)
2. ~C //AThis is problem 5 on p. 372. (I'm doing your homework for you) here is the problem written out. Click here to see the first step in the proof.
In each section in Hurley, the exercises will begin with already worked-out proofs where you simply provide the justification. This section can be very helpful! Study these proofs to learn how proofs are done and why certain steps were taken. Then copy the given premises and the conclusion to be proved onto a separate piece of paper. Try to work the proofs yourself. You can check yourself against the worked-out proofs.
Do not attempt Part II of the exercises in Hurley until you are comfortable with Part I.
Hurley introduces "strategies" at the end of each section. Keep a finger in these as you try to do your homework, they can be useful when you are stuck, and will be easier to understand when you have a specific question to answer than when you read through them the first time.
Re-read this discussion often during Chapter 7.
LESSON #26
Rules Of Implication I
Reading Assignment: 7.1 (pp. 364-370)
All of the rules of implication are little arguments that "prove" something "new." You use them on entire lines, that is on the main operator for each line, and derive something new on a new line.
Modus Ponens: "The Granddaddy of all reasoning"
Obviously if it is true that if "if P is true, then Q is true," then if P is true, then Q will be true, too. (Did you catch that?!) To have an instance of modus ponens you must have a statement where the main connector is a É ; and another statement which affirms the antecedent. Then you can conclude the consequent. p É q
p
q
Modus Tollens:
This one's a little harder. Again, if it is true that "if P then Q, "then if Q is not true, then it means that P was not true either (because if P were true, then Q would be true, too. But Q is not true, so we know that P must not have been true either.) To do modus tollens you again need a É statement; as well as another statement which says the second side is not true. Then you can conclude that the first side is not true. p É q
~q
~p
Hypothetical Syllogism:
You can think of hypothetical syllogism as simply "eliminating the middle man" and pulling the ends together. To do hypothetical syllogism you must have two É statements where the first side of one is the same as the second side of the other. Then you can eliminate this common component and connect the remaining sides together with another É . p É q
q É r
p É r
Disjunctive Syllogism:
A disjunction means that either one side or the other is true (or maybe both). They are not both false. So if you know that one side is false, then it must be the case that the other side is the true side. To do disjunctive syllogisms, you must have a "v" statement and another statement which denies the left disjunct. Then you can conclude that the other side is true. p v q
~p
q
Note: Some students notice that given the definition of "or" this should work the same with either disjunct. This is true, but in the interests of working proofs one step at a time, and justifying each step, we only do DS with the left disjunct. To do the other we will soon learn a rule (commutativity) that switches the order of V statements.
Logic Coach Assignment: 7.1 I all, II1-15, III 1-5
Assignment 1: (20 points each)
Use the first four rules of inference to derive the conclusions of the following arguments:
NOTE: Be sure to copy the problems down correctly and neatly!
A) 1. (P · Q) v (X É
Y)
2. ~(P · Q)
3.
~Y // ~X
B) 1. ~X É (Y É
~Z)
2. ~M É (~Z É X)
3. ~M · ~X
// ~Y
C) 1. B É (D É
~E)
2. F v (~E É
M)
3. B
4.
~F // D É M
D) 1. ~X v ( P v G)
2. P É V
3. ~~X
4.
~V //G
Assignment 2:
Translate the following argument into symbolic form, then use the first four
rules to derive the conclusion.
Either funding for nuclear fusion will be cut or if sufficiently high temperatures are achieved in the laboratory, nuclear fusion will become a reality. Either the supply of hydrogen fuel is limited, or if nuclear fusion becomes a reality, the world's energy problems will be solved. Funding for nuclear fusion will not be cut. Furthermore, the supply of hydrogen fuel is not limited. Therefore, if sufficiently high temperatures are achieved in the laboratory, the world's energy problems will be solved. (C, H, R, S, E)
Home | Table of Contents | Next Assignment | Questions