CSE321 Midterm No. 1 October25, 1995

All questions count equally. Answer each question in the space provided.

1. Without using a truth table, prove that the following two compound propositions are logically equivalent.Give a brief explanation of each step in your proof.
   • 
   • 
2. In the following expressions each variable ranges over the nonnegative integers. Which of the expressions are tautologies? (No explanation required)
   1. )
   2. 
   3. 
   4. 
3. We define the Fibonacci sequence by the rule that , , and every further term is the sum of the preceding two. Thus the sequence begins . Let z be the number ; z has the property that . Prove that, for all positive integers n, .
4. Consider the following functions of n:

   
   is equal to n when n is odd, and to when n is even
   is equal to n when , and to when n > 100.

   For each distinct pair, state whether is (no explanation required)

• About this document ...