Maîtriser le vocabulaire et les notations de la théorie des ensembles (appartenance, inclusion, cardinal).
Effectuer les opérations ensemblistes : union, intersection, complémentaire, différence.
Connaître et appliquer les lois de De Morgan.
Comprendre le produit cartésien, les relations binaires et la notion d'application.
Appliquer la formule d'inclusion-exclusion au calcul de cardinaux et de probabilités.
Calculer des arrangements et des combinaisons ; construire le triangle de Pascal.
Établir le lien entre opérations ensemblistes et requêtes SQL (UNION, INTERSECT, EXCEPT).
Situation professionnelle — Technicienne en informatique industrielle
Contexte : Aurélie est technicienne support dans une entreprise de logistique
gérant plusieurs milliers de références produits. Elle administre une base de données relationnelle
recensant fournisseurs, catégories de produits et mouvements de stock.
Sa responsable lui confie deux demandes :
Extraire les fournisseurs qui livrent à la fois la catégorie A et la catégorie B (audit croisé).
Extraire les fournisseurs qui livrent A mais pas B (renégociation des contrats B).
Aurélie reconnaît une intersection (requête 1) et une différence ensembliste (requête 2).
Elle formalise le problème en notations mathématiques avant d'écrire les requêtes SQL.
Ce chapitre fournit tous les outils pour raisonner de la même façon.
1. Notions fondamentales
Définition — Ensemble
Un ensemble est une collection bien définie d'objets appelés éléments.
On note les ensembles par des lettres majuscules. Les éléments se désignent en extension (liste)
ou en compréhension (propriété) :
Extension : \(A = \{1,\, 3,\, 5,\, 7,\, 9\}\)
Compréhension : \(A = \{x \in \mathbb{N} \mid x \text{ impair},\; x \leq 9\}\)
Un ensemble peut être fini (nombre d'éléments déterminé) ou infini
(\(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{R}\), etc.).
Définition — Appartenance
On note \(x \in A\) si \(x\) est un élément de \(A\), et \(x \notin A\) sinon.
Exemple : Pour \(A = \{2, 4, 6, 8\}\) : \(4 \in A\) et \(5 \notin A\).
Définition — Inclusion
\(A\) est inclus dans \(B\), noté \(A \subseteq B\), si tout élément de \(A\) appartient à \(B\) :
\[A \subseteq B \iff \bigl(\forall x,\; x \in A \Rightarrow x \in B\bigr)\]
Inclusion stricte : \(A \subsetneq B\) signifie \(A \subseteq B\) et \(A \neq B\).
Égalité : \(A = B \iff A \subseteq B\) et \(B \subseteq A\).
Exemple : \(\{2, 4\} \subseteq \{1,2,3,4,5\}\) mais \(\{2,6\} \not\subseteq \{1,2,3,4,5\}\).
Définition — Ensemble vide et ensemble universel
L'ensemble vide \(\emptyset\) ne contient aucun élément.
Il est inclus dans tout ensemble : \(\emptyset \subseteq A\) pour tout \(A\).
L'ensemble universel \(E\) (ou \(\Omega\)) contient tous les éléments du contexte.
Tout sous-ensemble vérifie \(A \subseteq E\).
Définition — Cardinal
Le cardinal de \(A\), noté \(|A|\) ou \(\text{Card}(A)\), est le nombre d'éléments de \(A\). Exemples : \(|\{a,b,c,d\}| = 4\) • \(|\emptyset| = 0\) • \(|\{0\}| = 1\).
Propriété — Ensemble des parties
L'ensemble de tous les sous-ensembles de \(A\), noté \(\mathcal{P}(A)\), vérifie \(|\mathcal{P}(A)| = 2^{|A|}\).
Exemple : \(A = \{1,2,3\}\) donne \(|\mathcal{P}(A)| = 8\) parties :
\(\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\).
Exemple — Base de données produits
\(A = \{\text{REF01, REF03, REF05, REF07}\}\) (en stock) \(|A| = 4\)
\(B = \{\text{REF02, REF03, REF05, REF09}\}\) (commandés) \(|B| = 4\)
Dans toute la section, \(A\) et \(B\) sont des sous-ensembles de l'ensemble universel \(E\).
Union A ∪ B
Éléments dans A ou B (ou les deux)
Intersection A ∩ B
Éléments dans A et B à la fois
Complémentaire Ā
Éléments de E non dans A
Différence A \ B
Éléments dans A mais pas dans B
Définition — Union
\[A \cup B = \{x \in E \mid x \in A \text{ ou } x \in B\}\]
Exemple : \(\{1,2,3\} \cup \{2,3,4,5\} = \{1,2,3,4,5\}\)
Propriétés de l'union
Commutativité : \(A \cup B = B \cup A\) •
Associativité : \((A \cup B) \cup C = A \cup (B \cup C)\)
Élément neutre : \(A \cup \emptyset = A\) •
Idempotence : \(A \cup A = A\) •
Absorption : \(A \cup E = E\)
Distributivité : \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
Définition — Intersection
\[A \cap B = \{x \in E \mid x \in A \text{ et } x \in B\}\]
Exemple : \(\{1,2,3\} \cap \{2,3,4,5\} = \{2,3\}\)
Si \(A \cap B = \emptyset\), \(A\) et \(B\) sont disjoints.
Propriétés de l'intersection
Commutativité, associativité, élément neutre \(E\), élément absorbant \(\emptyset\).
Distributivité : \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
Exemple : \(E=\{1..5\}\), \(A=\{1,3,5\}\) donc \(\bar{A}=\{2,4\}\).
Définition — Différence
\[A \setminus B = A \cap \bar{B} = \{x \in E \mid x \in A \text{ et } x \notin B\}\]
Exemple : \(\{1,2,3,4\} \setminus \{2,4,6\} = \{1,3\}\)
Attention : la différence n'est pas commutative (\(A \setminus B \neq B \setminus A\) en général).
2.5 Diagrammes de Venn
Le rectangle représente \(E\), les ellipses les ensembles \(A\) et \(B\).
La zone colorée illustre l'opération.
Théorème — Lois de De Morgan
\[\overline{A \cup B} = \bar{A} \cap \bar{B}\]
\[\overline{A \cap B} = \bar{A} \cup \bar{B}\]
En mots : le complémentaire d'une union est l'intersection des complémentaires,
et vice versa.
Extension : \(\overline{A_1 \cup \cdots \cup A_n} = \bar{A}_1 \cap \cdots \cap \bar{A}_n\)
Attention
Ne pas confondre \(\overline{A \cup B}\) avec \(\bar{A} \cup \bar{B}\).
Par De Morgan : \(\overline{A \cup B} = \bar{A} \cap \bar{B}\), pas \(\bar{A} \cup \bar{B}\) !
1re loi : \(A \cup B = \{1,2,3,4\}\) donc \(\overline{A \cup B} = \{5,6\}\).
Et \(\bar{A} \cap \bar{B} = \{4,5,6\} \cap \{1,5,6\} = \{5,6\}\). ✓
2e loi : \(A \cap B = \{2,3\}\) donc \(\overline{A \cap B} = \{1,4,5,6\}\).
Et \(\bar{A} \cup \bar{B} = \{4,5,6\} \cup \{1,5,6\} = \{1,4,5,6\}\). ✓
3. Produit cartésien et relations
3.1 Produit cartésien
Définition — Produit cartésien
\[A \times B = \{(a, b) \mid a \in A,\; b \in B\}\]
On a \(|A \times B| = |A| \times |B|\).
Attention : \(A \times B \neq B \times A\) en général (les couples sont ordonnés).
Exemple :
\(A = \{1, 2\}\), \(B = \{x, y, z\}\) :
\(A \times B = \{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}\), cardinal \(= 2 \times 3 = 6\).
Application BD : si \(A\) = clients et \(B\) = produits,
une table de commandes est un sous-ensemble de \(A \times B\).
3.2 Relations binaires
Définition — Relation binaire
Une relation binaire \(\mathcal{R}\) de \(A\) dans \(B\) est un sous-ensemble de \(A \times B\).
On note \(a \mathrel{\mathcal{R}} b\) si \((a,b) \in \mathcal{R}\).
Une relation sur \(A\) (de \(A\) dans \(A\)) peut être :
• Réflexive : \(\forall a,\; a\,\mathcal{R}\,a\)
• Symétrique : \(a\,\mathcal{R}\,b \Rightarrow b\,\mathcal{R}\,a\)
• Antisymétrique : \(a\,\mathcal{R}\,b\) et \(b\,\mathcal{R}\,a \Rightarrow a=b\)
• Transitive : \(a\,\mathcal{R}\,b\) et \(b\,\mathcal{R}\,c \Rightarrow a\,\mathcal{R}\,c\)
Définition — Application
Une application \(f : A \to B\) est une relation telle que tout \(a \in A\)
a exactement un image \(f(a) \in B\).
• Injective : \(f(a_1)=f(a_2) \Rightarrow a_1=a_2\)
• Surjective : tout \(b \in B\) a au moins un antécédent
• Bijective : injective et surjective (correspondance parfaite 1-1)
4. Formule du cardinal (inclusion-exclusion)
Formule fondamentale — 2 ensembles
\[|A \cup B| = |A| + |B| - |A \cap B|\]
Si \(A\) et \(B\) sont disjoints : \(|A \cup B| = |A| + |B|\). Intuition : en additionnant \(|A|\) et \(|B|\), on compte deux fois les éléments de \(A \cap B\).
Extension à 3 ensembles
\[|A \cup B \cup C| = |A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|A \cap B \cap C|\]
Exemple 1 — Sondage clients :
200 clients interrogés. 120 satisfaits du SAV (ensemble \(A\)), 90 satisfaits du délai (ensemble \(B\)),
60 satisfaits des deux (\(A \cap B\)).
Satisfaits d'au moins un critère : \(|A \cup B| = 120+90-60 = \mathbf{150}\)
Insatisfaits des deux : \(200-150 = \mathbf{50}\)
Exemple 2 — Contrôle qualité (3 défauts) :
Sur 500 pièces : défaut de surface \(|A|=80\), dimensionnel \(|B|=60\), matière \(|C|=40\).
\(|A \cap B|=15\), \(|A \cap C|=10\), \(|B \cap C|=8\), \(|A \cap B \cap C|=3\).
Application en probabilités
Dans un espace de probabilité quelconque :
\[P(A \cup B) = P(A) + P(B) - P(A \cap B)\]
C'est la formule des probabilités totales généralisée.
Si \(A\) et \(B\) sont incompatibles (\(A \cap B = \emptyset\)) : \(P(A \cup B) = P(A)+P(B)\).
5. Dénombrement
5.1 Règles fondamentales
Règle de la somme
Si une expérience peut donner \(m\) résultats ou \(n\) résultats (cas exclusifs),
le nombre total est \(m + n\). Exemple : 4 outils manuels ou 3 électriques : \(4+3=7\) choix.
Règle du produit
Si une procédure comporte \(k\) étapes indépendantes avec \(n_1, \ldots, n_k\) possibilités chacune,
le nombre total est \(n_1 \times n_2 \times \cdots \times n_k\). Exemple : Code = 1 lettre (26) + 2 chiffres (10×10) : \(26 \times 100 = 2600\) codes.
5.2 Factorielle et permutations
Définition — Factorielle
\[n! = 1 \times 2 \times 3 \times \cdots \times n \qquad (0! = 1)\]
Le nombre de permutations (arrangements de \(n\) éléments parmi eux-mêmes) est \(n!\). Exemple : 4 pièces en ligne : \(4! = 24\) dispositions.
5.3 Arrangements (ordre compte, sans remise)
Définition — Arrangements \(A_n^k\)
Liste ordonnée de \(k\) éléments distincts tirés parmi \(n\) (\(k \leq n\)) :
\[A_n^k = \frac{n!}{(n-k)!} = n(n-1)\cdots(n-k+1)\]
Exemple — Code PIN à 4 chiffres distincts parmi \(\{0..9\}\) :
\(A_{10}^4 = 10 \times 9 \times 8 \times 7 = 5\,040\)
5.4 Combinaisons (ordre indifférent, sans remise)
Définition — Combinaisons \(\binom{n}{k}\)
Sous-ensemble de \(k\) éléments tirés parmi \(n\) (l'ordre ne compte pas) :
\[\binom{n}{k} = C_n^k = \frac{n!}{k!\,(n-k)!} = \frac{A_n^k}{k!}\]
Propriétés des coefficients binomiaux
\(\binom{n}{0}=\binom{n}{n}=1\) •
\(\binom{n}{1}=n\) •
Symétrie : \(\binom{n}{k}=\binom{n}{n-k}\)
Relation de Pascal : \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\)
Somme d'une ligne : \(\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n\)
Exemple — Contrôle qualité :
Un technicien prélève 5 pièces parmi 20 (ordre sans importance) :
\[\binom{20}{5} = \frac{20 \times 19 \times 18 \times 17 \times 16}{5!} = \frac{1\,860\,480}{120} = 15\,504\]
5.5 Triangle de Pascal
Chaque nombre est la somme des deux nombres directement au-dessus.
1
1
1
1
2
1
1
3
3
1
1
4
6
4
1
Ligne \(n\) : \(\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}\) — lignes \(n=0\) à \(n=4\).
Formule
Ordre
Remise
Nombre
Permutations
Oui
Non
\(n!\)
Arrangements \(A_n^k\)
Oui
Non
\(\dfrac{n!}{(n-k)!}\)
Combinaisons \(\binom{n}{k}\)
Non
Non
\(\dfrac{n!}{k!(n-k)!}\)
Tirage avec remise (ordonné)
Oui
Oui
\(n^k\)
6. Applications informatiques — Opérations ensemblistes en SQL
Les SGBD relationnels implémentent directement les opérations ensemblistes sur des tables.
Opération
Notation
SQL standard
Union (sans doublons)
\(A \cup B\)
UNION
Union (avec doublons)
—
UNION ALL
Intersection
\(A \cap B\)
INTERSECT
Différence
\(A \setminus B\)
EXCEPT (Oracle : MINUS)
UNION (\(A \cup B\))
-- Tous les fournisseurs (catA ou catB)SELECT id_fourn FROM livraisons_catA
UNIONSELECT id_fourn FROM livraisons_catB;
INTERSECT (\(A \cap B\))
-- Fournisseurs livrant A ET BSELECT id_fourn FROM livraisons_catA
INTERSECTSELECT id_fourn FROM livraisons_catB;
EXCEPT (\(A \setminus B\))
-- Fournisseurs livrant A mais PAS BSELECT id_fourn FROM livraisons_catA
EXCEPTSELECT id_fourn FROM livraisons_catB;
De Morgan en SQL
-- Fournisseurs ni catA ni catB-- = complement(A union B)SELECT id_fourn FROM tous_fournisseurs
EXCEPT
(SELECT id_fourn FROM livraisons_catA
UNIONSELECT id_fourn FROM livraisons_catB);
Règle SQL
Pour UNION / INTERSECT / EXCEPT :
les deux requêtes doivent retourner le même nombre de colonnes
avec des types compatibles. Les noms des colonnes sont ceux de la première requête.
Méthode — Résoudre un problème de dénombrement
Identifier l'ensemble universel et les ensembles en jeu.
Traduire les conditions en opérations ensemblistes.
Choisir la formule :
ordre + sans remise → \(A_n^k\) ;
sans ordre + sans remise → \(\binom{n}{k}\) ;
avec remise → \(n^k\) ;
cardinal d'union → inclusion-exclusion.
Calculer (factorielles ou touche nCr de la calculatrice).
Vérifier la cohérence (ordre de grandeur, cas limite).
À retenir — Théorie des ensembles et dénombrement
Opérations et lois
\(A \cup B\) : union (« ou »)
\(A \cap B\) : intersection (« et »)
\(\bar{A} = E \setminus A\) : complémentaire
\(A \setminus B = A \cap \bar{B}\) : différence
De Morgan : \(\overline{A \cup B} = \bar{A} \cap \bar{B}\)
De Morgan : \(\overline{A \cap B} = \bar{A} \cup \bar{B}\)