Exercice 6 / 9Moyen
Les propriétés de la relation « même VLAN »
À toi
Sur E = {1 ; 2 ; 3 ; 4}, quatre postes, la relation R « est dans le même VLAN que » est donnée par ses couples :
R = {(1 ; 1) ; (2 ; 2) ; (3 ; 3) ; (4 ; 4) ; (1 ; 3) ; (3 ; 1) ; (2 ; 4) ; (4 ; 2)}
Étudie ses propriétés, dis de quel type de relation il s'agit, et donne le nombre de VLAN.
Ensembles, relations et applications
Notations
Un ensemble s'écrit entre accolades, éléments séparés par des points-virgules : {1 ; 2 ; 3}. x ∈ E se lit « x appartient à E », A ⊂ B « A est inclus dans B ». card(E) est le nombre d'éléments de E. Un couple s'écrit entre parenthèses : (a ; b).
Les opérations
Dans E = {1 ; 2 ; … ; 8}, avec A = {1 ; 2 ; 3 ; 4} et B = {3 ; 4 ; 5} :
| Opération | Se lit | Contient | Exemple |
|---|---|---|---|
| A ∪ B | A union B | les éléments de A ou de B | {1 ; 2 ; 3 ; 4 ; 5} |
| A ∩ B | A inter B | les éléments de A et de B | {3 ; 4} |
| A \ B | A privé de B | les éléments de A qui ne sont pas dans B | {1 ; 2} |
| Ā | complémentaire de A | les éléments de E hors de A | {5 ; 6 ; 7 ; 8} |
| A Δ B | différence symétrique | les éléments d'un seul des deux | {1 ; 2 ; 5} |
Lois de De Morgan : ∁(A ∪ B) = Ā ∩ B̄ et ∁(A ∩ B) = Ā ∪ B̄.
Cardinal d'une réunion : card(A ∪ B) = card(A) + card(B) − card(A ∩ B). Dans un groupe, 12 étudiants font du Python, 9 du PHP et 4 les deux : 12 + 9 − 4 = 17 font au moins l'un des deux. Sans la soustraction, les 4 seraient comptés deux fois.
Produit cartésien et dénombrement
E × F est l'ensemble des couples (x ; y) avec x ∈ E et y ∈ F. L'ordre compte : (x ; y) n'est pas (y ; x). card(E × F) = card(E) × card(F) : 3 systèmes et 4 navigateurs donnent 3 × 4 = 12 configurations de test. Une suite de k éléments pris dans un ensemble de n éléments est un élément de Eᵏ : il y en a nᵏ. Un code de 3 lettres majuscules : 26³ = 17 576 possibilités.
L'ensemble des parties
P(E) est l'ensemble de toutes les parties de E, ∅ et E compris. Si card(E) = n, card(P(E)) = 2ⁿ : chaque élément est dans la partie ou n'y est pas. Pour E = {x ; y} : P(E) = {∅ ; {x} ; {y} ; {x ; y}}, 4 parties.
Ne confonds pas : x ∈ E (un élément dans un ensemble), {x} ⊂ E (une partie dans un ensemble), {x} ∈ P(E) (une partie est un élément de P(E)).
Les propriétés d'une relation sur E
| Propriété | Définition | Pour la réfuter |
|---|---|---|
| Réflexive | x R x pour tout x | un (x ; x) manquant |
| Symétrique | x R y ⇒ y R x | un (x ; y) sans son retour |
| Antisymétrique | x R y et y R x ⇒ x = y | un aller-retour entre deux éléments différents |
| Transitive | x R y et y R z ⇒ x R z | un enchaînement sans son raccourci |
- Relation d'équivalence : réflexive, symétrique, transitive. Elle range E en classes disjointes. « A le même reste dans la division par 3 » sur {1 ; … ; 6} : classes {1 ; 4}, {2 ; 5}, {3 ; 6}.
- Relation d'ordre : réflexive, antisymétrique, transitive. L'ordre est total si deux éléments sont toujours comparables, partiel sinon. Le diagramme de Hasse ne garde que les liens directs, sans boucles ni raccourcis dus à la transitivité.
Les applications
f : E → F est injective si chaque élément de F a au plus un antécédent, surjective s'il en a au moins un, bijective s'il en a exactement un. Entre deux ensembles finis de même cardinal, injective, surjective et bijective reviennent au même. Si card(E) > card(F), aucune application de E vers F n'est injective (principe des tiroirs).
En SQL
| Opérateur | Opération | Lignes renvoyées |
|---|---|---|
UNION | réunion, doublons supprimés | card(A ∪ B) |
UNION ALL | réunion, doublons gardés | card(A) + card(B) |
INTERSECT | intersection | card(A ∩ B) |
EXCEPT | différence A \ B | card(A \ B) |
CROSS JOIN | produit cartésien | card(A) × card(B) |
Tu es bloqué ?
Ouvre les indices un par un, le corrigé en dernier.
Indice 1
Réflexive : chaque couple (x ; x) est-il présent ?
Indice 2
Antisymétrique : un seul aller-retour (x ; y) et (y ; x) avec x ≠ y suffit à dire non.
Indice 3
Une relation réflexive, symétrique et transitive est une relation d'équivalence : ses classes sont les groupes d'éléments en relation entre eux.
Voir le corrigé
Connecte-toi pour voir le corrigé
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données
Pour revoir la notion : chapitre 2 du cours Ensembles, Union, intersection, complémentaire et diagrammes de Venn.
Tes réponses
Connecte-toi pour faire cet exercice
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données