Chapitre 4 Relations d’ordre
D´efinition 4 1 Soit A un ensemble et R une relation sur cet ensemble 1 R est appel´ee une relation d’ordre ou un ordre partiel si les conditions suivantes sont verifi´ ´ees (a) Pour tout a ∈ A on a (a,a) ∈ R (reflexivit´ e) ´ (b) Pour tout a,b ∈ A si (a,b) ∈ R et (b,a) ∈ R alors a = b (antisym´etrie)
Exercices de Math´ematiques Relations d’ordre
C’est une relation d’ordre, mais partiel car {a} et {b} ne sont pas comparables Soit f l’application de E dans IN qui a toute partie de X associe son cardinal Elle est strictement croissante car si A ⊂ B ⊂ X, avec A 6= B alors Card(A) < Card(B)
Relations d’ordre
Relations d’ordre Cechapitretraitedesrelationsd’ordre Apr`esdesrappelsdenotionsabord´ees l’an dernier, on s’int´eresse plus particuli`erement aux “ordres bien fond´es” qui permettent de g´en´eraliser le principe de r´ecurrence 1 1 Ordre et ordre strict D´efinition (relation binaire) Soit E un ensemble Une relation binaire
Correction TP 6 : Relation d’ordre
Exercice 3 : Relation d’ordre partielle Une relation d’ordre est une relation binaire r´eflexive, antisym´etrique et tran-sitive De plus, elle est partielle si au moins un couple d’´el´ements ne peut pas ˆetre compar´e La relation de divisibilit´e sur l’ensemble des entiers est bien une relation d’ordre :
1 Relations d’´equivalence et d’ordre
La relation R est-elle r´eflexive, sym´etrique, transitive ? Exercice 6 Dans N∗, on d´efinit une relation
Relation binaire, relation dordre, treillis
* L’inclusion est une relation d’ordre partiel sur les parties d’un ensemble: X = {a,b,c} * Les entiers naturels peuvent etre munis d’un ordre plus subtilˆ que l’ordre usuel q est plus grand que p si q est multiple de p , D48 est un treillis J -L Baril Relation binaire, relation d’ordre, treillis
VIII Relations d’ordre et d’équivalence
VIII-RELATIONSD’ORDREETD’ÉQUIVALENCE Danstoutcechapitre,E estunensemble 1 Relations binaires Définition1 0 1 On appelle relation binaire tout triplet R = (E,F,Γ) oùE etF sontdesensemblesetoùΓ est
Réduction d’ordre partiel - École Polytechnique
Réd d’ordre part pour LTL− Plutôt que de proposer directement un algorithme pour calculer ample(s), on va proposer des conditions qui le garantissent Condition C0: ample(s) = ∅ ssi enabled(s) = ∅ (autrement dit: si s a au moins un successeur, alors cela est aussi vrai dans le graphe réduit ) Condition C1: si un chemin partant de
Relations de couples
Attention : en mathématique partiel ne s'oppose pas à total : un ordre total est d'abord un ordre partiel Comme une relation d'ordre, disons 4, n'est pas forcément totale, a 64b n'est pas équivalent à b ˚a : ceci n'est vrai que pour des relations d'ordre total Exercice 3 (Minorant, minimal, minimum, in mum)
[PDF] relation d'ordre exemple
[PDF] relation d'ordre inclusion
[PDF] relation d'ordre majorant minorant
[PDF] le representant permanent du royaume du maroc aupres de l onu est
[PDF] le developpement durable au maroc
[PDF] le développement durable au maroc définition
[PDF] conseil supérieur de l'éducation de la formation et de la recherche scientifique maroc
[PDF] rapport du conseil supérieur de l'enseignement maroc 2016
[PDF] vision stratégique 2015 2030 ppt
[PDF] les projets intégrés de la vision stratégique 2015-2030
[PDF] montrer qu'une suite est décroissante par récurrence
[PDF] un+1 suite
[PDF] montrer qu'une suite géométrique est croissante
[PDF] la charte nationale de l'éducation pdf
Chapter 1
Relations d"ordre
Ce chapitre traite des relations d"ordre. Apr`es des rappels de notions abord´ees l"an dernier, on s"int´eresse plus particuli`erement aux "ordres bien fond´es" qui permettent de g´en´eraliser le principe de r´ecurrence.1.1 Ordre et ordre strict
D´efinition (relation binaire).SoitEun ensemble. Unerelation binaire RsurEest un sous-ensemble deE×E. On notexRypour signifier que (x,y)? RetxR/ ypour signifier que (x,y)/? R. D´efinition (classification).SoitRune relation binaire surE. On dit queRest•r´eflexivequand?x?E,xRx;•irr´eflexivequand?x?E,xR/ x;•sym´etriquequand?x,y?E,xRy?yRx;•antisym´etriquequand?x,y?E,xRyetyRx?x=y;•transitivequand?x,y,z?E,xRyetyRz?xRz.
D´efinition (ordre).Une relation binaire est unordre(ou unerelation d"ordre) quand elle est r´eflexive, antisym´etrique et transitive. D´efinition (ensemble ordonn´e).SoitEun ensemble et?une relation d"ordre surE. On dit que (E,?) est unensemble ordonn´e. Remarque: Attention, les d´efinitions ci-dessus correspondent `a l"ordre large mais pas `a l"ordre strict : (IR,<) o`u1.2 Minorants, majorants, minimaux et maximaux
D´efinition (minorant, plus petit ´el´ement)Soit (E,?) un ensemble ordonn´e etFune partie (c"est-`a-dire un sous-ensemble) non vide deE. On dit quex?Eest unminorantdeFsi tout ´el´ement deFest plus grand que xpour?:?y?F,x?y. Si le minorant deFest un ´el´ement deFon dit que c"estle plus petit ´el´ementdeF. D´efinition (majorant, plus grand ´el´ement).Soit (E,?) un ensemble ordonn´e etFune partie non vide deE. On dit quex?Eest unmajorant deFsi tout ´el´ement deFest plus petit quexpour?:?y?F,y?x. Si le majorant deFest un ´el´ement deFon dit que c"estle plus grand ´el´ement deF. Remarque: Il n"y a pas toujours un minorant ou un majorant : si l"ensemble c"estZet la partiePl"ensemble des entiers relatifs divisibles par 2, il n"y a ni minorant ni majorant.Th´eor`eme 1.2Soit(E,?)un ensemble ordonn´e etFune partie non vide deE.Fa au plus un plus petit ´el´ement et au plus un plus grand ´el´ement.1.3. PRODUIT D"ORDRES3D´efinition (´el´ement minimal).Soit (E,?) un ensemble ordonn´e etF
une partie non vide deE. Un ´el´ementx?Fest un´el´ement minimalde Fquand aucun ´el´ement deFn"est strictement plus petit, pour?, quex: ?y?F,y?x?y=x. D´efinition (´el´ement maximal).Soit (E,?) un ensemble ordonn´e etF une partie non vide deE. Un ´el´ementx?Fest un´el´ement maximalde Fquand aucun ´el´ement deFn"est strictement plus grand, pour?, quex: ?y?F,x?y?y=x.1.3 Produit d"ordres
D´efinition (ordre produit simple).Soit (E,?E) et (F,?F) deux en- sembles ordonn´es. On d´efinit l"ordre produit simple?prodsurE×Fpar D´efinition (ordre produit lexicographique).Soit (E,?E) et (F,?F) deux ensembles ordonn´es. On d´efinit l"ordre produit lexicographique?lexsur E×Fpar, on notant?Eet?Fles ordres stricts associ´es `a?Eet?F, ?x?Ex? ou x=x?ety?Fy?. Remarque: Si?Eet?Fsont des ordres totaux,?lexest aussi un ordre total; ce n"est pas vrai pour?prod.1.4 Ordre bien fond´e
D´efinition (ordre bien fond´e)Soit (E,?) un ensemble ordonn´e. On dit que?estbien fond´equand il n"existe pas de suite infinie strictement d´ecroissante d"´el´ements deE. Remarque: L"ordre usuel surNest bien fond´e, mais pas celui surZ, ni celui sur IR +.Th´eor`eme 1.3(caract´erisation des ordres bien fond´es)Soit(E,?) un ensemble ordonn´e. L"ordre?est bien fond´e si et seulement si tout partienon videFdeEadmet au moins un ´el´ement minimal.Th´eor`eme 1.4Le produit lexicographique de deux ordres bien fond´es est
bien fond´e.4CHAPTER 1. RELATIONS D"ORDRE1.5 Application `a la terminaison de programmes
Si on consid`ere le programme suivant, o`u les entiersmetnsont strictements positifs avant de commencer, on montre facilement qu"ils restent tout le temps strictement positifs.while (m != n) { if (m > n) m = m - n; else n = n - m; La question est: est-ce que cette boucle s"arrˆete toujours, pour n"importe quel choix demetndansN?? la r´eponse et oui et on peut le montrer grˆace `a l"ordre lexicographique: si on consid`ere l"ordre lexicographique naturel sur N ?×N?, on s"aper¸coit qu"`a chaque it´eration le couple (m,n) est strictement inf´erieur `a celui d"avant. Comme l"ordre lexicographique surN?×N?est bien fond´e (d"apr`es le th´eor`eme pr´ec´edent), on ne peut effectuer qu"un nombre fini d"it´erations dans le programme. Le proc´ed´e se g´en´eralise aux fonctions r´ecursives, quand on veut prouver qu"elle termine. Il suffit de trouver un ordre bien fond´e sur les entr´ees, et de montrer que lors d"un appel `a la fonction, on ne lance des appels r´ecursif que sur des donn´ees plus petites pour l"ordre consid´er´e. Voir le TD pour un exemple.1.6 Diagramme de Hasse d"un ensemble ordonn´e
fini Quand (E,?) est un ensemble fini ordonn´e, on peut le repr´esenter graphique- ment par sondiagramme de Hasse, qui est un graphe non-orient´e avec lescontraintes suivantes :•les sommets sont les ´el´ements deE;•six?yon placexplus bas queysur le diagramme;•six?yet qu"il n"y a pas dez?Etel quex?z?y, on met une
arˆete entrexety. Exemple: Le diagramme de Hasse pour l"ordre?surE={1,2,3}est :