From rapaport@cse.Buffalo.EDU Wed Feb 20 19:19:37 2008 Date: Wed, 20 Feb 2008 19:19:37 -0500 (EST) From: "William J. Rapaport" To: korourke@buffalo.edu, rapaport@cse.Buffalo.EDU Subject: Re: Homework 5 Cc: cse191-sp08-list@listserv.buffalo.edu A student writes: | | I'm have an little difficulty with number 16, any suggestions? In 16, you are asked to show that if m,n are integers and if mn (i.e., m*n) is even, then m is even or n is even. I suggested that you try Proof by Contraposition. That strategy requires you to prove Even(mn) -> Even(m) v Even (n) indirectly, by proving its contrapositive instead, namely: -(Even(m) v Even (n)) -> -Even(mn) You can do that directly by assuming the antecedent: -(Even(m) v Even (n)) and trying to show the consequent: -Even(mn) The next step is to rewrite both of these in a more usable form. I can't say too much more without giving away the answer, but here are some ideas: * Use DeMorgan's Law on the antecedent. * Rewrite the predicate "-Even" as the predicate "Odd". * Use the definition of "Odd" that I gave you in problem 6. * Don't forget that you can also use the theorem you were supposed to prove in problem 6 as a lemma (whether or not you succeeded in proving it :-) From rapaport@cse.Buffalo.EDU Wed Feb 20 19:24:27 2008 Date: Wed, 20 Feb 2008 19:24:27 -0500 (EST) From: "William J. Rapaport" To: ajclark3@buffalo.edu, rapaport@cse.Buffalo.EDU Subject: Re: Help with proofs Cc: cse191-sp08-list@listserv.buffalo.edu A student writes: | ...I have read 1.6 multiple times, went through | my notes, and I am still oblivious on how to construct proofs. Something as simple as the first homework problem is giving me | trouble. The first problem is this: Show that the product of two odd numbers is odd. First, let's rewrite it logically: Show AxAy[Odd(x) ^ Odd(y) -> Odd(xy)]. To do that, choose two arbitrary numbers, call them m and n, and show that: Odd(m) ^ Odd(n) -> Odd(mn). To do that, try a direct proof: Assume the antecedent: Odd(m) ^ Odd(n) and try to show the consequent: Odd(mn). Next, you need to try to rewrite these in a more usable form. As in my previous hint, I can't say too much without giving away the answer, but try rewriting the antecedent using the definition of "Odd", and then computing mn (i.e., m*n) using m and n rewritten in terms of the definition. From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Sun Feb 24 08:42:23 2008 Date: Sun, 24 Feb 2008 08:41:51 -0500 From: "William J. Rapaport" Subject: 191: HW #5 Answers Posted To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: 191: HW #5 Answers Posted ------------------------------------------------------------------------ The answers to HW #5 have been posted at http://www.cse.buffalo.edu/~rapaport/191/S08/hw.html From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Mon Feb 25 11:51:10 2008 Date: Mon, 25 Feb 2008 11:50:17 -0500 From: "William J. Rapaport" Subject: 191: A careless error in HW #5 To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: 191: A careless error in HW #5 ------------------------------------------------------------------------ In HW #5, several of you said things like this: If m is even, then m=2k+1. If n is even, then n=2k+1. That's not correct. That would mean that m=n! But surely not all even numbers are equal. Some of you realized this (perhaps inadvertently) and instead you said: If m is even, then m=2k+1, for some k. (1) If n is even, then n=2k+1, for some k. (2) That's OK, because the "for some k" is an existential quantifier, so, what you really said, in the language of FOPL, is: If m is even, then Ek[m=2k+1] If n is even, then Ek[n=2k+1] And, as you should know from both 191 and from your knowledge of programming, as long as the variable is bound (i.e., declared), then you can use the same variable in different propositions (i.e., in different procedures). But there's a "caveat", i.e., a warning: When you **instantiate** the variable (i.e., when you bind it to a constant, or give it a value), you have to instantiate them to **different** arbitrary constants (this is the rule of existential instantiation)! So, from (1) and (2) above, you **cannot** infer: Let m=2k+1 Let n=2k+1 Therefore, m*n = (2k+1)*(2k+1) = 4k^2 + 4k + 1 because that implies that m=n (because you said that they both = 2k+1)! What you **can** say, however, is: Let m = 2k_1 + 1 (I can't type this very well; I mean 2 * k_sub_1 + 1) Let n = 2k_2 + 1 (i.e., 2 * k_sub_2 + 1) Therefore, etc. To make this a bit easier on all of us, let me use entirely different arbitrary constants. You can say: Let m = 2k+1 Let n = 2j+1 Therefore, m*n = (2k+1)(2j+1) = 4kj + 2k + 2j + 1