Computer Science 280: Homework 10

Homework 10:
4/16/08 (due 4/23/08) Read 7.1-7.6 (7.5 is not on the final). Hand in all the following problems. Don't forget to explain your reasoning in all these problems.

Section     Number                Points        Comments
7.2         3                     4             DAM2, 7.2, 3
            10(e),(f),(h),(i),(k) 5             DAM2, 7.2, 7(e),(f),(h),(i),(k)
            12(a),(e),(k),(l)     4             DAM2, 7.2, 9(a),(e),(k),(l)
7.3.        4(b)                  4             DAM2, 7.2, 29(b)
            5(d)                  4             DAM2, 7.2, 30(h) 
7.4 	    4 		          5             DAM2, 7.4, 4
            7(b),(c) 	          10            DAM2, 7.4, 7(b),(c)
7.6 	    2(b) 		  2             DAM2, 7.6, 2(b)
	    6(e),(f) 	          4  	        DAM2, 7.6, 4(e),(f). If it's true, explain why;
		 		 	        if it's false, give a counterexample.
	    7(b),(c),(e), 	  6             DAM2, 7.6, 5(b),(c),(e)
	    10(c),(e),(f) 	  6             DAM2, 7.6, 7(c),(e),(f)
            27(b),(c),(e) 	  3             DAM2, 7.6, 9(b),(c),(e)


Finally, here's one more problem to think about (but not to hand in): You are kidnapped by a gang of logic-fiends and placed in a room with two doors. The leader tells you that the red door leads to freedom and the green door to death, but you can't see the colors. He also tells you that you may ask his assistant one Yes-No question and that his assistant took CS280, so understands logic perfectly, but either is always truthful or is a complete liar. What question should you ask? (Hint: There are only two primitive propositions: which door leads to freedom and whether the assistant lies or tells the truth. Let's say that you want an answer of Yes to your question to mean to take the red door. For all the possible pairs of values for the propositions, figure out what the truth answer to your question would have to be. From this result, you can construct the question.)

Isn't logic wonderful ...