Main Connectives in a Proof
Date: 10/28/2001 at 22:02:09 From: Elizabeth Subject: Logic Given 1. [~A^ ~(D^E)] ->(B -> ~D) 2. ~(D^E) ^ ~R 3. E -> F 4. ~A V (D^E) 5. ~(D^E) -> (B V E) Prove ~D V F ^ means "and" -> means "then" V means "or" ~ means "not" This is what I've done so far: Statements Reasons 1. [~A^ ~(D^E)] ->(B -> ~D) 1. Given 2. ~(D^E) ^ ~R 2. Given 3. E -> F 3. Given 4. ~A V (D^E) 4. Given 5. ~(D^E) -> (B V E) 5. Given 6. (~D V ~E) ^ ~R 6. (5)De Morgans 7. (~D V ~E) 7. (6) Law of simplification 8. ~R 8. (6) Law of simplification 9. ~(D^E)->(B->~D) 9. (1) Law of simplification 10. ~A -> (B->~D) 10. (1) Law of simplification 11. ~A 11. (4,7)Law of Disjunctive inference 12. (B->~D) 12. (10, 11) Law of Detachment
Date: 10/29/2001 at 16:59:40 From: Doctor Achilles Subject: Re: Logic Hi Elizabeth, Thanks for writing to Dr. Math. Great start on the proof! You did exactly the right thing with lines 7 and 8. One thing to be careful about when doing proofs is not to apply rules to parts of a line, but only to the entire line. For example, you cannot go from: 1. [~A ^ ~(D^E)] -> (B -> D) to 10. ~A -> (B -> D) Let's take a simpler example to see why. Going from: 1. P ^ Q -> R to 2. P -> R is like going from the English sentence "IF it is freezing out AND there are rain clouds THEN it will snow" to "IF it is freezing out THEN it will snow." This is not a valid inference, because there have to be clouds before it can snow, no matter how cold it gets. Similarly, you can't get your line 11 either. The way I always approach proofs is looking for what I've been taught to call the "main connective" or the "main logical symbol." You can identify the main connective by looking at the structure of the sentence. Most sentences are made by taking two smaller sentences and sticking a logical symbol between them. For example, the sentence: 1. [~A ^ ~(D ^ E)] -> (B -> ~D) is made by sticking a -> between the sentence A ^ ~(D ^ E) and the sentence B -> ~D. The -> in the middle is therefore the main connective. BE CAREFUL, because the subsentence B -> D also has a -> in it, but this -> is NOT the main connective, the main connective is the -> that connects the two big sentences. What is the main connective of this? 2. ~(D^E) ^ ~R Well, that sentence is made by taking a ~(D ^ E) and combining it with a ~R. In this case they're combined using an ^. (Notice again that the ^ in the subsentence ~(D^E) is NOT the main connective). I said before that MOST sentences are made by taking two smaller sentences and sticking a logical symbol between them. The only exception is when the main connective is ~. Take a look at this made-up sentence: ~[P v (F -> ~R)] This sentence is made by starting with P v (F -> ~R) and just sticking a ~ on the whole thing. The main connective is therefore ~. (Once again, be careful to notice that the main connective is the ~ in front of the whole thing and it is not the ~ that's just in front of the R.) One more made up sentence: ~P v (F -> ~R) Notice here tha because there are NO parentheses around the whole sentence, the ~" in front only applies to the P and DOES NOT apply to the entire sentence. The main connective here is therefore the v that connects ~P with F -> R. So what's the big deal about main connectives? Here is Dr. Achille's big number one MOST IMPORTANT RULE ABOUT DOING PROOFS: The ONLY thing you can work on when you're doing a proof is the main connective of a sentence. This means: When you're working on a proof, the first thing to do is identify the main connective and figure out what you can do with it. Here's a list of all the things you can do with a proof: When you are GIVEN a sentence whose main connective is ^, you are entitled to each part by itself. When you are GIVEN a sentence whose main connective is <->, you should find ONE of the two parts, and that entitles you to the other. When you are GIVEN a sentence whose main connective is ->, you should find the part BEFORE the -> and then you are entitled to the part after. (This one is a little tricky): When you are GIVEN a sentence whose main connective is v, you should first assume that the part before the v is true, then derive some new sentence X, then assume that the part after the v is true and derive THE SAME sentence X, and that entitles you to X. When you are GIVEN a sentence whose main connective is ~, you can usually apply one of these rules to it: DeMorgan's rule 1: ~(p ^ q) -------- ~p v ~q DeMorgan's rule 2: ~(p v q) --------- ~p ^ ~q Disjunctive syllogism (DS): (p v q) ~p ------- q Modus tollens: (p -> q) ~q --------- p (When using these rules, you can substitute entire subsentences for the p's and q's, as long as you don't mess with their internal structure while you're doing it.) Here's a list of strategies for proving something: When you're trying to FIND a sentence whose main connective is ^, you need to derive both parts separately. When you're trying to FIND a sentence whose main connective is <->, you need to assume the left side, then derive the right, THEN assume the right and derive the left. When you're trying to FIND a sentence whose main connective is ->, you should assume the LEFT, then derive the RIGHT. When you're trying to FIND a sentence whose main connective is v, you just need to derive one part or the other, it doesn't matter which, and then you get the whole sentence for free. When you're trying to FIND a sentence whose main connective is ~, you should assume the rest of the sentence without the ~ and then derive a contradiction. For instance, one way to prove ~(p ^ ~p): 1) p ^ ~p Assumption, for contradiction 2) p simplification on the ^ in 1 3) ~p simplification on the ^ in 1 Since 2 and 3 contradict each other, you are entitled to conclude that the assumption is false, and therefore that ~(p ^ ~p) is true. That's a lot of information to get started on. Let's look at what you're given now for the problem: 1. [~A^ ~(D^E)] ->(B -> ~D) 1. Given The main connective here is ->, so we're going to want to find the first part ~A ^ ~(D^E) so that we can get the second part. We don't have any way to find the first part yet, so for now we'll just keep in the back of our heads that we want to find it. 2. ~(D^E) ^ ~R 2. Given The main connective here is ^, so you did the right thing by simplifying. 3. E -> F 3. Given Just as in line 1, we want E, but we don't have it yet, so we'll be on the lookout. 4. ~A V (D^E) 4. Given It's tricky to work with v sentences. Maybe we'll get lucky and be able to apply a disjunctive syllogism to this one. We'll keep our eyes open for A or for ~(D^E). 5. ~(D^E) -> (B V E) 5. Given We don't have ~(D^E) yet, but just as in 1 and 3, we'll keep our eyes peeled. The easiest thing to work with looks like line 2, so let's start there. 6. ~R 6. Simplification of 2 7. ~(D^E) 7. Simplification of 2 Hold on, we were on the lookout for ~(D^E). (Check back at line 5). So now what? Well we have ~(D^E) (7) and we have ~(D^E) -> (BvE) (5), so that means we are entitled to: 8. B v E 8. Detachment on 5 and 7 Look back at number 4; we can ALSO use ~(D^E) for a disjunctive syllogism on 4. 9. ~A 9. DisSyll on 4 and 7 Now check back at line 1. We were looking for ~A ^ ~(D^E), and we can get it now by combining line 7 with line 9. 10. ~A ^ ~(D^E) 10. Combining 7 and 9 So now we are entitled to the second part of line 1. 11. B -> ~D 11. Detachment on 1 and 10 What use is this line? Well, if we had B, we could get ~D, and then getting to ~D v F (which is what we're after) would be easy. The only other places B appears is on lines 5 and 8. 5 is pretty ugly, but we might be able to do something with 8. The main connective of 8 is v, so we have to assume one side, derive a new sentence, then assume the other side and derive the same sentence again. If we can do that, then we can keep the sentence we derive. 12. B 12. NEW ASSUMPTION This combines nicely with 11. 13. ~D 13. Detachment on 11 and 12 (still under assumption on 12) This is very close to our goal, and introducing v is free. That is, since we have ~D we can make a new sentence ~D v X, where X is WHATEVER WE WANT. Since our goal here is ~D v F, let's make that. 14. ~D v F 14. v introduction on 13 (still under assumption on 12) BUT WE'RE NOT DONE YET. We're still under the assumption on 12. Remember, we started with B v E and we agreed that we would just assume for a minute that B was true and then do some work from there, and then we would assume that E is true and work from there. Now it's time to finish the second part of our agreement. 15. E 15. NEW ASSUMPTION Where else do we see E? It's tied up in a lot of things, but take a look at line 3. We've been waiting for E alone. 16. F 16. Detachment on 3 and 15 (still under assumption on 15) Now, we can introduce F v X, where X is anything we want. We can also, using the same rule, introduce X v F, where X is anything we want. The goal of this whole proof has been to find ~D v F, so let's do that. 17. ~D v F 17. v introduction on 16 (still under assumption on 15) Now, we fulfilled our agreement with line 8. We assumed each part and independently derived ~D v F. So we can now write: 18. ~D v F 18. v removal line 8 (see sub-proofs on 11-14 and on 15-17) And thus we've derived our goal. This is a lot of information to digest, and it requires thinking in new ways about logic. If I went over anything too quickly or you have more questions, please write back. Good luck and I hope this was helpful. - Doctor Achilles, The Math Forum http://mathforum.org/dr.math/
Date: 10/29/2001 at 21:30:14 From: Elizabeth Subject: Re: Logic I just wanted to say thank you very much.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.