Chapitre 4 - Relations binaires sur un ensemble.
Relations binaires sur un ensemble. De façon informelle une relation binaire sur un ensemble E est une proposition qui lie entre eux certains éléments de cet
RELATIONS BINAIRES
Définition (Propriétés des relations binaires) Soit une relation binaire sur E. • Réflexivité : On dit que est réflexive si : ?x ? E x.
1. Relations binaires 2. Relations déquivalence 3. Relations dordre
C5 : Relations. 1. Relations binaires. Définition. Une relation binaire R sur un ensemble E est une propriété portant sur les couples.
Relations binaires. Relations déquivalence et dordre
20 août 2017 Définition 1 : Une relation binaire ? définie sur un ensemble E est au choix : • une propriété qui relie ou non deux éléments x et y de E.
1 Mathématiques pour lInformatique Relations binaires Jérôme
Relations binaires. Jérôme Gensel. I) Relations binaires. 1. Généralités. Définition 1 : Une relation binaire d'un ensemble E vers un ensemble F est une
Relation
Une relation binaire R d'un ensemble de départ E vers un ensemble R qui décrit si un étudiant suit un cours régulièrement : GR = {(a Math)
1. Cours 3: Relations binaires sur un ensemble.
Cours 3: Relations binaires sur un ensemble. 1.1. Notion de relation: On appelle relation dVun ensemble A vers un ensemble B toute correpondance *.
Chapitre3 : Relations dordre
4.0 International ». https://www.immae.eu/cours/ Une relation binaire définie sur E est une propriété que chaque couple (x y) d'éléments de E est.
Mathématiques discr`etes Chapitre 4 : relations binaires
Exercice de cours 2. On consid`ere la relation binaire donnée par le diagramme sagittal suivant. Déterminer sa matrice d'in- cidence et ses propriétés.
Relations binaires entre ensembles - L2 Informatique - UFR S.A.T
Remarque : Lorsque E=F on parle de relation binaire définie dans l'ensemble E. Son graphe est une partie de. E2. Pr. Ousmane THIARE. Relations binaires entre
[PDF] 1 Relations binaires 2 Relations déquivalence 3 Relations dordre
Une relation binaire est une relation d'équivalence si et seulement si elle est réflexive symétrique et transitive Exemples Le parallélisme est une relation
[PDF] Relations binaires sur un ensemble
De façon informelle une relation binaire sur un ensemble E est une proposition qui lie entre eux certains éléments de cet ensemble
[PDF] RELATIONS BINAIRES - Christophe Bertault
Définition (Relation binaire sur un ensemble) On appelle relation binaire sur E toute partie de E × E Si est une telle relation la proposition (x y) ? sera
[PDF] Relations binaires Relations déquivalence et dordre
20 août 2017 · Définition 1 : Une relation binaire ? définie sur un ensemble E est au choix : • une propriété qui relie ou non deux éléments x et y de E
[PDF] Relation - Université de Toulouse
Relation binaire Une relation binaire R d'un ensemble de départ E vers un ensemble d'arrivée F est définie par une partie GR ? E × F
[PDF] 1 Cours 3: Relations binaires sur un ensemble
Cours 3: Relations binaires sur un ensemble 1 1 Notion de relation: On appelle relation dVun ensemble A vers un ensemble B toute correpondance *
[PDF] RELATION BINAIRE - Licence de mathématiques Lyon 1
On considère la relation entre deux éléments de définie par : La relation est-elle réflexive symétrique et transitive ? Allez à : Correction exercice 6 :
[PDF] CHAPITRE : Relations binaires - Les pages perso du LIG
25 fév 2018 · 2 Relations binaires : définitions 3 3 Propriétés classiques des relations binaires et interpétation sur les différentes représentations
[PDF] Mathématiques pour lInformatique Relations binaires Jérôme Gensel
Définition 1 : Une relation binaire d'un ensemble E vers un ensemble F est une partie R de E×F Si (xy)?R on dit que x est en relation avec y et on note
[PDF] Mathématiques discr`etes Chapitre 4 : relations binaires
Exercice de cours 1 On consid`ere l'ensemble E = {0 1 2 3} et la relation binaire R donnée par son graphe GR = {(0 1) (1 1) (1 0) (2 3) (3
C'est quoi un couple binaire ?
En mathématiques, une relation binaire entre deux ensembles E et F (ou simplement relation entre E et F) est définie par un sous-ensemble du produit cartésien E × F, soit une collection de couples dont la première composante est dans E et la seconde dans F. Cette collection est désignée par le graphe de la relation.Quand Dit-on qu'une relation est symétrique ?
Une relation R est symétrique si pour tout x,y ? E on a xRy si et seulement si yRx. Diagramme cartésien : symétrie par rapport à la diagonale. Diagramme sagittal : quand une fl?he va de a vers b, il y a aussi une fl?he de b vers a. Exemples : Quel que soit l'ensemble, la relation d'égalité = est symétrique.Comment montrer qu'une relation est une relation d'équivalence ?
Une relation R sur un ensemble E est une relation d'équivalence sur E si elle vérifie ces trois propriété :
Réflexivité : Pour tout de x de E, xRx.Symétrie : Pour tout (x,y) de E, si xRy alors yRx.Transitivité : Pour tout (x,y,z) de E si xRy et yRz alors xRz.- Plus formellement, une relation ? est dite antisymétrique si elle vérifie la condition suivante : (x ? y ? y ? x) ? x = y. En d'autres termes, si, dans une relation ? on a à la fois le couple (x, y) et son couple réciproque (y, x), alors x et y sont un seul et même élément.
Chapitre 4 : relations binaires
1. G´en´eralit´es
D´efinitionSoientE1,E2,...Endes ensembles. Unerelationn-aireest la donn´ee d"un sous-ensemble de
E1×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: GR={(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.
1Repr´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 cbdiagramme cart´esien :
c b a a b cdiagramme sagittal :
b c cba amatrice 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 GR={(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. 2Exemples 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. 3Exercice 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 aExercice 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. 4Exemples 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 deAqui 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 deAqui 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." 6E={1,2,3,4,6,9,12,18,36}muni de la relation|.
12 346918
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
306 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 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