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}

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