CS 2104 Problem Solving in Computer Science, Spring 2012 OOC 3: Logic ------------------------------------------------------------------------------- 1. [10 points] Consider the following (alleged) inference rule: If A, then B. Not A. Therefore, not B. Is this actually an inference rule? Verify your conclusion by constructing a relevant truth table. Soln: To be an inference rule, the argument form must be a tautology, so we must consider (If A, then B) and (not A) --> (not B) A B If A then B not A (If A then B) and (not A) not B Rule ------------------------------------------------------------------------- F F T T T T T F T T T T F F T F F F F T T T T T F F T T ------------------------------------------------------------------------- So, this is not a valid inference rule. (Only the second row of the truth table needed to be shown to verify that, but that's hindsight.) 2. [10 points] Suppose an argument was constructed using the (alleged) inference rule given in question 1, by substituting propositions for the variables A and B. a) Without knowing what specific propositions are substituted for A and B, is it possible to say anything definitive regarding the validity of the argument? Explain clearly. Soln: An argument is value if, and only if, the form of the argument is a tautology. Since we showed in question 1 that the rule is NOT a tautology, no argument based on it could be valid. b) Again, without knowing what specific propositions are substituted for A and B, is it possible to say anything definitive regarding the soundness of the argument? Explain clearly. Soln: An argument is sound if, and only if, the argument is valid and its premises are true. Since, from part a, the argument cannot be valid, it also cannot be sound. 3. [25 points] Consider each of the following arguments, and decide whether the argument is invalid or valid. For each argument, justify your conclusion clearly. a) If a mouse has built a nest in my car's heater, then I will have a cold drive to work. I was warm during my drive to work. Therefore, a mouse has not built a nest in my car's heater. Soln: Let's symbolize this argument: M: a mouse has built a nest in my car's heater C: I will have a cold drive to work W: I was warm during my drive to work... but that's really "not C" So, the argument form is: (if M then C) and (not C); therefore, not M. Now, that's just modus tollens (slide 15 of the Propositional Logic notes) and so this IS a valid argument. b) If a mouse has built a nest in my car's heater, then I will have a cold drive to work. I was cold during my drive to work. Therefore, a mouse has not built a nest in my car's heater. Soln: Again, let's symbolize this argument; aha, the symbolization above will do for this one as well. So, this argument form is: (if M then C) and (C); therefore not M. This isn't one of the inference rules from the notes, so we need to analyze it. In this case, we see this is NOT a tautology, because if M and C are both true then the form is false: M C if M then C (if M then C) and (C) not M Form ----------------------------------------------------------- T T T T F F Therefore, this argument IS NOT valid. c) If it snows tonight, then I will walk to campus in the morning. If I walk to campus in the morning, I will have to skip breakfast. So, if it snows tonight then I will skip breakfast in the morning. Soln: Now we need a new symbolization: S: it snows tonight W: I will walk to campus in the morning B: I will skip breakfast Then the argument form is: (if S then W) and (if W then B); therefore (if S then B) Again, we need to analyze this with a truth table: S W B (if S then W) and (if W then B) (if S then B) Form ------------------------------------------------------------- F F F T T T T T F F T T T T T T F T F T F F T T F T T T T T T T T F F F F T F T T F T F F T T T T T F T F F F T T T T T T T T T So, this argument form is a tautology and the argument IS valid. d) If it snows tonight, then I will walk to campus in the morning. If I walk to campus in the morning, I will have to skip breakfast. So, if I eat breakfast in the morning then it must have not snowed overnight. Soln: The symbolization above will do for this one as well. The argument form is: (if S then W) and (if W then B); therefore (if not B then not S) Again, we need to analyze this with a truth table: S W B (if S then W) and (if W then B) (if not B then not S) Form --------------------------------------------------------------------- F F F T T T T T F F T T T T T T F T F T F F T T F T T T T T T T T F F F F T F T T F T F F T T T T T F T F F F T T T T T T T T T So, this argument form is a tautology and it IS valid. Note: The two implications "if P then Q" and "if not Q then not P" are logically equivalent. That is, they always have the same truth value. So, if you compare this part to part d, you see that the conclusions of the two arguments are, in fact, the same, as are the premises. e) If it snows tonight, then I will walk to campus in the morning. If I walk to campus in the morning, I will have to skip breakfast. So, if it does not snow tonight then I will eat breakfast in the morning. Soln: We can use the same symbolization again. The argument form is: (if S then W) and (if W then B); therefore (if not S then not B) Again, we need to analyze this with a truth table: S W B (if S then W) and (if W then B) (if not S then not B) Form --------------------------------------------------------------------- F F F T T T T T F F T T T T F F So, this argument form is NOT a tautology and the argument IS NOT valid. Note: "if not P then not Q" is the inverse of "if P then Q". They are NOT logically equivalent, nor is one the negation of the other. 4. [25 points] Consider each of the following arguments, and decide whether the argument is invalid or valid but unsound or sound. For each argument, justify your conclusion clearly. Note on solutions: In order to determine soundness, you must determine whether each of the propositions used in these arguments is true or false. That may have required a little research: true Nev: Yucca Mountain is in Nevada. true West: Yucca Mountain is west of the Mississippi River. false North: Mt Erebus is north of the Arctic Circle. Of course, you must also consider whether the argument form is even valid. a) If Yucca Mountain is in Nevada, then it is west of the Mississippi River. Yucca Mountain is not west of the Mississippi River. Therefore, Yucca Mountain is not in Nevada. Soln: First of all, if we symbolize this we have the form (if Nev then West) and (not West); therefore, not Nev That's modus tollens again, so we know it's valid. But, the second premise is false, since Yucca Mountain IS west of the Mississippi River. Therefore, this argument is valid but unsound. b) If Yucca Mountain is in Nevada, then it is west of the Mississippi River. Yucca Mountain is west of the Mississippi River. Therefore, Yucca Mountain is in Nevada. Soln: this time the argument form is (if Nev then West) and (West); therefore Nev. Constructing the truth table shows that this form is NOT a tautology, and therefore this argument is simply invalid. c) Yucca Mountain is in Nevada or Mount Erebus is north of the Arctic Circle. Yucca Mountain is in Nevada. Therefore, Mount Erebus is not north of the Arctic Circle. Soln: this time the argument form is (Nev or North) and (Nev); therefore, not North Constructing the truth table shows that this form is NOT a tautology, and therefore this argument is simply invalid. d) Yucca Mountain is in Nevada or Mount Erebus is north of the Arctic Circle. Mount Erebus is not north of the Arctic Circle. Therefore, Yucca Mountain is in Nevada. Soln: the argument form is (Nev or North) and (not North); therefore, Nev. This form is modus tollendo ponens (slide 15 of the notes again), if you believe that "and" is commutative, which it is. So the argument is valid. Now, Yucca Mountain IS in Nevada, which makes the first premise true. And, Mt Erebus is NOT north of the Arctic Circle, so the second premise is also true. Therefore, the argument is (valid and) sound. e) Mount Erebus is north of the Arctic Circle. Mount Erebus is not north of the Arctic Circle. Therefore, Yucca Mountain is not in Nevada. Soln: the argument form is (North) and (not North); therefore, (not Nev) Now the argument form IS a tautology. Consider the fact that either North is false or not North is false, so that the "and" of the premises must always be false. Hence, the argument form must always be true. On the other hand, one of the premises MUST be false; that's clear even if you don't know which one is false. Therefore, the argument IS valid, but is NOT sound. Note: This illustrates the adage that you can (validly) infer anything you like from a contradiction, including unrelated things. But doing so does not yield a sound argument. 5. [10 points] Is the following statement true or false? Justify your conclusion carefully. Some integer is equal to the sum of its proper divisors Soln: This is an existential statement; that is, it asserts the existence of an integer that has a specific property. We could show it's true by finding a single example of such an integer. Consider that the proper divisors of 6 are 1, 2 and 3, and that 6 = 1 + 2 + 3. So, the statement is true. Note: such integers are called "perfect", and there are others. 6. [10 points] Is the following statement true or false? Justify your conclusion carefully. Every integer x has a divisor y such that y < x. Soln: In order to show this statement is true, we'd need to construct a proof that held for every integer. Merely showing it's true for some integers, even a lot, would not be sufficient. However, we could show the statement is false by finding a single integer that does not have the specified property. The key is to consider negative integers. For example, 4 is a divisor of -12, but it's certainly not true that 4 < -12. 7. [10 points] Is the following statement true or false? Justify your conclusion carefully. Some prime integer is equal to the sum of its positive divisors. Soln: This is a bit harder. To show it's true, we'd just need to find a single prime integer that equalled the sum of its positive divisors, but to show it's false, we'd need to make an argument that it would be impossible for such an integer to exist. The truth should be obvious if you consider just one example. Let's consider the prime integer 71. Since it's prime, it's only positive divisors would be 1 and 71, and it's clearly not true that 71 = 1 + 71. But now it's obvious that cannot hold for any prime integer either. Suppose that p is some arbitrary prime integer. Then the positive divisors of p are 1 and p. And it's clear that p cannot equal 1 + p, since that would imply that 0 = 1. So, the statement is false.