[PDF] [PDF] Relation - Université de Toulouse





Previous PDF Next PDF



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.



Chapitre 4 - Relations binaires sur un ensemble.

Une relation binaire R sur un ensemble E qui est réflexive transitive et antisymétrique est appelée relation d'ordre sur E. La plupart des relations d'ordre 



RELATION BINAIRE

Relation binaire. Pascal Lainé. 3. Exercice 11 : Soient un ensemble fini non vide et un élément fixé de . Les relations définies ci-dessous sont-elles des.



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 x. • Transitivité 



Relations binaires. Relations déquivalence et dordre

20 Aug 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 d'arrivée F est définie par une partie GR ? E × F. Si (xy) ? GR



Table des mati`eres

Les relations binaires sont classées en fonction de leur propriétés. Définition 1.1.2 Une relation binaire R sur E est dite. - réflexive si ?a ? E a R a



relations-binaires.pdf

Relations d'équivalence. Exercice 1 [ 02643 ] [Correction]. Soit R une relation binaire sur un ensemble E à la fois réflexive et transitive.



decomposition rectangulaire optimale dune relation binaire

Mots-des: Strategie de decomposition rectan^aire relation binaire



[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] RELATION BINAIRE - Licence de mathématiques Lyon 1

Relation binaire Pascal Lainé 1 RELATION BINAIRE Exercice 1 : Soit { } et la relation binaire sur dont le graphe est {( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )}



[PDF] RELATIONS BINAIRES - Christophe Bertault

Christophe Bertault — Mathématiques en MPSI RELATIONS BINAIRES Dans tout ce chapitre E est un ensemble quelconque 1 RELATIONS BINAIRES SUR UN ENSEMBLE



[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] Relations binaires - Xiffr

On définit une relation binaire R sur G par : xRy ?? xy?1 ? H Montrer que R est une relation d'équivalence et en décrire les 



[PDF] Relation - Université de Toulouse

Définition 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] Relations binaires sur un ensemble

Définition et exemples de relation binaires sur un ensemble 0 1 1 Définitions 1 Sur tout ensemble E l'égalité = sur E est une relation binaire



[PDF] Relations binaires sur E Relations d´equivalence Relations dordre

Relations d'ordre 1 Relations binaires de E dans E : représentations propriétés 1 Exercice corrigé en amphi ? est une relation binaire sur un ensemble 



[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 * qui lie 

  • Qu'est-ce qu'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.

  • 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.

  • 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.
  • 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.

Relation

Université de Toulouse

Année 2020/2021

1 / 35

Relations

Relations2 / 35

Définition

Relation binaire

Unerelation binaireRd"un ensemble de départEvers un ensemble d"arrivéeFest définie par une partieGREF. Si(x;y)2GR, on dit quexesten relation avecyet l"on notexRy.

SiE=Fon dit queRest unerelation internesurE.Exemples :SoientA=fa;b;c;d;egl"ensemble des élèves etB=fMath;Info;Ang;Physg

l"ensemble des cours. On peut définir les relations suivantes :Rqui décrit si un étudiant suit un cours régulièrement :

G

R=f(a;Math);(a;Phys);(b;Info);(c;Ang);(d;Ang);(e;Math);(e;Ang)gla relationSdécrit si un étudiant a acheté un cadeau à un autre étudiant définit par

G

S=f(b;a);(a;a);(c;a);(a;d);(d;c)gRelations3 / 35

Mode de représentation

Diagramme cartésien et matrice de relationRMathPhysAngInfo aVV bV cV dV eVVSabcde aV bVV cVV dV e

Diagramme sagittal

a b c d eMathPhysAngInfoa bcde

Relations4 / 35

Relation fonctionnelle

Une fonctionf:E!Fassocie a chaque élément deEau plus un élément deF. On peut alors définir la relationRfdéfinie par le graphe G

Rf=f(x;f(x)) :x2Eg EF:

Réciproquement, pour une relationRtelle que pour toutx2Eil y a au plus uny2FvérifiantxRyalors on peut lui associer une fonctionftelle quef(x) =ysi et seulement sixRy. On dit queRest unerelation fonctionnelle.Relations5 / 35

Relation réflexive

Réflexivité

Une relationRestréflexivesi pour toutx2Eon axRx:Diagramme cartésien : la diagonale doit être notée.

Diagramme sagittal : chaque sommet admet une boucle. 123
123
1VVV 2VV 3V Exemples :Quel que soit l"ensemble, la relation d"égalité=est réflexive. Sur?, la relation est réflexive, maisRelation symétrique

Symétrie

Une relationRestsymétriquesi pour toutx;y2Eon axRysi et seulement siyRx:Diagramme cartésien : symétrie par rapport à la diagonale. Diagramme sagittal : quand une flèche va deaversb, il y a aussi une flèche debversa.123 123
1VV 2V 3V Exemples :Quel que soit l"ensemble, la relation d"égalité=est symétrique. Sur?, la relation est n"est pas symétrique.

La relation

lsurAest symétrique.Relations7 / 35

Relation transitive

Transitivité

Une relationResttransitivesi pour toutx;y;z2Etel quexRyetyRz alors nécessairement on axRz.Diagramme sagittal : tout chemin qui part d"un sommetset va à un sommets0en suivant la direction des flèches admet un raccourci, c"est

à dire un chemin de longueur un.1

2341234

1V 2VVVV 3 4V Exemples :Quel que soit l"ensemble, la relation d"égalité=est transitive. Sur?, la relation est transitive. La relation "est le père de" n"est pas transitive.

Relations8 / 35

Relation antisymétrique

Antisymétie

Une relationRestantisymétriquesi pour toutx;y2EvérifiantxRyet yRxalors on ax=y:1

2341234

1V 2VV 3VV 4VV

Exemples :Sur?, la relationest antisymétrique.

La relation

lsurAn"est pas antisymétrique.Relations9 / 35

Relations d"équivalence

RelationsRelations d"équivalence10 / 35

Définition et exemples

Définition

Une relation binaire définie sur un unique ensembleEest unerelation

d"équivalencesi elle est réflexive, symétrique et transitive.Exemples :Par définition, pourx;y2?, on notexy[modn], lirexest congru àymodulo

n, si et seulement s"il existek2?tel quexy=kn. On a défini une relation d"équivalence sur

?car on peut vérifier :Réflexivité :xx[modn]carxx=0:net 02?.Symétrie :sixy[modn]alors il existek2?tel quexy=k:n, on a donc

yx=k:netk2?d"oùyx[modn].Transitivité :sixy[modn]etyz[modn]alors il existek;k02?tels que xy=k:netyz=k0:n. Ainsixz=xy+yz= (k+k0):n. On en déduit que xz[modn]RelationsRelations d"équivalence11 / 35

Définition et exemples

Définition

Une relation binaire définie sur un unique ensembleEest unerelation d"équivalencesi elle est réflexive, symétrique et transitive.Exemples :

Sur n"importe quel ensemble la relation=est une relation d"équivalence..Sur l"ensemble des motA, la relationlest une relation d"équivalence.Sur l"ensemble des personnes, la relation "a le même âge que" est une relation

d"équivalence. Des personnes liées appartiennent à la même tranche d"âge.Sur l"ensemble des triangles, la relation "a les mêmes angles que" est une relation

d"équivalence. Des triangles liés par cette relation sont dits semblables.La relationRdéfinie sur?rf0gparxRysi et seulement sixy>0 est une relation

d"équivalence. Deux réels liés par cette relation ont le même signe.

RelationsRelations d"équivalence12 / 35

Classes d"équivalence et partition

Classes d"équivalence

SoitRune relation d"équivalence sur un ensembleE. Laclasse d"équivalenced"un élémentx, notéCl(x), est l"ensemble des éléments de

Equi sont en relation avecx. Autrement dit

Cl(x) =fy2E:xRyg:Proposition

Une classe d"équivalence n"est jamais vide.

L"intersection de deux classes d"équivalence distinctes est vide.

RelationsRelations d"équivalence13 / 35

Classes d"équivalence et partition

Partition

SoitEun ensemble, la famille d"ensembles(Ai)i2Iindexée parIest une

partitionsi :l"union des(Ai)i2Iest égale àE, c"est à direE=[i2IAi,deux éléments de(Ai)i2Idistincts sont disjoints, c"est à dire que si

i6=jalorsAi\Aj=;.Théorème Etant donné une relation d"équivalence sur un ensemble, les classes d"équivalences forment une partition.

RelationsRelations d"équivalence14 / 35

Ensemble quotient

Ensemble quotient

SoitEun ensemble munit d"une relation d"équivalenceR. L"ensemble quotient est l"ensemble des classes d"équivalence de tous les éléments deE.

On le noteE=R.Théorème

Etant donné une relation d"équivalenceRsurE, la fonction suivante est surjective : f:E!E=R x7!Cl(x)RelationsRelations d"équivalence15 / 35

Relations d"ordre

RelationsRelations d"ordre16 / 35

Définition

Définition

Une relation binairesur un ensembleEest unerelation d"ordresi elle est réflexive, transitive et antisymétrique. Autrement dit : réflexive :on a xxpour toutx2E. transitive :si xyetyzalorsxz. antisymétrique :si xyetyxalorsx=y.Un ordre esttotalsi pour tous élémentsx;y2Eon axyouyx. Un

ordre est ditpartielpour souligner qu"on n"a pas forcément cette propriété.RelationsRelations d"ordre17 / 35

Exemples d"ordres sur les nombres

etsont des relations d"ordre total sur?qui s"étendent à?,?

ou?.ne sont pas des relations d"ordre sur?.Sur?la relationadiviseb, notéeajb, est une relation d"ordre mais

n"est pas total. On rappelle queadivisebs"il existek2?tel que b=ak. réflexive :on a xxpour toutx2?. transitive :si xdivisey(c"est à dire il existektel quey=k x) et ydivisez(c"est à dire il existektel quez=k0y) alors z=k0y= (k"˛)xdoncxdivisez. antisymétrique :si xyetyxalorsx=y.RelationsRelations d"ordre18 / 35 Exemples d"ordre ordres sur les parties d"un ensemble SoitEun ensemble l"inclusion, notée, est une relation d"ordre sur l"ensemble des partiesP(E)qui n"est pas totale. réflexive :on a AApour toutA2 P(E). transitive :si ABetBCalorsAC. antisymétrique :si ABetBAalorsA=B.RelationsRelations d"ordre19 / 35

Ordres sur les mots

Il existe différentes notions pour ordonner l"ensemble des motsA:La relationuest préfixe dev, notéeuvperdvet définit par9w2 A

tel quev=u:w, est une relation d"ordre qui n"est pas totalSoitun ordre total surAon définit l"ordre lexicographiquesur

A ulexv()8 >:upréfixe dev ou bien

9m2?tel queu1:::um=v1:::vmetum+1vm+1

C"est une relation d"ordre total surA. Par exemple : alexfa,poulelexpoulet,avionlextrain, livraisonlexlivre,footlexfort.RelationsRelations d"ordre20 / 35

Mode de représentation

123123

1VVV 2VV 3V Pour simplifier la lecture du diagramme, on supprime les boucles dues à la réflexivité et les flèches déductibles par transitivité :123 L"idée est de représenter les sommets du diagramme et tracer seulement les flèches correspondant aux successeurs immédiats. On dit queyest un successeur immédiat dexsixy,x6=yet il n"existe pas deztel que xzy.RelationsRelations d"ordre21 / 35

Fonctions croissantes et décroissantes

Definition

SoientAetBdeux ensembles munis respectivement des relations d"ordre

AetBetf:A!Bune application. On dit quefestcroissantesixAyalorsf(x)Bf(y).festdécroissantesixAyalorsf(y)Bf(x).feststrictement croissantesixAyetx6=yalorsf(x)Bf(y)

etf(x)6=f(y).feststrictement décroissantesixAyetx6=yalors f(y)Bf(x)etf(x)6=f(y).Proposition Une application strictement croissante ou strictement décroissante dont l"espace de départ est muni d"un ordre total est injective.

RelationsRelations d"ordre22 / 35

Elément minimal, borne inférieure

Soit(E;)un ensemble ordonné etAE.x2AestminimaldeAs"il n"admet pas d"élément plus petit dansA.x2EminorantdeAsi8y2Aon axyAadmet au plus un seul minorant dansA(par antisymétrique), c"est

le plus petit élémentdeA, s"il existe on le notemin(A).Le plus grand des minorants est laborne inférieure, on la note

inf(A). Autrement dit :

8y2Aon ainf(A)yet8zminorant deAon azinf(A)RelationsRelations d"ordre23 / 35

Elément maximal, borne supérieure

Soit(E;)un ensemble ordonné etAE.x2AestmaximaldeAs"il n"admet pas d"élément plus grand dansA.x2EmajorantdeAsi8y2Aon ayxAadmet au plus un seul majorant dansA(par antisymétrique), c"est

le plus grand élémentdeA, s"il existe on le notemax(A).Le plus petit des majorants est laborne supérieure, on la note

sup(A). Autrement dit :

8y2Aon aysup(A)et8zmajorant deAon asup(A)zRelationsRelations d"ordre24 / 35

Induction

RelationsInduction25 / 35

Ordre bien fondé

Définition

Un ensemble ordonné(E;)estbien fondés"il n"existe pas de suite infinie strictement décroissante d"éléments deE.De manière équivalente, on a :

Théorème

Un ensemble ordonné(E;)est bien fondé si et seulement si toute partie non vide admet au moins un élément minimal.Examples L"ordre usuelsur?est bien fondé mais il ne l"est pas sur?,?,

[0;1].L"ordrejsur?n f0;1gdéfini par "ajb()adiviseb" est bien fondé.SoitAun alphabet contenant au moins deux lettres,vperdest bien

fondé mais paslex.RelationsInduction26 / 35

Application à la terminaison d"algorithme

Variant de boucles

Etant donné(E;)un ordre bien fondé, unvariantde boucle est une fonction de l"ensemble des états du programme dansEstrictement décroissant à chaque passage dans la boucle.Proposition Si une boucle admet un variant alors elle termine.

Algorithme d"Euclide :

Donnée :(x;y)2?2

Résultat : le pgcd dexety

a x b y whileb6=0dotmp a a b b tmp[modb]RelationsInduction27 / 35 Application à la terminaison des algorithmes récursifs

Proposition

Soitfune fonction récursive définit sur un ensemble ordonné(E;)bien fondé. Sifest défini sur les éléments minimaux et si pour toutx2Enon minimal, le définition def(x)ne fait appel à des valeursf(y)pouryx avecx6=yalorsfest bien définit.Examples : On considère la fonctionfactdéfinie par :fact(0) =1;fact(n+1) = (n+1)fact(n). Elle est bien définie car(?;)est bien fondé.

On considère la fonctionfdéfinie sur?n f0;1gpar :f(p) =1 sippremier;f(n) =f(a) +f(b)sin=abeta6=1 etb6=1.

Elle est bien définie car(?n f0;1g;j)est bien fondé.RelationsInduction28 / 35 ?et le principe de récurrencePrincipe de récurrence SoitPune propriété dépendant d"un élémentnde?. Si les deux hypothèses suivantes sont vérifiées

Initialisation :P(0)est vraie,

Héridité :8n2?on a "P(n)est vraie=)P(n+1)est vraie"

Alors pour toutn2?, la propriétéP(n)est vraie.Preuve :On raisonne par l"absurde : supposons que les hypothèses du théorème sont vraies

mais que la conclusion est fausse. SoitX=fn2?;P(n)est fausseg. L"ensembleXest une partie non vide de?, comme(?;) est bien fondé,Xadmet un plus petit élément notén0. CommeP(0)est vraie, on an0>0 doncn01 est un entier positif ou nul, autrement dit n

012?.P(n01)est vraie carn01=2X. Par hypothèseP(n01) =)P(n0)donc

P(n0)est vraie ce qui est contradictoire avec le fait quen02X.RelationsInduction29 / 35 ?et le principe de récurrence généraliséPrincipe de récurrence généralisé SoitPune propriété dépendant d"un élémentnde?. Si les deux hypothèses suivantes sont vérifiées

Initialisation :P(0)est vraie,

Héridité :8n2?on a

"P(k)est vraie pourkOn applique le principe de récurrence du théorème précédent à la propriétéQtel que pour

n2?,Q(n)est vraie siP(k)est vraie pour toutkn.RelationsInduction30 / 35

Principe d"induction

Principe d"induction

SoitPune propriété dépendante d"un élémentxdeEmuni d"un ordre bien fondé. Si les deux hypothèses suivantes sont vérifiées : Initialisation :P(x)est vraie pour tout éléments minimaux deE,

Héridité :

Si p ourtout x2Equi n"est pas minimal on a :

P(y)est vraie8yxavecy6=x=)P(x)est vraie

Alors pour toutx2E, la propriétéP(x)est vraie.Preuve :On raisonne par l"absurde. SoitX=fx2E;P(x)est fausseg. L"ensembleXest une partie non vide deE, comme(E;) est bien fondé,Xadmet un plus petit élément notéx0. CommePest vraie pour tout élément minimal deE, l"élémentx0n"est pas minimal. Pour tout y2Etel queyx0ety6=x0, la propriétéP(y)est vraie carx0minimal dansXet doncy=2X

. Par hypothèse d"héréditéP(x0)est vraie ce qui est contradictoire avec le fait quex02X.RelationsInduction31 / 35

Définition inductive

Définition inductive d"un ensemble

SoitEun ensemble. Une définition inductive d"un sous-ensembleXdeE

consiste à la donnée :d"un sous-ensembleBdeEappelébase,d"un ensembleKd"opérations':Er'!Eoùr'est l"arité de'.

quotesdbs_dbs43.pdfusesText_43
[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

[PDF] ordre de grandeur electron