Homework 4 Solution

CS 280 - Spring 2002

Due: Friday, March 1

Part A

  1. Let A be the set of song titles that contain the word "Me", and let B be the set of song titles that include the word "the".  Express each of the following sets as a combination of A and B.
    For this problem, there isn't a real good way to produce the over-bar in HTML, so I'll use Ac to represent the complement of A.
    1. The set of song titles that do not contain the word "Me".
      Ac
    2. The set of song titles that contain both "Me" and "the".
      A intersect B
    3. The set of song titles that contain "Me", but not "the".
      A - B
    4. The set of song titles that contain neither "Me" nor "the".
      Ac intersect Bc [which is equivalent to (A union B)c]
    5. The set of song titles that contain "Me" or "the", but not both.
      A summetricDifference B
       
  2. Problem 20, page 96 in the text.
    1. Show A = A intersect (A union B).
      Proof using a Membership Table (1 indicates "in the set" and 0 indicates "not in the set").  Because the the columns for A and for A intersect (A union B) are identical, the sets are equal.  It's also possible to prove this using set-builder notation and logical equivalence; at some point in such a proof you need a lemma showing that "p and (p or q)" is logically equivalent to "p".
      A B A union B A intersect (A union B)
      0 0 0 0
      0 1 1 0
      1 0 1 1
      1 1 1 1
    2. Show A = A union (A intersect B).
      Because the columns for A and for A union (A intersect B) are identical, the sets are equal.  
      A B A intersect B A union (A intersect B)
      0 0 0 0
      0 1 0 0
      1 0 0 1
      1 1 1 1

Part B

  1. Problem 24, page 96 in the text.
    Claim: (A-B)-C is the same set as (A-C)-B.
    Proof using set-builder notation and logical equivalence:
    (A-B)-C = {x | (x in A-B) and not (x in C) }                by def of set difference
    = {x | [(x in A) and not (x in B)] and not (x in C) }    by def of set difference
    = {x | [(x in A) and [ not (x in B) and not (x in C) ]    by associative law for     and
    = {x | [(x in A) and not (x in C)] and not (x in B) }    by commutative and associative law for     and
    = (A-C)-B                                                                    by def of set difference
    It's also possible to prove this using a Membership Table, but 8 lines are needed in the table.
     
  2. Problem 12, page 67 in the text.
    Proofs are not necessary for this problem.  There are many possible answers for each part.
    1. A function from N to N that is 1-to-1, but not onto.
      f(x) = x2
    2. A function from N to N that is onto, but not 1-to-1.
      f(x) = floor(x/2).
    3. A function from N to N that is both onto and 1-to-1, but is not the identity function.
      f(x) = x-1 if x is odd
      f(x) = x+1 if x is even
      Basically, this function just swaps adjacent even and odd numbers.
    4. A function from N to N that is neither 1-to-1 nor onto.
      f(x) = 0 if x is even
      f(x) = 1 if x is odd

Part C

  1. Problem 20, page 68 in the text.
    If f and f o g are 1-to-1, does it follow that g is 1-to-1?
    Yes.  Actually, just knowing that f o g is 1-to-1 is enough to conclude that g is 1-to-1.  Suppose that g(x)=g(y).  Then it's certainly the case that f(g(x))=f(g(y)).  Since f o g is 1-to-1, we use the definition of 1-to-1 (i.e., h is 1-to-1 means that h(x)=h(y) implies that x=y) to conclude that x=y.  We've shown that g(x)=g(y) implies that x=y, so by definition of 1-to-1, g is 1-to-1.
     
  2. Problem 30, page 55 in the text.
    Is the symDif operation associative?
    It's probably easiest to do this with a Membership Table.  Since the appropriate columns match, the symDif operation is associative.
    A B C A symDif B (A symDif B) symDif C B symDif C A symDif (B symDif C)
    0 0 0 0 0 0 0
    0 0 1 0 1 1 1
    0 1 0 1 1 1 1
    0 1 1 1 0 0 0
    1 0 0 1 1 0 1
    1 0 1 1 0 1 0
    1 1 0 0 0 1 0
    1 1 1 0 1 0 1