MATH 211 Exam 1 With Solution, Spring 2013

MATH 211 SPRING 2013 TEST I VERSION A NAME: K 5a na SECTION: \ x " (1) True/False Questions: Here A,B etc. denote sets while z,y,--- denote i elements, and P(A) denotes the power set of a set A. en (t)F 6¢ {x,y} v (B) {2} = {{z},{2}} (r) F_ The proposition (-p = Q- (q — p) is not a contradiction. ae + ‘ Ti(e) {9} foul) Pte). ay @®) (AN B)U(ANB) =U. } F_ Given f : A— B, S and T are subsets of A we have — ye ; . 5 7 Y. )u sp). . \3 T (&) |P({a,b,c})] = 3°. \ Bn; A ={9, hl (9) ey 9, \o, \ \ok 2. Oy \3 16,-- T 3) For i = 1,2,..let the set Ay = {7+ i,74 2i,7+3,..}. Then 03> =149,'3, the set ()72, Ai has an infinite cardinality. b Peg & tM, Is 19-5 ; hs = Zitat, 20)... F f:N—N where f(n) =n? +7 is one-to-one but not onto. : ; £ @) Given two sets A and B, A can either be an element of B or a subset of B but not both. (x) F The set Z x Z is countable. By @) It is possible to find two countably infinite sets A and B such that AU B is uncountable. (2) Show that the proposition p — (—p — p) is a tautology using D., ots, (a) A truth table } 9g “P| => F | poy 7 rl TT Fit | * ¥ 2 yrs ‘ (b) logical equivalences, naming all rules of inference that you use = avin) s apvlnypy y) ute wsgehion chim : exanpba ney vary) eof eat Ojo bare gins. our cn (3) Find a function f from N to N that is neither one to one nor onto. (2 ts ) beh: F as not 1-42 beth Co) & FC) ore L. buk 6 bd . (Let): Fis not ont . 2. 43 not on | MASA (4) Simplify the proposition (p @ g) © p as much as possible. (3 i ts ) See ea ahae™ , Pro 4 = (94 Pall rate a(apy (4) pe4) “(env Capeav9) a Gre(gedvbons) derrery | 2 (began roped) vg) a (Gpyeyn svt eae) Ag by absrption y c ass eCShve 5 f ¢ (7) Consider a geometric sequence with a = 3 and r = 2. Find a7 +--+ + ay4 Ne (by applying the formula). ? Agar ty = (A+ 1 Bu) - (age +46) IC \S = [rx ral al Oo Fal Z~\-2' +1) iz r- 7 4 ( 2” at) ; (3) (8) Consider the premises: “Every computer science major takes discrete math- ematics”. “If a student takes discrete mathematics then he receives an ks overall semester average above 72”. “Salwa scored an average below 72”. fl Show that the statement: “Salwa is not a computer science major” is a valid conclusion. Make sure you define appropriate predicates and indicate A; the names of all rules of inference you use in your proof. OMowr + all s adie Code Mm is a CS, major Di: “% the disorete A (x) x PECLEA AW eye 42 . ae (Cc) > DM) " qr < 2. Vx(D~M— Ao) at war; Me @ CCsalwa)—s Daly wa) “gtek Acsal |wa) unt. iat &@ // i yn \ SX yr 2, OS yy a (8 => of a en REL > | Q2 i, ee _ x 129) ra » NY 2 € » J = S \e (5) Does there exist two irrational numbers z and y such that zy is rational? Justify your answer. 2 Yes. we Kaw Mat Va ats Arrahoned se Uk xaVi & 4 oie, Ae vy = Vr.V2=2 whichis rama! S> (6) Prove that an integer n is odd if and only if n? + 11 is even. or qa yn be addi. oe VS ZK+ \ Sor seme WK \ iateger es ag 1 A = (aK+\) MN afi o ie Seah & p(rKt42k+6) @ atl with es eViw . Comunsely we nerd ti shew Yok a Y\ \S odd WO USE wra\\ 25 even O conbvauposi Hive a gumninsd # ~y pe WAS a odd aioe Ww every SE n=LK Jor Some Late i. EA Gollaws Ahaf nba e AKT eM = n(rxr4 5) +h. Here wai is not even 6 9) Find a function f from Z to N that is one to one but not onto. tes ys Nok ont + oO vs nit am cS on { 220 image of ame onbee mn ZB, ve = oe 5@) 7 ~ Sayre wevis Wa ogo cf =z Caz bh! Z cosy -22i| =0 eside Sina. ~2% >0 Se -224\| Do. fae 5 &> Dp O82. 250 Ly §C2)=22 =0 + beh fiskch: Wt Ie\=fe.). sf 25 21 Shier Geos Gal Gan Se geo 2tr >. Cased: bath veges; en 9 HaMAK « Gre bt ZB Q0, BX<o S a2, = +2415 Ue Br) = Las Ais even 9, One: By <0, 3 2ersmiler te Coed. “—» (10) Translate the following to logical notation: "Exactly two cats on campus (3) h, gave birth this season”. (define your predicates, state your domain and use " quantifiers as appropriate) Deman ! cabs ov" oe an C ( x) = c- hil isa tn Wesseason” ‘be an3ul(@.+% 5 Cy) nC) | A "Ors ectz —> (@)=%) V% =) [other ways are poss ble a