From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Fri Jan 18 10:41:50 2008 Date: Fri, 18 Jan 2008 10:41:18 -0500 From: "William J. Rapaport" Subject: Hint on HW #1 To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: Hint on HW #1 ------------------------------------------------------------------------ A few of you who don't have recitation before HW #1 is due have asked me for help on HW #1, problem 10f (p. 17). I strongly suggest that you first try to do problems 9 and 11, the answers to which are at the end of the book (pages S-1 and following). These answers are fully worked out in the Student Solutions Guide (and possibly also on the book's website, though I haven't had a chance to check that out yet). But, in any case, here's another hint: The sentence for 10f is this: "You will get an A in this class if and only if you either do every exercise in this book or you get an A on the final." First, figure out what the atomic propositions are. To get you started, one of them is "You will get an A in this class." Second, assign letters to each of them; e.g., you could call that one "p". [Optional: Then rewrite the sentence with the atomic letters, something like this: "p if and only if you either..."] Third, replace the "logical terms", like "if and only if", "either...or", etc., with their symbols (<->, v, etc.). However, in this step, you need to be careful about the different ways of saying things in English, as I discussed in lecture. Again, try exercises 9 and 11 first, and then do 10f. From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Fri Jan 25 08:40:16 2008 Date: Fri, 25 Jan 2008 08:35:59 -0500 From: "William J. Rapaport" Subject: The Barber Paradox (Rosen, 1.1, prob. 44) To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: The Barber Paradox (Rosen, 1.1, prob. 44) ------------------------------------------------------------------------ I understand that several of you had questions about HW #1, problem 44, about the barber who shaves all & only those who don't shave themselves. The problem as stated in the book is perhaps not as clear as it should be. Here's another version: Consider a barber, who lives in the village, shaves all those people who live in the village who don't shave themselves, and he shaves only those people who live in the village who don't shave themselves. Can such a barber exist? Suppose such a barber exists. Then (I) either he shaves himself or else ("+", i.e., XOR) (II) he does not shave himself. (This is an exclusive disjunction: He can't both shave himself and not shave himself.) Case I: Suppose the barber shaves himself. But he shaves only villagers who don't shave themselves. That's a contradiction. Therefore, our supposition is wrong. Therefore, he does not shave himself. Case II. We have just concluded that the barber does not shave himself. But he shaves all villagers who don't shave themselves! Another contradiction. Conclusion: Such a barber cannot exist. Another version of this considers a book that is a catalog of all book catalogs that do not list themselves. By similar reasoning, no such catalog can exist. By the way, there is, in SEL, a catalog of catalogs! It **does** list itself! The most important version of this is the set of all sets that do not contain themselves as members. No such set can exist. This is called "Russell's paradox", because it was discovered by Bertrand Russell. For more information, do a Google search on "barber paradox", or see: Wikipedia contributors, "Barber paradox," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Barber_paradox&oldid=186398870 (accessed January 25, 2008). http://mathworld.wolfram.com/BarberParadox.html