[PDF] 1 Relations binaires 2 Relations déquivalence 3 Relations dordre
Une relation binaire R sur un ensemble E est une propriété portant sur les couples R est antisymétrique si pour tout x y ? E (xRy et yRx) ? x = y ;
[PDF] RELATIONS BINAIRES - Christophe Bertault
La relation d'égalité = sur E est réflexive transitive symétrique et antisymétrique • Les relations ? sur et sont réflexives transitives et antisymétriques
[PDF] Relations binaires antisymétriques - IGM
Relations binaires antisymétriques Soit E un ensemble et R une relation binaire sur E On dit que R est antisymétrique si pour tous x y ? E
[PDF] Relations binaires sur un ensemble
Définition 4 1 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
[PDF] RELATION BINAIRE - Licence de mathématiques Lyon 1
la relation est antisymétrique { { la relation est transitive Il s'agit bien d'une relation d'ordre Allez à : Exercice 11 : 3 donc on n'a pas
[PDF] Contribution Relations binaires dans un ensemble à 3 éléments
Une relation non symétrique est dite antisymétrique quand pour tout couple d'éléments distincts considérés si la relation est vérifiée de x vers y elle ne l'
[PDF] Relations
4 oct 2011 · Ensemble A et ensemble B en relation si leurs éléments sont La relation R sur A est antisymétrique si ?ab ? Aa = b et aRb =? b Ra
[PDF] Relations binaires Relations déquivalence et dordre
20 août 2017 · Elle n'est pas antisymétrique 1 4 Relation totale ou partielle Définition 4 : Soit ? une relation binaire sur E • On dit que
[PDF] Relations
La notion de relation en mathématiques généralise toutes ces situations xPrérequisx 2) Dire que la relation est antisymétrique signifie que :
[PDF] 1 Relations binaires 2 Relations déquivalence 3 Relations dordre
Une relation binaire R sur un ensemble E est une propriété portant sur les couples R est antisymétrique si pour tout x y ? E (xRy et yRx) ? x = y ;
[PDF] Relation - Université de Toulouse
Relation antisymétrique Antisymétie Une relation R est antisymétrique si pour tout xy ? E vérifiant xRy et yRx alors on a x = y
[PDF] RELATIONS BINAIRES - Christophe Bertault
Antisymétrie : On dit que est antisymétrique si : ?x y ? E x y et y x =? x = y Exemple • La relation d'égalité = sur E est réflexive transitive
[PDF] 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
[PDF] RELATION BINAIRE - Licence de mathématiques Lyon 1
la relation est antisymétrique { { la relation est transitive Il s'agit bien d'une relation d'ordre Allez à : Exercice 11 : 2 la relation est réflexive
[PDF] Relations
4 oct 2011 · Ensemble A et ensemble B en relation si leurs éléments sont Exemples de relations antisymétriques (ou non) L'infériorité large
[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 Les relations ? et ? sur R sont réflexives antisymétrique et
Relation Symétrique Et Antisymétrique PDF - Scribd
"dans l'une [des deux relations] touteS leS relationS ont leur reciproque etc " Il vaut mieux dire : "dans l'une tous les couples en relation ont leur
[PDF] Contribution Relations binaires dans un ensemble à 3 éléments
Une relation non symétrique est dite antisymétrique quand pour tout couple Le calcul du nombre de relations antisymétriques est un peu plus compliqué
Comment montrer qu'une relation est antisymé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.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.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.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.
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreRelations
Arnaud Labourel
Courriel : arnaud.labourel@lif.univ-mrs.fr
Universite de Provence
4 octobre 2011
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationRelations entre ensembles
Ensembles en relation
EnsembleAet ensembleBen relation si leurs elements sont liesDenir une relation = enoncer une regle permettant de repondre a la question :Est-ce quea2Aest en relation avecb2B?Exemple
Al'ensemble des etudiants de l'Universite de ProvenceBl'ensemble des unites de valeurs (ECTS)Inscription d'un etudiant a une UV = creation d'une relation
entreAetBArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationExemples de relations entre ensemblesUn ensemble et ses parties
SoitEun ensemble quelconque non videL'appartenance d'un element deEa un element deP(E) creeune relation entreEet l'ensemble de ses parties.L'appartenance est souvent notee2Un ensemble en relation avec lui-m^eme
SoitZles entiers relatifsa2Zest lie ab2Zsibaest strictement positif : relationde stricte inferiorite entreZet lui-m^eme (notee<)Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationConventions d'ecriture
Deux elements en relation
SiRest le symbole d'une relation entre deux ensemblesAetB, alors on noteraaRble fait quea2Aetb2Bsont en relation parRa Deux elements qui ne sont pas en relation
Negation de relation : symbole propre, ou barrer le symboleRNegation de l'egalite = est l'inegalite6=Negation de la stricte inferiorite6<(et non pas large
superiorite)Negation de la relationavant: la relationapresArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relations Relations et fonctions
Arite d'une relationGraphe d'une relation
Denition
Le graphe d'une relationRest l'ensemble des couples (a;b) pour lesquels nous avonsaRb. Cet ensemble est une partie deABEgalite de relations R 1=R2si elles ont m^eme grapheNouvelle denition de relation
Toute partie deABest unerelation entre AetB
=)les relations pourront se denir en comprehension (predicat) ou en extension (enumeration) Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relations Relations et fonctions
Arite d'une relationDiagramme sagittal
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relations Relations et fonctions
Arite d'une relationDiagramme sagittal
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relations Relations et fonctions
Arite d'une relationDiagramme sagittal
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relations Relations et fonctions
Arite d'une relationMatrice de relation
0 B BBBBBBBBBBB@a e i o u
1 0 0 0 0 1
2 0 1 0 0 1
3 0 0 1 1 0
4 1 1 0 0 1
5 0 0 1 0 0
6 0 0 1 0 0
7 0 1 0 0 0
8 0 0 1 0 1
9 0 1 0 0 11
C CCCCCCCCCCCAArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relations Relations et fonctions
Arite d'une relationRemarques sur ces representations Fidelite
Tous les liens entre elements deAetBsont representes et peuvent ^etre reconstituesChoix arbitraires diagramme sagittal : ou placer les sommets, quelle forme de echesdiagramme cartesien et matrice : ordre de parcours des elements =)Diculte pour etablir l'egalite entre relationsArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relations Relations et fonctions
Arite d'une relationDes notions proches
Pourquoi ?
f:A!Bassocie a des elements deAune image dansBL'ensemble des couples (a;f(a)) = graphe d'une relationR
entreAetBRelations fonctionnelles Particularite d'une telleR: pour unaquelconque, au plus un elementbdeBassocieReciproquement : toute relation ayant cette particularite denitune fonction deAversB. =Relation fonctionnelle Les relations peuvent se denir comme des ensembles Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relations Relations et fonctions
Arite d'une relationRelation entre3 ensemblesArite d'une relation = Nombre d'ensembles mis en relation (un m^eme ensemble pouvant ^etre considere plusieurs fois)Relationn-aireSiA1;A2;;Ansont des ensembles non vides : toute partie du
produitA1A2 Anest appelee une relationn-aire entre ces ensembles.Un peu de vocabulaire Relation binaire = relation d'arite 2
Relation ternaire = relation d'arite 3
quaternaire, etc. Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relations Relations et fonctions
Arite d'une relationExemple de relation ternaire
A=fArgentine, Belgique, Cameroun, Canada, TogogB=ffrancais, espagnol, allemand, hollandais, anglaisgC=N
Triplets (a;b;c) : partie de ces triplets = relation ternaire (Argentine, espagnol ,100) ( Belgique , francais , 55 ) ( Belgique ,hollandais, 65 ) ( Belgique ,allemand, 15 ) (Cameroun, francais , 70 ) (Cameroun, anglais , 25 ) ( Canada , francais , 23 ) ( Canada , anglais , 99 ) ( Togo , francais , 93 ) Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation entreAet lui-m^emeRelations surACelles qui nous interessent dans ce cours
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation entreAet lui-m^eme (cont'd)Remarques sur la representation cartesienne
Proprietes et conventions
Forme carree
M^eme ordre de parcours
La diagonale (x;x)Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation re
exive Denition
La relationRsurAest re
exive quand tout element deAest en relation avec lui-m^eme : 8a2A;aRaSur les diagrammes
Une relation re
exive se repere facilementDiagramme sagittal : une boucleDiagramme cartesien : la diagonale Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesExemples de relations re exives (ou non) L'egalite
Quel que soitA, la relation d'egalite est, par essence, re exive.Chez les entiers Chez les couleurs
Consequences :est re
exive (mais pas<)Plus concretement : longueur de mots Soit l'ensemble des mots de la langue francaiseFSoit la relation `surF: deux mots deFsont lies par`si leur nombre de lettres sont egauxgrand `petit,grand`6grande, etgrand`grandArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation symetrique
Denition
La relationRsurAest symetrique quand deux elements deAsont en relation quel que soit l'ordre : 8a;b2A;aRb()bRaSur les diagrammes
Sur le diagramme cartesien : symetrie par rapport a la diagonaleSur le diagramme sagittal : quand une eche va deaversb, il y a aussi une eche debversaArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesExemples de relations symetriques (ou non) L'egalite
Quel que soit l'ensembleA, sia=balorsb=a.
La relationn'est pas symetrique (36 mais il est faut de dire 63)Longueur des mots
grand `petitetpetit`grandArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation transitive
Denition
La relationRsurAest transitive si
8a;b;c2A;aRbetbRc=)aRcSur les diagrammes
Sur le diagramme sagittal, on ferme les triangles
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation transitive
Denition
La relationRsurAest transitive si
8a;b;c2A;aRbetbRc=)aRcSur les diagrammes
Sur le diagramme sagittal, on ferme les triangles
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesExemples de relations transitives (ou non) L'egalite, encore !
Quel que soitA, sia=bet sib=calorsa=c
C'est aussi vrai de: 36 et 610 et 310La longueur des mots grand `petitetpetit`minusetgrand`minusLe pere de mon pere n'est pas mon pere Eric Pere JeanetJeanPereNicolasmais on n'a pas
(forcement !)EricPereNicolasArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation transitive et matrice de relation Soit une relationRrepresentee par sa matriceR(carree) Rest transitive()R2R0
B B@a b c d
a0 0 1 0 b1 1 1 1 c0 0 0 0 d0 0 1 01 C CA R0 B B@a b c d
a0 0 0 0 b1 1 1 1 c0 0 0 0 d0 0 0 01 C CA R 2Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation transitive et matrice de relation Soit une relationRrepresentee par sa matriceR(carree) Rest transitive()R2R0
B B@a b c d
a0 0 1 0 b1 1 1 1 c0 0 0 0 d0 0 1 01 C CA R0 B B@a b c d
a0 0 0 0 b1 1 1 1 c0 0 0 0 d0 0 0 01 C CA R 2Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation irre
exive Denition
La relationRsurAest irre
exive si8a2A;a6RaExemples L'inegalite...
La relationPereArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation antisymetrique Denition
La relationRsurAest antisymetrique si
8a;b2A;a6=betaRb=)b6Ra
Ou : lo rsqueRest antisymetrique : siaRbetbRaalorsa=bSur les diagrammes Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesExemples de relations antisymetriques (ou non) L'inferiorite large
47 et 46= 7 et on n'a pas 74
33 et 33 possible car 3 = 3La longueur des mots n'est pas antisymetrique
Elle est symetrique...
La relationanterieur ou egalSoit l'ensembleDdes dates sur un calendrierSoit la relation binairesurDqui lie une date a une autre si
la premiere est anterieure ou egale a la seconde03=02=200705=03=2007 et 03=02=20076= 05=03=2007 donc on ne peut pas avoir 05=03=200703=02=2007Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensemblePour aller au dela de l'egalite Proprietes de l'egalite
Re exive(rouge=rouge),symetrique(si cTable= cMur alors cMur = cTable), ettransitive(si cTable = cMur et si cMur=cPlafond alors cTable=cPlafond).Denition d'une relation d'equivalence Relationre
exive,symetriqueettransitiveExemple : relation `Elle revient a etablir une relation d'egalite sur la longueur des mots Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensembleRelation d'equivalence (cont'd) Convention
SiRest une relation d'equivalence, on dit queaest equivalent ab quandaRb. La relation etant symetrique, on a aussibequivalent aa: on dit queaetbsont equivalents.Exemple SurA=f0;1;2;3;4;5;6;7;8;9g, on denit la relation6x 6ylorsquexyest un multiple de 6Montrons que
6est une relation d'equivalence (re
exive, symetrique et transitive) Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensembleExemple dex6y(cont'd) Diagramme cartesien dex6yArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensembleClasse d'equivalence d'un element Denition
Soit une relation d'equivalenceRsurA, et soita2AL'ensemble des elements deAequivalents aas'appelle la
classe d'equivalence de aNotation :C`(a)Exemple de 60 1 2 3 4 5 6 7 8 9
f0;6g f1;7g f2;8g f3;9g f4g f5g f0;6g f1;7g f2;8g f3;9g =)6 classes d'equivalence pour6Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensembleEnsemble quotient Denition
Soit une relation d'equivalenceRsurA, et soita2AL'ensemble des classes d'equivalence s'appelle l'ensemble
quotientdeApar la relationRNotation :A=RNouvelle methode de construction d'ensemble A partir d'un ensembleA, on peut construire un autre ensemble par l'operation quotientA=RExemple de 6ff0;6g;f1;7g;f2;8g;f3;9g;f4g;f5ggArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensembleQuelques proprietes 8a2A;a2 C`(a) carRest re
exive (aRa)Deux classes ayant un element commun sont egales Les classes d'equivalencedecoupentl'ensembleAen parties disjointes.= une partition deAArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensemblePartition d'un ensemble : rappel Denition
Une partition d'un ensembleAest une collection departiesnon vides deA, appelees lescomposantesde la partition, qui possede deux proprietes essentielles :1Tout element deAappartient a une composante de laquotesdbs_dbs43.pdfusesText_43
Deux elements qui ne sont pas en relation
Negation de relation : symbole propre, ou barrer le symboleRNegation de l'egalite = est l'inegalite6=Negation de la stricte inferiorite6<(et non pas large
superiorite)Negation de la relationavant: la relationapresArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationGraphe d'une relation
Denition
Le graphe d'une relationRest l'ensemble des couples (a;b) pour lesquels nous avonsaRb. Cet ensemble est une partie deABEgalite de relations R1=R2si elles ont m^eme grapheNouvelle denition de relation
Toute partie deABest unerelation entre AetB
=)les relations pourront se denir en comprehension (predicat) ou en extension (enumeration) Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationDiagramme sagittal
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationDiagramme sagittal
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationDiagramme sagittal
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationMatrice de relation
0 BBBBBBBBBBBB@a e i o u
1 0 0 0 0 1
2 0 1 0 0 1
3 0 0 1 1 0
4 1 1 0 0 1
5 0 0 1 0 0
6 0 0 1 0 0
7 0 1 0 0 0
8 0 0 1 0 1
9 0 1 0 0 11
C CCCCCCCCCCCAArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationRemarques sur ces representationsFidelite
Tous les liens entre elements deAetBsont representes et peuvent ^etre reconstituesChoix arbitraires diagramme sagittal : ou placer les sommets, quelle forme de echesdiagramme cartesien et matrice : ordre de parcours des elements=)Diculte pour etablir l'egalite entre relationsArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationDes notions proches
Pourquoi ?
f:A!Bassocie a des elements deAune image dansBL'ensemble des couples (a;f(a)) = graphe d'une relationR
entreAetBRelations fonctionnelles Particularite d'une telleR: pour unaquelconque, au plus un elementbdeBassocieReciproquement : toute relation ayant cette particularite denitune fonction deAversB. =Relation fonctionnelle Les relations peuvent se denir comme des ensembles Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationRelation entre3 ensemblesArite d'une relation = Nombre d'ensembles mis en relation (un m^eme ensemblepouvant ^etre considere plusieurs fois)Relationn-aireSiA1;A2;;Ansont des ensembles non vides : toute partie du
produitA1A2 Anest appelee une relationn-aire entre ces ensembles.Un peu de vocabulaireRelation binaire = relation d'arite 2
Relation ternaire = relation d'arite 3
quaternaire, etc. Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreComment representer les relationsRelations et fonctions
Arite d'une relationExemple de relation ternaire
A=fArgentine, Belgique, Cameroun, Canada, TogogB=ffrancais, espagnol, allemand, hollandais, anglaisgC=N
Triplets (a;b;c) : partie de ces triplets = relation ternaire (Argentine, espagnol ,100) ( Belgique , francais , 55 ) ( Belgique ,hollandais, 65 ) ( Belgique ,allemand, 15 ) (Cameroun, francais , 70 ) (Cameroun, anglais , 25 ) ( Canada , francais , 23 ) ( Canada , anglais , 99 ) ( Togo , francais , 93 ) Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation entreAet lui-m^emeRelations surACelles qui nous interessent dans ce cours
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation entreAet lui-m^eme (cont'd)Remarques sur la representation cartesienne
Proprietes et conventions
Forme carree
M^eme ordre de parcours
La diagonale (x;x)Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation re
exiveDenition
La relationRsurAest re
exive quand tout element deAest en relation avec lui-m^eme :8a2A;aRaSur les diagrammes
Une relation re
exive se repere facilementDiagramme sagittal : une boucleDiagramme cartesien : la diagonale Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesExemples de relations re exives (ou non)L'egalite
Quel que soitA, la relation d'egalite est, par essence, re exive.Chez les entiersChez les couleurs
Consequences :est re
exive (mais pas<)Plus concretement : longueur de mots Soit l'ensemble des mots de la langue francaiseFSoit la relation `surF: deux mots deFsont lies par`si leur nombre de lettres sont egauxgrand `petit,grand`6grande, etgrand`grandArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation symetrique
Denition
La relationRsurAest symetrique quand deux elements deAsont en relation quel que soit l'ordre :8a;b2A;aRb()bRaSur les diagrammes
Sur le diagramme cartesien : symetrie par rapport a la diagonaleSur le diagramme sagittal : quand une eche va deaversb, il y a aussi une eche debversaArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesExemples de relations symetriques (ou non)L'egalite
Quel que soit l'ensembleA, sia=balorsb=a.
La relationn'est pas symetrique (36 mais il est faut de dire63)Longueur des mots
grand `petitetpetit`grandArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation transitive
Denition
La relationRsurAest transitive si
8a;b;c2A;aRbetbRc=)aRcSur les diagrammes
Sur le diagramme sagittal, on ferme les triangles
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation transitive
Denition
La relationRsurAest transitive si
8a;b;c2A;aRbetbRc=)aRcSur les diagrammes
Sur le diagramme sagittal, on ferme les triangles
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesExemples de relations transitives (ou non)L'egalite, encore !
Quel que soitA, sia=bet sib=calorsa=c
C'est aussi vrai de: 36 et 610 et 310La longueur des mots grand `petitetpetit`minusetgrand`minusLe pere de mon pere n'est pas mon pere Eric PereJeanetJeanPereNicolasmais on n'a pas
(forcement !)EricPereNicolasArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation transitive et matrice de relation Soit une relationRrepresentee par sa matriceR(carree)Rest transitive()R2R0
BB@a b c d
a0 0 1 0 b1 1 1 1 c0 0 0 0 d0 0 1 01 C CA R0 BB@a b c d
a0 0 0 0 b1 1 1 1 c0 0 0 0 d0 0 0 01 C CA R2Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation transitive et matrice de relation Soit une relationRrepresentee par sa matriceR(carree)Rest transitive()R2R0
BB@a b c d
a0 0 1 0 b1 1 1 1 c0 0 0 0 d0 0 1 01 C CA R0 BB@a b c d
a0 0 0 0 b1 1 1 1 c0 0 0 0 d0 0 0 01 C CA R2Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation irre
exiveDenition
La relationRsurAest irre
exive si8a2A;a6RaExemplesL'inegalite...
La relationPereArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesRelation antisymetriqueDenition
La relationRsurAest antisymetrique si
8a;b2A;a6=betaRb=)b6Ra
Ou : lo rsqueRest antisymetrique : siaRbetbRaalorsa=bSur les diagrammes Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreIntroduction
Les proprietes essentiellesExemples de relations antisymetriques (ou non)L'inferiorite large
47 et 46= 7 et on n'a pas 74
33 et 33 possible car 3 = 3La longueur des mots n'est pas antisymetrique
Elle est symetrique...
La relationanterieur ou egalSoit l'ensembleDdes dates sur un calendrierSoit la relation binairesurDqui lie une date a une autre si
la premiere est anterieure ou egale a la seconde03=02=200705=03=2007 et 03=02=20076= 05=03=2007donc on ne peut pas avoir 05=03=200703=02=2007Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensemblePour aller au dela de l'egaliteProprietes de l'egalite
Re exive(rouge=rouge),symetrique(si cTable= cMur alors cMur = cTable), ettransitive(si cTable = cMur et si cMur=cPlafond alors cTable=cPlafond).Denition d'une relation d'equivalenceRelationre
exive,symetriqueettransitiveExemple : relation `Elle revient a etablir une relation d'egalite sur la longueur des mots Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensembleRelation d'equivalence (cont'd)Convention
SiRest une relation d'equivalence, on dit queaest equivalent ab quandaRb. La relation etant symetrique, on a aussibequivalent aa: on dit queaetbsont equivalents.Exemple SurA=f0;1;2;3;4;5;6;7;8;9g, on denit la relation6x6ylorsquexyest un multiple de 6Montrons que
6est une relation d'equivalence (re
exive, symetrique et transitive) Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensembleExemple dex6y(cont'd) Diagramme cartesien dex6yArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensembleClasse d'equivalence d'un elementDenition
Soit une relation d'equivalenceRsurA, et soita2AL'ensemble des elements deAequivalents aas'appelle la
classe d'equivalence de aNotation :C`(a)Exemple de60 1 2 3 4 5 6 7 8 9
f0;6g f1;7g f2;8g f3;9g f4g f5g f0;6g f1;7g f2;8g f3;9g =)6 classes d'equivalence pour6Arnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensembleEnsemble quotientDenition
Soit une relation d'equivalenceRsurA, et soita2AL'ensemble des classes d'equivalence s'appelle l'ensemble
quotientdeApar la relationRNotation :A=RNouvelle methode de construction d'ensemble A partir d'un ensembleA, on peut construire un autre ensemble par l'operation quotientA=RExemple de6ff0;6g;f1;7g;f2;8g;f3;9g;f4g;f5ggArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelations
Denitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensembleQuelques proprietes8a2A;a2 C`(a) carRest re
exive (aRa)Deux classes ayant un element commun sont egales Les classes d'equivalencedecoupentl'ensembleAen parties disjointes.= une partition deAArnaud Labourel, arnaud.labourel@lif.univ-mrs.frRelationsDenitions
Proprietes des relations binaires
Relations d'equivalence
Relations d'ordreDenition
Classe d'equivalence
Classes d'equivalence et partitions d'un ensemblePartition d'un ensemble : rappelDenition
Une partition d'un ensembleAest une collection departiesnon vides deA, appelees lescomposantesde la partition, qui possede deux proprietes essentielles :1Tout element deAappartient a une composante de laquotesdbs_dbs43.pdfusesText_43[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
[PDF] ordre de grandeur d'un noyau atomique
