Mathématiques pour l'informatique 201-N11 • Cégep à Montréal
La théorie des ensembles paraît abstraite jusqu'au premier contrôle, où l'on découvre que la moitié des points se perdent sur deux symboles : et . Écrire n'est pas une maladresse d'écriture, c'est une phrase qui n'a pas de sens.
Cette fiche rassemble les gestes qui décident : distinguer les deux niveaux, remplir un diagramme de Venn depuis le centre, et réfuter une propriété de relation par un seul contre-exemple bien choisi.
Le fil du chapitre
Presque toutes les erreurs du chapitre viennent d'un mélange de NIVEAUX : celui des éléments et celui des ensembles, autrement dit l'appartenance et l'inclusion.
Le test à faire avant d'écrire un symbole : ce qui est à gauche est-il un élément ou un ensemble ? La réponse choisit le symbole, et l'inverse n'est jamais vrai.
Remplir un diagramme de Venn commence TOUJOURS par la région centrale, puis les intersections deux à deux, puis les zones isolées : dans cet ordre, aucune soustraction ne se fait à l'aveugle.
Une propriété se PROUVE sur tous les cas, mais se RÉFUTE par un seul contre-exemple. C'est ce qui rend la réfutation trois fois plus rapide, et c'est ce que le barème attend.
Sur un ensemble à éléments, il suffit d'aller jusqu'à : un chemin plus long repasserait par un sommet déjà visité, sans rien ajouter.
Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.
Ce qu'il ne faut pas écrire
« , puisque est dans . »
Ce qu'il faut écrire
« : est un élément. On écrirait pour dire la même chose au niveau des ensembles. »
Pourquoi : Les deux symboles relient des objets de nature différente. L'un des deux est toujours faux, et le correcteur le repère avant même de lire le raisonnement.
Ce qu'il ne faut pas écrire
« pour tout ensemble . »
Ce qu'il faut écrire
« toujours, et toujours ; mais seulement si on l'a explicitement mis dans . »
Pourquoi : L'ensemble vide est inclus partout parce qu'il n'a aucun élément à faire échouer l'inclusion. Y appartenir est tout autre chose : il faudrait qu'il soit listé comme élément.
Ce qu'il ne faut pas écrire
« a éléments, donc en a . »
Ce qu'il faut écrire
« : chaque élément est pris ou laissé. »
Pourquoi : Le choix se fait élément par élément, indépendamment : deux possibilités par élément donnent une puissance de deux, jamais un carré. Le contrôle : a exactement une partie.
Ce qu'il ne faut pas écrire
« connaissent Python et connaissent Java, donc connaissent au moins l'un des deux. »
Ce qu'il faut écrire
« : les qui connaissent les deux ont été comptés deux fois. »
Pourquoi : Le contrôle est immédiat : un sous-total supérieur à la population totale est impossible. C'est le premier réflexe de vérification du chapitre.
Ce qu'il ne faut pas écrire
« Je mets dans la zone Python, dans Java, puis j'ajuste. »
Ce qu'il faut écrire
« Je commence par la région CENTRALE, , puis je remonte : seul vaut , et seul vaut . »
Pourquoi : Chaque zone extérieure se déduit des zones intérieures déjà connues. En partant du bord, chaque nombre écrit doit être corrigé ensuite, et les corrections s'emmêlent.
Ce qu'il ne faut pas écrire
« La relation n'est pas symétrique, donc elle est antisymétrique. »
Ce qu'il faut écrire
« Antisymétrique signifie : si ET y sont, alors . Une relation peut n'être ni l'une ni l'autre. »
Pourquoi : Les deux propriétés ne sont pas complémentaires. La relation n'est ni symétrique, puisque manque, ni antisymétrique, puisque .
Ce qu'il ne faut pas écrire
« et sont dans , et aussi, donc est transitive. »
Ce qu'il faut écrire
« Il faut vérifier TOUS les couples enchaînables ; un seul enchaînement sans raccourci suffit à réfuter la transitivité. »
Pourquoi : Une propriété universelle se prouve sur tous les cas et se réfute par un seul. Vérifier un cas favorable ne démontre rien du tout.
Ce qu'il ne faut pas écrire
« La classe de et celle de ont un élément commun, mais elles restent distinctes. »
Ce qu'il faut écrire
« Deux classes ayant un élément commun sont ÉGALES : les classes forment une partition. »
Pourquoi : Si appartient aux deux classes, la transitivité relie tous les éléments de l'une à tous ceux de l'autre. Il n'y a donc pas de chevauchement partiel possible.
Ce qu'il ne faut pas écrire
« J'ajoute les couples obtenus par et c'est terminé. »
Ce qu'il faut écrire
« La fermeture est la réunion de , , jusqu'à : un chemin peut traverser trois arcs ou plus. »
Pourquoi : Ajouter les raccourcis de longueur deux crée de nouveaux enchaînements, qui en créent d'autres. Sur sommets, un chemin utile ne dépasse jamais arcs, mais il peut les atteindre.
On liste les couples, puis on teste dans cet ordre, en cherchant d'abord à RÉFUTER.
Si un élément n'a pas son couple → la relation n'est pas réflexive, et c'est terminé
Exemple : sur un ensemble à trois éléments, il manque le couple 3-3
c'est le test le plus rapide : il se lit sur la diagonale de la matrice
Si un couple y est sans que y soit → elle n'est pas symétrique
Exemple : présent, absent
Si deux couples et y sont avec → elle n'est pas antisymétrique
Exemple : et avec
Si deux couples et y sont sans → elle n'est pas transitive
Exemple : et sans
Si aucun contre-exemple n'apparaît → démontrer la propriété dans le cas général, en partant des hypothèses
Exemple : « soit et dans ; alors... »
L'ordre compte : réflexivité d'abord, car elle se lit d'un coup d'œil sur la diagonale et disqualifie aussitôt un ordre comme une équivalence.
On regarde ce que l'énoncé demande de compter.
Si les éléments d'une réunion de deux ensembles qui se recouvrent →
Exemple :
Si les éléments d'une réunion de trois ensembles → les trois effectifs, moins les trois intersections doubles, plus l'intersection triple
Exemple :
Si les éléments qui ne sont dans AUCUN des ensembles → effectif total moins le cardinal de la réunion
Exemple :
Si les sous-ensembles d'un ensemble → , y compris l'ensemble vide et lui-même
Exemple :
Si les couples d'un produit cartésien → , l'ordre comptant dans un couple
Exemple : couples
Un diagramme de Venn rend l'inclusion-exclusion inutile : une fois les sept régions remplies, tout se lit par simple addition. C'est aussi ce qui permet de vérifier la formule.
Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.
Quand l'utiliser : L'énoncé demande de montrer que deux expressions ensemblistes sont égales, comme une loi de De Morgan.
Phrase de conclusion
« Soit . Alors et , donc . La réciproque se démontre de même, donc les deux ensembles sont égaux. »
Le piège : Ne faire qu'une inclusion et conclure à l'égalité : le barème compte les deux sens séparément.
Barème : 1,5 point par inclusion, 0,5 point la conclusion. Un raisonnement par équivalences vaut les trois points s'il est écrit avec des « si et seulement si ».
Quand l'utiliser : L'énoncé donne une relation et demande sa nature.
Phrase de conclusion
« est réflexive, symétrique et transitive : c'est une relation d'équivalence, et ses classes forment une partition de . »
Le piège : Conclure « ce n'est pas une relation d'ordre » sans dire laquelle des trois propriétés échoue ni donner le contre-exemple.
Barème : 0,5 point par propriété correctement tranchée avec sa justification, 1 point la conclusion nommée.
Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.
Le total ne dépasse pas la population
Après une inclusion-exclusion, comparer le cardinal obtenu à l'effectif total interrogé.
pour une réunion dans un groupe de : une intersection a été oubliée.
La somme des régions du diagramme
Additionner les sept régions du Venn : on doit retrouver le cardinal de la réunion, et en ajoutant l'extérieur, l'effectif total.
, plus à l'extérieur, soit .
Le compte des parties est une puissance de deux
Vérifier que le nombre de sous-ensembles trouvé est bien , et qu'il inclut l'ensemble vide et .
Un ensemble à éléments a parties, dont et lui-même.
Le contre-exemple est écrit
Chaque propriété réfutée doit être accompagnée du couple précis qui la met en défaut, pas d'une phrase générale.
« Pas transitive » sans couple ne rapporte rien ; « et sans » rapporte le point.
Sur étudiants, connaissent Python, Java, le langage C. De plus, connaissent Python et Java, Python et C, Java et C, et connaissent les trois.
Combien n'en connaissent aucun, et combien n'en connaissent qu'un seul ?
Étape 1
Région centrale : étudiants connaissent les trois langages.
Pourquoi
C'est la seule donnée qui n'a besoin d'aucune soustraction. Toutes les autres régions se déduiront d'elle, ce qui impose de commencer ici.
Étape 2
Intersections doubles exclusives : pour Python et Java seuls, pour Python et C, pour Java et C.
Pourquoi
Les de l'énoncé incluent les qui connaissent aussi le troisième langage. On retire donc la région centrale une fois, et une seule.
Étape 3
Python seul : .
Pourquoi
On retire les deux intersections, ce qui enlève deux fois les du centre ; on les remet donc une fois. C'est l'inclusion-exclusion appliquée à une seule zone.
Étape 4
Java seul : . Langage C seul : .
Pourquoi
Le même schéma se répète, avec les deux intersections qui concernent chaque ensemble. Trois calculs de même forme, donc trois occasions de vérifier le motif.
Étape 5
Réunion : , donc ne connaissent aucun des trois.
Pourquoi
La formule donne directement la réunion, et le complément se lit par soustraction sur l'effectif total. Les deux voies, formule et diagramme, doivent coïncider.
Étape 6
Exactement un langage : étudiants.
Pourquoi
« Exactement un » ne se lit que sur les régions exclusives, jamais sur les données brutes de l'énoncé, qui comptent chacun plusieurs fois.
Étape 7
Contrôle : , et .
Pourquoi
La somme des sept régions plus l'extérieur redonne l'effectif total. Un écart d'une unité signale une soustraction faite deux fois.
Conclusion rédigée
« étudiants ne connaissent aucun des trois langages, et n'en connaissent qu'un seul. »
L'erreur classique sur cet exercice : Répondre à la question « combien ne connaissent que Python » : ce nombre compte aussi ceux qui en connaissent deux ou trois.
Appartenir relie un élément à un ensemble, être inclus relie deux ensembles. Le nombre trois appartient à un ensemble qui le contient, tandis que l'ensemble formé du seul nombre trois y est inclus. Écrire le mauvais symbole ne donne pas une phrase maladroite mais une phrase sans signification.
Trente-deux, soit deux puissance cinq. Chaque élément est indépendamment pris ou laissé, ce qui fait deux possibilités par élément. Ce compte inclut l'ensemble vide et l'ensemble tout entier. Un ensemble vide a donc exactement une partie, lui-même.
En commençant toujours par la région centrale, celle des éléments communs aux trois. On remonte ensuite aux intersections deux à deux en retirant le centre, puis aux zones isolées en retirant les deux intersections qui les touchent et en remettant le centre. Dans cet ordre, aucun nombre écrit n'a besoin d'être corrigé ensuite.
Non, les deux notions ne sont pas complémentaires. L'antisymétrie exige que la présence simultanée des deux couples force l'égalité des deux éléments. Une relation peut parfaitement n'être ni symétrique ni antisymétrique, par exemple si elle contient les couples un vers deux, deux vers un, et deux vers trois.
Seulement si elles sont égales. Dès qu'un élément appartient aux deux, la transitivité relie tous les éléments de la première à tous ceux de la seconde, et les deux classes coïncident. C'est ce qui fait des classes une partition : elles sont non vides, deux à deux disjointes, et leur réunion est l'ensemble entier.
