MATH 211 Exam 2, Fall 2007

Math 211 — Fall 2007-08 Discrete Structures Quiz 1, October 26 — Duration: 1 hour GRADES (each problem is worth 12 points): 1 2 3 4 5 6 TOTAL/72 YOUR NAME: So Lo T { ONS YOUR AUB ID#: PLEASE CIRCLE YOUR SECTION: Section 1 Section 2 Section 3 Section 4 Recitation W 4 Recitation W 11 Recitation Th 12:30 Recitation Th 3:30 Professor Makdisi © Ms. Karam Ms. Karam Ms. Karam INSTRUCTIONS: . 1. Write your NAME and AUB ID number, and circle your SECTION above. 2. Solve the problems inside the booklet. Explain your reasoning precisely and clearly tq ensure full credit. Partial solutions will receive partial credit. Each problem is worth 12 points. 3. You may use the back of each page for scratchwork OR for solutions. There are two extra blank sheets at the end, for extra scratchwork or solutions. If you need to continue a solution on another page, INDICATE CLEARLY WHERE THE GRADER SHOULD CONTINUE READING. 4. Open book and notes. $e CALCULATORS, ALLOWED. Turn OFF and put away any cell phones. ARE GOOD LUCK! 1. a) (6 pts) Show the logical equivalence pA (q -+ r) = (“pV q) > (p Ar) USING a truth table: Pog FF Quer pAQ-+r) pV pA (Ya (Ar) ToT T + [“\ T TT /t\ T T F F r\ oo F /_F T F T 7 T F T TT T F PF = F F = POT T F + E F POT FOF F x F F FOF T et / = F \ Ff FOF F.- FE F / AAne circled calvmas q nee 20 Cpr) cpa) b) (6 pts) Give a direct os (WI fou stag a truth table or other logical equiv- alence) that if pA (q-» r), then (=p V q) + (pAr). Geel paged oO We om dedee P © ond we om dedoce Veo ®. Wypetbesis: assume 7p v' ®@ Coby G2® , ble a © fee @UD, © fn-O Ot spac @ te renee in @-@ shows vs Mal Gera) — Cenc). Che dared cenclosin) ® 2 2. Let J: Z— Z be the function defined by f(n) = |]. a) (3 pts) Find the image set f({—3, 3, 6, 8, 10}). This is £E-3), £057, 800, £10), Hod} el, UL EDL [eR =F 9, oe, 3B Wg = 40,36, te} b):(5 pts) Find the inverse image set f-1({0,5}). The (new | lo) € 0.633 Yen [Elo v [k(-53 = Gner| (oe dai) vis«< & <«){ (rez |Geten) Vv (se ew <6) 3 ; = 4 ne2l Inlxve ant i {ne on bare S Pn < Cys 728 The ae Ass) memas Wl € §o.1,2,33 integer m sah = $3 -L-1,0,U2,3 c) (4 pts) Explain why f is neithér an-injection nor a surjection. £ is mk on ifeckon \ecaus, SFB be CY-3)=F)20 Coon Mar ommples fx eZ ath yp, bob UnleFory ee possible ) | g is cade g Suryeckon Loecerae Ane anynok in pat (Q abwve Shows Mab there dog at erik ay neZ fe deh [E\>5 S S Ves a geimae . Carain, Sar couslerepm sles Ht pescible .) 3. Given the sets A = {1,2,3,4}, B= {3,4,5,6}, C= {2,3,5). a) (3 pts) Find AU(B—C). BIC = §3.4,5,65-92,35% = UG (Rec etal xen a »4¢) Ao(B-C) = Gaz aioqag = U43.4,63, b) (3 pts) Is the following statement true? Explain why or why not. vee A, ByeCst.(z=yt1 Vv z=y-1). Check Re all xq “wheal tha predicate, PA) is trve, YEN dee there ith NES HOH wlley 3)? Yes, bayer x: Red, 48 / take. S=3 se weye! : ” Ke 3; yes, Anke Bee Kaye Xe yes ptake yas se weqnt Coe can dle ke 423) Since GO is Wve in ack ob Mercer ely KEL HH, HH Ke all ells ob A Mie canclole Mat YES the abe statemeb is deve, ©) (3 pts) Is the following statement true? Explain why or why not. Vz € B, Bye Ost. (2 =y 41 v z=y-1). tos : Nae Re seme, bin ty pork WY chav, O xe . be ws, =: POD btwe Sree te cor eke ye Le xe a yeu ‘\ SPO) hee ee we am Bega, Ber Sor xe ‘ 5, PG) ie FALSE sce Gee coo agpen Ge yatt -] ot ot, Rey sae ely in & yee ee muah Sak nate Hone Lal, 5 Se Ae ancuer is NO . met Co LS Chas 7 POa ty nde ales We Gr XeB, tha BE) § Rel pan vad d) (3 pts) Briefly explain why the following statement is FALSE: ) eh vf Sx kya xey ae 3r €Zst. EC, Gat v aa}). WS Abs: ca tare exuh ; mar Some Ke DL } sch: eC 2K ‘ his westh Hah schebea (40 9 yen ¥ yx Ce hut, xy BC hy 3 clmaty — clite » a Ge water obh x ts chose’) Yet, KHZ Cs a cel oth Deluah aly Ane aban chubemest is FALSE. Hee Ne hx o exisk -oaoSSee 4. Let A,B,C be sets. 5, (12 pts) Let z be an irrational number. Prove the statement a) (4 pts) Show that if AC B and AC C, then AC BNC. Gent ASB nein: Weed? xed) © ; he ete ct YOEM, (@# Oggiaz is rational). Gee Reece Vea wait tna mh adSy (O# seer esenin) preang: Wx, (ke €c) © ‘Work directly from the definition of rational numbers in terms of integers, Do NOT assume ‘ . any other properties of rational or irrational numbers. Parnes) ond age xeA We wg gue Mak x ¢Q. CO) bent eh OT ve olla that xeB : , * Real = : GrLinns Ded@, we. doleic ah xe © Me Qs Fee | Fez a (nfo nine %)S.- BaD Fy tek XE RAC ia) . a mut doe. tee Stitemarts 5 arta acQ. Ze} Shoe tet —S Te rocenin, in D~D Srous us teak . > sto a . : mat Conratichon: %,(kea—>xebac). ° @: Re oe! Gun atO,and ae Q This meme that? AG BAC 5 this is uhak we vented to pros: Seppe ce xe Q, © From © se bow Amnew Sb. no onl at%. om b) (8 pts) UNRELATED: Show that if AN B = 0 and A'C BUC; then-AC CG. Furthermare, Since ato Gee Ane g > D ; ; we haw’ mf oO” @. Goer Ko Quer, dd wees Sige xe Q jo boo We, [ xen Get vec) @ : SET sk. tho al ~% © co : WE carclole Hoot . Lak x be airway 2 assine teh yeh — @ yo * 2 GH) ECS) age din xeR y “C- °@ c * (%)~ tr Cie nae wsad do to. ater dition SiheseonpNens spn xe 8, 5 * ook eet {fn ®) ShyO~, He doh xe AaB © Were n@, ve brow QM ad Linde (oashmne 2 M+ © eantadih @ Teall on ane bat - ANS Sand nbn ay cece @ ~ LS © sae tik Ke Q, Corker dichtng Hoe ensgtul iver (©) ~~ ° . ~ “ i The pre by code didtec i ©-0 ; This ty, (B-@) shoes w fhah 2 _e © He A eR ® L? Sinlickn, ~#Q ® CNOA mn Met we w® Bmeg oO wm 1 - = Vv. Cc . The Peacoat in Ss DD dhs ue the, = che Be $Q —> ato» GME prove the anv otet\) y “ This oy ele Le bene 44 comb drclen Ch qf Gere = 6, we Uesll bane %, (xeA—> xe). © . ORs Poppe axdQ. BXH OK OC, onindiclear) Wis is the - : Since OC Q, conclode . B The sme cc sayy ter NEC o pork is awe emplebe. \ 0 Breas ato. 8x$o 4 ony either oe Ake above peck, we able, > Qo combicns HG) NAR) nee ew. et Oa 6. Let f: X “+ ¥ be a function. a) é pts) Given subsets A,B,C © X, Show that if A C BUC, then f(A) € F(@OvF¥ Cc) Que jum state Hak AS ROT, in elher wore : S Vx seek — > xe v rec), ©” ar Tha hy te bb at an aren clemerk ol LK) @ SeRRECTION; Blank sheet. Ex Cb conkinved ewes We Wek chee Hap Te : a Fete) Cee IE). eee ss elon ef T. @ Thee ‘ wie, ashe ek gurjecly, FOD= 54) Axe 5 YFG} . —— eek “te. © . ae seuss Sch 8 ley. LASER? © spiel, “ Hi Bak 35 © 8 now ribes (a>) a 4 are WR cletala yy, vw ws x He Lave cadached achat Ee Get e&v xee, @ tahoe fe £-1(T) onl y=FGD, aoy F oe Se ve have Shoton ©. Hy 4rfOo be xe QR es : me Derek cy. ye fem ee, mama : S YEA)» bea ge Fc) ° . “ ° ° a Th resent DAD shout ak Anilety Byec sh. =feq, . i “9 axe shee tos t@tce) Vy, yer yeh (emery. D te tee Ta bey : nek ) (6 pts) Set Linch ES. if fis surjective, then f(J-(7)) => : | Gos Bis srs, BE VyeY, Beek gt. yt SO. Now scombine Stotomns GE) (abs sys Ha feaye+y HE cheno PEED + wd WD GK ay thet Te £C- ery) V— w4 . t [Ree De a Lik be mabey clare t C(E“eD, © rice as By dof. ot (6 sha sean Sxe fa sh. ye FD. 3) SM KEENE, Hos mens Laer © by ek E~(asel. OO, we thin yeT © BNy ye SE) ayer © Wey pT. — AE Shee Ts CCE) Ceenkinne Lon wD)