[go: up one dir, main page]
Scribd
Upload
46 views60 pages

Module 3 (Relation and Functions)

Uploaded by

snophlwfxncilukjyl
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
46 views60 pages

Module 3 (Relation and Functions)

Uploaded by

snophlwfxncilukjyl
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/ 60
Module 3 Relafions and Funcfiong kef A and B be & Sef. Dhen She Bef of All ordered pares (a,b) there AEA and beEB 1 Called fhe cavfestan product oF cass product. te 19 denoted by AXB , Ihus Axa ={ (a,b) /aen and beB} &g:- Az {-1,0,1} and p-{a.3} AxB= { (118) (13) (0.2) (0,9) C2) C9) h BxA = { (a,-1) (210) (21) (8,-1) (3.0) tah Axa A BxA AxAz= A= {Guy (-1,0) (-141) (0,1) (0.0) Co, (uy) (1.0) GS Note: TF As to , goto} then AXB = men elemu se (4) het Aa fash - B={213} anc c={4,6} find (i) Bxc (i) (AuB)xc (ii) (8xA)u(Bxc) solv: (i) Bx = {(9.4) (0.6) 04,4) (3,695. (iD (Ava)xc = { | St xtaey { Cra) (1.6) C204) C96) C44) C2.09 04,0) F a} (ii) (AYA) U (nee) (eva) = {C2 Craylrs) C2 10024) Cas)h fave) - £ Can) (2.6) (4A) C.0)F (BVA) ulmxey = {CaN) (043) (4.5) (3) (9) (45) 2) (016) (2,4) (906) 9, (9) Find m™ and ha cach of She following caze% (3) (aa, 24g) = (6,1) (ii) (yma, Our) = (a-1, yra) soln'- (i) (a4, ary) = (6.1) OW=6 Oe | rae—al, (i) (y-a, 2441) = (1-1, gre) yoo = 4-4 , atta Yr t-Yy4+1=0 oe MAHA! =o oN) ere Stee ys peal [eer (3) Suppose A,B,C Co 2x%Z where A= { (>, Wy) / Y= 5X '} rtp ye e9 =f (yy au-ye A}, Find (v auc (ii) BUT So" (i) Aa AUC = Ane i Rog = Ans] =Anc faiaa. =} Cay eane B Qa aro Te can be wepwesenfed dragercm cattcdt @8 A gular Note: A coafang an efemenls , B comfang 1 efements ~fhen ef orfron -faom A £0 B confaing ca cfemnenfa, fous Prvbleans fi ar 2 G) A=1!:2:3) »B=f{% 4.5} find tre following rs 2 (1) [Ax p] f contains how (i) Number of a efecfions -farm A toB (iD Np of bimaay welefions on A (v) No of velafions fom A fo B thet comfain (1,0) and (1,5) (2) No. of veferfions Poem AbB S owmdered pares. frons foom Arto B Jhaf comfain exacfty (Ui) No. of refer dnaf cordfaing fleas oadered pouss men 2 3X3 =F A - gla SIA x so\r:- (i) 1A xB) = fi) ARB =e” (i) No. of aefafion on A = a” (iv) bef R= {(rarlns)f ra ; Aleve JaxBl=4 mo of avefafion 18 = q-g =< + at - 198 , 7 of aefefion from A to B jhe ofement (112) & (usd ovdered pays OT", m™_ gF- sia ie comdcin (v) ARB coarfaining omy S Acg = 106 elements ) Deas} F ovdeved prs possibilities ave a = 364941 546 2) he aztruas 4 > \ Ac Ute MS, ep and Ro beshe wefafion om DD aetime cor nr Y fefmed as (ANER fandouly f ass amuditple of b. Rave down R as a sef of ordered Pars. Soler. a rvs mntrple of b 1 (a.b) Sarpe A and ‘A is aq muttiple of by} Bae , ho r > r f = £(9.8) (251) (21a) (3.1) (313) (40 qt) (412) (e,1) Ce. 2) Ce.) Cer6) P CH) _Funcfrons ce hef A and & pe the Q Non- empty gefs . Shen A Senet oe or mapping fA toB a vefafion fom A fo B such that evevy element. of e ofermenf in ee b = fla) A has & aintgst of ta’? and tq’? re cattee| ewe be te catted Fhe manage 4ne preimage of ‘b’ | 4 function f fom Ade B denoted bY Pp toh 1 8 Dhe picforat ve pregenfafion of f fo eB b=fta) > range of FS. Sea) domain co-domain | Nolet: i (1) Lverny Pancefion 1% a vefefion buf every rrefafion meet meof be aPuncfion : (@) A confangousm cfemenle , B conams m efements jnen a function tf! favm A toB confang mn” efements, problems (4) Defeamine jhe Pollorwing acfafions ave fancf 100s @ nef Gi) Met aay - pef{ol oy R= {(u- (1,0) (a) (a0) scle:- Given get Cucp Cie) (ey (e)} A B . 3 Pe { a Pruncfron because ¥ , ok B&B ne 4a of A we velelet +o beth —1 and o of- B fy n=fiaap aed pa{-1o} S = {Cry (a,-1) (3,0)5 A e Tk wa funcfion . i rhe Because every element of amenf in B > | A here unrqyure ef€ fy Aaf1.9.34} , 9+ { (2.0) (a) tnd} Sole: - A HI 2 3 A Th 12 mef a fPunefion pecauze J of ¢ eforfect fo any element of A (Co-clomnean) , @) For Aah a3 45h and B= {rw myizd Pauncfion f fom A tog defined by | ae fey Ca.) (Ary) C504) Cap. Find tne vonage of ne following i) As { 1213} (i) Aa- Loa ast Sole: B (D A= {33 dhe vanage, f(A) < f of Wy Aor {oaad Sra) = fad Ae FE bot $ Foom R4AOR defined by Sr foo | ms for 3720 ~ 8x41 Pow %A $9) = 3(S)-5 = 0 (x= 9,29) 4 (Js) = -aCY)+ | =6 (x=-9,<9) (i) fty=b = anf) ret f(y = % ie SIE es Gop Yy (4S9 =o $'(0) = g 0579 to find, pry , bef Silay ex > SOWE) gl prs - 3A} =) ars — | —- faz o\ fas al fla=d L'(y=o pty a1 ay To find SCV ley an = POY = =| (9 >0) (0<9) -3A+) = -J 32-45 = —-] =y ~3X= 2 Bx = jr=%] a >o a g'CYH4 24 To fined f(s) Figaa 7 Hd = SxS = 3 BxA=S Hag » 350 ay 3 a SMy =k = [Fra] 346 -BAF) =3 —3%A=2 Merk, 3 LIND =~ 7s gly a {2 8h, —B%A+) = —-€ ga = 4 ca ee Ce » 2 x0 a a oe 3 3 Hf ‘Cog. ( 2 (bs Yan fis [-s.J py “SSF ST case (i) -SK Ox-FK T ot Sta oh ac oat oa co omen OK 3x < 10 >B —6 << < fo < case -¢ 6 34-565 645 < BX RHE al << oot < Jo hx ae 10 | “3 cas eli) —6 < -BAFI A —6-1< —-3% Mi An funefion. qo = a(n3-1) , WER fake % & % ER (Nef possible) So, ket ADO, go) = o(o-I)-0 cad eee qe (3-1) =o ‘9! 1g mof ome—one Puncfion, 4) ket fi z—vzZ defined by fia) =a+) for a&z Find wihefner f 13 one-one (D onto Solm- Plav= att! , Az Fake UGA € Z comnder . Py) =F) aH =O, +f =y % =a, 3 - 1B ome - OMe Now, Few pooving onto Pune, comsider bEZ Staab 4 z fa) a+ =] 5 a= b-j ia 7 Ge =y bole Zz (5) hef A=R ,Baf asa ww real § 1%0} Phe function PiA—-B defined by f(a) = a> Solr fa) =a? 9, 2% ER comsides, —PCen) =fCa,) a, =tfg> Qe + a, eq, =% @ qo) " f ip mey one OFF a f Now, fake beB. f(ay=b ean az= b sasib (AIDEA berowe A=R) . 2 oafo. Ney e (4) [Alam . lela, fis one-one from Abs plavm) = (a-my ni '(@) Ialem, lalen . £18 onto fur Prom Abe | plaim) = = c-* ace (m-K) lee ee BE ae (6) Shere 60 one-one Punefion Ato B and lAl=3 watnat + |p) = 9 Sole. plm,an) = a! fi-™)! GO a! OD! 60 = m(n-i)(n-2) (0D: ~ wr! ; => 60 = aln-a(m) [Go = 5x 4x3] « faes] Hlemce [Bl=Sy (4) hef Ae {12.345 64} and pif yoz Find tne nO of onto PuncHions faom A to B. sole- JAJ=zaiom ¢ IBl)=T=4 pln) = FS VE MG Cre K)™ K=0 A om p43) = 70 enk ac, AY) K=0 ko0, pla) = 4e, 47 = 16384 oo A -4xelet+ = — S448. fe Cee) eae ete = + = F6s neg, Plaa= 4a at 6x 1as = F eos, pla ee “40 qt = —A kaa, plad = CF 46 ( =o. pla,dj= 16384 — 8448 4468-440 = 840074 4) Composition of Pundions Comsider 3 Mon-emply functions f: A+B and g: Bc. ahe co of 4nese @ funefrons go : Ac wth qof . ghey Bets A,B,C and fre rmpos £10 we defined as he Punefion Aihere AEA 7~ qed. Nefe:- 1 ft AA then Sof = ~* Popo are a. ged = gq (Fen) 3. Pog = P( qe) gp rob lems (a) hel fee ond c= {rom yz} poh Pf: A+B and 9: Boe given: by S=fCa) Ca.) (3,6) (4.c)} cinct gaC (ar Cbry) Core)F find gf 9 al qot So] > gh = {0 lary (sp lnDy, an consider the Puncfrons f and 9 clefined by Pray= 22 and GO = +I LW KER. Find gof , fog 2 And algo show phacf- fog F gof 4 and "9 soln Pgopcny = GF) To find got Tofinel fo goofy a VF oy) fog ia) =P(I™) = 409 ; =flavy = Grr! fog = Fer )44 aod a eay 9 aly goh ond A Logs) 2 | To Fant F ToFind g? Sofa) = PCF) Ca 4a = pos) = gla = @93 9°99 = CMD 41, Pofm= x1, : TH) het Pf and g be the Panefrons Poom R to R defined by Pex) = axtb etnel go = Jamt ar if geht = gx2—974+3 - Find a and b. Sol Gy oF Ca) = 9x2-9043 fe g(axtb) = | — (a+b) + Catt) = 917-94 X43 garb + att brFeab = 97-943 ary +(@ab-a)a +(I-b +e) = 99?-4 443 Eqsuccting dhe co-efPficients of a x 8 consents gA2=— 4] M43 aoe Oe 0 ake At @ab-a=—-G, when asa, Sb~3=—-9 [b=-1J —6b+3=-q Athen qe To [bal 7 @ Dheowem 4 hef fr A+B and 9: Bc be any roo Peines 08 Shen the following ave Fme (5) rf f and 9 cave Ome one -20 gof 1 also one—one Qi) af get yz I-I thefts I-| fi rp f and q are pato 30 qof 1s algo onto. (fv) af get ig omfo Then 9 1g Orfo. proof If FIA 7B and a Boe then goh Aa (i) To_pwve af 1g ome ONL (9h: AC comsidew , A ” ae A gost) = go (%) | a ($cay) = q($ea)) Cr ge FY Pc =P) (+ P os I) | = a) =O, = gf rg ome OTL 7 aa CA then Pea) PC) CB and | $a) = fC) fake ‘g’ on. b-S (iD Foke, gq tpeay) = Gh Coy) ea =y gf lay = 19), =y =O, 13 OME - OTK, (ii) Jaxe aca ,Since f 18 onto -) fCajy=b and 4:ince og tS onto =$ C = 4b) ¢ a Compequentiy , gohy =9[Fay = glb)=¢ os gc 13 onto, (iv) Since got 13 onefo. gore) = 9 = glb) wf , cle ag is omtey, Bs Iheorem @! hef PIA7B,9: B70 and h:C—*D be Shree Punchons then prove haf (hog) oP = holqof) proof i comsidew LHS 1-349 [2-qh) » {freoglof hi) 7 go & Pi / / =y (hog) F(9) 7 (hog) (Fem) = hog (4) @ y= fer) > A(GCy)) = hCz) (- zeqty)) = EHS Af BYch DP Now, comsidey RHS) fholqo#)] eS h( gotta) = h(9 (fer) = b(9¢4)) 07 = RHS oS ae Hence proved Pauncfrions faom z40Z gia 3% - heap =o f xis odd Defermine erarfy theft AY heh Pr guh be the defined by Peay =x-\ 7 mw ig even and h(a) =) { Fo¢gon)] (m) and (Gog)oh)ov and $o(qoh) =(Fo9) eh. Sol: - [ Zo(qon) }(%) =$lger 9) =F(q(rory) » =F * =F (3h) (= Shop| = 3h0U—-| | E} Ol) =a — a ppm reven : of ae odd hw =o S00 | =o [ fog Joh} Pog (btn?) : $(qnew) ae (a(n) shea) | Pp wie even -\ S-r. ee ee wo ddl Q ©. folqeh) = (fog) eh y [Camiin[rese be i 3.{0) = Sez Ext Aiea! 7 ek does ce tugs | (Gan a PTF gq ars j ants Fo cad, okher. [Camiin|rase pa p= det ~4a-f 2) es 1g t+ a y w= 7 = Tonnes Joh O) = xe [Camin] owe 1 rage. 1 Tee erin is: A als =e at ~ : ; a =X akge a trey yy ee Xi 73 6G =e ae TP fv be of A=>8 ia “Foe? Bs “ewe Bhd ait ~ Rar ee tie. > Nepal that | = obs tee e ~ F Fake O., a € A: < : 7 CT toweda Jay = a j al i gaan = gl FOOT. : 7% (dn POA) = ge Cx) « eh J = Uo G@d= + Tp C42) : no Ops & J ft ia te L 4 : Ts = 8. _p qoke aen, FEl=® 2 ob Take ; fla oe Coy) defee| ROP ; eRe AW 10: C2 airs | @uwextely PP Tone one aud onto PT | ees ae 0. b i Tae (oe. = st = ts Sr Go Py a Urtog : Soe an a P\ra) Ms 61329 NpF te Couto inh 0: gL Ban, ; pagen. ma “m2 6), QF 3 w he i | = : = Dorr p= {mmetf {1329-1 Z| i Be oan ZS a Te | = | Teal oe { a Roy sth ss } ef 35 . & B ic e aes Lig es alias aged Be BG wy = ease | va =. bi, Wa a aie me eet ee ee i J Relofrons I XK wer - one Madnx! A mabix weprese nfafion of refafion by assigning , a ie (aber 1g called Fhe 0 HP (an eR gelation mafrix of R. And 1k 12 denoted by Mp@ M(R) ext Bp =fa-b.c¥ » Bath 24 and Ref (ary (aa) (b.3) Cerf @) Diagraph of a Relaken: Dhe picforial wepresenfafion of the wefasion R afa Bef A 2 called directed graph @ digrraph of R. exr- Tf A={1a3} Raft) (Hay (2.2) (3.2) Rs Dhen Me= . b ~ hop, OWRD Node (Verfex) he each efement of Eage a Dvav an ar wPy catfed az eclge _ Farom ome Berfex fo anosher re vfex. Loop + (one inebreed and Lewminay ports a7 Same for tne neater) Dhe invbral ancl -bearminaf rderfexs ave © ys catled Qoop. omnnecfiog Bame Berber An-cegree: She MS ef edges enfering certlect Tm —deqr ss of hock —Oag Jeaving —tracf anderen. to ewertex IS ge ofex. a arertex he MO ug —degerce S ceqree of catted ore Problems :- - (a) het Ae {1a aay defn by aRy Pe @) wrtte clown R (iD Daw the drageaph of R (wy Defermne the indeqress and ouf-cle Yeofsces 1 the qrare. sol W) R= {ha (2.4) 5 w —_ ® 4 and R pe the vwefation on A ya et qs of @ [vethes [ala] ala. ernie Eafe] foster] ft] ef (@) hep Aa{1, a.a,af and bef R be tne relation on A defn by 2ARy WF Wy divides Yy” pootHen aly (a) wete down R as a 34 of ordered pair. (b) Devan Ine diag-raph of R. (© Deferrmine the im—degrees’ and uf degrees of the Weotices im-tnre diag-aph. Ang :-(a) “x divides y", aly ifr, Ne, ila, a 242 aja ala, 4/4 e pe{(y 1) Cosa (1a) reap (212) (208) (2.92) (ce) Vertex 4 a23a4 in-degree 12 2 A 3 out ~deqre er al | (3) Lek Ax {1.9.3.6} and R be Teles on A defred by aRb iff “a is anuthiple of b” @ Wwte down R. (6) Deaw +he aig~aph of R ©) Defermine im-degree and ou} —degeree ofthe Vesftees tm +ne geaph. A) pate down the relation ™mafaty, Solr Given A={1-9,3.4,6} @) a is multiple of b - r={(oy (3,1) ( 212)€3 11) (3:3) (Ae) 2) (4) (611) 06.2) (6. 3)(6,6)} & @ (© Verhees 41 2 3 4 6 An-deg ace se \ Ouf—cleqaee 1b @ a 3 4 @ M,= Hae ) R 1}]4 0000 | 4 ft 0.0 0 oo 0 400 ia 1 O10 €'4 440 @) Find +he velafion represented by-the ting raph given befow. Algo pare down if3 mafaix. o Solr: pa {agoyg (212) (2.3) (4.1) (4.424 Q Tl pee BeOoL oOoOPR CoPRFs 3 ! 0 Q A 3 oO 4 6 G) For A={vb, cele, fF find the vrejation and selation of mafrx. o @7 © 6+ 4) Reflexive Refation:— A relation R on a sefA ig gaid +o be weflexive rf (a,a) eR-for any aeA ex: Tf A={112137 Raftvy (22)(2. 9} A wrefafion R, ona Sef A ig gaid +o be iaveflexive rf faiaye R forany 2A ex: A=-{ : 2134 pe fii lay (af () Symmefnie Reledrom ?= A relation R om a eet A is Said £0 be Byrn ef 70 ep Cay b) ER hence (bayeR for at] abeA. exe: A={h 2134S R=f (11) (211) (ria) (3,1) Criadd @)_A-symmef-re Relasions- A relafion R om a Bd A is gaid to be By mmm ef 3c if (a-BJER buf (balZR for abe. a. acti ns}, pater (2) (24) af Herve (13)ER but (AER. :) (©) Ardi-symmefne Relafon A elation R on gf 18 gatd to be anfi-symmefaic if (arb)e R and (bea) €R Where a=b for a,beA ex t- Dats, 2134 LR= (1 (ai2af (6) Trransrtive Relafion :- A Relation R on ase A ig Zaid to be fransifive relation If (AbJER § (bic) ER then (ACJER for a,bic CA exi- Azg{1 2135 pifen (1,2) (2,1) (212) (13) (3) (3,3) (3.2)(2a)h (FJ Eqyuivalerce Relofrom:- A Relasion R om a BIA ig gaid +o be eqyetivrtence vefafion f if areplexive, sytamef rie and f-ransifive A ={1.2035 eftvi) (a) (2.3) (ua) Cat) (32) (2 ex: Ga) ket Ae Following rrefasions ON A. (i) gy wf an tnantsn y( 2230s) (29749 I] foe 2 4 _preblems {i 2 3A Defewmine the amafure of the | ) ! 0 70). 40 \ I ! | o 0 Gi) Ry 1% represented by the digvaph BY Sole: (i) RR, Replexive, Symmef ric and Prangishive. Ths a equiv lence crefafion. (ii) Rg aftr ly (3) (ea) (311) (3,2) (2.9 (314) Carr} Ry 13 Nef Reflexive , Ne} Symmetne , and 18 fransistive. iid = Rox f Cardy Care) (ard) (bre) Cerdy Rs ig teansihive. @ on-tne se zt a vefafion R 1s defined by aRp PP a divictes b. PT R 1x veflexive ,fvansrhs and anf rsyymmefore buf not symmefenc, som For any a7 bic eau “ @ divides b" (Give? y+ “a divides a” 43 kme > Re plexive, +} tq divides b’ bab b doce net divides a > Ris net : Bg romeh ne ~y a divides b! & b dividey a! then A=b =7 RB Gane e. + a divides b', b divides c +he a divides C jm => R we Pvansiftve. —————— ) het AHL 2B AF and Raf (tI) (12) C21) (2.2) (3.1)( 3.9(13)(41) (44) F, bea relation om A. Ts Roan equivalence rejafion. colm-W(aayer, WaeR SR vefferxive (ee (11) (2.270413) (a) (i) Cam)ER Jhen (baVER, WarbER =p Syrmmeme Here, (A,IJER but CLYDER Rs nefsymnetnc = = Hence Th 18 mof eqyurvatence vxefafion, @ heft S be the Sef of at] Now- th = da (cra) Rea) Rowe Bymmelve. (i) @m)Reeay § CA Reeg) Hun ad =be ofan ad= be & cfh=de ak = (§) =y af=be > af= eb ey (a,b) R (ef) Rs Lreansitive Hence th 38 an eqyseuvatence Refcefron. By 3) Fora fixed infeger N>1, PT the refafion . Congruenf- modufo mn” 1% an eqstivafence Tefafon on the ef of arf impegess Z. Solt- Given for arbez then A= b (moda) [o-o= x afa-b- (ab wa mutfsple of m (i) a= a (moda) he A-a=0 1% a -mutfiple of -. Ri Re plexive. (i) Wa bez QE b(mod n) = (a-p) 1 a mulfiple of 1 =y (b-a) 4 mutfiple of-n > b=almoda) 7 Rw Biypommeyne. Gv Uabcez a= b(moda) & b= C(mody) cb 4 oe cmufiple of 1 => @-b) +(b-o) = a-c 3 a mubfple of > a= c(mody = Row frvansifive Hence 12 eqyurvatence. Refection. ow Eqyeivatence class; hef R be an eqptivelence refatien ona Bet A and acA .dhen the Sef of atf those elements x of A which owe vrefated bya by R 1s catled -Jhe equivalence cfass of ce and if-1e cfenefed by [aj @ ROW re (a) -{xen/ Cain eR] exi- A=¢{ 12.35 Ref (riplngy (era) (3H oo fs) = {2} {3J={1! 33 @&) PARTITION OF A_SET: het A be a nron-empby Sep, then there exisk 00 empty Subse}s Ai, Aa, As, --- Ar of AL suchthet the fellowing 40 comdittong are Safisfied @ A= A\VALL-— vA, @) AsnaAj=f for tAj se By Az, ---Ak are Aisyorn ohen Sef pe A1,Ar,---Ay} 1 catled paafthien of A. i eee Bath) GP) Ay-t13, Ar ={233 Ag=t45 oa =t Dy P21 As f 1% paotiton pat J of A- (A) For the equivalence relation aL Cr (a2) Cast) (2129 (8049 (3) (3.9) (4 depimed om sep He {23:4} defermne te partion anducect, Solm- Given A={! 9.345 Raf Vlng7 Cay OD (3.3) (4-99} Now, Equivalence classes of A py atras ta) = {1a} (3) ={2AJ fa) = {24d Ta whreh 0) and [3] ave dishincf. : 0 fa ww the paofrtion ofA p {i 2 £3.03) ee son (3) So A= i 1213.43 cine fhe euivadence refas pe {tur (a2) (23) ca,ayta.sy(aaptarsy(s FF defined om A. Find the pookitien of A inducect bY R. soln: (1) ={ip JY ={2,35, (aja {235 weted ts} ={4-5} Tm whieh (19-2) aad (4) ave hs 2 po{oL Ly “A ={Od. 299 tad) ig tre parton of A PT eee ca (13 o{2az0test Qincf - ) he A= {112:3,4,5,6, +} Defined by a wefation R om A by p=f{car)/@-b) 1g divisible by 3) ST R & equivalence arelafion, Algo Lind +he pach Lion of A induced by R. SOM- Given, A={h 213,415, 6,4 Raf (any/Ca-b) ig Alvisible by 3} 2 Ref (4/1) (52) Co y9 (2129 913) (49) (81S) EO) (a4) (1.4) Cut) (ais) (216) (6D (419) (a4) (sh) re Acb (i) (a,aeR > RB Replexive. Woe (11) (22994) (515) (616) (419) ER. (iy Ca-DIER fil bay ER — Symmefanc area) Bymmedre GH faweR & (b.cVER then (AO) eR . Rig Pransi£tve R we equivalence qefapion. nee cfasses #8, Eqyuivale pati aas tsjo {a5 ta) = { 25} te) ={ 3/6) (3) =f{a6h (aja fi ab (ay = {aay Tr which Ci) 02) and (3) ave Ars tinef pa{tvt Ady, pafinsas, fod 49033 1s parfidien of A. @ het 4 ={ 1, 2,3,A 5}. Define a relation R on AXA by CapReamy PP WY = UY @) Verrfy haf Rs an egveurvalence relafion on AXA () Defermine the equivalence classes (C39), (2) and [01.1 (ii) Determine the paafition of AXA imduced by R. Solm- For any (14) E-AXA - We have WHY = UY re (ueyReayy - RY ove lexive S ferke Cary) (aa) AKA IP CrWRoa wy = Y= y+ Yp_ = WatY= UTY 7 (421%) R (arr) he: Aymmeprre: hashly Bake (Ai /%y) (42%) (a) & XA PB) Revi) Ord Car DReagivgy Fhe Oty, = Ate x,+Y2= TY =y tr +¥, = IMs = (x yy) R (5 +3) -. Rw transifive. Rw egyrivalence vefafion om AXA ) (og ={Ouyeava/rury = 1435 = { (9 (249 (30 [ (2:49) = {ry eaxa/ ary = 249} 2 f (2a) (oa) (3.99 (05) 9) ECan) ay rryad tl ={o} OY Come fon} (C123) ={Crycvy =(Gnd Cen ay) =f C39 C29 ng) = UE) = [C229] renay) = {Crap toa oatengh = [l2ay}= (C029) C2) (as) = f(s) (ag) (2aplen oD} = [n= (eg = Ley) | = { (ny) (easy Ja{ (259/52 (3.4) (495 = (tsa) = (3) =a [Cas = {ao (4.0) } = (6s) =e) [e) = {9 YJ = [(s4J (6.37) =LED -: parhifron of AXA PCCD Leas), eval trong)- (9 U9) (2 [49] Usd, () PARTIAL ORDER (‘posefs) A rvefafion R on a sef A 12 2afd to be pafiatt oaderx im velation on gef 4 Ae { (1) Rs aedlexive (i) R18 anfi—symmefare (i) Rw fvansibtive on A. A sef'A ioth a partial order R om eae cae a poset If 1% cemofed by plArR) © (AR) @) Flasse Diagvams She digraph of a padtal onder 1x called poset digram (D Hage diagram. Working Rate t (4) Elianinate Replexive edass (etrmmate doops) @ Suppose rnc Ai qreaph edg 68 from a to _b § edges Sarom btoc 8 qexen fren eliminate jne edge Prom_o fC. (3) Now Draw the digraph att edges poi ret 1n uprard Aicvecfion +40 Toeneecl to put ArDkKS 19 jne edges (rat vs understood ak edges ave upnard], preblemg ay Tet Ax{1, 8,3, 44 and Rea{ (1-1) (12) (2a) (204) (13) (213) (aap (104) (4a) }. Verret drab Rove ot pastas ovdex on AL anc alo pare down Hasse diagram of R. So|ns- Given Aa fnraay pain (29 (0) 3) (202: 99109 (9475. Herve, R Re plexivey Arehi- symmehox and 113 2 vansishve =y rt posed Hasse chagaam a a{trny tun (2) (2.490 13) (2,3)( 314) tea) wag} = car = (Hhef Nal 23,4} and R be defined as %Ra +f APG» PT (AiR) 2 el poses waite ut Hasse clam. Soft: Given Aa{h21 3.9} & mARy rf ay aR H{ (ri plraytnan (nay (212929) (29 (40) } Rw Replexive , Pacfi-syrmmelox and Pransibive Riz paofial order on Sef A Hasse drag rary R= {OC V013) Wray (22) (214) (373) ceay 2\. 2 4: Digrmph of R o Daw the hasse chiagrerm ryeprrese ving the x que divigow of 36 ' GT 121 18/,5E sola bef A={ 4» 34 , OF te afb =y coe I oo SeXy co . ho CO ycuancroarcragere) CAI 2) C0) C36) ove) (204926) coi) (2 Na 23e) (aa (s6)( 2,9) Caiv2) (48) (mae) . taray (2) (ar36) (66) (612) C0, 18) (6136) caxay Ca,18) (136) Crna) (12136) (isis) (18136) (36.36)f, nb we GokGa) (vy) aaph for & refafion om jhe Sef 13 ag Shown belo. @) he drag au {ra.3 68h yerrrrfy haf. (A WR) A posef and fotte down ifs Hasse oii x sol:- Qa CYC MeO cre) (202) (216) (2.8) | (213) (3,6) ce.8) Cab) } Rs replerive, Drfr-symmefry & +eansrefive Risa pada] ordey on A 6 8 ft} we A wey" Hasse crag vam. e: 6F Defeamine She amafmy of ne partial orden Whose Hasse raey-reim w oe S and draw ifg diag -vaph and mafn ae 3 I solm- af (1-1) (212) (313) (4a) (515) C2) (1.9) (414) Ch, (20) (25)J (2s as. Mp oo a a CO ae) a) Oe Oe AO 0. O40 sto On 070. 4: “ Rig a parfial order on A Hasse dragrams 1s HW () Defermine She amafaix of tne pachal ordey ihoge Hasse diagram 2 Uy and daavn Ps atigrraph and ancfox 3 a a solr Qe {11} (212929) (5.5) (112) (109) (HOP (2.4) (ais) } 4 a3 4 5 Mp= ao alo istee Optaeels oO Bo 0 Oe 410 oo 0 20 00. 01 Hn. (g) bef A={2.3,4,6,12} on A» define the ~refation R by aRp PP a divides b. pT Ra partial | order om A. Daan the Haase diagram for +hig Aefafion. Solmr- R= {ti YOuaynaycraycr "6 C112) GD (214) (216) (2012) (3, 13) (3+ 6) (3112) ( (£04) (4-12) (6:6) (6 yee} (A.QER, for at}atA,>R % aeflexve a divides b and b divides athen a divides C TR be berangi hive a divides b and b divides a then azb thence © R is avdr—symmeforc. wis Qa Te Viet paras onder om A- Hasse diagram for R, 1 (6) Draw the Hasse diagram ofthe rrefafion R on Batt 23 H5F Whose amafvix 12 as given below ss wn i ie =O OT o 0 0 0 SO|™- R= fay ean (3,4) (2.5) ait) (siS)} \ i ee) Oe v Saoa6 Cec 2cs) (213) Cag (245) Rha) a a ® Extremal elements rn posts consider a posef (AR) a) M Fm (2) _Mevernal_efemert of A AeA ww catlecl mMaxiamce| cleaner f jhaf ar Aa efemenf sfx MO efemenf rAa rn A Auch there ex @® _Mimmas element: An efemenf acA anal efemenf of A jhere exrsf “7° efermene- Ra. w cattect mini aba nA such-|hat (3) Upper bound : An efemenf acA w Bald +o be upper on of a 4ubsef B of ATL xRa for atl eR @ ower bound: Am elemenp aeA '% Baid -lo be Qower bounce of a Subse B of A. rf aRa for atl xEB © Leask upper bound : Dn element acA i said +0 be Leask upper bound of a Subsef p of A if i Gafisfies the following cond (i) a 18 am wppew bound of B. (i) TH aA we an upper bound of B.Ihen aRd 6) Greafest fower bound: Ob of a 3ubsef 1g gaid +o be q An element acA owing cond, BHA te safrsfres she foll 12 lower bound of B jer bound of B then A&Ra. (pe cl ) ee dad w an Qo Prob lems (a) bet pa{2, 3,4,6,8,19,24F .R be aRy Pf ry Lef pif, 6 1a} Find’ (i) AU upper bounds of B. (i) Atl Power pounds of B wae Gi) LuB of B OY Gp ose. olh:- R= fers) couyer) (208) (2412) cPi2u) (2%) (2,6) (Fy (3.20) CuYu) (4.8) (aia) (aaa) (6) C6412) (634) (8) (6124) (19 \2) (12124) (2020 2. Consider she flasse chiag-am of - pose (A a given below 4 a $ a e Q b f pe {odie} Sind @) all atpper bounds of B. (i) ath Power bounds ofp (iD) Ghe Jeast upper bound of B (iw) 4c qrrecdest Corre bound of 2. Sol - (7) Bz {cide} he wppry bounds ave Sirgen” (rn) Bafordey ts welafed +o c, ab ~ abit ave Lover bounds of B. (ii) Ohe apper bound AD is celafed to oper Upper bore q Fe os aaah Qeas} wp pre bound tua cand b veld ed by C ODB lower bounds (ww) he c 1 «GLB of B. Hw: 3. comsider the posef- whose Hasse drageram 18 Show eo of BatGdey J 9 goff.1. LOB © Bae. 7 GiB of B= a.

You might also like