Question 0.  (1 point)

First, set up all the tools required for this class. make sure you are enrolled in the Piazza site for this class.  Confirm you have access to this class via Gradescope https://gradescope.com/ using your ucsd.edu email address. Make sure you are enrolled in the canvas site. This will be the main website for the class.

Make sure you complete the Canvas assignment:

First Day Survey: Prior Knowledge #FinAid

This is important for the university to determine the commencement of academic work for each student in the class for the purposes of Financial Aid. Please fill it out.

Question 1.  (15 points) Let A = {aa, bb, ab}, B = {a, b}, C = {ab, abab, ababab}.  For each set, write out each of its elements.

a.  (A u B u C)

Solution:

{aa, bb, ab, a, b, ab, abab, ababab}

b.  (A n C) × (B u C)

Solution:

{(ab, a), (ab, b), (ab, ab), (ab, abab), (ab, ababab)}

c.  A o C

Solution:

{aaab, aaabab, aaababab, bbab, bbabab, bbababab, abababab} d. p(C) (the power set of C)

Solution:

{0, {ab}, {abab}, {ababab}, {ab, abab}, {ab, ababab}, {abab, ababab}, {ab, abab, ababab}}

e.  (B o B) × B

Solution:

{(aa, a), (ab, a), (ba, a), (bb, a), (aa, b), (ab, b), (ba, b), (bb, b)}

Question 2.  (14 points) True/False State whether each statement is true or false and justify with one or two sentences.  For example, if the statement is true and follows from definition(s), write out the relevant definitions and explain how they apply.

a.  A u B = A n B

Solution: True, this is called DeMorgan’s law.

b.  There exists a finite set A that has the same number of elements as its own power set p(A). Solution:  False, it can be shown that if A is finite and |A| = n, then |p(A)| = 2n  and n < 2n  for all integers n.

c.  {0} u {0, 1} = {0, 1}.

Solution: False: the correct set would be:  {0, 0, 1}.

d.  0 e {0, 1}

Solution: False, the only elements of {0, 1} are 0 and 1, not the empty set.

e.  {0, 1} n {00, 11} = {0}

Solution: False, the correct set should be 0.

f.  0 C {0, 1}.

Solution: True, the empty set is a subset of any set.

g.  0 is a language.

Solution:  True, the empty set can be considered to be the empty set of strings and so it is a set of strings.

Question 3.  (23 points) CSE 105 is a fairly proof heavy class. The goal of this problem is to help refresh your memory on different proof techniques: proof by induction, closure proofs and set equality proofs.

For each part of this question, complete the proofs by filling in the blanks.

Note:  there  may  be  alternate  correct proofs  to  each  of these  claims .   The point  of this  question  is  to practice certain proof strategies .

a.  (6 points)

Definition: The reverse of a string u, denoted uR , is defined recursively as follows:

(1) εR  = ε (Note that ε is the empty string.)

(2)  For any character a, and any string w, then (wa)R  = awR .

This definition, in words, is on page  14 .

Claim:  (uv)R  = vR uR  for any strings u and v .

Proof: By structural induction on v .

Base case: v = ε . Let u be any string.

(uε)R  =   uR  = εuR     = εR uR

Induction step:  Let v be an arbitrary string.  Assume that for all strings u, (uv)R  = vR uR . We need to show that, for each character a and all strings u, (u va)R  = (va)R uR .

By the recursive definition of reverse:  (u va)R  =  a(uv)R  .

By the inductive hypothesis:  (uv)R  =  vR uR  .

Also, by the recursive definition of reverse:  (va)R  =  avR  .

Thus,

(u va)R      ()       a(uv)R

()        a /vR uR、= (avR )uR

()      (va)R uR .                 □

b.  Prove that if A C R is closed under multiplication and B C R is closed under multiplication then

A n B is closed under multiplication and A n B is not necessarily closed under multiplication.

A n B is closed under multiplication.

Let x, y be elements of A n B .  (Show that xy e A n B .

Solution:

Suppose that x, y are elements of A n B . Then xy is an element of A because A is closed under multiplication.  xy is an element of B because B is closed under multiplication.  So since xy is an element of both A and B , xy is an element of A n B .