CSE 321 Winter 2010 Homework #1 Due Wednesday, January 13th at the start of lecture. Bring to class to turn in. Problem 1 [10 points]: Section 1.1, Exercise 10. Problem 2 [10 points]: Section 1.1, Exercise 16. Problem 3 [10 points]: Section 1.1, Exercise 20, a, c, e, g. In the next three problems you will use three distinct techniques for reasoning about Boolean functions: truth tables, logical equivalences, and formal proofs. In each problem you should use only the technique specified in that problem. Show all steps of your work. Problem 5 [10 points]: Use truth tables to prove that the following propositions are equivalent: (p --> (q --> r)) is equivalent to (p and q --> r) (p or q) --> s is equivalent to (p --> s) and (q --> s) (p --> q or r) is equivalent to (p --> q) or (p --> r) Problem 6 [30 points]: Use logical equivalences to prove the following: (p and not(q)) or (q and not(s)) or (p and not(s)) = (p and not(q)) or (q and not(s)) (p and q) or (q and s) or (p and s) = (p or q) and (p or s) and (q or s) Problem 7 [30 points]: Use natural deduction to prove the following tautologies: (p and (p --> q)) --> q (p or q) and (p or s) --> (p or (q and s)) (p --> q) --> ((s --> p) --> (s --> q)) ((p --> q) --> p) --> p For the first three problems you should use only the rules in intuitionistic logic. For the last problem you may also use the "proof-by-contradiction" rule. Extra credit [5 points]: Show that you can swap a pair of memory registers using exclusive-or without any temporary storage. To be precise, suppose that your machine has two memory registers R1 and R2 with the same number of bits. The instruction XOR1 makes the assignment R1 <-- R1 xor R2 and the instruction XOR2 makes the assignment R2 <-- R1 xor R2. Describe how you swap a pair of values and explain why your solution works.