Mathématiques discrètes
Les mathématiques discrètes sont les mathématiques des objets séparés et dénombrables : vrai ou faux, dans un ensemble ou dehors, ce chemin-ci ou celui-là. Ce sont les maths sur lesquelles tournent les ordinateurs, et elles commencent par une logique qu'on allume et qu'on éteint.
Dernière mise à jour
Les mathématiques discrètes sont les mathématiques des objets séparés et dénombrables. Un énoncé est vrai ou faux, un élément est dans un ensemble ou non, un réseau a un lien entre deux points ou n'en a pas. Il n'y a rien entre les deux, c'est ce que veut dire « discret », et c'est exactement ainsi qu'un ordinateur voit le monde.
Un premier cours couvre six thèmes : la logique, les ensembles, le dénombrement, les graphes, l'arithmétique et la démonstration. La logique vient en premier, parce que tous les autres thèmes s'écrivent avec elle. Choisissez un connecteur ci-dessous et basculez p et q.
Table de vérité de p ∧ q
| p | q | p ∧ q |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
Basculez p et q, ou cliquez sur une ligne. La ligne en surbrillance est celle qu'ils désignent.
Lisez p comme « x est dans A » et q comme « x est dans B ». Les zones coloriées sont celles où l'énoncé est vrai ; le point est la ligne actuelle.
p ∧ q
Se lit p et q
Avec ces valeurs, p ∧ q est vrai.
Vrai seulement quand p et q sont vrais tous les deux.
En ensembles ET, c'est l'intersection : x est dans A ∩ B exactement quand x est dans A et x est dans B.
La logique : énoncés et connecteurs
Un énoncé (ou proposition) est une phrase qui est soit vraie soit fausse, comme « 7 est premier » ou « il pleut ». La logique construit des énoncés plus grands à partir de plus petits avec quelques connecteurs, et une table de vérité donne le résultat pour chaque combinaison d'entrées.
| symbole | nom | se lit | vrai quand |
|---|---|---|---|
| ∧ | ET, conjonction | « p et q » | les deux sont vrais |
| ∨ | OU, disjonction | « p ou q » | au moins l'un est vrai |
| ¬ | NON, négation | « non p » | p est faux |
| ⊕ | XOR, ou exclusif | « p ou q, mais pas les deux » | exactement l'un est vrai |
| → | IMPLIQUE, implication | « si p, alors q » | dans tous les cas sauf p vrai et q faux |
| ↔ | SSI, équivalence | « p si et seulement si q » | p et q ont la même valeur |
Deux de ces connecteurs surprennent. Le OU logique est inclusif : « p ou q » est vrai quand les deux sont vrais, contrairement au « fromage ou dessert ? » de tous les jours. La version exclusive a son propre nom, XOR.
L'autre est IMPLIQUE. p → q n'est faux que sur une seule ligne, quand p est vrai et q est faux. Voyez-le comme une promesse : « s'il pleut, je prendrai un parapluie ». La promesse n'est rompue que s'il pleut et qu'il n'y a pas de parapluie. Un jour sec, la promesse n'a pas été rompue, quoi que vous ayez emporté : l'énoncé compte donc comme vrai.
Énoncés équivalents
Deux énoncés sont équivalents quand leurs tables de vérité coïncident sur chaque ligne. Dans le widget, choisissez OU et niez p : la colonne de ¬p ∨ q est identique à celle de p → q, donc les deux disent la même chose.
Les équivalences les plus utiles sont les lois de De Morgan, qui disent comment NON traverse ET et OU :
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
En mots : « pas les deux » revient à « l'un ou l'autre est faux », et « ni l'un ni l'autre » revient à « les deux sont faux ». Les programmeurs s'en servent tous les jours pour réécrire une condition comme « non (connecté et vérifié) ».
Logique et ensembles sont une seule idée
Lisez p comme « x est dans A » et q comme « x est dans B ». Alors ET est l'intersection, OU la réunion et NON le complémentaire, et chaque table de vérité est un diagramme de Venn colorié, c'est pourquoi le widget en dessine un à côté de la table. Les lois de De Morgan deviennent des règles sur les ensembles :
(A ∩ B)′ = A′ ∪ B′
La page sur la notation ensembliste colorie chacune de ces règles sur un diagramme cliquable.
Le dénombrement
En mathématiques discrètes, dénombrer veut dire compter sans faire la liste. Deux règles font l'essentiel du travail.
Le principe multiplicatif. Si un premier choix peut se faire de m façons et un second de n façons, le couple peut se faire de m × n façons. Un code PIN à 4 chiffres offre 10 choix pour chaque chiffre : il y a donc 10^4 = 10000 codes possibles.
Les combinaisons. Le nombre de façons de choisir k objets parmi n, quand l'ordre ne compte pas, s'écrit C(n, k). Choisir 3 garnitures parmi 8 :
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
Le numérateur compte les choix ordonnés, et diviser par 3 × 2 × 1 retire les 6 ordres dans lesquels les trois mêmes garnitures auraient pu être choisies.
La réponse est 6 × 5 divisé par 2, soit 15. Si vous avez trouvé 30, vous avez compté chaque binôme deux fois, une fois dans chaque ordre.
Les graphes
Un graphe est un ensemble de points, appelés sommets, reliés par des lignes, appelées arêtes. Il modélise tout ce qui est fait de connexions : les routes entre des villes, les amis dans un réseau social, les liens entre des pages web.
Un premier résultat : si 5 personnes se serrent toutes la main une fois, il y a C(5, 2) = 10 poignées de main. Chaque personne serre 4 mains, ce qui fait 5 × 4 = 20 mains tendues, et chaque poignée de main en réunit deux, donc 20 / 2 = 10. Ce raisonnement est le lemme des poignées de main : la somme des degrés de tous les sommets vaut le double du nombre d'arêtes.
Arithmétique et démonstration
L'arithmétique modulaire est l'arithmétique d'une horloge. 17 mod 5 vaut 2, le reste de la division de 17 par 5. Neuf heures après 8 heures, il est 5 heures sur un cadran de 12 heures, car 17 mod 12 vaut 5. La même idée, avec de très grands nombres, fait fonctionner le chiffrement RSA derrière les sites web sécurisés.
Le raisonnement par récurrence montre qu'un énoncé est vrai pour tout entier n en deux étapes : on le vérifie pour n = 1, puis on montre que s'il est vrai pour un certain n, il l'est aussi pour n + 1. C'est ainsi qu'on démontre, par exemple, que
1 + 2 + ... + n = n(n + 1) / 2
pour tout n, et pas seulement pour les valeurs qu'on a essayées.
À quoi servent les mathématiques discrètes
- La programmation : chaque instruction if est de la logique, et les lois de De Morgan réécrivent les conditions.
- Les bases de données : une requête qui joint ou filtre des tables est une suite d'opérations sur des ensembles.
- Les algorithmes : le dénombrement dit combien d'étapes prend un programme quand l'entrée grandit.
- Les réseaux et les cartes : les plus courts chemins et les réseaux sociaux sont des problèmes de graphes.
- La sécurité : le chiffrement repose sur l'arithmétique et l'arithmétique modulaire.
- Le matériel : un processeur est fait de portes logiques, qui sont des tables de vérité gravées dans le silicium.
Les mathématiques discrètes sont-elles difficiles ?
Elles sont difficiles autrement que l'algèbre et l'analyse. Il y a peu de formules à retenir et les calculs sont petits, mais beaucoup de questions demandent de démontrer quelque chose plutôt que de le calculer, et écrire un raisonnement convaincant est une compétence nouvelle pour la plupart des étudiants.
Ce qui aide le plus, c'est de traiter de petits cas à la main avant de chercher le motif : dessinez le diagramme de Venn, écrivez la table de vérité, listez chaque cas. La notation paraît lourde au début, mais l'essentiel se résume aux symboles de cette page et de la page sur la notation ensembliste.
Questions fréquentes
- Que sont les mathématiques discrètes ?
- La branche des mathématiques qui étudie des objets séparés et dénombrables plutôt que des grandeurs qui varient de façon continue. Ses principaux thèmes sont la logique, les ensembles, le dénombrement, les graphes, l'arithmétique et la démonstration. L'analyse se demande comment les choses changent de façon continue ; les mathématiques discrètes se demandent combien, lesquels, et si un énoncé est vrai.
- Les mathématiques discrètes sont-elles difficiles ?
- Elles sont difficiles autrement que l'analyse. Il y a moins de formules à appliquer et plus de raisonnements à construire, et pour beaucoup d'étudiants c'est le premier cours centré sur l'écriture de démonstrations. Les calculs sont en général légers. Ceux qui les trouvent difficiles s'adaptent surtout à la démonstration, et cela progresse vite en s'entraînant sur de petits exemples.
- À quoi servent les mathématiques discrètes ?
- À presque tout en informatique. La logique fait fonctionner les circuits et les instructions if, les ensembles sont à la base des requêtes sur les bases de données, le dénombrement dit combien de temps prend un algorithme, les graphes modélisent les réseaux et les cartes, et l'arithmétique est le fondement du chiffrement qui protège les paiements en ligne.
- Quels thèmes couvre un cours de mathématiques discrètes ?
- Un premier cours typique couvre la logique des propositions et les tables de vérité, les ensembles et les diagrammes de Venn, les fonctions et les relations, les techniques de démonstration dont la récurrence, le dénombrement avec les permutations et les combinaisons, les probabilités de base, les graphes et les arbres, et l'arithmétique modulaire. Certains cours ajoutent les suites définies par récurrence et l'algèbre de Boole.
- Faut-il des mathématiques discrètes pour faire de l'informatique ?
- Oui. Presque toutes les formations en informatique en exigent, en général en première ou en deuxième année, car les algorithmes, les structures de données et la théorie du calcul les supposent toutes. Pour programmer, on peut commencer sans, mais la logique, les ensembles et le dénombrement reviennent dans le code de tous les jours plus tôt qu'on ne le pense.
- Quelle différence entre mathématiques discrètes et continues ?
- Les mathématiques discrètes traitent des valeurs qu'on peut énumérer une par une, comme les nombres entiers, le vrai et le faux, ou les nœuds d'un réseau. Les mathématiques continues, comme l'analyse, traitent des grandeurs qui peuvent prendre n'importe quelle valeur dans un intervalle, comme le temps, la distance ou la température.
- Qu'est-ce qu'une table de vérité ?
- Un tableau qui liste toutes les combinaisons de vrai et de faux pour les entrées d'un énoncé logique, avec la valeur de l'énoncé pour chacune. Avec deux entrées p et q, il y a quatre lignes. Une table de vérité permet de prouver que deux énoncés sont équivalents : si leurs colonnes coïncident sur chaque ligne, ils sont toujours d'accord.
