CS40 Midterm Exam
E01, 08S, Phill Conrad, UC Santa Barbara
05/02/2008

Name: __________________________________________________________

Umail Address: __________________________@ umail.ucsb.edu

Please write your name only on this page. That allows me to grade your exams without knowing whose exam I am grading.

This exam is closed book, closed notes, closed mouth, cell phone off,
except for:

• You are permitted one index card (max size 4x6) on which to write notes
• These cards will be collected with the exam, and might not be returned
• Please write your name on your note card.

There are 100 points worth of questions on the exam, and you have 50 minutes to complete the exam.

A hint for allocating your time:

• if a question is worth 10 points, spend no more than 5 minutes on it
• if a question is worth 20 points, spend no more than 10 minutes on it
• if a question is worth 40 points, spend no more than 20 minutes on it
• etc.

1. Let A = {x,y,z}, B = {0,1}
   
   
   1. (2 pts) What is |A|?
      
      
      
   2. (2 pts) List all the elements of B × B as a set.
      
      
      B × B = __________________________________________
      
      
      
   3. (4 pts) What is the cardinality of ℘(A ×A)?
      
      
      
      
   4. (2 pts) Let R be a relation on A, with R={ (x,y), (y,x) }. Is R reflexive? (yes or no)
      
      
      
      
   5. (2 pts) Let S be a relation on B, with S = { (0,1), (0,0), (1,0) }. Is S symmetric? (yes or no)
      
      
      
      
   6. (2 pts) Let Q be a relation on A, with Q = { (x,y), (z,z) }. Is Q transitive? (yes or no)
      
      
      
      
   7. (4 pts) Fill in the blank by listing a set of ordered pairs for a function F: B→A
      is one-to-one but is not onto.
      
      List them as a set of ordered pairs.
      
      F = ___________________________________________________________
      
      
      
      
2. Consider this function definition
   
   
   
   Use proof by induction to prove that the value of this function is as follows for all values of n≥0
   (You must use proof by induction to get full credit for the problem)
   
   
   As a reminder, there are three required parts of an inductive proof:
   • (5 pts) define a predicate P(n),
   • (5 pts) prove a base case,
   • (10 pts) prove an inductive step.

3. (20 pts) Euclid's algorithm for finding the gcd of two integers is based, in part, on this lemma:

   If a and b are integers with a > b, and we divide b into a giving: a = bq + r then if some integer divides both a and b, it must divide r also.

   Prove this. Start by clearly stating what you are given, and what you are proving.
   

   As a reminder, the definition of x divides y, written x | y is as follows:

   When x and y are both integers, x≠0, x | y ↔ (∃k ∈ Z)(y=kx)

4. Again, as a reminder here is the definition of x divides y, written x | y:

   When x and y are both integers, x≠0, x | y ↔ (∃k ∈ Z)(y=kx)

   Thus, divides is a binary relation on Z, the set of all integers.

    

   1. (2 pts) Is the divides relation reflexive? (yes or no)
      
      
   2. (2 pts) Is the divides relation symmetric? (yes or no)
      
      
   3. (2 pts) Is the divides relation transitive? (yes or no)
      
      
      

      ---

      Use this for scratch work, or to continue your answer from #4
      
      

5. Consider the following silly statement:

   If x is a foo, then x can ride a skateboard.

   
   
   1. (6 pts) Suppose you were going to use "proof by contrapositive" to prove this statement.
      Describe what you would assume and what you would try to show.
      
      (That's all you have to do—I'm not asking for a full proof)
      
      What you would assume:
      
      
      
      What you would try to show:
      
      
      
      
   2. (4 pts) What is the tautology from propositional logic that justifies the use of "proof by contrapositive" as a proof technique? State it in terms of p and q.
      
      
      
      
      
   3. (6 pts) Suppose you were going to prove the statement by contradiction.
      Describe what you would assume, and what you would try to show.
      
      (That's all you have to do—I'm not asking for a full proof)
      
      What you would assume:
      
      
      
      What you would try to show:
      
      
      

6. Consider these definitions:

   defn of subset: A ⊆B ↔ ∀x(x ∈ A →x ∈ B) defn of union: x ∈ A∪B ↔ (x ∈ A ∨ x ∈ B)

   Come up with similar definitions for each of these by filling in the blank:
   
   
   

   1. (4 pts) , proper subset, A ⊆B ↔ ___________________________________________
      
      
      
      
      
      
   2. (4 pts) set difference: x ∈ A-B ↔_______________________________________
      
      
      
      
      
7. We may ask whether ¬(p→q) is the same as ¬(¬p ∧ q)
   
   
   1. (10 pts) To investigate this question, first complete the truth table below:
      
      

      p	q	p→q	¬ (p→q)	¬ p	q	(¬p ∧ q)	¬(¬p ∧ q)
      T	T				T
      T	F				F
      F	T				T
      F	F				F

      
      
      
      
   2. (2 pts) So, on the basis of your truth table above:
      
      Is ¬(p→q) ≡ ¬(¬p ∧ q) a tautology? (yes or no)

End of Exam

Total points: ?