Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

68 FUNCTIONS AND ALGORITHMS [CHAP. 3

CARDINAL NUMBERS

3.43. Find the cardinal number of each set: (a){x|xis a letter in “BASEBALL”};

(b) Power set ofA={a, b, c, d, e}; (c){x|x^2 = 9 , 2 x= 8 }.

3.44. Find the cardinal number of:

(a) all functions fromA={a, b, c, d}intoB={ 1 , 2 , 3 , 4 , 5 };

(b) all functions fromPintoQwhere|P|=rand|Q|=s;

(c) all relations onA={a, b, c, d};

(d) all relations onPwhere|P|=r.

3.45. Prove:

(a) Every infinite setAcontains a denumerable subsetD.

(b) Each subset of a denumerable set is finite or denumerable.

(c) IfAandBare denumerable, thenA×Bis denumerable.

(e) The setQof rational numbers is denumerable.

3.46. Prove: (a)|A×B|=|B×A|; (b) IfA⊆Bthen|A|≤|B|; (c) If|A|=|B|thenP(A)|=|P(B)|.

SPECIAL FUNCTIONS

3.47. Find:(a) 13. 2 ,− 0. 17 , 34 ;(b) 13. 2 ,− 0. 17 , 34 .

3.48. Find:

(a) 29(mod 6); (c) 5(mod 12); (e)− 555 (mod 11).

(b) 200(mod 20); (d)− 347 (mod 6);

3.49. Find: (a) 3!+ 4 !; (b) 3!( 3 !+ 2 !); (c) 6!/ 5 !; (d) 30!/ 28 !.

3.50. Evaluate: (a) log 2 16; (b) log 3 27; (c) log 100 .01.

MISCELLANEOUS PROBLEMS

3.51. Letnbe an integer. FindL(25) and describe what the functionLdoes whereLis defined by:

L(n)=

{

0ifn= 1

L(n/ 2 )+1ifn> 1

3.52. Letaandbbe integers. FindQ( 2 , 7 ),Q( 5 , 3 ), andQ( 15 , 2 ), whereQ(a, b)is defined by:

Q(a, b)=

{

5ifa<b

Q(a−b, b+ 2 )+a ifa≥b

3.53. Prove: The setPof all polynomialsp(x)=a 0 +a 1 x+···+amxwith integral coefficients (that is, wherea 0 ,a 1 ,...,am

are integers) is denumerable.

Answers to Supplementary Problems

3.27. (a) Yes; (b) No; (c) Yes; (d) No.

3.28. (a){( 1 , 1 ), ( 2 , 4 ), ( 3 , 3 ), ( 4 , 3 )};

(b){( 1 , 1 ), ( 2 , 2 ), ( 3 , 1 ), ( 4 , 1 )};

(c){( 1 , 4 ), ( 2 , 3 ), ( 3 , 3 ), ( 4 , 4 )}.

3.29. {(a, 4 ), (b, 6 ), (c, 4 )}

3.30. (a) No, (b) yes, (c) no, (d) yes.

3.31. (a)f, h; (b)f, h; (c)f, h; (d)g.

3.32. (a)f, g; (b)h; (c) none; (d) none; (e) {all prime

numbers}.

3.33. (a)g, k; (b)f, g, h; (c)g; (d) none.