Mathématiques discrètes

Les mathématiques discrètes fournissent le langage nécessaire au raisonnement sur les programmes et les algorithmes. Le parcours durable est :

1. propositions, prédicats et techniques de preuve ;
2. ensembles, fonctions et relations ;
3. induction et récursion ;
4. dénombrement et combinatoire ;
5. graphes et arbres ;
6. probabilités discrètes.

Cette page est une référence initiale sur les preuves et les structures finies, pas un cours complet de combinatoire ou de théorie des graphes. Berkeley CS 70 développe les preuves et les probabilités ; les notes algorithmiques se trouvent dans la branche Informatique.

Énoncés et preuves

Une proposition est vraie ou fausse ; un prédicat comme $P(n)$ devient une proposition lorsque sa variable est spécifiée ou quantifiée. Une affirmation universelle $\forall n\,P(n)$ exige un argument couvrant chaque $n$ autorisé ; un contre-exemple la réfute. Une affirmation existentielle $\exists n\,P(n)$ ne demande qu'un témoin. Le domaine compte : « tout nombre a un inverse multiplicatif » est faux sur les réels à cause de zéro, mais vrai sur les réels non nuls.

L'implication $P\Rightarrow Q$ n'implique pas sa réciproque $Q\Rightarrow P$. Elle équivaut à sa contraposée $\neg Q\Rightarrow\neg P$. Pour un entier $n$, « $n$ pair implique $n^2$ pair » se prouve en écrivant $n=2k$, d'où $n^2=2(2k^2)$. Tester quelques nombres pairs illustrerait l'énoncé sans le prouver.

La récurrence prouve $P(n)$ pour tout entier $n\ge n_0$ en établissant un cas initial, puis que $P(n)$ implique $P(n+1)$. Pour $1+\cdots+n=n(n+1)/2$, le cas $n=1$ est vrai. Ajouter $n+1$ à la somme supposée donne $(n+1)(n+2)/2$, donc le cas suivant. Un invariant de boucle suit le même schéma : initialisation, préservation par une itération, puis conclusion à la sortie. La terminaison demande encore un argument distinct, par exemple une mesure entière non négative qui décroît strictement.

Compter les bons objets

Un ensemble contient des éléments distincts sans ordre. Une fonction associe exactement une sortie à chaque entrée ; une relation est un ensemble de couples sans cette obligation. Le dénombrement dépend de l'ordre et des répétitions :

Choisir $r$ objets parmi $n$ objets distincts	Nombre
Ordonnés, avec répétition	$n^r$
Ordonnés, sans répétition	$n!/(n-r)!$
Non ordonnés, sans répétition	$\binom nr=n!/[r!(n-r)!]$

Ici $n,r$ sont des entiers non négatifs, avec $r\le n$ sans répétition, et $0!=1$. Le choix vide compte une fois ; dans cette formule de dénombrement, $0^0=1$. Choisir deux personnes distinctes parmi cinq donne 20 affectations à deux rôles distincts, mais seulement 10 comités de deux personnes : chaque comité était compté dans les deux ordres. Diviser un nombre de cas favorables par le nombre total ne donne une probabilité que si les issues élémentaires sont équiprobables.

Graphes, arbres et jeux finis

Un graphe $G=(V,E)$ comprend des sommets et des arêtes. Précisez si les arêtes sont orientées, et si les boucles ou arêtes multiples sont permises. Un arbre fini simple non orienté est connexe et sans cycle ; avec $n\ge1$ sommets, il possède $n-1$ arêtes et un unique chemin simple entre deux sommets. Le nombre d'arêtes ne suffit pas : un triangle et un sommet isolé ont quatre sommets et trois arêtes, mais ne forment pas un graphe connexe.

Un arbre de jeu représente des historiques, pas seulement des positions distinctes : plusieurs historiques peuvent atteindre la même position. Les stratégies gagnantes dans les jeux finis emploient récurrence, invariants et arbres pour distinguer preuve d'existence, construction et exécution.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.