Exercice 5 / 9Moyen
Les parties d'un ensemble de droits
À toi
Sur un fichier, on peut donner les droits D = {lecture ; écriture ; exécution}. Une combinaison de droits est une partie de D.
- Combien y a-t-il de combinaisons de droits, card(P(D)) ?
- Combien de parties de D ont exactement 2 éléments ?
- Une application propose 7 options, chacune activée ou non. Combien de configurations différentes existe-t-il ?
- « {lecture} ∈ P(D) » est-il vrai ?
- « lecture ⊂ D » est-il vrai ?
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
Un ensemble de n éléments a 2ⁿ parties, en comptant ∅ et l'ensemble lui-même.
Indice 2
Pour chaque option, deux choix : activée ou non.
Indice 3
∈ relie un élément à un ensemble ; ⊂ relie deux ensembles.
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