Scribd
Upload
63 views59 pages

Maths Sem 3 Unit 1

Maths

Uploaded by

ch.akash1203
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
63 views59 pages

Maths Sem 3 Unit 1

Maths

Uploaded by

ch.akash1203
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 59
we LEcrv pE=2 & r : poe 18 pap Discrere ‘ | (vacate, ; ait Vea ea a ps MATH EMATI om] [_] buetr bhe set-in Ck BO OUI ee a eee AS RCC Od ge 2, >| BLUR TT oF G= DUCE ke tina 7 S557 3S C= Sot of DR DGD i C= LE q SUS Re Ua et D=Lw: ve Say of Gndia fF 4 (onside te seb B=T1 3 St cp toto WI Pe b> _ TRE ws EB + -FASE WORLLS SYSBR THE \Z) (2) {DLT 4s} eB FALIE TEL oyysyy SE Tey IL TyOR TWE 1 1 a Uke Ta Powe mak OPEL OLS Rus OA EE TST sy a + TT Rat gs tasy yey Ua ty Toe TAT, a TE aA - LECTURE -2 Re DSceerE fai a MATHEMATICS 4 [oare LJ pall OPEPATIONS. of Seas) > omen > RUB = RUE Sa Ea See a =e Wh, 3S, 47 Ee a0 TMTERSeGipp > kAB ={ 4. GA ond GEBS RnB = Ha} a> COMPLIMENT OF A SET > Ao oO BO ak DFFERENCE > Ah-B BA uw ES) SYP METRIC DIFFERENCE > FOB = B0B)— TAB) # | Some Ofna tons .— [Pow Let > Sat of oD Bar Subsets pf oO dek Diy pie Akt ~> ANB= Fenty of Sats > Se¥ vf a ata We ae # | ACGEBPA OF SETS > - Taal 3 ; KUU =U 77 FUBHR BNVER TANG HB Te > BUREK ee KAREN EWvoLUHOW> (AT)E = A 1 7 Ta Pegons tar > (RUBY = RAB Tomwmutshve Tan > RVB=BUA | RaB= BAA 3 ame Mombasa ew > KUCBAL) =(huad UT) Ka (Bucy = BUEN Oo Lom yin La 7 Ky Rc UY ANA =® ung yy zt ] Walt Ake Act th tatelbta, rour - | = Tee ee ~ pecs met im ot arr er ited éF td Ewe peaternsit MATTE {Ur , Dis { 7 aie itis por suf — At Dual EF ch an Wuabon E [2X3 UL EAC Top aOR Od omen Ole U od Pwo an Equolun Eee by neflocng wel ocean Of UNL ALN 0 Vo _ GPUS ; 4 YAMPLE] > Ed Wa al Ga os GAR BURR RAE) VIN BUAT)~ 8 UD) UA My HUY Wena op sb > v malo. wae murnOr ef UMrdur Mou ee Do a OL odor le oP c Inpe Q= Pua > wl far > €lLLoy) 23 Bh eee ate UM ae ay paca) i Ue We Zt 3u.68} (owe) = {ps7 ry O = EEF a CM = PPE () | G/B = g att @) | KA B/C= RDG {LO Spe Tuy (@)] (78) “=e, Sane S| poy = to = gp ae 3 pL vas bl lope © fa by CGh w ate aes Prove qhat .> (we) AP XR) = -nnp)e (ero) eave] 1) lee] TT) Vet DUG) & TAXB nL Px ey : = LEA SYERY LEP LED SER OLETT CELE Sear) & Fe ne aL) © Chay x BA ay aC Hom Prev 2 ey) CEN KE YoRA Q WeP 7 7 “KE Ra wd TERA T LER THE? ad GER od FOO WER 4 EB WEP, FeO OAIE AX B one Wa) Eex D> WOH) EB nl Px 8) oe Your Prod a EX(BIT) ARB NE 2) UL Prove SSI Ax CBUC) = &XB) ULAKT) Tae Ut | See OB meal WXC oe Ext: ) 5 >] SGT ak Os BL Chou Hhak Say and Te S hau mM Ro ends Dn COMMON | Bp | VRETOY OF SETS tr ur OO RPO SAE ry of Ser STF 0 EpcEr on of Ly oF ae [op wats of eet T anc ba Guy Ty Ryan EL Fi Ay OU LES ee cea Ob Ui iy eg tor yb en {B53 B1_ By~- By, L Onn ar jo tuerors ob atk 5 Buu the gue PF HLTAL AR cates MG ae ga ml ty cotled Mer tres Ake Oh Lek Ke Tew jade Blue, OS ¥_ Pot (ero, Bion} GT Pe Ve =p BuL Re, 2 Ove0K} ae Pa =AT ea CaF A BIE, 2anten FF fF a eee aa : AMfo3/4 DISCRETE. rest = ee NATH S ee Ls MONDAY) LEcTUFE—' » a tWouabste’ a Denial o Tk ae Fact we U sald bo be unable Daye, ont ont and onde Puibue eT ey Ee 4 Twas db > FAG xy aad Uncourtablt gab > Fac whoo wok kevrtabt iy laa T “Peep Bop MO sp A SOUS PE EL ae TPR Ler R IS 0 COWETA QE Wet L289 AQ anki ep RERS | Ted FT poner DRGLE CH Tod Eup A ep Pen a PLT tne > SD ative, = Big coomtabie 7 1s GRIST LE REE => BO aworRtie Qs Tp A EK A=Ta aay af avieB PF aka €B7 I (tr =abky, bie ak. yj Bek BOA SS (bibs TER qT BY Erumrodte B09 teuudaule Sree Vrevt tbat wulecseetrow of J Cotrtudrte 125 DW eur twbtye, fel) Lek AGB Me toro countable [owe J P Atta, RABLOA, = subse at Gin tab Jey IS BUFO - eS vie a3 OA Pal ae rae mop SIE BP PSO FADEC TET COTA tee BT ESTER ERE AEE ea a eee => BOA a 7 Beg Ae Seis Cy Kaaba Thi scoupernB tek Ou aE (4 12> hy Undo | Munaerg or Mn Twn Leb a be any deb ‘aid TB,,B1 Rs) (oem be Aw gd of A> on a A of He Four DADA... ADR Whee | Tack Px Aro be ot Be oo Bit Lal quis Bb Ginatect’ Hi Bi Be Ba | OL Manna > ty Fe onep = | rE of Bee pore POA Os 73 Dae VPP Ee pS Se ag She Aeon SE Z,, Bo TE Pon 3 Pee | oy : y Ta RENO LE OF weLUNDD : i ND EX CWUITOW 7 i | MEOpAM | Let P ond /O te Tare? PES Be OMI ATEN hen ( i ior > a ae TS yP AS PP OOTP PD Li AN SS POR SE Os TOF] APD DLO a clus Wy) = iP Rite” 8) WO php” te) = 1e8- Piet jbo R\---B) hu ae $ i EooCcecce et does Cora ety = | {Pl +) eI Eilts miaIe-Pr+LiPn BI [Was lt) i =VPo of SPN ey B fps = Ie reMatA ny | a Bj >™ Guey = ati By AEDS = oe r ete Pt ok POOPY ST TOT SPAR = PT = TR ET FTP RD +4 ae 24 DISCPETE * (pxce ne. } pay MATHMATICS pare] | J ay fulahiens —> ; 7 RERKS Pe 7 A=S') 23h “f Reylay eta) 8 ous by J ee & wi } | 7 fapinao para ed Ree tes OT | \\\ Ve A | ar AUT IG 7, mE — 2) Syma c Delatug > Rok th ath = ERabhor ay pee RIV Ly sa F Trav Relate, > Re AF aRbe LRe > apo, aria be TEE PRD, ahi —. eID Lea F FI INVERSE Of A RELATION <> Lt Fae 1 RY FPR RRR Then Di wea yolabew 1b @ ser fee Pu7h = Denoted— Gy Et Re doe: a Eh Gb Ras oppo qty BEB an Oe IPA Beye Cr He] fadchrat OOO ona la yekactio @ on a tet 9 Cabbed fresno] | aasbieel cide. rolatiow if Lt omen [STARS Sti fatty my ow 7 Lecpeeecect Zi tae — d | tek me SRS TEE SET ved ahi wy defined ad aRb U ab cheek Petaiion 3 erttal man Fatakies eek 1] wot TE Gb oe Mal Tip eb aca 7) ara Synod c THE) = ; ji care ach e bho Er of fo bea SIS ey Poterst te ct yi Cota Tran dthuet —> Ff pap QCv Ghee rs So ake Mt Kompodibion. of Pei pw GL RR SBI TH T STB ae ay TAD es oe Telapiow as caamoted ky S$ =e aes epee Tt. het Teale eet te Sok = CLAS Logs Est a a Soy EIU Tey se fa uy (4sy3etuue ~ | Ae ee ee eee fee D Attlee | Luywinelrt ce, Arona ny od ake Hagan ie [awe = ie EAN TIS 4 wo Pettey teeta _4 = oe ; a ti tos th, i on t ay a (Sie ena TT ep ee t Pa SPR Le He] PONCTIOUS >. Ch Pe bade Leet are een ae DrPoy 22k. FR Sabsel eF RFR (alba Fours Por RoR A Apr UF Tak WW EAE FA OS ue Yee Ch hak CY EFL FU a FP DOWa, ef a Fumie “rhe 0k FD ae ain OF SFE Iu ses is Ds ¥F Las oo bicioen > the wt BO atti ee er APSCEN ae Space a a Ogee SapneEiin [Spa ee Ey CSE a eeaal Donde Da RUF hs ee aE Tanege eh Und he PU FU " [al eo Oe ORS Of Al Ae MO OF Oak Sea yoke Foo cal OGL DE OA ROG of paneboue te Se = "7 (ey) Couct Set 2 us a oot) ol s,4asybLL Loe) ae POs Oe a A ea | : onl des Clan [No Sf Clomy =F ][) Range of mS - oe Hara Hs TS as Tyo Saas Ste t 2. Only MM ~ MGFCUUE AD ie ik te OMe fuwetron = fh pumctron Ahad mol OUL- ONL [pace ne. ) j ay TL => POC FP UL) [oate ) Ge Cot Om) ls ee ey Taek Ondvr OL = Poesy > oe ae pss ees ee Bye Due omc Lien > AP WG gute coed ae POL Gan Our Dae ore Om — OW vtec ond W Equal FON a STA De Dg oy = q2 By = Bee 7, pom YOK ae ter 7 Dart Ty AG AO COME Fo ae 5 Ft) eG EF Bnd GOTH EF & 4 DGS ay feta Bias = Cpe Cee i Tae neat Lind De ee a Bato, CT IC LD Chee et Ue quay FUT SRD OL w= SVT Saige =o yates Sie — ee | St { TP STALE OO 0 colon oe Too Bo anu Uy oto bil met beth Ca betes ee |] Property i> Bove that zo Fu, amaeg Tita dilate Tote Tra oo aA Ee ED PRR Koxfound— poop Baste legic ofaahony @l Ts 1) yet ees dg iH Ve o& ZR fonaBOre Whe FE anda, on or pa fer eioys Hee TP one, Tay aod Dad acer Sates ce eae Pees Fu BAL FIC 7 jl g (elf) i 7 Ae FORTS, 1 Thsst Tired i TF OF PDP) ae F Fi F Dap VIS It tos _D of Aire pao Poaitons 4 a-t -pale whe both poe Gan Fat Wa WIS ce 3 wo yh ee ah a) BA. Ar (ose Ape He Ok a 4 yt tbr ay Sigal wt of ac | : ee Set a aaa i Ta Aes iw radon ay ERE ON URS BET Sp OE Toy TE Ee TE « rye i ; mil BVO Dexa BFAD > * Kerra SH J RAE CORE Fan ob Pa ° Lenora > Gree | eR eae DE > 4) * Guinn! > =u 1 es Vee iP a = eae pe ay and ; 0 Ui ee ee See raody” — = A 424 | {Wis te SL ir F F TF T F Foe T | TROY > = F pope PG a mug ob A OA Und. aD arama (15 Tepe “CetRCOAK ry CR REIT or. Salen PIGEOWHOLS PewcieeB Uitnrercanr] > Show Mad =} (race ne] Ta wed “Wm ie obser grows arr Adtt oO we Mm yt We. ee aie a Aorta MATHEMATICAL en] | TJ v Th. pwd te otabtgh Ja- Vola by- ou (A gen Ag rdvuol inVvelomag nahh munabey Une op etraeat {ee ; 7 = Wevking Per > Let mp Dre Lied. Di trae ta se PLN) O SAU na enn eee Oud wt wah De Port Ral Ph) Aya pe OL AZ Me) i Baty of Prducen S Ply.) Pu ee fl) wu ee red i 2 Trade ben eye > Ren Nak PLE) aE dpe mae il Than PLES) wat lag be ru Phew POL) 4 Tre For A MZ E=|> Prev Ae BAR LSS ae ‘Bal Hen Dene Sol} Road of Tnduetoc [> et Us oA ra PLn) =IF +5 Fa-- UW eae fo mei PU) Ha sitery | Je 0 ran po ey Traum SOF Fo war PLY= te see re - FF Dyes y fading aD beth sida pp tm PUrhi) =tepeee ~~~ CL) ee) 5 tor) fe ty AY TUT Y © EV Pauw OF (ei) ved ode yy ue B, = (0, 2, 4) and B, = (1, 5) Bacarra: (6) How many different subsets of A can you generate from B, and B, ? Sol. (a) The possible number of minsets generated by B, and B, are 22 = 4. The minsets are Ay = B, By! = (0, 2, 4) 0 (0, 2, 3, 4) = (0, 2, 4) Ay = By OB, = (1, 3, 5) 9 (1, 5) = (1, 5) Ag = BY OB, = (1, 3, 5) 9 (0, 2,8, 4) = (3) A,=B, OB, = (0,2, 4) (1, 5156 The minsets are {{3}, (1,5), (0, 2, 4]} (b) Number of subsets generated by B, = 28 = 8 Number of subsets generated by B,=2=4 Required Number of subsets =8+4=12, Example 5. Let By By and B, are subsets of a universal set U. (a) Find all minsets generated by B,, B, and By (b) Draw a Venn diagram representing all minsets obtained in part (a) (c) Find the minset normal form of the following sets WBS (ii) By 0 By (iii) BY A BY. Sol. (a) The possible number of minsets generated by B,, B, and B, minsets are 2° = 8. The A, = B, OB, By; A, = BY AB, OB, B,OBfnB,; — Ay=B, BOB! A, = BY OBS OB,; A= BYOB, OB, A,=BOBSaBs; — Ag= BY OBS OBS DISCRETE STRUCTURES (b) The Venn diagram for the sets A,, Ao, ... Ay obtained in part (a) is shown in Fig. 1.95 Cis) Lea] Fig. 1.26 (c) (i) The minset normal form for B,° (using Venn diagram) is given as BY =A,UA,UA,UA, = (BSB, OBS) U BYE AB, OB) UB AB AB) U BY OBE By) (ii) The minset normal form for B, 7B, (using Venn diagram) is B, OB, =A, UA, = (B, OB, 1 B,) U (By NB, B,*) The minset normal form for B,¢ 7B, (using Venn diagram) is BY OB = Ag U Ag = (BY 9 By 0 By) U (BY NB,’ 9 B,’) Example 6. Consider the universal set U=(1, 2, 3, 4, ... 10) and the subsets A=(1, 7,8), B=(1, 6, 9, 10), C =(1, 9, 10)- (a) List the non-empty minsets generated by A, B and C. Do the minsets form a partition of U? (6) How many elements of U can be generated by A, B and C? (c) Compare the number obtained in (b) with n(P(U)). (d) Give an example of one subset that cannot be generated by A, B and C. Sol. (a) The possible number of minsets generated by n sets is 2". These minsets are given below: A, = ANB = (1,7, 8) 911, 6,9, 10) (2, 3, 4,5, 6,7, 8) =6 ABN C=({1, 7,8) (2,3, 4,5, 7, 8) (1,9, 10) =6 A, =A° NBN C= 12,3, 4,5, 6, 9, 10) 9 (1, 6, 9, 10) 9 (1, 9, 10) = (9, 10) A,= AN Ben C= (1,7, 8) 9 (2, 3, 4, 5, 7, 81.0 (2, 3, 4, 5, 6, 7, 8) = (7, 8} Ag = Aen Bn O° = (2, 3,4, 5, 6, 9, 10) n (1, 6, 9, 10) 9 (2, 3, 4, 5, 6, 7, 8) Ag= ANB nC = (2,3, 4,5, 6, 9, 10) 012, 3, 4, 5, 7, 8) 0 (1, 9, 10) = A, = APO Ben C= (2,3, 4,5, 6,9, 10) 9 (2, 3,4, 5, 7, 81.0 (2, 8, 4,5, 6, 7, 8) 2, 8, 4, 5) Ag=ANBNC={1), Hence, the minsets generated by A, B and C are (9, 10), (7, 8), (6), (23, 4, 5), (1)- = (6) 8 Clearly, A, A;= 6 fori #j and |_| A, =U. Hence, they form a partition of U. mt (b) From part (a), there are five different minsets generat Hence, 2° clements of U can be generated by A, B and C, Ae hee 45 (c) As U contains 10 elements, therefore, oe a n (P(U)) = 21°, (d) {1, 2} cannot be generated by A, B and C since 2 A, B, and C. TEST YOUR KNOWLEDGE 1.3 Partition A = (0, 1, 2, 3, 4, 5] with the minsets generated by. B different subsets of A can you generate from B, and B,? 2 Let A= 14,5, 61, B, = (4, 5}, By = (5, 6) (a) Find the minsets and maxsets generated by B, and By. (b) Do minsets form a partition of A? 0, 2, 41, By = (1, 51. How many Let S be a set of words or string of length < 2. i.e., S = {0, 1, 00, 01, 10, 11) and A = {0, 00, 01), B = (00, 01, 10, 11). Find a partition of S using minsets generated by A and B Answers {1, 5}, (0, 2, 4}, {3}. Required number of subsets = 12 2. (a) The minsets are A, = (5), Ay = (6), Ag The maxsets are m, = (4, 5, 6), my (0) Yes 3. The minsets are A, = (00, 01), A, = (10, 111, A, =(0}, A,= (1). ‘The required partition is (Ay, Ay, Ay, Aj). (4, 51, m, = (4, 6) sTION = 61 Ly gay +y—aie aloo dividlble by'm => x~z is divisible by m = x=z(modm) is transitive Hence = is an equivalence relation. Example 17. Let A be the set of integers ‘and let ~ be the relation on Ax A defined by (a, b)~(c,d)ifa+d=b+e ve that ~ is an equivalence relation. Sol. Reflexive. (a,b) ~ (a, b)ifa+b=b +a, which is true. Hence ~ is reflexive. Symmetric. Let (a, b)~(¢, d), thena+d=6 +e : c+ =d +aand hence (¢, d) ~ (a, 6) Hence ~ is symmetric. ‘ ‘Transitive. Let (a, 6) ~ (c,d). Then a + d=bt+e Let (c,d)~(e,f), thenc+f=d+e Adding, a+d+c+fzb+erd+e = a+f=b+re => (a,b) ~ @, A. Hence ~ is transitive. ~ is equivalence relation. Example 18. Define partial order relation with example. (P.T.U. B.Tech. Dec: 2004 ; May 2006) Sol. Partial order relation. A relation R on a set Ais said to be a partial order rela- mona iit it is (i) reflexive (i) antisymmetric (i) transitive, 1a D(A) denotes the power set of A and define a relation Ras (A, B) ¢ ReAcB. We show Ris a partial order relation. Reflexive. Since A cA for all Ac P(A). (A, A)e R. Hence R is reflexive. Arter manetric.Let(A, B)e Ry B, A) R, then AGB, BSA->A=BforallA, Be P(A), Ris antisymmetric. if(A, B)e R, (B, C)e R, then ‘AcB,BcC. = AcgCforallA,B,Ce P(A). 7 Ris transitive also. Hence the relation R is partial order relation. . 19, Let A = (a, b, ¢). Let R be a relati ay). See iefiaive closure of R. a relation on A defined by R = ((a, a), (a, 6), (b, ©), aL. Given relation R = ((a, a), (a, b), ( ©), ‘ ’ ‘ sins @B), ( e)in-R, the required ere ttantae ste ie aabgs Cae Ry= l(a, a, (a, B), (b, ©), (, a), (bb), (e, ol: Example 20. Let A= (I, 2, 3, 4) and let Ri \ ind the transitive closure of R. and let R is defined by R = ((1, 2), (2, 3), (3, 4), (2, DI. Sol.Given R= ((1, 2),(2,3), (8, 4), (2, ) Here (1, 2), 2, 1) € R. If Ris transitive. Then there should be (1, 1) ¢ R, "Similarly (1, 2) € R, (2, 8) ¢ R. If Ris transitive, there should be (1, 3) eR Finally, EE STE Example 26. Let A= (1, 2,3, 4, 6) and R be the relation “x divides y”. Write Ras set rdered pairs. Find the inverse R of the relation R. Can R-! be described in words, bs Sol. We know that x/y (read as x divides y) if there exists an integer z such that y =. Ve find those numbers in A which are divisible by 1, 2, 3, 4 and 6. Since W/1, 1/2, V3, 1/4, U6, 2/2, 2/4, 2/6, 9/8, 3/6, 4/4, 4/6 Thus, R= (C1, 1,1,2), (1,9), (1,4) (1, 8) @ 2) 2 4), (2, 6), (3, 3), (8, 6), (4, 4), (4,6) Reverse the ordered pairs of R to obtain R~. Thus, R= ((1, D, 2, V, B,D, 4, Vs ©, VD, 2,2) 4 2), (6, 2), (3, 3), (6, 8), (4,4), (6,4) Yes, R-! can be deseribed by the statement “sis a multiply of y”. Example 27. Let R and R be the relations on A = {1, 2, 3) defined by R=(1, D), (1,2), 2,9) BV, 8,39) = (1,2), 0,9), 2, D, 8,9) (a) Find ROS, RUS (b) Find Re. Sol.(a) RAS=((,2), 6,3) RUS =((L, D, (1,2), (1, 3s 2, D, 2 3) B, VB, 3)) (b) Use the fact that A x Ais the universal relation on A. Hence, Ax A=(1, 2,3) x (1, 2,3) = (L, 1, (1, 2), (1, 3) (2s 1), 2, 2s (2, 3), (8, Dy Bs 2, Bs 3) ‘CA R= The set of ordered pairs which are in Ax A but 1, 3), (2, 1), (2, 2), (3, 2). mple 28. If A = (1, 2, 3, 4) and let / R= (1, V, (1, 2), 2,3), 2, 9, (3, 4), (47D, (4, 2)) S= (03, ), (4, 4,42. 9), 2, 9, , DL, BI Find (i) RoS, (ii) SoR, (iii) RoR, (iv) SoS Sol. (i) To find RoS ot in R Here BES dVEeR > (3, 1) € RoS (4,4¢€9,14,DeR => (4, 1) € RoS, pane R= (4, 2) e RoS (2,3)€S,(3,4eR => (2,4) € RoS (2,4)€8,4,)eR = (2, 1) € RoS (2,4)¢€5,4,2)¢R = (2, 2) RoS abesaveR = (1, 1) € RoS G,VeS,0,2¢6¢R = (1, 2) € RoS G4M¢e5,4)EeR = (1, 1) RoS a,%¢8,4,2¢R => (1,2) € RoS RoS = ((3, 1), (4, 1), (4, 2), (2, 4), (2, 1), (2, 2), (1, 1), (1, 2) (ii) To find SoR Here ,DeRG,) and G,4eS = (2,2, (1 de SOR (1,2¢ R,(2,3) and (2,4)¢S = (1,3), (1,4) SOR a ELATIONS, 65 (2,3)€ R38, eS = 12, De SoR 2,4)eR, 4,468 = (2,4)¢ SoR B,4)eR, 44S = @,4)e SoR (4, )e R,(1, 1) and (1, 4) S = (4,0), (4,4) ¢ SoR (4, 2) € R, (2,3) and (2, 4) S = (4,3), (4,4) ¢ SOR : SoR = (1,1), (2, 4), (1, 3), 2D, (2, 4), B, 4), 4, Ds 4s 4), 4, 39} (iii) To find RoR, Here (1,DeR(,2eR + (1,2) RoR (1,2€R,(2,3)eR > (1,3) € RoR (1,2€R,@,4eR > (14)¢ RoR 2,3)eR,G,4)eR = (2,4)€ RoR G,4)eR, 4 DER > De RR (4,)eR, 0,1) and 0,2eR = 40, (4,2) ¢ RoR (4,2)¢R,@,3) and @deR = 49,40 RoR F ROR = ((1y 2, 1, 8), (1,4), (2 4B, D, (4, D, 4, 2, (4,9) 4,4) (iv) To find SoS Here, @,DeS,G,Dandd,VveS = G 1), (8, 2) € SoS 2,3)€8,@, eS = (De SS 248,44 HeS = (Ae SoS GpesadeS 2 Ae SoS 4 €8,4,HeS) 2) GsA)e SS E SoS = ((3, D, (3, 2), (2, 1), 2, 4) G, 40) Example 29. Let S = (1, n)ine 2, T= fin, D, n € Z) are relations on Z. Find (i SoT, (i) ToS. Sol.) DET Anes > Mme SoT, ne Z ee SoT =2ZxZ (ii) To find ToS, here (1, n)e S,(n, De T = (1, De Tos ToS = (1, DI. TEST YOUR KNOWLEDGE 2.1 SHORT ANSWER TYPE QUESTIONS }. What is a congurent relation ? 2. Define an equivalence relation with the help of a1 3. What is a relation ? Give example. ants ot ae a re ae aes , B ° : : __ (P.T.U. B.Tech. May : ae is ee i finite set A having n elements. What will be the number of relations on A? . = (1, 2, 3, 4) and R = ((2, 2), (8, 3), (4, 4), (1, 2)) be a relation on A. Examine whether R is symmetric, transitive or reflexive. (P.T.U. M.C.A, 2003: 6 INCLUSION-EXCLUSION PRINCIPLE rig. ILLUSTRATIVE EXAMPLES Example 1, Out of 1200 students at a college 582 took Economies 627 took English 543 took Mathematics 217 took both Economics and English INCLUSION-EXCLUSION PRINCIPLE wee 307 took both Economics and Mathematics 250 took both Mathematics and English 222 took all three courses. How many took none of the three ? Sol. Let A, B, C denote the set of students studying Economics, English, Mathematics respectively. Given ‘ | A| =582 | B | =627 | c | =543 [ANB | =217 307 [BoC | =250 [AnBoC | =222 ‘The total number of students who took any of three subjects pauBuC|=1Al+/B/+1C1-1AnB]-|Bn01—1 onal +|AABoC] = 582 + 627 + 543 — 217 — 307 — 250 + 222 = 1200 Students who took none of three subsets ‘total students in the college) — (total stu = 1200 — 1200 = 0. dents who took any of three subjects) mmers interviewed for a job. 25 knew JAVA, 28 knew Example 2. 40 computer prograi w both languages ? ORACLE, and 7 knew neither language. How many kne Sol. Now, | J | =25 | 0 | =28 | JU | =40-7=33 mmers who knew both languages are Computer progra: JUO | =25 + 28-33 = 20. jInol=ls1+1Ol-! Example 3. A survey of 550 television watchers produced the following information : 285 watch football games 195 watch hockey games 115 watch baseball games 45 watch football and baseball games 70 watch football and hockey games 50 watch hockey and baseball games 100 do not watch any of the three games. (a) How many people in the survey watch all three games ? (b) How many people watch exactly one of the three games ? Sol. (a) F, H, Bd : eapedtively Given enote the sets of watchers watching football, hockey, baseball | F | =285; | H| = 195; | BI = 115 [FAB] =45;| FAH | =70;| HOB] =50 ae | FUHUB | =550- 100 = 450 number of people watch all three games IFoHoB| = 450 — 285 - 195 — 115 + 45 + 70 + 50 = 20. i. | 186 DISCRETE STRUCTURE (b) 20 watch all three games. 45 - 20 = 25 watch football and baseball but not all three. 70 — 20 = 50 watch football and hockey but not all three. 50 — 20 = 30 watch hockey and baseball but not all three. 285 — 25 — 50 — 20 = 190 watch only football. 195 — 50 — 30 — 20 = 95 watch only hockey. 115 - 25 — 30 — 20 = 40 watch only baseball. Number of people exactly watch one of the three games = 190 + 95 + 40 = 325. a (®) Alternative. To find the number of people watch- (2) 40 B ing, exactly one of the three games, we use Venn-diagrams (see Fig. 6.3). Required number of people watching exactly one of the three games = 190 +95 + 40 = 325. Bu Example 4. Among 100 students, 32 study Mathematics, 20 study Physics, 45 study Biology, 15 study Mathematics and Biology, 7 study Mathematics and Physics, 10 study Physics and Biology and 30 do not study any of three subjects. (a) Find the number of students studying all three subjects. (b) Find the number of students studying exactly dne of the three subjects. Sol. (a) Let M, P, B denote the sets of students studying Mathematies, Physics and Biology. Given n(M) = 32, n(P)=20, n(B) = 45 n(MnB) = 15, n(MnP)=7, n(PAB) = 10 n(MABoP) = 30 Now, — n(MABoP)=100-n(MUBUP) = 100-n(MABnP) = 100-30=70 Required number of students studying all the three subjects is given by n(M APB) Using inclusion-exclusion principle, we have n(M 9 P 1B) = n(M) + n(P) + n(B) — n(M 9 P) -n(P 0B) =n(BAM)+n(MaPob) = 70 = 32 + 204+ 45-7-10-15+n(MAPOB) => 70 = 65 +n(MOAP OB) => n(MAPOB)=70-65=5 (b) To find the number of students studying exactly one of the subjects we use Venn-diagram (see Fig, 6.4) As 5 study all three subjects 7-5 = 2 study Maths and Physics but not all three 15 - 5 = 10 study Maths and Biology but not all three Vig. 64 oon NCLUSION-EXCLUSION PRINCIPLE 187 10- 32-(10+2+5) study Biology and Physics but no! 5 study Maths only 20 -(2 +5 +5) = 8 study Physies only 45 -(10 + 5 + 5) = 25 study only Biology only Number of students studying exactly one of threo subjects = 15 + 8 + 25 = Example 5. In a survey of 300 students, 64 had taken a Mathematics course 94 had taken a English course 58 had taken a Computer course 98 had taken both a Mathematics and a Computer course 96 had taken both a English and a Mathematics course 22 had taken both a English and a Computer course 14 had taken all three courses. (a) How many students were surveyed who had taken non of the three courses ? () How many had taken only a Computer course ? Sol. Let M, E, C denote the sets of students taking mathematics, English; Computer Courses respectively. Then | M| =64;| EB] =945 | C1 =58 [Mac | =28;|MnB | =26;| BOC | =22 |MaEnC|=14 @ |MuBuc|=[Mi+iBl+1e1-IMacl -|MaE|-| Eacl+)MaEnC] = 64 +944 58- 28-26-22 +14= 154 Students who had taken none of the courses = 300 - 154 = 146. (b) 14 had taken all three courses. 98 — 14 = 14 had taken both a Mathematies and a Computer but not all three 22-14 = 8 had taken both a English and a Computer courses but not all three 58-14-8-14=22 had taken only Computer course. Example 6. Let A, B, C, D denote respectively, Art, Biology, Chemistry and Drama courses, Find the number of students in a dormetory given the data. 12 Take A, 5 Take AandB 3 Take A, B,C 20 Take B, 7 Take AandC 2Take A, B,D 20 Take C, 4 Take AandD 2Take B,C,D 8Take D, 16 Take Band C 3 Take A, C,D 4Take Band D 2Take A,B, C,D 3Take CandD 71 Take none. Sol, We first find the number of students who take at least one course, By Inclusion-Exclusion principle. T=n(AUBUCUD) 61-8, + 8g 84 | General Exclusion-Inclusion Principle n(A) + n(B) + n(C) + n(D) = 12 + 20 + 20 + 8 = 60 where a. | 188 DISCRETE sy; Rucy Ue (A 0B) + (B.C) + (CAD) + HD OA) + ANC) + np, 541643444744 =39 ‘0 = MAA BAC) +nBACAD)+NAOCND) + 2AnBrD, 3+24+34+2=10 5,=MAQBOCOD)=2 * T= 60-39 + 10-2=70-41=29 Hence the required number of students = Number of students who take at least one course + Number of students who take none gop, = 29+71=100. Example 7. Suppose that 100 of the 120 Mathematics students at a college take at ig one of the languages French, German and Russian. Also suppose 65 study French, 20 study French and German 45 study German, 25 study French and Russian 42 study Russian, 15 study French and Russian (a) Find the number of students studying all the subjects (b) Find the number of students studying taking exactly one subject. Sol. (a) Let F, G and R denote the sets of students studying French, German, Russia respectively. Given nF UGUR) 00, n(F)=65, n(G) = 45, n(R) = 42, n(F AG)=20, n(F 9 R) = 25, n(G AR) = 15, we find n(Fn GOR). Using Inclusion-Exclusion principle, nF UG UR) = n(F) + n(G) + n(R) = {F.9 G) = n(G OR)— A(R OF) + nF GOR = 100 = 65 + 45 + 42-20 15-25 + n(F n GAR) = 100 = 92+n(F AGAR) = nF AGAR) = 100-92 =8. (b) To find the number of students taking exactly one subject, we use Venn-diagrams. (see Fig. 6.5) 8 read all three subject 25-8 = 17 read French and Russian but not German (Se 20 —8 = 12 read French and German but not Russian read Russian and German but not French Ce) 15-8 65 — (17 + 8 + 12) = 28 read French only 45 — (12 + 8 + 7) = 18 read German only 42 -(17 + 8 +7) = 10 read Russian only Required number of students who study exactly one subject = 28 + 18+ 10=56, Example 8. In a survey of 60 people, it was found that 25 read Newsweek magazine 26 read Time, 26 read Fortune CLUSION-EXCLUSION PRINCIPLE 7 read both Newsweek and Fortunt 41 read both News week and Time 8 read both Time and Fortune 3 read all three magazines 189 (a) Find the number of students who read at least one of the three magazines (8) Find the number of students who read exactly one magazine (c) Find the number of students who read no magazine at all. Sol. Let N, F, T denote the sets of students reading ewsweck, Fortune, Time magazines respectively. (a) Required number of students =n(NUTUF)=A(N) +n(T)+n(F)-n(NOT) . By =n(TAF)-n(F AN) +n(NOTOF) = 25 +26 + 26-11-8-9+3=52. (8) To find the number of students who read exactly one \igazine, we use Venn-diagram. (see Fig. 6.6). Here 3 read all three magazines Fig. 6.6 11-3 =8 read Newsweek and Time but not‘all three magazines 9—3=6 read Newsweek and Fortune but not all three magazines 8—3=5 read Time and Fortune but not all three magazines 25 —( 8 + 3° 6) = 8 read only Newsweek 26 — (8 + 3 +5) = 10 read only Time 26 — (6 + 3 + 5) = 12 read only Fortune Required umber of students who read exactly one magazine =8+10+12=30. (c) Required number of students who study no magazine = 60 —n(NUTUF)=60-52=8. Example 9. Among the first 500 positive integers : (a) Determine the integers which are not divisible by 2, nor by 8, nor by 8. (6) Determine the integers which are exactly divisible by one of them. Sol. Let A is the number of integers divisible by 2 Bis the number of integers divisible by 3 Cis the number of integers divisible by 5. 00 JAl= [2] 250; (Bi =[22] =166; 11 =[522] = 100 500 _ [500] _ [Anz =[22 S00 | «833 janci=[2]- 500 [pac =( 220] 33; |AnBoc | =[52025]=16 3x3x5 (@)| AUBUC | = 250 + 166 + 50 — 83 - 100-33 + 1 The integers not divisible by 2, 3 and 5 = 500 — 366 = 134. 366 a wo REE wry (b) The integors divisible by all the three = 16 83 — 1G = 67 intogers are divisible by 2 and 3 but not all the three 50__ 16 = 34 integers aro divisible by 2 and 6 but not by al the three 33 16 = 17 integers are divisible by 3 and 6 but not by al the thre 250 — 67 — 34-16 = 133 integers are only divisible by 2 166 — 67-17-16 = 66 integers are only divisible by 3 100 -34-17-16= 33 integers are only divisible by 5 Total number of integers only divisible by 2, 3 and 5 = 133 +33 + 66= 232. 10. Among the first 1000 positive integers : ‘are not divisible by 5, nor by 7, nor by 9. le by 5, but not by 7, not by 9. Example (a) Determine the integers which (b) Determine the integers divisibl Sol. Let A is the number of integers divisible by5 Bis the number of integers divisible by 7 Cis the number of integers divisible by 9. 1000 1000 So Ay =|222| = 205 jp = [290°] 242 5 7 1000 1000 c - [2] AnBl=|=>7|= Ic] 9 ol Ae l=lex7 28 1000 1000 } Anc| =|] =225 ea I | [5] 2; |[Bnc| 3] 15 jAnBac | =( a8. 5x 7x9 (a) The number of integers divisible by 5, 7 and 9 | AUBUC | = 200+ 142 + 111 ~ 28-22-15 +3 = 391. ‘ ‘The number of integers not divisible by 5, nor by 7, nor by 9 = Total number of integers — integers divisible by 5, 7 and 9 = 1000 - 391 = 609. (b) The integers divisible by all the three integers = 3 28 — 3 = 25 integers divisible by 5 and 7 but not by all the three - 22-3 = 19 integers divisible by 5 and 9 but not by alll the three - 25 - 19 -3 = 153 integers divisible by 5 but not by 7, not by 9- ad DISCRETE STRUbTURES « 532 : pag | aar | rap | @advaanvean (OP ae P - 7 T . T T T Fr F T Tee rE : e F F F F Te F . ci F T F F T T z . T F T, iF. T Sole p T F F F F Paley F F F :F F ee F F F F Fig. 13.3 (iii) P 4 ae ae GPlyvin@) T T F F F T F F T T F T T F T F F T T T Fig. 13.4 (iv) P q a Pee T T T T T T F rT T F PF 7 T F a A - F Dee T iT: F F T Ty F iT: F T F Fr F F Fig. 13.5 13.6. COMBINATION OF PROPOSITIONS ar 4 three We can combine the Propositions to produce new propositions. There are fundamental and three derive 44, Jained ed connectors to combine the propositions. These are exp as follows one by one, (a) Fundamental Connectors 1. Conjunction. It mean: tions. Conjunction of otherwise false. It is -oposi- 's ANDing of two statements, Assume p and q be Hae ae P and q to be a proposition which is true when both p and q denoted by p »q. (Fig. 13.6) AL CALCULUS: 533 P. 4 PAG T iT T T F F F T F F Pr 7 Fig. 13.6. Truth Table of p aq. ,Disjunction. It means ORing of two statements. Assume p and q be two proposi- gesisunction ofp and to be a proposition which is true when elther one or both p and q it eand is false when both p and q are false. It is denoted by p v (Fig. 18.7) P q PYG T T rr T F ? F T 7 F F F Fig. 18.7. Truth Table of pv q. 4. Negation. It means opposite of original statement, Assume p be a proposition. Nega- fimofp to be a proposition which is true when p is false, and is false when p is true. It is éauted by ~ p. (Fig. 13.8) P -P T F F T Fig. 13.8. Truth Table of ~ p. Example 2. Consider the following : p:Heis rich q: He is Generous. : Write the proposition which combines the proposition p and q using conjunction (\), "junction (v), and negation (~). Sol. Conjunction. He is rich and generous i.e., P99: Disjunetion, He is rich or generous ie., pV 4- Negation, He is not rich i.e., ~ p Heis not generous i.e., ~ g. Iti is false that he is rich or generous i.e., ~ (p V 4)- Hoi nee - 'S neither rich nor generous i.c., ~ Pp A~ 7: 1s false that he is not rich i.e., ~ (~ P). DISCRI Se a Example 3. Let p be “It is hot day” and q be “The temperature is 45°C”. Write in simpy sentences the meaning of following : @)~p (ii) ~(pv@ (iii) ~ (pag (iv) ~ (~ p) (u)pyq (vi)paq (vii) = pa~q (viii) ~ (~ py ~ @. Sol. (7) It is not a hot day. (ii) It is false that it is hot day or temperature is 45°C. (ii) It is not true that it is hot day and temperature is 45°C. (iv) It is false that it is not a hot day. (v) It is hot day or temperature is 45°C. (vi) It is hot day and temperature is 45°C. (vii) It is neither a hot day nor temperature is 45°C. (viii) It is false that it is not a hot day or temperature is not 45°C. Example 4. Consider the following statements : p: He is coward. q: He is lazy. r: He is rich. Write the following compound statements in the symbolic form. (i) He is either coward or poor. (ii) He is neither coward nor lazy. (iii) It is false that he is coward but not lazy. (iv) He is coward or lazy but not rich. (v) It is false that he is coward or lazy but not rich. (vi) It is not true that he is not rich. (vii) He is rich or else he is both coward and lazy. Sol. (i) pa~r (iv) pvg)a-r (vit) rv D Aq). (Wi) ~pa~q (ii) ~ (p a~q) ) (py ga~r) Wi)~ (=r) , 538 DISCRETE STRUCTURE LL 13.7. (b) VARIATIONS IN CONDITIONAL STATEMENT Contrapositive. The proposition ~ ¢ + ~ p is called contrapositive of p ~ g, Converse. The proposition q — p is called the converse of p = q. Inverse. The proposition ~ p — ~q is called the inverse of p > q. Example 12. Show that p > q and its contrapositive'~ q > ~ p are logically equivalen, Sol. Construct truth table for both the propositions. (as in Fig. 13.18) P q ~P a] p>q ~q>~p T . F F = T T F F T F F F T T F T his F F T T T uy Fig. 13.18 As, the values in both cases are same, hence both propositions are equivalent. Example 13. Show that proposition q — p and ~ p ~~ q is not equivalent to p +. Sol. Construct truth table for all the above propositions : P q ~P ~q Pa Zp Prd T T F F > T T T F F T F T T F T or F T F F F F T T T T T Fig. 13.19 As the values of p ~ q in table is not equal to q — p and ~ p > ~ q as in Fig. 18.19. Sc both of them are not equal to p —> q but they are themselves logically equivalent. Example 14. Prove that the following propositions are equivalent to p — q. @-(a-~q Wi) -pvq (iii) ~q>~p. Sol. Construct the truth table for all the above propositions : P q ~P 4 | ~Pva | ~q>~p| @a-g | -@a-o | PP v T F F v T F T a iT F F 7 F F T F E F T T F T T F T o F F T T T T F © u Fig. 13.20 ii e In the above table (Fig. 13.20) the values ofp — q is equivalent to (i), (di) and (iii), hens they are equivalent to p - q. Hence proved, seonditional state- 2. Biconditional. Statements of the form “if and only if” are called biconditional stal ments.

You might also like