[PDF] Exercices Mathématiques Discr`etes : Relations

View - Download Exercices Mathématiques Discr`etes : Relations

Previous PDF

Next PDF

Exercices Mathematiques Discretes : Relations

Relations binaires

Rb1Soi entA=f0;1;2;3;4getB=f0;1;2;3gdeux ensembles. Ecrire explicitement les couples (a;b)2Rou (a;b)2Rsi et seulement si : a=b ; a+b= 4; a < b ; pgcd(a;b) = 1; ppcm(a;b) = 2; adiviseb: Rb2D eterminersi les r elationssuiv antes,d eniessur un ensem blede p ersonnes,son tr e exives, symetriques, antisymetriques et/ou transitives. (a) ( a;b)2R1ssiaest plus grand queb. (b) ( a;b)2R2ssiaetbsont nes le m^eme jour. (c) ( a;b)2R3ssiaa le m^eme prenom queb. (d) ( a;b)2R4ssiaetbont un grand-parent commun. Rb3D eterminersi les relations suiv antes,d eniessur R, sont re exives, symetriques, anti- symetriques et/ou transitives. (a) ( a;b)2R1ssia+b= 0. (b) ( a;b)2R2ssiab2Q. (c) ( a;b)2R3ssiab0. (d) ( a;b)2R4ssi (a= 1)_(b= 1). Rb4D eterminersi les relations suiv antes,d eniessur Z, sont re exives, symetriques, anti- symetriques et/ou transitives. (a) ( a;b)2R1ssia=b2. (b) ( a;b)2R2ssia7b. (c) ( a;b)2R3ssia+ 1 =b. (d) ( a;b)2R4ssiab= 0. Rb5Soi tA=f1;2;3;4;5gun ensemble etR=f(1;2);(2;3);(3;4);(4;5);(5;1)gune relation surA. CalculerR2,R3,R4etR5. En deduireRn, pourn1. RepresenterR,R2par un graphe etR3par une matrice.

Rb6Prou verqu esi Rest une relation re

exive (resp. symetrique), alorsRn(n1) est egalement re exive (resp. symetrique). Rb7Soi tAun ensemble etRA2une relation binaire surA. On dit queRestirre exive si et seulement si pour tout elementa2A,an'est pas en relation avec lui-m^eme. (a)

Donner un exemple de relation irr e

exivesur Z. (b)

T outerelation non r e

exiveest-elle irr e exive?Justier. (c)

S iRest irre

exive,R1est-elle irre exive? Justier. (d)

Si Rest irre

exive,Rnest-elle irre exive quel que soitn1? Justier. 1 (Examen juin 2008) Rb8Soi t2 Zl'ensemble des parties deZetR1la relation binaire denie par : R

1=f(X;Y)22Z2Zjil existef:X!Yinjectiveg:

(a) Soit X1=fx2Zjx31g, trouvezY122Ztel queY16=X1et (Y1;X1)2R1. (b) So itX2=fx2Zjx52g, trouvezY222Ztel queY26=X2et (X2;Y2)2R1. (c)

La relation R1est-elle (i) re

exive? (ii) transitive? (iii) symetrique? (iv) anti- symetrique? (Examen juin 2010)

Relations fonctionnelles

Rf1P armiles relations suiv antes,lesquelles son tfonctionnelles ? (a)f(x;y)2R2jy=jxjg. (b)f(x;y)2R2jx=jyjg. (c)f(x;y)2R2jxy= 1g. (d)f(x;y)2R2j3x+ 2y= 7g. Rf2Don nerun exemple de relation fonctionnelle sur Nqui est re exive. Rf3Don nerun exemple de relation fonctionnelle sur Nqui est symetrique.

Relations d'equivalence

Re1P armiles relations suiv antessur f1;2;3g, lesquelles sont des relations d'equivalence? (a)R1=f(1;1);(2;2);(3;3)g. (b)R2=f(1;1);(2;2);(3;3);(1;2);(2;1)g. (d)R4=f(1;1);(3;3);(1;3);(3;1)g. Re2P armiles relations binaires sur un ensem blede p ersonnesde l'exer ciceRb2, lesquelles sont des relations d'equivalence? Re3P armiles relations binaires sur Rde l'exerciceRb3, lesquelles sont des relations d'equi- valence? Re4P armiles relations binaires sur Zde l'exerciceRb4, lesquelles sont des relations d'equi- valence? Re5D ecrirela partition e ngendreepar la r elationd' equivalencesur Zdenie parR= f(a;b)ja5bg. Re6Prou verque si Rest une relation d'equivalence, c'est aussi le cas deR1. 2 Re7Representation des rationnels.Pour eviter de representer le rationnel13 par 0:3333:::, on peut l'encoder via le couple (1;3). Cependant, cette representation comporte un inconvenient. En eet, par exemple, les couples (1;3) et (2;6) representent le m^eme rationnel ( 13 =26 ). Donner une relation d'equivalence surZN0qui permet de regler ce probleme. Que represente alors le quotient deZN0par cette relation d'equivalence? Re8So itA=Z2etRla relation binaire surZ2denie par :

R=f((a1;b1);(a2;b2))ja1+b1=a2+b2g:

(a)

Pro uverque Rest une relation d'equivalence.

(b)

Repr esenterla classe d' equivalencede (1 ;1).

(c)

Ca lculerle quotien tde Z2parR.

Re9S oitA=R2etRla relation binaire surR2denie par :

R=f((x1;y1);(x2;y2))jx1y1=x2y2g:

(a)

Pr ouverque Rest une relation d'equivalence.

(b)

Repr esenterla classe d' equivalencede (0 ;0).

(c)

Rep resenterla classe d' equivalencede (1 ;1).

(d)

Calculer le quotien tde R2parR.

Re10Soit A=R[x] l'ensemble des polyn^omes a coecients reels, deni par :

R[x] =fanxn++a0jn2Netai2Rpour 0ing:

(a) O nconsid erela relation binaire R1surR[x] denie par : R

1=f(p1;p2)jp1(0) =p2(0)g:

i.

Pr ouverque R1est une relation d'equivalence.

ii.

C alculerle quotien tde R[x] parR1.

(b) On consid erela relation binaire R2surR[x] denie par : R

2=f(p1;p2)jp1(i) =p2(i);oui2=1g:

i.

Pr ouverque R2est une relation d'equivalence.

ii.

C alculerle quotien tde R[x] parR2.

Re11On consid erela r elationbinaire R1Z2denie par (a;b)2R1si et seulement si a 2=b2. (a) Pr ouverque R1est une relation d'equivalence surZ. (b)

Calculer la classe d' equivalencede 0 p ourR1.

(c)

Ca lculerla classe d' equivalencede 2 p ourR1.

(d)

Calculer le quotien tde ZparR1.

(Examen juin 2009) 3 Re12La relation R2=f(X;Y)jX; YNetX\Y6=;gest-elle une relation d'equivalence sur les parties deN?(Examen ao^ut 2009) Re13S oitF=ff:R!Rg. Pour toutf;g2F, on denit la relation binairesurFde la facon suivante : fg, 9A2N;8x2R(jxj> A)f(x) =g(x)): (a)

Don nezdeux fonctions f;g2Ftelles quef6=getfg.

(b) La relation est-elle une relation d'equivalence surF? (Examen juin 2010) Re14D ecidezsi l'a rmationsuiv anteest vraie ou fausse. (Examen ao^ut 2010) La relation binaireRZ2denie parR1=f(a;b)2Z2tel qu'il existeppremier oupjaetpjbg est une relation d'equivalence. Re15S oitSl'ensemble des fonctions deZdansZ, i.e.S=ff:Z!Zg. EtR2S2la relation binaire denie par : (f;g)2R2si et seulement sifx2Zjf(x)6=g(x)gest ni: (a)

Do nnezdeux fonctions f6=g2Stelles que (f;g)2R2.

(b) Prouv ezqu eR2est une relation d'equivalence surS. (c) Soi tf0la fonction denie parf0(x) = 0 pour toutx2Z. On note [f0] la classe d'equivalence def0pourR2. Prouvez qu'il existe une fonction injectiveF:Z! [f0]. (Examen ao^ut 2010)

Relations d'ordre

Ro1P armiles relations suiv antessur f1;2;3g, lesquelles sont des relations d'ordre? (a)R1=f(1;1);(2;2);(3;3)g. (b)R2=f(1;1);(2;2);(3;3);(1;2);(1;3)g. (c)R3=f(1;1);(2;2);(3;3);(1;2);(2;3)g. (e)R5=f(1;1);(2;2);(3;3);(1;2);(2;1)g. Ro2So it( A;R) est un ensemble ordonne, prouver que (A;R1) est un ensemble ordonne. Ro3T rouverdeux elementscompar ableset deux elementsincompara blesdans les deux ensembles partiellement ordonnes ci-dessous : (2 f0;1;2g;) ; (f1;2;4;6;8g;j):

Ro4So itRune relation binaire surN2denie par :

(a1;b1)R(a2;b2) si et seulement si (a1a2)^(b1b2): Prouver queRest un relation d'ordre surN2. Cette relation d'ordre est-elle totale? Justier. Representer l'ensemble des couples (a;b)2N2tels que (a;b)R(3;4), ainsi que l'ensemble des couples (a;b)2N2tels que (3;4)R(a;b). 4 Ro5A c haquenaturel n2N, on peut associer son ecriture en base 2 (par exemple 5 = (101)

2). On suppose 0<1, classer selon l'ordre lexicographique les elements suivants :

0;01;101;1101;1011;1001;1000;1010:

Associer a chaque element ci-dessus le naturel qu'il represente en base 2. Comparer l'ordre naturel surNet l'ordre lexicographique sur les representations en base 2 des naturels. Ro6T racerles diag rammesde Hasse d esensem blesordonn esci-de ssous: (f1;2;3;4;5;6g;j) ; (f2;3;5;7;11g;j) ; (f1;2;4;8;16g;j) ; (f1;3;5;7;15;30;35g;j): Ro7R epondreaux questions suiv antesp ourc hacundes ordres partiels repr esentespar les diagrammes ci-dessous :

1. Trouver les elements maximaux. 6. Trouver le supremum defa;b;cg.

2. Trouver les elements minimaux. 7. Trouver les bornes inf. deff;g;hg.

3. Existe-t-il un maximum? 8. Trouver l'inmum deff;g;hg.

4. Existe-t-il un minimum? 9. Trouver les bornes sup. deff;g;hg.

5. Trouver les bornes sup. defa;b;cg. 10.Trouver le supremum deff;g;hg.bacdefihgjklm

bacdefihgjklm bacdefihgjklm Ro8Do nnerun ensem bleordonn ea vecun maxim ummais pas de minim um. Ro9D eterminersi ( N0;j) a un maximum? un minimum? Ro10D eterminersi les diagrammes de Hasse ci-dessous repr esententun treilli s.abd cefg aceg bdfh aceg bdfhj 5 Ro11D eterminersi les ensem blesordonn essuiv antsson tdes treillis : (f1;3;6;9;12g;j) ; (f1;5;25;125g;j) ; (Z;): Ro12Pr ouverque tout sous-ensem bleni non vide d'un treillis a un inm umet un suprem um. Ro13Pr ouverque si ( A;R) est un treillis, alors (A;R1) est aussi un treillis.

Ro14Pr ouverque tout ordre total est un treillis.

Ro15Pr ouverque tout treillis ni a un maxim umet un minim um. Ro16Do nnerun exemple de treillis inni sans maxim um,ni minim um. Ro17Do nnerun exemple de treillis inni a vecun maxim umet sans minim um. Ro18Do nnerun exemple de treillis inni sans maxim ummais un minim um. Ro19Do nnerun exemple de treillis inni a vecun maxim umet un minim um. Ro20V erierque N2muni de l'ordre lexicographique forme un ensemble bien ordonne. Ro21T rouverun ordre tot alcompatible a vecl'ordre de d ivisionsur f1;2;3;6;8;12;24;36g. Ro22T rouverun ordre total compatible a vecles ordres donn espar les diagrammes d eHasse de la questionRo10. Ro23S oitAun ensemble et4A2une relation binaire surA. On dit que4est unpre-ordre surAsi elle est re exive et transitive. (a) Don nerun exemple de pr e-ordrequi n'est pas un ordre. (b) S oitAun ensemble et4un pre-ordre surA. Prouver que la relation binaire denie ci-dessous est une relation d'equivalence surA: =f(a;b)j(a4b)^(b4a)g: (c) On d enitla relation binaire sur le quotient deAparde la facon suivante : [a][b] si et seulement sia4b: Prouver queest bien denie (i.e.8x2[a];8y2[b] ([a][b]))(x4y)). (d) Pr ouverque est une relation d'ordre sur le quotient deApar. Ro24Re presenterle dia grammede Hasse d'un ensem bleordonn eni qui p ossedeun mini mum mais pas de maximum et qui possede trois elementsa1; a2; a3tels que supfa1;a2;a3g n'existe pas. Un tel ensemble peut-il ^etre un treillis?(Examen juin 2008) Ro25So itC=ff:R!Rjdom(f) =RgetRla relation binaire denie par :

R=f(f;g)2CCj 8x2Rf(x)g(x)g:

(a)

Don nerdeux fonctions f; g2Ctelles que (f;g)2R.

(b)

Pr ouverque Rest une relation d'ordre surC.

(c)Rest-elle une relation d'ordre totale? (Examen juin 2008) 6 Ro26T racerle d iagrammede Hasse de (2 f2;3;5g;).(Examen juin 2009) Ro27S oitC=ff:R!Rjdom(f) =RgetR2la relation binaire denie par : R

2=f(f;g)2CCj 8x2Zf(x)g(x)g:

(a)

Don nerdeux fonctions f; g2Ctelles que (f;g)2R2.

(b)R2est-elle une relation d'ordre surC? (Examen juin 2009) Ro28D eterminersi la relation binaire R3Z2Z2denie ci-dessous est une relation d'ordre : (a1;b1)R3(a2;b2) si et seulement si (a1a2) ou (b1b2): (Examen juin 2009) Ro29D ecidersi l'a rmationsuiv anteest vraie ou fausse. Justier. SoitAun ensemble, un pre-ordre surAest une relation binaire re exive et transitive. Tout pre-ordre surAest aussi un ordre surA.(Examen juin 2009) Ro30La relation R1=f(x;y)2R2jx2y2gdenit-elle un ordre surR? (Examen ao^ut 2009) Ro31S oitE=f0;1g3etR3une relation binaire surEdenie par : (a1;b1;c1)R3(a2;b2;c2) si et seulement sia1a2etb1b2etc1c2: (a) Pro uverque R3est un ordre surEet tracer le diagramme de Hasse de (E;R3). (b) L' ensembleor donne( E;R3) possede-t-il un maximum? (Examen ao^ut 2009) Ro32S iX6=;est un ensemble ni, on note 2Xl'ensemble des parties deX. Etant donne A22X, on notejAjle nombre d'elements deA. SoitRX2X2Xla relation binaire denie par : (A;B)2RXsi et seulement sijAj jBj;ouA;B22X: Decidez si les armations suivantes sont vraies ou fausses. (a) Q uelque soit X6=;ensemble ni, la relationRXest une relation d'ordre. (b) Q uelque soit X6=;ensemble ni, la relationRXn'estpasune relation d'ordre. (c) Quel que soi tX6=;ensemble ni, la relationRXn'estpasune relation d'equivalence. (Examen juin 2010) Ro33S oitl'ensem bleE=f0;1;2g, on munitE2de la relation binaireR2denie par : R

2=(a1;b1);(a2;b2)2E2E2ja1a2etb1b2:

(a) Pro uvezque la relation R2est une relation d'ordre surE2. (b)

T racezle d iagrammede Hasse de ( E2;R2).

(Examen juin 2010) 7 Ro34S oit = fa;bg. Un mot ni de longueurnsur est une fonctionw:f0;:::;n1g !. Dans ce cas, on noteDom(w) l'ensemblef0;:::;n1get l'ensemble des mots nis sur . Un mot inni sur est une fonctionw:N!. Dans ce cas, on noteDom(w) l'ensembleNet !l'ensemble des mots innis sur . On dira qu'un motw1(ni ou inni) est unsous-motd'un motw2(ni ou inni) si et seulement si les deux conditions suivantes sont satisfaites :

Dom(w1)Dom(w2);

il existeF:Dom(w1)!Dom(w2) telle queFest strictement croissante1etw1(n) = w

2(F(n)), pour toutn2Dom(w1).

On notew1w2siw1est un sous-mot dew2.

(a) On consid ereles mots nis w1:f0;:::;3g ! etw2:f0;:::;5g ! denis ci-dessous. w

1(n) =(

asin= 0;1 bsin= 2;3;w2(n) =( asin= 0;2;4 bsin= 1;3;5 Le motw1peut ^etre represente par la suitew1(0):::w1(3) =aabbet le motw2 par la suitew2(0):::w2(5) =ababab. Montrer quew1est un sous-mot dew2(i.e., w 1w2). (b) Do nner(si p ossible)un mot ni w12et un mot inniw22!tels quew1w2. (c) Donner (si p ossible)un mot inni w12!et un mot niw22tels quew1w2. (d)

La relation est-elle un ordre sur ?

Si oui, s'agit-il d'un ordre total?

Si non, trouver un sous-ensemble inni de ordonne par. (e)

La relation est-elle un ordre sur !?

Si oui, s'agit-il d'un ordre total?

Si non, trouver un sous-ensemble inni de !ordonne par. (f) On note a!(resp.b!) le mot inniw:N! tel quew(n) =a(resp.b) pour toutn2N. On note (ab)!le mot inniw:N! tel quew(n) =asinest pair etw(n) =bsinest impair. La relationest-elle un ordre sur l'ensemble

X=fa;b;a!;b!;(ab)!g?

Si oui, tracer le diagramme de Hasse associe a (X;). Si non, donner un sous-ensemble deX, contenant 3 elements, sur lequelest un ordre.

On notew1w2si et seulement siw1w2etw2w1.

(g) La relation est-elle une relation d'equivalence sur ? Si oui, calculer la classe d'equivalence du motaabb. Si non, donner un sous-ensemble inni de sur lequelest une relation d'equivalence. (h)

La relation est-elle une relation d'equivalence sur !?1. On dit qu'une fonctionf:N!Nest strictement croissante si et seulement si8x;y2Nx < y)

quotesdbs_dbs35.pdfusesText_40

[PDF] relation d'équivalence et classe d'équivalence

[PDF] exo7 relation binaire

[PDF] liste des verbes d'action

[PDF] liste des verbes d'état cm2

[PDF] exercice sur les verbes d'état et d'action cm2

[PDF] les verbes d'action pdf

[PDF] film éthique et culture religieuse

[PDF] les verbes d'état pdf

[PDF] tous les verbes d'état

[PDF] liste des verbes attributifs

[PDF] surclassement pop corn c'est quoi

[PDF] upload file magazines gaumont 262 web

[PDF] exercice de maths rapport et proportion

[PDF] gaumont pathé

[PDF] montrez que la productivité globale des facteurs est source de croissance économique.