Ift1065 2
Ift1065 2
8 décembre 2023
Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Uti-
lisation Commerciale 4.0 International (CC BY-NC 4.0).
© Texte et images (sauf celles de Wikimédia et dans le domaine publique). 2023 Miklós Csűrös, Département
d’informatique et de recherche opérationnelle, Université de Montréal. [email protected]
Table des matières
Introduction 9
1 Logique propositionnelle 11
1.1 Propositions 11
1.2 Constantes, variables propositionnelles et opérateurs 11
Ordre des opérations 12
1.3 Tautologie et équivalence logique 13
1.4 Modèles et satisfiabilité 15
1.5 Formes normales 16
3 Inférence logique 23
3.1 Règles d’inférence 24
3.2 Inférence pour calcul des propositions 25
3.3 Déduction naturelle 26
Règles d’élimination et d’introduction 27
Règles dérivées 28
3.4 Égalité 28
3.5 Règles pour quantificateurs 29
3.6 Systèmes d’inférence formelle 30
3.7 Sémantique et inférence 31
2
4 Preuves 33
4.1 Preuve directe 33
4.2 Preuve indirecte 34
Preuve par contraposition 34
Preuve par contradiction 35
4.3 Stratégies de démonstration 36
Si et seulement si 36
Preuve par cas 36
Preuves d’existence 38
Preuve d’unicité 39
5 Ensembles 41
5.1 Appartenance et égalité 41
Notation par compréhension 42
Notation en image 42
Cardinalité d’un ensemble 43
5.2 Opérations ensemblistes 44
Théorie des opérations 45
5.3 Sous-ensembles 46
Propriétés de la relation d’inclusion 46
Techniques de preuve avec ensembles 47
5.4 Collections d’ensembles 47
Ensemble puissance 48
5.5 Paradoxe du barbier qui rase ceux qui ne se rasent pas 49
6 Relations et fonctions 51
6.1 Produit cartésien 51
Définition de couples 51
6.2 Relations binaires 53
Inverse et complément 53
Équivalence et ordre 54
3
6.3 Fonctions 55
Opérateurs binaires 56
L’univers des fonctions 56
La fonction vide 56
Composition de fonctions 56
6.4 Bijections 58
Techniques de preuve 58
Inverse d’une fonction 58
Composition et les bijections 59
Cardinalité par bijection 59
7 Séquences et induction 61
7.1 Séquences 61
Le produit cartésien généralisé 62
7.2 Chaînes de caractères 63
7.3 Induction mathématique 64
Preuve par induction 64
Choisir le cas de base 66
Induction d’ordre 2 66
Induction généralisée 67
7.4 Minimum, maximum et bon ordre 68
7.5 Fonction de plancher 69
Calcul avec le plancher 69
Système de numération 70
9 Structures récursives 81
9.1 Structures récursives 81
Successeur dans la théorie axiomatique et les ordinaux finis 81
Chaînes et concaténation 82
Listes et arbres 83
Syntaxe 83
9.2 Induction structurale 84
Théorie de chaînes avec concaténation 84
Induction avec arbres 86
9.3 Construction des entiers 87
Axiomes de Peano 87
Propriétés des opérations arithmétiques 88
Les entiers négatifs 89
11 Divisibilité et congruence 93
11.1 Divisibilité 93
5
11.2 Congruences 95
Arithmétique modulaire 96
Types entiers en programmation 98
11.3 Les nombres premiers et le plus grand commun diviseur 99
Plus grand commun diviseur : l’algorithme d’Euclide 100
Décomposition en produit de facteurs premiers 102
12 Algorithmes 105
12.1 Modèles de calcul 105
12.2 Correction et efficacité 107
Exactitude 107
Complexité 107
12.3 Analyse de temps de calcul 108
Meilleur, pire, ou moyen 108
12.4 Tri par sélection et tri par insertion 109
12.5 Algorithmes récursifs 111
Algorithme et définition récursive 111
Penser en récurrences 111
Diviser pour régner 112
Programmation dynamique 113
14 Dénombrement 129
14.1 Égalité et ordre 129
14.2 Principe de multiplication 130
Principe d’exponentiation 130
Permutations 131
14.3 Principe d’addition 132
Principe de soustraction 133
14.4 Principe de division 134
Combinaisons 134
14.5 Inclusion-exclusion 136
14.6 Coefficients binomiaux 138
Identités remarquables 138
Coefficients multinomiaux 139
14.7 Principe des tiroirs 140
15 Graphes 143
15.1 Terminologie 143
Adjacence, incidence et degré 144
15.2 Opérations et preuves avec graphes 145
Poignées de main 145
15.3 Chemins 147
15.4 Couplage dans les graphes bipartis 148
Théorème de Kőnig 148
Ensembles défectueux 149
Hypergraphes et familles d’ensembles 150
Matrices 0-1 150
Théorème de Cantor-Schröder-Bernstein 151
17 Arbres 159
17.1 Forêts et arbres 159
17.2 Arbre enraciné 162
17.3 Hauteur et profondeur 163
Implémentations informatiques 164
17.4 Parcours 165
17.5 Arbre syntaxique 166
Ambiguïté et les parenthèses 167
Évaluation de formules 167
Liaison de variables 168
Bibliographie 185
Introduction
C E S N O T E S D E C O U R S accompagnent et complémentent le livre principal
du cours (en version française ou anglaise) :
RosenFR Kenneth H. Rosen. Mathématiques discrètes (édition révisée). Che-
nelière Education, 2002. Traduction française de la 3e édition anglaise.
RosenEN Kenneth H. Rosen. Discrete Mathematics and Its Applications 7th
edition. McGraw-Hill, 2012.
D’autres références à des articles Wikipédia sont indiquées sur la marge par
le logo .
......................................................................................
Calendrier
x + 2 > 0 n’est pas une proposition (parce qu’elle contient une variable x libre)
x + 2 > x n’est pas une proposition (même si toujours vraie — parce qu’elle contient la variable x)
«Je m’excuse.» N’est pas une proposition (mais plutôt un énoncé performatif).
priorité opération notation variantes TABLE 1.5: Ordre et notation des opéra-
tions logiques de base. La dernière colonne
plus forte négation ¬p p̄ montre des variations communes de nota-
↑ conjonction (et) p∧q pq tion.
disjonction (ou) p∨q p+q
↓ conditionnel p→q p ⇒ q, p ⊃ q
plus faible biconditionnel p↔q p⇔q
bilité d’une troisième valeur logique ou le principe du tiers exclu (p doit être p ∨ ( p ∧ q) ≡ p
(absorption)
p ∧ ( p ∨ q) ≡ p
faux ou vrai). La contradiction fondamentale ( p ∧ ¬ p) exprime le principe de
¬( p ∧ q) ≡ ¬ p ∨ ¬q
non-contradiction (p ne peut être faux et vrai en même temps). (De Morgan)
¬( p ∨ q) ≡ ¬ p ∧ ¬q
Si la proposition biconditionnelle A ↔ B est une tautologie, alors les
formules A et B sont égales pour toutes valeurs de vérité aux variables dans A
et B, et donc elles ont des tables de vérité identiques. En conséquence, les TABLE 1.7: Équivalences logiques avec
propositions conditionnelles
deux formules sont équivalentes pour le calcul.
p → q ≡ ¬p ∨ q
Définition 1.3. Deux propositions p et q sont dites logiquement équivalentes
( p → q) ∧ ( p → r ) ≡ p → (q ∧ r )
quand p ↔ q est une tautologie, et alors on écrit p ≡ q . ( p → r ) ∧ (q → r ) ≡ ( p ∨ q) → r
( p → q) ∨ ( p → r ) ≡ p → (q ∨ r )
L’équivalence p ≡ q est exploitée dans le calcul logique parce qu’on a le
( p → r ) ∨ (q → r ) ≡ ( p ∧ q) → r
droit de remplacer p par q dans tout contexte de formule. C’est notre outil
p ↔ q ≡ ( p ∧ q) ∨ (¬ p ∧ ¬q)
p ↔ q ≡ ¬ p ↔ ¬q
Théorème 1.1
p → q ≡ ¬q → ¬ p
p ↔ q ≡ ( p → q) ∧ (q → p)
p ↔ q ≡ ( p → q) ∧ (¬ p → ¬q)
14
fondamental pour évaluer les formules plus complexes, et pour développer des
preuves. Par exemple, l’équivalence p ↔ q ≡ ( p → q) ∧ (q → p) est utilisé
fréquemment quand on démontre «si et seulement si» en le séparant dans les
deux implications «si p alors q» et la réciproque «si q alors p».
Si on veut démontrer une équivalence avec juste quelques variables, le plus simple est d’afficher sa table de vérité, et
inspecter les colonnnes qui correspondent aux deux cotés de l’équivalence :
¬( p → q) ≡ p ∧ ¬q non-implication (1.3a)
p → q ≡ ¬q → ¬ p équivalence de la contraposée (1.3b)
q → p ≡ ¬ p → ¬q équivalence entre réciproque et inverse (1.3c)
p ↔ q ≡ ( p → q) ∧ (q → p) expansion avec réciproque (1.3d)
p ↔ q ≡ ( p → q) ∧ (¬ p → ¬q) expansion avec inverse (1.3e)
Démonstration. I. Preuve avec table de vérité. On confirme les équivalences par les colonnes identiques dans la table
de vérité. Voir Table 1.3 pour Eq. (1.3a).
p q p→q ¬p ¬q ¬q → ¬ p ¬ p → ¬q q→p p↔q ( p → q) ∧ (¬ p → ¬q) ( p → q) ∧ (q → p)
implication contraposée inverse réciproque
0 0 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 0 0 0 0 0
1 0 0 0 1 0 1 1 0 0 0
1 1 1 0 0 1 1 1 1 1 1
( p → q) ∧ (¬ p → ¬q) ≡ ( p → q) ∧ (q → p) ≡ p ↔ q,
Une proposition logique est satisfaisable s’il y a un modèle qui la rend f ≡ «il fait froid»
m ≡ «je mets mon manteau»
vraie. Dans ce cas-là, on peut trouver des valeurs pour des variables avec les-
u ≡ «je prends ma parapluie»
quelles la formule est vraie. La formule ( p ∨ q) ∧ (¬ p) ∧ (¬q), par exemple,
f ∧n → m axiome
n’est pas satisfaisable parce qu’elle reste fausse avec toutes valeurs de p, q.
p∧c → u axiome
Une formule est donc non-satisfaisable si et seulement si sa négation est une
tautologie. Avec le même exemple :
¬ ( p ∨ q) ∧ (¬ p) ∧ (¬q) ≡ (¬ p ∧ ¬q) ∨ p ∨ q par De Morgan
e ≡ (¬ a ∧ ¬b ∧ c) ∨ (¬ a ∧ b ∧ ¬c) ∨ ( a ∧ ¬b ∧ c) ∨ ( a ∧ b ∧ ¬c)
001 010 101 110
d ≡ (¬ a ∧ b ∧ c) ∨ ( a ∧ ¬b ∧ ¬c) ∨ ( a ∧ ¬b ∧ c) ∨ ( a ∧ b ∧ ¬c)
011 100 101 110
e ≡ ( a ∨ b ∨ c) ∧ ( a ∨ ¬b ∨ ¬c) ∧ (¬ a ∨ b ∨ c) ∧ (¬ a ∨ ¬b ∨ ¬c)
000 011 100 111
d ≡ ( a ∨ b ∨ c) ∧ ( a ∨ b ∨ ¬c) ∧ ( a ∨ ¬b ∨ c) ∧ (¬ a ∨ ¬b ∨ ¬c)
000 001 010 111
tés et aux relations des éléments dans un univers de discours. On utilise des
variables (x, y, . . .) pour dénoter ces éléments dans les énoncés. Un tel énoncé,
ou prédicat, devient une proposition quand on remplace les variables par
des éléments actuels du domaine. On dénote les prédicats comme des fonc-
tions. P( x ) est un prédicat avec un argument x dans l’univers de discours U
si P( x ) est une proposition (soit vrai soit faux) pour chaque élément x de U.
tf P
ra
au
principe de non-contradiction
(pas de vrai et faux simultanément) TABLE 2.1: Quelques domaines importants
domaine opérations relations
N +· =≤
Z +−· =≤
Q + − ·/ =≤
Définition 2.1 (Domaine). Un domaine ou univers de discours comprend (i) les R + − ·/ =≤
éléments (objets) du domaine, (ii) l’égalité (=) et d’autres relations fondamentales, ensembles ∪ ∩ −4× ∈=⊆
incluant (iii) les fonctions et les opérations sur les éléments.
Définition 2.2 (Prédicat). P( x ) est un prédicat (aussi appelé fonction pro-
positionnelle) avec un 2 argument x dans l’univers de discours U si et seulement 2. En général, le prédicat peut avoir
si P( x ) est une proposition (soit vrai soit faux) pour chaque élément x de U. 0, 1, 2, 3, . . . arguments, dénotés par
variables distinctes.
2.1 Quantificateurs
On construit une proposition sur un élément particulier par le remplace-
ment de l’argument du prédicat : M(Socrates) est la proposition «Socrates
18
est mortel». Mais on voudrait aussi formuler des propositions sur l’ensemble
des éléments du domaine : «Tous les humains sont mortels», ou «Il existe (au
moins) un être immortel.» Les propositions de ce genre sont des prédicats
quantifiés. Dans les formules logiques, on précède les arguments par des
quantificateurs 3 qui établissent les liaisons des variables. En particulier, le 3. :quantificateur logique
(fr)
symbole ∀ est utilisé dans les propositions universelles, et ∃ est utilisé dans les
propositions existentielles :
∀ x : H ( x ) → M( x ) et ∃y : ¬ M(y)
Définition 2.3. La quantification universelle d’un prédicat P( x ) est la ∀ x P( x ) exprime que P( x ) est toujours
proposition ∀ x P( x ) qui affirme que P( x ) vaut pour chaque élément du domaine : vrai (et donc jamais faux).
Si on veut un domaine restreint, on inclut la restriction dans la formule avec quantification explicite :
Construction :
Il faut quantifier chaque variable séparément dans une formule avec plus
( x 6= y) → P(y) x, y libres
qu’une variable. Dans une telle formule, un prédicat quantifié (p.e., ∀ x Q( x )) P( x ) ∧ ∀y : ( x 6= y) → ¬ P(y) x libre, y lié
contient une proposition imbriquée avec d’autres quantificateurs (p.e., ∃ x : P( x ) ∧ ∀y : ( x 6= y) → ¬ P(y) x, y liés
Q( x ) = ∀y : R( x, y)). On peut mettre en évidence les imbrications par F IGURE 2.2: Imbrication et liaison de
parenthèses, mais comme les quantificateurs ont la priorité la plus forte, on variables. La formule exprime qu’il y a
exactement un élément x qui satisfait le
peut les laisser tomber sans confusion : prédicat P.
∀ x ∀ y : x 2 + y2 ≥ 0 ≡ ∀ x : ∀ y : x 2 + y2 ≥ 0
| {z } | {z }
≡ R( x,y) ≡ Q( x )
∀ x ∀y : R( x, y) ≡ ∀ x : Q( x )
Quand les quantificateurs sont tous ∀ ou tous ∃, l’ordre n’est pas important : Observer que Q( x ) ≡ ∀ a : R( x, a) n’est
pas la même chose que S( x ) ≡ ∀ a : R( a, x )
∀ x ∀y : R( x, y) ≡ ∀y ∀ x : R( x, y) ∃ x ∃y : Z ( x, y) ≡ ∃y ∃ x : Z ( x, y) mais ∀ x : Q( x ) ≡ ∀ x : S( x ).
| {z }
≡S(y)
∀ x : Q( x ) ≡ ∀y : S(y) ∃ x ∃y : Z ( x, y) ≡ ∃ x ∃y : Z (y, x ).
Avec des quantificateurs variés, il faut faire attention à l’ordre :
∀ x ∃y : x + y = 0 ≡ ∀ x ∃y : x + y = 0 pour tout x, il existe y — cet y peut être différent pour tout x
∃y∀ x : x + y = 0 ≡ ∃y ∀ x : x + y = 0 il existe y tel que pour tout x — cet y est le même pour tout x
sont deux propositions complètement différentes.
20
∀ x ∀y : P( x, y) ≡ ∀y∀ x : P( x, y) et ∃ x ∃y : P( x, y) ≡ ∃y∃ x : P( x, y)
parce que c’est un seul joueur qui a le droit de choisir x et y dans n’importe
quel ordre.
(2) ∃ choisit δ
(3) ∀ choisit x avec c − δ < x < c ou c < x < c + δ
(4) si L − e < f ( x ) < L + e, on gagne (avec ∃).
Une preuve de la limite peut en fait suivre cette recette : prenons l’exemple
de
x2 − 1
lim = 2. (2.1)
x →1 x − 1
(1) Soit e un nombre réel positif. (2) Choisir δ = e. (3) Soit x un nombre
2
quelconque avec 1 < x < 1 + δ. On a alors 2 < xx−−11 < 2 + δ. De même,
x 2 −1
pour tout 1 − δ < x < 1, on a 2 − δ < x −1 < 2. (4) En conclusion, on a
x 2 −1
toujours x −1 − 2 < δ = e, donc la limite dans (2.1) est correcte.
21
en incluant la condition que pour tout autre y, P(y) est faux. Ou bien, avec la contraposée («si P(y) vaut, alors c’est le
même élément que x») :
∃!x : P( x ) ≡ ∃ x : P( x ) ∧ ∀y : P(y) → y = x . (2.2)
On peut aussi remplacer le conditionnel par la disjonction (y = x ∨ ¬ P(y)), et même continuer avec De Morgan («il
n’y pas d’autre élément y pour lequel P(y) soit vrai») :
∃!x : P( x ) ≡ ∃ x : P( x ) ∧ ¬ ∃y : P(y) ∧ y 6= x .
Exemple 2.4 (Théories des nombres). La théorie des nombres naturels N contient les objets 0, 1, 2, . . . , les opérations d’addition
(+) et de multiplication (·), l’ordre (≤), et la fonction de successeur s(n). Cette dernière permettre de définir les axiomes pour la
structure :
? tout nombre naturel possède un successeur : ∀n ∈ N : s(n) ∈ N ;
? mais 0 n’est le successeur d’aucun nombre naturel : ¬∃n ∈ N : s(n) = 0 ;
et d’autres, avec les axiomes pour les opérations : p.e., ∀n : 0 · n = 0 ou a + s(b) = s( a + b).
La théorie des nombres rationnels Q contient aussi les opérations soustraction et division, satisfaisant des axiomes additionnels
1
comme ∀ x : x 6= 0 → ∃y : x · y = 1 qui exprime que tout x, à l’exception de 0, possède un inverse multiplicatif (égale à x −1 et x
dans notations usuelles).
3 Inférence logique
U N E P R E U V E établit une nouvelle proposition (la conclusion) à partir
d’autres propositions (les prémisses), selon des règles formelles d’inférence.
En général, on définit un argument comme une séquence de propositions
logiques, avec une conclusion (la dernière proposition) et des prémisses (toute
autre proposition précédant la conclusion, possiblement aucune). Un argu-
ment est dit valide si lorsque les prémisses 1 sont vraies, la conclusion est vraie 1. Donc s’il n’y a pas de prémisses, l’argu-
aussi. Noter bien qu’on peut avoir un argument valide avec des fausses pré- ment est valide quand la conclusion est une
tautologie.
misses. Si l’argument est valide et ses prémisses sont vraies, l’argument est dit
correct.
Considérons, par exemple, les deux raisonnements suivants 2 . 2. Michael Huth and Mark Ryan. Logic in
Computer Science: Modelling and Reasoning
? «Si le train est délayé, et elle ne trouve pas de taxi libre à la gare, Jeanne about Systems. Cambridge University Press,
arrivera en retard. Jeanne est arrivée à temps. Or le train était délayé. Donc, 2nd edition, 2004
elle a dû trouver un taxi.» TABLE 3.1: Table de vérité pour l’exemple
de Jeanne et Jean, avec les deux rangées où
? «S’il pleut, et Jean ne prend pas son parapluie, il sera trempé. Il est sec. Or deux prémisses, p et ¬r, sont vraies.
il pleut. Donc, il a dû prendre son parapluie.»
Tous les deux raisonnements suivent le même arrangement : on a trois p q r ¬r p ∧ ¬q p ∧ ¬q → r
···
prémisses p ∧ ¬q → r , ¬r ), et p d’où on déduit la conclusion q. 1 0 0 1 1 0
On peut afficher la structure de l’argument verticalement avec une ligne 1(p) 1(c) 0 1(p) 0 1(p)
horizontale qui sépare les prémisses de la conclusion : ···
(p)=prémisse, (c)=conclusion
p ∧ ¬q → r p ∧ ¬q → r
¬r ¬r
ou, pour effet dramatique à la fin, (3.1)
p p
q ∴q
On peut vérifier la validité de ces arguments par la table de vérité (Table 3.1). Le symbole de trois points en triangle
La vérité des trois prémisses entraîne la vérité de la conclusion. Pourtant un ∴ veut dire «par conséquent» (therefore).
argument valide peut toujours être incorrect si les prémisses sont fausses 3 : 3. En fait, on n’a même pas besoin de dé-
Jeanne a peut-être pris sa voiture et peut–être avec Jean même. battre la correction des prémisses (y incluant
l’implication). Le raisonnement suivant est
Les variables propositionnelles dans (3.1) dénotent des propositions diffé- aussi valide, «Si la terre est bleue comme une
rentes, mais du point de vue de validité, les deux arguments suivent la même orange, et les mots ne mentent pas, alors les
guêpes fleurissent vert. Les guêpes ne fleu-
recette. En fait, on peut remplacer les variables par des formules quelconques rissent pas vert. Or la terre est bleue comme
et l’argument reste valide. On peut même conclure que l’équation (3.1) nous une orange. Donc, les mots mentent.»
donne une forme d’argument qu’on peut employer dans tout contexte en rem-
plaçant p, q, r par des formules pertinentes. Par exemple, avec un ensemble
de taxis T, et avec les prédicats «t est à la gare» G (t), «t est libre» L(t), on
peut écrire «il y a un taxi libre à la gare» comme ∃t ∈ T : G (t) ∧ L(t) et
remplacer chaque occurrence de q par cette formule.
24
1 p→q prémisse
2 ¬q supposition
3 ¬p MT, 2, 1 Déduction dans notation Fitch :
? format vertical, énoncés étiquetés ;
4 ¬q → ¬ p → I, 2––3
? indentation dénote preuve conditionnelle, avec
une supposition au début ;
? justification exacte pour chaque ligne (règle
appliquée et référence à ses prémisses).
On a besoin d’une règle dans Ligne 4 qui introduit l’implication à partir de la preuve imbriquée 2––3. C’est la règle → I
du théorème suivant. La preuve exacte du théorème dépend de l’ensemble de règles qu’on adopte.
Théorème 3.1 (Théorème de Déduction). Soit Γ un ensemble (possiblement
vide) de formules (le contexte), et soit φ, ψ deux formules (l’hypothèse et la conclusion).
Alors
Γ, φ ` ψ
( → I)
Γ ` (φ → ψ)
est une forme d’argument valide.
27
¬φ ` 0
.
3.4 Égalité RAA
φ
1 ¬φ ` 0 prémisse
Les règles pour le calcul des prédicats servent à travailler avec les éléments
2 ¬¬φ ¬I, 1
du domaine. Le domaine est toujours équipé d’un prédicat d’égalité : x = y
3 φ ¬¬E, 2
peut être faux ou vrai quand x, y sont des éléments quelconques du domaine.
Il est important de souligner que cette égalité = est spécifique aux éléments du TXC φ ∨ ¬φ.
domaine. On n’écrit pas φ = ψ entre deux formules logiques (on avait défini
1 ¬(φ ∨ ¬φ) supposition
l’équivalence de propositions ≡ pour cela). La négation d’égalité 6= définit la
2 φ supposition
notion d’éléments distincts, et ainsi on a les conditions d’unicité
3 φ ∨ ¬φ ∨I1 , 2
4 0 ¬E, 3, 1
∃!xP( x ) ≡ ∃ x ∀y : P( x ) ∧ x 6= y → ¬ P(y)
5 ¬φ ¬I, 2––4
≡ ∃ x ∀y : P( x ) ∧ P(y) → x = y .
6 φ ∨ ¬φ ∨I2 , 5
7 0 ¬E, 6, 1
8 ¬¬(φ ∨ ¬φ) ¬I, 1––7
9 φ ∨ ¬φ ¬¬E, 8
29
t=u φ(t)
=I =E
t=t φ(u)
Exemple 3.2. On veut démontrer qu’il n’y a pas de plus grand nombre naturel.
L’idée de la preuve est de se servir de la propriété fondamentale des nombres naturels :
avec le successeur de n, dénoté par la fonction s(n) = n + 1, on a toujours n < s(n) :
∧E ∨E → E 0E ¬E ¬¬E
règles pour logique des propositions
∧I ∨I → I (¬E) ¬I (¬¬I dérivée)
= E ∀E ∃E
règles pour logique des prédicats
= I ∀I ∃I
Il existe d’autres systèmes d’inférence corrects, basé sur d’autres jeux de TABLE 3.10: Régles de proposition logique
dérivées dans déduction naturelle.
règles basiques. L’approche classique est celle des systèmes à la Hilbert : SH syllogisme hypothétique, SD syllogisme
on n’a que modus ponens pour l’inférence. Afin d’introduire des implica- disjonctif, RES résolution.
φ→ψ ψ→η
tions pour modus ponens, on a le droit d’instancier un des axiomes (il y en a SH .
φ→η
7). Les preuves dans un tel système sont plutôt pénibles : voir Exemple 3.3.
Déduction naturelle avec la mécanique des suppositions et démonstrations 1 φ→ψ prémisse
imbriquées, par contre, n’est pas seulement proche au raisonnement mathéma- 2 ψ→η prémisse
`φ → (ψ → φ) (K) φ∨ψ ¬φ
SD .
` φ → (ψ → χ) → (φ → ψ) → (φ → χ) (S) ψ
La technique est d’instancier les axiomes (S) et (K) avec des formules opportunes (p ou 1 φ∨ψ prémisse
p → p ici) : 2 ¬φ prémisse
3 φ supposition
1 p → ( p → p) → p → p → ( p → p) → ( p → p) (S)
φ ψ χ φ ψ φ χ 4 0 ¬E, 3, 2
2 p → ( p → p) → p (K) 5 ψ 0E, 4
φ ψ φ
6 ψ supposition
3 p → ( p → p) (K)
φ ψ
φ 7 ψ copier, 6
4 p → ( p → p) → ( p → p) MP, 2, 1 8 ψ ∨E, 1, 3––5, 6––7
5 p→p MP, 3, 4
φ∨ψ ¬φ ∨ η
RES .
ψ∨η
3.7 Sémantique et inférence
1 φ∨ψ prémisse
Les règles de l’inférence logique visent l’inférence de la vérité : 2 ¬φ ∨ η prémisse
3 supposition
φ est vrai φ → ψ est vrai φ est vrai ψ est vrai φ
(→ E) (∧I) 4 ¬¬φ ¬¬I, 3
ψ est vrai φ ∧ ψ est vrai
5 η SD, 4, 2
La sémantique de l’inférence est bien définie par les tables de vérité : on s’in- 6 ψ∨η ∨I2 , 5
téresse à 0 et 1. D’autres systèmes d’inférence accompagnent des sémantiques 7 ψ supposition
différentes. Par exemple, on définit la notion de «formule avec syntaxe cor- 8 ψ∨η ∨I1 , 7
recte» (ou formule bien formée) par des règles d’inférence de syntaxe : 9 ψ∨η ∨E, 1, 3––6, 7––8
D’autres règles de syntaxe pour la logique des prédicats incluent ∧F, ¬F,
→ F, ∀F, et ∃F, et celle de liaison de variables du domaine. Les «axiomes»
sont les formules atomiques. Les systèmes d’inférence logique et syntaxique
sont des systèmes formels.
32
(i) Un théorème est une phrase qu’on peut inférer par des règles à partir des
axiomes : ` φ.
(ii) Le système est consistant si on ne peut pas inférer toutes les phrases pos-
sibles.
(iii) Le système est correct si l’inférence est valide selon la sémantique.
La notion d’inférence dans un système formel est au cœur de l’informatique :
voir Table 3.11. Exemple 3.4 montre comment adapter la déduction naturelle
au typage.
Exemple 3.4 (Esquis d’un système d’inférence de types). Constantes : 0 dénote erreur ; au lieu de 1, on a des types t.q. int ou
Object. La flèche p → q dénote une fonction qui prend un argument de type p et retourne une valeur de type q.
? élimination de flèche = application d’une fonction
? p ∧ q dénote deux types en même temps (p.e., Object et Triangle) ; avec élimination et introduction
? p ∨ q dénote un de deux types (p.e., union dans C) avec élimination et introduction
? pas de connecteur ↔
? négation ¬ p interpretée comme p → 0 (appeler la fonction avec type p jète une erreur)
? pas de principe du tiers exclu (pas de règle ¬¬E) : ¬¬φ correspond à (φ → 0) → 0, une fonction qui jète une erreur quand on
l’appèle avec une fonction φ → 0
? mais on a l’analogue de non-contradiction ¬E :
φ ¬φ type p avec p → 0 jète erreur
car
0 erreur 0
Exemple : inférer le type de y dans x=2; y=sqrt(x); avec la fonction sqrt de type double → double et conversion automa-
tique int → double.
1 int x=2
2 int → double conversion de types
3 double → double sqrt()
4 double → E, 1, 2
5 double → E, 4, 3
Avec typage strict, par contre, sqrt est de type (double → double) ∧ (int → 0) : inférez la conséquence !
4 Preuves
Dans une preuve directe, on veut démontrer H → C, et on travaille On veut le théorème universel
∀n∀m : Q(n) ∧ Q(m) → Q(nm).
directement : on assume H et infère C, en une séquence de propositions avec On commence avec la démonstration de
justifications. Le théorème suivant est démontré directement. Q(n), Q(m) ` Q(nm) («lemme») :
1 ∃ k : n = k2 prémisse Q(n)
Théorème 4.1. Le produit de deux nombres carrés est un nombre carré.
2 ∃ k : m = k2 prémisse Q(m)
Preuve directe. (1) Supposons que m et n sont des nombres carrés. 3 p n= p2 ∃ E, 1
on finit par généralisation existentielle (∃I) pour inférer Q(nm). Table 4.1 3 Q(m) ∧ E2 , 2
donne les détails. Il n’est pas difficile d’imaginer qu’un ordinateur aurait pu 4 Q(nm) lemme, 2, 3
trouver la déduction à partir de l’énoncé formel du théorème, s’il trouve 5 Q(n) ∧ Q(m) → Q(nm) → I, 1––4
6 ∀m : Q(n) ∧ Q(m) → Q(nm) ∀I, 5
7 ∀n∀m : Q(n) ∧ Q(m) → Q(nm) ∀I, 6
34
l’étape clé d’employer distributivité. Mais pour les lecteurs et lectrices hu-
maines, c’est mieux de condenser la preuve, épargner les détails de mani-
pulations simples, et transcrire les formules logiques en parole. La preuve
informelle est alors une recette de construire la preuve formelle.
Théorème 4.2. Le carré d’un entier impair est impair 4 . 4. On veut ∀n : impair(n) → impair(n2 )
avec le prédicat
Preuve directe. (1) Soit n un nombre impair quelconque.
impair(n) ≡ ∃k : n = 2k + 1.
(2) Il existe alors un nombre entier k tel que n = 2k + 1.
(3) On a donc
(4) Or, (2k2 + 2k) est un nombre entier, donc n2 est impair.
Théorème 4.3. Un entier est pair si son carré est pair 6 . 6. On veut ∀n : pair(n2 ) → pair(n) avec le
prédicat
Preuve par contraposition. (1) Supposons que n n’est pas pair,
pair(n) ≡ ∃k : n = 2k.
(2) donc 7 il est impair.
(3) Par Théorème 4.2, n2 est impair, 7. Ici on a besoin d’un lemme : «tout entier n
(4) donc n2 n’est pas pair. est soit pair soit impair» qu’on va démontrer
(5) On vient de démontrer [(1)–(4)] que si n n’est pas pair, alors n2 n’est pas pair non formellement un jour, mais pour le moment
on le prend pour acquis.
plus.
(6) On conclut la contraposée : que si n2 est pair alors n est pair aussi.
√ √
(2) En multipliant les deux inégalités, ( n) · ( n) < ab,
(3) et donc n < ab
(4) et spécifiquement 9 n 6= ab. 9. Formellement, on doit travailler avec
√ √
(5) Par la contraposée, si n = ab, alors a ≤ n ou b ≤ n, comme affirmé par le l’axiome d’antiréflexivité pour «supérieur» :
théorème. ∀ x ¬( x < x ), d’où (par règle de substitution
après instanciation universelle)
n = ab → ¬(n < ab) Par la contraposée,
n < ab → n 6= ab.
Preuve par contradiction
Dans une preuve par contradiction (aussi appelée démonstration à l’ab-
surde) on vise à démontrer une proposition p par réduction à l’absurde. On
assume (¬ p), et on infère une contradiction. Souvent, c’est une contradiction
dans la forme φ ∧ ¬φ avec un énoncé quelconque φ.
Noter la différence subtile par rapport à la contraposée quand on veut
démontrer un énoncé conditionnel H → C. La preuve par contraposition
assume la négation de la conclusion (¬C) et arrive à la négation de l’hypo-
thèse (¬ H ). La preuve par contradiction assume l’hypothèse et la négation
de la conclusion (H ∧ ¬C), et arrive à une contradiction qui est typiquement
( H ∧ ¬ H ). Toutes les deux sont des preuves indirectes, et en fait la preuve
par contraposition peut être facilement transformée dans une preuve par
contradiction. Pour cette dernière, on suppose la négation de l’énoncé condi-
tionnel, et on assume H et ¬C. La preuve avec la contraposée nous donne
(¬C ` ¬ H ), et cela mène à la contradiction ( H ∧ ¬ H ). On doit conclure
(réduction à l’absurde) que ¬( H ∧ ¬C ), ou bien ( H → C ). Avec l’exemple
de démontrer Théorème 4.3 par contradiction : «Supposons que n2 est pair
et n n’est pas pair. [. . . ] donc n2 n’est pas pair et c’est une contradiction.»
√
Théorème 4.5. 2 n’est pas un nombre rationnel.
√
Preuve par contradiction. Supposons que 2 est un nombre rationnel. Alors
√ p
il existe 10 deux entiers positifs p et q avec 2 = q , et p et q ne sont pas 10. Un nombre rationnel s’écrit comme p/q
p
pairs simultanément. (Car on peut simplifier p/q quand tous les deux sont ou q , avec des entiers p et q > 0. L’égalité
p2 du domaine Q est définie par l’égalité entre
pairs.) En élevant au carré, il s’ensuit que q2
= 2. Ainsi, p2 = 2q2 , et cela entiers (Z) à l’aide de deux axiomes :
signifie que p2 est pair, ce qui implique que p doit être pair (Théorème 4.3). a c
= ≡ ( ad = cb)
Puisqu’on peut écrire p = 2k avec un entier k, on a 4k2 = 2q2 , de sorte b d
que 2k2 = q2 . Cela signifie que q2 est pair, et donc q est également pair ∀p ∈ Z :
p
≡p
1
(Théorème 4.3). Or, c’est une contradiction : selon la supposition originale, p | {z }
√
ou q doit être impair. On conclut que 2 ne peut pas être rationnel. établit que les entiers sont des rationnels
Si et seulement si
Supposons que A ↔ B est une tautologie, et on veut la démontrer. Il y a
deux démarches basiques :
? démontrer A → B, et sa réciproque B → A ; ou
? démontrer A → B, et son inverse ¬ A → ¬ B.
Théorème 4.6. Un entier est impair si et seulement si son carré est impair.
L’équivalence entre plus que deux propositions est démontrée de façon ef-
ficace comme un cycle d’implications. Par exemple, si on a trois propositions
équivalentes p ≡ q ≡ r (p ≡ q, q ≡ r, r ≡ p), on cherche la démonstration
des théorèmes p → q, q → r et r → p.
Théorème 4.7. Soit n un entier quelconque. Les propositions suivantes sont équiva-
lentes.
? n est pair
? (n + 1) est impair
? n2 est pair
pair(n) → impair(n + 1) Supposons que n est pair. Il existe alors un entier k tel
que n = 2k. On a alors n + 1 = 2k + 1, donc (n + 1) est impair.
que
( H1 ∨ H2 ) → C ≡ ( H1 → C ) ∧ ( H2 → C ).
Il n’est pas nécessaire que H1 et H2 soient des cas exclusifs, mais en pratique
on travaille souvent avec des cas qui ne se chevauchent pas.
La technique se généralise à une partition dans plus que deux cas : si on
peut écrire H comme une disjonction d’un nombre fini de cas, on peut don-
ner autant de preuves avec la même conclusion et les combiner pour H ` C.
Théorème 4.10. 197 est un nombre premier 13 . 13. Un nombre naturel n ∈ N est un nombre
premier ssi il a exactement deux diviseurs
La preuve exploite Théorème 4.4 pour réduire le nombre de cas dans la positifs. Dans d’autres mots, n > 1 et n ne
possède aucun autre diviseur que 1 et n :
recherche de diviseurs.
prime(n)
Preuve par exhaustion. Supposons que 197 n’est pas un nombre premier, et il
≡ (2 ≤ n )
a des diviseurs entre 2 et 196 (inclusivement). Donc il existe deux nombres
∧ ∀ a∀b : ab = n → ( a = 1 ∨ b = 1)
entiers a, b t.q. 1 < a, b < 197 et ab = 197. Sans perte de généralité 14 ,
√ 14. Ici, on commence une preuve par cas :
supposons que a ≤ b, et donc a ≤ 197 (Théorème 4.4). Or, si a ≤
√ a ≤ b ou b ≤ a. Les deux cas sont sy-
197 < 15 (152 = 225), a doit être une des valeurs 2, 3, 4, 5, 6, 7, 8, 9, 10, métriques. «Sans perte de généralité» veut
11, 12, 13, ou 14. dire qu’on fournit juste une moitié de la
preuve, parce que l’autre cas est démontré
On montre qu’aucun 1 < a < 15 ne divise 197 dans une preuve par ex- identiquement après échange de symboles
haustion. (cas 1) a ne peut pas être pair (2, 4, 6, 8, 10, 12, 14) car 2 ne divise (travail pour le lecteur ou la lectrice).
pas 197. (cas 2) a ne peut pas être 3 ou 9 car 3 ne divise pas 197. (cas 3) Ni 5
ne divise 197 (197 = 5 · 39 + 2), (cas 4) ni 7 ne divise 197 (197 = 7 · 28 + 1),
(cas 5) ni 11 ne divise 197 (197 = 11 · 17 + 10), et (cas 6) ni 13 ne divise 197
(197 = 13 · 15 + 2) sans reste. Il n’y a pas d’autres cas, donc il n’y a au-
cun choix possible pour un diviseur a. Par conséquence, 197 est un nombre
premier.
38
Preuves d’existence
Un grand nombre de théorèmes en informatique affirment qu’il existe un
objet avec des propriétés particulières (ou qu’il existe un groupe d’objets avec
des relations particulières entre eux). On peut donner une preuve d’existence
directement : il suffit de montrer un élément (ou un group d’éléments) qui est
un témoin de l’existence. Dans le cas spécial où le théorème est
¬∀ x : P( x ) ≡ ∃ x : ¬ P( x ) par De Morgan
pas tout le monde est P il y a non-P
Théorème 4.12. Il existe des nombres irrationnels a, b tel que ab est rationnel.
√
On construit une preuve par élimination, en utilisant que r = 2 est
irrationnel (r 6∈ Q)
r
(r 2 = 2) ∧ (0 < r ) → r r ∈ Q ∨ r r ∈ Q
| {z } | {z } | {z }
≡H ≡C1 ≡C2
√ √
Preuve constructive. Soit a = 2, et b = log2 9. a = 2 est irrationnel par
Théorème 4.5. On montre que ab est rationnel et que b est irrationnel.
√ log2 9
1/2 log2 9
ab = 2 = 3| log32
{z }
=2
| {z }
√
= 2
1
= 3 2 ·log3 2·2·log2 3
1
= 3. log3 2 =
log2 3
39
Si b est rationnel, alors b = p/q avec des entiers positifs p et q. Par défi-
nition du logarithme 15 , 2 p = 9q , et c’est impossible parce que 2 p est pair 15. En particulier, si b = log2 9 = q , alors
p
quand p > 0 tandis que 9q est impair. En conséquence, b = log2 9 doit être p = q log2 9 et donc
q
irrationnel. 2 p = 2q log2 9 = 2log2 9 = 9q .
Théorème 4.13. Un nombre de Mersenne 16 est un entier de forme n = 2 p − 1, 16. :nombre de Mersenne
(fr)
où p est un nombre premier. Les nombres de Mersenne ne sont pas tous des nombres
premiers.
Preuve d’unicité
Supposons qu’on doit démontrer non pas seulement qu’il existe une solu-
tion à un problème ∃ x : P( x ), mais aussi que cette solution est unique. Il faut
complémenter la preuve d’existence d’un x avec une preuve d’unicité : que
tout y est soit x = y soit ¬ P(y). On a les démarches possibles 19 : 19. Rappelons les formules équivalentes pour
l’existence d’un x unique satisfaisant le
(i) démontrer que pour un y quelconque, si y 6= x alors ¬ P(y) ; prédicat P( x ) :
(ii) démontrer que pour un y quelconque, si P(y), alors x = y ; ∃!x : P( x ) ≡ ∃ x : P( x ) ∧ ∀y : y 6= x → ¬ P(y))
(iii) démontrer que P(y) avec y 6= x mène à une contradiction. ≡ ∃ x : P( x ) ∧ ∀y : P(y) → y = x
Notons qu’on peut monter une preuve d’unicité sans ou avec construction ≡ ∃ x : P( x ) ∧ ¬ ∃y : P(y) ∧ y 6= x .
2− x = x.
a ∈ A si a est membre de l’ensemble A ;
On écrit
a 6∈ A si ¬( a ∈ A)
∃S : ∀ x : x 6∈ S (5.1)
aucun x n’est membre de S
A = { a} un singleton
S = {1, 2, 3, 4, 5, 6} éléments séparés par virgules, entre accolades
= {6, 5, 4, 3, 2, 1} l’ordre des éléments est sans importance
= {2, 1, 2, 3, 4, 5, 6} répétition est sans importance
42
On remarque que ∃ x : P( x ) est vrai si et seulement si l’ensemble caracté- TABLE 5.1: Ensembles importants
ristique de P n’est pas vide, et ∀ x : P( x ) ssi son ensemble caractéristique est le
∅ = {} ensemble vide
domaine entier :
N = {0, 1, 2, 3, . . . } nombres naturels
N+ = {1, 2, 3, . . . } entiers positifs
∃ x : P( x ) ≡ { x | P( x )} 6= ∅ ∀ x ∈ U : P( x ) ≡ { x | P( x )} = U.
Z = {0, ±1, ±2, . . . } nombres entiers
Q = p/q| p ∈ Z, q ∈ N+ nombres rationnels
R nombres réels
Schéma non-restreint. Dans nos discussions on omet souvent le domaine à la
C = p + q · i p, q ∈ R nombres complexes*
gauche de la barre, suivant un schéma non-restreint : on écrit { x | φ} où φ
est une formule logique quelconque avec variable libre x. Ainsi, √
∗ i= −1
R = x ∈ Z pair( x ) = { x |pair( x )} ∀ x : x ∈ R ↔ pair( x ),
les nombres pairs non-restreint x est membre ssi il est pair
Notation en image
Supposons qu’on s’intéresse aux valeurs possibles d’une fonction f ( x )
quand x prend valeurs dans un ensemble A. L’appartenance d’une valeur y à
cet ensemble dépend de l’existence d’un x avec f ( x ) = y, donc on définit en
compréhension : F = {y|∃ x : f ( x ) = y}. Il arrange alors mieux d’employer
la notation en image : f ( x ) x ∈ A .
43
On peut écrire les nombres pairs en image : R = {2x | x ∈ Z}. Les nombres
quadratiques :
x2 x ∈ Z = y ∈ Z Q(y) avec Q(y) = ∃ x ∈ Z : x2 = y.
Notons que la même valeur y = f ( x ) peut être atteinte avec des arguments x
différents, mais la répétition ne cause pas de problème à cause de l’axiome
d’extension. Ici, x2 = (− x )2 , donc on énumère tout deux fois (sauf 0).
En parcourant les entiers signés avec x = 0, −1, 1, −2, 2, −3, 3, ..., on a
{ x2 } = {0, 1, 1, 4, 4, 9, 9, 16, 16, . . . }.
Définition 5.6. Soit S un ensemble. Si le nombre des éléments distincts 10 est un 10. L’ensemble vide contient n = 0 éléments
nombre naturel n, on dit que S est un ensemble fini, et sa cardinalité est |S| = n . distincts. Il y a n ∈ N+ éléments distincts,
s’il existe une fonction f qui énumère les
(|∅| = 0.) Autrement, S est un ensemble infini avec cardinalité infinie 11 : éléments de S avec domaine
|S| = ∞ . [n] = {1, 2, . . . , n} :
∀i ∈ [ n ] : f (i ) ∈ S
∀ s ∈ S : ∃i ∈ [ n ] : f (i ) = s
∀i ∈ [n] : ∀ j ∈ [n] : ( f (i ) = f ( j)) → (i = j)
Les conditions assurent qu’on compte
proprement :
(i) f (i ) est le i-ème élément ;
(ii) chaque élément est compté une fois ; et
(iii) on compte les éléments distincts une fois
(condition d’unicité).
11. On examinera les cardinalités infinies plus
attentivement.
44
Différence. La différence de deux ensembles A, B, dénotée 14 par B − A , 14. Ou, dans quelques ouvrages, avec le sym-
contient les objets qui sont dans B mais non pas dans A : bole spécifique à la différence d’ensembles :
B \ A.
B − A = x x ∈ B ∧ ( x 6∈ A)
∀ x : x ∈ B − A ↔ ( x ∈ B) ∧ ¬( x ∈ A)
On note que différence n’est pas commutative : A − B 6= B − A en général. TABLE 5.3: Table d’appartenance pour
La différence symétrique de deux ensembles A, B, dénotée par A4 B est différences d’ensembles.
l’ensemble des éléments qui sont exclusivement soit dans A soit dans B :
x∈A x∈B x ∈ B−A x ∈ A4 B
A4 B = ( A − B) ∪ ( B − A) a b b ∧ ¬a a⊕b
0 0 0 0
∀ x : x ∈ A 4 B ↔ ( x ∈ A ) ⊕ ( x ∈ B ). 0 1 1 1
1 0 0 1
1 1 0 0
Complément. Le complément d’un ensemble A, dénoté par A est l’en-
semble des éléments qui ne sont pas dans A,
A = x x 6∈ A ∀ x : x ∈ A ↔ x 6∈ A. (5.5)
B−A A4 B
La notion du complément est par rapport à l’univers U :
A = U − A = x ∈ U ¬( x ∈ A) .
45
A∩∅ = ∅
(domination)
A∪U = U
A∩A = A
(idempotence)
A∪A = A
A∩A = ∅
(complément)
A∪A = U
A∩B = B∩A
(commutativité)
A∪B = B∪A
A ∩ ( B ∩ C ) = ( A ∩ B) ∩ C
(associativité)
A ∪ ( B ∪ C ) = ( A ∪ B) ∪ C
A ∩ ( B ∪ C ) = ( A ∩ B) ∪ ( A ∩ C )
(distributivité)
A ∪ ( B ∩ C ) = ( A ∪ B) ∩ ( A ∪ C )
A ∪ ( A ∩ B) = A
(absorption)
A ∩ ( A ∪ B) = A
A∩B = A∪B
(De Morgan)
A∪B = A∩B
46
5.3 Sous-ensembles
On ajoute la relation d’inclusion au domaine 15 . On dit que A est le sous- 15. :inclusion
(fr)
A⊆B ≡ A = A∩B .
relation entre A, B prédicat avec A, B
A ⊆ B ≡ (∀ x : x ∈ A → x ∈ B). (5.6)
On note que l’ensemble vide est toujours 16 un sous-ensemble : ∅ ⊆ A pour 16. ∀ A : ∅ ⊆ A parce que ∀ x ∈ D : x ∈ A
tout ensemble A. quand D = ∅. Avec l’implication matérielle
sur appartenance : x ∈ ∅ ≡ 0 donc
(∅ ⊆ A) ≡ (0 → ( x ∈ A)).
Super-ensemble. Le symbole miroir dénote la relation de sur-ensemble
(super-ensemble) :
B ⊇ A ≡ A ⊆ B. B inclut A
A ⊂ B ≡ ( A ⊆ B) ∧ ( A 6= B) et B ⊃ B ≡ ( B ⊇ A) ∧ ( B 6= A)
En conséquence, ∅ ⊂ A pour tout ensemble A 6= ∅, mais ∅ 6⊂ ∅. Inclusion parmi les ensembles de Table 5.1 :
∅ ⊂ N+ ⊂ N ⊂ Z ⊂ Q ⊂ R ⊂ C
Propriétés de la relation d’inclusion
Théorème 5.1. Soit A, B et C des ensembles. Alors
et c’est vrai 17 pour tout A (une tautologie). Par (5.6), pour tout A, B, on a 17. La démonstration formelle du séquent
` ∀ x : x ∈ A → x ∈ A est simple :
( A ⊆ B) ∧ ( B ⊆ A) ≡ ∀ x : x ∈ A → x ∈ B ∧ ∀ x : x ∈ B → x ∈ A
A⊆ B B⊆ A 1 x nouvelle variable
2 x∈A supposition
≡ ∀ x : ( x ∈ A → x ∈ B) ∧ ( x ∈ B → x ∈ A)
≡ ∀x : x ∈ A ↔ x ∈ B 3 x∈A copier, 2
4 x∈A→x∈A → I, 2––3
≡A=B ∴ (5.7b)
5 ∀x : x ∈ A → x ∈ A ∀I, 1––4
La démonstration de la transitivité est un exercice.
47
( A ∩ B) ∪ ( A − B) = A et (5.8a)
( A ∩ B) ∩ ( A − B) = ∅. (5.8b)
∃S : ∀ x : (∃ A : x ∈ A ∧ A ∈ F ) ↔ ( x ∈ S ). (5.9)
x est un élément d’un membre de F
On écrit alors
[
S = ∪F ou S= A.
A ∈F
Ensemble puissance
Une famille naturelle qu’on considère est la collection des sous-ensembles
d’un ensemble.
∀ A ∃B : ∀C : C ∈ B ↔ C ⊆ A. (5.10)
On écrit alors B = P( A) ou B = 2 A :
P( A ) = 2 A = S S ⊆ A .
En particulier,
2∅ = { ∅ } un ensemble singleton
2∅
2 = {{∅}, ∅} 2 éléments
{ a,b}
2 = {}, { a}, {b}, { a, b} . 4 éléments
Théorème 5.4 (Paradoxe de Russell). On définit l’ensemble («le barbier») F IGURE 5.1: Bertrand R USSELL (1872–
1970), mathématicien, philosophe, moraliste
et activiste pacifiste, à l’age de 21 ans
B = x x 6∈ x , (5.11) (collation de grades à Trinity College).
B ∈ B ↔ B 6∈ B. (*)
introduit la notion d’un couple qui est une paire de valeurs ordonnées ( x, y).
Le produit cartésien X × Y construit l’ensemble de couples quand x ∈ X
et y ∈ Y. Maintenant, une fonction ou une relation est définie comme un
sous-ensemble de X × Y qu’on obtient par compréhension restreinte :
f = ( x, y) ∈ R × R y = x2 la fonction de carré est un ensemble
A = ( x, y) ∈ H × H x est l’enfant/e de y la relation d’enfant-parent est un ensemble
Les membres de A × B sont des paires ordonnées : si C = A × B, l’égalité entre F IGURE 6.1: Portrait de René D ESCARTES
couples est définie par (1596–1650), nommé Cartesius en Latin, par
Frans Hals [Louvre]. Descartes a inventé le
produit qui porte son nom pour définir R2
∀( a, b) ∈ C : ∀(c, d) ∈ C : ( a, b) = (c, d) → ( a = c) ∧ (b = d) .
et R3 en géométrie 2D et 3D.
Quand A = B, on écrit
A2 = A × A.
Exemple 6.1 (Jeu de cartes). Le produit cartésien entre les quatre enseignes S =
{♠, ♥, ♦, ♣} et les treize valeurs V = {As, 2, 3, 4, 5, 6, 7, 8, 9, 10, Valet, Dame, Roi}
donne le jeu de 52 cartes :
S × V = (♠, As), (♠, 2), . . . , (♣, Roi) .
| {z }
cardinalité 4 · 13 = 52
A × B = | A| · | B|
Définition de couples
L’importance théorique du produit cartésien est qu’il permet de construire
de nouveaux domaines : si on a R avec la fonction de carré f ( x ) = x2 ,
52
Si ( x, y) ∈ R, alors on écrit
Inverse et complément
Définition 6.4. À partir d’une relation R ⊆ X × Y, on construit
(1) la relation inverse (réciproque) de Y à X : R−1 = (y, x ) ∈ Y × X ( x, y) ∈ R ,
et
(2) le complément de R : R = ( x, y) ∈ X × Y ( x, y) 6∈ R .
TABLE 6.3: Inverses et compléments.
La notation R dénote le complément en tant que l’ensemble. Mais si on a
un symbole spécial (p.e., @ ou m) pour la relation, c’est le symbole biffé (6@ et Relation Inverse Complément
= = 6=
6m) qu’on préfère pour dénoter le complément. ≤ ≥ >
⊆ ⊇ 6⊆
parent enfant non-parent
diviseur multiple «ne divise pas»
54
Équivalence et ordre
Quand on veut caractériser ou définir une relation fondamentale dans un domaine, on cherche des propriétés géné-
riques, comme réflexivité ou transitivité. Il y a deux types fondamentaux dans la discussion de structures :
I. relation d’équivalence : réflexive, symétrique, et transitive (p.e., égalité)
dans beaucoup de langages de programmation, il y a une égalité pour «identité selon emplacement en mémoire» et
une autre pour «équivalence selon sémantique» : p.e., == et une méthode equals( x ) d’un objet
en Java, on doit redéfinir la méthode equals dans le code d’une nouvelle classe d’objets(=domaine) : selon la
spécification, il faut satisfaire les trois propriétés d’équivalence
II. relation d’ordre (préordre) : réflexive, anti-symétrique, et transitive et la version stricte qui enlève refléxivité : elle est
antiréflexive, asymétrique, et transitive (p.e., ⊆ et ⊂ entre ensembles )
l’ordre est totale si tous les éléments sont comparables : si tout couple ( x, y) satisfait la trichotomie que soit x < y,
soit x = y, soit x > y
on peut ordonner (ou trier) les éléments d’un ensemble (dans l’ordre croissant) seulement si on a un ordre
Table 6.4 montre des exemples de relations binaires avec la définition des propriétés.
6.3 Fonctions a
1
b
Une fonction associe à chaque valeur d’un ensemble de départ X une 2
c
seule valeur d’un ensemble d’arrivée Y. Une telle association correspond à 3
d
un ensemble de couples ( x, y) ∈ X × Y, avec un couple pour chaque dis- 4
e
tinct x ∈ X.
domaine codomaine
Définition 6.5 (Fonction). La relation binaire f ⊆ X × Y est une fonction (ou
application) si elle satisfait les conditions d’existence et d’unicité ∀ x ∃!y : x f y F IGURE 6.2: La fonction f : {1, 2, 3, 4} →
{ a, b, c, d, e} est définie par les couples
∀ x ∃y : x f y totale à gauche
(1, a), (2, b), (3, c), (4, c)
∀ x ∀y∀z : ( x f y) ∧ ( x f z) → (y = z) déterministe
donc on écrit f (1) = a, f (2) = b et
X est appelé le domaine et Y le co-domaine de f , ce qu’on spécifie par la nota- f (3) = f (4) = c.
tion f : X → Y .
a a
La seule valeur y ∈ Y telle que ( x, y) ∈ f est notée 1 1
b b
f (x) = y notation préfixée pour fonction f 2
c
2
c
3 3
d d
On dit alors que y = f ( x ) est l’image de x sous f . L’ensemble image est 4 4
e e
l’ensemble des images (qui existe par l’axiome de remplacement), un sous-
ensemble du co-domaine : ceci n'est pas ceci n'est pas
une fonction une fonction
(totalité) (déterminisme)
Im( f ) = f ( X ) = f ( x ) x ∈ X = y ∈ Y ∃ x ∈ X : ( x, y) ∈ f
| {z } | {z }
définition en image définition en compréhension
Le produit cartésien de 8 colonnes (C) et 8
rangées (R)
Définir une fonction. Dans un domaine fini X, il suffit de donner l’ensemble
a, b, . . . , h × 1, 2, . . . , 8
des associations pour chaque x ∈ X. Dans un domaine infini comme R | {z } | {z }
=C =R
ou N, on définit les fonctions par formules logiques sur les couples ( x, y) dans
donne les 8 · 8 = 64 cases de l’échiquier
la relation : (Fig. 6.3). Le coloriage des cases est une
fonction à 2 arguments avec domaine R × C
f ( x ) = x2 défini par f = ( x, y) ∈ R2 y = x2 } (les cases) et co-domaine {blanc, noir}
selon laquelle les voisins dans la même
Exemple : g = ( x, y) ∈ R2 : x2 + y2 = 1 ∧ x ≥ 0 ∧ y ≥ 0 définit une rangée ou la même colonne onte des
fonction g : [0, 1] → [0, 1] dans l’intervalle fermée [0, 1] = { x ∈ R | 0 ≤ couleurs opposées, et couleur(a, 1) = noir.
x ∧ x ≤ 1}. 8
7
6
Fonction anonyme. On écrit une fonction anonyme avec le symbole 7→ 5
(flèche avec taquet) : x 7→ x2 dénote la même chose que f ( x ) = x2 , mais 4
sans nommer la fonction par f = x 7→ x2 . 3
2
1
λ-calcul. En logique et informatique théorique, le système formel de lambda- a b c d e f g h
calcul utilise le symbole λ pour construire une fonction à partir d’un terme
F IGURE 6.3: La structure et la sémantique
avec variables libres. Le λ préfixe une variable libre (l’argument de la fonction) de l’échiquier. Le coloriage des cases est une
dans un terme qui calcule la valeur de la fonction, et ainsi λ établit la liaison : fonction.
Opérateurs binaires
TABLE 6.5: Exemples d’opérateurs.
Dans le domaine des nombres naturels, l’addition est une fonction avec ? opérateurs binaires en arithmétique :
multiplication, addition, . . .
domaine N × N et co-domaine N. On utilise l’opérateur + en une notation
? opérateurs binaires en logique boo-
infixée pour dénoter cette relation : x + y = z (au lieu, par exemple, d’une léenne : ∧, ∨, →
notation préfixée +( x, y) = z). ? opérateurs binaires en théorie des
ensembles : ∪, ∩
Définition 6.6. (i) Une fonction f : X → X est appelée opérateur unaire sur ? opérateur unaires : ¬ (négation logique),
X. (ii) Une fonction f : X × X → X est appelée opérateur binaire sur X. On opposé − (comme multiplication
par (−1)), ++ (incrémentation en
utilise l’opérateur dans la notation infixée z = x f y pour dénoter z = f ( x, y). C/Java/C++/Javascript/Python/Perl/. . . )
Notations équivalentes :
L’univers des fonctions
(( x, y), z) ⊆ add ↔ z = add( x, y) ↔ z = x + y
| {z } | {z } | {z }
L’ensemble de toutes les fonctions X → Y s’écrit comme YX : relation fonction opérateur
( f : X → Y) ↔ f ∈ YX
A2 = A × A = {( a, b) | a ∈ A ∧ b ∈ A} produit cartésien
A2 = fonctions 2 → A f (0) = a, f (1) = b
Également, notre notation pour l’ensemble des parties de A par 2 A , est cohé-
rente :
TABLE 6.6: Exponentiation ensembliste avec
A
l’ensemble vide.
2 = B B⊆A axiome de l’ensemble des parties
2 A = fonctions A → 2 f ( x ) = 0 ↔ x 6∈ B, f ( x ) = 1 ↔ x ∈ B
∅∅ = fonctions ∅ → ∅ = {∅}
A∅ = fonctions ∅ → A = {∅}
∅ A = fonctions A → ∅ = ∅
La fonction vide
Comparer avec les identités pour les naturels
La fonction vide est simplement ∅ avec domaine ∅ (car il ne contient au- 00 = 1, n0 = 1, 0n = 0 pour tout 0 < n.
cun couple). La fonction vide est intéressant quand on considère des formules
ensemblistes : ∅∅ et A∅ sont des singletons avec la fonction vide, et il n’existe
aucune fonction avec domaine A 6= ∅ et co-domaine ∅ (Table 6.6).
Composition de fonctions
La composition est l’opération fondamentale dans l’univers des fonctions.
Alors f ◦ g (« f après g») est une fonction f ◦ g : X → Z et ( f ◦ g)( x ) = f g( x ) .
X Y Z
a
α 1 57
b
β 2
c
γ 3
d
δ 4
Preuve de Théorème 6.3. Pour tout x, il existe un unique y = g( x ) avec y ∈ Y et
pour cet y, il existe un unique z ∈ Z avec z = f (y). g f
F IGURE 6.4: Composition de fonctions.
composée f ◦ g comprend les
La fonction
La fonction d’identité existe dans tout domaine A 6= ∅. Elle est déno- associations (α, c), ( β, b), (γ, d), (δ, b) .
tée 5 par ι A ( x ) = x . Parmi les fonctions A → A, la composition est une 5. Il n’y a pas une notation standardisée pour
la fonction d’identité.
opération binaire associative 6 et ι A est son élément d’identité : 6. Associativité : f ◦ ( g ◦ h) = ( f ◦ g) ◦ h.
On peut omettre les parenthèses avec
( f ◦ ι A )( x ) = f (ι A ( x )) = f ( x ) composition multiple :
6.4 Bijections
Définition 6.7. Une fonction f : X → Y est dite 8 8. Termes anglais : identiques en écriture ou à
l’ancienne
(i) surjective si son ensemble image coïncide avec son co-domaine : ? injective ou one-to-one function
? surjective ou onto function
∀y ∈ Y : ∃ x ∈ X : f ( x ) = y
? bijective ou one-to-one correspondence
surjective injective
R E M A R Q U E . Les notions de surjection, injection et bijection dépendent du domaine et du
co-domaine de la fonction. Par exemple, la fonction f ( x ) = x2 n’est pas injective en tant que F IGURE 6.5: Surjection et injection.
f : Z → Z ou f : R → R parce que l’image de x et de (− x ) est le même, et x 6= − x quand f est surjective si pour tout y dans le
x 6= 0. Avec un tel choix de domaine et co-domaine, f n’est surjective non plus, parce que les co-domaine, il y a (au moins) un x avec
nombres négatifs dans le co-domaine ne sont jamais engendrés par f . Dans le domaine des y = f ( x ). La fonction est injective si les
nombres complexes, la fonction f : C → C est une surjection car il y a toujours (1 ou 2) solution images des éléments distincts sont distincts.
à y = x2 . La fonction f : N → N est injective (mais non pas surjective), parce qu’il y a (au plus)
une solution x non-négative à y = x2 . On peut même choisir le co-domaine des nombres carrés
Q = {y | ∃ x ∈ N : y = x2 }, et alors f : Z → Q est une surjection, et f : N → Q est une
bijection.
a
Techniques de preuve 1
b
2
Supposons qu’on a une fonction f : A → B. Les preuves des propriétés c
3
de f remontent à des démonstrations ensemblistes selon les définitions. d
4
? pour démontrer que f est injective, il faut une preuve d’unicité pour
x ∈ A : on montre que f ( x ) = f (u) → ( x = u) pour tout x, u ∈ A ; bijective
F IGURE 6.6: Bijection. La fonction f est
? pour démontrer que f n’est pas injective, il faut un contre-example : on bijective si elle est injective et surjective :
montre f ( x ) = f (u) et x 6= u avec un couple ( x, u) ∈ A2 ; pour tout y dans le co-domaine, il y a
exactement un x dans le domaine avec
? pour démontrer que f est surjective B ⊆ Im( f ), il faut une preuve d’exis- y = f ( x ).
tence pour x ∈ A : pour y ∈ B arbitraire, il existe x ∈ A avec f ( x ) = y
(preuve constructive si possible) ;
? pour démontrer que f n’est pas surjective B 6⊆ Im( f ), il faut un contre- a a
1 1
b b
exemple : un y ∈ B tel que f ( x ) 6= y pour tout x ∈ A.
2 2
c c
3 3
d d
Inverse d’une fonction 4 4
Démonstration. Selon sa définition, f −1 = ( f ( x ), x ) | x ∈ X , et c’est (i) totale à
la gauche ssi f est surjective ( f prend toutes les valeurs y), et (ii) déterministe ssi f est
injective (il y a une seule x avec f ( x ) = y).
Cardinalité par bijection
∀ x ∈ A : ∃!y ∈ B : ( x, y) ∈ F et ∀y ∈ B : ∃!x ∈ A : ( x, y) ∈ F
| {z } | {z }
c’est une fonction l’inverse est aussi une fonction
On note que la définition implique la transitivité d’égalité de cardinaux : si f et g sont des bijections, alors f ◦ g est
une bijection. (La définition satisfait aussi les critères de symétrie et réflexivité, donc l’égalité par cardinalité est une
équivalence entre ensembles.) Ainsi la cardinalité | A| = n peut être établie par une bijection à {0, 1, . . . , n − 1} ou
à n’importe quel autre ensemble image avec cette cardinalité. La définition aide à établir même une cardinalité infinie
de | A| = |N| : un tel ensemble est dénombrable. Voir Table 6.4 pour exemples.
Pour un ensemble de taille finie | A| = n, la bijection f : A → [n] définit
aussi l’énumération 10 des éléments f −1 : [n] → A. Ainsi, on peut établir 10. Il y a n ∈ N+ éléments distincts, s’il existe
l’égalité de cardinaux finis par un argument d’énumération. une fonction a : [n] → A bijective qui
énumère les éléments de A :
Preuve ensembliste.
TABLE 6.7: Preuves de cardinalité par
A ∪ B = ( A ∪ B) − B + ( A ∪ B) ∩ B par Théorème 6.9 bijection.
? Preuve qu’il y a 7 jours de la semaine :
= | A − B| + | B|
= | A| − | A ∩ B| + | B| par Théorème 6.9 (1, lundi), (2, mardi), (3, mercredi), (4, jeudi),
(5, vendredi), (6, samedi), (7, dimanche) .
? Preuve qu’il y a autant d’entiers pairs que
des nombres naturels avec une bijection
Selon la définition on démontre que deux ensembles ne sont pas de même {2x | x ∈ Z} → N :
cardinalité en prouvant qu’il n’existe pas de bijection entre eux. (
p {0 ≤ p }
h( p) =
Théorème 6.11 (Diagonalisation de Cantor). Soit S un ensemble et 2S son −( p + 1) { p < 0}
ensemble puissance. Il n’existe pas de surjection f : S → 2S . ? Preuve qu’il y a autant de nombres naturels
pairs P = {2n | n ∈ N} que des
Preuve par contradiction. Supposons qu’il existe une surjection f : S → 2S , et nombres naturels : la fonction n 7→ 2n
est une bijection N → P. Alors que P
alors pour tout A ⊆ S, il existe un tel x ∈ S que f ( x ) = A. On définit alors est un propre sous-ensemble P ⊂ N, ils
l’ensemble ont la même «taille» | P| = |N|, et c’est
tout à fait possible avec les cardinalités
D = x ∈ S| x 6∈ f ( x )
infinies.
par compréhension. Comme D ∈ 2S et f est une surjection, il existe un tel d
que f (d) = D. Mais d ∈ D ↔ d 6∈ f (d) par la définition de D et c’est une
contradiction.
L’importance de ce théorème est que |S| < 2S pour toute cardinalité,
même infinie. Ainsi, l’ensemble de tous les sous-ensembles de N a une cardi-
nalité infinie 11 plus grande que |N| ! 11. Plus tard on montrera que |2N | = |R| par
une bijection.
7 Séquences et induction
U N E S É Q U E N C E est une énumération d’éléments, donc elle est une fonc-
tion avec un domaine ordonné. On choisit typiquement l’énumération par
des nombres naturels. Une telle fonction a : I → A avec le domaine (les
indices) I = {0, 1, . . . , n − 1} ou I = {1, 2, . . . , n} est une séquence de
longueur n = | I |. Au lieu d’écrire a(i ) avec i ∈ I, on utilise la notation
indexée ai = a(i ) pour les membres.
En généralisant le produit cartésien qui engendre des couples, une sé-
quence finie peut être également considéré comme un tuple de n éléments
quelconques (un n-uple), créé par le produit cartésien de n ensembles. Ce
concept formel est très flexible, et on l’utilise en informatique pour définir
rigoureusement nos structures. Par exemple, une chaîne de n caractères est un
n-uple dans le produit de n copies d’un alphabet. Les tuples sont également au
cœur des bases de données relationnelles : une table avec n colonnes est une
collection de n-uples qui forment ses rangées.
Une séquence infinie correspond à une fonction N → A avec l’indice parcourant tous les nombres naturels. On ren-
contre les séquences numériques N → N et N → R ou les suites infinies dans beaucoup de problèmes informatiques.
Par exemple, le temps tn de résoudre l’instance d’un problème de taille n ∈ N est une séquence d’intérêt fondamentale
en algorithmique. Afin de travailler avec l’infini, on a besoin de le définir, et de donner une technique de preuve asso-
ciée. La fonction fondamentale de successeur s(n) induit l’ensemble infini N comme une suite {0, s(0), s(s(0)), . . .}
et on peut établir l’appartenance n ∈ N par n applications de s à partir de 0. La définition de N comme un ensemble
inductif nous permet d’établir qu’un prédicat P(n) vaut pour tout n ∈ N par un argument inductif. Si on a P(0), et on
a P(n) → P(n + 1) pour tout n, alors on a le droit de déduire la généralisation universelle ∀n : P(n).
7.1 Séquences
Définition 7.1. Une séquence (ou suite) est une fonction f : I → A dont le
domaine (l’ensemble des indices) est un sous-ensemble 1 des nombres naturels 2 I ⊆ 1. Typiquement, les indices sont des entiers
N. On dénote alors les éléments (ou membres) de la séquence dans la notation consécutifs 0, 1, . . . ou 1, 2, . . . .
2. Parfois on travaille avec des indices négatifs
indexée f i = f (i ) avec les indices i ∈ I. Si I est fini, la séquence est finie. aussi, donc plus généralement, I ⊆ Z, mais
Autrement, elle est infinie. La longueur de la séquence est | I |. on n’en aura pas besoin dans ce cours.
On peut écrire la séquence avec les limites en indice et exposant (subscript et superscript) :
{ an }9n=1 = { a1 , a2 , . . . , a9 } ou { ai }i∞=0 = { a0 , a1 , . . . }
une séquence de neuf éléments une suite infinie
Exemple 7.1 (Suite des nombres carrés). La suite des nombres carrés {cn }∞
n=0 se
définit par cn = n2 . On peut définir la même suite sans la nommer :
2 ∞
n 7 → n2 = n = n2 n=0 = n2 n∈N = {0, 1, 4, 9, 16, . . . }.
62
Définition 7.2. La suite s : X → Y avec domaine 3 X ⊆ N et codomaine 3. Plus génériquement, on a la même dé-
Y ⊆ R (ou autre ensemble totalement ordonné) est dite finition si on permet des indices négatifs
X ⊆ Z.
? croissante au sens large, ou non-décroissante si
∀i, j ∈ X : i < j → si ≤ s j ,
∀i, j ∈ X : i < j → si ≥ s j ,
Définition 7.3. Le produit cartésien de n ensembles A1 , A2 , . . . , An avec n ∈ N est l’ensemble des n-uples (ou tuples) :
∏in=1 Ai = A1 × A2 × · · · A n = ( a1 , a2 , . . . , a n ) a1 ∈ A1 ∧ a2 ∈ A2 ∧ · · · ∧ a n ∈ A n .
( a1 , a2 , . . . , an ) = (b1 , b2 , . . . , bn ) → ( a1 = b1 ) ∧ ( a2 = b2 ) ∧ · · · ∧ ( an = bn ) .
| {z }
∀ i : a i = bi
La fonction b : 2{1,...n} → {0, 1}n est bijective. On définit les opérations bit à bit TABLE 7.1: Opérations élémentaires sur bits
dans {0, 1}n :
n n OR 0 1 AND 0 1
a ∨ b = OR( ai , bi ) i=1 a ∧ b = AND( ai , bi ) i=1 0 0 1 0 0 0
n n 1 1 1 1 0 1
a ⊕ b = XOR( ai , bi ) i=1 ¬ a = NOT( ai ) i=1
XOR 0 1 NOT
0 0 1 0 1
par les opérations élémentaires OR, AND, XOR et NOT sur les bits (Table 7.1). Ainsi,
1 1 0 1 0
b( A ∪ B) = b( A) ∨ b( B) b( A ∩ B) = b( A) ∧ b( B) TABLE 7.2: Opérations sur les bits en Java.
b( A4 B) = b( A) ⊕ b( B) b ( A ) = b ( I − A ) = ¬ b ( A ). int a; // 32 bits
int b; // 32 bits
L’ordinateur stock un entier 0 ≤ a < 232 comme la suite a0 , . . . , a31 de 32 bits (ou 4 ...
octets) dans la représentation binaire : int union = a | b; // OR
a = a0 + a1 · 2 + a2 · 22 + a3 · 23 + · · · + a31 · 231 . L’«entier» (de 32 ou 64 bits) est int intersect = a & b; // AND
un type fondamental dans beaucoup de langages de programmation, et vient avec des int diffsym = a ^ b; // XOR
opérations sur les bits. Ainsi, un entier peut encoder un sous-ensemble d’un ensemble int non_a = ~ a; // NOT
de 32 éléments et on peut facilement implanter les opérations ensemblistes. Table 7.2
montre l’exemple en Java.
64
On admet la notion d’infini, au moins dans le cas des nombres naturels, comme
l’idée d’une manque de borne : il y a un successeur à tout nombre naturel n. La
fonction de successeur s : N → N doit satisfaire les propriétés :
Corollaire 7.2. Preuve par induction est une forme d’argument valide avec successeur
s(n) = n + 1.
φ (0) ∀ n ∈ N : φ ( n ) → φ ( n + 1)
(IND)
∀n ∈ N : φ(n)
65
1 = 12 1 + 3 = 22 1 + 3 + 5 = 32 1 + 3 + 5 + 7 = 42 ···
Preuve par induction. Soit pn la somme des n premiers nombres positifs im-
pairs. On démontre(5) que pn = n2 pour tout nombre naturel n ∈ N par (5) On commence la preuve avec un
avertissement au lecteur ou à la lectrice : il y
induction.
aura un cas de base et un étape inductif.
(base) On a p0 = 02 . C’est une question de style si on veut
structurer le texte en indiquant «cas de base»
(induction) Supposons que pn = n2 pour un n quelconque(8) . Ainsi, et «pas inductif» (base step et induction step)
explicitement. En général, il n’est pas
pn+1 = pn + (2n + 1) membre additionnel dans la somme nécessaire, après avoir annoncé qu’une
2 preuve par induction suivra.
= n + (2n + 1) par l’hypothèse d’induction (8) Dans l’étape d’induction, on veut
2T = 2T ∩ 2S + 2T − 2S = T0 + T1 = 2S + 2S = 2 · 2n = 2n +1 .
H.I.
scinder par 2 S par (7.4) S
par 2 = T0 et (4)
Puisque (base) P(0) est vrai, et que (induction) P(n + 1) est vrai lorsque P(n) est vrai,
Équation (7.3) est vrai pour toute cardinalité finie |S| ∈ N.
66
Corollaire 7.5.
(i) La table de vérité pour une formule logique avec n variables propositionelles
contient 2n rangées.
(ii) La table d’appartenance pour une formule ensemblistes avec n ensembles comprend
2n rangées
(iii) Il y a 2n chaînes de bits de longueur n.
(iv) Il y a 2n fonctions A → B pour un domaine de taille n = | A| et codomaine de
taille | B| = 2.
02 ≤ 20 12 ≤ 21 22 ≤ 22 32 > 23 42 ≤ 24 52 ≤ 25 · · ·
( n + 1)2
( n + 1)2 = n2 ·
n2
25 1 2
≤ n2 · x 7→ 1 + est une fonction décroissante
16 x
< n · 2 ≤ 2n · 2 = 2n +1
2
par l’hypothèse d’induction
Induction d’ordre 2
Lors d’une preuve par induction, l’étape de base couvre P(0), et l’étape
d’induction montre P(n) → P(n + 1) avec une preuve conditionnelle qui
commence par l’hypothèse d’induction P(n). La même structure peut être
adaptée à des prédicats dépendants de plus d’un seul antécédent. Dans une
induction d’ordre 2, le cas inductif établit Q(n) ∧ Q(n + 1) → Q(n + 2), Induction dans N avec deux cas de base :
et l’étape de base montre Q(0) ∧ Q(1). La preuve conditionnelle dans l’étape Q (0) ∧ Q (1) ∀ n : Q ( n ) ∧ Q ( n + 1) → Q ( n + 2)
d’induction assume l’hypothèse d’induction Q(n) ∧ Q(n + 1), avec un n ∀n : Q(n)
quelconque, et conclut Q(n + 2).
En posant P(n) ≡ Q(n) ∧ Q(n + 1), Théorème 7.1 s’applique parce qu’on
établit Q(n) ∧ Q(n + 1) → Q(n + 2) ≡ Q(n) ∧ Q(n + 1) → Q(n + 1) ∧ Q(n + 2)
dans l’étape d’induction.
67
Induction généralisée
Dans une preuve par induction «forte» 8 , l’étape d’induction établit 8. Induction généralisée :
∀n : (∀k < n : Q(k)) → Q(n)
Q (0) ∧ Q (1) ∧ · · · Q ( n − 1) → Q ( n ).
∀n : Q(n)
Théorème 7.7 (Induction généralisée). Si ∀n : ∀k < n : Q(k) → Q(n),
alors ∀n : Q(n).
est le cas de base sans antécédent. La preuve conditionnelle dans l’étape d’in-
duction pour un 0 < n quelconque montre que Q(n) découle de l’hypothèse
que Q(k) est vrai pour tout k < n.
Théorème 7.1 s’applique avec P(n) ≡ ∀k ≤ n : Q(k). Dans le cas inductif,
P ( n ) → P ( n + 1) ≡ ∀ k ≤ n : Q ( k ) → Q ( n + 1).
Théorème 7.8 (Division euclidienne). Pour tout a et m > 0 des entiers naturels,
il n’y a qu’un seul couple d’entiers naturels (q, r ) avec r < m tel que
a = q · m + r. (7.5)
Preuve par induction. Soit m > 0 un entier positif quelconque. On montre d’abord
qu’il existe un couple satisfaisant (7.5) par induction en a. (base) Si a < m,
alors q = 0, r = a est une solution car a = 0 · m + a. (induction) Soit b ≥ m, et
supposons que (7.5) est vrai pour tout a < b. (1) Soit a = b − m. Comme m > 0, et
b ≥ m, 0 ≤ a < b. (2) Par l’hypothèse d’induction, il existe (q0 , r 0 ) tel que
a = q0 · m + r 0 . (3) Ainsi, b = a + m = (q0 + 1) · m + r 0 . En conséquence, il existe
un couple (q, r ) avec 0 ≤ r < m pour tout a ∈ N satisfaisant (7.5).
Maintenant, on montre que la solution est unique. Supposons que a = (q · m) + r et
a = ( p · m) + s, avec r, s < m. D’abord, on montre que nécessairement q = p, par
contradiction. Supposons, sans perte de généralité, que q < p. On a alors une
contradiction :
0 = a − a = p · m + s − q · m + r = ( p − q) ·m + (s − r )
| {z } | {z }
1≤ 0− m <
> 1 · m + (0 − m ) = 0
Puisque p = q, on a q · m + s = q · m + r, donc s = r.
68
On note que min est une fonction bien définie car le minimum est unique
par anti-symétrie : si m et m0 sont deux plus petits éléments, alors m ≤ m0 (car
m est minimum) et m0 ≤ m (car m0 est minimum). Puisque ≤ est un ordre,
m0 ≤ m et m ≤ m0 impliquent m = m0 . On définit le maximum (ou le plus
grand élément) unique dans A 6= ∅ avec la même logique :
m = min A ↔ m ∈ A ∧ ∀n ∈ A : m ≤ n
m = max A ↔ m ∈ A ∧ ∀k ∈ A : k ≤ m
∀ A : ( A ⊆ E) ∧ ( A 6= ∅) → ∃m ∈ A : (∀ x ∈ A : m ≤ x ).
A est une partie non-vide m est le plus petit
Théorème 7.9 (Bon ordre parmi les nombres naturels). Si E ⊆ N n’est pas
vide, alors E contient un minimum min E.
Preuve esquissée. On peut démontrer le théorème par induction : si E possède un
élément inférieur ou égal à n, alors E contient un minimum. On définit le prédicat
correspondant :
P(0) est immédiate car ∀n : 0 ≤ n. L’induction P(n) → P(n + 1) est par cas : si E
contient un k ≤ n, on se sert de l’hypothèse d’induction, ou si E ne contient pas un
tel k, alors (n + 1) est le minimum.
Le bon ordre sert comme un bouton d’avance rapide dans la preuve sui-
vante pour Théorème 7.8.
Preuve pour Théorème 7.8 avec bon ordre. Soit m > 0 un entier positif quelconque.
On montre que pour tout a et m > 0 des entiers naturels, il n’y a qu’un seul couple
d’entiers naturels (q, r ) avec r < m tel que a = q · m + r. (1) Soit
R = a − q · m q ∈ N ∧ qm ≤ a = { a, a − m, a − 2m, . . . } (2) L’ensemble R
n’est pas vide parce que a − 0 · m = a ∈ R. Soit r = min R et q la valeur avec laquelle
a − qm = r. (3) Maintenant r < m, car si r ≥ m, alors r − m ∈ R est un élément plus
petit. (4) On a alors un couple d’entiers naturels (q, r ) avec lequel a = qm + r et
0 ≤ r < m. L’unicité de la solution est démontrée comme précédemment :
(qm + r ) − (q0 m0 + r 0 ) = 0 n’est pas possible si (q, r ) 6= (q0 , r 0 ) avec 0 ≤ r 0 < m.
69
b x c = max{n ∈ Z | n ≤ x } d x e = min{n ∈ Z | x ≤ n}
La partie fractionnaire est dénotée 10 par { x } = x − b x c 10. Attention : c’est la même notation que
pour ensemble singleton de x.
Exemple 7.3.
1065 = 1065 1065 = 0 1065 = 1065
10.65 = 10 10.65 = 0.65 10.65 = 11
−10.65 = −11 −10.65 = 0.35 −10.65 = −10 plancher
x 7→ b− x c 6= x 7→ −b x c mais b− x c = −d x e
fractionnaire
F IGURE 7.1: Fonctions de plancher (R →
Les fonctions x 7→ b x c et x 7→ d x e sont surjectives mais non pas injectives. Z), plafond (R → Z) et partie fractionnaire
(R → { x ∈ R | 0 ≤ x < 1})
On détermine alors la valeur par les inégalités b x c ≤ x < b x c + 1 .
En informatique, on se sert du plancher (et du plafond) pour exprimer
n’importe quelle notion d’«arrondi» : pour tout entier naturel n ∈ N et
nombre réel u ≥ 1
a = q · m + r. (*)
j k n o
a a
Spécifiquement, q = m et r = a mod m = m · m (partie fractionnaire).
70
Système de numération
Exemple d’un entier en décimal (m = 10) :
On encode les entiers positifs par des chaînes non-vides avec un alphabet
1065 = 1 · 103 + 0 · 102 + 6 · 101 + 5 · 100
A = {0, 1, . . . , m − 1} : c’est le système de numération à la base m > 1.
La suite unique {d0 , d1 , . . . , dt } avec dt 6= 0 représente n = d0 + d1 m + n en binaire dlg(n + 1)e blg(n)c
d2 m2 + · · · dt mt . Dans la représentation binaire (m = 2), les bits { 0 , 1 } 0 λ 0
encodent dk ∈ {0, 1}, et n = d0 + d1 · 2 + d2 · 22 + · · · dt · 2t avec dt = 1, 1 1 1 0
2 1 0 2 1
ou n = 0 avec la suite vide. La chaîne de bits correspondante dt dt−1 · · · d0
3 1 1 2 1
commence avec le bit de poids fort dt ( 1 si 0 < n) et finit avec le bit de 4 1 0 0 3 2
poids faible d0 ( 0 si pair, 1 si impair). La longueur de la représentation 5 1 0 1 3 2
binaire est le nombre de bits (t + 1). 6 1 1 0 3 2
7 1 1 1 3 2
Théorème 7.11 (Longueur de l’encodage binaire des naturels). Le nombre 8 1 0 0 0 4 3
naturel n ∈ N s’écrit sur lg(n + 1) bits dans la représentation binaire. 9 1 0 0 1 4 3
10 1 0 1 0 4 3
...
Démonstration. Soit β : N → N le nombre de bits dans la représentation binaire. On
TABLE 7.3: Représentation binaire des
a β(0) = 0, et pour tout t ≥ 0, β(n) = t + 1 si et seulement si 2t ≤ n < 2t+1 . On a nombres naturels. λ dénote la chaîne vide.
alors 2t < n + 1 ≤ 2t+1 (car n est entier), et donc t < lg(n + 1) ≤ t + 1 ou
lg(n + 1) = (t + 1). En conclusion, β(n) = lg(n + 1) quand n = 0 et quand
1 ≤ n.
On remarque qu’on peut écrire également que β(n) = 1 + blg nc pour
tout n > 0, mais la formule du théorème marche aussi avec n = 0.
8 Sommation et définitions récursives
L A S O M M E ∑in=1 ai sur n ∈ N éléments consécutifs dans une suite est
l’extension de l’addition dans un couple (n = 2) à l’addition dans un tuple.
On définit la somme comme une séquence indexée (n) dans l’ensemble in-
ductif N. L’induction correspond à une définition récursive de la somme : si
n = 0, alors la somme est 0, sinon c’est l’addition d’un élément à la somme
de (n − 1) éléments.
En général, une relation de récurrence définit chaque terme d’une suite à partir
des membres précédents :
( a 0 , a 1 . . . , a n −1 ) 7 → a n .
conques m et n) :
n n n
∑ a i = a m + a m +1 + · · · + a n indice de sommation i arbitraire : ∑ aj = ∑ ai
i =m j=m i =m
En particulier :
n m m +1
∑ ai = 0 si m > n; ∑ ai = am ; ∑ ai = a m + a m +1 .
i=m i =m i =m
vide si n < m 1 membre 2 membres
∑i ∈ I ai ∑ i2 = 1 + 4 + 9 = 14 ensemble d’indices
i ∈{1,2,3}
∑ P (i ) ai ∑ i2 = 1 + 4 + 9 = 14 prédicat
1≤ i <4
8.2 Séries
La suite des sommes partielles {sn } = {∑in=0 ai } définit la notion de la
série 4 comme le couple des suites { an } et {sn } avec la sommation infinie 4. :série
(fr)
∞
∑ ai = nlim
→∞
sn .
i =0
ou lim = −∞ ou ni l’un ni l’autre — v. Table 8.1). Par Théorème 8.1, la Donc, limn→∞ ∑i∞=0 (−1)i n’existe pas.
notation de somme infinie suffit à définir la série : p.e. dans le cas de la série
∞
∑i∞=1 n12 (qui est convergente), la suite des termes est n12 n=1 , et la suite des
n 1 ∞
sommes partielles est ∑k=1 k2 n=1 .
Il est nécessaire mais non pas suffisante pour la convergence de la série que
les termes convergent vers 0. TABLE 8.2: Preuve de Théoreme 8.2
n
0
n Hn
0 0
1 1
2 3/2 = 1.5
Théorème 8.3. La série harmonique diverge : ∑i∞=1 1/i = ∞.
3 11/6 =≈ 1.8
4 25/12 ≈ 2.1
Démonstration. La suite { Hn } est strictement croissante : Hn < Hn+1 pour tout n
1 5 137/60 ≈ 2.3
(par (8.1b), Hn+1 = Hn + n+ 1 > Hn car ( n + 1) > 0). On démontre d’abord que 10 2.9
pour tout k ∈ N, H2k ≥ 1 + k/2 par induction. 100 5.2
(base) Soit k = 0. On a H20 = H1 = 1 ≥ 1 + 0/2. 1 000 7.5
10 000 9.8
(induction) Supposons que H2k ≥ 1 + k/2 pour un k quelconque. Soit n = 2k , et 100 000 12.1
alors 2k+1 = 2n. On décompose la somme : 1 000 000 14.4
2n n 2n 2n
1 1 1 1 n
H2n = ∑ i
=∑ + ∑
i i
≥ Hn + ∑
2n
= Hn +
2n
car 1/i ≥ 1/(2n) pour tout i ≤ 2n
i =1 i =1 i = n +1 i = n +1 |{z}
| {z } | {z } | {z } =1/2
2n termes = Hn n termes
k 1 k+1 k
≥ 1+ + = 1+ . par l’hypothèse d’induction Hn ≥ 1 +
2 2 2 2
k
H2k ≥ 1 + . (*)
2
La borne (*) implique que la suite n’admet pas de borne finie L :
La définition récursive invite des preuves par induction. Les preuves suivantes
utilisent la récurrence (8.2) avec le premier terme et (8.3) avec le dernier
terme.
n
Théorème 8.5 (Somme unaire). un = ∑1=n pour tout n ∈ N.
i =1
Preuve par induction en n. (base) u0 = 0 par définition de Â. (induction) Supposons que um = m pour un m 0. Par la définition
de somme, um+1 = 1 + Âim=+21 1. Avec un changement de variable j = i 1, on a um+1 = 1 + Âm
j=1 1 = 1 + um = 1 + m.
Théorème 8.6
(conclusion) un(Nombres
= n vaut pour tout n 2 N. Pour tout n ∈ N,
triangulaires). ⌅
Si la relation est une suite de fonctions d-aires gn : Ad → A, la récurrence est d’ordre d. Les conditions initiales
définissent les éléments initiaux sans dépendance. La récurrence avec les conditions initiales engendrent une fonction bien
définie (Théorème 8.4). La solution de la récurrence est une formule explicite pour la même fonction. Par exemple, la
suite des nombres triangulaires, définie par t0 = 0 et tn = tn−1 + n admet la solution explicite tn = n(n + 1)/2. Afin
de démontrer qu’une formule particulière est la solution de la récurrence (Théorème 8.4), on montre que la formule
satisfait les conditions initiales, ainsi que la relation de récurrence.
Les définitions récursives de la somme et du produit donnent immédiatement la solution à des relations de récur-
rence d’ordre 1 quand an dépend de an−1 :
n
a n = a n −1 + f ( n ) ↔ a n = a0 + ∑ f ( i ) (8.5a)
i =1
n
g n = g n −1 · h ( n ) ↔ g n = g0 · ∏ h ( i ) (8.5b)
i =1
78
Fibonacci, mais la solution pour factorielles (récurrence d’ordre 1) garde le avec la suite géométrique de (8.7), on a
produit ∏. n
g n = g0 · ∏ q = a · q n .
i =1
Suite arithmétique
Définition 8.3. Une suite { an } est une progression arithmétique si la
différence ( an+1 − an ) entre les membres consécutifs est constante.
∞ n qn ∑in=0 qi
1
∑ qk = la série géométrique converge ssi |q| < 1 0 1 1
k =0
1−q 1 −1/2 0.5
2 1/4 0.75
3 −1/8 0.625
4 1/16 0.6875
5 −1/32 0.65625
10 10−3 0.66602
15 −3 · 10−5 0.66665
20 10−6 0.66666
...
79
(q − 1) Gn = qn+1 − 1,
√ n √ n n Fn
1+ 5
2 − 1−2 5 0 0
Fn = √ formule de Binet (8.8) 1 1
5 2 1
3 2
Preuve de la formule de Binet. La relation de récurrence est satisfaite par toute fonc- 4 3
tion f (n) = α(q1 )n + β(q2 )n avec α, β ∈ R si q1 , q2 sont les racines de q2 = q + 1 : 5 5
6 8
α(q1 )n + β(q2 )n = α (q1 )n−1 + q1n−2 + β (q2 )n−1 + (q1 )n−2 7 13
8 21
√
9 34
avec q1,2 = 1±2 5 . Les conditions initiales f (0) = 0 et f (1) = 1 sont satisfaites quand
10 45
α = − β = √1 . En conclusion, Fn = f (n) pour tout 0 ≤ n. 15 610
5
20 6765
25 75025
Factorielles ...
La factorielle n! est le produit des n premiers entiers positifs. TABLE 8.11: Factorielles.
1 si n = 0 n n!
n! = 0 1
n · (n − 1)! si n > 0 1 1
2 2
Ainsi, 3 6
n 4 24
n! = ∏ k = 1| · 2 · 3 · 4 · ·{z· · (n − 1) · n} 5 120
k =1 6 720
n facteurs 7 5040
On note que pour la somme des logarithmes, 8 40320
9 362880
n n 10 3628800
∑ lg n = lg ∏ k = lg(n!). 15 1307674368000
i =1 k =1 20 2432902008176640000
25 15511210043330985984000000
...
9 Structures récursives
Définition 9.1 (John von Neumann). On définit le successeur 1 d’un en- 1. Ernst Zermelo, en proposant l’axiome de
semble A par l’infini, a défini la fonction de successeur
comme s( A) = { A}. La définition de von
Neumann a beaucoup d’avantages : entre
s ( A ) = A ∪ { A }. (9.1) autres, le fait que l’entier n est representé par
un ensemble de n éléments.
La fonction de successeur de (9.1) est une injection et elle est définie pour
tout ensemble. On définit l’ensemble des ordinaux finis N avec la propriété
Définition 9.2 (Les ordinaux finis). Un ordinal fini est (i) soit l’ensemble vide
∅ ; (ii) soit x ∪ { x } où x est un ordinal.
L’ensemble récursif des ordinaux finis existe par l’Axiome d’infini et il sert
comme un modèle pour les nombres naturels. En particulier, on construit une
82
0=∅
1 = s (0) = {0} = { ∅ },
2 = s(1) = {0, 1} = ∅, {∅} ,
n o
3 = s(2) = {0, 1, 2} = ∅, {∅}, ∅, {∅}
n o
4 = s(3) = {0, 1, 2, 3} = ∅, {∅}, ∅, {∅} , ∅, {∅}, ∅, {∅}
etc.
n≤m↔n⊆m
n < m ↔ n ∈ m.
Chaînes et concaténation
On définit l’ensemble des chaînes finies A∗ = ∪∞ `
`=0 A par récurrence avec
l’opération fondamentale du domaine, la concaténation · (souvent omise dans
les expressions).
w ∈ A∗ ↔ (w = λ) ∨ (∃ a ∈ A : ∃u ∈ A∗ : w = au) .
| {z } | {z }
cas de base cas récursif
83
Listes et arbres
Les principes fondamentaux d’organisation de données, notamment les
arrangements séquentiel et hiérarchique, correspondent à des structures qu’on
peut définir récursivement. Les listes (Déf. 9.4) et les arbres (Déf. 9.5) sont des
structures auto-similaires. Une liste non-vide est la combinaison de sa tête et la
sous-liste après. Un arbre non-vide est une collection de sous-arbres joints à
une racine commune. liste vide liste non-vide
c’est une liste
Définition 9.4. Une liste est (i) soit la liste vide ; (ii) soit un couple ( x, L) avec tête
une liste L.
? le degré d peut varier chez les nœuds ; d > 1 est en général assumé
? degré constant : arbre d-aire (arbre binaire : d = 2 ; liste : d = 1) arbre vide
? en informatique, on travaille typiquement avec des arbres ordonnés : il y a racine
un ordre parmi les enfants (p.e., enfant gauche et droit), mais certaines ap-
plications demandent des enfants non-ordonnés (p.e. phylogénie d’espèces)
On définit le syntaxe pour des expressions bien formées comme un sous- c'est un arbre
(φ → ψ) ∈ F (φ ∧ ψ) ∈ F (φ ∨ ψ) ∈ F
avec φ, ψ ∈ F.
84
Théorème 9.1 établit que la longueur des chaînes est additive par concaté-
nation.
Preuve par induction structurale. On démontre que |uv| = |u| + |v| par induc-
tion u. (base) Si u = λ, alors |u| = 0, et, par la définition de la concaténa-
tion, uv = λv = v. Donc |λv| = |v| = 0 + |v| = |u| + |v|. (induction)
Soit u = aw avec a ∈ A et w ∈ A∗ , et supposons que pour tout v ∈ A∗ , on
a |wv| = |w| + |v|.
Preuve de Théorème 9.1 par induction sur |u|. On démontre que |uv| = |u| +
|v| par induction sur |u| ∈ N. (base) Si |u| = 0, alors u = λ, et, par
définition de la concaténation : λv = v. Donc |λv| = 0 + |v| = |v|.
85
(induction) Supposons que l’égalité (9.4) du théorème est valide pour tous
mots de longueur ` pour un ` ∈ N, et soit |u| = ` + 1. Alors u = aw avec
a ∈ A et w ∈ A∗ .
∃α∃ β : αβ 6= βα,
On démontre les propriétés d’une opération par induction. Théorème 9.2 éta-
blit que λ est l’élément neutre (comme le 1 pour multiplication des entiers).
Théorème 9.2. La chaîne vide est l’élément neutre de concaténation : pour tout α ∈
A∗ ,
λα = αλ = α. (9.5)
αλ = ( aβ)λ
= a( βλ) cas récursif de concaténation
= aβ = α par hypothèse d’induction
Théorème 9.3. Un arbre binaire avec n nœuds internes contient m = n + 1 nœuds 1 arbre avec n = 1, m = 2
externes.
Preuve par induction structurale. (base) Un arbre vide comprend m = 1 nœud
externe et n = 0 nœud interne. (induction) Soit T = ( x, T1 , T2 ) un arbre 2 arbres avec n = 2, m = 3
binaire non-vide. avec m nœuds externes et n nœuds internes. Soit m1 , n1 et
m2 , n2 le nombre des nœuds externes et internes dans les sous-arbres T1 , T2 , et
supposons que m1 = n1 + 1 et m2 = n2 + 1. L’arbre T contient 1 nœud
interne (sa racine), et les nœuds des sous-arbres, donc n = 1 + n1 + n2 et
arbitraire avec 0 < n nœuds internes, et supposons que le théorème est F IGURE 9.3: Arbres binaires avec n ≤ 3
correct pour tout arbre binaire avec (n − 1) nœuds internes au plus. Soit nœuds internes et m ≤ 4 nœuds externes
m1 , n1 et m2 , n2 le nombre des nœuds externes et internes dans les sous-arbres
T1 , T2 . On a et donc n1 < n, n2 < n. Par l’hypothèse d’induction avec
les sous-arbres : m1 = n1 + 1 et m2 = n2 + 1. Ainsi m = m1 + m2 et
m = n + 1.
was forgotten. A promise of Zariski in 1924, to reestablish Peano’s priority
was apparently not kept (see [5, p. 321] for details).
4. Arithmetic
Peano proposed six axioms to define natural numbers. 87We list them as
follows: the primitive notions N0 , 0 and an operation fulfill the following
axioms:
P0. N0 is a set,
P1. 0 2 N0 ,
9.3 Construction des entiers P2. (n) 2 N0 for every n 2 N0 ,
P3. if S is a set, 0 2 S and (S) ⇢ S, then N0 ⇢ S,
P4. is injective,
C’était au début de la XXe siècle que Giuseppe P EANO a établi une axio-P5. (n) 6= 0 for every n 2 N0 .
matisation rigoureuse des entiers naturels par induction. Notamment, cinq
[. . .]
axiomes fondamentaux sur le successeur et l’induction mathématique suffisent
pour définir l’arithmétique avec cinq axiomes additionnels. L’arithmétique
s’étend aux entiers négatifs qu’on obtient en ajoutant les inverses additifs. L’en-
semble des ordinaux finis (Déf. 9.2) avec le successeur s( x ) = x ∪ { x } est une
structure qui satisfait les axiomes, et ainsi elle est un modèle pour les nombres
naturels.
a + b = b + a. (9.6)
Lemme 9.5.
∀a : a + 0 = 0 + a (9.7)
Lemme 9.6.
∀ a ∈ N : ∀ b ∈ N : s ( a ) + b = a + s ( b ). (9.8)
Z = N ∪ {− a| a ∈ N}
| {z }
0 et les entiers négatifs
où − a est la notation usuelle de l’inverse additif (l’opposé) de a ∈ Z avec les TABLE 9.1: Preuve de a = −(− a) à partir
propriétés : des axiomes.
a + (− a) = (− a) + a = 0
(− a) + a = 0 inverse gauche de a
Ainsi, on définit la soustraction par a − b = a + (−b) , pour laquelle (− a) + −(− a)) = 0 inverse droit de − a
l’ensemble Z est fermé. On peut démontrer d’autres propriétés de l’inverse et
a = −(− a) régularité
de la soustraction à partir des axiomes : v. Table 9.1 pour un exemple.
( a ≤ a) réflexivité
( a ≤ b ∧ b ≤ a) → ( a = b) anti-symétrie
( a ≤ b ∧ b ≤ c) → ( a ≤ c) transitivité
( a ≤ b) ∨ (b ≤ a) totalité
( a ≤ b) → ( a + c ≤ b + c) stabilité (0 ≤ c ) ∧ ( a ≤ b ) → ( a · c ≤ b · c )
( a + c ≤ b + c) → ( a ≤ b) (0 < c ) ∧ ( a · c ≤ b · c ) → ( a ≤ b )
( a ≤ b) ∧ (c ≤ d) → ( a + c ≤ b + d)
AEC).
11.1 Divisibilité
Définition 11.1. On définit la relation «divise sans reste» par l’opérateur | (barre
verticale) entre entiers (k, n) ∈ Z2 , dénotée
k | n ↔ (∃q ∈ Z : n = k · q)
Pour tout entier positif 2 0 < k, 2. Divisibilité est définie pour des entiers
signés, mais le signe ne change rien : k divise
(k | n) ↔ (n mod k = 0) n si et seulement si |k | divise |n|.
k | n ↔ k | (−n) et
par division euclidienne. k | n ↔ (−k ) | n
Exemple 11.1.
L’ensemble des multiples d’un k ∈ N est l’ensemble des entiers auxquels il est
diviseur :
m ∈ N (3|m) = n ∈ N n mod 3 = 0 = 3k k ∈ N = {0, 3, 6, . . . }
| {z } | {z } | {z } | {z }
par divisibilité par division euclidienne par image multiples de 3
Théorème 11.2. Divisibilité est une relation avec des propriétés suivantes :
(i) Pour tout a ∈ Z,
a | b ∧ a | c → a | (b + c) (11.1c)
a | b ∧ a | c → a | (b − c) (11.1d)
a | b → a | (bc) (11.1e)
a | b∧b | c → a | c transitivité (11.1f)
Corollaire 11.3. La relation de divisibilité | est un ordre partiel parmi les entiers
naturels : ( P, |) est un poset pour tout ensemble P ⊆ N.
Démonstration. Par Théorème 11.2, | est une relation binaire qui est réflexive,
transitive et antisymétrique 3 dans N. Donc c’est un préordre dans N et dans 3. Par contre, on n’a pas anti-symétrie dans Z
tout sous-ensemble de N. (En particulier, les diviseurs positifs d’un n > 0 ont car (− x ) | x. P.e., 2 | (−2) et (−2) | 2
mais 2 6= −2.
un ordre imposé par divisibilité, voir l’exemple de n = 60 dans Figure 11.1.)
95
11.2 Congruences
Définition 11.2. On définit la relation de congruence dans Z, dénotée par
≡ (mod n) ( «congrus modulo n») pour un n ∈ N arbitraire :
a≡b (mod n) ↔ n | ( a − b)
∀ x : ( x ≡ x ), ∀ x ∀y : ( x ≡ y) → (y ≡ x ), et ∀ x ∀y∀ x : ( x ≡ y) ∧ (y ≡ z) → ( x ≡ z).
réflexive symétrique transitive
∀ x ∀y : ( x ≡ y) ↔ ∃C ∈ X : ( x ∈ C ) ∧ (y ∈ C ) .
| {z }
appartiennent au même ensemble dans X
∀ x ∀ y : ( x ≡ y ) ↔ f ( x ) = f ( y ).
Arithmétique modulaire
Pour calculer le reste d’une somme ou d’un produit, il suffit de manipuler
les restes des membres :
Théorème 11.7. Soit n > 0 un entier positif. Pour tout a, b ∈ Z, Si on calcule modn, on a le droit de
remplacer toute valeur x par ( x mod n)
( a + b) mod n = ( a mod n) + (b mod n) mod n à n’importe quelle étape de manipulation
d’une formule.
( a · b) mod n = ( a mod n) · (b mod n) mod n TABLE 11.1: Preuve de Théorème 11.7
On remarque que ak 6= ( a mod n)k mod n en général. Pour exponentia- Démonstration. Par division euclidienne,
a = pn + r et b = qn + s avec p = b a/nc,
tion, on utilise plutôt la définition par récurrence : pour tout a ∈ Z, k ∈ N,
q = bb/nc, r = a mod n et q = b mod n.
1 (i) On a ( a + b) = (( p + q)n + (r + s)),
si k = 0 donc n | (( a + b) − (r + s)). On a
ak = donc ( a + b) ≡ (r + s) (mod n), ou
a · ( ak−1 ) si k > 0
( a + b) mod n = (r + s) mod n. (ii) On
a ab = ( pqn + ps + qr )n + rs, d’où
donc, pour tout n > 0, n | ( ab − rs), donc ab ≡ rs (mod n) et
( ab) mod n = (rs) mod n .
1 si k = 0
ak mod n =
( a mod n) · ( ak−1 mod n) mod n si k > 0
Définition 11.3. Soit n > 0 arbitraire. L’ensemble 4 Zn est défini par 4. La notation standard est Z/nZ, mais Zn
suffit pour nos buts.
Zn = [ k ] k ∈ Z = [0 ], [1 ], . . . , [ n − 1 ] ,
| {z }
partition en n ensembles
9 0 1 2 3 4 5 6 7 8 r −1 00 = 1 01 = 0 10 ≡ 1 11 ≡ 1
0 0 0 0 0 0 0 0 0 0
20 ≡ 1 21 ≡ 2 22 ≡ 4 23 ≡ 8 24 ≡ 7 25 ≡ 5 26 ≡ 1
1 0 1 2 3 4 5 6 7 8 1
2 0 2 4 6 8 1 3 5 7 5 30 ≡ 1 31 ≡ 3 32 ≡ 0
3 0 3 6 0 3 6 0 3 6 40 ≡ 1 41 ≡ 4 42 ≡ 7 43 ≡ 1
4 0 4 8 3 7 2 6 1 5 7 50 ≡ 1 51 ≡ 5 52 ≡ 7 53 ≡ 8 54 ≡ 4 55 ≡ 2 56 ≡ 1
5 0 5 1 6 2 7 3 8 4 1
60 ≡ 1 61 ≡ 6 62 ≡ 0
6 0 6 3 0 6 3 0 6 3
7 0 7 5 3 1 8 6 4 2 4 70 ≡ 1 71 ≡ 7 72 ≡ 4 73 ≡ 1
8 0 8 7 6 5 4 3 2 1 8 80 ≡ 1 81 ≡ 8 82 ≡ 1
TABLE 11.3: Multiplication et exponentia-
tion modulo 9.
Théorème 11.8. Addition modulaire ⊕n est commutative et associative, avec
élément neutre 0. Multiplication modulaire n est commutative et associative, avec
élément neutre 1 (si n > 1). ⊕n est distributive sur n .
Exemple 11.2 (Arithmétique binaire). Avec n = 2, on obtient l’arithmétique binaire (mod 2), avec résidus Z2 = {0, 1}. Les
tableaux d’opérations :
⊕2 0 1 2 0 1 2 0 1
0 0 1 0 0 1 0 0 0 pair + impair = impair, pair + pair = impair + impair = pair
1 1 0 1 1 0 1 0 1 impair · impair = impair, pair · pair = pair · impair = pair
On remarque que la structure est isomorphe à des opérations logiques a ⊕2 b correspondant à a0 ⊕ b0 (ou exclusif) et a 2 b corres-
pondant à a0 ∧ b0 (conjonction) avec 00 ≡ 0 (faux) et 10 ≡ 1 (vrai).
3 − 5 = −2 3 256 5 = −2
127 + 127 = 254 ≡ −2 (mod 256) 127 ⊕256 127 = −2
−(−128) = 128 ≡ −128 (mod 256) −1 256 −128 = −128
Le fait qu’il n’y a pas de plus grand nombre premier a été démontré par n πn
1 2
Euclide en une preuve fameuse. 2 3
3 5
Théorème 11.9 (Euclide, Éléments XI, Proposition 20). L’ensemble des 4 7
nombres premiers est infini. 5 11
6 13
Lemme 11.10 (Euclide, Éléments VII, Proposition 31). Tout n > 1 possède un 7 17
8 19
diviseur qui est un nombre premier. 9 23
10 29
Preuve par induction généralisée. (base) À n = 2, le lemme est vrai car 2 | 2 avec le 11 31
nombre premier 2. (induction) Soit 2 ≤ t un entier arbitraire, et supposons que le 12 37
lemme est vrai pour tout 1 < n ≤ t. On montre que (t + 1) doit avoir p | (t + 1) 13 41
14 43
avec un nombre premier p. Si (t + 1) est un nombre premier, le lemme vaut pour 15 47
n = t + 1 avec p = t + 1. Si (t + 1) est un nombre composé, alors il a un diviseur 16 53
1 < d ≤ t. Si d est un nombre premier, il p = d est témoin pour le lemme. Si d n’est 17 59
pas un nombre premier, alors il a un diviseur p qui est un nombre premier, par 18 61
l’hypothèse d’induction. Or, divisibilité est transitive : si p | d et d | (t + 1), alors 19 67
20 71
p | (t + 1). (conclusion) Tout entier 2 ≤ n possède un diviseur premier. 21 73
Preuve de Théorème 11.9. On démontre que pour tout ensemble fini 22 79
23 83
P = { p1 , p2 , . . . , pm } de nombres premiers, il existe un nombre premier p 6∈ P.
24 89
Considérons le successeur du produit s = ∏im=1 pi + 1. (Avec s = 2 quand m = 0). 25 97
On a ...
s = 1 + pk · ∏ pi donc s mod pk = 1 (11.2)
1≤ i ≤ m
i 6=k
pour tout k. Par Lemme 11.10, soit s est un nombre premier, soit s est un nombre
composé avec un diviseur p qui est un nombre premier. Si s est un nombre premier,
alors s 6∈ P car s > pk pour tout k. Si p | s, alors p 6= pk pour tout k car pk - s
par (11.2), donc p 6∈ P.
100
(gcd(0, 0) = ∞ n’est pas défini.) Deux entiers sont premiers entre eux (ou
étranges) si leur PGCD est 1.
u0 = 1 v0 = 0 x0 = 0 y0 = 1 initialisation
u k +1 = x k v k +1 = y k xk+1 = uk − xk · b ak /bk c yk+1 = vk − yk · b ak /bk c si bk 6= 0
101
Théorème 11.12 (Inverses multiplicatifs). Soit 0 < b < m deux entiers positifs
qui sont premiers entre eux. Alors il existe un entier positif v < m t.q.
ab ≡ 0 (mod n) n divise ab
u( ab) ≡ u · 0 (mod n) multiplication par u
b≡0 (mod n) u · 0 ≡ 0; u( ab) ≡ (ua)b ≡ 1 · b
F IGURE 11.2: Portrait de Carl Friedrich
G AUSS (1777–1855), l’un des plus grands
mathématiciens de tous les temps, à l’age
Preuve de Lemme 11.15. Puisque p possède 2 diviseurs positifs, pour tout de 63, par Christian Albrecht Jensen. Gauss
entier a, gcd( a, p) = 1 ou gcd( a, p) = p. Si gcd( a, p) = 1, p divise b par a inventé l’arithmétique modulaire par
congruences, et a été le premier à démontrer
Lemme 11.14. Si gcd( a, p) = p, alors p divise a. proprement le théorème fondamental de
l’arithmétique sur l’unicité de la décomposi-
Théorème 11.16 (Théorème fondamental de l’arithmétique). Tout entier tion en facteurs premiers.
positif n peut être écrit comme un produit de nombres premiers :
k
n= ∏( pi )ei = |p1 ·{z· · p}1 · |p2 ·{z· · p}2 · · · |pk ·{z· · p}k
i =1
e1 fois e2 fois ek fois TABLE 11.8: Décomposition en facteurs
premiers. (Les points de suspension . . .
avec un k ∈ N quelconque, des nombres premiers p1 < p2 < · · · < pk , et leurs dénotent une suite infinie de 0s.)
exposants ei > 0. La décomposition en produit de facteurs premiers est
unique. n factorisation suite {ek }
1 1 {0, . . . }
En une représentation équivalente, pour chaque entier positif n > 0 il 2 21 {1, 0, . . . }
existe une suite infinie unique {e j }∞ N+ t.q. 3 31 {0, 1, 0, . . . }
j =1 ∈ N 4 22 {2, 0, . . . }
∞ 5 51 {0, 0, 1, 0, . . . }
n= ∏(π j )ej = 2e1 · 3e2 · 5e3 · 7e4 · 11e5 · · · 6
7
21 · 31
71
{1, 1, 0, . . . }
{0, 0, 0, 1, 0 . . . }
j =1
8 23 {3, 0, . . . }
avec la suite des entiers premiers {π j } = {2, 3, 5, 7, 11, . . . }, et leurs expo- 9 32 {0, 2, 0, . . . }
10 21 · 51 {1, 0, 1, 0, . . . }
sants e j ≥ 0. Table 11.8 montre des exemples. Seulement un nombre fini 11 111 {0, 0, 0, 0, 1, 0, . . . }
des e j sont positifs : ∑∞
j=1 e j < ∞. 12 22 · 31 {2, 1, 0, . . . }
13 131 {0, 0, 0, 0, 0, 1, 0, . . . }
Définition 11.6. Le plus petit commun multiple (lcm, least common 14 21 · 71 {1, 0, 0, 1, 0, . . . }
multiple) entre a, b ∈ Z − {0} est le plus petit entier positif qu’ils divisent simulta- 15 31 · 51 {0, 1, 1, 0, . . . }
16 24 {4, 0, 0, . . . }
nément (lcm( a, b) n’est pas défini quand a = 0 ou b = 0) 17 171 {0, 0, 0, 0, 0, 0, 1, 0, . . . }
n o 18 21 · 32 {1, 2, 0, . . . }
lcm( a, b) = min k ∈ N+ ( a | k) ∧ (b | k) 19 191 {0, 0, 0, 0, 0, 0, 0, 1, 0, . . . }
n o 20 22 · 51 {2, 0, 1, 0, . . . }
= min k ∈ N+ k mod | a| = 0 ∧ k mod |b| = 0 . 21 31 · 71 {0, 1, 0, 1, 0, . . . }
22 21 · 111 {1, 0, 0, 1, 0, . . . }
Il est facile de déterminer divisibilité à partir de la décomposition en fac- 23 231 {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, . . . }
24 23 · 31 {3, 1, 0, . . . }
teurs premiers : a divise b si et seulement tout facteur premier de a est un fac- 25 52 {0, 0, 2, 0, . . . }
teur de b, avec une multiplicité dans a inférieure ou égale à celle dans b (voir 26 21 · 131 {1, 0, 0, 0, 0, 1, 0, . . . }
27 33 {0, 3, 0, . . . }
...
103
22 · 31 · 51 = 60
gcd( a, b) · lcm( a, b) = ab
21 · 31 · 51 = 30 20 · 31 · 51 = 15
pour tout a, b > 0. Table 11.10 montre des exemples. 22 · 30 · 51 = 20 22 · 31 · 50 = 12
1 0 1
2 · 3 · 5 = 10 21 · 31 · 50 = 6
Preuve de Théorème 11.16. Existence. On démontre par induction que tout n
peut être factorisé. (base) L’entier n = 1 est factorisé par le produit vide avec k = 0 : 20 · 30 · 51 = 5 20 · 31 · 50 = 3
∏0i=1 ( pi )ei = 1. (induction) Supposons que tout m ≤ n peut être factorisé pour un n 2 0 0
2 ·3 ·5 = 4 21 · 30 · 50 = 2
positif. Si (n + 1) est un nombre premier, il peut être factorisé avec k = 1, 20 · 30 · 50 = 1
( p1 , e1 ) = (n + 1, 1). Autrement, (n + 1) est un nombre composé, et par
Lemme 11.10 il existe un nombre premier p qui divise (n + 1). Soit m = (n + 1)/p.
Puisque p > 1, m < (n + 1), et par l’hypothèse d’induction, il existe une factorisation TABLE 11.10: Plus grand commun divi-
seur et plus petit commun multiple par
m = ∏ik=1 ( pi )ei . Alors (n + 1) = pm = p ∏ik=1 ( pi )ei est une décomposition décomposition en facteurs premiers
de (n + 1) en facteurs premiers. (conclusion) Il existe une décomposition pour tout
n > 0. 90 = 21 · 32 · 51
Unicité. Supposons que n = ∏ik=1 ( pi )ei = ∏`j=1 (q j ) f j sont deux décompositions 60 = 22 · 31 · 51
en facteurs premiers pi et q j , avec exposants positifs ei et f j . Considérons les facteurs
gcd(90, 60) = 21 · 31 · 51 = 30
différents :
lcm(90, 60) = 22 · 32 · 51 = 180
f f
D1 = i 0 < i ≤ k ∧ ¬∃ j : piei = q j j D2 = j 0 < j ≤ ` ∧ ¬∃i : q j j = piei 2022 = 21 · 31 · 3371
1065 = 31 · 51 · 711
On démontre que D1 = D2 = ∅ et donc les deux factorisations sont identiques.
gcd(2022, 1065) = 20 · 31 · 50 · 710 · 3370 = 3
Supposons par l’absurde que D1 6= ∅. Soit m ∈ D1 un élément quelconque (p.e.,
m = min D1 ), et p = pm le facteur premier correspondant avec son exposant e = em lcm(2022, 1065) = 21 · 31 · 51 · 711 · 3371 = 717810
selon la première décomposition. Soit f = f j s’il existe p = q j , ou f = 0 si q j 6= p 2023 = 71 · 172
pour tout j. Par notre supposition, e 6= f . On a alors 1065 = 31 · 51 · 711
Machine de Turing. La machine de Turing 2 comprend seulement un ru- F IGURE 12.1: Alan T URING (1912–1954),
inventeur des fondations scientifiques de
ban infini de cellules contenant un symbole chacune, et une tête de lecture- l’informatique. [Autour de 1930.]
écriture qui se positionne sur une cellule à la fois. L’algorithme sur la ma- 2. (fr):machine de Turing
chine de Turing comprend un ensemble Q (fini) d’états incluant un ensemble
F ⊆ Q d’états terminaux, un alphabet A de symboles, et l’ensemble T de
règles d’action pour la tête et les transitions d’états :
T : (Q − F) × A → Q × A × {+1. − 1}
état lire prochain écrire déplacer
Machine RAM. La gestion de mémoire est difficile avec une machine de F IGURE 12.2: Machine RAM : l’architec-
Turing car la tête glisse par une case à la fois, donc on a un accès séquentiel aux ture von Neumann. L’aspect innovateur
était de stocker les données et le code dans
cellules du mémoire. Dans une machine RAM 3 on peut adresser le mémoire
le même mémoire vive. L’unité de contrôle
directement, et y stocker les données. L’ensemble d’instructions imite les exécute les instructions, en maintenant l’état
langages des CPUs contemporaines. La machine RAM permet l’abstraction du programme avec l’adresse de l’instruction
courante. L’unité arithmétique performe
d’un emplacement en mémoire par une variable. Une variable comprend le calcul avec les valeurs en mémoire et la
(i) le nom, (ii) l’adresse en mémoire (lvalue), (iii) la valeur (rvalue), (iv) le type variable spéciale accumulateur.
(déterminant la représentation de la valeur dans les cellules du mémoire), et 3. (fr):machine RAM. RAM = Random
Access Memory (mémoire vive avec adressage)
(v) la portée (visibilité de la variable).
106
Algorithme M A X 3 : retourne le maximum de trois nombres F IGURE 12.3: Pseudocode d’un algorithme
Entrée : trois nombres x, y, z ∈ R avec mots-clés français.
Sortie : maximum de x, y, z
M1 max = x
M2 si y > max alors max = y // maintenant max = max{ x, y}
M3 si z > max alors max = z
retourner max
Algorithme M A X N
double maxN(double[] x)
// retourne le maximum de 0 ≤ n < ∞ éléments {
double m = Double.NEGATIVE_INFINITY;
Entrée : taille n, valeurs ( x0 , x2 , . . . , xn−1 ) avec n ∈ N for (int i=0; i<x.length; i++)
if (x[i]>m) m=x[i];
int maxN(int[] x)
X1 max = −∞ // initialisation pour séquence vide {
int m = Integer.MIN_VALUE; // "-infini"
X2 for i = 0, 1, . . . , n − 1 do for (int i=0; i<x.length; i++)
if (x[i]>m) m=x[i];
X4 return max
F IGURE 12.4: Pseudocode et implémen-
tations Java pour un algorithme simple qui
trouve le maximum dans un tableau. Nos
idiosyncrasies de notation : mots-clés en gras
(if..then, for..do, return), tabulation pour
imbriquer les blocs d’instruction.
107
Exactitude
La correction ou exactitude d’un algorithme peut être démontrée comme
tout autre énoncé logique. Typiquement, on donne une preuve par induc-
tion sur l’entrée. Une technique essentielle est l’introduction de conditions
logiques invariantes pour les itérations d’une boucle. La preuve de Théo-
rème 12.1 est un exemple d’une telle démarche. TABLE 12.1: Algorithme pour maximum
de n éléments. Noter que cette version on
Théorème 12.1. L’algorithme M A X (Table 12.1) détermine le maximum de n commence les membres avec l’indice 1.
éléments correctement. (Le maximum de la séquence vide est −∞.)
Algorithme M A X ( x1 , . . . , xn )
X1 max = −∞
Preuve d’exactitude. Soit mi = max après l’exécution de Ligne X3 à i = 1, 2, . . . n, et X2 for i = 1, 2, . . . , n do
m0 = −∞. On montre par induction que X3 if xi > max then max = xi
X4 return max
mi = max x1 , . . . , xi invariant de la boucle
pour tout i. (base) m0 = −∞. (induction) Supposons que l’invariant vaut pour
un i < n. Au début de la (i + 1)-ème itération, max = mi , et selon l’H.I., après
l’exécution de X3, max = mi+1 = max{mi , xi+1 } = max{ x1 , . . . , xi+1 }.
(conclusion) max = mn = max{ x1 , . . . , xn } est correctement retournée en
Ligne X4.
Complexité
La complexité d’un algorithme mesure sa performance en fonction de la
taille du problème il est destiné à résoudre. En particulier, on caractérise les
ressources (temps, mémoire) nécessaires pour l’exécution.
? usage de mémoire ou «complexité d’espace» (space complexity) : c’est le
mémoire de travail nécessaire à part de stocker l’entrée même. Le mé-
moire de travail est le mémoire utilisé à part de l’entrée et de la sor-
tie. Afin de caractériser un algorithme, on veut estimer en particulier
l’empreinte (footprint), ou l’usage de mémoire maximal pendant l’exécu-
tion en fonction de l’entrée.
? temps de calcul ou «complexité de temps» (time complexity) : c’est le temps
d’exécution dans un modèle formel de calcul.
La théorie de la complexité 4 est une des branches importantes de l’informa- 4. :Théorie de la complexité
(fr)
Ce tri est utile seulement quand le coût des comparaisons est négli- 0 2 1 (1, 0 , 6, 5)
0 3 1 (1, 0 , 6, 5)
geable par rapport aux échanges, mais alors il atteint le minimum possible.
0 1 (0, 1, 6, 5) S5
1 1 (0, 1 , 6, 5) S2
1 2 1 (0, 1 , 6, 5) S4
1 3 1 (0, 1 , 6, 5)
1 1 (0, 1, 6, 5) S5
2 2 (0, 1, 6 , 5) S2
2 3 3 (0, 1, 6, 5 ) S4
2 3 (0, 1, 5, 6) S5
3 (0, 1, 5, 6) S1
110
Tri par insertion. Le tri par insertion 7 maintient l’ordre dans les préfixes 7. :tri par insertion
(fr)
Définition 12.1. Un 8 algorithme est dit récursif s’il permet de résoudre un 8. Parfois, pour un problème compliqué,
problème avec une entrée de plus petite taille. l’algorithme récursif est défini à l’aide d’un
ou de multiples algorithmes auxiliaires, avec
des récursions entre eux.
(ii) chaque appel récursif nous rend «plus proche» à un cas terminal.
(iii) La récursion exploit un ordre parmi les instances (entrées), avec les élé-
ments minimaux correspondant aux cas de base, impliquant la finitude des
récurrences (ce qu’on peut démontrer par induction).
Penser en récurrences
Parfois, la récursion nous fournit des solutions très simples à des problèmes
complexes. La clé est d’identifier des sous-problèmes dont la solution mène
à la solution du problème original. On construit un tel algorithme en identi-
fiant la relation de récurrence, sans devoir réfléchir sur l’ordre final des actions
exécutées à travers de toutes les instances de sous-problèmes calculés. L’algo-
rithme résultant n’est pas nécessairement le plus efficace possible, mais souvent
plus facile à concevoir qu’une solution par des itérations compliquées. Et assez
souvent, comme dans le cas du problème de l’Exemple 12.2 ou des problèmes
typiques sur des arbres, l’algorithme récursif est le plus simple et le plus effi-
cace.
Exemple 12.2 (Tours de Hanoï). Dans le jeu de Tours de Hanoï, il faut déplacer
des disques à diamètres différents (1, 2, . . . , n) d’une tour de départ à une tour d’arrivée
en passant par une tour intermédiaire, tout en respectant Règles 1 et 2 ci-dessous.
L’opération M O V E (i → j) déplace le disque en haut de tour i à tour j. Les disques
sont en ordre décroissant au début, et il y a trois tours.
Règle 1. On ne peut déplacer plus d’un disque à la fois. Un déplacement consiste de
mettre le disque supérieur sur une tour au-dessus des autres disques (s’il y en a).
Règle 2. On ne peut placer un disque que sur un autre disque plus grand ou sur un
emplacement vide.
On peut trouver une solution par un algorithme récursif : après qu’on place le n-ème
disque sur la tour finale, on doit ranger les (n − 1) disques restants au-dessus, et ils se
trouvent forcément en ordre décroissant sur la même tour (car le n-ème se déplace
entre les deux autres tours). Or, c’est le même problème pour déplacer (n − 1) disques
d’une tour à l’autre ! On définit alors par récurrence l’algorithme H A N O I (i, k, j, n)
qui déplace les n disques supérieurs sur tour i vers tour j en utilisant la tour intermé-
diare k :
H A N O I (i, j, k, n)
H1 if n 6= 0 then // cas terminal : n = 0, rien à déplacer
H2 H A N O I (i, j, k, n − 1) // sous-problème : déplacer (n − 1) disques
H3 M O V E (i → j )
H4 H A N O I (k, i, j, n − 1) // sous-problème : déplacer (n − 1) disques
Programmation dynamique
Quand on dessine un algorithme récursif avec des sous-problèmes chevau-
chants, l’ordre d’évaluation est important. Démarches possibles :
? en calcul descendant (top-down) : avec appels récursifs ; ou
? en calcul ascendant (bottom-up) : programmation dynamique
L’approche par programmation dynamique est basée sur l’identification des
sous-problèmes distincts qu’on calcule en induction, des plus petits vers les plus
grands.
Exemple 12.4 (Nombres Fibonacci par programmation dynamique). On peut
calculer les nombres Fibonacci f 0 = 0, f 1 = 1, f n = f n−1 + f n−2 par une
implémentation directe de la définition récursive, mais c’est très inefficace car les
récurrences nécessitent le calcul du même nombre Fibonacci plus qu’une fois. Au lieu
TABLE 12.8: Nombres Fibonacci par
des appels récursifs, c’est mieux de calculer les f n dans l’ordre ascendant de n. programmation dynamique et deux variables
F I B O R E C (n) // algorithme inefficace pour calculer f n auxiliaires.
R1 if n ∈ {0, 1} then return n F I B O D P 2 (n) // n > 0
// p = f i−1 et f = f i
R2 else return F I B O R E C (n − 1) + F I B O R E C (n − 2) // appels récursifs
D1 p = 0; f = 1 // i = 0
F I B O D P (n) // algorithme plus efficace pour calculer f n D2 while (0 < n) do
E1 f 0 = 0, f 1 = 1 D3 ( p, f ) = ( f , p + f )
D4 n = n−1 // i = i + 1
E2 for i = 2, 3, . . . , n do f i = f i−1 + f i−2 // programmation dynamique
D5 return f
E3 return f n
Algorithme F I B O DP utilise un mémoire de travail avec (n + 1) variables (les f i ),
mais, en fait, il suffit de garder juste les deux nombres précédents à la fois :
v. Table 12.8.
13 Analyse d’algorithmes
L’ E F F I C A C I T É d’un algorithme est jugée par surtout par son temps de calcul.
Le temps de calcul, comme les autres quantifications de performance, est
une fonction de la taille de l’entrée. En général, la performance n’est pas
entièrement déterminé par la taille, et on considère le pire (ou meilleur ou
moyen) cas.
Les fonctions qu’on rencontre en informatique sont parfois compliquées et difficile à exprimer simplement en une forme
fermée. Le but de l’analyse algorithmique est d’établir le comportement asymptotique de ces fonctions : quel genre de
terme domine le temps de calcul ? Typiquement, on arrive à caractériser le temps de calcul comme essentiellement une
fonction logarithmique, linéaire, quadratique, etc. Les techniques d’analyse asymptotique nécessitent leur notation ma-
thématique (équivalence asymptotique ∼ et «grand-O») qui formalisent les notions comme «essentiellement linéaire».
Entre autres, on a besoin des résultats sur les solutions asymptotiques pour les récurrences qui émergent quand l’algo-
rithme analysé est récursif.
f (n)
f (n) ∼ g(n) si et seulement si lim =1 « f est asymptotiquement équivalent à g»
n→∞ g(n)
f (n)
f (n) = o g(n) si et seulement si lim =0 « f est négligeable par rapport à g»
n→∞ g (n )
Théorème 13.1. Dans le domaine des fonctions, ∼ est une relation d’équivalence
et o est un ordre strict.
L’équivalence asymptotique est une relation d’équivalence, donc on peut TABLE 13.1: L’échelle standard : ordres de
définir les classes d’équivalence par des membres représentatifs. Par exemple croissance typiques dans l’analyse d’algo-
rithmes.
n ∼ (n + 1), et on peut choisir f (n) = n ou g(n) = n + 1 comme
h(n) ordre f (n)
représentatifs de toute fonction équivalente h : N → R avec limn→∞ n =
h(n) constante 1
n +1 = 1. En algorithmique, on préfère les caractérisations asymptotiqes logarithmique log n
en termes de fonctions élementaires, choisies sur une échelle standard qui linéaire n
linéarithmique n log n
comprend les fonctions représentatives quadratique n2
cubique n3
? pouvoirs de n : g(n) = n a incluant a = 0 pour constantes, exponentiel(*) An avec un 1 < A
? logarithmes et logarithmes itérés : g(n) = log n, log log n, log log log n, . . . ,
? exponentielles : g(n) = an avec une constante 1 < a, (*) Noter qu’on parle de croissance exponen-
tielle avec n’importe quel base : g(n) = 2n
et leurs produits comme n log log n. On cherche des approximations asymp- ou g(n) = 3n , mais an = o (bn )] si
a < b. Chaque choix de A correspond à une
totiques de forme T (n) ∼ c · g(n) où T (n) est la quantité (temps de calcul)
différente classe d’équivalence.
116
caractérisée, c est une constante et g(n) est une fonction sur l’échelle standard,
appellée l’ordre de croissance de T. La base du logarithme est sans impor-
tance dans l’ordre de croissance car la constante peut absorber le changement
de base : loga x = logb x/ logb a.
On rencontre les temps quadratiques et cubiques le plus souvent avec des
algorithmes itératifs : deux ou trois boucles imbriquées sur les éléments d’une
séquence. La croissance logarithmique et linéarithmique caractérisent le temps
de calcul des algorithmes populaires employant le principe de diviser-pour-
régner.
? solution logarithmique : diviser pour éliminer ; p.e., T (n) = T (bn/2c) + 1 (recherche dichotomique)
? solution linéarithmique : combiner en temps linéaire ; p.e., T (n) = T (bn/2c) + T (dn/2e) + n − 1 (tri fusion).
x ∈ { ak }ik+=ni −1 = x ∈ { ak }m −1
k =i ∨ ( x = am ) ∨ x ∈ { ak }ik+=nm−+11
| {z } | {z } | {z }
≡ 0 si am < x succès ≡ 0 si x < am
117
1 + blg nc lg n 1 + blg nc 1 + lg n
lim ≥ lim = 1; lim ≤ lim = 1,
n→∞ lg n n→∞ lg n n→∞ lg n n→∞ lg n
d’où 1 + blg nc ∼ lg n. Une recherche avec succès se termine au pire juste avant la
récursion pour déclarer échec, donc après Bn − 1 appels.
Démonstration. À chaque itération de la boucle de Ligne F2, il y a une comparaison (Ligne F3), et la somme (i + j) croît par 1.
On sort de la boucle quand i = n ou j = m, et au pire cela arrive avec i = n, j = m − 1 ou i = n − 1, j = m,
après i + j = n + m − 1 comparaisons.
Le tri fusion 3 (mergesort) est un exemple classique d’usage du principe de 3. :tri fusion
(fr)
diviser pour régner dans une procédure récursive. Un sous-problème est le tri 9 6 3 0 2 1 8 7 5 4
des éléments aux indices g, g + 1, . . . , d − 1 avec 0 ≤ g ≤ d < n (une «sous-
séquence»). Démarche de l’algorithme : couper en deux sous-séquences, les division 50-50% sans réarrangement
trier dans deux appels récursifs, et ensuite combiner les résultats par F U S I O N .
Algo M E R G E S O RT ({ Ti }in=−01 , g, d) // premier appel avec g = 0, d = n 9 6 3 0 2 1 8 7 5 4
// récursion pour trier la sous-séquence aux indices g..d − 1 n/2 éléments n/2 éléments
M1 if d − g < 2 then return { Ti }dg−1 // cas de base : séquence vide ou un seul élément
M2 m ← (d + g)/2 // partitionner : m est au milieu récursion récursion
M3 M E R G E S O RT ( T, g, m) // sous-problème : trier partie gauche
M4 M E R G E S O RT ( T, m, d) // sous-problème : trier partie droite
M5 C = F U S I O N ({ Ti }im=−g1 , { Ti }id=−m1 ) // combiner : fusion des résultats 0 2 3 6 9 1 4 5 7 8
0 1 2 3 4 5 6 7 8 9
nombre de comparaisons au total : C (0) = C (1) = 0, et Analyse du tri par fusion. Par Lemme
Analyse du
7.4,trilapar fusion.
fusion de Ligne
Par Lemme
M5 se fait
7.4, la fusion de Ligne M5 se fa
1
10
11
Analyse du tri par fusion. Par Lemme 7.4, la fusion de Ligne M5 se fait 100
C (n) = C bn/2c + C dn/2e + (n − 1) si 1 < n par (n 1) comparaisons au pire. On a alors la récurrence pour C (n), le
(13.2)de comparaisons
111
1 0 1 0 = 1 0 1 0
nombre au total
nombre
: de comparaisons au total :
1 1 1 1 1 1 1 1
1000
1001
nombre
8 de comparaisons au total8 1 0
:0 1 0 0 1 0 0 1 0 0
1010
1011
<0 Analyse8du tri par fusion. < Par Lemme 7.4, la fusion de Ligne M5 se fait 1100
1 0 1
0 {n = 0, 1} 1 0
1 0 1 1 0 1 1 0
{n = 0, 1}
1
S(n) des codages en binaire (v. C(n) =
1101
n −1
:CC (bnn/2
nombre
1 c1 + C d n/2
)1 = 1 e1 +1 : b1n/2
nCtotal
(au )1: 1c{n1+>C1}dn/2 e + (n 1) {(7.5) n > 1}
0 de comparaisons
Fig. 13.2) ! On a alors C (n) = S(n) = ∑k=1 1 + blg kc , et c’est une 1 0 0 :
81 0 0 1
C bn/2c + C dn/2e + (n 1) {n > 1} Same recurrence as mergesort (ex
8
1 0 0
1 0 0 1
0 1 0
8 1 0 0 1
0 0 1 0
1 0 0 1
0 0
Same recurre
Lemme 7.2.
S(n) = n lg n − n 21−u − (1 − u) + 1. (13.3)
Tri hybride. En pratique,
Tri hybride. Tripar
le tri hybride.
Enfusion performe
En le
pratique, pratique,
le mieux
tri par le tri par
fusion dansfusion
une ap-
performe
Tri hybride. En pratique, le tri par fusion performe le mieux dans une ap-
performe le mieux
le mieux dans dans un
une ap-
proche hybride : laprocherécursion est trop:hybride
proche
hybride couteuse
la : pour
récursionla récursion
est les
troppetits
estsous-tableaux,
trop pour
couteuse couteuse pour sous-tableaux,
les petits les petits sous-t
partest 1rapide.
0 plus
proche hybride : la récursion est trop couteuse pour les petits sous-tableaux,
et le tri par insertionetestleplus rapide.
et insertion
tri par le triPour insertion
cette
plusraison,
est il vaut
rapide.
Pour implanter
cettePour cette
le tri
raison, raison,
il vaut il vaut implant
implanter le tri
Démonstration. On obsèrve que 1 + blg nc est exactement le nombre de bits dans la avec
et le tri par insertion est0plus 0rapide.
0 Pour0 cette raison, il vaut implanter le tri
par fusion un seuil ` > 1par
par fusion surfusion
avec les
unpetits
seuil >0seuil
avecsous-tableaux.
`un 1 sur`les 1 surpasse
On
> petits les petits
les sous-
sous-tableaux.
sous-tableaux. On passe On passe l
les sous-
représentation binaire de n. Figure 13.3 montre comment sommer les longueurs en par fusion avec un seuil 1` > 01 sur 0 les0 petits
1 sous-tableaux. On passe les sous-
tableaux de taille d tableaux
g < ` en tableaux
de Ligne
taille dM1 < `d en gLigne
de taille
gdirectement <à `unM1
entriLigne
par insertion.
M1 directement
directement à un
à un tri par tri par in
insertion.
tableaux de taille d g 2< ` 0 en Ligne
0 1 M1 0 directement à un tri par insertion.
bits : on peut placer tout dans une rectangle n × (1 + t), et il manque 20 , 21 , . . . , 2t
Gestion d’espace 3auxiliaire.
0 0 Typiquement,
1 1 on utilise un seul tableau auxiliaire
zéros en haut dans les colonnes 0, 1, . . . , t jusqu’à t = blg nc. Donc 4 pour faire la fusion. Avec
0 1 un0arrangement
0 bitonique, on peut simplifier les
t conditions dans5la boucle
0 1 de0la fusion.
1
S ( n ) = n (1 + t ) − ∑ 2i = n(1 + t) − (21+t − 1). 6 0 1 1 0
7
n
i =0 0 1 1 1
8 1 0 0 0
Avec la partie fractionnaire u = lg n − t, on a également, par la substitution 9 1 0 0 1
t = (lg n) − u 10 1 0 1 0
11 1 0 1 1
S(n) = n 1 + lg n − u) − (21+lg n−u − 1) = n lg n + n(1 − u) − 21−u · 2lg n + 1, 1+t
et on arrive à Éq. (13.3) en notant 2lg n = n. F IGURE 13.3: Somme des longueurs de
codage en binaire.
Démonstration.((si) Supposons que f = O( g). Par Définition 13.2, il existe 0 < c, 0 ≤ N t.q. | f (n)| ≤ c| g(n)| pour tout n ≥ N.
| f (n)| si n < N f + (n)
Soit f + (n) = Alors, | f (n)| ≤ f + (n), et on a limn→∞ | g(n)| = c, donc f + (n) ∼ c| g(n)|. La preuve pour
c · | g(n)| si N ≤ n
Ω procède de même façon (mutatis mutandis).
(seulement si) Supposons qu’il existe une fonction f − : N → R et une constante 0 < a t.q. f − (n) ∼ a · | g(n)| et f − (n) ≤ | f (n)|
f (n)
pour tout n. Soit 0 < ε < 1 arbitraire (p.e., ε = 1/2). Par la définition de la limite limn→∞ a|−g(n)| = 1, il existe N ∈ N
f ( n)
t.q. pour tout n ≥ N, 1 − ε < a| g(n)|
, donc (1 − ε) a| g(n)| < | f (n)|. Avec c = (1 − ε) a, une constante positive, on a
c| g(n)| < f − (n) ≤ | f (n)| pour tout n ≥ N. La preuve pour O procède de même manière (avec 1 < ε).
On remarque qu’il est bien possible pour deux fonctions f , g de ne pas être en aucune relation par ordre de crois-
sance : ni f = O( g), ni f = Θ( g), ni f = Ω( g).
f ( n ) = c 0 g0 ( n ) + c 1 g1 ( n ) + c 2 g2 ( n ) + · · ·
f = O ( g0 ) f = c 0 g0 + O ( g1 )
f = c 0 g0 + c 1 g1 + O ( g2 ) ···
Ici, le dernier terme dans les formules est le terme d’erreur. Plus généra-
lement, une formule avec des termes en notation de Landau (o, O, Θ, Ω)
est interprétée comme des termes cachés : chacun peut être remplacé par une
fonction bien définie, avec l’ordre de croissance du terme borné en notation
Landau. Par exemple :
n
nn = 2lg n = 2n lg n = 2Θ(n log n) et f (n) = 2Θ(n log n) ↔ lg f (n) = Θ(n log n)
122
Fonctions notables
Nombres harmoniques. Expansions asymptotiques :
n
1 1 1 1
Hn = ∑ i
= 1 + + + · · · = ln n + γ + O(1/n) = ln n + O(1) = Θ(log n)
2 3 n
croissance logarithmique
i =1
ϕn ϕn − (− ϕ)−n
Fn = √
Fn = √ ∓ O( ϕ−n ) = Θ( ϕn ) croissance exponentielle 5
5 | {z }
(1.618··· )n −(−0.618··· )n
O ( f g ). Θ( f · g) = Θ( f ) · Θ( g)
Les mêmes règles appliquent à Ω et Θ (v. Table 13.5).
123
z0 = ( x0 + y0 ) mod d q1 = b( x0 + y0 )/dc
Algo M U L ( xn−1 · · · x0 , yn−1 · · · y0 )
zi = ( xi + yi + qi ) mod d qi+1 = b( xi + yi + qi )/dc pour 1 ≤ i < n M1 z = 0 · · · 0
M2 for i = 0, 1, . . . , n − 1 do
zn = qn . M3 if xi = 1 then z = A D D (z, y)
M4 y = y << 1 // décalage à gauche
Figure 13.5 montre le pseudocode de l’addition en binaire avec un carry bit. M5 return z
F IGURE 13.6: Multiplication en binaire. En
Multiplication à base d-aire se calcule par des additions « décalées » :
Ligne M4, on met à jour y2i : la multipli-
n −1 cation par 2i est un décalage gauche de bits
xy = ∑ xi d · y = ∑ y · di
i
décalage de xi y = y par i vers gauche par i positions (dénoté par << i en Java, C,
i =0
et d’autres langages de programmation).
{ i | x i 6 =0}
124
0 si b = 0
N ( a, b) =
max n Fn ≤ b ∧ Fn+1 ≤ a si 0 < b
a b N ( a, b)
0 0
1 1 1
2, 3, . . . 1 2
2 2 2
3, 4, . . . 2 3
3, 4 3, 4 3
5, 6, . . . 3, 4 4
5, 6, 7 5, 6, 7 4
8, 9, . . . 5, 6, 7 5
...
125
Fn Fn+1 Fn+2
Cas (i)
b < Fn a
Fn Fn+1
Cas (ii)
b a
Théorème 13.8. Si a < Fn+2 ou b < Fn+1 , alors l’algorithme d’Euclide fait n
divisions au plus.
CPU pour 32 bits ou 64 bits. Il est rarement nécessaire de dépasser cette ran-
gée arithmétique dans les applications informatiques, excepté dans le domaine
de cryptographie. En une application cryptographique, on transforme un
message clair m en un message chiffré s (le cryptogramme), à l’aide d’une
clé k secrete. La fonction de chiffrement (m, k ) 7→ s est calculée rapidement,
tandis que déduire le message m à partir de s doit être difficile sans connaître
la clé. Un tel problème algorithmique difficile est celui du logarithme discret : 10. Algorithme inventé en 1977 par Ro-
étant donné les entiers n, x et y = x k mod n, inférer l’exposant k. Le pro- nald R IVEST, Adi S HAMIR, et Leonard
tocole du chiffrement RSA 10 est basé sur le théorème d’Euler. Sa sécurité A DLEMAN.
Théorème 13.9 (Théorème d’Euler). Soit ϕ : N+ → N+ la fonction d’in- TABLE 13.7: La fonction d’indicatrice
d’Euler, dénotée par ϕ. La colonne P(n) est
dicatrice qui est le nombre d’entiers positifs inférieurs à n qui sont premiers avec n. l’ensemble des entiers positifs entre 1 et n
Pour deux entiers 0 < a, n, si gcd(n, a) = 1, alors a ϕ(n) ≡ 1 (mod n) qui sont premiers avec n.
n ϕ(n) P(n)
Démonstration. Soit P(n) l’ensemble des entiers premiers avec n comptés par ϕ 1 1 {1}
2 1 {1}
P(n) = k 1 ≤ k ≤ n ∧ gcd(n, k) = 1 3 2 {1, 2}
4 2 {1, 3}
Considérons la fonction x 7→ ax mod n pour un a fixe et tout x ∈ P(n). Elle est une 5 4 {1, 2, 3, 4}
injection par Lemme 11.14, si ax ≡ ay (mod n) et x, y ∈ P(n), alors x = y car 6 2 {1, 5}
a( x − y) ≡ 0 (mod n) implique que n | ( x − y). À cause de l’existence de l’inverse 7 6 {1, 2, 3, 4, 5, 6}
multiplicatif de a modulo n (Théorème 11.12), la fonction est aussi surjective 8 4 {1, 3, 5, 7}
9 6 {1, 2, 4, 5, 7, 8}
dans P(n) car pour tout y ∈ P(n), on a ax mod n = y avec x = a−1 y mod n.
10 4 {1, 3, 7, 9}
Considérons le produit de tous les entiers premiers avec n, entre 1 et n. Puisque 11 10 {1, . . . , 10}
x 7→ ax mod n est une bijection entre eux, 12 4 {1, 5, 7, 11}
...
∏ k≡ ∏ ( ak) (mod n) 1 · 3 · 5 · 7 ≡ (1 · 3) (3 · 3) (5 · 3) (7 · 3) (mod 8)
k∈ P(n) k∈ P(n) ≡3 ≡1 ≡7 ≡5
≡ a| P(n)| · ∏ k (mod n)
k∈ P(n)
a p−1 mod p = 1 .
Mc ≡ M (mod n)
Le chiffrement RSA 11 utilise Corollaire 13.11 pour l’encodage-décodage 11. :chiffrement RSA
(fr)
Dans des applications contemporaines (utilisant Transport Layer Security v1.3), e est
souvent choisi fixe (le nombre premier e = 65537 = 216 + 1 est populaire), et n est
choisi pour atteindre une longueur exigée (p.e., 1024/2048/4096 bits ou 128/256/512
bytes).
L’adversaire Ève connait les clés publiques d’Alice et Bob. Si elle veut briser le message
chiffré S, elle doit deviner la clé privée d de Bob qui est l’inverse multiplicatif
modulo ϕ(n), et pour cela, elle doit calculer ϕ(n) = ( p − 1)(q − 1) qui requiert la
factorisation de n = pq. Elle ne peut pas prétendre être Alice non plus, parce que pour
cela elle doit deviner la clé privée d d’Alice, et cela demande ϕ(n) pour le calcul de
l’inverse.
14 Dénombrement
et ainsi f établit un bon ordre dans S par x y ↔ f ( x ) ≤ f (y). Ou F IGURE 14.1: Compétences de dénom-
bien, avec un bon ordre quelconque à la main on peut énumérer les membres brement à l’école maternelle : établir la
de S : cardinalité |S| = n avec 1 ≤ n ≤ 10.
On utilise une composition de la bijection
g : S → R (compter S) et la bijection
s0 = min S, s1 = min S − {s0 } , s2 = min S − {s0 , s1 } , ... f : R → [n], avec R = {doigts},
R = {dés}, et R = {numéraux}. On
note aussi les représentations isomorphes de
car tous les minimums existent. Et parfois, c’est plus facile de commencer avec la fonction de successeur n 7→ n + 1.
l’énumération. Si la suite {si }in=−01 énumère les éléments d’un ensemble S sans 2. À part du dénombrement exact et asymp-
oublier ni répéter les membres, alors la taille de l’ensemble est |S| = n, car la totique, la combinatoire comme domaine
de mathématiques inclut des études de
fonction f (s) = min{i : si = s} est une bijection S → [n] bien définie. construction, existence ou optimisation
de structures discrètes, ou, en général,
l’emploi de techniques de dénombrement
14.1 Égalité et ordre pour adresser des problèmes mathématiques
diverses.
t t
|
A1 × A2 × · · · × A t
{z }
= ∏ Aj = ∏ nj
j =1 j =1
produit cartésien : nombre de tuples
Principe d’exponentiation
Le principe d’exponentiation est celui du produit quand on choisit du
même nombre de possibilités à chaque tâche.
Si une procédure comprend t tâches, et pour chacune tâche, il y a n
façons de l’effectuer, alors il y a nt façons d’effectuer la procédure.
On formalise le principe d’exponentiation comme le dénombrement des
fonctions avec domaine et co-domaine fixés. Puisqu’on peut énumérer les
membres d’un ensemble A = { a1 , . . . , at }, toute fonction f avec domaine A
est uniquement déterminée par la séquence des images correspondants, ou le
t-tuple
f ( a1 ), f ( a2 ), . . . , f ( a t ) .
B A = | B || A| = nk
Permutations
Le principe de multiplication s’applique aussi si les choix ne sont pas in-
dépendants mais le nombre de choix possibles ne change pas dans la même
position : l’ensemble des tuples A1 × A2 × · · · × At a toujours la même
cardinalité ∏tk=1 | Ai | si tout ensemble Ai dépend de ( Ai−1 , . . . , A1 ) mais la
taille | Ai | dépend seulement de i. On utilise le principe de multiplication dans TABLE 14.1: k-arrangements des éléments
{1, 2, 3} avec répétitions.
le dénombrement des injections.
k=1 k=2 k=3 k=4
Théorème 14.3 (Dénombrement des injections). Soit A, B deux ensembles 1 11 111 1111
finis de tailles t = | A| ≤ | B| = n. Le nombre des fonctions injectives A → B est 2 12 112 1112
égal à 3 13 113 1113
21 121 1121
t −1 22 122 1122
n! 23 123 1123
P(n, t) = n(n − 1)(n − 2) · · · (n − t + 1) =
| {z } ∏ (n − i ) = (n − t)!
.
31 131 1131
i =0
factorielle décroissante 32 132 1132
33 133 1133
Démonstration. Mettre les éléments de A = { a1 , a2 , . . . , at } dans n’importe quel 211 1211
t 212 1212
ordre. La suite des images f ( ai ) i=1 détermine la fonction f : A → B. On compte
213 1213
le nombre de possibilités : (1) il y a n choix pour b1 = f ( a1 ) ; (2) il y a (n − 1) choix 221 1221
pour b2 = f ( a2 ) 6= b1 ; (3) il y a (n − 2) choix pour b3 = f ( a3 ) ∈ B − {b1 , b2 }, 222 1222
etc., jusqu’à (n − t + 1) choix pour bt = f ( at ) ∈ B − {b1 , . . . , bt−1 }. En 223 1223
conséquence, le nombre de t-tuples des injections est ∏kt− 1 n!
231 1231
=0 ( n − k ) = ( n − t ) ! . 232 1232
233 1233
Il existe plusieurs notations pour la factorielle décroissante, avec souli- 311 1311
gnement ou parenthèses dans l’exposant. En une définition récursive : 312 1312
313 1313
1 321 1321
si t = 0 322 1322
nt = n(t) =
n · (n − 1)(t−1) si t > 0 323 1323
331 1331
332 1332
et donc 333 1333
n!
P(n, t) = n(t) = . . . (81 choix au total)
(n − t)!
lorsque 0 ≤ t ≤ n sont des entiers.
La définition récursive est valide pour tout 0 ≤ t : mais si n < t, on a
P(n, t) = n(t) = n(n − 1) · · · 0 · · · (n − t + 1) = 0. En effet, si | A| > | B|,
132
Corollaire 14.4 (Dénombrement des bijections). Soit A, B deux ensembles finis TABLE 14.2: k-arrangements des élé-
ments {1, 2, 3, 4} sans répétitions (ou
de même taille n = | A| = | B|. Le nombre de fonctions bijectives A → B est égal
k-permutations). La colonne k = 4 donne les
à (n!). permutations.
Un arrangement de 0 ≤ k objets parmi n est un choix de k objets, cha- k=1 k=2 k=3 k=4
cun étant choisi parmi les n. Dans un arrangement avec répétitions (ou 1 12 123 1234
avec remise), les object choisis ne sont pas nécessairement distincts. Dans un 2 13 124 1243
3 14 132 1324
arrangement sans répétitions, les objets sont distincts. Une permutation 4 21 134 1342
est un n-arrangement de n éléments sans répétition, c’est à dire, un ordon- 23 142 1423
24 143 1432
nancement de tous les éléments. Une k-permutation est un k-arrangement 31 213 2134
sans répétitions. Un k-arrangement est la même chose qu’une séquence de 32 214 2143
longueur k ou un k-uple, mais considéré comme un objet combinatoire. 34 231 2314
41 234 2341
Un k-arrangement a1 · · · ak choisi parmi les éléments d’un ensemble A 42 241 2413
de taille n correspond à une fonction g : [k] → A, et un arrangement sans 43 243 2431
312 3124
répétitions est injective. En particulier, une permutation est une bijection 314 3142
[k] → A. Par nos théorèmes sur le dénombrement des fonctions, on a le 321 3214
comptage des arrangements : 324 3241
341 3412
? le nombre de k-arrangements avec répétitions est nk (Théorème 14.2), 342 3421
n! 412 4123
? le nombre de k-arrangements sans répétitions est (n−k)!
(Théorème 14.3), 413 4132
421 4213
? le nombre de permutations est (n!) (Corollaire 14.4).
423 4231
431 4312
432 4321
14.3 Principe d’addition
Le principe d’addition est la règle que la cardinalité d’ensembles disjoints
est additive.
Si on peut accomplir une tâche de n1 façons et une deuxième en n2
façons, et si on ne peut effectuer ces tâches simultanément, alors il y a
(n1 + n2 ) façons d’effectuer l’une ou l’autre de ces tâches.
t
[ t
|
A1 ∪ A2 ∪ · · · ∪ A t =
{z }
Aj = ∑ | A j |.
j =1 j =1
union d’ensembles disjoints
Principe de soustraction
Le principe de soustraction découle de l’addition. Le cas particulier de
Théorème 14.5 de t = 2 est le résultat que
| A ∪ B| = | A| + | B| si A ∩ B = ∅. (14.1)
Combinaisons
Une k-combinaison de k objets parmi n objets distincts est un choix
TABLE 14.3: k-combinaisons des éléments
non-ordonné de k éléments distincts de l’ensemble. Une k-combinaison {1, 2, 3, 4} sans répétitions. (Comparer avec
correspond à un sous-ensemble de taille k : on a autant de k-combinaisons les k-arrangements sans répétitions : il suffit
de trier les membres de l’arrangement pour
que des sous-ensembles de cardinalité k. On compte les k-combinaisons (non- obtenir la combinaison correspondante.)
ordonnées) par une application du principe de division avec le nombre de
k-permutations (ordonnés). k=1 k=2 k=3 k=4
1 12 123 1234
Théorème 14.7 (Dénombrement de combinaisons). Le nombre de combinaisons 2 13 124
3 14 134
quand 0 ≤ k ≤ n est égal à 4 23 234
24
n(n − 1)(n − 2) · · · (n − k + 1) n! n 34
C (n, k) = = =
k (k − 1)(k − 2) · · · 1 (n − k)! · k! k
Théorème 14.8 (Dénombrement de combinaisons avec répétitions). Le TABLE 14.4: k-combinaisons des élé-
ments {1, 2, 3, 4} avec répétitions. La
n+k−1 dernière colonne montre la bijection aux
nombre de combinaisons avec répétitions est égal à .
k 4-combinaisons sans répétitions parmi
{1, 2, . . . , 7} qu’on obtient par +1 dans la
2e, +2 dans la 3e et +3 dans la 4e colonne.
Démonstration. Sans perte de généralité, on compte les combinaisons de l’ensemble
A = {1, 2, . . . , n}. Une k-combinaison sans répétitions est alors une chaîne
k=1 k=2 k=3 k=4 C (7, 4)
a0 a1 · · · ak−1 avec 1 ≤ a0 < a1 < · · · < ak−1 ≤ n. Une k-combinaison avec 1 11 111 1111 1234
répétitions est une chaîne b0 b1 · · · bk−1 avec 1 ≤ b0 ≤ b1 ≤ · · · ≤ bk−1 ≤ n. On 2 12 112 1112 1235
définit la fonction suivante sur les combinaisons avec répétitions : 3 13 113 1113 1236
4 14 114 1114 1237
f (b0 · · · bk−1 ) = a0 · · · ak−1 avec ai = bi + i. 22 122 1122 1245
23 123 1123 1246
Par construction, l’image a0 · · · ak−1 alors admet 24 124 1124 1247
1 ≤ a0 < a1 < · · · < ak−1 ≤ n + (k − 1), donc f établit une fonction de 33 133 1133 1256
34 134 1134 1257
k-combinaisons avec répétitions parmi n éléments aux k-combinaisons sans répétitions
44 144 1144 1267
parmi n + (k − 1) éléments. La fonction est inversible, étant donné que pour tout 222 1222 1345
1 ≤ a0 < a1 < · · · < ak−1 ≤ n + (k − 1), on a 1 ≤ b0 ≤ b1 ≤ · · · ≤ bk−1 ≤ n si 223 1223 1346
bi = ai − i. Puisque f est une bijection (voir l’exemple dans Table 14.4), le nombre 224 1224 1347
de k combinaisons avec répétitions parmi n éléments est égal à C (n + k − 1, k). 233 1233 1356
234 1234 1357
244 1244 1367
333 1333 1456
334 1334 1457
344 1344 1467
444 1444 1567
2222 2345
2223 2346
2224 2347
2233 2356
2234 2357
2244 2367
2333 2456
2334 2457
2344 2467
2444 2567
3333 3456
3334 3457
3344 3467
3444 3567
4444 4567
136
= | A ∪ B| + |C | − ( A ∩ C ) ∪ ( B ∩ C ) par distributivité
= | A ∪ B| + |C | − | A ∩ C | + | B ∩ C | − ( A ∩ C ) ∪ ( B ∩ C )
= | A| + | B| − | A ∩ B| + |C | − | A ∩ C | − | B ∩ C | + | A ∩ B ∩ C |
Théorème 14.11. Soit { A1 , . . . , An } une séquence d’ensembles (non pas nécessairement disjoints). Alors
A 1 ∪ A 2 ∪ · · · ∪ A n = | A 1 | + · · · + | A n | − | A 1 ∩ A 2 | + · · · + | A n −1 ∩ A n | ± · · ·
n \ \
= ∑ (−1)t+1 ∑ Ai = ∑ (−1)| I |+1 Ai
t =1 | I |=t i ∈ I ∅6= I ⊆{1,...,n} i∈ I
| {z } | {z }
t-intersections tout ensemble d’indices I 6= ∅
Démonstration. (Omise.)
k k
k n t k−t k
∑ (−1) t (k − t) = ∑ (−1) tn
t =0 t =0
t
+ ∑ Fi ∩ Fj 2-intersections sous-comptés
0≤ i < j < k
Ainsi,
k k
|S| = kn + ∑ (−1)t ∑ ∩i∈ I Fi = kn + ∑ (−1)t ∑ (k − t)n sommer par t-intersections
t =1 | I |=t t =1 | I |=t
k k k
= k n − k · ( k − 1) n + ( k − 2) n − ( k − 3) n ± · · · choix si | I | = t
2 3 t
k
k
= ∑ (−1)t t
(k − t)n .
t =0
La somme étend jusqu’à t = k avec le terme (−1)k (kk)0n = 0n : la formule vaut pour n = 0 (il y aura une surjection car 00 = 1) et
pour 0 < n (terme sans effet car 0n = 0).
138
n ( k ) 0 si k < 0
(nk) = = ∏ k −1 ( n − i ) (14.4)
k! i =0 si 0 ≤ k
k!
La définition de (14.4) est valide aussi pour n < 0 (avec la factorielle décrois-
sante n(k) = 0), mais normalement on assume que 0 ≤ n. Si n ∈ N, alors
TABLE 14.6: Formule du binôme avec
n ≤ 5.
n 0 si k < 0 ou si n < k
= (14.5)
k n!
si 0 ≤ k ≤ n ( x + y)2 = x2 + 2xy + y2
k!(n−k )!
( x + y)3 = x3 + 3x2 y + 3xy2 + y3
Les coefficients binomiaux ont reçu leur nom de la formule du bi-
( x + y)4 = x4 + 4x3 y + 6x2 y2 + 4xy3 + y4
nôme 6 :
n ( x + y)5 = x5 + 5x4 y + 10x3 y2 + 10x2 y3 + 5xy5 + y5
n n k n−k
( x + y) = ∑ x y (14.6)
k =0
k
6. La formule est valide aussi avec un
exposant négatif, mais alors on a une série
La formule est valide dans tout domaine équipé avec des opérations d’ad- −n k
infinie : (1 + x )−n = ∑∞k =0 ( k ) x
dition, multiplication et exponentiation, donc non pas seulement pour x, y conjointement avec la définition générale des
réels, mais aussi pour nombres complexes, congruences modm, ou même coefficients binomiaux de (14.4).
(fr):formule du binôme.
polynômes, ou matrices carrées.
La formule de (14.6) vient du dénombrement des termes dans le dévelop-
pement 7 du produit de la puissance : 7. Exemple : ( x + y)3 = xxx + xxy +
x3 x2 y
n xyx + xyy + yxx + yxy + yyx + yyy
( x + y)n = ( x + y)( x + y) · · · ( x + y) = ∑ ck · x k yn−k , x2 y xy2 x2 y xy2 xy2 y3
| {z } k =0
n facteurs n
n-k
parce que les exposants dans les termes possibles x a yb
sont tous avec a + 1 1 1 1 1 1 1 1 1
1
n=
n n n−1 F IGURE 14.3: Représentation des co-
Une récurrence évidente dans (14.4) est = · pour
k k k−1 efficients binomiaux dans le triangle de
0 < n, k. La récurrence fondamentale des coefficients binomiaux est la Pascal. Après avoir initialisé les cellules
(n0 ) = (nn) = 1, on peut remplit les
relation de récurrence de Pascal (Figure 14.3). autres cellules par la récurrence de Pas-
1
cal de (14.7) : (n+ n n
k ) = ( k ) + (k −1), la
n+1 n n somme des deux voisins précédents dans la
= + (14.7) même rangée (même k), ou colonne (même
k k k−1
n − k = (n − 1) − (k − 1)). On obsèrve
aussi les identités de crosse de hockey :
avec les cas de base (n0 ) = (nn) = 1. On peut justifier la récurrence de (14.7)
k k+1 n n+1
par un argument sur le dénombrement de combinaisons. Une k-combinaison + +···+ =
k k k k+1
.
139
n
0 = (−1 + 1)n = ∑ (nk)(−1)k 1n−k = ∑ (2in ) − ∑ (2in+1)
k =0 0≤2i ≤n 0≤2i +1≤n
ou que la somme des coefficients binomiaux pairs est égal à la somme des
coefficients impairs. L’identité de Vandermonde est la formule que pour
tout 0 ≤ t ≤ n et 0 ≤ k ≤ n,
9. Argument pour pair-impair : créer
t
n t n−t appariement X ∪ {z}, X − {z} entre les
=∑ . (14.8) sous-ensembles X de taille paire ou impaire à
k i =0
i k−i
l’aide d’un membre z fixe («bit de parité»).
Argument pour Vandermonde : choisir k
Les preuves peuvent suivre un argument combinatoire 9 , induction avec la éléments parmi n éléments partitionnés en
récurrence de Pascal, ou la route algébrique avec la formule du binôme : gauche et droit est la même chose que
choisir i éléments parmi les t éléments à la
l’identité de Vandermonde (14.8) découle par la manipulation des sommes gauche et (k − i ) éléments parmi les (n − t)
dans ( x + 1)n = ( x + 1)t ( x + 1)n−t . éléments à la droite ; avec tout i = 0, . . . , t.
Coefficients multinomiaux
La formule du binôme se généralise à la formule du multinôme 10 10. :formule du multinôme
(fr)
n n
( x1 + x2 + . . . + x k ) = ∑ ( x 1 ) n1 ( x 2 ) n2 · · · ( x k ) n k
n1 +n2 +···+nk =n n1 , n2 , . . . , n k
k n k
avec les coefficients multinomiaux pour ∑i ni = n ( xi ) ni
∑ xi = n! ∑ ∏ ni !
i =1 ∑ik=1 ni =n i =1
n n!
= k .
n1 , n2 , . . . , n k ∏ i =1 ( n i ! )
TABLE 14.7: Dénombrement d’anagrammes
Dans le cas des coefficients binomiaux, on a k = 2 et n1 = k, n2 = n − k. par coefficients multinomiaux. Les ana-
On retrouve les coefficients multinomiaux (i) dans le dénombrement des grammes de banana sont des permutations
des lettres aaannb : on a (63) choix pour
anagrammes, des chaînes avec une composition donnée ni fois symbole ai pour la position des as, suivi par (32) choix pour
tout 1 ≤ i ≤ k ; ou (ii) dans le comptage de fonctions [n] → [k] si on fixe la placer les ns : (63)(32)(11) = (3 62 1).
taille des ensembles préimages par { x | f ( x ) = i } = f −1 (i ) = ni ; ou mot composition permutations
6!
(iii) dans le dénombrement de permutations d’un multi-ensemble. lollol 4l,2o 4!2! = 15
6!
banana 3a,2n,1b 3!2!1! = 60
6!
omgomg 2o,2m,2g 2!2!2! = 90
8!
piripiri 4i,2p,2r 4!2!2! = 420
12!
patatipatata 5a,4t,2p,1i 5!4!2!1! = 83 160
140
Le théorème suivant est un usage ancien 11 du principe des tiroirs. 11. Jean Leurechon. Selectæ Propositiones
in Tota Sparsim Mathematica Pulcher-
rimæ. Pont-á-Mousson, 1622.
Théorème 14.13. Il y a deux personnes dans le monde 12 qui ont le même nombre https:
//www.e-rara.ch/zut/content/zoom/3157025
(positif) de cheveux.
12. En fait, même dans l’arrondissement
Côte-des-Neiges–Notre-Dame-de-Grâce !
Démonstration. I Exercice.
Le principe des tiroirs est connu aussi sous le nom principe du pigeon-
nier (provenant de l’anglais pigeonhole principle), en un métaphore colombophile
(Figure 14.4).
Le principe des tiroirs est un outil non-constructif : on sait qu’il y a un
tiroir avec deux objets mais on ne sait pas lequel. Les deux théorèmes suivants
sont des applications fameuses du principe, menant à des preuves ultra-courtes.
Le premier théorème est un résultat important dans la théorie de nombres F IGURE 14.4: Deux pigeonniers sur une
qui montre l’existence d’approximations rationnelles de précision arbitraire ferme en Hongrie. Exercice : I dénombrer
les boulins. [Magyar Néprajzi Lexikon, 1982]
aux nombres irrationnelles. La preuve, basée sur le principe des tiroirs, a
manifesté 13 l’utilité de techniques combinatoires dans mathématiques diverses
qui, de prime abord, semblent rien à voir avec le le combinatoire. 13. À cause de prouver ainsi des variantes
de ce théorème, le principe des tiroirs est
Théorème 14.15 (Théorème de Dirichlet). Soit x ∈ R un nombre réel souvent éponyme avec Dirichlet («donc, par
le Schubladenprinzip de Dirichlet, . . . »).
quelconque. Pour tout entier positif n, il existe un nombre rationnel p/q ∈ Q t.q.
p 1 1
1 ≤ q ≤ n et x − q < nq ≤ q2
.
141
0.2
catégorie quand les sous-suites dans l’autre catégorie sont courtes (p.e., un dicté par la preuve.
suite presque triée) Mais est-il possible que toutes les sous-suites monotones
soient courtes ? Le théorème suivant l√affirmemque non : il y a toujours une
sous-suite monotone de longueur n − 1 . La preuve 14 est rapide avec le 14. A. Seidenberg. A simple proof of a theo-
principe des tiroirs. rem of Erdős and Szekeres. Journal of the Lon-
don Mathematical Society, 34:352, 1959. D O I :
10.1112/jlms/s1-34.3.352
Théorème 14.16 (Théorème d’Erdős-Szekeres). Soit A = ( a1 , a2 , . . . , an )
une suite de nombres réels distincts, et c, d des entiers positifs quelconques. Si cd < n, 17
15.1 Terminologie
(fr) :lexique sur la théorie de graphes
Dans un graphe simple, il n’y a pas de multiples arêtes entre les sommets,
ni boucles qui sont des arcs allant d’un sommet à lui-même. Les arêtes d’un
graphe simple sont des paires de sommets : si le graphe est orienté, les paires
sont ordonnées, ou si le graphe est non-orienté, les paires ne sont pas ordonnées
(donc c’est un ensemble de deux éléments plutôt qu’un couple). Un graphe
doté d’une ou plusieurs arêtes multiples ou de boucles est appelé multigraphe 1 . 1. Le terme pseudographe est utilisé parfois —
L’ordre du graphe G = (V, E) est le nombre de sommets |V |, et la taille c’est un graphe avec boucles mais non pas
des arêtes multiples.
de G est le nombre des arêtes | E|.
Définition 15.1 (Graphe orienté). Un graphe orienté (simple) est un
couple (V, E) constitué de l’ensemble de sommets ou nœuds 2 V, et l’ensemble 2. Je préfère utiliser nœud+arc pour graphe
d’arcs E. Les arcs sont des paires ordonnées E ⊆ V × V. orienté, et sommet+arête pour graphe non-
orienté, mais il n’y a pas de règle stricte sur la
Un multigraphe orienté est un triple (V, E, f ) de nœuds V, arcs E, et la terminologie.
fonction d’incidence f : E → V × V associant à chaque arc une paire de nœuds.
Les arcs e1 , e2 ∈ E sont des arcs multiples si f (e1 ) = f (e2 ).
Dans un graphe orienté G = (V, E), on dénote l’arc (u, v) ∈ E plus
simplement comme uv ∈ E. La source ou l’origine de l’arc uv est u, et son
cible ou l’extrémité est v. Noter que uv et vu sont des arcs différents. [Wikimédia]
uv = vu est la même arête. En général, «G est un graphe» veut dire que = {1, 2, 3, 4, 5, 6} et arêtes E =
V
{1, 2}, {1, 5}, {2, 5}, {2, 3}, {3, 4}, {4, 5}, {4, 6} .
G = (V, E) est un graphe simple non-orienté.
Il y a des notations standard pour des familles notables de graphes d’ordres
différents mais de structure similaire : v. Table 15.1.
144
arêtes entre V1 et V2 : E = V1 × V2
(n + 1) sommets V = {v0 , . . . , vn }, n
chemin (path) Pn
arêtes : E = {v0 v1 , v1 v2 , . . . , vn−1 vn }
Graphe non-orienté.
L’arête {u, v} ∈ E est dénotée par uv, sans importance à l’ordre : uv = vu. Si uv ∈ E, alors v est adjacent à u.
L’arête uv ∈ E est incidente au sommet u et aussi au sommet v. Deux arêtes sont adjacentes si elles sont incidentes à un
même sommet. Le degré de u ∈ V est le nombre d’arêtes qui y sont incidentes, dénoté par deg(u) ou d(u). La liste
de degrés est la suite croissante des degrés des nœuds :
Graphe orienté.
L’arc (u, v) ∈ E est dénotée par uv, et l’ordre est important : l’arc part de u et arrive à v. Si uv ∈ E ou vu ∈ E,
alors v est adjacent à u. Le degré sortant de u ∈ V est le nombre d’arcs qui y partent ; le degré rentrant est le
nombre d’arcs qui y arrivent.
145
? le complément d’un graphe G = (V, E) avec les arêtes qui ne sont pas 1 2 2
dans G :
5 5
G = V, E = V, {uv 6∈ E}
3 4 3 4
G G’
Poignées de main F IGURE 15.3: G 0 est le sous-graphe de G
engendré par les sommets {2, 3, 4, 5}.
Dans les preuves avec graphes, on peut
(i) argumenter par des principes de dénombrement (Chapitre 14) ; ou
(ii) employer induction structurale par décomposition en sous-graphes ou par
opérations sur graphes (p.e. enlever/ajouter des sommets ou des arêtes) ; ou
(iii) chercher des propriétés reliées dans le graphe.
Le Lemme des poignées de main est un exemple classique de relier de deux
propriétés de graphes : ici, la somme des degrés et le nombre d’arêtes.
146
Démonstration. Preuve 1 par compter. Chaque arête xy ∈ E est compté deux fois
dans les degrés : une fois dans d(u), et une fois dans d(v).
∑ d( x ) = ∑ ∑ 1 = ∑ ∑ ∑ 1 + ∑ ∑ 1 = ∑ 2 = 2m.
x ∈V x ∈V y| xy∈ E uv∈ E x =u y=v x =v y=u uv∈ E
Un autre résultat sur des degrés extrêmes dans (15.1) découle par le prin-
cipe des tiroirs (Eq. 14.9) : dans un graphe G = (V, E) avec n = |V |
sommets et m = | E| arêtes,
j 2m k l 2m m
δ( G ) ≤ et ∆( G ) ≥ .
n n
degré min. degré max.
Lemme 15.1 reste valide s’il y a des arêtes multiples dans le graphe, et
même s’il y a des boucles 3 , donc pour des multigraphes en général. On peut 3. À noter qu’une boucle uu contribue +2 au
aussi adapter les preuves aux graphes orientés sans aucune difficulté, en consi- degré d(u).
dérant la sommation des degrés 4 rentrants ou des degrés sortants : tous les 4. Une boucle uu ajoute +1 au degré sortant
deux sont égaux au nombre d’arêtes, v. Équation (15.3). et au degré rentrant de u.
Lemme 15.3 (Lemme des poignées de main pour graphe orienté). Soit
G = (V, E) un graphe orienté. Alors
∑ d+ (u) = ∑ d − ( u ) = | E |, (15.3)
u ∈V u ∈V
15.3 Chemins
Les chemins sont des suites d’arêtes adjacentes d’un sommet à un autre (ou
soi-même, avec un chemin de longueur 0). Deux sommets sont connexes s’il
y un chemin entre eux, et le graphe est connexe si toutes paires de sommets
sont connexes.
Définition 15.6. Un chemin simple ( trail en anglais) est un chemin avec arêtes
distinctes. Un chemin élémentaire (simple path) est un chemin avec sommets 6 6. Un chemin élémentaire est forcément
distincts. simple car si on ne répète aucun sommet, on
ne répète aucune arête non plus.
Il n’y a pas de différence entre chemins au sens général et chemins élémen-
taires pour connexité : si on a un s − t chemin avec sommets répétés, alors
ils forment des cycles redondants au long du chemin qu’on peut éliminer, et
obtenir un s − t chemin élémentaire. La preuve du lemme suivant formalise
cet argument à l’aide du bon ordre 7 par longueur. 7. Une démarche alternative est par induction
généralisée dans la longueur du chemin :
Lemme 15.4. Soit G = (V, E) un graphe non-orienté. Si les sommets s, t ∈ V dans l’étape inductive, on enlève un cycle
redondant, et il y a un chemin simple pour
sont connexes, alors il existe un chemin élémentaire 8 entre eux. ce qui reste par l’hypothèse d’induction.
8. [RosenFR] donne ce théorème (7.4,
Démonstration. Puisque s et t communiquent, il existe un s − t
Théorème 1) pour l’existence d’un chemin
chemin P = x0 . . . x` de x0 = s à x` = t. On montre que si P ne contient simple mais avec cette même preuve pour
pas (` + 1) sommets distincts, alors il n’est pas de longueur minimale. Supposons chemin élémentaire. Erreur de traduction, sans
que P visite le même sommet deux fois : xi = x j avec i < j. Alors, le chemin doute («there exists a simple path») !
P0 = x0 · · · xi x j+1 · · · x` est de longueur ` − ( j − i ) < `.
En conséquence, le chemin de longueur minimale de s à t est élémentaire.
148
Théorème 15.5. Le graphe G = (V, E) est biparti ssi on peut colorier les
sommets par une fonction c : V → {1, 2} de sorte que si uv ∈ E, alors c(u) 6=
c ( v ).
V
* * * *
F IGURE 15.5: Un couplage avec 5 arêtes
(coloriées), et une couverture par 10 som-
Définition 15.9. Une couverture par sommets (vertex cover) est un en- mets (coloriés). Les nœuds marqués * sont
semble de sommets C ∈ U ∪ V t.q. pour chaque arête xy ∈ E, x ∈ C ou y ∈ C. exposés. (On peut faire mieux, avec un
couplage de taille 9.)
Théorème de Kőnig
Théorème 15.6 (Dénes Kőnig 1931). Dans tout graphe biparti, la taille maxi-
male d’un couplage est égale à la taille minimale d’une couverture par sommets.
149
Ensembles défectueux
On définit le voisinage d’un ensemble de sommets X ⊆ U :
Matrices 0-1
Définition 15.10. Une matrice ne comportant que des éléments de valeur 0 eou 1
dans les cellules est une matrice 0-1 (ou matrice booléenne).
Théorème de Cantor-Schröder-Bernstein
On compare la cardinalité de deux ensembles U, V par des couplages définis
par fonctions f : U → V.
Maintenant, = est une relation d’équivalence 9 entre cardinalités. La rela- 9. Réflexive car la fonction d’identité est une
tion ≤ est clairement réflexive et transitive, mais son anti-symétrie ne découle bijection ; symétrique car l’inverse d’une
bijection est une bijection (Théorème 6.4),
pas immédiatement quand les ensembles U, V sont infinis. Heureusement, la et transitive car la composition de bijections
méthode de chemins alternants peut être utilisée pour couplage même dans un est une bijection (Théorème 6.7).
graphe infini, notamment pour construire une bijection entre deux ensembles
à partir de deux injections entre eux.
16.1 Isomorphisme
Une application entre graphes établit une association entre les sommets de
deux graphes. Une telle fonction est un morphisme si elle préserve adjacence :
les sommets adjacents ont des images adjacents. Si sa réciproque est aussi un
morphisme, la fonction est un isomorphisme 1 . S’il existe un isomorphisme
F IGURE 16.1: Morphisme du snark fleur J5
entre deux graphes, les deux graphes sont isomorphes, ou simplement, ils sont le au cycle C5 . Ici, on morphe le fleur dans le
même. cycle, en projettant les sommets du premier
dans ceux du deuxième, sans briser les liens.
Définition 16.1 (Morphisme et isomorphisme de graphes). Soit G = 1. Un isomorphisme est nécessairement une
bijection, mais pas toutes les bijections sont
(VG , EG ) et H = (VH , EH ) deux graphes. des isomorphismes. Une bijection entre
(i) Une fonction f : VG → VH est un morphisme (homomorphism en englais) si les sommets montre que les deux graphes
ont le même nombre de sommets, mais les
pour toute paire de sommets (u, v) ∈ VG2 , images ne préservent pas automatiquement
l’adjacence.
uv ∈ EG → f (u) f (v) ∈ EH
α β
C3 G
(ii) Une fonction f : VG → VH est un isomorphisme s’il est un morphisme et
sa réciproque f −1 est aussi un morphisme : pour toute paire de sommets (u, v) ∈ c γ δ
VG2 , 2
uv ∈ EG ↔ f (u) f (v) ∈ EH
H 1
3
Deux graphes sont isomorphes s’il existe une isomorphisme entre eux.
F IGURE 16.2: (Homo)morphisme et
Un morphisme n’est pas nécessairement une injection : il est possible qu’on isomorphisme. Le graphe H avec sommets
{1, 2, 3} et arêtes {1, 2}, {2, 3}, {3, 1}
a une arête uv t.q. f ( x ) = f (y) = u et f (z) = v quand y est un sommet de
est isomorphe à C3 = K3 . On peut trouver
degré 2 avec arêtes xy et yz (v. un exemple dans Fig. 16.2). un morphisme du graphe G avec sommets
Isomorphisme est une relation d’équivalence : il est réflexive (car identité {α, β, γ, δ} à C3 . G est isomorphe au graphe
cycle C4 .
est un isomorphisme sur soi-même), symétrique (car il est défini par un mor-
phisme dont le réciproque est aussi un morphisme), et transitive (car la com-
position de isomorphisme est un isomorphisme). Il est un problème difficile
de déterminer si deux graphes sont isomorphes. En comparant leurs matrices
d’adjacence, on doit trouver une bijection entre les ordres de rangées (et co-
lonnes), donc un réarrangement d’une matrice qui donne l’autre matrice. Une
154
propriété de graphes qui est préservée sous tout isomorphisme est appelé une
propriété invariante. Il y a beaucoup de propriétés invariantes : nombre de
sommets et des arêtes (ordre et taille) ; séquence de degrés ; présence, absence
ou nombre de sous-graphes isomorphes à un graphe donné : p.e., graphe sans
triangles ou graphe acyclique ; et beaucoup d’autres.
Un automorphisme est un isomorphisme du graphe avec soi-même.
À part d’identité (qui est un automorphisme pour tout graphe) le graphe
doit avoir des symétries pour d’autres automorphismes. Il y en a 384 pour
l’hypercube Q4 , par exemple (Figure 16.3).
On obtient T donc par multiplication 2 matricielle : 2. Ou, si S, R, T sont des matrices de valeurs
logiques,
0 _
si T0xz = 0 T xz ≡ S xy ∧ Ryz ,
T0 = S · R}
| {z et ∀ x : ∀z : T xz = min 1, T0xz = y ∈Y
1 si T0xz > 0
produit de 2 matrices et on peut même écrire T ≡ S ∧ R après
avoir défini la conjonction matricielle
comme l’analogue de multiplication
16.3 Connexité matricielle par ∧ (au lieu de multiplication)
et ∨ (au lieu d’addition).
Définition 16.4 (Sommets connexes). On dit que deux sommets s, t commu- Notre notation R ◦ S («R après S») reste
niquent ou sont reliés ou sont connexes, s’il existe un chemin entre eux. Un tel avec Rosen et d’autres manuels en
informatique, sans différence entre
chemin est un s − t chemin. composition de fonctions et celle de
relations :
Composantes connexes ( x, z) ∈ R ◦ S ↔ ∃y : ( x, y) ∈ S ∧ (y, z) ∈ R.
Un graphe G = (U, V ) est connexe s’il existe un chemin entre toute D’autres manuels, surtout en mathématiques
paire de sommets (Définition 13.5). Si G n’est pas connexe, alors il peut être peuvent utiliser l’ordre SR ou S; R pour
dénoter la composition de relations, en tant
décomposé dans des sous-graphes connexes. que «multiplication de relations», étant
donné la correspondance à la multiplication
Définition 16.5. Une composante connexe d’un graphe G est un sous-graphe matricielle. En même temps, l’ordre
connexe maximal de G. ( g ◦ f )( x ) = g( f ( x )) est une notation
universelle pour composition de fonctions.
Soit G = (V, E) un graphe. La connexité entre les sommets de G est une relation binaire. On peut même introduire un
opérateur pour notation infixée : x y si x et y communiquent, ou dans d’autres mots, s’il existe un x − y chemin
dans le graphe. Avec une définition récursive :
En Equation (16.1b), on se sert de la structure récursive des chemins : s’il existe un x − z chemin P = x0 · · · x` avec
x0 = x et z = x` , et une arête zy, alors P0 = x0 · · · x` y est un x − y chemin. La connexité est une relation
d’équivalence dans un graphe non-orienté : il est réflexive (x x), symétrique (x y → y x), et transitive (x y ∧
y z → x z). Les classes d’équivalence (Théorème 11.6) selon sont les composantes connexes de G.
Coupures point
d’articulation
Dans beaucoup d’applications, il est intéressant de caractériser la robustesse pont
✂
✂
d’un réseau : la faille de quels liens ou nœuds brise la connexité. Soit G =
(V, E) un graphe non-orienté. avec Γ(u) = {uv|v ∈ V ∧ uv ∈ E}, les
voisins de u.
Un pont (ou isthmus) est une arête uv dont le retrait «brise» le graphe :
ceci n’est pas un pont
G − uv a plus de composantes connexes que G. Un point d’articulation
F IGURE 16.6: Il y a un pont et trois points
est un sommet u dont le retrait produit le graphe G − u avec plus de compo- d’articulation dans ce graphe comportant
santes connexes que G. Notons que les extrémités d’un pont sont des points trois composantes biconnexes.
d’articulation mais un point d’articulation n’est pas nécessairement incident
à un pont (Figure 16.6). Un sous-graphe G 0 de G qui ne contient aucun
point d’articulation (dans G 0 ) est dit biconnexe. Les sous-graphes biconnexes
maximaux de G sont ses composantes biconnexes.
156
On peut calculer les arêtes de G ∗ par l’induction de l’Équation 16.1. On définit les prédicats C` pour ` = 0, 1, 2, . . . :
C` ( x, y) ≡ il existe un x − y chemin de longueur ` ce qui est une relation binaire entre sommets. Alors :
Dénombrement de chemins
En notant que A0 = I, la matrice d’identité 3 , et que l’exponentiation matri- 3. La matrice d’identité I est la natrice avec 1
cielle est définie par la même récurrence 4 , on a sur la diagonale et 0 ailleurs : I xy = 1 si
x = y, et I xy = 0 si x 6= y.
4. Exponentiation matricielle est définie par
` multiplication matricielle :
M(`) = ∏ A = A` `
k =1 A`+1 = ∏ A = A` · A si ` ≥ 0
k =1
Dans la théorie des graphes, les arbres 1 sont les structures les plus simples : 1. Plus spécifiquement, il s’agit d’un arbre
ils ont le moindre nombre d’arêtes pour rester connexe. Connexité est établie libre, pour ne pas confondre avec l’usage de
l’arbre enraciné en informatique, qui dénote
par des sous-graphes chemins (Fig. 17.2) qui sont des instances d’arbres eux- une structure récursive, ou un graphe orienté
mêmes. Figure 17.1 montre tous les arbres avec 6 sommets au plus. (nommé arborescence en théorie des graphes).
Définition 17.2 (Forêt et arbre). (i) Un graphe sans cycle est dit acyclique.
(ii) Une forêt est un graphe acyclique.
(iii) Un arbre (libre) est une forêt connexe.
160
P = x0 · · · x k et P 0 = y0 · · · y ` , x0 = y0 = u, xk = y` = v
Un arbre contient assez d’arêtes pour être connexe, mais non pas trop pour
inclure un cycle : il est un graphe extrême pour les deux propriétés.
Preuve de Théorème 17.4. (V. Table 17.2.) a ∧ c → b : par Lemmes 17.6 et 17.7.
b ∧ c → a : par Lemme 17.7 et Théorème 17.3. b ∧ a → c : par Lemme 17.6 et
Théorème 17.3.
Définition 17.4. Un arbre ordonné T est un arbre enraciné dans lequel les en-
fants sont ordonnés ou numérotés 5 . Un arbre ordonné est donc soit un nœud externe, 5. La numérotation définit un système d’adres-
soit un nœud interne r avec enfants T1 , . . . , Td , où la racine de Ti est appelée le i-ème sage universel pour ses nœuds : l’adresse du
nœud u est la chaîne des indices des enfants
enfant de r. visités sur le chemin de la racine à u.
Définition 17.5. Le degré (ou arité) d’un nœud est le nombre de ses enfants : les
nœuds externes sont de degré 0. Le degré de l’arbre est le degré maximal de ses nœuds.
Un arbre d-aire est un arbre ordonné où chaque nœud interne possède exactement d
enfants. En particulier, un arbre binaire 6 est un arbre numeroté où chaque nœud 6. :arbre binaire
(fr)
Dans un arbre binaire, les feuilles sont les nœuds internes avec deux en-
fants externes. Les feuilles d’un arbre binaire complet de hauteur h sont au
niveau (h − 1) ou (h − 2).
RosenFR utilise une traduction erronée (arbre «équilibré» pour arbre complet) et une terminologie confuse.
terme correct signification RosenFR RosenEN
arbre m-aire m enfants à tout nœud interne arbre m-aire complet full m-ary tree
(arbre dégéneré) ≤ m enfants à tout nœud arbre m-aire
arbre binaire (parfait/full) arité = 2 arbre binaire complet full binary tree
arbre binaire complet (complete) externes aux plus bas ≤ 2 niveaux arbre binaire équilibré balanced binary tree
arbre binaire équilibré (balanced) hauteur logarithmique
(nœud) interne > 0 enfants (sommet) interne internal (vertex)
nœud externe 0 enfants feuille leaf
feuille (leaf) 2 enfants externes
Implémentations informatiques
Dans une structure de données, on veut retrouver facilement soit le parent,
soit les enfants, soit les deux à tout nœud, selon les demandes de l’application.
Dans une telle structure, les nœuds externes ne portent pas de données, et on
les représente simplement par des liens null 7 . Ainsi, un nœud interne x dans 7. Si on ignore les nœuds externes, on ob-
un arbre binaire contient deux variables (p.e, x.left et x.right) pour ses enfants tient un arbre d’arité variable sur les nœuds
internes de l’arbre original, dans lequel un
gauche et droit, et/ou une variable x.parent pour son parent. Dans les arbres nœud peut avoir un enfant gauche, un enfant
de recherche employés pour indexer les bases de données, les enfants externes droit, deux enfants, ou aucun enfant. C’est la
notion de l’«arbre binaire» (et non pas «arbre
aux feuilles sont les entrées dans le fichier sur stockage externe, tandis que les binaire parfait») assumé par Rosen, et dans
nœuds internes sont dans le mémoire vive pour rapide recherche. quelques autres ouvrages.
165
17.4 Parcours
Un parcours visite tous les nœuds de l’arbre. Lors d’un parcours préfixe
(ou parcours preordre, preorder traversal), chaque nœud est visité avant que ses
enfants soient visités. On calcule ainsi des propriétés avec récurrence vers le
parent comme la profondeur (17.1). Dans un parcours postfixe (ou parcours
postordre, postorder traversal), chaque nœud est visité après que ses enfants sont
visités. On calcule ainsi des propriétés avec récurrence vers les enfants comme
la hauteur (17.2) Voir Figures 17.7 et 17.8 pour le pseudocode.
F : : = a | ¬F | F ∧ F | F ∨ F | F → F (17.3)
F::=D | D → F p → q → r ≡ p → (q → r )
D::=C | D ∨C p ∨ q ∨ r ≡ ( p ∨ q) ∨ r
C::= L | C ∧ L p ∧ q ∧ r ≡ ( p ∧ q) ∧ r
L : : = a | ¬ L | ( F) parenthèses pour changer priorité
Une opération x op y est écrite en notation polonaise inverse 10 (reverse 10. :notations postfixe, infixe et préfixe
(fr)
Liaison de variables →
y z x y
tion
? récurrences et diviser-pour-régner .. (fr):machine de Turing, (fr):machine
Les cardinaux sont des nombres qui représentent la cardinalité des en-
sembles. Les cardinaux finis sont les nombres naturels (=taille d’un ensemble).
Les cardinaux infinis sont des nombres transfinis, avec des règles d’arithmétique
particulières 3 . 3. « Il est la source de beaucoup de troubles quand
on prend des principes déduits à partir des
expériences avec le fini, et on essaye de les forcer
L’infini dénombrable : ℵ0 sur l’infini. L’infini se secoue et s’en échappe. »
[Rózsa Péter]
La plus petite cardinalité infinie est celle de tous les entiers naturels, dé- Aleph ℵ est la première lettre de l’alpha-
notée par ℵ0 = |N| («aleph-zéro»). Un ensemble infini dénombrable bet hébreu (et d’autres alphabets sémitiques).
172
...
Preuve avec couplage de Cantor. On démontre que le théorème avec une bi-
9 ...
jection C : N2 → N, le couplage de Cantor. On arrive à la fonction par
y 5 8 ...
l’énumération des couples ( x, y) ∈ N × N par antidiagonales :
2 4 7 ...
(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (3, 0), (2, 1), (1, 2), (0, 3), . . .
| {z } | {z } | {z } 0 1 3 6 ...
x + y =1 x + y =2 x + y =3
x
Cela donne, avec les nombres triangulaires (Théorème 8.6) F IGURE 42.3: Couplage de Cantor. L’énu-
mération des couples ( x, y) par antidiago-
( x +y)−1
( x + y + 1)( x + y) ( x +y)2 + x +3y nales définit une bijection, ou couplage,
C ( x, y) = ∑ ( d + 1) + y =
2
+y = 2 . entre N2 et N.
d =0
173
Pour l’inversion du couplage de Cantor, supposons que c ∈ N, et on veut trouver tels ( x, y) que C ( x, y) = c. On écrit
d = x + y, et alors on cherche d entier (l’antidiagonale) tel que
√
d ( d + 1) (d + 1)(d + 2) 8c + 1 − 1
≤c< alors d= ,
2 2 2
et on a y = C − d(d + 1)/2 et x = d − y. Exemples pour couplage Cantor :
Par Théorème 42.1, les nombres rationnels sont énumérables, par l’in- C (2, 1) = (32 + 2 + 3)/2 = 7
jection facile p/q 7→ ( p, q). On peut répéter les astuces de dénombrer les √
C −1 (9) = d = b( 73 − 1)/2c = 3
couples (=2-tuples) pour dénombrer tous les tuples d’entiers, ou toutes les
y = 9−6 = 3
chaînes finies sur un alphabet dénombrable.
x = 3−3 = 0
Théorème 42.2. L’ensemble de toutes les suites finies d’entiers naturels est énumé-
rable : N∗ = ℵ0 . avec N∗ = ∪∞
`=0 N .
`
i =1
et c’est une bijection f : N∗ → N+ . (Elle est difficile d’inverser.)
(Preuve 2 avec couplage de Cantor) On définit une bijection N∗ → N par
récurrence.
Corollaire 42.4. (i) Les prédicats sur les entiers naturels ne sont pas énumé-
rables. (ii) Les chaînes binaires infinies ne sont pas énumérables. (iii) Les fonc-
tions N → {0, 1} ne sont pas énumérables.
Théorème 42.5. Il existe un prédicat sur les nombres naturels qui n’est calculé par
aucun programme.
En fait, presque tous 12 les prédicats sont incalculables. Soit P l’ensemble 12. La notion de «presque tout» applique à un
de tous les prédicats. Si A dénote les prédicats qu’on pourrait calculer par un ensemble infini A. Si un
sous-ensemble B ⊆ A est de cardinalité
algorithmes, alors | A| = ℵ0 , mais l’ensemble des prédicats qui sont impossibles strictement inférieure | B| < | A|, alos
à calculer est de même taille que l’atout : | P − A| = | P| = c. presque tout x ∈ A est x 6∈ B.
L’ordinateur exécute un programme décrit dans le code source. La ma-
chine RAM est basée sur la même notion : on peut stocker le programme
dans le mémoire, encodé en bits et octets. Pour tout modèle formel de cal-
cul, on a une bijection entre les nombres naturels et les algorithmes possibles,
donc un prédicat sur les entiers naturels est en même temps un prédicat sur les
programmes possibles. Le programme se décrit en une chaîne finie, mais son
exécution ne s’arrête pas nécessairement — on peut écrire le code pour une
boucle infinie, par exemple. Les prédicats qu’on ne peut pas calculer incluent
tout aspect de l’exécution du code, comme le problème d’arrêt : est-ce que
l’exécution se termine en un temps fini ? La diagonalisation pour un prédi-
cat P sur les programmes correspond à la construction de l’algorithme D ( x )
qui calcule P( x ) et fait le contraire. Alors D ( D ) donne une contradiction 13 13. Par exemple, D se termine si P( D ), ou
car on doit calculer P( D ) à partir du code source. il se met dans une boucle infinie si ¬ P( D )
est une contradiction quand P( D ) est «D se
Un énoncé est indécidable 14 s’il est impossible de démontrer qu’il soit vrai termine»
ou qu’il soit faux. Un tel problème est adressé par l’hypothèse du continu : 14. Indécidable : aucune preuve pour montrer
si l’énoncé logique est vrai ou faux. On peut
l’existence de cardinaux infinis entre le dénombrable ℵ0 et le continu c = 2ℵ0 décider si un énoncé (fini) est tautologie ou
ne peut pas être décidée. Si on veut, on peut l’assumer sans contradiction contradiction dans logique propositionnelle
avec la reste de la théorie des ensembles, ou si on préfère, on peut assumer (Définition 1.2), ou calculer sa valeur pour
une affectation particulière sans problème
l’hypothèse 2ℵ0 = ℵ1 . (en principe, au moins, sans regard au temps
On trouve l’analogue d’incalculabilité dans toute approche formelle, requis). Par contre, la vérité de formules
logiques quantifiées dans le domaine des en-
énoncé par le théorème d’incomplétude de Gödel : si un système formel tiers ne peut pas être déterminée par aucun
d’inférence est assez puissant pour exprimer l’arithmétique des entiers, alors algorithme, sauf la validité du syntaxe. Un
soit il y a des énoncés logiques qui sont indécidables soit le système est incon- algorithme (absurde) qui calcule la vérité de
la formule correspond à une preuve directe
sistant, et tout peut être «démontré». La diagonalisation se fait en encodant les (v. Notes de cours §4.1). Mais même si on
énoncés et les démonstrations formelles par entiers naturels. P.e., dans déduc- permet des preuves indirectes (admettant la
loi du milieu exclu), presque tout énoncé est
tion naturelle on peut énumérer les règles d’inférence (Notes de cours §3.3), impossible à prouver. En conséquence, il est
et numéroter les propositions, avec un syntaxe pour imbrication des preuves également impossible à décider si une théorie
conditionnelles et la liaison des variables. Par exemple, avec la théorie axio- est satisfaisable (Notes de cours §2.7).
Théorème 42.6 (Gödel, 1931). Un système formel qui est consistant, et assez
puissant d’exprimer l’arithmétique entière ne peut pas être complet.
2.1 Un prédicat P scinde l’univers en deux : les P et les non-P. Il est impossible
d’avoir un élément x avec P( x ) faux et vrai en même temps (principe de non-
contradiction), et il est également impossible d’avoir un élément x pour le-
quel P( x ) n’est ni vrai ni faux (principe du tiers exclu). 17
2.2 Imbrication et liaison de variables. La formule exprime qu’il y a exactement
un élément x qui satisfait le prédicat P. 19
2.3 f ( x ) tend à L quand x tend à c. 20
9.1 Une liste est soit une liste null (un seul nœud externe), soit un couple formé
par un nœud interne (la tête) et d’une autre liste (la queue). 83
178
9.2 Un arbre enraciné est soit un arbre null (nœud externe), ou il est composé
d’un nœud interne (la racine) et un ensemble d’arbres enracinés (les enfants). 83
9.3 Arbres binaires avec n ≤ 3 nœuds internes et m ≤ 4 nœuds externes 86
9.4 Les axiomes de base dans Formulario mathematico, 1908. Écrit en latino sine
flexione, une langue inventée par Peano. Axiome 0 déclare que N (dénoté
par N0 ici) est un ensemble. Le symbol ⊃ signifie implication matérielle →. 87
11.1 Ordre parmi les diviseurs positifs de 60, illustré par un diagramme de Hasse.
Dans un tel diagramme, le placement vertical des éléments donne le sens de
la relation entre des membres reliés, et on ne montre pas les relations impli-
quées par réflexivité et transitivité. 94
11.2 Portrait de Carl Friedrich G AUSS (1777–1855), l’un des plus grands mathé-
maticiens de tous les temps, à l’age de 63, par Christian Albrecht Jensen. Gauss
a inventé l’arithmétique modulaire par congruences, et a été le premier à dé-
montrer proprement le théorème fondamental de l’arithmétique sur l’uni-
cité de la décomposition en facteurs premiers. 102
42.1 Ouroboros, ou le serpent qui se mord la queue, est un ancien symbol mystique
d’éternité, ou l’infini par induction. [Illustration dans un manuscrit enluminé
par le copiste Théodore Pélécanos de Crète, 1478] 171
42.2 Fusion de deux énumérations. 172
42.3 Couplage de Cantor. L’énumération des couples ( x, y) par antidiagonales dé-
finit une bijection, ou couplage, entre N2 et N. 172
Liste des tableaux
1.1 Constantes logiques et variantes de notation 11
1.2 Table de vérité pour les opérateurs logiques de base. 11
1.3 Implication logique. Le conditionnel p → q est vrai quand p est faux ou q
est vrai. 12
1.4 Table de vérité pour OU exclusif et des formules équivalentes avec négation,
conjonction et disjonction. 12
1.5 Ordre et notation des opérations logiques de base. La dernière colonne montre
des variations communes de notation. 13
1.6 Équivalences logiques. 13
1.7 Équivalences logiques avec propositions conditionnelles 13
1.8 Théorie pour un modèle simple de météo 15
1.9 Terminologie pour formes normales 16
1.10 Table de vérité pour incrémenter un compteur sur trois bits abc + 1 =
de f . 16
3.1 Table de vérité pour l’exemple de Jeanne et Jean, avec les deux rangées où
deux prémisses, p et ¬r, sont vraies. 23
3.2 Quelques lettres grècques. 24
3.3 Règles d’inférence dans calcul des propositions 25
3.4 Règles de base dans déduction naturelle. 27
3.5 Preuve de ¬ p ∨ q ` p → q et de p → q ` ¬ p ∨ q. 27
3.6 Règles d’introduction et d’élimination pour ↔. 28
3.7 Règles dérivées dans déduction naturelle. 28
3.8 Règles d’introduction et élimination de quantificateurs. Dans toute les for-
mules, t est un terme et y est une nouvelle variable ajoutée à Γ. 29
3.9 Preuve altérnative pour «il n’y a pas de plus grand nombre naturel» 30
3.10 Régles de proposition logique dérivées dans déduction naturelle. 31
3.11 Systèmes formels en informatique 32
12.1 Algorithme pour maximum de n éléments. Noter que cette version on com-
mence les membres avec l’indice 1. 107
12.2 Algorithme pour minimum de n éléments. Noter que cette version on com-
mence les membres avec l’indice 1. 108
12.3 Tri par sélection. 109
12.4 Trace d’exécution du tri par sélection sur {1, 0, 6, 5} avec n = 4. L’élément
encadré est celui choisi par m. 109
12.5 Tri par insertion. 110
12.6 Trace d’exécution du tri par insertion sur {1, 0, 9, 7, 2} avec n = 5. L’élé-
ment encadré est x j+1 qui est inséré dans sa place par la boucle while sur j. 110
12.7 Définition et calcul de la factorielle 111
12.8 Nombres Fibonacci par programmation dynamique et deux variables auxi-
liaires. 113