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.