Maths discrètes - Relation -ordre lexicographique


  • D

    Bonjour, je m'exerce sur un exercice typique (que nous avons déjà traité ensemble: https://forum.mathforu.com/topic/30046/relation-d-ordre-ordre-total/5) mais qui pose énormément de problème d'un point de vu raisonnement.

    Soit X l'ensemble des mots binaires non vides. On note ≤\leq la relation d'ordre lexicographique sur X (en posant 0 <1). On considère la relation R sur X, définie par:

    U R V SSI il existe w € X tel que w ≤\leq u et w ≤\leq v

    La relation R est t-elle:

    Reflexive?
    Oui en prenant U=001, w=000, V=010
    R=ewe (e=element vide)≤\leq u et ewe≤\leq V

    symetrique?
    Non car w≤\leq u different de u≤\leq w et w≤\leq v différent v≤\leq w

    Transitive?
    URV et VRW
    Je dirais non mais je ne sais pas comment l'écrire

    Antisymètrique: U R V et VRU
    |u|≤\leq |v| et |V|≤\leq |U| Non

    Pouvez-vous me corriger?

    Merci


  • mtschoon

    Je viens de modifier ton énoncé avec la précision donnée, mise en gras dans ton énoncé
    Cela change ainsi l'explication proposée au départ !

    Un conseil ; n'essaie pas de répondre aux questions en imitant un autre exercice, mais comprends ce que signification la relation R
    Dans l'exercice que tu donnes en lien, il s'agit de facteurs alors que dans cet exercice, il s'agit de l'ordre lexicographique c'est à dire de l'ordre du "dictionnaire" avec des 0 et 1, sachant que 0 < 1

    L'énoncé te précise que ≤\le est une relation d'ordre (donc à utiliser directement)

    W≤UW \le UWU signifie que W est "avant" U dans l'ordre lexicographique (W peut être préfixe de U, mais c'est un cas particulier, il faut étudier le cas général avec 0 et 1.

    On compare les chiffres ( 0 - 1) de gauche des deux mots
    Si un mot commence par 0 et l'autre par 1, alors 0...≤1...0... \le 1...0...1...
    Si les deux mots commencent par le même chiffre (deux 0 ou deux 1), on compare les deux chiffres suivants, etc, etc...

    Exemples :
    01≤011001 \le 0110010110
    100100≤1001001100100 \le 10010011001001001001
    010111≤1100010111\le 11000101111100
    101≤110101 \le 110101110
    101≤101101\le 101101101 (car ≤\le réflexive)


  • mtschoon

    Je te donne quelques indications pour l'étude à faire sur R.
    (rédaction abrégée)

    Réflexivité : U R U ?
    Soit W tel que W≤UW \le UWU et W≤UW \le UWU équivaut à dire W est tel que W≤UW\le UWU
    C'est vrai

    Symétrie U R V => V R U ?
    Soit W tel que W≤UW \le UWU et W≤VW \le VWV équivaut à dire W est tel que W≤VW \le VWV et W≤UW \le UWU
    C'est vrai

    Transitivité U R V et V R T => U R T ?
    Soit W tel que W≤UW \le UWU et W≤VW \le VWV
    Soit W' tel que W′≤VW' \le VWV et W′≤TW' \le TWT

    Il faut voir deux cas suivant que W≤W′W \le W'WW ou W′≤WW'\le WWW

    Je te fais le cas W≤W′W \le W'WW

    W≤UW \le UWU
    W≤W′≤TW \le W' \le TWWT

    Vu que la relation ≤\le est transitive (car relation d'ordre) , on peut déduire que W≤TW \le TWT

    Bilan, on obtient W≤UW \le UWU et W≤TW \le TWT donc U R T est vrai.

    Je te laisse traiter les cas W′≤WW' \le WWW

    Dans les deux cas, c'est vrai

    Anti-Symétrie
    U R V et V R U => U=V ?
    C'est faux

    Un contre-exemple pour le prouver.
    Soit U=101 et V=110
    En choisissant W=010, on a bien W≤UW \le UWU et W≤VW\le VWV et pourtant U≠VU \ne VU=V

    Bon courage pour tes révisions.


  • D

    Je n'avais pas tout mais ça à l'air de rentrer doucement.

    Merci ces révisions me stressent énormément.


  • mtschoon

    Le mieux serait de ne pas stresser mais c'est normal !

    Tu travailles avec sérieux donc ton travail portera ses fruits.

    Un conseil , que tu appliques déjà peut-être.

    Parfois, tu ne sais pas faire un exercice tout simplement car tu as des difficultés à comprendre l'énoncé.
    Alors, sans refaire tous les exercices de l'année ( ce serait un travail fastidieux !), tu pourrais relire les énoncés avec grand soin (au mot près, car un mot peut changer le sens d'un énoncé) et t'assurer de bien comprendre ce qu'il signifie. C'est la base pour pouvoir répondre correctement.
    Bien sûr, si un énoncé te pose problème, tu peux nous poser la question.

    Bon travail !


Se connecter pour répondre