[PDF] [PDF] Mathématiques discr`etes Chapitre 4 : relations binaires

View - Download [PDF] Mathématiques discr`etes Chapitre 4 : relations binaires

Previous PDF

Next PDF

U.P.S. I.U.T. A, D´epartement d"Informatique Ann´ee 2009-2010 Math ematiques discr`etes

Chapitre 4 : relations binaires

1. G´en´eralit´es

D´efinitionSoientE1,E2,...Endes ensembles. Unerelationn-aireest la donn´ee d"un sous-ensemble de

E

1×E2×...×En. Autrement dit, c"est la donn´ee d"un ensemble den-uplets (a1,a2,...,an).

Une mani`ere de repr´esenter une relationn-aire est de donner la liste desn-uplets dans un tableau ayant

ncolonnes. Cette notion est utilis´ee en informatique pour les bases de donn´ees relationnelles.

Exemple 1

SpectacleGenreLieu

West Side StoryMusiqueZ´enith

CarmenMusiqueCapitole

Don JuanTh´eˆatreCapitole

Julio IglesiasMusiqueZ´enith

Icin=....

Les ensembles consid´er´es sont

Dans ce cours, nous allons nous int´eresser au casn= 2, et lorsque les deux ensembles sont identiques.

D´efinitionSoitEun ensemble. On appellerelation binairesur l"ensembleEune proposition qui est vraie pour certains couples (x,y)?E×Eet fausse pour les autres. Legraphede la relation binaireR est l"ensembleGRdes couples (x,y)?E×Etels quexRy: G

R={(x,y)?E×E|xRy}.

La donn´ee du graphe d"une relation binaire est ´equivalente `a la donn´ee de la relation binaire.

Notation :SiRest la relation,x?Eety?E, on ´ecritxRysixest en relation avecy.

Exemples 2

•E=N, etxRyssiy= 2x.

•E=N, etnRmssindivisem.

•E=Z, eta≡b[5]ssib-aest un multiple de5.

1

Repr´esentations(lorsque l"ensembleEest fini)

Illustrons par l"exemple simple suivant, avecE={a,b,c}etGR={(a,a),(a,c),(c,b)}.

•liste dans un tableau (comme ci-dessus dans l"exemple 1, utilis´e en informatique mais rarement en

math´ematiques) EE aa ac cb

•diagramme cart´esien :

c b a a b c

•diagramme sagittal :

b c cba a

•matrice d"incidence :

a b c a b c( (1 0 10 0 00 1 0)

Exercice de cours 1.

On consid`ere l"ensembleE={0,1,2,3}et la relation binaireRdonn´ee par son graphe G

R={(0,1),(1,1),(1,0),(2,3),(3,3)}.

Donner la repr´esentation deRsous forme de liste, de diagramme sagittal et de matrice d"incidence.

Propri´et´es des relations binaires

D´efinitionSoitRune relation binaire sur l"ensembleE.

• Restr´eflexivesi?x?E, xRx.

• Restsym´etriquesi?x?E,?y?E,(xRy→yRx). • Restantisym´etriquesi?x?E,?y?E,(xRyetyRx)→x=y. • Resttransitivesi?x?E,?y?E,?z?E,(xRyetyRz)→xRz. 2

Exemples 3

E={a,b,c,d}.

Convention : pour simplifier on ne repr´esente qu"une foisEsur le diagramme sagittal. a ba b c d dc simplifi´e en a b c d - r´eflexive. a b c d sym´etrique. a b c d non sym´etrique carcRdmaisd?Rc. a b c d antisym´etrique : six?=yalors on n"a pas simul- tan´ementxRyetyRx. a b c d non antisym´etrique caraRdetdRaeta?=d. a b c d transitive. a b c d non transitive caraRb, bRcmaisa?Rc. 3

Exercice de cours 2.

On consid`ere la relation binaire donn´ee par le diagramme sagittal suivant. D´eterminer sa matrice d"in-

cidence et ses propri´et´es. dc b a

Exercice de cours 3.

SoitE={0,1,4,7,8,11}.

a) Repr´esenter le diagramme sagittal de la relation binaire d´efinie surEpar : xRy??x+yest pair. b) Etudier les propri´et´es deR.

2. Relation d"´equivalence

D´efinitionSoitEun ensemble etRune relation binaire surE. On dit queRest unerelation d"´equivalencesiRest r´eflexive, sym´etrique et transitive.

Exemples 4

•E=l"ensemble des ´etudiants de premi`ere ann´ee. x≂yssixetysont n´es la mˆeme ann´ee. C"est une relation d"´equivalence. •E=Z, soitmun entier positif non nul. Lacongruence modulomest d´efinie par : x≡y[m]ssiy-xest un multiple dem. C"est une relation d"´equivalence. D´efinitionSoitRune relation d"´equivalence surE.

Sia?E, on appelleclasse d"´equivalencedeal"ensemble de tous les ´el´ements deEqui sont ´equivalents

(parR) `aa. On la note aou a: a={x?E|xRa}.

Remarque :siaRbalors

a=b.

D´efinitionL"ensemble des classes d"´equivalence est appel´eensemble quotient, not´e parfoisE/R.

Ces notions sont utiles en arithm´etique et en cryptographie. 4

Exemples 5

•dansZ, pour la congruence modulo3:

0 ={···,-6,-3,0,3,6···}0 =3 =6...

1 ={···,-5,-2,1,4,7···}1 =4 =7...

2 ={···,-4,-1,2,5,8···}2 =5 =8...

l"ensemble quotient est not´eZ/3Z={0,1,2}.

•modulo2:

Z/2Z={0,1}.

0=ensemble des entiers pairs,

1=ensemble des entiers impairs.

Exercice de cours 4.

SoitE={3,4,9,10}etRla relation binaire d´efinie surEpar : xRy??x-yest pair. a) Montrer queRest une relation d"´equivalence. b) D´eterminer les classes d"´equivalence deR.

3. Relations d"ordre

D´efinitionSoitEun ensemble etRune relation binaire surE. On dit queRest unerelation d"ordresiRest r´eflexive, antisym´etrique et transitive.

Exemples 6

•E=l"ensemble des capitales europ´eennes.

xRyssixest avantydans l"ordre alphab´etique. Exercice de cours 5. On consid`ere l"ensembleE=Ndes entiers naturels, et on le munit de la relation binairen|m: "ndivisem" ssimest un multiple den.

V´erifier que c"est une relation d"ordre surE.

Exercice de cours 6. On consid`ere un ensembleE, on munitP(E) de la relation binaire?. V´erifier que c"est une relation d"ordre surP(E). D´efinitionSoitEun ensemble et?une relation d"ordre surE. Deux ´el´ementsxetydeEsontcomparablessix?youy?x.

On dit que la relation d"ordre?est unordre totalsi deux ´el´ements quelconques sont comparables. Dans

le cas contraire on dit que?est unordre partiel.

Exemples 7

•E=N?, ordre de la divisibilit´e.2?5et5?2: 2 et 5 ne sont pas comparables. C"est un ordre partiel. 5 D´efinitionsSoitEun ensemble,?une relation d"ordre surEetAune partie deE. - on dit quex?EmajoreA, ou quexest unmajorantdeAsi?y?A, y?x. - on dit quex?EminoreA, ou quexest unminorantdeAsi?y?A, x?y. - leplus petit ´el´ementdeAest (s"il existe) unx?Atel que?y?A, x?y. C"est un minorant de

Aqui appartient `aA. On le note p.p.e ou minA.

- leplus grand ´el´ementdeAest (s"il existe) unx?Atel que?y?A, y?x. C"est un majorant de

Aqui appartient `aA. On le note p.g.e ou maxA.

- laborne inf´erieuredeAest (s"il existe) le plus grand ´el´ement de l"ensemble des minorants deA.

On le note infA.

- laborne sup´erieuredeAest (s"il existe) le plus petit ´el´ement de l"ensemble des majorants deA.

On le note supA.

Exemple 8

L"ensemble des majorants deAest :

L"ensemble des minorants deAest :

infA ...,minA .... supA ..., etmaxA ... NB :supAet infAne sont pas n´ecessairement des ´elements deA. Exercice de cours 7. On consid`ere l"ensembleE={1,2,3,4,6,9,12,18,36}des diviseurs de 36 muni de la relation|.

PrenonsA={4,6}.

D´eterminer si la partieAadmet un max, un min. Quels sont les majorants deA? En d´eduire supA. Quels sont les minorants deA? En d´eduire infA.

Proposition :

sont ´equivalentes : ii) inf(x,y) =x, iii) sup(x,y) =y.

Diagramme de Hasse

Afin de mettre en ´evidence la hi´erarchie, on peut repr´esenter une relation d"ordre sur un ensemble fini

par une version simplifi´ee de son diagramme sagittal que l"on appellediagramme de Hasse: on ˆote du

diagramme sagittal les boucles (r´eflexivit´e) et toutes les fl`eches qui peuvent se retrouver par transitivit´e.

Exemples 9

ab c est remplac´e par acb

"on va du plus petit au plus grand, et on met une fl`eche entre deux ´elements s"il n"y a pas d"´el´ement

intercal´e entre les deux." 6

•E={1,2,3,4,6,9,12,18,36}muni de la relation|.

12 34
6918
1236
Exercice de cours 8. On consid`ereE={1,2,3,5,6,10,15,30}l"ensemble des diviseurs de 30, muni de la relation|.

V´erifier que son diagramme de Hasse est

30
6 15 12 10 3 5 D´efinitionUn ensembleEmuni d"une relation d"ordre est untreillissi : ?(x,y)?E2, sup(x,y) et inf(x,y) existent et sont dansE,

o`u sup(x,y) et inf(x,y) repr´esentent respectivement les bornes sup´erieure et inf´erieure de{x,y}.

On note aussi :

inf(x,y) =x?yet sup(x,y) =x?y.

Exemples 10

•(P(E),?) est un treillis,

car siA,B? P(E), alorsA?B=A∩B? P(E) etA?B=A?B? P(E) •On prendE=N?etxRysi et seulement six|y(xdivisey). (N?,|) est un treillis. x?y=PGCD(x,y) "le plus grand commun diviseur". x?y=PPCM(x,y) "le plus petit commun multiple".

•E={a,b,c,d,e,f}

On d´efinit la relation d"ordreRsurEpar le diagramme de Hasse suivant : ab cd ef En"estpasun treillis carb?cn"existe pas. En effetdetesont des majorants de{b,c}mais ne sont pas comparables. 7quotesdbs_dbs19.pdfusesText_25

[PDF] relation binaire pdf

[PDF] relation antisymétrique

[PDF] ensemble quotient exercice corrigé

[PDF] relation d'equivalence exercice corrigé pdf

[PDF] exercice relation d'equivalence

[PDF] chargaff adn

[PDF] ordre de grandeur de la voie lactée

[PDF] a+t / g+c

[PDF] niveaux d'organisation du vivant svt

[PDF] les différents niveaux d'organisation du vivant

[PDF] niveau d'organisation du vivant exercices

[PDF] les différents niveaux d'organisation des êtres vivants

[PDF] niveau d'organisation biologique

[PDF] décomposition d'un vecteur dans une base 1ere s

[PDF] diamètre du noyau d'un atome