Solution Set of Homework Assignment 2

Section 1.4

2. a) {x | x is an nonnegative integer which is a multiple of 3 and is less than or equal to 12}

b) {x | x is an integer which |x| <= 3 }

c) {x | x is a letter which is between l and q alphabetically}

8. If B contains A itself and all the elements of A, then A B and A B.

e.g.) A= and B={ }

18. A or B is .

Section 1.5

4. a) A B=B={a, b, c, d, e, f, g, h}

b) A B=A={a, b, c, d, e}

c) A-B=

d) B-A={f, g, h}

8. A=(A-B) (A B)={1,3,5,6,7,8,9}

B=(B-A) (A B)={2,3,6,9,10}


Additional Problems

1) Suppose that f(x) is not one-to-one. Then there exist x1,x2 s.t. x1 x2 and for x1,x2 f(x1)= f(x2).

This is a contradiction to the fact that f is strictly increasing function. Hence f(x) is one-to-one.

2) i) First we show that if C A then (A B) C = A (B C).

(A B) C

=(A C) (B C) by Distributive law

=A (B C) from C A

Thus if C A then (A B) C = A (B C).

ii) And we should show that if (A B) C = A (B C) then C A.

(A B) C = A (B C)= (A B) (A C) = ((A B) A) ((A B) C)

That is, (A B) C =((A B) A) ((A B) C)

\ (A B) C (A B) A.

We know that C (A B) C and that (A B) A=A.

Hence C A. Thus if (A B) C = A (B C) then C A.

From i) and ii) (A B) C = A (B C) if and only if C A.

3) A path from start cell to goal cell is a sequence of up-moves and right-moves and diagonal moves.

The maximum length of the path is 14, when no diagonal move is chosen and whenever a diagonal move

is chosen, one up-move and one right-move is deleted. The order among up-moves or among right-

moves or among diagonal moves doesn’t matter. Thus the total number of different paths is