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|?
      
      Answer: 3. There are three elements in the set {x,y,z}
      13/13 students got this correct.
      
      
      
   2. (2 pts) List all the elements of B × B as a set.
      
      
      B × B = ___{ (0,0), (0,1), (1,0), (1,1) }____________
      
      7/13 got a perfect score here.
      Common errors: not putting {} around the set
      Using {} for the ordered pairs (e.g. {0,0} instead of (0,0) )
      Forgetting one of the elements
      Listing A×B instead of B×B
      
      
      
   3. (4 pts) What is the cardinality of ℘(A ×A)?
      
      512.
      
      This is because A ×A has nine elements, and the power set of a set with nine elements has 2⁹ elements.
      7/13 got this correct. Some common wrong answers: 2³=8, 9, 18
      
      
   4. (2 pts) Let R be a relation on A, with R={ (x,y), (y,x) }. Is R reflexive? (yes or no)
      No. It is symettric, but not reflexive. 13/13 got this correct
      
      
   5. (2 pts) Let S be a relation on B, with S = { (0,1), (0,0), (1,0) }. Is S symmetric? (yes or no)
      Yes. 13/13 got this correct
      
      
   6. (2 pts) Let Q be a relation on A, with Q = { (x,y), (z,z) }. Is Q transitive? (yes or no)
      
      Yes, it is transitive.
      
      Only 6/13 got this right. A relation is transitive if whenever (a,b) and (b,c) are in the relation, (a,c) is also in the relation. This is an implication, so for it to be false, it must be the case that the first part is true, and the second part is false. There are no pairs that make the first part true, so the implication is never false, thus the relation is transitive.
      
      
   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 = ___________________________________________________________
      
      6/13 got this fully correct. 4 more had a correct answer, but forgot the {} around the list of ordered pairs, and so lost one point. Thus 10/13 understood how to construct a set with the correct elements.
      
      There are six possible correct answers. For F to be a function, both 0 and 1 must appear exactly once in the left side of one ordered pair. For F to be one to one, no element of A can appear more than once on the right side of an ordered pair. For F to be not onto, there must be at least one unused element of A. All of these answers fit those criteria.
      F={(0,x),(1,y)}
      F={(0,x),(1,z)}
      F={(0,y),(1,x)}
      F={(0,y),(1,z)}
      F={(0,z),(1,x)}
      F={(0,z),(1,y)}
      
      Wrong answers included cor
      
      
      
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.
     
     
     The results here were disappointing, and show that we clearly need more practice with proof by induction. Hence, the new homework assignment 6, and the detailed discussion on induction in class on Monday and Wednesday. (05/05, and 05/07).
     
     Here were the scores:
     
     
   • -0: perfect. (I'll scan this and post it so you can see what a good inductive proof written by a student looks like)
   • -1: almost perfect. -1 for not being careful to distinguish between P(n) and F(n).
     This a common mistake. Don't write P(n) = F(n) = 1 + 2 + ... + n.
     Write instead: P(n) is the proposition that F(n) = 1 + 2 + ... + n
     or, shorter: P(n) is that F(n) = 1 + 2 + ... + n.
     
     Why? F(n) is a function that returns an integer value. P(n) returns true or false.
     So P(n) can't be equal to F(n).
   • -6: didn't state hypothesis clearly, and made algebra mistakes in the proof
   • -6: base case should have been 0, didn't state hypothesis clearly, and proof, although valid, was not clearly presented as an inductive proof
   • -9: setup the problem perfectly (except for starting from 1 instead of 0, but the proof skidded way off course into meaningless notation
   • -9: unclear statement of the proposition, didn't have 0 as base case, confused P(n) with F(n), and proof was incomplete
   • -14: no clear statement of what was being assumed, or what was being proved, and no proof. Partial credit for a few initial attempts, including a base case for P(1)
   • -14: similar to previous description.
   • -15: similar to previous description, except even the base case was not clearly labeled as such. Could not see that an inductive proof was being attempted.
   • -16: unclear and/or false statements in statement of assumption and what was being proved. Partial credit for a base case, but the proof was a direct proof, not an inductive proof.
   • -16: unclear and/or false statements in statement of assumption and what was being proved. Partial credit for a base case. No valid proof.
   • -16: similar to previous description
   • -20: no clear statements at all.
     
     
     

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)

   There were four perfect papers here. I'll scan a couple and post them.

   Here's the full range:

   -0,-0,-0,-0,-2, -3, -4, -4, -5, -10, -10, -13, -15. This isn't what I would have hoped for, but falls within the range of reasonable responses; the median grade is an 80%, or a B.
   So we aren't going to belabor this topic, or offer any second chances. However, if you got more than 4 points off here, you should come to my office hours. Soon! We can go over your answer, and also make sure you are prepared for the final, and any upcoming quizzes.
   

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)
      
      
      The correct answers: Yes, No, Yes.
      
      11/13 got this part perfectly correct. See me if you need an explanation of any of these.
      
      
      

      ---

      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:
      
      x cannot ride a skateboard
      
      
      What you would try to show:
      
      x is not a foo
      
      9/13 got this correct. Some wrong answers:
      
      

      • show: if x can't ride a skateboard, x is a foo
      • assume: if x can't ride a skateboard then x is not a foo (that's what you are trying to prove, not the assumption)
      • assume: x is not a foo. show x cant ride a skateboard
      • assume x can't ride a skateboard implies that x is not a foo (that's the full statement you are trying to prove, not the assumption.) show: that for all x that can't ride a skateboard, x is not a foo (that's ok as a full statement of what you are trying to prove, but I asked you to break it up).
        
        
        
   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.
      
      Either modus tollens: (p → q ∧ ¬q) ⇒ ¬ p,
      or p→q ≡ ¬q→¬ p
      
      12/13 got this correct. Only wrong answer: p and not p (which is a contradiction, not the justification for the contrapositive.)
      
      
   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:
      
      x is a foo and x cannot ride a skateboard (i.e. p and not q)
      
      What you would try to show:
      
      any contradiction
      
      Only 5/13 got this perfectly right, so we need more practice on proof by contradiction.
      
      Some wrong answers:
      * assume x isn't a foo, show if x isn't a foo, x can't ride a skateboard
      * assume if x isn't a foo it can ride a skateboard, show a contradiction
      * assume x is not a foo, show it can ride a skateboard
      * assume x is a foo implies x can ride a skateboard, show x is a foo implies x cannot ride a skateboard
      * assume if x is not a foo than x can ride a skateboard. show not p implies q
      * assume that x is not a foo, show thatn x can ride a skateboard
      * assume if x is not a foo, show that x cannot ride a skateboard
      * assume if x is not a foo, then x cannot ride a skateboard. show x cannot ride a skateboard implies x is not a foo.
      
      

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 ↔ ___________________________________________
      
      There are two possible answers: ∀x(x ∈ A → x ∈ B) ∧ A ≠ B or
      ∀x(x ∈ A → x ∈ B) ∧ ∃ x (x ∉A ∧ x ∈ B)
      
      This was suprisingly hard. only 6/13 got it right. Wrong answers varied widely, but looked like wild guessing.
      
      
   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	F	F	T	F	T
      T	F	F	T	F	F	F	T
      F	T	T	F	T	T	T	F
      F	F	T	F	T	F	F	T

      
      13/13 got this right (except one person got -1 for what was presumably a careless mistake in one single entry in the table.)
      
      
   2. (2 pts) So, on the basis of your truth table above:
      
      Is ¬(p→q) ≡ ¬(¬p ∧ q) a tautology? (yes or no) NO
      
      13/13 got this right.

End of Exam

Total points: ?