CoursMathsDis PDF
CoursMathsDis PDF
CoursMathsDis PDF
Christophe GUYEUX
guyeux@iut-bm.univ-fcomte.fr
21 avril 2008
Table des matieres
1
3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Elements maximaux . . . . . . . . . . . . . . . . . . . . . . 37
5 Treillis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
V. Relations dequivalence . . . . . . . . . . . . . . . . . . . . . . . . . 41
1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2 Classes dequivalence . . . . . . . . . . . . . . . . . . . . . 42
3 Ensemble-quotient . . . . . . . . . . . . . . . . . . . . . . . 44
4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
VI. Compatibilite entre une operation et une relation binaire . . . . . . . 46
3 Relations n-aires 48
I. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1 Relations orientees et non orientees . . . . . . . . . . . . . . 48
2 Relations equivalentes, relations egales . . . . . . . . . . . . 50
3 Interpretation fonctionnelle . . . . . . . . . . . . . . . . . . . 51
4 SGBD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
II. Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2 Theoreme des projections . . . . . . . . . . . . . . . . . . . 52
III. Operations sur les relations n-aires . . . . . . . . . . . . . . . . . . . 52
1 Somme et produit . . . . . . . . . . . . . . . . . . . . . . . . 52
2 Reunion et intersection . . . . . . . . . . . . . . . . . . . . . 53
3 Produit cartesien . . . . . . . . . . . . . . . . . . . . . . . . 53
IV. Selection dune relation n-aire . . . . . . . . . . . . . . . . . . . . . 53
V. Dependances fonctionnelles et cles . . . . . . . . . . . . . . . . . . . 54
1 Dependances fonctionnelles . . . . . . . . . . . . . . . . . . 54
2 Theoreme des dependances fonctionnelles . . . . . . . . . . . 55
3 Cles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
II Arithmetique 57
2
4 Division (( entiere )) informatique et division euclidienne . . . 70
5 Arithmetique modulo 2n dans les ordinateurs . . . . . . . . . 71
III. Algorithmes dEuclide et applications . . . . . . . . . . . . . . . . . 75
1 PGCD de deux entiers . . . . . . . . . . . . . . . . . . . . . 75
2 Algorithme dEuclide . . . . . . . . . . . . . . . . . . . . . . 75
3 Theoreme de Bezout . . . . . . . . . . . . . . . . . . . . . . 77
4 Algorithme dEuclide generalise . . . . . . . . . . . . . . . . 78
6 Cryptologie et arithmetique 90
I. Methodes de cryptage (( a cle publique )) . . . . . . . . . . . . . . . . 90
1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
2 Utilisation de lindicatrice dEuler . . . . . . . . . . . . . . . 91
II. Choix dun nombre n . . . . . . . . . . . . . . . . . . . . . . . . . . 93
1 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . 93
2 Decomposition en facteurs premiers . . . . . . . . . . . . . . 94
7 Tests de primalite 95
I. Theoreme de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . 95
II. Test de Miller-Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . 96
III. Tests de Lucas, Selfridge et Pocklington . . . . . . . . . . . . . . . . 96
3
III Logique 105
4
7 Technique de lhypothese supplementaire . . . . . . . . . . . 173
8 Methodes de demonstration . . . . . . . . . . . . . . . . . . 175
9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
10 Tableaux de Beth . . . . . . . . . . . . . . . . . . . . . . . . 179
V. Completude du calcul propositionnel . . . . . . . . . . . . . . . . . . 180
1 Theoreme de completude . . . . . . . . . . . . . . . . . . . . 180
2 Theoreme de completude generalise . . . . . . . . . . . . . . 184
5
12 Algorithme de resolution 211
I. Resolution sans variables . . . . . . . . . . . . . . . . . . . . . . . . 211
1 Cadre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
2 Le systeme formel RSV . . . . . . . . . . . . . . . . . . . . 211
3 Principes generaux . . . . . . . . . . . . . . . . . . . . . . . 211
4 Le systeme formel RSV . . . . . . . . . . . . . . . . . . . . 211
5 Quelques indications sur les algorithmes de resolution . . . . 212
6 Exemples complets de resolution . . . . . . . . . . . . . . . . 215
7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
II. Resolution avec variable . . . . . . . . . . . . . . . . . . . . . . . . 220
1 Unification . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
2 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
3 Strategie de resolution . . . . . . . . . . . . . . . . . . . . . 224
4 Exemples complets de resolution . . . . . . . . . . . . . . . . 225
5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
III. Clauses de Horn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
2 Deduction ordonnee . . . . . . . . . . . . . . . . . . . . . . 229
3 Le resultat evoque dans le paragraphe precedent . . . . . . . 229
6
15 Introduction aux expressions rationnelles 242
I. Presentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
II. Regles de definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
III. Proprietes des operateurs . . . . . . . . . . . . . . . . . . . . . . . . 244
IV. De nouvelles abreviations . . . . . . . . . . . . . . . . . . . . . . . . 245
V. Universalite des expressions rationnelles . . . . . . . . . . . . . . . . 245
7
18 Construction dautomates finis a partir dexpressions rationnelles 276
I. Automates a transitions instantanees . . . . . . . . . . . . . . . . . . 276
II. Donnees et resultat . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
III. Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
IV. Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
V. Finalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
8
3 Graphes connexes . . . . . . . . . . . . . . . . . . . . . . . 304
4 Graphes complets . . . . . . . . . . . . . . . . . . . . . . . . 304
5 Graphes biparti . . . . . . . . . . . . . . . . . . . . . . . . . 305
6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
III. Representation des graphes . . . . . . . . . . . . . . . . . . . . . . . 307
1 Matrice dincidence . . . . . . . . . . . . . . . . . . . . . . 307
2 Matrice dadjacence . . . . . . . . . . . . . . . . . . . . . . 308
3 Listes dadjacence . . . . . . . . . . . . . . . . . . . . . . . 310
9
1 Definitions et exemples . . . . . . . . . . . . . . . . . . . . . 340
2 Arborescences ordonnees . . . . . . . . . . . . . . . . . . . . 341
3 Codage de Huffman . . . . . . . . . . . . . . . . . . . . . . 343
V. Parcours en largeur dun graphe . . . . . . . . . . . . . . . . . . . . 348
1 Presentation . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
2 Idee de lalgorithme . . . . . . . . . . . . . . . . . . . . . . 348
10
27 Problemes de chemin 372
I. Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . 372
1 Presentation . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
2 Lalgorithme . . . . . . . . . . . . . . . . . . . . . . . . . . 372
3 Description de lalgorithme de Dijkstra . . . . . . . . . . . . 373
4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
II. Methode PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
1 Presentation de la methode . . . . . . . . . . . . . . . . . . . 375
2 Algorithme du chemin critique . . . . . . . . . . . . . . . . . 375
3 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
VI Annexes 390
29 Annales 391
I. Partiel du 22 octobre 2007 (S1) . . . . . . . . . . . . . . . . . . . . . 391
II. Partiel du 22 octobre 2007 (S3) . . . . . . . . . . . . . . . . . . . . . 396
30 Bibliographie 406
Index 409
11
Remerciements
Je tiens a remercier vivement Michel Bour, qui ma tres amicalement laisse ses sup-
ports de cours. Ce document sen inspire tres largement, au point den etre, frequemment,
quune remise en forme. Sans lui, ce support de cours nexisterait pas.
12
Premiere partie
13
Chapitre 1
14
2. B = {x N|x(2x + 3) = 14}
3. C = {x N10 |x4 1 est divisible par 5 }
2 Regles de fonctionnement
Relation dappartenance Il faut etre capable de decider si un objet est ou non element
de lensemble (symbole ).
Objets distincts Il faut etre capable de distinguer les elements dun ensemble entre
eux. Un ensemble ne peut pas contenir deux fois le meme objet.
Ensemble vide Ensemble ne contenant aucun element1 (symbole : le cercle barre2 ).
Derniere regle de fonctionnement des ensembles Un ensemble ne peut pas sappar-
tenir a lui-meme.
R EMARQUE 1. Cette derniere regle de fonctionnement peut sembler obscure, pas na-
turelle.
Dans leuphorie de la naissance de la theorie des ensembles, les mathematiciens ne
voyaient pas dobjection a envisager un ensemble dont les elements seraient tous les
ensembles (en particulier, ) : lensemble des ensembles, a lorigine de tout !
Leur enthousiasme fut stoppe lorsque Russell leur opposa le paradoxe...
R EMARQUE 2. Il ne faut pas negliger limpact dune telle revelation. Certains allerent
jusqua y voir la preuve de la nom-existence de Dieu.
1
Lensemble vide ne correspond pas a rien ; cest en fait un ensemble qui ne contient rien, mais en
tant quensemble il nest pas rien : un sac vide est vide, mais le sac en lui meme existe.
2
La notation a ete introduite par le mathematicien francais Andre Weil du groupe Bourbaki. Uni-
code : U+00D8
15
3 Sous-ensembles, ensemble des parties
Sous-ensemble Ils sont definis par la relation dinclusion : (( A sous-ensemble de B
(A B) )) si et seulement si tout element de A appartient a B. On dit alors que
A est sous-ensemble, ou partie, de B.
Lensemble vide est inclus dans nimporte quel ensemble3 .
Tout ensemble est inclus dans lui-meme.
Ensemble des parties Soit A un ensemble, lensemble des parties de A, note P(A),
est lensemble de tous les sous-ensembles de A.
Comme A A, A P(A).
De plus, en general, si A possede n elements, P(A) en possede 2n .
4 Representation graphique
On peut representer ensembles et sous-ensembles a laide dun diagramme de Venn
(les celebres (( patates )))...
16
2. Les docteurs sont des gens heureux.
3. Nul ne peut etre a la fois docteur et poete.
5 Exercices
Exercice 5. Est-ce que {a} {a, b, c} ? Former la liste des parties de {a, b, c}.
Exercice 7. Quels sont les elements de P() ? Quels sont ceux de P(P()) ?
17
II. Operations sur les ensembles
1 Egalite de deux ensembles
D EFINITION 1. Deux ensembles sont egaux si et seulement si ils ont les memes elements.
A B et B A A = B.
Exercice 9. Dans chacun des cas suivants, determiner si les ensembles sont egaux :
1. A = {x R|x > 0} et B = {x R|x > |x|}
2. A = {x R|x > 0} et B = {x R|x 6 |x|}
3. A = Z et B = {x Z|x2 x pair }
4. A = {x N20 | x impair, non divisible par 3 } et B = {x N20 | 24 divise x2
1}
2 Reunion, intersection
Reunion A et B sont deux ensembles, on considere la reunion de A et de B, notee
A B, lensemble des elements qui sont elements de A ou de B.
18
P ROPRI ET E II (P ROPRI ET ES DE L INTERSECTION ) : Lintersection de deux en-
sembles possede certaines proprietes :
idempotence : A A = A
commutativite : A B = B A
associativite : A (B C) = (A B) C
element neutre : si lon se place dans un ensemble E et que A est une partie de
E, alors E est element neutre pour lintersection : A E = A
Proprietes mutuelles de ces deux operations Ces deux operations ont des proprietes
symetriques...
Exercice 10. Dans chacun des cas suivants, faire la reunion des ensembles A et B.
1. A = {x N|x impair }, B = {x N|x pas divisible par 3 }
2. A = {x R|0 6 x 6 3}, B = {x R| 2 < x 6 1}
3. A = {(x, y) R2 |x + y 6 2}, B = {(x, y) R2 |2 < 3x y}
Exercice 11. Dans chacun des cas suivants, faire lintersection des ensembles A et B.
1. A = lensemble des rectangles, et B = lensemble des losanges.
2. A = {x R|0 6 x 6 3}, B = {x R| 2 < x 6 1}
3. A = {(x, y) R2 |x + y 6 2}, B = {(x, y) R2 |2 < 3x y}
19
3 Complementation
4 Produit cartesien
Le produit cartesien des ensembles A et B (dans cet ordre) est lensemble, que lon
note A B ((( A croix B ))) des couples ordonnes (a, b) ou a A et b B.
III. Exercices
Exercice 13 (Ensemble des parties). On se place dans lensemble P(E) des parties
dun ensemble non vide E ; A, B et C sont des parties de E.
1. A (A B) = A (A B) = ?
2. Montrer que (A C) (A B) et (A C) (A B) implique que C B.
Montrer que, pour quil soit possible de conclure a legalite de B et de C, les
deux propositions suivantes sont necessairement realisees : A B = A C et
A B = A C.
3. Montrer que (A B) (B C) (C A) = (A B) (B C) (C A).
20
Exercice 14 (La difference symetrique). Pour deux ensembles A et B, on appelle
difference symetrique, note AB, lensemble defini par
AB = (A B) \ (A B)
cest-a-dire que AB est constitue des elements qui appartiennent soit a A, soit a B,
mais pas aux deux.
1. Soit A = {1, 2, 3, 4, 5, 6}, B = {1, 3, 5, 7, 9}, C = {4, 5, 6, 7, 8, 9} et D =
{2, 3, 5, 7, 8}.
Trouver AB, CB, A (BD), BC, AD et (A B)(A D).
2. Verifiez que AB = [A (E \ B)] [(E \ A) B]
3. Calculer AA, AA, AE et E \ (AB).
4. Montrer que, si AB = C, alors AC = B et BC = A.
5. Montrer que la difference ensembliste est commutative, possede un element neutre,
est distributive, et associative.
6. Montrer que si AB = AC alors B = C.
(X A = X B) et Y X = Y A = Y B.
21
Exercice 17. Soit E un ensemble non vide et P(E) lensemble de ses parties.
Soit f une application croissante, pour linclusion, de P(E) dans lui-meme (cest-
a-dire : si X et Y sont deux parties de E et si X Y , alors f (X) f (Y )).
1. Montrer que, pour tout couple (X, Y ) de parties de E, on a : f (X) f (Y )
f (X Y )
2. On dit quune partie X de E est reguliere si et seulement si f (X) X. Montrer
quil existe au moins une partie reguliere dans E et que, si X est reguliere, il en
est de meme de f (X).
3. Soit A lintersection de toutes les parties regulieres de E. Montrer que A est
reguliere et que f (A) = A.
Fin du Chapitre
22
Chapitre 2
I. Definitions
On se donne deux ensembles E et F .
1 Definition
23
2 Remarques
R EMARQUE 1. Lorsque E = F , on parle de relation binaire definie dans lensemble
E. Son graphe est une partie de E 2 .
3 Exercices
Exercice 3. Sur lensemble Z des entiers relatifs, on definit deux relations, notees
respectivement et , de la facon suivante :
xy quand la somme x + y est paire
xy quand la difference x y est paire
Sont-elles egales ?
Reponse : xy x + y = 2k x + y 2y = 2k 2y.
Donc xy x y = 2(k y) = 2k xy.
Application.
24
Voici la formalisation (partielle) de ces propositions :
x E, y F, (x, y) G
x E, y F, y F, [(x, y) G et (x, y ) G = y = y ].
R EMARQUE 3. Une application est donc une relation fonctionnelle particuliere : tout
element de lensemble de depart possede exactement une image.
Exercice 4. Parmi les relations suivantes de R vers R, reperez les relations fonction-
nelles, reperez les applications :
1. R = {(x, y) R2 , |y| = x}
2. R = {(x, y) R2 , xy = 1}
3. R = {(x, y) R2 , y x + 2 = 0}
Reponse : Les deux dernieres sont des relations fonctionnelles, et la derniere est la
seule application.
D EFINITION 4. Cet unique y est alors appele image de x par lapplication definie par
R.
25
Exercice 5. Interpreter chacune des situations suivantes au moyen dune application.
Pour cela, on definira deux ensembles A et B ainsi que f : A B.
1. Le resultat dune course de tierce.
2. Le registre dun hotel qui possede 55 chambres.
3. Le numero dINSEE.
4. La parite dun entier naturel.
5. Un emploi du temps.
Reciproquement...
3 Applications injectives
3.1 Definitions
26
3.2 Exercices
Exercice 6. Tracez le graphe dune application qui est injective, et dune application
qui ne lest pas.
Exercice 8. On suppose gof injective. Montrer que f est injective. Est-ce que g est
obligatoirement injective ?
4 Applications surjectives
4.1 Definition
La definition dune application f exige seulement que chaque element x de E ad-
mette une image (unique) y dans F , mais pas que tout element y de F admette un
antecedent dans E.
Exercice 9. Tracez le graphe dune application qui est surjective, et dune application
qui ne lest pas.
27
Exercice 10. Donnez des exemples (sous forme analytique) de fonctions surjectives,
et de fonction qui ne le sont pas.
Exercice 11. On suppose gof surjective. Montrer que g est surjective. Est-ce que f
est obligatoirement surjective ?
28
5 Applications bijectives
5.1 Definition
Exercice 12. Dans chaque cas, dire si lapplication f : A B est injective, surjec-
tive ou bijective.
1. A = R, B = R, f (x) = x + 7
2. A = R, B = R, f (x) = x2 + 2x 3
3. A = {x R|4 6 x 6 9}, B = {x R|21 6 x 6 96}, f (x) = x2 + 2x 3
4. A = R, B = R, f (x) = 3x 2|x|
5. A = R, B = R, f (x) = ex + 1
6. A = N, B = N, f (x) = x(x + 1)
N OTATION : On la note f 1
29
Exercice 13. Reprendre lexercice precedent, en trouvant lapplication reciproque des
applications bijectives.
30
...tout simplement parce quil ny a (( pas assez )) delements dans F (ou (( trop )) dans
E).
Si lon veut pouvoir definir une bijection entre deux ensembles, il semble necessaire
et suffisant quils aient le meme (( nombre delements )) (on se limite ici au domaine
fini).
Cette notion intuitive, resultat immediat dune simple operation de comptage, est
reliee a la notion mathematique de mise en bijection avec une partie de N de la forme
{1 , 2 , . . . , n}.
Ainsi, pour n N donne, les ensembles a n elements sont tous ceux qui peuvent
etre mis en bijection avec {1 , 2 , . . . , n} (et, par convention, a 0 element).
Pas de probleme donc lorsque lon sen tient aux ensembles finis, dont la definition
mathematique est :
D EFINITION 11 (E NSEMBLE FINI ). Un ensemble est dit fini sil ne peut pas etre mis
en bijection avec une partie stricte de lui-meme.
E XEMPLE 3. Il existe des bijections entre N et lensemble des entiers pairs (2N) ou
impairs (2N + 1), qui conduisent a des formulations du style (( il y a autant dentiers
que dentiers pairs )).
31
R EMARQUE 9. (2N) (2N + 1) = N, bien que ces trois ensembles (( on le meme
nombre delements )), les deux premiers etants disjoints... A rapprocher de + =
.
3 Nombre dinfinis
3.1 Notion de puissance dun ensemble
Le resultat fondamental est...
P REUVE Admis
Ce resultat montre que, meme si E est un ensemble infini, il ne peut etre mis en
bijection avec P(E), qui a donc (( strictement plus delements )) que E.
Consequemment, N et ses parties infinies, Z, et meme Q ont tous la meme puis-
sance, dite puissance du denombrable . Mais...
32
3.2 R est indenombrable : une demonstration de Cantor.
Supposons que R soit denombrable.
On pourrait alors ecrire la liste de TOUS les reels, a partir du premier, en ecriture
decimale r1 , r2 , r3 , etc.
R EMARQUE 11. On choisit pour les nombres decimaux lecriture qui ne comporte
que des zeros a partir dun certain rang, sil y a ambigute.
1 Definition
Soit R une relation binaire definie dans un ensemble E, de graphe G.
33
D EFINITION 15 (A NTISYM ETRIE ). R est dite antisymetrique si, lorsque x est en re-
lation avec y , alors y ne peut pas etre en relation avec x (sauf si x = y ) :
x E, y E, (x, y) G et (y, x) G = x = y
34
E XEMPLE 7 (R ELATION DE DIVISIBILIT E ). On note a|b si et seulement si b est un
multiple de a ( k N , b = ka).
Cest une relation dordre definie dans N . En effet, elle est
reflexive : a = 1a, donc a|a est vrai,
antisymetrique : si a|b et b|a, alors k, k N , a = kb et b = k a. Donc
a = kk a. Comme a 6= 0, kk = 1. Mais k, k N , donc k = k = 1, et a = b.
transitive : si a|b et b|c, alors alors k, k N , a = kb et b = k c. Donc a =
kk c : il existe k N (k = kk ) tel que a = k c : a|c.
35
3 Exercices
Exercice 16. Parmi les relations suivantes sur lensemble E, reperez les relations
dordre, les relations dordre total :
1. E = Z, xRy k N : x = y k .
2. E = N, xRy x < y.
3. E = R, xRy x2 = y 2 .
4. E = R2 , (x1 , x2 )R(y1 , y2 ) (x1 6 y2 ) (x2 6 y1 ).
Exercice 17. Tenter de caracteriser par son graphe une relation dordre (partiel to-
tal).
Exercice 18. Definir, par leurs graphes, les relations dordre dans E qui comportent
respectivement le moins et le plus possible de points ; que peut-on dire de ces rela-
tions ?
36
4 Elements maximaux
Soit (E, R) un ensemble ordonne et A une partie de E. Quelques definitions...
R EMARQUE 16. Il existe des parties non majorees (R+ pour 6 dans R)
R EMARQUE 17. Il peut exister une infinite de majorants pour une partie majoree.
N OTATION : Max A.
37
R EMARQUE 18. Si A est non majoree, il est exclu quelle admette un element maxi-
mum.
R EMARQUE 19. Cet element maximum nexiste pas toujours, meme pour une partie
majoree. Ainsi, lintervalle reel ]2,3[ est majore, mais na pas delement maximum.
Cependant, sil existe, cet element est unique.
Exercice 23. Etant donne B = {1, 2, 3, 4, 5} ordonne selon la relation 4 < 2, 5 < 2,
5 < 3, 2 < 1, 3 < 1. Trouver Min A et Max A.
Exercice 24. Trouvez des exemples de bornes sup et de bornes inf sur R.
Exercice 25 (Une relation dordre). On considere lensemble des points dun plan
affine euclidien, et on y definit une relation binaire (symbole 6) par P1 6 P2
(x1 6 x2 et y1 6 y2 ).
1. Definir, lorsquils existent, les points Sup{P1 , P2 } et Inf{P1 , P2 }.
2. Existent-ils toujours, quels que soient les points P1 et P2 ?
38
P ROPRI ET E VI : Il est clair que :
dans certains cas, les elements definis ici nexistent pas,
que lelement maximum est aussi borne superieure.
Et finalement, pour une partie A dun ensemble ordonne E :
A peut ne pas etre majoree.
Si A est majoree, elle peut ne pas admettre de borne superieure.
Si SupA existe (A est majoree), A peut ne pas admettre delement maxi-
mum.
Si MaxA existe, alors SupA = MaxA.
...et on a les memes resultats pour les parties minorees.
5 Treillis
5.1 Cas des ensembles totalement ordonnes
Dans un ensemble totalement ordonne, si lon choisit une paire delements quel-
conques (x, y) il est possible de decider lequel est le plus petit et lequel est le plus
grand.
39
Et, comme cette partie {x , y} admet un element minimum et un element maxi-
mum, ces deux elements sont aussi (respectivement) borne inferieure et superieure, on
peut ecrire Inf{x , y} = x et Sup{x , y} = y.
Lexistence de ces deux elements est assuree, ce qui nest pas le cas dans un en-
semble qui nest que partiellement ordonne.
R EMARQUE 20. Il suffit que la propriete soit vraie pour deux elements distincts (i.e.
une partie a deux elements) pour quelle soit vrai pour toutes les parties finies.
D EFINITION 28 (T REILLIS COMPLET ). Si la propriete est vrai pour toute partie, alors
le treillis est dit complet.
R EMARQUE 21. Cette notion noffre un interet que dans le cas dun ensemble par-
tiellement ordonne, car lexistence dune borne inferieure et dune borne superieure
pour tout couple (et donc pour toute partie finie) permet de les comparer aux autres par
lintermediaire de ces bornes, meme si on ne peut pas les comparer entre eux.
En effet, on a toujours Inf{x , y} 6 x 6 Sup{x , y} et Inf{x , y} 6 y 6
Sup{x , y} (on reprend les exemples vus plus haut).
40
Exercice 27 (Diagrammes de transitivite). On considere...
1. E = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9} et on definit la relation binaire R dans E par
son graphe G = { (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (2,2),
(2,3), (2,4), (2,6), (2,8), (2,9), (3,3), (4,3), (4,4), (4,6), (4,8), (4,9), (5,3), (5,4),
(5,5), (5,6), (5,7), (5,8), (5,9), (6,6), (6,8), (6,9), (7,7), (7,8), (7,9), (8,8), (9,9) }
(cest-a-dire : 1R1, etc. . . ). Montrer que cette relation est une relation dordre.
E est-il totalement ordonne par cette relation ? est-il un treillis ?
2. Memes questions pour E = {1 , 2 , 3 , 4 , 5 , 6} et G = { (1,1), (1,2), (1,3),
(1,4), (1,5), (1,6), (2,2), (2,4), (2,5), (2,6), (3,3), (3,4), (3,6), (4,4), (4,6), (5,5),
(5,6), (6,6)}.
V. Relations dequivalence
On se place encore dans ce paragraphe dans le cas ou E = F .
1 Definition
Soit R une relation binaire definie dans un ensemble (non vide) E, de graphe G.
D EFINITION 29 (R ELATION SYM ETRIQUE ). R est dite symetrique si, des que x est
en relation avec y , alors y est en relation avec x
x E, y E, (x, y) G = (y, x) G
Exercice 28. Est-ce quune relation sur un ensemble A dont le graphe est constitue
uniquement de couples (x,x) est symetrique ? transitive ?
41
E XEMPLE 14 (R ELATION DE CONGRUENCE MODULO n DANS Z). Par definition :
.
reflexivite : x x[n] : en effet, x x = 0 n, et 0 Z.
symetrie : si x y [n], k Z, x y = k n ; alors y x = (k) n ; or, si
k Z, (k) Z, donc y x [n].
transitivite : si x y [n] et y z [n], k Z, x y = k n et l Z,
y z = l n. En aditionnant membre a membre ces deux egalites, on obtient
x z = (k + l) n, or (k, l) Z2 , donc k + l Z, donc x z [n].
Cest bien une relation dequivalence.
2 Classes dequivalence
2.1 Definition
42
Exercice 31. Trouvez les classes dequivalences des deux exercices precedents.
Exercice 32. On definit une relation sur lensemble des mots de la langue francaise
de la facon suivante : (( le mot M est lie au mot N si N est une anagramme1 de M. ))
Quelle est la classe dequivalence du mot chien ?
R EMARQUE 23. On dit aussi que les classes sont deux a deux disjointes.
1
Mot obtenu par transposition des lettres dun autre mot. Une anagramme interessante : aimer -
Marie. Le pseudonyme de Alcofribas Nasier est, a peu pres, lanagramme de Francois Rabelais.
43
P ROPRI ET E IX : Les classes dequivalence realisent une partition de E.
P REUVE Comme les classes sont des parties de E, leur reunion est une partie de
E.
Reciproquement, tout element de E appartient a une classe ((( tout element est
classe )) ). Donc E est une partie de la reunion des classes ; et E est egal a la reunion
des classes.
P1 R P2 x1 y1 = x2 y2 et x1 x2 > 0
3 Ensemble-quotient
N OTATION : E/R.
44
Pour parler aisement dune classe, on choisit un de ses elements, et cet element,
surmonte dun point, sert a representer la classe en question.
Une fois que ce choix est fait, il est definitif, et il nest plus question devoquer les
autres elements de cette classe, il faut se tenir, sous peine dincoherence, au choix qui
a ete fait.
4 Exercices
Exercice 36. Donner des exemples de relation R dans {1, 2, 3} ayant les proprietes
suivantes :
1. R est symetrique,
2. R nest ni symetrique ni antisymetrique,
3. R est transitive mais R R1 nest pas transitive.
45
Exercice 37. Soit R et S deux relations dans A.
1. Montrer que si R et S sont transitives alors R S est transitive.
2. Si R est antisymetrique alors R S est antisymetrique.
R = {(1, 1), (1, 5), (2, 2), (2, 3), (2, 6), (3, 2), (3, 3), (3, 6), (4, 4), (5, 1), (5, 5), (6, 2), (6, 3), (6, 6)}
Exercice 39. Tenter de caracteriser par son graphe une relation dequivalence.
Exercice 40. Definir, par leurs graphes, les relations dequivalence dans E qui com-
portent respectivement le moins et le plus possible de points.
Que peut-on dire de ces relations ?
D EFINITION 34. La relation binaire (dans E ) de symbole R est dite compatible avec
loperation (definie dans E ) de symbole lorsque, quels que soient les elements x, x ,
y et y de E : si xRx et si yRy , alors (x y)R(x y )
46
Autrement dit, loperation conserve la relation.
Lorsquune relation dequivalence est compatible avec une operation, on peut definir
dans lensemble-quotient une operation, dite induite de celle qui existe dans lensemble
dorigine.
Fin du Chapitre
47
Chapitre 3
Relations n-aires
I. Definitions
1 Relations orientees et non orientees
Exactement comme dans le cas des relations binaires, on considere une partie G de
lensemble produit cartesien de n ensembles (E1 , E2 , . . . , En ), soit G E1 E2
En .
D EFINITION 1 (R ELATION n- AIRE ). Cette partie definit une relation n-aire entre ces
ensembles.
Comme dans le cas des relations binaires, les n-uplets sont ordonnes et, meme si
deux des ensembles Ei et Ej sont identiques (pour i 6= j), le couple delements (xi , yj )
est considere comme different du couple (yj , xi ) lorsque xi 6= yj .
Cependant, dans la plupart des applications pratiques des relations n-aires, et dans
toutes celles que nous verrons en tout cas, on (( etiquette les colonnes )), ce qui permet
de saffranchir de cet ordre, et de considerer ce que lon appelle des relations n-aires
non orientees, dont les domaines sont les ensembles (E1 , E2 , . . . , En ), dans un ordre
non specifie, car ils sont nommes.
48
et soit
G est le graphe dune relation ternaire orientee qui represente une cave a vins.
3 1988 Alsace
4 1991 Alsace
8 1989 Beaujolais
4 1989 Cotes du Rhone
Il est evident que lordre des elements du n-uplet element de G a une importance
fondamentale, surtout lorsque lintersection des domaines nest pas vide.
Autrement dit, cette relation doit etre consideree comme differente de la relation
definie sur E3 E2 E1 par le graphe G represente par le tableau
Alsace 1988 3
Alsace 1991 4
Beaujolais 1989 8
Cotes du Rhone 1989 4
Pour saffranchir de lordre en evitant toute ambigute, il faut nommer les colonnes
du tableau, cest-a-dire ajouter un ensemble dattributs (ou cles, ou etiquettes) qui
pourraient etre ici {Nombre, Annee, Region}.
On obtiendrait
Cette relation ternaire ne sera pas consideree comme differente de la relation representee
par
49
En effet, les attributs ne sont pas ordonnes, lensemble {Region, Annee, Nombre}
est egal a lensemble {Nombre, Annee, Region}.
Dans la suite, le terme de relation n-aire sera reserve aux relations non orientees.
On peut toujours associer a une relation n-aire une relation n-aire orientee, definie
sur D1 D2 Dn , ou les Di sont les domaines attaches aux attributs de A,
enonces dans un certain ordre.
Bien entendu, si les attributs sont enonces dans un ordre different, la relation n-
aire orientee associee peut ne pas etre la meme, mais, pour une meme relation n-aire,
toutes les relations n-aires orientees associees se deduisent les unes des autres par une
permutation sur les domaines.
50
3 Interpretation fonctionnelle
Chaque ligne du tableau dune relation n-aire R[A] aux attributs A, de domaines
(D1 , D2 , . . . , Dn ), peut etre interpretee comme une application de A (lensemble
des attributs) dans D1 D2 Dn .
4 SGBD
II. Projections
1 Definitions
Soit R[A] une relation n-aire dattributs A, et a A.
On pose A = {a} B, et on suppose que le domaine de a est D1 et que les
domaines des attributs de B sont D2 , . . . , Dn .
51
2 Theoreme des projections
Soit R[A] une relation n-aire dattributs A, a A, b A (b 6= a).
(Ra )b = (Rb )a .
N OTATION : On notera cette projection RB (ou R[A \ B]) (si B A, cest la pro-
jection suivant B de R sur C = A \ B.
Pour lenonce de la definition, comme lordre dans lequel on enonce les attributs
est sans importance, on suppose que, dans A B, les elements sont enumeres dans
lordre suivant
les attributs de A qui ne sont pas dans B, les domaines sont D1 , . . . , Dp ,
les attributs communs a A et a B, les domaines sont Dp+1 , . . . , Dq ,
les attributs de B qui ne sont pas dans A, les domaines sont Dq+1 , . . . , Dn .
(lun de ces sous-ensembles peut etre vide).
52
E XEMPLE 2. Le domaine de lattribut Groupe est {1, 2, 3}, celui de Nom est {A,B,C}
et celui de Age est {19, 20, 21}.
2 Reunion et intersection
Cest le cas particulier de la somme et du produit de deux relations dattributs A et
B dans le cas ou A = B.
Donc, dans le cas ou A = B, R S = R + S et R S = R S.
3 Produit cartesien
Il sagit du cas particulier du produit de deux relations dans le cas ou A B =6 o.
Donc, dans le cas ou A B =6 o, R S = R S.
53
D EFINITION 7. La selection de R suivant F est une relation ayant les memes attributs
A, notee (R : F ) [A] et telle que R(x1 , x2 , . . . , xn ) et F (x1 , x2 , . . . , xn ).
Autrement dit, il sagit des elements des domaines des attributs qui sont en relation
par R et qui satisfont la formule F donnee.
E XEMPLE 3. Sur une relation dattributs {Nom , Age , Note} on pourra definir la re-
lation [(Age 6 19) et (Note > 16)] pour selectionner les etudiants admis a sinscrire
au departement dInformatique.
et
R(x1 , . . . , xp , xp+1 , . . . , xq , xq+1 , . . . , xn )
si et seulement si
xp+1 = xp+1 , . . . , xq = xq
.
54
x pour (x1 , . . . , xp ),
y pour (xp+1 , . . . , xq )
et z pour (xq+1 , . . . , xn ).
E XEMPLE 5. La relation precedente est le produit de ses deux projections R[{Nom , Age}]
et R[{Nom , Groupe , Niveau}].
55
3 Cles
D EFINITION 9 (C L E ). Pour une relation R[A] dattributs A, une cle est un sous-
ensemble minimal K de A tel quil existe une dependance fonctionnelle C A \ K .
(K est un sous-ensemble minimal au sens quil ny a pas de partie stricte K de K
pour laquelle il existe une dependance fonctionnelle K A \ K ).
P ROPRI ET E III : Pour toute relation, il est possible dintroduire un attribut dont
les valeurs sont toutes differentes, et qui constitue donc une cle pour la nouvelle
relation obtenue (par exemple, une numerotation).
Fin du Chapitre
56
Deuxieme partie
Arithmetique
57
Chapitre 4
58
Il existe une version (( affaiblie )) du principe de recurrence : la recurrence restreinte,
qui permet de sassurer quune propriete est vraie a partir dun certain rang...
R EMARQUE 3. Toute phrase, telle que celles que lon peut souvent lire, de la forme
(( supposons la propriete vraie pour n )) devrait immediatement appeler la question :
quest-ce que cest que n ?
Si n est (( un entier quelconque )) , alors vous supposez la propriete vraie pour un
entier quelconque, et il ne vous reste plus grand chose a demontrer....
Si n est un entier fixe, mettons 47, alors vous allez demontrer la propriete pour
48, et il vous restera pas mal de chemin a faire. . .
Non, ce que vous supposez, ce nest pas que la propriete est vraie (pour quoi que
ce soit), mais que n est un entier pour lequel la propriete est verifiee (cet entier etant
evidemment quelconque parmi ceux pour lesquels la propriete est verifiee), ce nest
pas du tout la meme chose.
59
2 Operations et relation dordre dans N
On suppose ici connues les operations et la relation dordre classiques qui existent
dans N : addition, multiplication, relation dinegalite au sens large.
Ces elements peuvent etre definis rigoureusement, et toutes les proprietes demontrees
par recurrence.
3 Nombres premiers
3.1 Definitions
Reponse : (3+1)*(1+1)*(2+1)*(3+1)=96.
60
E XEMPLE 2. Ainsi, le plus petit nombre premier (et le seul qui soit pair) est 2.
Exercice 2. Ecrivez les nombres 3850 et 1911 sous forme de produits de nombres
premiers.
Reponses : 2 52 7 11 et 3 72 13.
1. Montrer que, pour que 2n + 1 soit premier, il faut que n soit une puissance de 2.
2. La reciproque nest pas vraie : donner un exemple de nombre de Fermat qui ne
soit pas premier.
3. Montrer que, pour k > 1, Fp divise Fp+k 2.
61
4. En deduire que Fp et Fp+k sont premiers entre eux.
5. En deduire quil existe une infinite de nombres premiers.
4 Relation de divisibilite
On a vu dans le chapitre sur les relations entre ensembles la relation binaire de
divisibilite definie dans N .
Cette relation est une relation dordre partiel : il existe des paires dentiers non
comparables par cette relation.
Cet ordre nest donc que partiel, mais il existe, pour chaque couple dentiers dis-
tincts, une borne inferieure et une borne superieure...
62
Reponse : 2346.
Exercice 5. Soient a, b, c, d des entiers naturels non nuls tels que ad = bc.
Prouvez que si a et b sont premiers entre eux, alors b|d
5 Entiers relatifs
Lensemble habituellement note Z des entiers relatifs est obtenu a partir de N par
le procede de symetrisation pour laddition.
Sans setendre sur le sujet, disons que cela consiste a introduire les entiers stricte-
ment negatifs comme opposes des positifs correspondants, par n + (n) = 0.
On sait que les porprietes des operations sont conservees ; la seule propriete perdue
dans cette extension est la compatibilte entre la relation dordre et la multiplication.
63
II. Division euclidienne dans Z et applications
1 Definition
On se donne deux entiers relatifs a et b, b non nul.
E XEMPLE 5. Tout nombre non nul est au moins divisible par 1 et par lui-meme (a =
a 1 + 0).
E XEMPLE 6. 0 est divisible par tout nombre entier non nul (0 = 0 b + 0).
64
2. Trouver les restes dans la division par 8 du carre dun entier impair.
3. Trouver les restes dans la division par 11 de 37n (pour n N ).
4. Montrer que 10n (9n 1) + 1 est divisible par 9.
n = np bp + np1 bp1 + + n1 b1 + n0
65
2.4 Exercices
66
3 Arithmetique modulo n
On rappelle ici la definition de la relation dite de (( congruence modulo n )) definie
dans Z etudiee dans le chapitre consacre aux relations entre ensembles.
P REUVE En effet :
x Z, x x = 0 = 0 n ; or 0 Z, donc x x[n] (reflexivite).
Si x y[n],k Z, x y = k n ; alors y x = (k) n, et, puisque k Z,
(k) Z, donc y x[n] (symetrie).
Si x y[n],k Z, xy = k n ; si, de plus, y z[n], l Z, y z = l n ;
alors (par addition), x z = (k + l) n ; comme k Z et l Z, (k + l) Z,
donc x z[n] (transitivite).
La classe dequivalence dun entier donne comprend donc cet entier et tous ceux
qui ont le meme reste que lui dans la division euclidienne par n.
67
N OTATION : Il est note Z/nZ.
R EMARQUE 6. Cest cette propriete qui permet de definir dans lensemble quotient
Z/nZ des operations, dites induites par celles qui existent dans Z...
y) et x y = (xy)
D EFINITION 10. Par definition, on pose x + y = (x + .
E XEMPLE 9. Cest ainsi quon obtient les tables doperations suivantes dans Z/4Z :
+ 0 1 2 3 0 1 2 3
0 0 1 2 3 0 0 0 0 0
1 1 2 3 0 1 0 1 2 3
2 2 3 0 1 2 0 2 0 2
3 3 0 1 2 3 0 3 2 1
68
R EMARQUE 7. On apercoit la presence de (( diviseurs de zero )) (2 2 = 0), mais
aussi lapparition dun inverse pour certains elements (3 3 = 1).
Reponses : 5 et 630.
69
Exercice 12. Resolvez modulo 18 les equations suivantes :
1. 2x + 17 = 15,
2. 3x + 4 = 12,
3. 5x + 13 = 16.
Exercice 13. Si m est un entier naturel plus grand que 2, quel est linverse de m 1
modulo m ?
Reponse : m 1.
Exercice 14. Un nombre (( pseudo-premier de base b )) est un entier naturel non pre-
mier p tel que (bp b)modp = 0.
Verifier que 561 est pseudo-premier de base 3 et que 341 est pseudo-premier de
base 2.
Pour des raisons pratiques de realisation des micro-circuits des processeurs qui
realisent ces operations, la (( division entiere )) ne donne pas exactement le meme
70
resultat que la division euclidienne.
Autrement dit, mathematiquement, le quotient est positif lorsque les deux nombres
ont le meme signe et le reste est toujours positif, et, pour que le reste soit toujours
positif, le quotient peut ne pas etre le quotient des valeurs absolues.
Informatiquement, le (( quotient )) est positif lorsque les nombres ont le meme signe,
le (( reste )) a le signe du dividende, et la valeur absolue du (( quotient )) est toujours le
quotient des valeurs absolues.
Mais il faut quand meme savoir que lon peut obtenir un (( reste )) negatif et prendre
ses dispositions le cas echeant...
Dans la plupart des microprocesseurs, les entiers sont representes sur 32 bits, les
calculs se font donc dans Z/232 Z (et quils le soient sur 64 bits ne change rien au
probleme).
71
Disposer dentiers signes ou dentiers non signes est uniquement une question de
choix du representant dans les classes dequivalence, mais la representation physique
est la meme.
Comme il nous est difficile de representer ici la liste complete de tous ces entiers,
nous allons illustrer ce propos en supposant que les entiers sont representes sur 4 bits.
Pourquoi ce choix ? Pourquoi ne pas avoir, en a.s., represente les entiers dans
lordre croissant de 0000 (-8) a 1111 (7) ?
Tout simplement pour des raisons defficacite : 0 doit toujours etre represente
par le code (( nul )) 0000.
72
Ensuite, il faut pouvoir comparer efficacement ces codes entre eux, ce qui ex-
plique que 0 doit etre suivi de 1, arithmetique signee ou pas.
Ces principes ont ainsi conduit a placer les codes interpretes comme entiers negatifs
apres ceux qui representent les entiers positifs.
Par ailleurs, on sapercoit que, de cette maniere, les codes des entiers negatifs com-
mencent tous par 1. On parle improprement de (( bit de signe )) : sil sagissait dun
veritable bit de signe, le code 1001 devrait etre celui de -1, or cest celui de -7. Mais il
nen reste pas moins que tous les entiers negatifs commencent par 1).
73
Operation binaire Entiers non signes Entiers signes
0100 4 4
+ 0110 +6 +6
1010 10 (-6)
E XEMPLE 12. Un depassement de capacite dans les deux cas, mais le resultat est
correct modulo 16 : les classes de 21, de -11 et de 5 sont les memes :
Operation binaire Entiers non signes Entiers signes
1100 12 (-4)
+ 1001 +9 +(-7)
(1)0101 5 5
Le resultat (correct modulo 16) est disponible dans tous les cas, les (( depassement de
capacite )) et (( resultat negatif )) sont signales par le positionnement dun bit dans un
registre special.
E XEMPLE 13. Un resultat correct en a.n.s., resultat negatif en a.s., mais correct mo-
dulo 16 :
Operation binaire Entiers non signes Entiers signes
0101 5 5
0010 2 2
1010 10 (-6)
E XEMPLE 14. Depassement de capacite dans les deux cas, resultat negatif en a.s.,
mais resultat correct modulo 16, compte tenu du choix des representants dans les deux
arithmetiques :
Operation binaire Entiers non signes Entiers signes
0101 5 5
0110 6 6
(1)1110 14 (-2)
74
E XEMPLE 15. Depassement de capacite dans les deux cas, resultat correct en a.s.,
correct modulo 16 en a.n.s.
Operation binaire Entiers non signes Entiers signes
1101 13 (-3)
1110 14 (-2)
(1011)0110 6 6
Par definition, le PGCD de a non nul avec 0 est a (defintion raisonnable, car 0 est
divisible par tout entier non nul, donc par a, qui lest aussi par a) et enfin le PGCD de
0 et de 0 nest pas defini.
Il est possible de considerer des nombres negatifs (bien que ce soit sans grand
interet dans les applications pratiques), mais le PGCD est celui des valeurs absolues.
2 Algorithme dEuclide
2.1 Algorithme
On se limite ici au cas de deux entiers a et b strictement positifs.
75
4. Reciproquement, soit d un diviseur commun a b et r, qui peuvent alors secrire
b = db et r = dr et legalite a = bq + r devient a = d(b q + r ).
Donc d est un diviseur commun a a et b, et, par inclusion reciproque, les en-
sembles des diviseurs communs a a et b dune part et a b et r dautre part sont
identiques.
En particulier a b = b r.
5. Si r = 0, le a b = b, sinon on peut effectuer la division euclidienne de b par r,
qui donne un reste r1 , tel que r1 < r et b r = r r1 .
6. Cet algorithme est itere jusqua lobtention dun reste nul, ce qui se produit obli-
gatoirement puisquil sagit dentiers et que la suite des restes ainsi construite
est strictement decroissante.
7. Le PGCD est alors lavant-dernier reste (le dernier non nul).
R EMARQUE 8. Cet algorithme permet donc dobtenir le PGCD de deux nombres sans
connatre leurs decompositions en facteurs premiers.
2.2 Programmation
Voici sa programmation iterative en C :
(en toute rigueur, il faudrait verifier que a et b sont bien positifs ; par ailleurs, cette
fonction retourne 0 comme PGCD de 0 et de 0 : a verifier avant lappel).
76
3 Theoreme de Bezout
On considere deux nombres entiers strictement positifs a et b.
Exercice 15. Montrez que, si m est multiple de deux nombres premiers entre eux a et
b, alors m est multiple de ab.
Exercice 16. Montrez que, si on divise deux entiers naturels a et b par leur pgcd, alors
les quotients obtenus sont premiers entre eux.
Reciproquement, montrer que, si les quotients obtenus en divisant a et b par un
diviseur commun d sont premiers entre eux, alors d = pgcd(a, b).
77
Reponse : Soit d = pgcd(a, b), et q1 et q2 les quotients de a et b par d. Alors d =
aa + bb = dq1 a + dq2 b . Donc 1 = q1 a + q2 b : q1 et q2 sont premiers entre eux. La
reciproque est du meme genre.
Cette famille...
est strictement decroissante,
est telle que rk+1 = 0,
verifie r0 r1 = r1 r2 = . . . = rk1 rk = rk rk+1 = rk 0 = rk .
Dune maniere generale, si (u, v) est un couple de Bezout pour ri+1 et ri+2 , soit
uri+1 +vri+2 = d, comme ri = qi+1 ri+1 +ri+2, on a uri+1 +v(ri qi+1 ri+1) = d,
soit (u qi+1 v) ri+1 + v ri = d.
4.2 Lalgorithme.
Ceci donne lidee de construire deux familles par les relations :
u0 = 1, u1 = 0,ui+2 = ui qi+1 ui+1
v0 = 0, v1 = 1, vi+2 = vi qi+1 vi+1 .
Cest ce que lon appelle algorithme dEuclide generalise. On a alors (uk , vk , rk ) =
(u, v, d), u et v tels que a u + b v = d.
78
P REUVE 1 :
Pour cela, il suffit de montrer par recurrence que i {0, . . . , k}, r0ui +r1 vi = ri .
Initialisation de la recurrence : la relation est vraie pour i = 0, en effet
r0 u0 + r1 v0 = r0 , puisque u0 = 1 et v0 = 0.
Caractere hereditaire de la propriete : en supposant que i est un entier pour
lequel r0 ui + r1 vi = ri et r0 ui+1 + r1 vi+1 = ri+1 , calculons r0 ui+2 +
r1 vi+2 = r0 (ui qi+1 ui+1) + r1 (vi qi+1 vi+1 ) = r0 ui + r1 vi
qi+1 (r0 ui+1 + r1 vi+1 ) = ri qi+1 ri+1 = ri+2 .
4.3 Exemple.
Illustrons la mise en uvre de cet algorithme...
On a bien 3 23 4 17 = 1.
R EMARQUE 10. Il est possible dobtenir -1 (ou d en general) comme resultat, donc
au bv = 1, cela depend de la parite du nombre diterations effectuees dans lalgo-
rithme precedent.
Ce nest pas un resultat faux, puisqualors bv au = 1 et quon a quand meme un
couple de Bezout pour (b, a).
Sil est necessaire dobtenir un couple (u, v) tel que aubv = 1 et ou a et b figurent
dans cet ordre, et que lalgorithme a fourni un couple (u , v ) tel que bv au = 1,
il suffit de prendre u = b u et v = a v et, dans ces conditions au bv =
a(b u ) b(a v ) = ab au ab + bv = bv au = 1.
Exercice 17. Exprimer pgcd(1330, 602) comme combinaison a coefficients entiers des
nombres 1330 et 602.
79
Reponse 14 = 1330 (19) + 602 42.
Fin du Chapitre
80
Chapitre 5
I. Introduction
Pour des raisons evidentes, il est impossible de representer exactement en machine
un nombre reel dont le developpement binaire, et a fortiori decimal, est infini.
E XEMPLE 1. Par exemple 1/3, mais aussi 1/10 (dont le developpement decimal 0,1
est fini, mais pas le developpement binaire) ne sont pas exactement representables.
E XEMPLE 2. En (( virgule fixe )), les limitations physiques des machines interdiraient
de representer simultanement, par exemple, 10100 et 10100 , alors que la representation
en virgule flottante le permet.
81
Bien entendu, laddition de ces deux nombres donnera le premier (exactement)
comme resultat, ce qui nest pas genant, mais leur multiplication donnera bien 1 comme
resultat (aux erreurs de representation et de calcul pres, car aucun de ces deux nombres
nest representable exactement en machine).
Cette meme norme prevoit un certain nombre de specifications qui concernent les
calculs sur les reels representes (independamment du format retenu) : aucune operation
sur les reels ne doit provoquer, par elle-meme, dinterruption du deroulement normal
du programme. Ni une division par 0, ni un depassement de capacite, ni une tentative
de calcul impossible.
Cest au logiciel qui gouverne les calculs de verifier le resultat et de provoquer, sil
le juge utile (et cest ce que font en general les compilateurs), une interruption.
Neanmoins, il a fallu prevoir des representations speciales pour ces cas particu-
liers :
lune sappelle (( INF )) (infini),
lautre (( NAN )) (abreviation pour (( not a number )) ).
E XEMPLE 3. Dapres ces specifications, le resultat de 1/0 (en reels) doit etre INF,
celui de 0/0 doit etre NAN.
On doit obtenir aussi 1 = NAN, ln 0 = INF, 1/INF = 0, mais INF/INF =
NAN, de meme que toute operation dont lun des operandes est NAN, par exemple
sin(NAN) = NAN, 1 + NAN = NAN...
82
R EMARQUE 1. Si vous voulez observer ces resultats, effectifs, vous serez obliges
doperer depuis lassembleur, aucun compilateur ne vous autorisera a tenter dobte-
nir de pareilles horreurs !
2 Format (( single ))
3 Format (( double ))
4 Format (( extended ))
83
On retrouve la valeur du reel x represente de la maniere suivante :
4. Pour les formats (( single )) et (( double )), la formule a appliquer est differente
dans le cas ou lexposant e est nul.
Il sagit de ce que lon appelle un (( reel denormalise )), introduit pour le motif
suivant :
les chiffres significatifs du reel represente sont contenus dans la mantisse ;
celle-ci est de longueur fixe pour un format donne,
donc, quel que soit lordre de grandeur du reel, sa representation est obtenue
avec la meme precision relative, ce qui permet de connatre la precision du
resultat dun calcul.
Cette mantisse (1, m) represente un nombre compris entre 1 (inclus, si m = 0)
et 2 (exclu).
84
On obtient ce nombre en multipliant ou en divisant le reel a representer par 2
jusqua ce que le resultat soit compris entre 1 et 2. Le nombre doperations ef-
fectuees donne lexposant (le vrai, negatif dans le cas de multiplications, positif
dans le cas de divisions).
Pour des nombres reels trop petits, lexposant peut alors etre lui-meme trop petit
pour etre representable dans la plage qui lui est fixee. On admet alors que, pour
la plus petite valeur de lexposant ((( biaise )) ), cest-a-dire 0, la mantisse est a
interpreter sous la forme 0, m, ce qui permet de representer encore quelques reels
trop petits pour etre representes dans la representation normalisee (les Anglo-
Saxons parlent de (( progressive underflow )) ).
Ces reels (( denormalises )) sont distingues des autres, parce quils sont representes
avec une precision moindre (la mantisse a moins de 52 chiffres binaires signifi-
catifs).
Autrement dit, la precision dun calcul qui utilise un reel denormalise nest plus
assuree, mais le risque dune division par 0 (alors que le (( vrai )) nombre nest
pas nul) est diminue.
Mais il est clair que, pour la precision dun calcul, il vaut mieux utiliser tous les
bits disponibles dans la mantisse (pour avoir le maximum de chiffres significa-
tifs).
Cest-a-dire quil faut choisir, parmi toutes les representations possibles pour un
nombre reel, celle pour laquelle i = 1 : cest ce que fait la machine (que les
operations soient implantees logiciellement ou effectuees par un coprocesseur
arithmetique).
Autrement dit, on reservera la valeur 0 pour i au cas ou lexposant (( biaise )) est
nul, comme pour les autres formats, et le probleme de la precision se pose de la
meme maniere.
85
6 Format (( extended )) des microprocesseurs.
Dans un langage tel que C (ou java),
le format (( single )) est obtenu avec les valeurs de type (( float )),
le format (( double )) est disponible dans les valeurs de type (( double )),
le format (( extended )) dans les valeurs de type (( long double )).
Pour etre complet, il est necessaire de preciser que les microprocesseurs modernes
possedent presque tous, integree, une unite de calcul specialisee dans le calcul sur les
reels, ayant des registres de taille adaptee a la representation de ces nombres (donc
plus longs que les registres de lunite de calcul arithmetique et logique principale).
Plus anciennement, ce role etait confie a une unite externe que lon appelait (( co-
processeur arithmetique )) et qui etait quelquefois optionnelle.
Si, dans ce cas, loption navait pas ete retenue, les operations sur les reels etaient
implementees logiciellement au prix dun dramatique allongement des temps de calcul.
Toujours est-il que les formats disponibles dans une unite de calcul sur les flottants
dependent de la taille des registres, et ceux-ci sont parfois limites a 64 bits, ce qui in-
terdit le format (( extended )) en natif sur la machine (si le langage de programmation
utilise y donne acces, les operations sont alors implementees logiciellement).
Lorsque le format (( extended )) est disponible en natif dans la machine, les registres
sont en general de taille 96 bits (et non 80).
Les 16 bits supplementaires, sils sont evidemment utilises par le processeur pour
sa cuisine interne, ne sont jamais significatifs dans les resultats accessibles a lutilisa-
teur, et sont mis a 0.
Autrement dit, on obtient le reel au format (( extended )) en supprimant les 16 bits
nuls.
Comme deux nombres dont les expressions binaires comportent le meme nombre
de chiffres nont pas necessairement le meme nombre de chiffre en representation
decimale, le nombre de chiffres significatifs en base 10 peut varier dune unite.
86
E XEMPLE 5. 1000 en base 2 est 8 en decimal : 4 chiffres binaires, 1 chiffre decimal,
1100 binaire est 12 decimal : 4 chiffres binaires, 2 chiffres decimaux.
Ainsi,
en format (( single )), on a 6 ou 7 chiffres significatifs,
en format (( double )), 15 ou 16 chiffres,
en format (( extended )), 19 ou 20.
Une telle precision peut sembler totalement superflue : elle est cependant large-
ment insuffisante pour, par exemple, les calculs en astronomie (trajectoires de satel-
lites, etc.), pour lesquels il est necessaire de faire appel a des precisions nettement
superieures...
Le plus grand nombre reel representable en format (( single )) est tel que
e = 254, donc le veritable exposant est 254 127 = 127
m est constitue de 23 (( 1 )) , la mantisse a donc pour valeur 1, 1 . . . 1, cest-a-dire
1 + 21 + 22 + 23 + + 223 (somme dune progression geometrique de
raison 1/2, donc) = 2 223 .
Il vaut donc exactement 2127 (2 223 ) = 2128 2104 , cest a dire approximati-
vement 3, 403 1038 .
Le plus petit reel positif normalise ((( single )) ) est tel que
e = 1, donc le veritable exposant est 1 127 = 126
m = 0, donc la mantisse vaut 1
Il vaut donc exactement 2126 cest-a-dire approximativement 1, 175 1038 .
Le plus petit reel positif denormalise ((( single )) ) est tel que
e = 0, donc le veritable exposant est 126
m = 0 . . . 01, donc la mantisse vaut 0, 0 . . . 01, soit 223
Il vaut donc exactement 2149 cest-a-dire approximativement 1, 401 1045 .
En format (( double )), les nombres correspondants sont 1, 710308, 2, 310308 , 510324 .
Les reels qui sont representes en machine sont exacts ; par contre, tous les nombres
reels ne sont pas representables (la representation est evidemment discrete).
87
3FFF pour les 16 premiers bits,
8000 hexadecimal pour les 16 suivants,
et tous les derniers sont nuls,
donc : 3FFF 8000 0000 0000 0000.
Le reel representable en machine, superieur a 1 et le plus proche de 1, a evidemment
un m egal a 0 . . . 01, il sagit donc de 3FFF 8000 0000 0000 0001.
La difference des mantisses (i, m) de ces deux nombres est 0, 0 . . . 01, soit (exac-
tement) 263 , ou encore (environ) 1, 08 1019 .
En dautres termes...
Dans lintervalle [1, 2[, les reels representables varient de 263 en 263 .
Dans lintervalle [2, 4[, les reels representables varient de 262 en 262 .
etc.
Dans lintervalle [263 , 264 [, les reels representables varient de 20 en 20 , donc
dunite en unite : on ne peut plus representer que des nombres entiers, mais
il sagit dentiers qui sont plus grands que les entiers de la machine (sur 32 bits
seulement).
Dans lintervalle suivant, on ne peut plus representer tous les entiers, on nen
represente plus quun sur deux, puis un sur quatre, etc.
R EMARQUE 2. Les calculs sur les reels en machine sont exacts dans le sens suivant :
Si, par exemple, on additionne, soustrait ou multiplie deux entiers representables
sous forme de reels en machine, et si le resultat est aussi representable sous forme de
reel en machine, alors ce resultat est exact.
Autrement dit, il sagit encore dun entier exactement.
E XEMPLE 7. Soit a representer 8, 5 sous forme de reel double precision (format (( double ))
)
1. Le ramener entre 1 et 2 par divisions par 2 : 8, 5 = 8 1, 0625.
2. Lexposant est donc 3, et e = 3 + 1023 = 1026, les 12 premiers bits sont donc
0100 0000 0010 (en effet, 1026 = 1024+2, et 1024 est 210 , dont lecriture binaire
est (( 1 )) suivi de 10 (( 0 )) . On rajoute 2, soit 10 binaire).
3. 1, 0625 = 1 + 0, 0625, et 0, 0625 = 24 , soit (en binaire) 0, 0001, donc m =
0001 00 . . .
88
On obtient : 0100 0000 0010 0001 0000 0000 . . ., soit 4021 0000 0000 0000 en
hexadecimal.
Fin du Chapitre
89
Chapitre 6
Cryptologie et arithmetique
Lidee est de doter tous les participants de la meme methode de cryptage. Les
resultats du cryptage dun meme message par divers individus sont cependant differents,
car chacun dentre eux emploie une (( cle )) qui lui est propre.
90
La cle de A est publique, ainsi nimporte qui est en mesure dappliquer la fonc-
tion fA a un message M quelconque.
Par contre, seul A connat la fonction inverse fA1 qui permet de retrouver le
message initial.
Cest ce message (( doublement )) crypte qui est envoye. B le recoit et lui applique
aussitot fB1 , ce quil est le seul a pouvoir faire, pour obtenir fA1 (M), auquel il ap-
plique fA : si le resultat est comprehensible, B est sur que le message lui etait bien
destine, et quil a bien ete envoye par A.
91
P ROPRI ET E I : sil est tres facile dobtenir un tres grand nombre entier compose
par produit de deux nombres premiers eux-memes grands, la decomposition en
facteurs premiers dun nombre compose est tres difficile.
92
2 4 10 + 1
Ici k = = 27, donc M 1327 [55].
3
On a 1327 = 1316+8+2+1 , or 132 4 [55], 134 4 4 16 [55], 138 16 16
256 36 [55] 1316 36 36 1296 21 [55], donc 133 4 13 52 [55] ,
1311 52 36 37 [55], 1327 37 21 7 [55].
Il faut aller chercher bien plus loin pour assurer un minimum de securite. Pour fixer
les idees, les cles utilisees sont a lheure actuelle le produit de deux nombres qui ont
entre 100 et 200 chiffres dans leur representation decimale.
1 Nombres premiers
Pour produire un nombre n utilisable, il faut tout dabord trouver deux nombres p
et q premiers, suffisamment grands.
Il faut verifier quils sont premiers et, pour cela, disposer dun critere de primalite
(voir plus loin).
Lorsque le nombre produit au hasard nest pas premier, il suffit de lui ajouter 2 ,
puis encore 2 etc., jusqua obtenir un nombre premier, ce qui interviendra tres rapide-
ment.
93
2 Decomposition en facteurs premiers
Theoriquement, bien sur, la decomposition dun nombre compose (non premier)
est un probleme resolu : il suffit de tenter de le diviser par tous les nombres premiers
jusqua sa racine carree.
Le seul moyen, donc, pour savoir si un nombre n obtenu comme ci-dessus est une
(( bonne )) cle, est de tenter de le decomposer par tous les algorithmes connus. Sil
resiste vaillamment, on peut ladopter, sinon, il faut en changer.
La conclusion de cette presentation est quil est donc necessaire de disposer dun
test de primalite et dalgorithmes de decomposition en facteurs premiers, questions
que nous allons aborder dans les paragraphes suivants.
94
Chapitre 7
Tests de primalite
I. Theoreme de Fermat
95
en conclut que n est compose.
Les nombres a tels que an1 1 [n] alors que n nest pas premier ne sont pas
nombreux. Cest pourquoi si, apres lessai de quelques valeurs de a, on trouve tou-
jours an1 1 [n], ce nombre n sera envoye a un veritable test de primalite.
On montre que :
Bien entendu, des que n est un tant soit peu grand, il est exclu de tester autant de
bases.
Il nen reste pas moins que si, apres une dizaine de bases, n est pseudo-premier
fort dans chacune de ces bases, il a de (( tres bonnes chances )) detre premier.
Ce test nest cependant pas, lui non plus, un veritable test de primalite, mais il est
presque aussi rapide que celui de Fermat, et il sert daiguillage entre les nombres que
lon enverra a un algorithme de decomposition et ceux que lon enverra plutot a un
veritable test de primalite.
96
P ROPRI ET E III (T EST DE L UCAS ) : Si on peut trouver un entier a pour lequel
n1
an1 1 [n], mais a q 6 1 [n] pour tous les diviseurs premiers q de n 1,
alors n est premier.
R EMARQUE 1. Selfridge a montre quil netait pas necessaire dutiliser la meme va-
leur de a pour tous ces diviseurs.
Ce test est theoriquement satisfaisant (cest un test qui peut repondre : (( oui, n est
premier ))), pratiquement il lest beaucoup moins : il exige la decomposition en fac-
teurs premiers de n 1 qui est une operation en general longue et difficile (voir les
algorithmes qui suivent).
Fin du Chapitre
97
Chapitre 8
I. Divisions successives
Lalgorithme est tres simple : tenter de diviser le nombre par les nombres premiers
successifs, dont on dispose dans un tableau.
Cet algorithme nest pas efficace, mais il est necessaire den disposer : tous les
autres algorithmes, concus pour trouver de (( grands )) diviseurs, connaissent des cas
dechec, qui sont dautant plus frequents que les diviseurs sont petits.
R EMARQUE 1. On pourrait alors envisager aussi daller plus loin, cest-a-dire, par
exemple, de tenter la division par tous les nombres premiers representables sur 32 bits
(cest-a-dire inferieurs a 232 = 4 294 967 296 : 10 chiffres (( seulement )) !).
Il faut alors savoir quil y en a 203 280 221 et que la maniere la plus economique
de les stocker necessite environ 194 Mo...
On nose evoquer le temps dexecution dun algorithme qui parcourrait un tel ta-
bleau. . . pour ne meme pas obtenir de resultat, ce qui est le cas des que le plus petit
diviseur du nombre a decomposer possede plus de 10 chiffres ce qui est fort peu pour
des nombres qui depassent les 100 chiffres decimaux).
Il faut bien saisir sur ces exemples lampleur du probleme !
98
II. Algorithme de Monte-Carlo (1975)
1 Presentation
Cet algorithme, dont lefficacite est tout-a-fait surprenante, utilise un generateur de
nombres au hasard (cest de lintervention de ce (( hasard )) que lalgorithme tire son
nom).
Soit
f cette fonction (le generateur),
A la valeur dinitialisation,
n le nombre a decomposer,
p un de ses facteurs premiers.
R EMARQUE 2. On ne connat pas p, bien sur, mais on sait que ym = xm [p], et cela
suffit.
Soit h la plus grande puissance de 2 qui est inferieure ou egale a m (par exemple,
pour m = 50, h = 32). On peut alors montrer quil existe un entier m tel que ym =
yh1 , cest-a-dire xm xh1 0[p].
2 Lalgorithme
Lalgorithme peut se decrire dans les termes suivants :
99
IMPRIMER n
n n/g
x x%n
x x %n
FINSI
SINON
k k 1
SI ( k = 0) ALORS
x x
h 2h
k h
FINSI
x (x2 + 1)%n
FINSI
JUSQUA (g est different de 1)
FAIT
FIN
On notera que lalgorithme ainsi decrit, si lon ne se trouve pas dans le cas derreur,
(( tourne )) tant quil na pas termine la decomposition du nombre, ce qui peut durer tres
longtemps... Il faut, bien sur, en plus, prevoir un arret au bout dun certain temps.
3 Discussion
Meme si, quelquefois, cet algorithme permet la factorisation de nombres plus grands,
il ne peut pas pretendre arriver a decomposer tous les nombres de 20 chiffres ou moins.
100
On peut reperer plus facilement ceux qui se factorisent aisement (par la methode
precedente, donc qui sont assez petits) en criblant les valeurs de P (x) pour obtenir la
congruence recherchee x2 y 2 [n] de maniere efficace.
Linteret de cette methode est quelle donne ses meilleurs resultats sur les nombres
qui font echouer la suivante, mais elle est tres difficile a programmer : le criblage nest
pas evident, et il y a enormement de (( petites astuces )), qui ne peuvent etre examinees
ici, pour retrouver les congruences recherchees aussi rapidement que possible.
Cest la methode la plus utilisee avec celle, plus recente, des courbes elliptiques.
On peut esperer decomposer des nombres jusqua 70 chiffres a peu pres dans des temps
raisonnables (on veut dire : quelques jours. . . ).
Le cas dechec est celui ou k = 0, on trouve alors que le PGCD est n, et on nob-
tient aucun renseignement sur un eventuel diviseur de n.
Par ailleurs, evidemment, on ne peut pas calculer ap1 quand on ne connat pas p.
Concretement, on opere etape par etape, en utilisant le PPCM des entiers depuis 1
jusqua un maximum fixe.
101
a beaucoup plus de cas dechec avec 2).
2. Le PPCM des entiers depuis 1 jusqua un maximum fixe dans la recherche est
egal a 2 3 2 5 7 2 3 11 13 2 17 19 23 5 3 29 . . .
(Ces nombres figurent dans une table, determinee a lavance, et obtenue par
lalgorithme suivant :
On parcourt les entiers depuis 2 jusquau maximum fixe, tout en disposant de
la table des nombres premiers inferieurs ou egaux a ce meme maximum.
Chaque fois que lon rencontre un nombre premier, on rajoute ce nombre pre-
mier.
Chaque fois que lon rencontre une puissance dun nombre premier, on rajoute
un facteur egal a ce nombre premier, pour completer le PPCM.
On obtient donc 2, puis 3, comme nombres premiers, puis, en passant par 4, on
rajoute un facteur 2, puis 5, premier, rien a rajouter pour 6, puis 7, premier, un
facteur 2 supplementaire en passant par 8, un facteur 3 a la rencontre de 9, etc. . .
Cette table contient 6634 elements pour le PPCM des entiers depuis 2 jusqua
65535, tous les nombres representables sur 16 bits).
102
La capacite de cet algorithme a trouver un diviseur p dun nombre n depend de la
taille du plus grand diviseur de p 1, ce qui explique ses resultats tres inegaux.
E XEMPLE 2. Il trouve instantanement le diviseur p = 1 325 815 267 337 711 173 (19
chiffres decimaux) de R53 , parce que le plus grand diviseur premier de p 1 est 8 941.
Mais il ne peut pas obtenir le diviseur q = 106 007 173 861 643 (15 chiffres decimaux
seulement) de R61 , parce que le plus grand diviseur premier de q1 est 868 911 261 161
(12 chiffres).
Ces considerations, dans loptique du cryptage RSA, montrent que si lon choisit
deux nombres premiers p et q de la forme p = 2p + 1 et q = 2q + 1 ou p et q sont
eux-memes premiers (ce qui est assez facile a fabriquer), il suffira que p et q aient en
gros au moins 12 chiffres pour que le cryptage soit invulnerable par lalgorithme de
Pollard (mais pas par un autre algorithme, peut-etre. . . ).
103
Les coordonnees de P3 sont obtenues comme suit :
y y1
2
si P1 6= P2
x2 x1 x3 = m2 x1 x2
Si on pose m = 2
3x1 + a , alors .
si P1 = P2 y 3 = m(x1 x3 ) y 1
2y1
2 Algorithme de Lenstra
Ici, il sagit de calculer dans Z/nZ, qui nest pas un corps, donc loperation risque
de ne pas etre definie.
Fin du Chapitre
104
Troisieme partie
Logique
105
Chapitre 9
Algebre de Boole
I. Proprietes generales
1 Definition
106
Propriete P(E) A
idempotence AA=A a+a=a
AA=A aa=a
commutativite AB =BA a+b=b+a
AB =BA ab= ba
associativite A (B C) = (A B) C a + (b + c) = (a + b) + c
A (B C) = (A B) C a (b c) = (a b) c
elements neutres A 6 o = A a+0=a
AE =A a1 =a
absorption AE =E a+1=1
A 6 o =6 o a0=0
distributivites A (B C) = (A B) (A C) a (b + c) = a b + a c
A (B C) = (A B) (A C) a + b c = (a + b) (a + c)
involution E \ (E \ A) = A a=a
complementation E\ 6 o = E 0=1
E \ E =6 o 1=0
partition A (E \ A) = E a+a=1
A (E \ A) =6 o aa = 0
(( Lois de De Morgan )) E \ (A B) = (E \ A) (E \ B) a+b =ab
E \ (A B) = (E \ A) (E \ B) ab=a+b
R EMARQUE 1. Les signes operatoires utilises sont les memes que ceux de laddition
et de la multiplication des reels. Cependant, ces operations nont evidemment pas les
memes proprietes, et ne portent pas sur les memes elements.
107
Exercice 2 (Operateurs de Sheffer et de Peirce). Soit (E, +, , ) une algebre de Boole.
1. On definit loperation de Sheffer1 par : a|b = a + b (cest le NAND des informa-
ticiens).
Comment obtenir a, a + b, a b en nutilisant que loperateur | ? Faire de meme
pour a + b ; etudier lassociativite de cette operation.
2. On definit la fleche de Peirce2 par : a b = ab (cest le NOR). Memes questions.
2. Les elements neutres sont notes 0 et 1, par analogie avec les entiers de meme
symbole (ne pas oublier que ces calculs ne se deroulent pas dans R...
4. Il faut shabituer aussi a celle des deux distributivites qui nest pas habituelle,
celle de la somme sur le produit (booleens), et, par exemple, ne pas hesiter a
ecrire directement (a + b)(a + c)(a + d)(a + e)(a + f ) = a + bcdef !
1
Dapres le logicien H.M. Sheffer
2
Lorsque les logiciens, dans les annees 1930, chercherent un symbole pour exprimer le connecteur
decouvert par C.S. Peirce (1839-1914)...Pierce Arrow etait le nom dune celebre marque de voiture !
108
2.2 Regles de (( redondance ))
Dans une expression booleenne, une sous-expression est dite (( redondante )) lors-
quon peut la supprimer sans changer la (( valeur )) de lexpression :
1. Dans une somme booleenne, tout terme absorbe ses multiples.
Autrement dit : a + a b = a.
P REUVE En effet, a + a b = a (b + b) + a b = a b + a b + a b =
a b + a b (par idempotence) = a (b + b) = a.
2. Dans un produit booleen, tout facteur absorbe tout autre facteur qui le contient
en tant que terme.
Autrement dit : a (a + b) = a.
P REUVE En effet, a (a + b) = a a + a b = a + a b = a.
a+ab =a+b
P REUVE a + a b = (a + a) (a + b) = 1 (a + b) = a + b.
E XEMPLE 1. ab + ac + bc = ab + (a + b) c = ab + ab c = ab + c
R EMARQUE 3. Lapplication de cette troisieme regle peut etre combinee avec celle
des autres, comme par exemple dans le calcul suivant :
a b + a c + b.c = a b + a c
P REUVE a b + a c + b c = a b + a c + (a + a) b c = a b + a c + a b c + a b c ;
a b absorbe a b c et a c absorbe a b c, dou le resultat.
109
Exercice 4 (Calcul booleen elementaire). Effectuez les calculs suivants :
1. (a + b) (b + c) (c + a)
2. (a + b) (a + c) + (b + c) (a + b) + (a + c) (b + c)
3. (a + b + c) (a + b + c) (a + b + c)
4. a + a b c + a + a b
5. a b + a b c + a b c
6. a b + a b c + a b c d
7. (a + b + c) (a + b + c + d)
110
D EFINITION 2 (F ONCTION BOOL EENNE ). On appelle fonction booleenne de n va-
riables toute application de An dans A dont lexpression ne contient que :
les symboles des operations booleennes,
des symboles de variables, de constantes,
deventuelles parentheses.
E XEMPLE 2. f (a, b, c) = a b + c.
R EMARQUE 4. Si a est une variable booleenne, elle peut intervenir dans lexpression
dune fonction booleenne sous la forme a ou sous la forme a, qui sont appelees les
deux aspects de cette variable : affirme et nie.
111
E XEMPLE 3 (M INTERME A TROIS VARIABLES ). abc
Exercice 7. Dressez la liste des mintermes et des maxtermes pour deux variables a et
b.
(n)
N OTATION (R EPR ESENTATION DES MINTERMES ) : On les represente par mi pour
(n)
un minterme, et Mi pour un maxterme.
Lindice i varie entre 0 et 2n 1, et fait lobjet dune convention de numerotation
des mintermes (et maxtermes).
Pour que cette numerotation ait un sens, il est indispensable dadopter un ordre
denumeration des variables, et, une fois que celui-ci a ete defini, de sy tenir une fois
pour toutes.
112
La convention est la suivante : a chaque variable, on associe 0 ou 1 selon que cette
variable apparat sous son aspect nie ou sous son aspect affirme dans lexpression du
minterme.
En ecrivant ces chiffres les uns a cote des autres, et dans le meme ordre que les
variables correspondantes, on obtient une expression quon peut considerer comme
lecriture dun entier positif en base 2.
113
E XEMPLE 7. a b c = a + b + c
Autrement dit,
114
R EMARQUE 5. On prend la negation de chacun des membres de legalite, et lon ob-
(n) (n)
tient : si i 6= j, alors Mi + Mj = 1. Ainsi, la somme de deux maxtermes distincts
vaut 1.
115
P REUVE En effet, comme elle ne fait intervenir que les trois operations booleennes,
il suffit de lui appliquer les regles du calcul booleen.
On developpe les negations (en appliquant les regles a + b = a b et a b =
a + b), jusqua ce quil ny ait plus de negations que sur les variables.
Puis on developpe les produits qui portent sur des sommes, en utilisant la distri-
butivite du produit sur la somme.
On obtient ainsi une expression qui secrit sans parentheses, et qui ne contient
que des sommes de produits de variables eventuellement niees.
P ROPRI ET E VII : Chaque monome peut ensuite etre mis sous la forme dune
somme de mintermes.
P REUVE 2 :
En effet, si, dans lexpression de ce monome, toutes les variables interviennent,
cest deja un minterme.
Dans le cas contraire, il manque (par exemple) la variable a dans son expres-
sion : on la fait intervenir sous la forme (a + a). On developpe, les deux monomes
obtenus font intervenir la variable a.
Ou bien, il sagit de mintermes et le processus est termine, ou bien il manque
encore une variable, quon fait intervenir en utilisant le meme procede, et ainsi de
suite jusqua aboutir aux mintermes.
116
P ROPRI ET E IX (F ORME CANONIQUE CONJONCTIVE ) : Toute fonction
booleenne de n variables (autre que la fonction referentiel) peut se mettre
sous la forme dun produit de maxtermes a n variables.
Cette forme, unique, est la Forme Canonique Conjonctive (FCC dans la suite).
R EMARQUE 8. Si on prend la negation de la FCD, on obtient bien sur une FCC... mais
pas celle de la fonction, celle de sa negation !
Il suffit de prendre la negation de la fonction, de calculer sa FCD puis de prendre
la negation du resultat.
Il existe une autre methode pour obtenir ces formes canoniques : la methode des
diagrammes.
117
III. Representation et simplification des fonctions
1 Diagrammes de Karnaugh
1.1 Presentation
La representation des fonctions booleennes par diagrammes de Karnaugh-Veitch :
est fondee sur les proprietes des mintermes (ils realisent une partition de lunite),
et est copiee de la representation des ensembles par diagrammes dEuler-Venn
(les fameuses (( patates ))).
Ces derniers diagrammes deviennent rapidement inextricables quand le nombre
de variables augmente, cest pourquoi, dans les diagrammes de Karnaugh, on divise
systematiquement l(( univers )) (le referentiel E) en deux parties egales en superficie
pour representer la partie concernee et son complementaire.
A chaque introduction de variable supplementaire, chaque case du precedent dia-
gramme est divisee en 2.
a a
b ab ab
b ab ab
0 0 2
1 1 3
118
H
HH ab
HH 00 01 11 10
c H
0 0 2 6 4
1 1 3 7 5
HH
H ab 00 01 11 10
cd HHH
00 0 4 12 8
01 1 5 13 9
11 3 7 15 11
10 2 6 14 10
Dans un tel diagramme, chaque case represente un minterme. Les autres monomes
regroupent un nombre de cases qui est une puissance de 2, selon le nombre de variables
presentes.
Reponse :
HH
HHabc 000 001 011 010 110 111 101 100
de HH
00 0 4 8 12 28 24 20 16
01 1 5 9 13 29 25 21 17
11 3 7 11 15 31 27 23 19
10 2 6 10 14 30 26 22 18
119
Cest-a-dire :
les quatre premieres colonnes correspondent a a, les quatre dernieres a a,
les deux premieres, et les deux dernieres colonnes correspondent a b, les quatre
centrales a b,
les colonnes 1, 4, 5 et 8 a c, les autres a c,
les deux premieres lignes a d, les deux dernieres a d,
enfin, la premiere et la derniere ligne sont associees a e, les deux centrales a e.
1.2 Utilisation
Les diagrammes peuvent etre utilises (( en reunion )) comme (( en intersection )).
Ils permettent :
dobtenir la FCD dune fonction booleenne plus aisement que par le calcul
algebrique (utilise pour decouvrir la forme en question),
une premiere approche du probleme de la simplification des fonctions booleennes
(dans des cas simples et pour un petit nombre de variables)...
Utilisation des diagrammes de Karnaugh pour representer les fonctions booleennes...
En reunion . Soit par exemple f (a, b, c) = a + bc. Son diagramme est :
H
HH ab
HH 00 01 11 10
c H
0 0 2 6 4
1 1 3 7 5
H
HH ab
HH 00 01 11 10
c H
0 0 2 6 4
1 1 3 7 5
La representation de f est contenue dans les cases rouges possedant les nombres
en italique et gras : on retrouve la meme FCD.
120
En complementation . Soit f (a, b, c) = a + bc, de diagramme :
H
HH ab
HH 00 01 11 10
c H
0 0 2 6 4
1 1 3 7 5
Alors la negation de a + bc est dans les cases pas rouge : la FCD de f est m0 +
m2 + m3 .
f (a, b, c, d, e) = a [b e (c + d) + b (c d e + c d e)].
La simplification des fonctions booleennes doit etre laissee aux methodes algebriques
dans les cas plus complexes, de maniere a pouvoir affirmer avoir trouve une forme mi-
nimale, et eventuellement toutes, si necessaire.
Il existe diverses methodes, nous nen exposerons ici quune seule, la methode de
Quine-Mac Cluskey, dite aussi methode des consensus.
Le consensus de ces deux monomes est alors le produit de toutes les autres va-
riables des deux.
121
E XEMPLE 13. Les monomes a b d e et a c d f presentent un consensus, car le
premier contient a et le second a.
Le consensus de ces deux termes est b c d e f .
E XEMPLE 14. abc et bcd presentent un consensus (acd), quand abc et bcd dune part,
et abc et bcd dautre part, nen presentent pas.
Etape preliminaire Developper lexpression pour quelle soit sous forme de somme
de monomes, et en suppprimer les termes redondants (par idempotence et application
de la regle n1) : on obtient ainsi lexpression de depart.
Toute autre tentative de simplification est, dans cette etape, parfaitement inutile.
122
Obtention dune forme stable par consensus Repeter les deux phases suivantes
jusqua ce que lexpression obtenue ne soit plus modifiee :
1. Rajouter tous les consensus des termes qui en presentent.
2. Supprimer les termes redondants introduits (idempotence et regle n1 exclusive-
ment).
E XEMPLE 15. Dans a + a b, les deux termes presentent un consensus, qui est b, et
on a alors a + a b = a + a b + b = a + b (comme on le sait, cest la regle n3).
Ici, il y a simplification.
E XEMPLE 16. Mais dans a b + a c, les deux termes presentent un consensus, qui est
b c, on a alors a b + a c = a b + a c + b c.
Ici, il apparat un terme de plus.
123
Choix dun nombre minimal de monomes principaux On calcule la FCD de la
fonction booleenne a simplifier.
Pour chacun des mintermes de cette forme, on dresse la liste des monomes princi-
paux qui le contiennent (dont ce minterme est un multiple).
Toute forme egale a lexpression donnee doit contenir tous les mintermes (cest-a-
dire, pour chacun dentre eux, au moins un des monomes principaux qui le contiennent).
Exprimer que ce minterme doit etre contenu dans toute forme representant la fonc-
tion booleenne a simplifier se fait en posant lequation booleenne dont le premier
membre est la somme des variables booleennes associees aux monomes principaux
qui contiennent ce minterme et dont le second membre est 1.
Ensuite, on forme le produit des premiers membres de ces diverses equations (en
algebre de Boole, un produit ne peut etre egal a 1 que si tous ses facteurs sont egaux a
1).
Trouvez sa FCD.
En deduire ses formes minimales.
f (a, b, c) = (a + b)(a + b + c)
124
1. On developpe : f (a, b, c) = ab + ac + ab + bc.
Il ny a pas de simplification possible par idempotence et regle 1 : cest donc
notre expression de depart.
2. Obtention dune forme stable par consensus.
ab, ac : pas de consensus,
ac, ab : consensus bc,
ab, ab : pas de consensus,
ac, bc : pas de consensus,
ab, bc : consensus ac,
ab, bc : pas de consensus,
Dou f (a, b, c) = ab + ac + ab + bc + ac + bc.
Par idempotence : f (a, b, c) = ab + ac + ab + bc.
Rajouter des consensus ne change alors rien : cest notre forme stable.
Soient p1 , p2 , p3 , p4 les quatre monomes principaux.
3. La FCD...
HH
HH ab 00 01 11 10
c HH
0 0 2 6 4
1 1 3 7 5
Dou la FCD : m2 + m3 + m4 + m5 + m7 .
4. Choix dun nombre minimal de monomes principaux :
hhhh
hhh mintermes
hhhh
2 3 4 5 7
monomes principaux hhhhhhh
1 X X
2 X X
3 X X
4 X X
p3 p3 p1 p1 p2
p4 p2 p4
Tout minterme de la FCD doit etre pris au moins une fois. Donc :
125
pour avoir m2 , pas le choix : il faut prendre p3 . Mais, comme on a pris p3 , on
a recupere m3 .
pour avoir m4 , il faut prendre p1 . Avec cela, on recolte m5 .
enfin, pour avoir m7 , on a le choix entre p2 et p4 .
Il y a donc deux formes minimales :
p1 , p2 , p3 ,
p1 , p3 , p4 .
Deuxieme exercice :
Exercice 18. Appliquez la methode des consensus a
S = ab+ac
Posons :
P1 = a b,
P2 = a c
P3 = b c.
La FCD de S est m1 + m3 + m6 + m7 .
m1 est contenu dans P2 . Le choix de P2 est donc obligatoire, ce que lon exprime
par lequation booleenne p2 = 1.
m3 est contenu dans P2 et P3 . On a donc le choix entre ces deux monomes, ce
que lon exprime par lequation booleenne p2 + p3 = 1 (evidemment, le choix
precedent rend cette condition inutile, mais on expose ici la methode).
m6 est contenu dans P1 , soit p1 = 1.
m7 est contenu dans P1 et P3 , soit p1 + p3 = 1.
Il faut donc developper le produit p2 (p2 + p3 )p1 (p1 + p3 ) = p1 p2 qui prouve que la
forme minimale (unique, dans cet exemple) de la fonction donnee est obtenue avec la
somme de P1 et de P2 ; il sagit, bien entendu, de a b + a c.
Troisieme exercice :
Exercice 19. Appliquez la methode des consensus a
S = ac+abd+abc+abc+bcd+abc
126
1. Suppression des multiples : a c absorbe a b c
Il reste :
ac+abd+abc+abc+bcd
2. Premiers consensus :
ac+abd+abc+abc+bcd+bcd+ab+bc+abd+b
cd+acd+acd+acd+abd
4. Nouveaux consensus (on na fait figurer quune seule fois chacun dentre eux) :
ac+abd+bcd+bcd+ab+bc+abd+bcd+acd+acd+acd+
abd+abd+cd+ad+bcd+bd+abc+b d+bcd+abc+abc+cd
6. Nouveaux consensus (on na fait figurer quune seule fois chacun dentre eux) :
ac+ab+bc+cd+ad+bd+abc+bd+cd+bc+abd+bcd+acd
8. Un dernier tour de consensus montre que cette expression est stable par consen-
sus.
127
A laide dun diagramme de Karnaugh, on determine les mintermes contenus dans
chacun des monomes principaux.
On en deduit la FCD, et, dans le tableau qui suit, on fait apparatre les monomes
principaux et les mintermes quils contiennent :
```
```minterme m0 m1 m2 m4 m5 m6 m7 m8 m9 m10 m13 m14 m15
monome ```
`
P1 = a c
P2 = a b
P3 = b c
P4 = c d
P5 = a d
P6 = b d
P7 = b d
P8 = c d
P9 = b c
La premiere colonne, par exemple, sinterprete comme suit : dans toute forme
(reduite ou non) pretendant representer lexpression donnee au depart, il est necessaire
quun monome au moins contienne le minterme m0 , puisque ce dernier figure dans la
FCD.
Cette condition peut etre realisee en choisissant le monome principal P1 , ou P3 , ou
P5 , ou P7 . Elle peut etre exprimee par lequation booleenne p1 + p3 + p5 + p7 = 1, etc.
On obtient lequation booleenne :
On developpe le produit, mais pas le premier facteur, car il est le seul a contenir
les monomes principaux p1 , p2 et p5 , donc on sait deja quil faudra en prendre un (et
un seul, pour une forme minimale...) des trois.
On obtient
(p1 +p2 +p5 )(p3 +p4 p7 )(p8 +p7 p9 )(p6 +p4 p9 ) = (p1 +p2 +p5 )(p3 p8 p3 p7 p9 +p4 p7 p8 +
p4 p7 p9 )(p6 + p4 p9 ) = (p1 + p2 + p5 )(p3 p6 p8 + p3 p4 p8 p9 + p3 p6 p7 p9 + p3 p4 p7 p9 +
p4 p6 p7 p8 + p4 p7 p8 p9 + p4 p6 p7 p9 + p4 p7 p9 ) = (p1 + p2 + p5 )(p3 p6 p8 + p3 p4 p8 p9 +
p3 p6 p7 p9 + p4 p6 p7 p8 + p4 p7 p9 ) = 1
128
On constate quil est possible de realiser la condition de la seconde parenthese en
ne choisissant que 3 monomes principaux : P3 , P6 et P8 , ou encore P4 , P7 et P9 (les
autres choix possibles en necessitent 4).
En plus, il faut choisir lun des trois de la premiere parenthese, comme on la dit
plus haut.
ac
bc+bd+cd ou
ou + ab
cd+bd+bc ou
ad
f (x1 , x2 , . . . , xn ) = g(x1 , x2 , . . . , xn )
F (x1 , x2 , . . . , xn ) = x1 r + x1 s = 0
Cette derniere equation est equivalente, en algebre de Boole, aux deux equations
(1) x1 r = 0
(2) x1 s = 0
3. Une equation du type de (2) se resout par introduction dune variable auxiliaire
y1 . En effet,
x1 s = 0 y1 E, x1 = y1 s
.
4. Dans ces conditions, x1 = y1 + s, valeur que lon porte dans (1), pour obtenir
lequation y1 r + r s = 0, qui est elle-meme equivalente aux deux equations
129
(3) y1 r = 0
.
(4) r s = 0
z1 E, y1 = z1 + r
2 Exercice
nx + y = x + z
Exercice 22. Resoudre le systeme dequations :
xy =xz
V. Exercices
Exercice 23 (Methode des consensus). Utiliser la methode des consensus pour obte-
nir toutes les formes minimales des fonctions booleennes suivantes :
1. Celles des precedents exemples et exercices.
2. d e + a c + b c + a b + a d e + a d e
130
Exercice 24. Pour chacune des expressions suivantes...
Reponse : xz + E = E, x + E 6= E et z + E 6= E.
131
3. Donner une forme minimale pour w
Exercice 30. On definit, dans {0, 1}, trois lois de composition, de maniere que, x
E, on ait fA (x) fB (x) = fAB (x), fA (x) + fB (x) = fAB (x) et fA (x) = fE\A (x).
Montrer que ({0, 1}, +, , ) est une algebre de Boole binaire.
Fin du Chapitre
132
Chapitre 10
Calcul Propositionnel
I. Introduction
1 Objets de la logique
Lobjet de la Logique est danalyser le raisonnement humain et, si possible, de le
formaliser de maniere a le rendre aussi independant que possible des diverses contin-
gences materielles qui pourraient influer sur lui.
Cest surtout le deuxieme aspect qui nous occupera dans ce chapitre (et les sui-
vants).
2 Production automatique
Chacun sait que, si un ordinateur calcule vite et bien, il est parfaitement incapable
de produire de lui-meme quelque (( raisonnement )) que ce soit.
Mais sil etait possible de programmer les raisonnements etudies par la logique
sous forme de calculs, precisement, il serait raisonnable de penser que lordinateur
serait alors, de ce point de vue aussi, bien plus rapide et efficace que lesprit humain.
133
Les divers domaines de recherche de ce que lon appelle de nos jours l(( Intelli-
gence Artificielle )) convergent presque tous vers ce but.
Meme si certains espoirs ont ete decus, comme dans le domaine de la traduction
automatique (on arrive tout juste a traduire quelques textes techniques (( standard )), et
il savere tres difficile de (( donner le sens des nuances )) a un algorithme...), de nom-
breux resultats interessants et prometteurs ont ete obtenus dans divers autres domaines
(diagnostic medical, etc.)
Il faut apprendre a dissequer nos demarches intellectuelles, et, avant tout, ne pas se
laisser paralyser par l(( evidence )) : rien ne lest pour un ordinateur. Le plus difficile
est peut-etre de pourchasser, pour les expliciter clairement, tous les sous-entendus qui
nous permettent de produire des raisonnements intelligibles.
Dune maniere generale, ce discours est articule en phrases, dun niveau de com-
plexite variable, et cest letude de ces (( enonces )) que se propose de faire la logique.
D EFINITION 1 (P ROPOSITION ). Parmi tous les enonces possibles qui peuvent etre
formules dans une langue, on distingue ceux auxquels il est possible dattribuer une
(( valeur de verite )) : vrai ou faux.
134
E XEMPLE 1. Ainsi, (( Henri IV est mort assassine en 1610 )), (( Napoleon Bonaparte a
ete guillotine en 1852 )) sont des propositions, puisquon peut leur attribuer une valeur
de verite ((( vrai )) pour la premiere, (( faux )) pour la seconde).
R EMARQUE 2. Ce nest pas la logique qui decide de ce qui est vrai et de ce qui est
faux : les valeurs de verite sont attribues en-dehors de la logique.
Exercice 1. Si je dis : (( la presente affirmation est vraie )), cette affirmation possede-
t-elle une valeur de verite ?
En effet, il est impossible dattribuer une valeur de verite a ces enonces : nous les
rejetons en dehors du cadre des propositions.
135
1.5 Dautres logiques
Il existe, bien entendu, dautres logiques :
Ces (( membres de phrases )) sont relies entre eux par des (( connecteurs logiques )),
de la maniere suivante...
On suppose quil est possible dattribuer une valeur de verite a cet enonce (( glo-
bal )), ce qui le classe parmi les propositions.
Ces propositions, au sens grammatical du terme, sont reliees entre elles par (( parce
que )) et par (( ou )), qui sont grammaticalement parlant des conjonctions (respective-
ment de subordination et de coordination) :
parce que : introduit habituellement un lien de (( cause a effet )),
ou : se contente de juxtaposer les propositions (au meme niveau).
136
mon manque de travail,
lexcessive difficulte du cours )).
E XEMPLE 2. En logique des propositions, les propositions (( il y a des gens qui font
ceci ou cela )) et (( les gens font ceci ou cela )) sont simplement differentes, et les connec-
teurs logiques ne permettent pas detablir un rapport semantique (au niveau du sens)
entre les deux.
Les connecteurs logiques sont donc des symboles qui permettent de produire des
propositions ((( plus complexes ))) a partir dautres propositions ((( plus simples ))).
Ils sont definis (axiomatiquement) a partir de leurs tables de verite.
137
P Q P Q
F F F
F V V
V F V
V V V
138
P P
F V
V F
P Q P Q
F F V
F V V
V F F
V V V
139
equivalence logique : Connecteur (( si et seulement si )), notation : .
2.4 Exercices
Exercices corriges
140
1. (( Pierre fait des Maths et de lAnglais mais pas de Chimie ))
2. (( Pierre fait des Maths et de la Chimie mais pas a la fois de la Chimie et de
lAnglais ))
3. (( Il est faux que Pierre fasse de lAnglais sans faire de Maths ))
4. (( Il est faux que Pierre ne fasse pas des Maths et fasse quand meme de la chimie ))
5. (( Il est faux que Pierre fasse de lAnglais ou de la Chimie sans faire des Maths ))
6. (( Pierre ne fait ni Anglais ni Chimie mais il fait des Maths ))
Reponses :
1. Sil pleut demain ou sil fait froid je sortirai
2. Le nombre 522 est divisible par 3 ou il nest pas divisible par 7
3. Ce quadrilatere est un rectangle ou un losange
4. Paul nira pas travailler ce matin mais il ne perdra pas son emploi
5. Il existe un nombre entier impair divisible par 2
6. Il existe un triangle equilateral dont les angles ne sont pas egaux a 60
141
3. vaut 4 implique que la somme des angles dun triangle vaut 182
4. Il nest pas vrai quun entier impair ne puisse pas etre divisible par 6
5. Si 2 est plus grand que 3 alors leau bout a 100C
6. Si 6 est plus petit que 7 alors 7 est plus petit que 6
7. Si 7 est plus petit que 6 alors 6 est plus petit que 7
8. 84 est divisible par 7 implique que 121 est divisible par 11
9. Si 531617 + 1 est divisible par 7 alors 531617 + 1 est plus grand que 7
10. Si 531617 + 1 est divisible par 7 alors 531617 13 est divisible par 43
11. La decimale de qui porte le numero 10400 est 3 implique que si ce nest pas 3
alors cest 3.
Reponses : F ; V ; V ; F ; V ; F ; V ; V ; V ; F ; V.
142
Exercice 10. Les variables propositionnelles N et T serviront, dans cet exercice, a
representer (respectivement) les propositions (( Un etudiant a de bonnes notes )) et (( Un
etudiants travaille )).
A laide des variables propositionnelles N et T , formaliser les propositions sui-
vantes (si, pour lune ou lautre dentre elles, la traduction vous parat impossible,
dites-le et expliquez pourquoi) :
1. Cest seulement si un etudiant travaille quil a de bonnes notes.
2. Un etudiant na de bonnes notes que sil travaille.
3. Pour un etudiant, le travail est une condition necessaire a lobtention de bonnes
notes.
4. Un etudiant a de mauvaises notes, a moins quil ne travaille.
5. Malgre son travail, un etudiant a de mauvaises notes.
6. Un etudiant travaille seulement sil a de bonnes notes.
7. A quoi bon travailler, si cest pour avoir de mauvaises notes ?
8. Un etudiant a de bonnes notes sauf sil ne travaille pas.
Exercice 11. Combien de lignes contient la table de verite dune forme proposition-
nelle qui depend de n variables ?
143
Reponse : 2n .
P ROPRI ET E I : Les regles (de syntaxe) qui permettent de former des formes pro-
positionnelles correctes sont les suivantes :
Toute variable propositionnelle est une forme propositionnelle
Si F et G sont des formes propositionnelles, alors (F ), (F ) (G), (F )
(G), (F ) (G) et (F ) (G) sont des formes propositionnelles.
144
R EMARQUE 9. Limplication nest pas associative : A (B C) 6= (A
B) C. Donc les parentheses sont obligatoires.
Il en est de meme pour eqv, et a fortiori quand ces deux operateurs sont melanges
dans une meme proposition.
Exercice 12. Quelles sont les facons de placer des parentheses dans p q r afin
dobtenir lexpression correcte dune forme propositionnelle ? Determiner la table de
verite de chacune des formes obtenues. Que remarque-t-on quand les trois propositions
sont fausses ?
p q r 1 2 3 4 5
V V V F F F F V
V V F V V F F F
V F V F F F F V
V F F F F F F F
F V V V F F V V
F v F V V F F F
F F V V F F V V
F F F V V V V V
On remarque que la proposition obtenue est vraie quelle que soit la facon de placer les
parentheses.
3.3 Exercices
Exercices corriges
Exercice 13. Construire les tables de verite des formes propositionnelles suivantes :
1. (p) q
2. (p) (p q)
3. ((p) (q))
4. (p q) (q)
5. (p q) (q p)
6. (p (q)) (q (p))
145
7. (p (q)) ((p) q)
8. p ((p) p)
Reponse :
p q 1 2 3 4 5 6 7 8
V V F V V F V F V V
V F F V V V V V F V
F V V V V V V V F V
F F F F F V V V V V
Reponse :
p q r 1 2 3 4 5 6 7 8
V V V V V V V V V V V
V V F V V V F F F V V
V F V V V V V V V F V
V F F V V V F V F V V
F V V V F V V V V V V
F V F V V F V V V V V
F F V F V V V V V V V
F F F V V V V V V V V
146
Exercices sans correction
Exercice 17 (Mes idees sur les chaussons aux pommes). Toujours pareil avec
1. Toute idee de moi qui ne peut sexprimer sous forme de syllogisme est vraiment
ridicule.
2. Aucune de mes idees sur les chaussons aux pommes ne merite detre notee par
ecrit.
3. Aucune idee de moi que je ne parviens pas a verifier ne peut etre exprimee sous
forme de syllogisme.
147
4. Je nai jamais didee vraiment ridicule sans la soumettre sur le champ a mon
avocat.
5. Mes reves ont tous trait aux chaussons aux pommes.
6. Je ne soumets aucune de mes idees a mon avocat si elle ne merite pas detre
notee par ecrit.
148
Si F est de la forme P , ou P est une variable propositionnelle, alors F (p) = p.
E XEMPLE 5. Si F = P Q, alors F = p + q.
E XEMPLE 6. Si G = Q P , alors G = Q + P = q + p.
R EMARQUE 10. On remarque que les deux fonctions de verites des exemples precedents
sont identiques. On en deduit que F et G sont logiquement equivalentes. G est appelee
implication contraposee de limplication F .
R EMARQUE 11. Il est clair que les (( tables de verite )) des connecteurs logiques sont
les memes que les tables des operations booleennes sur {faux,vrai}...
de la negation booleenne (pour la negation logique),
de la somme booleenne (pour la disjonction logique),
149
du produit booleen (pour la conjonction logique),
de la fonction booleenne de deux variables appelee (( implication )) (pour lim-
plication logique)
de la fonction booleenne de deux variables appelee (( equivalence )) (pour lequivalence
logique).
Ainsi, la determination de la valeur de verite dune proposition composee se ramene
a un simple calcul en algebre de Boole sur la fonction de verite de la forme proposi-
tionnelle associee.
Ainsi, une tautologie est une forme propositionnelle dont la fonction de verite est
independante des valeurs de verite associees a ses variables.
Autrement dit, quelle que soit la valeur de verite des propositions par lesquelles on
remplacerait les variables propositionnelles, la proposition obtenue serait vraie.
N OTATION : La notation utilisee pour marquer une tautologie F est |= F (se lit : (( F
est une tautologie ))).
E XEMPLE 8. Soit F = A A.
F (a) = a + a = 1, donc : |= F (F est une tautologie).
Par exemple : (( Si un etudiant est serieux, alors il est serieux )).
150
Exercice 19. Les formes propositionnelles suivantes sont-elles des tautologies ?
1. (p q) p
2. (p q) (p q)
3. (p q) (p q)
4. p (p q)
5. p ((p) p)
6. p (p q)
7. p (p p)
8. (p q) ((q r) (p r))
2.2 Antilogies
R EMARQUE 12. Le caractere dantilogie dune forme propositionnelle nest pas tou-
jours aussi evident.
151
N OTATION : On note ce resultat : F |= A (se lit : A est consequence logique de F ).
P Q P Q
F F V
F V V
V F F
V V V
Exercice 20. Dans chacun des cas suivants, que peut-on dire dune forme proposi-
tionnelle :
1. qui a pour consequence une antilogie,
2. qui a pour consequence une tautologie,
3. qui est consequence dune antilogie,
4. qui est consequence dune tautologie.
{P, P Q}
152
Exercice 21. Dans chacun des cas suivants, determiner si la premiere forme a pour
consequence logique la deuxieme forme (celle qui est sur la meme ligne) :
1 pq p
2 q p q
3 (p q) p
4 (p q) r p (q r)
5 (p q) (q r) p (q r)
6 p (q r) p r
7 p (q r) p q
8 (p q) r (p r) (q r)
9 p (q r) (p q) (p r)
{F } |= G et {G} |= F F G.
Cest cette notion de formes equivalentes qui autorise le remplacement dune ex-
pression par une autre (equivalente, bien sur) dans une forme propositionnelle.
E XEMPLE 13. On est autorise a remplacer A par A, puisque ces formes sont equi-
valentes.
2.5 Exercices
153
Exercice 22. Dans chacun des cas suivants, dire si les deux formes propositionnelles
inscrites sur la meme ligne sont equivalentes :
1 (p) p
2 p (p q) pq
3 p q (p) (p q)
4 p q (p) (q)
5 pq ((p) (q))
6 pq ((p) (q))
7 p ((p q)) ((p) q)
8 p (q r) (p q) r
9 p (q r) (p q) (p r)
10 p (q r) (p q) (p r)
11 (p q) (q p) (p q) (p q)
12 (p q) (q r) (r p) (p q) (q r) (p r)
Exercice 23. La forme propositionnelle f etant fixee, que peut-on dire dune forme
propositionnelle g qui possede chacune des deux proprietes :
f g est une tautologie,
f g est une antilogie.
Exercice 24. Soit f une forme propositionnelle dependant de trois variables p, q, r qui
possede deux proprietes :
f (p, q, r) est vraie si p, q, r sont toutes les trois vraies,
la valeur de verite de f (p, q, r) cha nge quand celle dune seule des trois va-
riables change.
Construire la table de verite de f , et determiner une formule possible pour f .
154
p q r f
V V V V
V V F F
V F V F
V F F V
F V V F
F V F V
F F V V
F F F F
Formule : (p q r) (p (q) r) (p q (r)) ((p) q r)
p q r f p q r g p q r h
V V V V V V V F V V V V
V V F F V V F V V V F V
V F V V V F V V V F V V
V F F F V F F F V F F F
F V V F F V V F F V V F
F V F V F V F V F V F V
F F V V F F V V F F V V
F F F V F F F F F F F V
Reponses :
f = (pqr)(p(q)r)((p)q(r))((p)(q)r)((p)(q)(r))
g = (p q (r)) (p (q) r) ((p) q (r)) ((p) (q) r)
h = (p q r) (p q (r)) (p (q) r) ((p) q (r)) ((p) (q)
r) ((p) (q) (r))
155
Supposons que lon remplace ces variables par des formes propositionnelles
G1 , G2 , G3 ,. . . , Gn ; la nouvelle forme propositionnelle obtenue est notee F .
P REUVE F etant une tautologie, sa fonction de verite ne depend pas des valeurs de
verite des variables propositionnelles, qui peuvent donc etre remplacees par nim-
porte quelle fonction booleenne.
Ce resultat peut evidemment etre applique aussi a des parties de formes proposi-
tionnelles, pour accelerer le calcul de leurs fonctions de verite :
Si une partie dune forme propositionnelle constitue a elle seule une tautologie,
la partie correspondante de la fonction de verite peut etre avantageusement remplacee
par 1.
156
P ROPRI ET E V (T H EOR EME DE LA VALIDIT E ) : Soit {G1 , G2 , . . . , Gn } un en-
semble de formes propositionnelles et H une forme propositionnelle ; alors :
{G1 , G2 , . . . , Gn } |= H si et seulement si {G1 , G2 , . . . , Gn1 } |= Gn H
{A (B C)} |= (A B) (A C).
157
Une nouvelle application de ce meme theoreme nous montre que la demonstration
demandee est encore equivalente a celle de :
Et enfin a celle de :
{A (B C), (A B), A} |= C.
{A (B C), (A B), A} |= C,
4 Conclusion
Le calcul sur les fonctions de verite parat tout-a-fait satisfaisant et seduisant, lors-
quil sagit de calculer des valeurs de verite ou dexaminer des consequences logiques.
Il est vrai quil est simple, necessite un minimum de reflexion (tres important dans
le cas des ordinateurs !) et quil est tres facile a programmer.
158
Il ne faut cependant pas exiger que ce temps demeure raisonnable des quil
sagit dexecuter un algorithme un peu complique. Et 32 variables constituent
un nombre ridiculement petit pour un systeme expert, dans lequel les expres-
sions offrent souvent une complexite qui na aucune commune mesure avec ce
que lon peut imaginer de plus complique. . .
Les (( raccourcis )) qui viennent detre etudies et qui permettent daccelerer, voire
de supprimer totalement, le calcul dune fonction de verite, sont plus utiles lorsque
lon opere (( a la main )) que pour la programmation dalgorithmes de logique.
Il faut donc garder en reserve la methode des fonctions de verite : celle-ci peut
etre tres utile dans certains cas, essentiellement lorsque le probleme peut etre resolu
(( a la main )), mais il faut aussi trouver une autre methode pour songer a aborder des
problemes plus complexes.
Cette methode, qui supprime toute reference aux valeurs de verite, fait lobjet du
paragraphe suivant.
5 Exercices
5.1 Sur les fonctions de verite
Exercice 27. Calculer les fonctions de verite des formes propositionnelles suivantes,
et dire sil sagit eventuellement de tautologies ou dantilogies :
159
(A B) (A B) B
(A C) (B D) (A B) C D
(A B) A B C
(A C) (B D) (A B C D)
(A C) (B D) (A B C D)
(A B) (A C) (B C)
((B C) (C A) (B C) (C A)) ((A C)
(A B))
(A B) (C (A B))
A A (B C (C A))
((A B) A) A
(A C) (B D) (C D) A B
A (A B) A
(A B (A A B)) (A B (A (A B)))
(A B) (A C) B C
(A B) (A C) (A C)
Exercice 28 (Le club des Ecossais). Pour constituer un club, on a enonce le reglement
suivant :
Article 1 : Tout membre non Ecossais porte des chaussettes oranges.
Article 2 : Tout membre porte une jupe ou ne porte pas de chaussettes oranges.
Article 3 : Les membres maries ne sortent pas le dimanche.
Article 4 : Un membre sort le dimanche si et seulement sil est Ecossais.
Article 5 : Tout membre qui porte une jupe est Ecossais et marie.
Article 6 : Tout membre Ecossais porte une jupe.
Determiner le nombre de membres de ce club.
Exercice 29. Trois dirigeants dune Societe (Pierre P., Marc M. et Alain A.) sont
prevenus de malversations financieres ; au cours de lenquete, lagent du fisc enre-
gistre leurs declarations :
Pierre P. : Marc est coupable et Alain est innocent.
Marc M. : Si Pierre est coupable, Alain lest aussi.
Alain A. : Je suis innocent, mais lun au moins des deux autres est coupable.
160
Ces trois temoignages sont-ils compatibles ? En supposant quils sont tous les trois
innocents, lequel a menti ? En supposant que chacun dit la verite, qui est innocent et
qui est coupable ? En supposant que les innocents disent la verite et que les coupables
mentent, qui est innocent et qui est coupable ?
Exercice 32. Le prince de Beaudiscours est dans un cruel embarras. Le voici au pied
du manoir ou la mechante fee Antinomie maintient prisonniere la douce princesse
Verite. Deux portes y donnent acces. Lune delles conduit aux appartements de la
princesse, mais lautre souvre sur lantre dun dragon furieux. Le prince sait seule-
ment que lune de ces deux portes souvre lorquon enonce une proposition vraie, et
lautre si on enonce une proposition fausse.
Comment peut-il delivrer la princesse ?
161
IV. Deuxieme point de vue : theorie de la demonstration
1 Presentation
Il sagit ici dexplorer les mecanismes du raisonnement humain, cest-a-dire les
schemas de pensee qui nous permettent de decider dagir dune certaine maniere, dans
le but dobtenir un certain resultat.
Nous disposons en fait dune (( base de connaissances )) qui fait que nous savons
que, dans telles ou telles circonstances, certaines causes produisent certains effets.
Pour obtenir ces effets, nous essayons de nous replacer dans les conditions de leurs
realisations.
Puis, le systeme est muni de (( regles dinference )), qui sont chargees de simuler les
divers modes de raisonnement que nous utilisons. Elles se presentent sous la forme de
regles qui, lors de la rencontre de formules dun type donne, autorisent la production
de nouvelles formules auxquelles on attachera le meme credit que celui qui est attribue
aux formules dont elle sont issues. Ces formules auront le statut de nouveaux resultats
consideres comme etablis, et pourront venir enrichir la (( base de connaissances )), on
les appellera des theoremes logiques .
Il faut aussi les distinguer des axiomes poses au sujet de la logique elle-meme,
comme, par exemple, celui que nous avons appele le principe de non-contradiction.
Ces axiomes enonces au sujet de la logique, ne sont pas non plus des axiomes lo-
giques.
162
Ils jouent le meme role, pour la logique, que laxiome dEuclide pour la geometrie :
ils conduisent a la construction dune certaine logique, etant bien entendu que dautres
axiomes peuvent conduire a la construction dautres logiques que celle qui est lobjet
du present chapitre.
Plus precisement :
Theoreme logique
D EFINITION 8 (T H EOR EME LOGIQUE ). Un resultat obtenu par une deduction cor-
recte ou une suite de deductions correctes (cest-a-dire qui utilisent explicitement
les regles dinference autorisees) a partir des axiomes logiques et, eventuellement,
dautres resultats du meme type deja etablis par ailleurs sappelle un theoreme lo-
gique.
Deduction sous hypothese Il est possible dutiliser des formules logiques supple-
mentaires (autres que des axiomes ou des theoremes) et de mener un raisonnement
correct a partir de ces formules (et des axiomes et des theoremes deja connus).
D EFINITION 11. On parle alors, non plus de demonstration, mais de deduction sous
hypotheses.
N OTATION : Lexpression : (( la formule logique H est obtenue par deduction sous
les hypotheses G1 , G2 , . . . , Gn )) est notee : {G1 , G2 , . . . , Gn } H.
163
Axiomes relatifs a limplication logique :
Axiome 1 : P (Q P )
Axiome 2 : (P Q) ((P (Q R)) (P R))
R EMARQUE 13. Il ne sagit pas la dun systeme daxiomes minimal, mais il nest pas
contradictoire.
R EMARQUE 14. Les noms sont traditionnellement des noms latins, utilises depuis les
philosophes du XVIeme siecle.
164
Ces noms utilisent une forme verbale - le gerondif - qui na pas dequivalent en
francais, et constituent donc des latinismes intraduisibles.
Une breve etude montrerait que ces quatre regles sont equivalentes.
Il est donc possible de nen conserver quune seule, quon appelle le (( modus (sous-
entendu : ponendo) ponens )), ou regle de detachement et qui est la premiere.
R EMARQUE 15. Sinon, il serait possible de supprimer quelques axiomes. Mais il vaut
mieux, dans un but ultime de programmation, diminuer le nombre de regles dinference
que celui daxiomes.
165
4.2 Cas de la deduction sous hypotheses
Une deduction sous hypotheses...
1. Commence par une premiere ligne qui comporte les mots (( Deduction sous les
hypotheses )).
2. Cette premiere ligne est suivie de lecriture de lensemble des hypotheses uti-
lisees...
3. Puis, comme dans une demonstration, de lignes numerotees dans lesquelles peuvent
figurer les memes elements, auxquels il faut rajouter les hypotheses, dont on a le
droit de se servir comme sil sagissait de resultats etablis.
4. La ligne indiquant la conclusion doit rappeler les hypotheses.
Dans la pratique, dans un but deconomie de place (la moindre deduction peut tres
vite prendre de nombreuses lignes), on sautorisera dautres elements (par exemple,
lutilisation de la technique de lhypothese supplementaire), qui seront vus dans la
suite.
4.3 Exemples
Voici, par exemple, comment on peut obtenir un (( modus (tollendo) tollens )) a
laide du (( modus ponens )) et des axiomes (il sagit donc de deduire P sous les
hypotheses P Q et Q) :
{P Q , Q}
:
1 Axiome 10 (P Q) ((P Q) P )
2 Hypothese P Q
3 m.p. sur 1 , 2 (P Q) P
4 Axiome 1 Q (P Q)
5 Hypothese Q
6 m.p. sur 4 , 5 (P Q)
7 m.p. sur 3 , 6 P
Conclusion : P .
P P
166
Ou encore :
(P P )
5 Theoreme de la deduction
5.1 Le theoreme
Il sagit du resultat qui equivaut, en theorie de la demonstration, au theoreme de la
validite en theorie des valeurs de verite.
167
5.2 Demonstration
La demonstration seffectue par recurrence sur la longueur de la deduction.
Hypothese : {G1 , G2 , . . . , Gn } H.
Soit p la longueur de la deduction qui amene a H.
Si p = 1 : une (( deduction de longueur 1 )) nautorise lecriture que dune seule
ligne. Cela signifie donc que lon peut directement ecrire H dans celle-ci. Ce
nest possible que si H est un axiome ou une hypothese
Si H est un axiome :
Deduction sous les hypotheses {G1 , G2 , . . . , Gn1 } :
1 Axiome 1 H (Gn H)
2 Axiome j H
3 m.p. sur 1 , 2 Gn H
Conclusion : {G1 , G2 , . . . , Gn1 } Gn H
Dans ce premier cas : {G1 , G2 , . . . , Gn } H implique {G1 , G2 , . . . , Gn1 }
Gn H (Les hypotheses ne sont en fait pas utilisees, donc elles ninter-
viennent pas).
Si H est lune des hypotheses {G1 , G2 , . . . , Gn1 }, posons H = Gi (0 < i <
n) :
Deduction sous les hypotheses {G1 , G2 , . . . , Gn1 } :
1 Axiome 1 Gi (Gn Gi )
2 Hypothese Gi
3 m.p. sur 1 , 2 Gn Gi
Conclusion : {G1 , G2 , . . . , Gn1 } Gn H
Dans ce deuxieme cas : {G1 , G2 , . . . , Gn } H implique {G1 , G2 , . . . , Gn1 }
Gn H (Seule lhypothese Gi a ete utilisee, les autres ne sont en fait pas
utilisees, elles ninterviennent pas).
Si H est lhypothese Gn : Alors on sait que : Gn Gn (voir paragraphe
precedent).
Dans ce troisieme cas : {G1 , G2 , . . . , Gn } H implique {G1 , G2 , . . . , Gn1}
Gn H.
Conclusion : la propriete est vraie pour p = 1.
Hypothese de recurrence : Soit p un entier tel que la propriete soit vraie pour
tous les entiers i de 1 a p (recurrence generalisee) ; on suppose que la longueur
de la deduction qui mene a H est (p + 1).
Si H est un axiome ou lune des hypotheses, le cas se traite comme ci-dessus.
Dans le cas contraire, H ne peut avoir ete obtenu que par un (( modus ponens ))
sur des formules P et P H. Ces formules ont elles-memes ete obtenues
par des deductions de longueur inferieure ou egale a p, donc on peut dire que
{G1 , G2 , . . . , Gn } P implique {G1 , G2 , . . . , Gn1 } Gn P et que
{G1 , G2 , . . . , Gn } P H implique {G1 , G2 , . . . , Gn1 } Gn
168
(P H).
Deduction sous les hypotheses {G1 , G2 , . . . , Gn1 } :
1 Resultat intermediaire 1 Gn P
2 Resultat intermediaire 2 Gn (P H)
3 Axiome 2 (Gn P ) ((Gn (P H)) (Gn H))
4 m.p. sur 1 , 3 (Gn (P H)) (Gn H)
5 m.p. sur 2 , 4 Gn H
Conclusion {G1 , G2 , . . . , Gn1 } Gn H,
et donc : {G1 , G2 , . . . , Gn } H implique {G1 , G2 , . . . , Gn1} Gn H,
lorsque la deduction est de longueur p + 1.
Le resultat est etabli.
Hypothese : Reciproquement, supposons {G1 , G2 , . . . , Gn1 } (Gn H). Alors,
Deduction sous les hypotheses {G1 , G2 , . . . , Gn }
1 Resultat obtenu sous les hyp {G1 , G2 , . . . , Gn1 } Gn H
2 Hypothese n Gn
3 m.p. sur 1 , 2 H
Conclusion {G1 , G2 , . . . , Gn } H
Donc : {G1 , G2 , . . . , Gn1} Gn H entrane {G1 , G2 , . . . , Gn } H.
Le theoreme est etabli.
169
1 Hypothese 3 A
2 Hypothese 1 A (B C)
3 m.p. sur 1 , 2 B C
4 Hypothese 2 B
5 m.p. sur 3 , 4 C
Conclusion {A (B C), B, A} C.
Deduction equivalente a la demonstration du theoreme dechange des premisses :
(A (B C)) (B (A C)).
R EMARQUE 16. Cette methode est beaucoup plus rapide que celle qui consisterait a
essayer de demontrer ce theoreme a partir des axiomes et de la regle dinference.
170
6.1 Theoreme de transitivite de limplication
171
6.3 Regle de disjonction des cas
Considerons laxiome 8
(P R) ((Q R) (P Q R))
En appliquant deux fois de suite le theoreme de la deduction, il est equivalent a la
deduction
{P R , Q R} P Q R
que lon peut utiliser sous cette forme comme regle dinference annexe : elle sappelle
regle de disjonction des cas .
172
6. (A B) (B C) (A C)
7. A (B C) (A B) (A C)
8. A (B C) (A B) (A C)
9. (A A)
10. (A B) A B
11. (A B) A B
12. A B (A B)
13. A B (A B)
14. (A B) A B
15. (A B) (A B)
16. (A B) A B
Cette hypothese pourra alors etre utilisee pour progresser, et pour atteindre, quelques
lignes plus loin, un certain resultat, disons R.
Dans une telle deduction, le resultat obtenu est celui qui est ecrit sur la derniere
ligne ecrite (meme si ce nest pas le resultat recherche !).
173
Autrement dit, si la deduction sarretait a cet endroit, le resultat obtenu serait R
mais, pour lobtenir, une hypothese non prevue au depart a ete utilisee.
On obtient
Deduction sous les hypotheses {H1 , H2 , . . . , Hn }
1
.. .. ..
. . .
i Hypothese supplementaire H
.. .. ..
. . .
j R
j+1 Suppression hyp. suppl. H H R
.. .. ..
. . .
On espere evidemment que ce dernier resultat a rendu le resultat recherche plus
accessible.
Cependant, les lignes ecrites dans le domaine de validite de lhypothese suplementaire
(de i + 1 a j) ne peuvent pas etre utilisees dans la suite de la deduction.
Dans certains cas complexes, il est possible de faire successivement plusieurs hy-
potheses supplementaires.
Il faut dans ce cas respecter la regle selon laquelle, lorsque plusieurs hypotheses
supplementaires coexistent, elles doivent etre supprimees dans lordre inverse de leur
introduction.
174
resultat nest pas immediat.
R EMARQUE 18. Il faut veiller que ce soit bien le resultat final attendu qui soit obtenu
avant la suppression des hypotheses supplementaires.
8 Methodes de demonstration
Il peut sembler a priori difficile de trouver les idees qui permettent de mener a bien
une deduction sous hypotheses.
On pourra sinspirer des principes suivants qui sont souvent dune aide precieuse
bien quon ne puisse affirmer quils fournissent dans tous les cas la solution la plus
courte, ni meme la solution elle-meme.
175
Lapplication de ces quelques principes permet en general de bien demarrer les
deductions, par leurs premieres lignes. On observe ensuite...
9 Exercices
176
Exercice 36. Etude de raisonnements concrets :
1. Peut-on conclure quelque chose au sujet de la reussite de lattaque envisagee
dans les conditions suivantes ?
Lattaque reussira seulement si lennemi est surpris ou si la position est peu
defendue. Lennemi ne sera pas surpris, a moins quil ne soit temeraire. Len-
nemi nest pas temeraire lorsque la position est peu defendue.
2. Peut-on conclure quelque chose au sujet de la culpabilite du suspect decrit dans
les propositions suivantes ?
Si le suspect a commis le vol, celui-ci a ete minutieusement prepare ou le suspect
disposait dun complice dans la place. Si le vol a ete minutieusement prepare,
alors, si le suspect avait un complice dans la place, le butin aurait ete beaucoup
plus important.
3. La conclusion du raisonnement suivant est-elle valide ? :
A moins que nous ne continuions la politique de soutien des prix, nous perdrons
les voix des agriculteurs. Si nous continuons cette politique, la surproduction se
poursuivra, sauf si nous contingentons la production. Sans les voix des agricul-
teurs, nous ne serons pas reelus. Donc, si nous sommes reelus et que nous ne
contingentons pas la production, la surproduction continuera.
4. Quelles sont les conclusions que lon peut tirer des renseignements suivants :
Jaime les tomates a la provencale, ou je suis ne un 29 fevrier, ou je sais jouer
du cornet a pistons. Si je sais jouer du cornet a pistons, alors je suis ne un 29
fevrier ou jaime les tomates a la provencale. Si je naime pas les tomates a la
provencale et si je suis ne un 29 fevrier, alors je ne sais pas jouer du cornet a
pistons. Je naime pas les tomates a la provencale ou je ne sais pas jouer du
conet a pistons.
177
Jespere bien que Clotaire est la. Barnabe est tres maladroit, et la main dAristide
tremble constamment depuis quil a eu cet acces de fievre qui le handicape, dit oncle
Jim.
Clotaire est surement la, affirme oncle Joe.
Quen sais-tu ? Je te parie cent sous que non, reprend oncle Jim.
Je peux te le prouver logiquement, retorque oncle Joe, qui poursuit : Prenons
comme hypothese de travail que Clotaire est absent , et voyons ce quil resulte de cette
supposition. Pour cela, je vais utiliser le principe de reduction a labsurde .
Je men doutais, grommelle oncle Jim. Je ne tai encore jamais entendu discuter
quelque chose sans que cela se termine par quelque absurdite !
Sans me laisser demonter par tes propos venimeux, dit noblement oncle Joe, je
continue ; Clotaire etant absent, tu maccordes que, si Aristide est egalement absent,
Barnabe est obligatoirement present ?
Evidemment, dit oncle Jim en haussant les epaules, sinon il ny aurait plus per-
sonne pour garder le salon.
Nous voyons par consequent que labsence de Clotaire fait intervenir une impli-
cation logique, (( si Aristide est absent, Barnabe est present )), et que cette implication
reste vraie tant que Clotaire est absent.
Admettons, fait Oncle Jim, et apres ?
Il nous faut a present tenir compte dune autre hypothetique, que je formule par
(( Si Aristide est absent, alors Barnabe est absent )), laquelle est toujours vraie,
independamment de la presence de Clotaire, nest-ce pas ?
Sans doute, dit oncle Jim, qui semble gagne par linquietude, je confirme quAris-
tide, sil sabsente, se fait obligatoirement accompagner par Barnabe.
Nous somme donc places en presence de deux implications. La premiere est vraie
tant que Clotaire est absent. La seconde, qui est toujours vraie, lest en particulier
lorsque Clotaire est absent. Or ces deux implications me paraissent parfaitement in-
compatibles. Donc, par une tres belle reduction a labsurde, je conclus quil est im-
possible que Clotaire soit absent, tu vas donc le voir tout de suite.
Il y a quand meme quelque chose qui me parat douteux, dans ton (( incompati-
bilite )), dit oncle Jim, qui semble totalement decontenance. Il reflechit, puis reprend :
Pourquoi, en effet, seraient-elles contradictoires ? Tu ne prouves en fait quune seule
chose : cest que cest Aristide qui est present !
Tres cher et tres illogique frere, fait oncle Joe, ne vois-tu pas que tu es en train
de decomposer une implication logique en premisse et conclusion ? Qui te permet
daffirmer que limplication (( si Aristide est absent, Barnabe est present )) est vraie ?
Nas-tu jamais appris que, de la valeur de verite dune implication, on ne peut rien
deduire sur celles de ses elements ?
A laide des variables propositionnelles A (pour : (( Aristide est present ))), B (pour :
(( Barnabe est present ))) et C (pour : (( Clotaire est present ))), formaliser les raison-
nements doncle Joe (dont la conclusion est C) et doncle Jim (dont la conclusion est
A). Qui a raison et qui a tort ?
178
10 Tableaux de Beth
Il sagit dune autre methode de demonstration formelle, ignorant tout systeme
daxiomes, mais comportant de nombreuses regles dinference.
Elle est particulierement adaptee a lautomatisation des demonstrations, et consti-
tue une ouverture sur les algorithmes etudies en seconde annee (utilisation systematique
du (( theoreme de falsification )) qui sera envisage plus loin).
AB AB
A
A B B
AB AB
A
B A B
A B A B
A
A B B
A
La regle de contradiction est A .
179
Une branche dun tableau de Beth est consideree comme terminee lorsque plus
aucune regle ne peut sappliquer et elle est consideree comme close lorsquelle contient
le symbole de contradiction .
Il nest pas necessaire, pour lapplication de la regle de contradiction, que A et A
figurent dans cet ordre, ni meme consecutivement, dans larbre : il suffit quils soient
dans la meme branche.
10.3 Exemple
Demonstration de ((P Q) P ) P
((P Q) P ) P
P
(P Q) Q
P Q P
P
Q
180
regles dinference,
demonstrations (ou deductions sous hypotheses).
On peut se demander si les resultats obtenus dans chacune des deux theories sont
identiques, cest-a-dire faire letude de la completude du calcul propositionnel...
1.1 Theoreme
Le theoreme de completude du calcul propositionnel senonce ainsi :
P ROPRI ET E XIII (T H EOR EME DE COMPL ETUDE ) : Tout theoreme est une tauto-
logie et reciproquement, soit :
F si et seulement si |= F .
Autrement dit, les deux points de vue (theorie des valeurs de verite, theorie de la
demonstration) sont equivalents pour les theoremes et les tautologies.
1.2 Demonstration
Hypothese : F (cest-a-dire : F est un theoreme) : La demonstration utilise les
resultats suivants :
Tous les axiomes du calcul propositionnel sont des tautologies (simple calcul sur
leurs fonctions de verite, qui ne sera pas developpe ici).
La regle de detachement est valide (voir exemple du paragraphe 3.3.2 : {P, P
Q} |= Q.
Il resulte de ces considerations que, lorsquon effectue une demonstration (donc :
une deduction sans hypotheses), cette demonstration utilise des axiomes, qui sont des
tautologies, cest-a-dire des formes propositionnelles (( toujours vraies )), et en deduit
dautres formes propositionnelles ; dapres la validite du (( modus ponens )), les formes
propositionnelles qui ont ete deduites sont (( vraies )) chaque fois que les formes dori-
gine le sont aussi ; or, ces dernieres le sont toujours, donc les formes deduites le sont
aussi toujours ; autrement dit, les formules deduites en theorie de la demonstration sont
des tautologies. Conclusion : |= F .
Hypothese : |= F (cest-a-dire : F est une tautologie) : Plus complique : il faut
exhiber une demonstration dune tautologie. La demonstration se fait en trois etapes :
etape 1 : On montre que, si |= F , alors {P1 P1 , P2 P2 , . . . , Pn Pn } F
[Dans cette expression, P1 , P2 , . . . , Pn sont les variables propositionnelles qui
interviennent dans lexpression de F , a lexclusion de toute autre].
etape 2 : On montre que A A.
181
etape 3 : On montre que, si, i {1, 2, ..., p}, Bi et si {B1 , B2 , . . . , Bp }
C , alors C ou transitivite de la deductibilite [ est un ensemble, eventuellement
vide, dhypotheses].
Conclusion : Letape 3, appliquee a P1 P1 , P2 P2 , . . . , Pn Pn
[lensemble dhypotheses est ici vide] permet dobtenir : F .
Voici le detail de la demonstration des trois etapes :
etape 1 : Toute ligne dune table de verite concernant une forme propositionnelle
peut etre interpretee comme introduisant une (( regle de deductibilite )). Exemple :
P Q P Q
la ligne de la table de verite de la disjonction logique peut
V F V
etre interpretee comme representant une deduction : {P, Q} (P Q). Cette
(( regle de deductibilite )) resulte immediatement des considerations suivantes :
Deduction sous les hypotheses {P , Q}
1 Hypothese 1 P
2 Axiome 6 P P Q
3 m.p. sur 2 , 3 P Q
Conclusion (P, Q) P Q.
[remarque : lhypothese Q ne sert en fait pas, mais peu importe]. Il suffit alors
detablir ces (( regles de deductibilite )) pour toutes les lignes des tables de verite
des connecteurs logique (ce qui est un peu long -il y en a 18 - mais ne presente
pas de veritable caractere de difficulte, elles sont proposees en TD) ; comme la
table de verite de F est obtenue a partir de celles des connecteurs logiques, cha-
cune de ses lignes peut aussi etre consideree comme une regle de deductibilite ;
comme F est une tautologie, sa derniere colonne est uniquement composee
de (( V )), autrement dit, les regles de deductibilite qui la concernent pourront
secrire :
{ P1 , P2 , . . . , Pn1 , Pn } F
{ P1 , P2 , . . . , Pn1 , Pn } F
. ... ... .. ...... .... . . .
{ P1 , P2 , . . . , Pn1 , Pn } F
{ P1 , P2 , . . . , Pn1 , Pn } F
[Le tableau comporte 2n lignes]. Il ne reste plus qua etablir que, si est un
ensemble quelconque de formes propositionnelles, et si on a {A} C et
{B} C, alors on a {A B} C, ce qui se fait de la maniere suivante
(il sagit en fait dune disjonction des cas) :
{A} C est equivalent a A C [dapres le theoreme de la
deduction].
{B} C est equivalent a B C [dapres le theoreme de la
deduction].
Donc, dans une
Deduction sous les hypotheses :
182
1 Resultat intermediaire 1 A C
2 Resultat intermediaire 2 B C
3 Axiome 8 (A C) ((B C) (A B C))
4 m.p. sur 1 , 3 (B C) (A B C)
5 m.p. sur 2 , 4 A B C
Conclusion A B C
Donc, si on suppose {A} C et {B} C, il existe une deduction sous les
hypotheses dont la conclusion est A B C. Cest a dire : A B
C. Dapres le theoreme de la deduction, ce dernier resultat est equivalent a :
{A B} C. Cest la conclusion qui etait recherchee.
Ce resultat est a present applique n fois de suite aux 2n (( regles de deductibilite )),
que lon prend deux par deux, pour obtenir enfin : {P1 P1 , P2 P2 , . . . , Pn
Pn } F .
etape 2 : Il faut montrer que : A A (theoreme du tiers-exclu).
Demonstration :
1 Axiome 6 A A A
2 Th. de la contrap. (A A A) ((A A) A)
3 m.p. sur 1 , 2 (A A) A
4 Axiome 7 A A A
5 Th. de la contrap. (A A A) ((A A) A)
6 m.p. sur 4 , 5 (A A) A
7 Axiome 10 ((A A) A) (((A A) A) (A A))
8 m.p. sur 3 , 7 ((A A) A) (A A)
9 m.p. sur 6 , 8 (A A)
10 Axiome 9 (A A) A A
11 m.p. sur 9 , 10 A A
Conclusion : A A.
etape 3 : Il faut montrer que, si, i {1, 2, ..., p}, Bi et si {B1 , B2 , . . . , Bp }
C, alors C. Pour cela, il suffit de remarquer quune (( conclusion partielle )),
cest a dire une formule obtenue au cours dune deduction, est dument etablie, et
peut donc servir pour des inferences dans la suite (cette remarque a deja ete uti-
lisee dans plusieurs des demonstrations de ce cours). Ainsi, il suffit de regrouper
au sein dune meme deduction (sous les hypotheses de ), les deductions qui
menent aux Bi (pour 1 6 i 6 p). Ceux-ci seront consideres, dans la suite,
comme (( conclusions partielles )) ou (( resultats intermediaires )). Et ils seront
donc reutilises en tant que tels dans la suite de la deduction, qui consistera a
recopier la deduction de C (sous les hypotheses Bi ). Dans cette deduction, les
references aux Bi , en tant quhypotheses, seront remplacees par les references
aux lignes qui precedent dans lesquelles les Bi ont ete obtenus comme (( conclu-
183
sions partielles )). Cette nouvelle deduction sera bien une deduction de C sous
les hypotheses de .
Le theoreme de completude est etabli.
Fin du Chapitre
184
Chapitre 11
I. Introduction
1 Insuffisances de la formalisation en Calcul Propositionnel
La Logique des propositions ne soccupe, on le sait, que des liens entre les propo-
sitions realises a laide des connecteurs logiques.
Autrement dit, une fois quune proposition (( complexe )) a ete analysee suivant ces
connecteurs, il subsiste des (( atomes )) (non secables en Logique des Propositions) et
lanalyse ne peut pas etre poussee plus profondement... alors quil existe cependant
encore des (( relations )) entre ces atomes, relations que la Logique des Propositions ne
permet pas de prendre en compte.
185
Ce premier exemple suggere la necessite, pour poursuivre lanalyse des proposi-
tions, de la creation dun langage qui permettrait de decrire des proprietes accordees
(ou non) a des individus, ou les reliant.
Cette preoccupation est aussi celle des Mathematiciens, qui soccupent, par exemple,
de decrire les proprietes des entiers naturels.
Il faudra donc envisager des (( variables )) , dans un certain domaine, et, pour cer-
taines (( valeurs )) de ces variables, certaines proprietes seront (( vraies )) ou (( fausses )).
Dans ce second exemple, comme dans le premier, la proposition evoque une pro-
priete, accordee ou refusee, a un objet bien precis (7).
Bien entendu, la valeur de verite depend de la valeur de cet objet, mais aussi de
lensemble dans lequel ces valeurs peuvent etre choisies.
Dune maniere generale, et avant de donner une definition precise de ces concepts,
on dira quune (( propriete )) possedee (ou non) par un objet est un predicat.
La valeur de verite de la proposition obtenue en appliquant ce predicat a un (ou
plusieurs) objets depend de lunivers du discours, cest a dire de lensemble des valeurs
reconnues comme possibles (par exemple, dans lexemple precedent, N ou R), et aussi,
bien entendu, de cette valeur elle-meme.
E XEMPLE 3. Considerons les propositions (( Tous les etudiants sont serieux )) et (( cer-
tains etudiants sont serieux )).
186
La Logique des Propositions est incapable de faire apparatre le lien manifeste qui
existe entre elles. Elle ne pourra les formaliser que par A et B, parce quelles sont
differentes et que lune nest pas la negation de lautre.
La generalisation du calcul propositionnel suggeree ici est encore plus grande que
dans les exemples precedents, puisque la propriete evoquee ((( etre serieux )) ) est ac-
cordee, par ces propositions, non pas seulement a un individu bien precis, mais a cer-
tains individus, consideres dans leur ensemble, ou meme a toute une categorie dindi-
vidus, sans quaucun ne soit nommement designe.
Lobjet du calcul des predicats est detudier et de formaliser les notions qui viennent
detre brievement evoquees, et que le calcul propositionnel ne permet pas de faire ap-
paratre.
187
le designer indirectement par une (( propriete )) caracteristique (quil doit donc
etre le seul a posseder, de maniere a ce quil soit identifie sans aucune am-
bigute).
E XEMPLE 5. Par exemple, si P ierre est le pere de Jean, il est possible de dis-
tinguer P ierre sans le nommer explicitement par la locution (( le pere de Jean )).
E XEMPLE 6. Lentier 7 peut etre distingue sans etre nomme explicitement par
lexpression 5 + 2 qui designe un et un seul entier positif.
Comme toute application donne une image et une seule de tout element de son
domaine, un groupe operatoire a n places represente bien, sans ambigute, un individu
de lunivers du discours.
E XEMPLE 7. Laddition ordinaire des entiers est une operation binaire sur IN et +(x, y).
Le groupe operatoire correspondant designe, de maniere unique, un element de cet
ensemble, des que les variables x et y ont ete remplacees dans son expression par des
sujets distingues (par une methode ou une autre).
Ainsi, +(5, 2) est lindividu qui peut aussi etre represente par 7.
188
E XEMPLE 8. Le groupe operatoire a 1 place pere(x) designe sans ambigute un et un
seul individu dans lunivers des etres humains, des que la variable x a ete remplacee
par un sujet distingue.
Si Jean est bien un nom dindividu (cest a dire, designe bien un individu unique),
sil en est de meme de P ierre, et si P ierre est le pere de Jean, alors pere(Jean)
distingue lindividu P ierre.
Par extension, et par convention, un nom dindividu est considere comme groupe
operatoire zero-aire (sans variable).
D EFINITION 3 (T ERME ). En calcul des predicats, on fait intervenir des groupes operatoires
a n places. Le resultat est un terme du calcul des predicats :
une variable,
une (( constante )) (un groupe operatoire zero-aire),
un groupe operatoire n-aire (n > 1) f (t1 , t2 , . . . , tn ), dans lequel t1 , t2 , . . . , tn
sont des termes et f un symbole operatoire (ou fonctionnel).
189
R EMARQUE 2. r (le symbole de lapplication) est encore appele symbole relationnel,
ou symbole de predicat.
Par extension et par convention, un groupe relationnel zero-aire (sans (( variables )))
est une proposition (qui a donc une valeur de verite).
R EMARQUE 3. On notera que, lorsque les termes qui interviennent dans un groupe
relationnel sont des individus, ce groupe devient une proposition (vraie ou fausse) :
double de(x, y) est un predicat, ou groupe relationnel a deux places defini sur
U = N.
double de(22, 11) est une proposition (vraie).
double de(+(23, 23), +(40, 5)) en est une autre (fausse !).
Dans une formule du calcul des predicats, un groupe relationnel est un atome.
5 Les quantificateurs
Considerons la proposition (( Tous les etudiants travaillent les mathematiques ))
pour lanalyser du point de vue du calcul des predicats.
Il faut preciser lunivers du discours, il sagit ici dun ensemble produit cartesien
de deux ensembles :
le premier est lensemble des etudiants,
le second un ensemble de noms de matieres (celles qui sont susceptibles detre
enseignees).
Il est bien clair quil sagit dune proposition. Or, si la seconde variable (y) est
bien remplacee par un symbole dindividu (maths), aucun nom, explicite ou impli-
cite, nest donne pour designer un etudiant particulier : on a (( travaille(x, maths) ))
sans que lon sache (( qui est x )) .
N OTATION : La notation utilisee pour cette quantification est (( x travaille(x, maths) )).
190
D EFINITION 6 (Q UANTIFICATEUR UNIVERSEL ). est un symbole de quantificateur,
appele le quantificateur universel. On dit alors que x est le quantificateur universel
de la variable x.
travaille(x, maths) nest pas une proposition : impossible de lui attribuer une
valeur de verite si on ne sait pas (( qui est x )).
E XEMPLE 10. Cest ainsi que travaille(Jean, maths) est vrai ou f aux, et que travaille(f ils(P ierre), m
est aussi vrai ou f aux.
En effet, il est devenu impossible de lui attribuer une valeur quelconque de lunivers
du discours, que ce soit par un nom ou par un terme, sous peine de perte totale de sens.
R EMARQUE 5. Il nest pas possible de substituer quoi que ce soit a x dans cette ex-
pression, si ce nest un autre symbole de variable : en effet, y travaille(y, maths) a
tres exactement le meme sens, et la meme valeur de verite.
E XEMPLE 11. Les (( variables liees )) (on dit aussi variables muettes) sont dun emploi
courant en Mathematiques.
3
X
Par exemple, considerons lexpression i = 1 + 2 + 3 = 6.
i=1
191
Bien quun symbole de variable (i) intervienne dans cette expression, le resultat ne
fait pas intervenir de variable : cest une simple valeur numerique.
On pourrait, sans changer cette valeur, attribuer un autre symbole a la variable
X3
muette, par exemple, on a aussi j = 6.
j=1
Bref, la variable nest en fait presente que (( fictivement )), elle nintervient pas dans
le resultat. Il est par consequent impossible de lui attribuer quelque valeur que ce soit,
alors que cest possible pour une variable libre.
Par exemple dans lexpression (i + j) (qui na pas de valeur), on peut (( donner a i
la valeur 3 )) pour obtenir (3+j) et a j la valeur 5 pour obtenir (3+5), qui a maintenant
une valeur.
E XEMPLE 12. Dans la proposition (( Tous les etudiants travaillent une matiere )) , inter-
vient le meme groupe relationnel a deux places travaille(x, y) ; on remarque quaucun
etudiant nest explicitement nomme, pas plus que la matiere quil travaille.
Il faut formaliser cette proposition en calcul des predicats par (( pour tout etudiant,
il y a une matiere, et cet etudiant travaille cette matiere )) , soit xy travaille(x, y) :
la variable x est liee par le quantificateur universel x et la variable y est liee par le
quantificateur existentiel y
192
Autrement dit, la matiere travaillee est fonction de letudiant, elle depend de cet
etudiant, elle nest eventuellement pas la meme pour tous les etudiants.
La difference fondamentale avec le cas precedent est que, dans cette derniere
proposition, on affirme que tous les etudiants travaillent la meme matiere.
E XEMPLE 15. En supposant que (a, b, c) prenne ses valeurs dans un univers du dis-
cours qui est une partie de R3 telle que b2 4ac > 0, la proposition :
193
6 Formules du calcul des predicats
Comme les groupes relationnels produisent des propositions
soit quand les variables sont remplacees par des individus,
soit quand elles sont liees par quantification,
il est possible de relier de telles expressions par les connecteurs logiques habituels,
comme en calcul propositionnel.
On obtient ainsi une formule du calcul des predicats...
Par convention, dans lecriture dune formule, un quantificateur est prioritaire sur
tout connecteur logique, son champ est donc generalement clairement delimite par
une paire de parentheses (dapres la regle de priorite, sil ny a pas de parentheses, son
champ est limite au premier connecteur rencontre).
On remarquera que, dans q(x), x est donc libre, alors quelle est liee dans p(x, y),
ce qui signifie donc que le symbole x na pas la meme signification dans lensemble
de la formule :
dans q(x), elle peut etre remplacee par nimporte quel terme ou individu,
ce nest pas le cas dans p(x, y).
194
R EMARQUE 7. Une telle expression serait consideree comme incorrecte en calcul
algebrique, par exemple, de meme que dans tout langage de programmation.
En effet, un meme symbole ou identificateur ne peut designer quun seul objet a la
fois et, pour des objets differents, dans une meme formule, il faut utiliser des symboles
differents.
Par contre, en calcul des predicats, une telle expression est parfaitement licite.
Il vaut evidemment mieux sabstenir dexpressions qui entretiennent de telles am-
bigutes, mais elles sont admises parce quelles peuvent intervenir (( independamment
de notre volonte )) lors de substitutions (voir plus loin).
2. Une expression analogue (une formule) du calcul des predicats pourrait etre
p(x, y) q(x, z).
Les atomes sont ici des predicats de poids deux qui, eux aussi, ne peuvent
prendre que les valeurs (( vrai )) ou (( faux )), mais pas independamment du predicat
195
considere.
Il nest donc pas possible de remplacer un atome par une simple variable booleenne.
Seule une fonction booleenne (de variables non booleennes) peut convenir, pour faire
intervenir les valeurs des variables qui sont les arguments du groupe relationnel.
si f (x, y) est la fonction booleenne associee au predicat p(x, y)
si g(x, z) est celle qui est associee a q(x, z),
alors la fonction de verite de la formule est : f (x, y) + g(x, z).
Attention, x, y et z ne sont pas ici des variables booleennes, mais elles prennent
leurs valeurs dans lunivers du discours. Il nest donc pas question de (( calculer avec
x, y et z comme en algebre de Boole )).
Le seul moyen, en general, pour etudier une telle fonction de verite est de construire
le tableau de ses valeurs, en donnant a x, y et z successivement toutes les valeurs
possibles dans lunivers du discours (si celui-ci est infini, on imagine aisement les
problemes qui vont se poser...).
1.2 Definitions
Les definitions de tautologie et de consequence logique (en calcul des predicats,
on dira plutot consequence valide) sont les memes...
|= P [P est une tautologie] si et seulement si, pour tous les univers du discours
possibles, pour tous les predicats qui peuvent intervenir dans P , et pour toutes
les valeurs des variables dans chacun des univers, la valeur de verite de P est
(( vrai )).
196
la valeur de verite de x p(x) est obtenue en faisant la liste des valeurs de verite
de p(x) pour toutes les valeurs possibles de x dans lunivers du discours (liste
effective lorsque cest possible, ou demonstration). Si, pour toute valeur de x, la
valeur de verite de p(x) est vrai, alors la valeur de verite de x p(x) est vrai.
Sil y a une seule valeur de x pour laquelle la valeur de verite de p(x) est f aux,
alors la valeur de verite de x p(x) est f aux.
la valeur de verite de x p(x) est obtenue en faisant la liste des valeurs de verite
de p(x) jusqua ce quon trouve vrai. Si on trouve vrai, la valeur de verite de
x p(x) est vrai. Si, pour tout element x de lunivers du discours, la valeur de
verite de p(x) est f aux (liste effective ou demonstration), alors celle de x p(x)
est f aux.
Bien entendu, dans certains cas, il nest pas necessaire detablir effectivement la
table de verite dune formule du calcul des predicats pour prouver quil sagit dune
tautologie. Par exemple, il est bien clair que, pour un atome p(x, y, z) (mais aussi pour
toute formule P ), on a : |= p(x, y, z) p(x, y, z).
Mais, pour donner un exemple de la complexite introduite en theorie des valeurs
de verite par le calcul des predicats, etudions la formule p(x) p(y) pour savoir sil
sagit dune tautologie (p(x) est evidemment un predicat unaire : difficile de proposer
un exemple plus simple). Pour prouver quil sagit dune tautologie, il faut prouver
que :
pour tout predicat unaire p,
pour tout univers du discours U,
pour toutes valeurs des variables x et y dans U,
la valeur de verite de la formule est vrai. (( Pour tout univers du discours )) : il faut
envisager des univers a 1, puis 2,... elements et essayer den deduire un resultat general,
si cest possible.
Dans un univers a un seul element, x, comme y, ne peut prendre quune seule
valeur ; on a donc x = y, et donc la valeurs de verite de p(x) est la meme que
celle de p(y), et donc p(x) p(y) est vraie [table de limplication].
Dans un univers a deux elements, pour que la valeur de verite de p(x) soit
definie, il faut se la donner pour chacune des deux valeurs de x ; or, il faut le faire
(( pour tout predicat unaire p )) , donc envisager toutes les fonctions booleennes
de deux variables : il y en a quatre, que nous noterons z, i, n, et r. Designons
les deux elements de U par 1 et 2 (pour ne pas les confondre avec des variables
booleennes) :
x z(x) i(x) n(x) r(x)
1 f aux f aux vrai vrai
2 f aux vrai f aux vrai
Puis il faut faire le tableau des valeurs de verite de p(x), p(y) et de p(x) p(y)
197
en fonction des valeurs de x et de y et de la fonction booleenne associee a p (z,
i, n, ou r)
fonction booleenne de p x y p(x) p(y) p(x) p(y)
z 1 1 f aux f aux vrai
1 2 f aux f aux vrai
2 1 f aux f aux vrai
2 2 f aux f aux vrai
i 1 1 f aux f aux vrai
1 2 f aux vrai vrai
2 1 vrai f aux f aux
2 2 ..... ..... .............
n . . ..... ..... .............
Inutile de construire le reste du tableau : on a trouve f aux dans une ligne, donc
p(x) p(y) nest pas une tautologie [en effet, il existe un predicat unaire, un
univers a deux elements, et, dans cet univers, une valeur de x et une valeur de y
pour lesquels la formule est fausse...].
Exemples Donnons enfin deux exemples pour lesquels la construction dune table
de verite nest pas necessaire :
E XEMPLE 18 (M ONTRER QUE x (r(x) s(x)) x (r(x) s(x)) N EST NI UNE ANTILOGIE , NI U
Pour montrer que cette formule nest pas une antilogie, il suffit dexhiber un exemple
dans lequel elle est vraie ; pour montrer quelle nest pas une tautologie, il suffit dex-
hiber un exemple dans lequel elle est fausse.
U est lensemble des habitants de la France ; r(x) est le predicat (( x habite Bel-
fort )) et s(x) est le predicat (( x habite la France )) . Puisque Belfort est en France,
198
tout habitant de Belfort habite la France, donc x (r(x) s(x)) est vrai.
Mais tous les habitants de la France ne sont pas concentres a Belfort, autre-
ment dit : il existe des habitants de la France qui nhabitent pas Belfort, donc :
x (r(x) s(x)) est vrai ; enfin, dapres la table de verite de la conjonction
logique, la formule est vraie.
U est un ensemble E, dans lequel on a defini deux parties R et S, telles que
S R ; r(x) est le predicat (( x R )) et s(x) est le predicat (( x S )) . Comme
S R, tout element exterieur a R ne peut pas etre dans S, donc x (r(x)
s(x)) est f aux, et donc la formule est fausse.
199
Mais attention : dans lunivers du discours U = R, x (x < 0) est vraie, x (x > 0)
est vraie aussi, mais x ((x < 0) (x > 0)) nest pas vraie ! Dans le meme univers,
x ((x < 0) (x > 0)) est evidemment vraie, alors que x (x < 0) x (x > 0)
nest, evidemment aussi, pas vraie !
Dapres les tables de verite des connecteurs logiques, x (p(x) q(x)) est
equivalente a x (p(x) q(x)), qui est equivalente a x p(x) x q(x), or x p(x)
est equivalente a x p(x) (voir ci-dessus), donc notre formule est encore equivalente
a x p(x) x q(x), soit, finalement, a x p(x) x q(x).
On remarquera bien que dans, par exemple, x p(x)x q(x), les deux occurrences
de x ne representent pas la meme variable, mais deux variables liees ou muettes, tan-
dis que dans x (p(x) q(x)), les deux occurrences de x representent bien la meme
variable (toujours muette).
3 Substitutions libres
On notera par A(x) une formule du calcul des predicats (eventuellement com-
pliquee !) dans laquelle la variable x presente des occurrences ; ces occurrences peuvent
etre libres ou liees, et A peut presenter des occurrences libres et des occurrences liees
de x ; bien entendu, il peut aussi ny avoir aucune occurrence libre, ou aucune occur-
rence liee ; enfin, dautres variables peuvent aussi presenter des occurrences dans A.
Soit ensuite t un terme du calcul des predicats, qui presente des occurrences de di-
verses variables (toutes libres, dans un terme, evidemment ; un terme ne comporte pas
de quantificateurs).
On dit que ce terme t est libre pour x dans A lorsque les occurrences libres de x
dans A ne rentrent dans le champ daucun quantificateur portant sur une variable de t.
Exemple : Soit la formule A(x) = x r(x, y) y s(x, y, z) [Cette formule presente
une occurrence liee et une occurrence libre de x].
Examinons le terme y (une variable est un terme) par rapport a la variable x dans
A. Comme loccurrence libre de x dans A (la seconde) entre dans le champ du
quantificateur y, et que y est une variable (et meme la seule...) du terme y, le
terme y nest pas libre pour x dans A.
Examinons le terme t = f (x, z) [ou f est un symbole operatoire, t est bien un
terme] par rapport a la variable x dans A. Comme loccurrence libre de x dans
A nentre pas dans le champ dun quantificateur portant sur x (et pour cause...),
ni dans celui dun quantificateur portant sur z (il ny en a pas...), ce terme t est
libre pour x dans A.
On appelle substitution libre de la variable x par le terme t dans la formule A le rem-
placement de x, dans toutes ses occurrences libres dans A (et uniquement celles-ci...)
par le terme t, a condition que ce terme soit libre pour x dans A. La nouvelle formule
obtenue est notee (x | t)A.
il est impossible deffectuer la substitution libre de x par y dans la formule de
lexemple ci-dessus (y nest pas libre pour x dans A).
200
il est possible deffectuer la substitution libre de x par t = f (x, z) dans A, car
ce terme est libre pour x dans A. Le resultat est (x | f (x, z))A = x r(x, y)
y s(f (x, z), y, z).
Par convention, si x ne presente pas doccurrences libres dans A, la substitution libre
de x par nimporte quoi est toujours possible, et elle laisse la formule A inchangee.
201
III. Theorie de la demonstration en calcul des predicats
1 Axiomes et regles dinference
Pour elaborer la theorie de la demonstration en calcul des predicats, on reprend
celle qui a ete donnee en calcul propositionnel en ajoutant les axiomes et les regles
dinference qui permettent de traiter les nouveaux symboles introduits (les quantifica-
teurs).
Nouveaux axiomes :
A14 = x A(x) A(r)
A15 = A(r) x A(x)
[Dans les conditions indiquees au paragraphe precedent : substitution libre de x
par r dans A, r etant libre pour x dans A].
Nouvelles regles dinference :
{C A(x)} C x A(x) [regle dintroduction de ou regle-]
{A(x) C} x A(x) C [regle dintroduction de ou regle-].
[La formule C ne contient pas doccurrences libres de x].
202
la deduction est faite (( a variables constantes )) (cette expression malheureuse,
mais consacree, signifie simplement que la deduction nutilise aucune des regles
dintroduction des quantificateurs, donc est faite comme en calcul proposition-
nel).
les hypotheses de la deduction sont toutes des formules closes (cest a dire sans
variables libres).
1 Definition
Lalphabet P R est celui de (( LP )) , auquel on adjoint :
le symbole de quantificateur universel
des symboles de variables et dindividus (les (( constantes )) )
des symboles operatoires et fonctionnels
Les formules sont celles du calcul des predicat (limitees au vocabulaire de (( PR ))
)
Les (schemas d) axiomes sont au nombre de 5 :
Axiome 1 : A (B A)
Axiome 2 : (A (B C)) ((A B) (A C))
Axiome 3 : (B A) (A B)
Axiome 4 : x A(x) A(t)
Axiome 5 : (C B(x)) (C x B(x)) [x netant pas variable libre
de C].
Il y a 2 regles dinference :
Le (( modus ponens )) (A, A B) B
La generalisation A x A.
203
(x = y) si et seulement si p (p(x) p(y)).
Or, quantifier un symbole de predicat nest pas possible en calcul des predicats du
premier ordre. Donc, lorsquon a besoin dune egalite, on se contente dune egalite
(( affaiblie )) comme simple relation dequivalence (reflexive, symetrique, transitive),
donc comme un predicat binaire, quil faudrait noter (x, y) mais que lon note (x
y). Bien entendu, il faut ajouter les axiomes qui fixent les proprietes de cette egalite,
pour obtenir un calcul des predicats egalitaire.
3 Interpretations de (( PR ))
Soit E la base dune interpretation de (( PR )) .
une formule de (( PR )) est dite satisfaite dans E chaque fois quil existe un en-
semble de valeurs, choisies dans E, pour les variables libres qui interviennent
dans cette formule tel que la proposition qui en resulte est (( vraie )) .
une formule de (( PR )) est dite valide dans E si, pour tout ensemble de valeurs,
choisies dans E, pour les variables libres qui interviennent dans E, la proposition
qui en resulte est vraie.
une formule de (( PR )) est universellement valide ou est une these lorsquelle est
valide dans toute interpretation. Lusage veut cependant que lon conserve terme
de tautologie (qui devrait etre reserve au calcul propositionnel).
4 (Meta-)Theoreme de completude
La demonstration est longue et repose sur un raisonnement par recurrence sur
la complexite de la formule (en gros, le nombre de connecteurs ou quantificateurs
qui interviennent dans celle-ci), apres avoir demontre la propriete individuellement
pour chaque formule de complexite 1 (un seul connecteur ou quantificateur). Toute
la difficulte provient de la cardinalite (du (( nombre delements )) ) de la base de lin-
terpretation. Le resultat est connu sous le nom de theoreme de completude de Godel
(1930). Bref, le (meta-) theoreme suivant peut etre enonce :
Le systeme formel (( PR )) est complet ( B si et seulement si |= B)
Le theoreme de completude generalise pour (( PR )) a aussi ete obtenu par Godel :
F |= B si et seulement si F B
5 Satisfiabilite et insatisfiabilite
Soit F un ensemble de formules de (( PR )) ; F est dit satisfiable sil est possible
de trouver une interpretation dans laquelle les formules de F sont simultanement sa-
tisfaites. La base dune telle interpretation est appelee modele de F . Evidemment, sil
nest pas possible de trouver un modele pour lensemble de formules F , celui-ci est dit
insatisfiable. Ce sont ces notions dinsatisfiabilite qui sont a lorigine des methodes de
demonstration dites de falsification (et qui servent dans les algorithmes de (( chanage
204
arriere )) ). Il sagit dobtenir une deduction dune formule B de (( PR )) a partir dun
ensemble dhypotheses F . On enonce le (meta-) theoreme suivant, appele Theoreme
de falsification :
Soit F un ensemble de formules closes et B une formule close de (( PR )) .
Alors, F B si et seulement si F {B} est insatisfiable
1.2 Methode
La methode a suivre est la suivante :
Reduire les connecteurs. En theorie, il faudrait ne conserver que les connecteurs
et , en fait, on ne conserve que , , . Cette reduction est obtenue par
les equivalences entre formules classiques
A B A B
A B (A B) (A B)
Renommer les variables liees, de maniere a ce que toute variable liee ne le
soit quune seule fois, et quaucune variable liee ne presente doccurrence libre,
dapres les egalites suivantes :
xA(x) = yA(y)
xA(x) = yA(y)
Faire (( remonter )) les quantificateurs en tete, par les equivalences suivantes :
A A
(xA(x)) xA(x)
(xA(x)) xA(x)
205
et, si x nest pas variable libre de C (ce qui doit etre le cas si on a correctement
renomme les variables...]
1.3 Exemple
On considere les propositions suivantes :
P1 Tout crime a un auteur
P2 Seuls les gens malhonnetes commettent des crimes
P3 On narrete que les gens malhonnetes
P4 Les gens malhonnetes arretes ne commettent pas de crimes
P5 Des crimes se produisent
On voudrait en deduire :
Q Il y a des gens malhonnetes en liberte
Sans anticiper sur les methodes de resolution, on va ajouter aux propositions P1 a P5
la proposition P6 Q (si on montre que cet ensemble de propositions est (( insatis-
fiable )) , on aura montre que Q est consequence de P1 a P5 ).
Pour cela, on va considerer les predicats
ar(x) : la personne x est arretee
mal(x) : la personne x est malhonnete
co(x, y) : la personne x commet laction y
cr(y) : laction y est un crime
On obtient
F1 y(cr(y) xco(x, y))
F2 xy(cr(y) co(x, y) mal(x))
F3 x(ar(x) mal(x))
F4 x(mal(x) ar(x) (y(cr(y) co(x, y))))
F5 xcr(x)
F6 (x(mal(x) ar(x)))
qui deviennent, sous forme prenexe,
F1 yx(cr(y) co(x, y))
F2 xy(cr(y) co(x, y) mal(x))
F3 x(ar(x) mal(x))
F4 xy(mal(x) ar(x) cr(y) co(x, y))
F5 xcr(x)
F6 x(mal(x) ar(x))
206
2 Forme de Skolem
2.1 Definition
On appelle forme de Skolem dune formule de (( PR )) , mise prealablement sous
forme prenexe, la formule obtenue en eliminant tous les quantificateurs de symbole ,
de la maniere suivante :
Soit xj un quantificateur existentiel qui figure apres les quantificateurs univer-
sels xj1 xj2 . . . xjn : alors xj est remplace par f (xj1 , xj2 ..., xjn ) (un terme,
groupe operatoire a n places).
Soit xj un quantificateur existentiel qui nest precede par aucun quantificateur
universel : on peut le supprimer et remplacer xj par un symbole de constante
(qui nest autre quun groupe operatoire a zero place).
Cette transformation est autorisee par le theoreme suivant :
A = xyp(x, y)
207
2.3 Exemple
Les formes de Skolem de nos formules sont donc :
F1 y(cr(y) co(f (y), y))
F2 xy(cr(y) co(x, y) mal(x))
F3 x(ar(x) mal(x))
F4 xy(mal(x) ar(x) cr(y) co(x, y))
F5 cr(a)
F6 x(mal(x) ar(x))
3 Forme clausale
3.1 Suppression des quantificateurs universels
Dans la forme de Skolem dune formule ne subsistent donc que des quantifica-
teurs universels. Ceux-ci sont purement et simplement supprimes. Cette suppression
est autorisee par la methode de resolution utilisee (et nest possible que si cest cette
methode qui est effectivement utilisee). En effet, pour prouver que la formule T est
consequence de lensemble de formules A, on cherche a prouver que A {T } nad-
met pas de modele. Pour cela, il suffit dexhiber une contradiction dans un (( cas par-
ticulier )) , et il est bien clair que, si, dans lensemble A de formules, on supprime les
quantificateurs universels, et quon prouve que ces formules, avec T , nadmettent pas
de modele, alors les formules (( completes )) , avec quantificateurs, et T , nen auront
pas non plus.
3.2 Clauses
On dit quune formule de (( PR )) est mise sous forme de clause lorsque son ex-
pression nutilise plus de quantificateurs, et que les seuls connecteurs qui y subsistent
sont les connecteurs et . Si une formule, sans quantificateur, se presente sous la
forme A B, elle est remplacee par deux formules : A et B. Il est bien clair que si lon
satisfait, dune part A, et dautre part B, on aura satisfait A B. Une clause (avec ou
sans variables) est donc de la forme : A B C . . .. A, B, C sont les litteraux de
la clause, ils apparaissent sous forme positive (A) ou negative (C). Enfin, la clause
vide (sans litteraux) est representee par . Elle est reputee insatisfiable dans toute in-
terpretation. Dans notre exemple, il ny a plus rien a faire, et les formules de depart
mises sous formes de clauses sont les formules de F1 a F6 , sans les quantificateurs
universels.
208
VI. Systeme de Herbrand
1 Introduction
Pour reconnatre si, oui ou non, un ensemble de formules admet un modele, il
faut essayer diverses bases possibles : a un element, a deux elements, ...., a une infi-
nite delements. Chacun de ces essais conduit lui-meme a de nombreux cas ; linteret
du theoreme de Herbrand est quil affirme que tous ces essais peuvent se ramener
a un seul, qui nutilise que le (( vocabulaire )) des formules qui sont en question, un
(( modele syntaxique )) unique. Par ailleurs la methode des (( tables de verite )) , ou, ce
qui revient au meme, la methode des fonctions de verite booleennes, conduit elle aussi
a un nombre dessais tres rapidement beaucoup trop grand (des que les formules sont
un peu compliquees ou un peu nombreuses et comportent beaucoup de variables. Le
nombre dessais crot comme 2n , et devient tres vite trop important).
209
3 Theoreme de Herbrand
Un ensemble de clauses admet un modele si et seulement sil admet un modele
de base lunivers de Herbrand. De plus, pour que cet ensemble de clauses soit insatis-
fiable, il suffit que lune des formules du systeme de Herbrand ne soit pas satisfiable.
Application :
1ere generation : avec x = a , y = a
{cr(a)co(f (a), a) , cr(a)co(a, a)mal(a) , ar(a)mal(a) , mal(a)
ar(a) cr(a) co(a, a) , cr(a) , mal(a) ar(a)}
satisfiables :
cr(a) co(f (a), a) co(a, a) ar(a) mal(a)
ou
cr(a) co(f (a), a) co(a, a) ar(a) mal(a)
2eme generation : avec x = f (a) , y = a
{cr(a) co(f (a), a) mal(f (a)) , ar(f (a)) mal(f (a)) , mal(f (a))
ar(f (a)) cr(a) co(f (a), a) , mal(f (a)) ar(f (a))}
la premiere exige mal(f (a)), donc la derniere exige ar(f (a)), donc la troisieme
ne peut etre satisfaite : cest termine.
Lensemble de clauses nadmet pas de modele ayant pour base lunivers de Herbrand,
donc il nadmet aucun modele, donc la formule F6 nest pas consequence des cinq
premieres, donc F6 est un theoreme, et donc (( il y a bien des personnes malhonnetes
en liberte )) .
4 Algorithme de Herbrand
Il sagit du premier algorithme de (( demonstration automatique )) . Dun point de
vue theorique, il ne fait rien de plus que celui qui consisterait a produire toutes les
consequences possibles (a laide des regles dinference) des formules de lensemble
de depart, pour essayer de trouver la formule finale comme consequence de cet en-
semble. Il est cependant plus facile a mettre en uvre, et donne souvent le resultat
plus rapidement que la methode des tables de verite. Cependant, il doit etre clair quil
sagit dun algorithme qui sarrete au bout dun temps fini (eventuellement long !) si
lensemble de clauses est insatisfiable, mais qui ne sarrete pas dans le cas contraire
(consequence desagreable de lindecidabilite du calcul des predicats...).
Fin du Chapitre
210
Chapitre 12
Algorithme de resolution
3 Principes generaux
Quelques principes generaux de la resolution sans variable (RSV) :
Les seules formules correctes admises sont les clauses, cest-a-dire des disjonc-
tions de litteraux, positifs ou negatifs (precede de ).
Les seuls connecteurs admis sont et .
Une clause est satisfaite quand lun de ses litteraux est vrai.
La clause vide (ne contenant aucun litteral) ne verifie pas cette condition, elle
est dite insatisfaite.
211
alphabet : les variables propositionnelles, et .
{F, F G} H, {F B, F H} B H
212
la suppression de tautologie,
la suppression des clauses subsumees (C est subsumee par C si tous les litteraux
de C sont dans C : A B C est subsumee par A B).
ab C1 = a b
bc C2 = b c
ca C3 = c a
abc C4 =abc
Generation 1 {C1 , C2 } C5 = a c
{C1 , C3 } C6 = b c
{C1 , C4 } C7 = b c
{C2 , C3 } C8 = a b
{C2 , C4 } C9 = a c
{C3 , C4 } C10 = a b
213
F {C} insatisfiable a condition que F soit satisfiable.
E XEMPLE 2.
ab C1
b c C2
a c C3
abc C4
On va demander a SL resolution un diagnostique sur a (a est deductible de cet en-
semble de clauses).
Le but est (( effacer a dans lensemble des clauses, liste dancetres [] (vide) )).
Avec la clause C4 , on obtient la resolvante {a, a b c} b c.
Le but est remplace par (( effacer les litteraux de b c dans lensemble des clauses,
liste des ancetres [ a ].
Effacer b (( . . . )), liste ancetre [ a ].
Avec C2 {b, b c} c.
(( Effacer c, liste ancetre [ a, b ]. ))
Avec C3 {c, c a} a.
(( Effacer a, liste ancetre [ a, b, c ]. ))
Succes car a dans liste des ancetres.
Effacer c (( . . . )), liste ancetre [ a ].
Avec C3 {c, c a} a.
(( Effacer a, liste ancetre [a]. ))
Succes car a dans la liste des ancetres.
214
Succes pour effacer a.
Il reste a verifier si on peut effacer a.
215
7. Les pantheres ne sont pas aptes a devenir des animaux familiers.
8. Aucun animal non carnivore ne tue de souris.
9. Je deteste les animaux qui ne sattachent pas a moi.
10. Les animaux qui vont roder dehors la nuit aiment toujours contempler la lune.
216
Reponse : Lunivers est { Exercices }.
217
{C3 , C1} V erif ier Ridicule : C7
{C7 , C4} V erif ier Avocat : C8
{C8 , C6} V erif ier Ecrit : C9
{C9 , C2} V erif ier P omme C10
{C10 , C5 } V erif ier Reves
Soit Reves V erif ier : Mes reves ne sont pas verifies.
218
{C7 , C2} Maths Dynamique : C11
{C11 , C10 } Maths ACSI : C12
{C12 , C1 } Maths P rimordiale : C13
{C13 , C8 } Maths Abstraction : C14
{C14 , C5 } Maths Inf ormatique : C15
{C15 , C4 } Maths Interessant : C16
{C16 , C6 } Maths Reussit : C17
{C17 , C9 } Maths Aime : C18
{C18 , C3 } Maths T ravaille
Soit Maths T ravaille : Je ne travaille pas les maths.
7 Exercices
219
14. Un joueur qui se couche avant quatre heures du matin na nul besoin de devenir
conducteur de taxi, a moins quil ne soit doue dun appetit feroce.
15. Un homme doue dun appetit feroce, deprime et qui ne risque nullement de se
ruiner, est un joueur.
220
1 Unification
1.1 Composants de substitutions et substitutions
221
1.2 Unificateurs
Etant donnes deux clauses A et B, on appelle unificateur de ces deux clauses toute
substitution s telle que sA = sB.
2 Resolution
Dans le systeme (( RAV ))(resolution avec variable) :
Les formules sont des clauses du calcul des predicats.
Il ny a pas daxiomes.
Deux regles dinferences :
resolution {af, bg} (f g)}, avec une substitution de renommage,
destinee a faire quil ny ait aucune variable commune entre af et bg,
et un unificateur de (a) et de b.
diminution {a b f } (b f ), ou : unificateur de a et b.
222
On commence donc par un renommage dans lune des deux clauses (qui ne doivent
plus avoir de variable commune) : par exemple dans C2 , (x|y).
(z|g(y))(x|f (c)){p(x, g(y))p(f (c), x)r(x, y, z)} = p(f (c), g(y))idemr(f (c), y, g(y)) p(f (c), g(y
223
La conclusion est valide ssi on peut deduire la clause vide de cet ensemble de
clauses.
{C5 , (y|a)C1} C7 = cv(f (a), a)
{C5 , (y|a)C2} C8 = cv(x, a) ma(x)
{C5 , (y|a)C4} C9 = ma(x) ar(x) cv(x, a)
{C7 , (x|f (a))C8 } C10 = ma(f (a))
{C7 , (x|f (a))C9 } C11 = ma(f (a)) ar(f (a))
{C10 , C11 } C12 = ar(f (a))
{C10 , (x|f (a))C6} C13 = ar(f (a))
{C12 , C13 } : la conclusion etait valide.
3 Strategie de resolution
correction Une strategie de resolution est correcte quand elle ne trouve dans larbre
des deductions la clause vide que lorsquelle est effective.
completude Une strategie de resolution est complete quand elle conduit effectivement
a la decouverte de la clause vide (si elle figure dans larbre de deduction).
224
R EMARQUE 6. Aucune strategie a ce jour ne peut detecter labsence de la clause vide
dans larbre des deductions lorsquil est infini. Ce resultat est du a lindecidabilite du
calcul des predicats.
Deux problemes :
1. gestion de lensemble des clauses,
2. parcours de larbre de deduction.
225
3. Utiliser la strategie de (( preference des clauses simples )) pour decider si la
conclusion est valide ou non.
On presentera la resolution de maniere tres claire : des numeros seront affectes
aux clauses, les deductions seront explicites, par exemple :
((x|a)Ci , Ck ) Cn , avec Cn = . . .
On supprimera au fur et a mesure les clauses subsumees, en indiquant, par
exemple,
5 Exercices
226
Tous ceux qui comprennent la logique peuvent se passer de dormir.
Certains etudiants ne peuvent pas se passer de dormir.
On desire verifier que la conclusion suivante est valide :
Certains etudiants ne comprennent pas la logique.
Exercice 11. Les etudiants de premiere annee dinformatique sont repartis en six
groupes, du groupe A au groupe F.
Chacun de ces groupes est subdivise en deux sous-groupes (A1 , A2 , B1 , B2 , etc. )
Pour lelaboration de lemploi du temps du second semestre, les contraintes sui-
vantes doivent etre respectees :
Si A1 et A2 suivent la meme matiere, sil en est de meme pour B1 et B2 , et si E1
suit la meme que F2 , C1 doit suivre la meme que D2 .
Si A1 et A2 suivent la meme matiere, sil en est de meme pour F1 et F2 , et si B1
suit la meme que C2 , D1 ne peut pas suivre la meme que E2 .
Si C1 , C2 , D1 et D2 suivent la meme matiere, et si A1 ne suit pas la meme matiere
que B2 , E1 ne peut pas suivre la meme que F2 .
Si A1 et A2 suivent la meme matiere, sil en est de meme pour D1 et D2 , et si B1
ne suit pas la meme que C2 , E1 doit suivre la meme que F2 .
Si E1 et E2 suivent la meme matiere, sil en est de meme pour F1 et F2 , et si C1
suit la meme que D2 , A1 doit suivre la meme que B2 .
227
Si B1 , B2 , C1 et C2 suivent la meme matiere, et si E1 ne suit pas la meme matiere
que F2 , D1 doit suivre la meme que E2 .
On souhaite verifier que la conclusion suivante est valide :
A tout instant de la journee, il y aura un groupe au moins dont les deux sous-
groupes ne suivront pas la meme matiere.
On pourra utiliser le predicat mm(x, y) qui signifie que le sous-groupe x1 suit la meme
matiere que le sous groupe y2 , et les symboles de CONSTANTES a, b, c, d, e et f qui
representent les groupes.
228
2 Deduction ordonnee
Une deduction est dite ordonnee quand elle porte sur le litteral de tete (entre deux
clauses).
Fin du Chapitre
229
Chapitre 13
t a b
0 0, 1 3
1 2
2 2 1
3 0, 1, 2
Les etats initiaux sont 0 et 1, le seul etat dacceptation est 2. Le determiniser en lui ap-
pliquant la (( construction par sous-ensembles )) ; donner le graphe du resultat obtenu.
t a b c
r r v r
s s p s
u r v s
v r v s
Soit R la plus petite relation dequivalence sur E (ensemble des etats) telle que uRv,
pRv et sR.
230
1. Verifier quil sagit dune congruence dautomates et dessiner le graphe de
lautomate-quotient.
2. Sachant que, dans lautomate dorigine, letat initial est p et que le seul etat
dacceptation est u, decrire le langage reconnu par lautomate.
Fin du Chapitre
231
Quatrieme partie
232
Chapitre 14
I. Introduction a la compilation
1 Le probleme pose est...
Donner a un ordinateur un fichier contenant du texte, le lui faire lire et comprendre
de maniere a lui faire executer un certain nombre de taches associees a ce fichier
On fait une compilation.
E XEMPLE 1. Dans if (temps == beau ) { etc., les unites lexicales sont (( if )), (( ( )),
(( temps )), (( == )), (( beau )), (( ) )).
233
2.3 Lanalyse semantique
Reconnatre la signification dun texte syntaxiquement correct : essayer de com-
prendre ce que cela signifie (le sens).
Cela implique notemment la transformation de la source en une forme utilisable,
qui fasse apparatre le sens du texte.
E XEMPLE 2 ( D ANALYSE S EMANTIQUE ). toto = titi + tutu ; est une instruction daf-
fectation a la variable (( toto )) dune valeur exprimee par une expression algebrique,
constituee de la somme des variables (( titi )) et (( tutu )).
Affectation
toto Addition
titi tutu
234
Il existe de nombreux types de grammaires, et encore bien plus de formalismes
exprimes pour representer cette grammaire.
Nous utiliseront pour commencer un seul symbolisme pour rempresenter les gram-
maires : la formalisation BNF (Backus-Naur Form).
2 Le formalisme BNF
Dans la syntaxe BNF, une grammaire est constituee dun ensemble de regles.
E XEMPLE 3. Dans if (temps == beau), if est un symbole terminal (on trouve le mot
dans le programme).
N OTATION : Les symboles non-terminaux sont entoures par des chevrons : < >.
235
Le premier membre dune regle de grammaire est un SNT (la regle en constitue
la definition), le second membre est une famille ordonnee (eventuellement vide) de
symboles, terminaux ou non.
< f ct > ::= < type >< nom > ( < parametres > ) < bloc >
< type > ::= int
::= char
D EFINITION 4 (A XIOME DE LA GRAMMAIRE ). Parmi tous les SNT, lun dentre eux
doit designer lensemble du texte a analyser, on lappelle axiome de la grammaire.
La grammaire est terminee quand tous les SNT ont recu au moins une definition.
5 Exercices
Exercice 1. Les mots du langage L sont constitues dun nombre, eventuellement nul,
de a, suivi dun b, suivi dau moins un c.
Donner une grammaire BNF de ce langage.
Exercice 2. Les mots du langage L commencent par un caractere a, suivi dun nombre
pair (eventuellement aucun) de caracteres b, puis de deux caracteres c.
Donner une grammaire BNF de ce langage.
236
Exercice 3. Les mots du langage L sont les noms de variables en C : ils commencent
obligatoirement parune lettre (majuscule ou minuscule), et se poursuivent par un
nombre quelconque de chiffres, lettres ou underscore.
Donner une grammaire BNF de ce langage.
237
(( Qui est le pere de loncle de la mere du petit fils de Paul ? ))
...et tous leurs derives. Ecrire la grammaire correspondante.
1 Principes generaux
On conseille de suivre cette demarche :
1. Commencer par ecrire la grammaire du langage (des expressions correctes).
2. Ecrire lanalyseur syntaxique pur.
3. Passer a lanalyseur syntaxique avec messages derreur.
4. Puis a lanalyseur syntaxique avec interpretation semantique.
2 La grammaire du langage
< expression > : := < groupe0 > < groupe1 >
< groupe0 > : := 0 < suite0 >
< suite0 > : := < groupe0 >
: :=
< groupe1 > : := 1 < suite1 >
< suite1 > : := < groupe1 >
: :=
Il faut :
238
Subdiviser au maximum les expressions en sous-expressions coherentes, en nhesitant
pas a multiplier les niveaux.
Retarder au maximum les alternatives (en multipliant les niveaux) pour ne les
faire intervenir que lorsquon ne peut plus faire autrement.
char s [512];
c h a r ** s s ;
i n t groupe0 ( ) {
i f ( * s s == 0 ) {
s ++;
return suite0 ();
}
return 0;
}
239
p r i n t f ( M auvais \n ) ;
else
p r i n t f ( M auvais \ n ) ;
}
i n t groupe0 ( ) {
i f ( * s s == 0 ) {
s s ++;
return suite0 ();
}
p r i n t f ( L e x p r e s s i o n d o i t commencer p a r 0\ n )
return 0;
}
i n t groupe0 ( ) {
i f ( * s s == 0 ) {
s s ++;
r e t u r n 1+ s u i t e 0 ( ) ;
240
}
p r i n t f ( L e x p r e s s i o n d o i t commencer p a r 0\ n )
return 0;
}
i f ( * s s == \ 0 )
p r i n t f ( Bon \n ) ;
e l s e i f ( * s s == 0 )
p r i n t f ( Nombre de 0 : %d , nomre de 1 : %d , e x p r e s s i o n . z e r o , e x p r e s s
else
p r i n t f ( C a r a c t e r e i n t e r d i t : %c \ n , * s s ) ;
}
ou la structure Expression et la fonction expression() sont ainsi definis :
s t r u c t Expression {
i n t zero ;
i n t un ;
}
Fin du Chapitre
241
Chapitre 15
I. Presentation
Dans la definition de la syntaxe dun langage de programmation, par exemple, on
rencontre souvent des definitions telles que celle dun identificateur :
(( Un identificateur est un identificateur de symbole ou un identificateur de variable ;
un identificateur de symbole commence par deux caracteres alphabetiques, suivi par
un nombre quelconque, eventuellement nul, de chiffres, suivis, etc. ))
Il sagit ici dintroduire des abreviations pour ce type dexpressions ; ces abreviations
conduisent a la notion dexpression rationnelle.
242
II. Regles de definition
Voici les regles qui permettent de definir les expressions rationnelles sur un alpha-
bet :
243
Reponse :
< expression > : := < primitive >
: := < parenthese >
: := < concatenation >
: := < etoile >
< primitive > : :=
: := x (avec x )
< parenthese > : := ( < expression > | < expression > < suite > )
< suite > : := < expression > < suite >
: :=
< concatenation > : := < expression > < expression >
< etoile > : := < primitive > *
: := < parenthese > *
: := < concatenation > *
244
P ROPRI ET E I : Les proprietes de ces operateurs sont les suivants :
1. Associativite : r|(s|t) = (r|s)|t et r(st) = (rs)t.
2. Commutativite de lalternative : r|s = s|r.
3. Distributivite de lalternative sur la concatenation : r(s|t) = rs|rt et (r|s)t =
rt|st.
4. est element neutre pour la concatenation.
5. La repetition est idempotente : r = r .
Exercice 5. Quel est le langage sur {a, b} decrit par lexpression rationnelle : b a(b ab a) b ?
En trouver une (( meilleure )) expression.
Reponse : Lensemble des mots sur {a, b} contenant un nombre impair de a. b a(b|ab a) .
E XEMPLE 2. On peut representer (( une lettre, suivie dun nombre quelconque, eventuellement
nul, de lettres ou de chiffres )) par [a zA Z][a zA Z0 9] .
245
E XEMPLE 3. Il est impossible de decrire, a laide dexpression rationnelles, le langage
defini par
{wcw|w est une chane de a et de b}
Fin du Chapitre
246
Chapitre 16
Automates Finis
I. Automates finis
1 Introduction
On va degager dans ce paragraphe la notion de machine comme modele conceptuel
pour la description de dispositifs informatiques aussi varies quun ordinateur entier, un
logiciel ou un compilateur.
D EFINITION 1 (M ACHINE ). Une machine est un dispositif dote dun certain nombre
detats, susceptible devoluer dun etat a un autre en fonction de divers parametres,
comme le temps (la machine est alors dotee dune machine interne).
Elle est de plus apte a communiquer avec lexterieur : elle peut accepter des donnees
en provenance de lexterieur (des entrees) ou communiquer des resultats a lexterieur
(des sorties).
2 Mecanismes
Cest le type le plus simple de machine :
247
D EFINITION 2 (M ECANISME ). Un mecanisme est totalement impermeable au monde
exterieur, il naccepte aucune entree ni aucune sortie.
Cest une machine a nombre fini detats, dont le comportement est gouverne uni-
quement par le temps, mesure par une horloge interne.
Un mecanisme peut etre entierement decrit par un couple (E, t), ou E est un en-
semble fini detats et t : E E est une fonction de transition des etats.
D EFINITION 3 ( E TAT- REPOS ). Sil existe un etat e E tel que t(e) = e, cet etat est
appele etat-repos .
R EMARQUE 2. Un mecanisme qui entre dans un tel etat nen sort evidemment plus.
E XEMPLE 1. Un feu de circulation routiere peut etre decrit par un mecanisme a trois
etats : V , O et R, donc E = {V, O, R}.
La fonction de transition des etats est telle que t(V ) = O, t(O) = R et t(R) = V .
On peut representer ce mecanisme par le graphe de transition des etats
R V
248
ou par la matrice booleenne T representant t :
0 0 1
T = 1 0 0
0 1 0
e1 0
11
e0 0
249
La table qui donne les valeurs de la fonction t est appelee table de transition detats
de lautomate considere :
t 0 1
e0 e0 e1
e1 e1 e0
Reponse :
0,2 1 2
1 0
u r s
2 0,1
250
0 1
1
s p
q r
1
0,1 0
Reponse :
0 1
p r p
q q q
r r q
s s p
E XEMPLE 3. Ici, E = {e0 , e1 , e2 , e3 }, I = {0, 1}, V = {a, b, c}, t est donnee, soit par
le graphe de lautomate :
251
0
e0 e1 :a
1 0,1
0
e3 :b e2 :c
1
0 1
t 0 1
e0 e1 e3
e1 e2 e2
e2 e3 e2
e3 e3 e2
g se lit dans le graphe : g(e1 ) = a, g(e2 ) = c, g(e3 ) = b.
R EMARQUE 3. Une telle machine est aussi appelee traducteur (elle (( traduit )) lentree
0001001 en une sortie acbcbbc).
R EMARQUE 4. Il est clair que, pour une machine de Moore (E, I, t, e0 , V, g), on peut
definir une machine de Mealy equivalente (cest-a-dire qui produit la meme sortie sur
toute sequence dentree), en posant h(e, i) = g(t(e, i)), soit h = got.
Reciproquement, en introduisant au besoin des etats supplementaires, on montre
quon peut remplacer toute machine de Mealy par une machine de Moore equivalente.
252
3 Automates de Moore
Lensemble des entrees I peut etre considere comme lalphabet dun systeme for-
mel.
Lensemble des (( mots )) construits avec cet alphabet (suite delements de lalpha-
bet) qui conduisent la machine a un etat dacceptation peut etre considere comme
lensemble des formules bien formees de ce systeme formel.
N OTATION : L(M)
R EMARQUE 6. Cela nest pas possible pour tous les langages. Quand cest possible,
cet automate analyse les mots du langage.
253
2 Exemple et exercices
0,1
1
e0 e1
0 0
e2 e3
1
0 1
t 0 1
e0 e1 e2
e1 e1 e2
e2 e2 e1
Letat initial est e0 et le seul etat dacceptation est e2 .
Exercice 7. Sur lalphabet I = {0, 1}, construire lautomate de Moore dont le lan-
gage est lensemble de tous les mots sur I se terminant par 10.
254
Reponse :
0 1
1 0
e0 e1 e2
1
Exercice 8. Construire un automate de Moore dont lalphabet est constitue des lettres
du mot (( ALGUE )) qui reconnat les mots contenant la sous-chane (( GEL )) (et seule-
ment celle-ci).
Reponse :
A,L,U,E G A,L,G,U,E
G E L
e0 e1 e2 e3
A,L,U
A,G,U,E
On peut imaginer des automates moins (( rigides )), pour lesquels, dans certaines
configurations, plusieurs transitions detats sont possibles ou, au contraire, aucune
nest prevue.
255
Pour un tel automate, qualifie de non-deterministe, t nest plus une fonction, mais
une relation binaire quelconque. Ainsi...
R EMARQUE 7. Il se peut donc quune entree puisse conduire un automate vers plu-
sieurs etats possibles ou quelle laisse lautomate indifferent.
E XEMPLE 5. Dans cet exemple, lorsque lautomate se trouve dans letat e0 , lentree a
peut le faire passer dans letat e1 ou dans letat e3 et, lorsquil se trouve dans letat e1 ,
rien nest prevu pour lentree b.
a,b,c
a,b
e0 e3
c a,b
a
c
e1 e2
c
a
Table de transitions
t a b c
{e0 } {e1 , e3 } {e3 }
{e1 } {e1 } {e2 , e3 }
{e2 } {e2 } {e2 } {e1 }
{e3 } {e3 } {e3 } {e3 }
Il est evidemment possible de concevoir des AFND produisant des sorties, et, en
particulier, des etats dacceptation et de rejet. On admettra par ailleurs quil puisse y
256
avoir, dans ces cas, plusieurs etats initiaux possibles.
t 0 1
e0 e0 , e1 e1
e1 e2
e2 e2 e1
e3 e0 , e1 , e2
Si e0 et e1 sont les etats initiaux et si e2 est le seul etat dacceptation, les mots
001111 et 01001 sont-ils reconnus par M ?
257
2 Utilite
Les AFND sont beaucoup plus simple a construire que les AFD.
Ainsi, les algorithmes de construction automatique dautomates produisent des
AFND, et les algorithmes de simplification dautomate utilisent des AFND.
Mais, etant non deterministes, ils ne sont pas programmables. Heureusement, on
sait les determiniser (i.e. construire un automate de Moore qui reconnat le meme lan-
gage)...
258
2 En pratique
En pratique, on part de letat initial de M, cest-a-dire de S.
Pour chacune des entrees, on forme lensemble Sx des etats de M que la relation de
transition t permet datteindre a partir de tous les etats de S, et on pose T (S, x) = Sx .
On recommence loperation pour chacun des etats Sx ainsi obtenus (pour les di-
verses entrees x), etc.
R EMARQUE 8. Le processus a une fin, parce que E est fini, donc aussi P(E) : si
lautomate de depart a n etats, lautomate determinise en aura au plus 2n ..
R EMARQUE 9. Il se peut quaucun etat ne soit accessible depuis lun quelconque des
etats dun etat Yx de M, sur une entree y.
On prend alors pour etat darrivee de M lensemble vide ; celui-ci constitue un etat
particulier de M, dont on ne peut sortir sur aucune entree (c.f. exemple ci-dessous).
E XEMPLE 8. Un exemple...
e1 1
1 1
0
e0 e1 e1 ,e3 0
1 0
0,1
0,1 0 e0 ,e1 e1 ,e2 ,e3 e3 0,1
1 0,1
e2 e3 0 e2 ,e3 1
1
1
0 e2
0 0
Exercice 10. Construire des automates de Moore equivalents aux AFND ci-dessous :
259
0
b
1 4
0 a
3 4 c c
a
1 1 0 3 6
1 1 a a
a
1 b
0 1 2 2 5
0,1 0 0
Exercice 11. Construire des automates de Moore reconnaissant les langages definis
par les expressions regulieres :
1. (a|b) b(a|b)
2. ((a|b)2 ) |((a|b)3 )
3. (a2 |b2 ) |(a3 |b3 )
4. ba |ab|(a|bb)ab .
a a,b
e0 b e1
VI. Exercices
260
2. Fabriquer un automate qui accepte les mots de longueur impair.
3. Fabriquer un automate qui accepte les mots dont la longueur est congrue a 1
modulo 4.
Exercice 13. Soit un automate fini deterministe A qui a n etats et qui na pas detat
inaccessible.
Montrer quil existe necessairement un mot de longueur inferieure ou egale a n1
qui est accepte par A.
2 Les palindromes
Exercice 15 (Suite palindrome). Soit = {a, b}. Construire un AFD qui accepte les
palindromes de longueur 3.
261
Exercice 16. Soit = {a, b}. On note L le langage constitue des mots dans lesquels
la lettre a, quand elle apparat, est toujours suivie dau moins deux lettres b.
1. Quels sont les mots de L de longueur inferieure ou egale 6 ?
2. Construire un AFD qui accepte L.
3. Donner une expression reguliere qui decrit L.
Fin du Chapitre
262
Chapitre 17
Loptimisation des programmes danalyse syntaxique (dont certains sont des realisations
concretes dautomates finis) rend necessaire la construction dun automate minimal (en
nombre detats) qui reconnaissent un langage donne.
I. Congruences dautomates
Soit (E, I, t) un AFD et R une relation dequivalence sur E.
1 Quelques rappels
On rappelle que R est une relation binaire sur lensemble E des etats, qui a en plus
les proprietes suivantes...
- reflexivite. Pour tout etat e E, eRe,
- symetrie. Pour tout couple detats (e1 , e2 ) E 2 : si e1 Re2 , alors e2 Re1 ,
- transitivite. Pour tout triplet detats (e1 , e2 , e3 ) E 3 : si e1 Re2 et e2 Re3 , alors
e1 Re3 .
263
1
0
e0 e1
0,1 0
1
e2 e3
1
0
2 Definition
Cest-a-dire si toute paire detats equivalents modulo R est transformee par toute
entree en une paire detats equivalents modulo R.
264
3 Ensemble quotient
Soit R une congruence dautomates sur lAFD (E, I, t).
Soit R la relation dequivalence pour laquelle E/R = {{e0 , e2 }, {e1 , e3 , e5 }, {e4 }}.
1. Donner la table de transition detats de lautomate-quotient.
2. Representer son graphe
Reponses :
E a b
A = {e0 , e2 } {e0 , e2 } {e4 }
B = {e1 , e3 , e5 } {e1 , e3 , e5 } {e0 , e2 }
C = {e4 } {e4 } {e1 , e3 , e5 }
265
a
b
a C b
b
Exercice 4. Soit M lautomate fini dont la table de transition des etats est
t 0 1
1 1 4
2 3 5
3 2 5
4 4 1
5 3 4
Exercice 5. Soit M lautomate fini dont le graphe est represente par la figure
266
0 0
1 1 O
0 1 5 2
1
0 1
1 1
3 4
0 0
Le tableau ci-dessous figure une relation binaire R dans lensemble des etats E =
{0, 1, 2, 3, 4, 5} :
0 1 2 3 4 5
0 1 0 0 0 1 0
1 0 1 0 0 0 1
2 0 0 1 1 0 0
3 0 0 1 1 0 0
4 1 0 0 0 1 0
5 0 1 0 0 0 1
Un chiffre 1 a lintersection de la ligne i et de la colonne j signifie que iRj, et un
chiffre 0 que ces deux elements ne sont pas en relation.
1. Montrer que R est une relation dequivalence sur E.
2. Montrer que R est une congruence dautomates.
3. Representer le graphe de lautomate-quotient M/R.
Reponses :
E 0 1
A = {0, 4} {0, 4} {1, 5}
B = {1, 5} {3, 2} {1, 5}
C = {3, 2} {3, 2} {0, 4}
267
0
A
1
0 C 1
0
B
R EMARQUE 1. On peut definir une application tx : E E par tx (e) = [tx (e)], puis
une application t : E I E par (e, i) 7 tx (e).
(q s) (w I , q et s sont w-compatibles)
268
2 Lalgorithme
2.1 La theorie
Pour obtenir lequivalence de Nerode associee a un automate, on dispose de lal-
gorithme suivant...
Cette relation est clairement une relation dequivalence, et Rk+1 est plus fine que
Rk . Lequivalence de Nerode est lintersection de ces relations Rk , pour toutes les
valeurs de k entier.
2.2 La pratique
Cet algorithme nest pas utilisable dans la pratique. On fait plutot...
1. Prendre comme partition de depart P0 = {A, E \ A}.
2. Si Pk = {E1 , . . . , En } est la partition correspondant a la relation Rk , morceler
eventuellement chaque classe Ei en sous-classes Ei1 , Ei2 , . . . , Eip de maniere
que deux etats q et s appartiennent a la meme sous-classe si, pour toute entree x,
les etats tx (q) et tx (s) appartiennent a la meme classe Ej (pouvant dependre de
x).
Lensemble des sous-classes obtenues constitue la partition correspondant a la
relation Rk+1
3. Repeter letape precedente jusqua ce que Pk+1 = Pk . La relation Rk est alors
lequivalence de Nerode associee a M.
R EMARQUE 2. Letape (3) est necessairement atteinte, puisque les relations Rk sont
de plus en plus fines.
Au pire, P = {{q}kq E}, la relation est legalite : ceci signifie que lautomate
nest pas simplifiable.
269
b
a
1 2 3
a
a
1 2,6
b a b
b
b
4 7 a,b b b a 7 a,b
a
a a
b a
4 3,5
b
5 6
a
b
t a b
0 1 2
1 5 3
2 5 1
3 4 5
4 5 4
5 5 5
Etat initial : 0
Etats dacceptation : 4
Cet automate reconnat le langage defini par lexpression reguliere (a|bb)bab .
Appliquer la methode de lequivalence de Nerode pour trouver lautomate minimal
reconnaissant le langage.
270
Exercice 7. Faire de meme avec lautomate de Moore dont la table de transition est :
t a b
a a c
b g d
c f e
d a d
e a d
f g f
g g c
2 Methode du dual
Soit M un automate de Moore :
1. Construire lautomate dual M 1 de M.
2. Appliquer la construction par sous-ensembles a M 1 pour le transformer en
automate M de Moore.
3. Construire le dual M 1 de M .
4. Appliquer la construction par sous-ensemble a M 1 pour obtenir lautomate de
Moore M .
Lautomate M est lautomate minimal tel que L(M ) = L(M).
271
Exercice 8. On donne un AFD par la table de transition des etats suivante :
t a b
0 1 2
1 3 4
2 3 4
3 5 6
4 5 6
5 7 8
6 7 8
7 9 10
8 9 10
9 11 12
10 11 12
11 1 2
12 1 2
Etat initial : 0
Etats dacceptation : 0 3 4 5 6 7 8 11 12
Cet automate reconnat le langage defini par lexpression reguliere ((a|b)2 ) |((a|b)3 ) .
Appliquer la methode du dual pour trouver lautomate minimal reconnaissant le lan-
gage.
272
la table de transition suivante :
t a b
0 1, 11
1 2, 7
2 3
3 4, 6
4 5
5 4, 6
6 10
7 8
8 9
9 10
10 22
11 12, 14
12 13
13
14 17 15
15 16
16 17
17 18
18 19, 21
19 20
20 19, 21
21 22
22
Etat initial : 0
Etat dacceptation : 22
Cet automate reconnat le langage defini par lexpression reguliere ba |ab|(a|bb)ab .
Le determiniser, puis lui appliquer la methode de votre choix pour obtenir lautomate
minimal reconnaissant le langage.
273
Exercice 10. On donne la table de transition suivante pour un automate fini :
t a b
0 1 2
1 3 4
2 5 6
3 1 2
4 7 8
5 7 8
6 1 2
7 9 10
8 10 11
9 7 8
10 10 10
11 7 8
Appliquer a cet automate lalgorithme de votre choix pour obtenir lautomate minimal
reconnaissant le meme langage (equivalence de Nerode ou dual).
(Lautomate minimal possede 7 etats).
IV. Synthese
1 Outils
1.1 Construction par sous-ensemble
Domaine dapplication : Cette methode sapplique aux automates finis non deterministes.
Il est aussi possible de lutiliser sur un AFD, mais cest sans interet.
Resultat : Automate reconnaissant le meme langage.
But : Obtenir un AFD reconnaissant le meme langage.
Autre utilisation : Peut permettre dobtenir lautomate minimal reconnaissant le meme
langage (methode du dual).
274
1.2 Equivalence de Nerode
Domaine dapplication : Cette methode ne sapplique quaux automates finis deter-
ministes (AFD).
Resultat : Le quotient de lautomate considere par lequivalence de Nerode ; un au-
tomate ne reconnaissant generalement pas le meme langage.
But : Simplifier lautomate considere, si cest possible, grace a la methode des quo-
tients.
2 Methodes doptimisation
2.1 Methode des quotients
Domaine dapplication : Cette methode ne sapplique quaux automates finis deter-
ministes (AFD).
Moyens : Equivalence de Nerode.
Resultat : On obtient lautomate minimal reconnaissant le meme langage.
Fin du Chapitre
275
Chapitre 18
III. Algorithme
1. Decomposer lexpression en ses sous-expressions.
276
2. En utilisant les regles (a) et (b) ci-dessous, construire un AFND pour les sym-
boles terminaux de la grammaire ou la chane vide (si un meme symbole a ap-
parat plusieurs fois dans lexpression rationnelle, un AFND separe est construit
pour chacune de ses occurences).
3. Combiner ensuite recursivement les AFND de base en utilisant la regle (c) jus-
qua obtenir lAFND pour lexpression rationnelle toute entiere.
(a) Pour <>, construire lAFND :
d f
a
d f
(c) Si N(s) et N(t) sont les AFND pour les expressions rationnelles s et t,
Pour st, on construit lAFND :
d N(s) N(t) f
Letat initial de N(t), qui est etat dacceptation pour N(s), perd ce
double caractere dans la nouvelle construction.
Pour s|t, on construit lAFND
N(s)
d f
N(t)
Les etats initiaux et les etats dacceptation des AFND de N(s) et de N(t)
perdent leur caractere dans le nouvel AFND.
277
Pour lexpression rationnelle s , on construit lAFND compose N(s ) :
d N(s) f
Les etats initiaux et les etats dacceptation de N(s) perdent leurs qua-
lites.
Pour une expression parenthesee (s), utiliser N(s) lui-meme.
IV. Exemple
On applique lalgorithme sur lexemple : (a2 |b2 ) |(a3 |b3 ) .
a a
3 4 5
1 2 9 10
b b
6 7 8
0 23
a a a
13 14 15 16
11 12 21 22
b b b
17 18 19 20
278
Exercice 1. On donne lexpression rationnelle (a|b) |(a2 |b2 ) .
Utiliser lalgorithme de Thompson pour obtenir un automate non deterministe, a
transitions instantanees, reconnaissant le langage.
On rappelle que, par definition, sont accessibles sur une entree donnee x depuis un
etat donne e : les etats accessibles en effectuant successivement
un nombre arbitraire (eventuellement nul) de transitions instantannees,
une transition dentree x et
un nombre arbitraire (eventuellement nul) de transitions instantannees.
E XEMPLE 1. Pour...
Letat 3, avec entree a : on passe a letat 4.
Si lentree a se produit au depart, les etats accessibles sont {4, 14}.
Et, a partir de letat 4 et de lentree a : {5, 9, 2, 10, 23, 3, 6}.
V. Finalisation
Lautomate construit par algorithme de Thompson nest pas utilisable tel quel.
Il faut en supprimer les transitions instantanees, ce qui se fait par un algorithme voi-
sin de la construction par sous-ensembles. Il faudra, par ailleurs, ensuite, le determiniser
et le minimiser.
On remplace cet automate par un automate M qui reconnat le meme langage, dont
lensemble des etats est E, letat initial est S, et lensemble des etats dacceptation est
A E et qui est obtenu de la maniere suivante :
S est compose de e et de tous les etats de M qui sont accessibles depuis e par un
nombre quelconque de transitions instantanees (eventuellement aucune). Dans
lexemple precedent,
S = {0, 1, 11, 2, 10, 12, 22, 3, 6, 13, 17, 23}
.
279
Soit Y E une partie de lensemble des etats, et x une entree. Limage Yx de Y
est constituee des etats accessibles depuis un etat quelconque de Y par (exacte-
ment) une entree x, suivie dun nombre quelconque de transitions instantanees.
A = {Y E|Y {a} 6= }, a savoir les parties Y ci-dessus definies de E qui
contiennent lancien etat dacceptation.
Exercice 3 (Reprise dun exercice precedent, version Thompson). Construire des au-
tomates de Moore reconnaissant les langages definis par les expressions rationnelles :
1. (a|b) b(a|b)
2. ((a|b)2 ) |((a|b)3 )
3. ba |ab|(a|bb)ab .
Exercice 4. Donner les automates finis minimaux (table de transition, diagrame) re-
connaissant les langages associes aux expressions rationnelles suivantes :
(a|b) (aaa|bb)
(a|bb) abb
Fin du Chapitre
280
Chapitre 19
Automates a pile
E XEMPLE 1. Le langage defini par {an bn |n N } nest pas representable par une
expression rationnelle.
281
1. Un alphabet dentree (ensemble fini non vide),
2. Un ensemble detats E (fini non vide),
3. Un etat initial e0 E ,
4. Eventuellement, une partie A E des etats dacceptation (pour un automate a
pile dit a etats dacceptation),
5. Un alphabet de pile P (fini, non vide),
6. Un symbole de pile initial p0 ,
7. Eventuellement, un ensemble Q P de symboles de sommet de pile,
8. Enfin, une relation t : E ( {}} P E P .
1.2 Transition
Comme t est une relation, il est possible, dans le cas dun automate a pile non
deterministe, quil y ait plusieurs transitions possibles dans la meme situation (meme
etat, meme entree, meme symbole de sommet de pile).
282
Cet automate reconnat, par pile vide, lensemble
R EMARQUE 4. En particulier si t est definie pour le triplet (e, x, p), t(e, x, p) est
unique.
E XEMPLE 3 (AUTOMATE A PILE D ETERMINISTE ). Ici, lalphabet dentree est {0, 1},
le fond de pile est Z et alphabet de pile {Z, A} :
R EMARQUE 5. Cet automate a pile deterministe reconnat, par etat final, le meme
langage que lexemple precedent.
283
2.2 Transitions
Il est fondamental de comprendre quune transition dun automate a pile, quelle
quelle soit, exige toujours de depiler un symbole de pile.
D EFINITION 6 (C ALCUL VALIDE ). Un calcul valide dans lautomate est une famille
de derivations (e1 , w1 , q1 ) (e2 , w2 , q2 ) . . . (en , wn , qn ).
On dit que ce calcul valide mene de la configuration (e1 , w1 , q1 ) a la configuration
(en , wn , qn )
N OTATION : On peut noter cela : (e1 , w1, q1 ) (en , wn , qn ).
284
D EFINITION 7 (M OT RECONNU ). On dit quun mot w est reconnu par un automate a
pile (etat initial e0 , symbole de pile initial p0 ) lorsquil existe un calcul valide
(e0 , w, q0 ) (e, , q)
On demontre que...
Cest pourquoi nous nenvisagerons plus que cette derniere dans la suite. Enfin,
2 Premiers exemples
E XEMPLE 4. Automate a pile (non deterministe) reconnaissant, par pile vide, len-
semble des mots de la forme ww t, concatenation de w (constitue de 0 et de 1) et de
son image miroir :
285
(Alphabet dentree {0, 1}, fond de pile Z, alphabet de pile {Z, A, B}.)
E XEMPLE 5. Automate a pile reconnaissant, par pile vide, lensemble des mots de la
forme wcw t , concatenation de w (constitue de 0 et de 1) et de son image miroir separes
par le caractere c :
(Alphabet dentree {0, 1, c}, fond de pile Z, alphabet de pile {Z, A, B}.)
286
III. Construction dun automate a pile
1 Introduction a la methode
On peut evidemment utiliser la methode (( directe )), comme dans lexemple precedent.
Pour les langages plus complexes, il peut etre necessaire davoir recours a un algo-
rithme. Nous laborderons par lexemple de la grammaire ecrite pour les expressions
algebriques elementaires :
E > T
E > T +E
T > F
T > F T
F > (E)
F > a
F > b
...
F > z
...en admettant comme symboles de variables les caracteres alphabetiques minuscules.
3 Algorithme de construction
Le principe est de construire un automate a pile non deterministe qui admet des
transitions vides :
1. Au depart, sur une transition vide, on empile le SNT de laxiome de la grammaire
(ici, E) : c.f. transition (1).
287
2. associer a chaque regle non terminale une -transition qui empile les symboles
de la partie droite (c.f. transitions (2) a (6))
3. associer a chaque regle terminale A x une transition (e0 , x, A) 7 (e0 , ) (c.f..
transitions (7) et (8))
4. associer a chaque symbole terminal une transition qui reconnat ce symbole et
depile ce caractere (c.f. transitions (9) a (12))
4 Exercices
Exercice 3. Soit lautomate a pile defini par = {a, b}, E = {q0 , q1 , q2 }, P = {p, A}
et les transitions suivantes
(q0 , a, p0 ) 7 (q1 , A)
(q1 , b, A) 7 (q2 , )
(q1 , a, p) 7 (q1 , Ap)
(q2 , b, A) 7 (q2 , )
288
3. Decrire letat de lautomate apres avoir lu n symboles a en entree (n N).
Quelle est alors la seule facon de vider la pile ? En deduire le langage reconnu
par cet automate a pile avec arret sur pile vide.
Exercice 5. Soit = {0, 1}. Donner un automate a pile qui accepte un mot u
ssi aucun prefixe de u ne contient plus de 1 que de 0. Preciser si lautomate est
deterministe.
Exercice 6. Soit = {1, 2}. Donner un automate a pile qui reconnat le langage
suivant :
{1n 2n |n > 0} {1n 22n |n > 0}
Preciser si lautomate est deterministe.
Exercice 7. Soit = {a, b, c}. Donner un automate a pile qui reconnat le langage
suivant :
{ai bj ck |i = j ou j = k}
Preciser si lautomate est deterministe.
289
1. Donner des exemples de mots reconnus.
2. Donner un automate a pile qui reconnat le langage genere par la grammaire
G.
Fin du Chapitre
290
Chapitre 20
Dans ce paragraphe, nous precisons les elements sur les grammaires et sur les
langages qui ont deja ete vus jusqua present.
I. Langages
N OTATION : Soit un ensemble de symboles, on note par lensemble des mots
sur , cest-a-dire lensemble des assemblages de symboles de .
N OTATION : Une telle production est le plus souvent notee , qui se lit (( se
reecrit en )).
R EMARQUE 1. La fleche nest pas ici le symbole de limplication logique, mais ce-
lui de reecriture (dans la symbolisation BNF, ou Bakus-Naur form, le symbole de
reecriture est (( : := )) ).
292
2.3 Les grammaires algebriques, ou de type 2
Toute production est de la forme A , ou A N et ( N) .
Il y a equivalence entre les langages reconnaissables par des automates a pile et les
langages algebriques (engendres par une grammaire algebrique).
Ces grammaires sont appelees (( contextuelles )) parce quil est impossible de don-
ner une definition (( independante )) de chacun des SNT, comme dans les grammaires
algebriques.
293
E XEMPLE 2. On ne peut, par exemple dans la grammaire ci-dessus, pas donner de
definition du SNT B independamment des symboles qui lentourent, donc la definition
de B est sensible au contexte et la grammaire dans laquelle elle figure est dite contex-
tuelle.
Fin du Chapitre
294
Chapitre 21
295
1. Verifier quil sagit dune congruence dautomates et dessiner le graphe de
lautomate-quotient.
2. Sachant que, dans lautomate dorigine, letat initial est p et que le seul etat
dacceptation est u, decrire le langage reconnu par lautomate.
Fin du Chapitre
296
Cinquieme partie
297
Chapitre 22
2 Exemples
Les graphes non orientes admettent une representation graphique permettant leur
visualisation :
298
Signalons aussi des a present la possibilite de ponderer les aretes dun graphe non
oriente :
3 Degre, chane
3.1 Degre dun sommet, dun graphe
P ROPRI ET E I (L EMME DES POIGN EES DE MAINS ) : La somme des degres des
sommets dun graphe est egale a deux fois le nombre daretes.
Exercice 1. Calculez les degres des sommets, et le degre des graphes ci-dessus.
299
D EFINITION 4 (G RAPHE R EGULIER ). Un graphe dont tous les sommets ont le meme
degre est dit regulier. Si le degre commun est k, alors on dit que le graphe est k-
regulier.
3.2 Chane
ayant pour elements alternativement des sommets (vi ) et des aretes (ei ),
commencant et se terminant par un sommet,
et telle que les extremites de ei soient vi1 et vi , i = 1, ..., k .
D EFINITION 7 (C HA INE EL EMENTAIRE ). Une chane dans lequel tous les sommets
sont differents sappelle une chane elementaire .
300
R EMARQUE 4. On parle aussi de chane simple .
R EMARQUE 5. Une chane simple a forcement toutes ses aretes differentes, et ne
contient evidemment pas de boucle.
4 circuit-cycle
D EFINITION 9 (C YCLE ). Un circuit dont tous les sommets et toutes les aretes sont
differentes, sappelle un cycle.
R EMARQUE 6. Dans le cas non oriente, un circuit qui a tous ses sommets differents
na pas forcement toutes ses aretes differentes.
D EFINITION 10 (G RAPHE SIMPLE ). Un graphe est dit simple, sil ne contient pas de
boucles et sil ny a pas plus dune arete reliant deux memes sommets.
301
5 Exercices
Exercice 8. Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit
relie avec exactement trois autres ?
Exercice 9. Un groupe de 15 fans dun chanteur celebre, possede les deux particula-
rites suivantes :
Chaque personne connat au moins 7 autres
Toute information detenue par une personne est repercutee dans la minute qui
suit a ses connaissances (et uniquement a elles)
Quel est le temps maximal entre le moment ou une des 15 fans apprend une chose
nouvelle sur leur idole, et celui ou le groupe entier est au courant ?
302
II. Quelques types particuliers de graphes
1 Graphes planaires
2 Multigraphes
Les graphes etudies ici sont simples, mais on peut imaginer des graphes avec une
arete qui relie un sommet a lui-meme (une boucle), ou plusieurs aretes reliant les deux
memes sommets (voir ci-dessous, a gauche).
V = {1, 2, 3, 4}
E = {(1,1), (1,3), (1,4), (2,3), (2,3), (3,4)}
303
3 Graphes connexes
D EFINITION 13 (G RAPHE CONNEXE ). Un graphe est connexe sil est possible, a par-
tir de nimporte quel sommet, de rejoindre tous les autres en suivant les aretes.
R EMARQUE 8. Cest en particulier le cas lorsqua partir dun sommet on peut at-
teindre tous les autres sommets.
Exercice 12. Representer un graphe non oriente connexe, et un graphe non connexe.
E XEMPLE 3 (G RAPHE NON CONNEXE ). Exemple dun graphe netant pas connexe :
V = {1, 2, 3, 4, 5, 6}
E = {(1,3), (1,4), (2,3), (3,4), (5,6)}
4 Graphes complets
304
E XEMPLE 4 (G RAPHE COMPLET K5 ). Exemple dun graphe complet :
V = {1, 2, 3, 4, 5}
E = {(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)}
Exercice 13. Un tournoi dechecs oppose 6 personnes. Chaque joueur doit affronter
tous les autres.
1. Construisez un graphe representant toutes les parties possibles.
2. Quel type de graphe obtenez-vous ?
3. Si chaque joueur ne joue quun match par jour, combien de jours faudra-t-il
pour terminer le tournoi ?
4. Aidez-vous du graphe pour proposer un calendrier des matches.
5 Graphes biparti
305
V = {1, 2, 3, 4, 5}
E = {(1,2), (1,4), (2,3), (2,5), (3,4), (4,5)}
Avec les notations de la definition, on a X={1, 3, 5} et Y={2, 4}, ou vice versa.
6 Exercices
Exercice 14. Trois professeurs P1, P2, P3 doivent donner ce lundi un certain nombre
dheures de cours a trois classes C1, C2, C3 :
P1 doit donner deux heures de cours a C1 et une heure a C2.
P2 doit donner une heure de cours a C1, une heure a C2 et une heure a C3 ;
P3 doit donner une heure de cours a C1, une heure a C2 et deux heures a C3.
On demande...
1. Comment representer cette situation par un graphe ?
2. Quel type de graphe obtenez-vous ?
3. Combien faudra-t-il de plages horaires au minimum ?
Aidez-vous du graphe pour proposer un horaire du lundi pour ces professeurs.
Exercice 15. Sur un echiquier 3x3, les deux cavaliers noirs sont places sur les cases
a1 et c1, les deux cavaliers blancs occupant les cases a3 et c3. Aidez-vous dun graphe
pour determiner les mouvements qui permettront aux cavaliers blancs de prendre les
places des cavaliers noirs, et vice versa.
306
Exercice 16. Quel est le nombre maximal daretes dans un graphe non oriente dordre
n qui ne possede pas daretes paralleles ? Et si lon suppose quil ne possede pas de
boucle ?
n(n + 1)
Reponse : .
2
1 Matrice dincidence
1.1 Presentation
La matrice dincidence dun graphe non oriente est une matrice J a coefficients
entiers dont les lignes sont reperees par les sommets dun graphe et les colonnes par
ses aretes :
Exercice 17. Representez le graphe non oriente dont la matrice dincidence est :
1 0 0 0 0 0 0 0 0
0 1 1 0 1 0 0 1 0
0 0 0 0 1 0 0 1 1
0 0 0 1 0 0 2 0 1
0 0 1 1 0 1 0 0 0
0 1 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0 0
307
1.2 Resultat
2 Matrice dadjacence
2.1 Presentation
On peut representer un graphe non oriente par une matrice dadjacences.
Dans une matrice dadjacences, les lignes et les colonnes representent les sommets
du graphe.
Un 1 a la position (i,j) signifie que le sommet i est adjacent au sommet j.
2.2 Exemple
Considerons le graphe G :
308
2.3 Proprietes de la matrice dadjacence
Cette matrice a plusieurs caracteristiques :
309
Exercice 21. On pose :
2 1 0 1
J = 0 1 1 0
0 0 1 1
1. Dessinez le graphe non oriente ayant J pour matrice dincidence.
2. Determinez sa matrice dadjacence B.
3. Verifiez les formules precedentes.
3 Listes dadjacence
On peut encore representer un graphe en donnant pour chacun de ses sommets la
liste des sommets auxquels il est adjacent.
310
3.1 Avantages et inconvenients de cette representation
Avantages Representation adaptee aux graphes peu denses.
Representation des graphes ponderes.
Faible occupation memoire.
Inconvenients Difficulte de savoir si deux sommets sont effectivement connectes.
Difficulte de mise en uvre.
Fin du Chapitre
311
Chapitre 23
I. Circuits euleriens
1 Introduction : les ponts de Konigsberg
La question a lorigine de la theorie des graphes est due a Euler1 , en 1736 : dans
cette partie de la ville de Konigsberg :
peut-on, lors dune promenade, revenir a notre point de depart en empruntant une, et
une seule fois, chaque pont ?
Pour y repondre, Euler a introduit le graphe suivant :
1
Leonhard Euler, mathematicien suisse (1707-1783). A consacre pres de 900 memoires aux
mathematiques, a loptique, a la science navale, a la musique, latronomie, la theorie des assurance...
312
Le probleme de depart se ramene alors a la question suivante : peut-on trouver un
chemin permettant demprunter une, et une seule fois chaque arete ? Un raisonnement
elementaire sur ce graphe en donne la reponse.
2 Definitions
Exercice 1. Donnez des exemples de graphes possedant des circuits euleriens, et dautres
exemples de graphes nen possedant pas.
Exercice 2. Soit G un graphe non eulerien. Est-il toujours possible de rendre G eulerien
en lui rajoutant un sommet et quelques aretes ?
313
3 Resultat dEuler
P REUVE 3 :
En parcourant un chemin ou un circuit, pour chaque sommet visite, on utilise une
arete pour arriver a ce sommet et une arete pour en repartir, ces deux aretes ne
devant plus etre utilisees par la suite. Le nombre daretes utilisables en ce sommet
diminue donc de deux. Si un sommet est dordre impair, une de ses aretes aboutis-
sant a ce sommet doit donc etre soit sur la premiere arete dun chemin, soit sur la
derniere. Un chemin nayant que deux extremites, le nombre de sommets dordre
impair ne peut exceder deux.
314
E XEMPLE 1 (L E GRAPHE G). On considere, dans ce paragraphe, pour illustrer les
definitions a venir, le graphe
Soit :
G=(V, E),
V={v1 , v2 , v3 , v4 , v5 },
E={e1 = (v1 , v2 ), e2 = (v2 , v3 ), e3 = (v1 , v3 ), e4 = (v3 , v4 ), e5 = (v3 , v5 )}
Ici,
V=V,
E={e3 , e4 , e5 }.
315
D EFINITION 5 (S OUS - GRAPHE ). On dit que le graphe (V , E ) est un sous-graphe du
graphe (V, E) si
1. V V ,
2. E E ,
3. E = {(x, y) | (x, y) E x V y V }
R EMARQUE 4. Un sous-graphe dun graphe donne est donc obtenu en y enlevant des
sommets et toutes les aretes incidentes a ces sommets.
Ici,
V={v1 , v3 , v4 , v5 },
E={e3 , e4 , e5 }.
316
Ici,
V={v1 , v2 , v3 , v4 },
E={e1 , e4 }.
Ici,
V={v1 , v2 , v3 },
E={e1 , e2 , e3 }.
Ici,
V={v1 , v4 , v5 },
E={}.
317
Exercice 4. Montrez que dans un groupe de six personnes, il y en a necessairement
trois qui se connaissent mutuellement ou trois qui ne se connaissent pas (on suppose
que si A connat B, B connat egalement A).
Montrez que cela nest plus necessairement vrai dans un groupe de cinq personnes.
Reponse : Un graphe ayant six sommets possede soit une clique a trois sommets, soit
un stable a trois sommets.
Cela nest plus valable pour les graphes a cinq sommets.
Reponse : 2n 1.
2 Graphe planaire
On rappelle la definition...
D EFINITION 9 (G RAPHE PLANAIRE ). Un graphe est dit planaire sil admet une re-
presentation graphique dans le plan telle que deux aretes quelconques ne se coupent
pas.
Exercice 6. Un graphe peut-il etre planaire sil possede un sous-graphe qui ne lest
pas ?
Reponse : Non : une fois dessine dans un plan, un graphe planaire a forcement tous ses
sous-graphes qui le sont aussi.
318
3 Exemples
E XEMPLE 7 (Kn ). On rappelle que lon note Kn tout graphe non oriente dordre n,
tel que toute paire de sommets est reliee par une unique arete. Alors K3 est planaire,
et K5 ne lest pas :
Reponse : Oui.
n(n 1)
Reponse : .
2
319
4 Problemes de denombrement
4.1 Cartes, regions
D EFINITION 10 (C ARTE , R EGIONS ). Une carte est une representation particuliere dun
graphe planaire. On dit quune carte est connexe si son graphe lest. Une carte divise
le plan en plusieurs regions.
E XEMPLE 9. Par exemple, la carte ci-dessous, avec six sommets et neuf aretes, divise
le plan en cinq regions (A, B, C, D, E).
On remarque que quatre regions sont limitees alors que la cinquieme (E), exterieure
au diagramme, ne lest pas.
D EFINITION 11 (D EGR E D UNE R EGION ). Le degre dune region r, note d(r), est la
longueur du cycle ou de la chane fermee qui limite r.
E XEMPLE 10. Dans le graphe ci-dessus, d(A)=4, d(B)=3, d(C)=3, d(D)=5, d(E)=3.
R EMARQUE 6. On remarque que toute arete limite deux regions, ou est contenue dans
une region et est alors comptee deux fois dans la chane fermee. Nous avons donc...
320
P ROPRI ET E II (L EMME DES R EGIONS ) : La somme des degres des regions dune
carte connexe est egale a deux fois le nombre daretes.
Exercice 9. Utilisez ce resultat pour prouver que K3,3 nest pas planaire.
321
5.2 Theoreme de Kuratowski
La reponse au probleme de caracterisation des graphes planaires est...
Exercice 11. En admettant, comme nous y invite le resultat precedent, que K5 nest
pas planaire, determiner les valeurs de n pour lesquelles Kn est planaire.
2
William Rowan Hamilton, mathematicien et physicien irlandais (1805-1865). Inventeur des quater-
nions.
322
2 Definition
D EFINITION 13 (C IRCUIT HAMILTONIEN ). Cest un circuit qui passe par tous les
sommets du graphe, une et une seule fois.
R EMARQUE 8. Dans le cas des graphes orientes (voir plus loin), on parle de graphe
hamiltonien sil est possible de trouver un cycle passant une et une seule fois par tous
les sommets.
3 Resultat
Contrairement aux graphes euleriens, il nexiste pas de caracterisation simple des
graphes hamiltoniens ou semi-hamiltoniens. On peut cependant enoncer quelques pro-
prietes et conditions suffisantes :
Exercice 12. Cherchez les raisons (elementaires) justifiant les trois points precedents.
323
P REUVE 4 :
En effet, un tel graphe verifie les conditions du theoreme precedent. Si x et y ne
sont pas adjacents, on a bien :
Fin du Chapitre
324
Chapitre 24
Arbres et arborescence
I. Presentation generale
1 Definitions
D EFINITION 2 (F OR ET ). Un graphe sans cycles mais non connexe est appele une
foret.
325
2 Caracterisation des arbres
P ROPRI ET E II : Tout arbre fini avec au moins deux sommets comporte au moins
deux feuilles.
4 Exercices
Indication : Recurrence.
326
Exercice 2. Combien darbres differents existe-t-il avec 3, 4, 5 sommets ?
Exercice 4. Soit un graphe G. Supposons quil y ait deux chanes elementaires dis-
tinctes P1 et P2 dun sommet s a un autre sommet s de G. G est-il un arbre ? Justifier
par une preuve.
2 Codage
2.1 La methode
Soit larbre T = (V, E) et supposons V = 1, 2, ..., n. Lalgorithme ci-dessous four-
nira le code de T , cest-a-dire une suite S de n 2 termes employant (eventuellement
plusieurs fois) des nombres choisis parmi {1, ..., n}.
327
P ROPRI ET E III (PAS G EN ERAL DE L ALGORITHME DE CODAGE ) : Initialement
la suite S est vide. Ce pas general est a repeter tant quil reste plus de deux
sommets dans larbre courant T :
identifier la feuille v de larbre courant ayant le numero minimum ;
ajouter a la suite S le seul sommet s adjacent a v dans larbre T courant ;
enlever de larbre T courant la feuille v et larete incidente a v.
1:4
2 : 10
3 : 6, 8
4 : 1, 5, 7, 8
5 : 4, 10
6:3
7:4
8 : 3, 4
9 : 10
10 : 2, 5, 9
Etape 1 :
2 : 10
3 : 6, 8
328
4 : 5, 7, 8
5 : 4, 10
6:3
7:4
8 : 3, 4
9 : 10
10 : 2, 5, 9
S={4}
Etape 2 :
3 : 6, 8
4 : 5, 7, 8
5 : 4, 10
6:3
7:4
8 : 3, 4
9 : 10
10 : 5, 9
S={4,10}
Etape 3 :
3:8
4 : 5, 7, 8
5 : 4, 10
7:4
8 : 3, 4
9 : 10
10 : 5, 9
329
S={4,10,3}
Etape 4 :
4 : 5, 7, 8
5 : 4, 10
7:4
8:4
9 : 10
10 : 5, 9
S = {4,10,3,8}
Etape 5 :
4 : 5, 8
5 : 4, 10
8:4
9 : 10
10 : 5, 9
S = {4,10,3,8,4}
Etape 6 :
4:5
330
5 : 4, 10
9 : 10
10 : 5, 9
S = {4,10,3,8,4,4}
Etape 7 :
5 : 10
9 : 10
10 : 5, 9
S = {4,10,3,8,4,4,5}
Etape 8 :
9 : 10
10 : 9
S = {4,10,3,8,4,4,5,10}
3 Decodage
3.1 La methode
Donnee : suite S de n 2 nombres, chacun provenant de {1, ..., n}.
Posons I = {1, ..., n}.
Pas general de lalgorithme de decodage : a repeter tant quil reste des elements dans
S et plus de deux elements dans I :
identifier le plus petit element i de I napparaissant pas dans la suite S ;
331
relier par une arete de T le sommet i avec le sommet s correspondant au
premier element de la suite S ;
enlever i de I et s de S.
Finalisation : Les deux elements qui restent dans I a la fin de lalgorithme constituent
les extremites de la derniere arete a ajouter a T.
I={1,2,3,4,5,6,7,8,9,10}
S={4,10,3,8,4,4,5,10}
Etape 1 :
1:4
4:1
I={2,3,4,5,6,7,8,9,10}
S={10,3,8,4,4,5,10}
Etape 2 :
1:4
332
2 : 10
4:1
10 : 2
I={3,4,5,6,7,8,9,10}
S={3,8,4,4,5,10}
Etape 3 :
1:4
2 : 10
3:6
4:1
6:3
10 : 2
I={3,4,5,7,8,9,10}
S={8,4,4,5,10}
Etape 4 :
1:4
2 : 10
3 : 6, 8
4:1
6:3
8:3
10 : 2
I={4,5,7,8,9,10}
S={4,4,5,10}
333
Etape 5 :
1:4
2 : 10
3 : 6, 8
4 : 1, 7
6:3
7:4
8:3
10 : 2
I={4,5,8,9,10}
S={4,5,10}
Etape 6 :
1:4
2 : 10
3 : 6, 8
4 : 1, 7, 8
6:3
7:4
8 : 3, 4
10 : 2
I={4,5,9,10}
S={5,10}
334
Etape 7 :
1:4
2 : 10
3 : 6, 8
4 : 1, 5, 7, 8
5:4
6:3
7:4
8 : 3, 4
10 : 2
I={5,9,10}
S={10}
Etape 8 :
1:4
2 : 10
3 : 6, 8
4 : 1, 5, 7, 8
5 : 4, 10
6:3
7:4
8 : 3, 4
10 : 2, 5
I={9,10}
S={}
335
Etape 9 :
1:4
2 : 10
3 : 6, 8
4 : 1, 5, 7, 8
5 : 4, 10
6:3
7:4
8 : 3, 4
9 : 10
10 : 2, 5, 9
I={}
S={}
4 Theoreme de Cayley
P REUVE 5 :
La preuve est immediate en utilisant le codage de Prufer.
En effet, on verifie aisement que les deux algorithmes constituent les deux sens
dune bijection entre les arbres sur n sommets numerotes et les mots de n2 lettres
sur lalphabet a n lettres.
Ce constat permet de conclure la preuve du theoreme de Cayley. En effet, il
existe nn2 mots de longueur n 2 sur lalphabet a n lettres, donc darbres sur n
sommets numerotes.
5 Exercices
336
Exercice 5. Decrivez larbre ci-dessous a laide du codage de Prufer.
337
1.1 Exercices
338
Resultat : Arbre ou foret maximale A = (V, F ) de poids minimum.
Algorithme : Trier et renumeroter les aretes de G dans lordre croissant de leur
poids : c(e1 ) < c(e2 ) < ... < c(em ).
1. Poser F := , k := 0
2. Tant que k < m et |F | < n 1 faire
Debut
si ek+1 ne forme pas de cycle avec F alors F := F {ek+1}
k := k + 1
Fin
Trouver une maniere de relier ces six villes, en minimisant le cout total de construc-
tion.
Exercice 10. Trouvez un arbre maximal de poids minimum du graphe ci-dessous (les
chiffres en bleu representent le poids des aretes) :
339
IV. Arborescence
1 Definitions et exemples
1.1 Definition dune arborescence
1.2 Exemple
340
D EFINITION 6 (H AUTEUR D UNE ARBORESCENCE ). On dira que la hauteur de lar-
borescence est le rang maximum
2 Arborescences ordonnees
2.1 Definition
R EMARQUE 2. On peut systematiquement etiqueter les sommets dun tel arbre comme
suit :
on attribue 0 a la racine r,
puis 1, 2, 3, ... aux sommets qui sont adjacents a r.
Les etiquettes suivantes sont constituees de letiquette du sommet pere, suivie
dun chiffre obtenu comme precedemment.
Ainsi, les sommets fils attaches au sommet 2 seront numerotes 2.1, 2.2, 2.3,...
D EFINITION 8. Cet ordre (0, 1, 1.1, 1.2, 2, 2.1, 3, 3.1, 3.1.1, 3.1.2, 3.2, 3.3) est ap-
pele ordre lexicographique, puisquil est semblable au classement des mots dans un
dictionnaire.
341
R EMARQUE 3. Il est identique a lordre obtenu en parcourant de haut en bas la branche
la plus a gauche de larbre, puis la branche immediatement a droite, et ainsi de suite
jusqua la branche la plus a droite.
On observe que les variables de lexpression (a, b, c, dete) sont les feuilles et que
les operations sont les autres sommets.
R EMARQUE 5. Larbre doit etre ordonne car a b et b a conduisent au meme arbre,
mais pas au meme arbre ordonne.
342
E XEMPLE 9. Lexpression (a b)/((c d) + e) devient ainsi / ab + cde.
2.3 Exercices
3 Codage de Huffman
3.1 Presentation
Le codage de Huffman est une methode de compression statistique de donnees qui
permet de reduire la longueur du codage dun alphabet.
Le code de Huffman (1952) est un code de longueur variable optimal, cest-a-
dire tel que la longueur moyenne dun texte code soit minimale. On observe ainsi des
reductions de taille de lordre de 20 a 90%.
3.2 Principe
Le principe de lalgorithme de Huffman consiste a recoder les octets rencontres
dans un ensemble de donnees source avec des valeurs de longueur binaire variable.
Lunite de traitement est ramenee au bit.
Huffman propose de recoder les donnees qui ont une occurrence tres faible sur une
longueur binaire superieure a la moyenne, et recoder les donnees tres frequentes sur
une longueur binaire tres courte.
343
Ainsi, pour les donnees rares, nous perdons quelques bits regagnes pour les donnees
repetitives.
E XEMPLE 10. Dans un fichier ASCII le w apparaissant 10 fois aura un code tres
long : 0101000001000. Ici la perte est de 40 bits (10 x 4 bits), car sans compression, il
serait code sur 8 bits au lieu de 12.
Par contre, le caractere le plus frequent comme le e avec 200 apparitions sera
code par 1. Le gain sera de 1400 bits (7 x 200 bits). On comprend linteret dune telle
methode.
E XEMPLE 11. Si un caractere est represente par la combinaison binaire 100 alors la
combinaison 10001 ne peut etre le code daucune autre information.
Dans ce cas, lalgorithme de decodage interpreterait les 5 bits comme une succes-
sion du caractere code 100 puis du caractere code 01
3.4 Methode
Lalgorithme opere sur une foret. Une foret est ici un ensemble darbres etiquetes
complets : tout noeud interne (cest-a-dire qui nest pas une feuille) a deux fils non-
vides.
La foret initiale est formee dun arbre a un noeud pour chaque lettre du langage-
source, dont letiquette est la probabilite de cette lettre.
La foret finale est formee dun unique arbre, qui est larbre de decodage du code.
Lalgorithme est de type glouton : il choisit a chaque etape les deux arbres detiquettes
minimales, soit x et y, et les remplace par larbre forme de x et y et ayant comme
etiquette la somme de letiquette de x et de letiquette de y.
344
Voici les differentes etapes de la construction dun code de Huffman pour lalpha-
bet source A, B, C, D, E, F, avec les probabilites P(A)=0.10, P(B)=0.10, P(C)=0.25,
P(D)=0.15, P(E)=0.35 et P(F)=0.05.
345
346
Le code dune lettre est alors determine en suivant le chemin depuis la racine de
larbre jusqua la feuille associee a cette lettre en concatenant successivement un 0 ou
un 1 selon que la branche suivie est a gauche ou a droite.
E XEMPLE 12. Ainsi, sur la figure ci-contre, A=0111, B=010, C=10, D=00, E=11 et
F=0110.
E XEMPLE 13. Par exemple le mot FADE serait code 011001110011. Pour decoder,
on lit simplement la chane de bits de gauche a droite. Le seul decoupage possible,
grace a la propriete du prefixe, est 0110-0111-00-11.
3.5 Conclusion
Ce principe de compression est aussi utilise dans le codage dimage TIFF (Tagged
Image Format File) specifie par Microsoft Corporation et Aldus Corporation.
Par ailleurs, le codage dimage est fait en retranscrivant exactement le contenu dun
ecran (image), en utilisant les methodes traditionnelles de compression.
R EMARQUE 8. Il existe des methodes qui ne conservent pas exactement le contenu
dune image (methodes non conservatives) mais dont la representation visuelle reste
correcte. Entre autres, il y a la methode JPEG (Join Photographic Experts Group) qui
utilise la compression de type Huffman pour coder les informations dune image.
Malgre son anciennete, cette methode est toujours remise au gout du jour, et offre
des performances appreciables. En effet, beaucoup de recherches en algorithmique ont
permis dameliorer les fonctionnalites de la methode Huffman de base, par exemple
les arbres binaires, les arbres equilibres, etc.
3.6 Exercices
347
Exercice 14. Utilisez le tableau ci-dessous pour determiner le codage de Huffman de
la langue francaise.
Frequences dapparition des lettres en francais
2 Idee de lalgorithme
Soit s un sommet origine.
1. Parcourir tous les arcs du graphe accessibles depuis s.
2. Calculer la distance entre s et tous les sommets accessibles (cette distance cor-
respond au plus petit nombre daretes).
3. Construction dune arborescence en largeur, de racine s, qui contient tous les
sommets accessibles dans le graphe.
Fin du Chapitre
348
Chapitre 25
Problemes de coloration
2 La coloration
R EMARQUE 1. Une coloration avec k couleurs est donc une partition de lensemble
des sommets en k stables.
349
E XEMPLE 1. Sur le graphe ci-dessous, on a eu besoin de trois couleurs pour colorer
les sommets de sorte que deux sommets adjacents ont des couleurs differentes. On a
donc trois stables : {1, 2}, {3, 5} et {4}. On ne peut pas utiliser moins de couleurs, a
cause des cliques 1-4-5 et 1-3-4.
R EMARQUE 2. Remarquons enfin que le sommet 2 aurait pu aussi etre vert. La colo-
ration minimale nest donc pas forcement unique.
P REUVE 6 :
Soit un graphe et r le degre maximum de ses sommets. Donnons-nous une palette
de (r + 1) couleurs. Pour chaque sommet du graphe on peut tenir le raisonnement
suivant :
ce sommet est adjacent a r sommets au plus,
le nombre de couleurs deja utilisees pour colorer ces sommets est donc
inferieur ou egal a r.
Il reste donc au moins une couleur non utilisee dans la palette, avec laquelle nous
pouvons colorer notre sommet.
350
P ROPRI ET E II : g(G) 6 n + 1 a(G)
P REUVE 7 :
Considerons S un stable de V de cardinal a(G) : une coloration possible des som-
mets consiste a colorer les sommets de S dune meme couleur et les n a(G)
autres sommets de couleurs toutes differentes.
On en deduit que g(G) 6 1 + (n a(G)).
3.2 Minoration
On a dautres resultats, concernant la minoration...
P ROPRI ET E III : Le nombre chromatique dun graphe est superieur ou egal a celui
de chacun de ses sous-graphes.
P REUVE 8 :
Ce resultat decoule de la definition meme du nombre chromatique.
P REUVE 9 :
Puisque, par definition, dans une clique dordre m, tous les sommets sont adjacents
entre eux, il faudra m couleurs. Donc, forcement, le nombre chromatique du graphe
sera superieur ou egal a lordre de sa plus grande clique.
351
4 Algorithme de coloration de Welsh et Powell
Cet algorithme couramment utilise permet dobtenir une assez bonne coloration
dun graphe, cest-a-dire une coloration nutilisant pas un trop grand nombre de cou-
leurs. Cependant il nassure pas que le nombre de couleurs utilise soit minimum (et
donc egal au nombre chromatique du graphe).
Etape 1 Classer les sommets du graphe dans lordre decroissant de leur degre, et
attribuer a chacun des sommets son numero dordre dans la liste obtenue.
Etape 2 En parcourant la liste dans lordre, attribuer une couleur non encore utilisee
au premier sommet non encore colore, et attribuer cette meme couleur a chaque
sommet non encore colore et non adjacent a un sommet de cette couleur.
Etape 3 Sil reste des sommets non colores dans le graphe, revenir a letape 2. Sinon,
la coloration est terminee.
5 Exercices
Exercice 1. Tout graphe contenant un triangle (K3 ) ne peut pas etre colore en moins
de trois couleurs.
1. Construire un graphe sans K3 qui necessite egalement trois couleurs.
2. Comment, a partir du graphe precedent, construire un graphe sans K4 necessitant
4 couleurs ?
3. Un graphe sans K5 necessitant 5 couleurs ?
352
Exercice 3. Sept eleves, designes par A, B, C, D, E, F et G, se sont rendus a la
bibliotheque aujourdhui. Le tableau suivant precise ((qui a rencontre qui)) (la bi-
bliotheque etant petite, deux eleves presents au meme moment se rencontrent necessairement...).
leleve A B C D E F G
a rencontre D,E D,E,F,G E,G A,B,E A,B,C,D,F,G B,E,G B,C,E,F
De combien de places assises doit disposer la bibliotheque pour que chacun ait pu
travailler correctement au cours de cette journee ?
A B C D E F G H
A
B
C
D
E
F
G
H
Exercice 5. Un lycee doit organiser les horaires des examens. On suppose quil y a 7
epreuves a planifier, correspondant aux cours numerotes de 1 a 7 et que les paires de
cours suivantes ont des etudiants communs : 1 et 2, 1 et 3, 1 et 4, 1 et 7, 2 et 3, 2 et 4,
2 et 5, 2 et 7, 3 et 4, 3 et 6, 3 et 7, 4 et 5, 4 et 6, 5 et 6, 5 et 7 et enfin 6 et 7. Comment
organiser ces epreuves de facon quaucun etudiant nait a passer deux epreuves en
meme temps et cela sur une duree miminale ?
353
Exercice 6. Sept agences de voyage romaines proposent des visites de monuments et
lieux touristiques : le Colisee, le Forum romain, le musee du Vatican et les thermes
de Caracalas. Un meme lieu ne peut etre visite par plusieurs groupes de compagnies
differentes le meme jour. La premiere Compagnie fait visiter uniquement le Colisee ; la
seconde le Colisee et le musee du Vatican ; la troisieme les thermes de Caracalas ; la
quatrieme le musee du Vatican et les thermes de Caracalas ; la cinquieme le Colisee et
le Forum romain ; la sixieme le Forum romain et les thermes de Caracalas ; la septieme
le musee du Vatican et le forum romain. Ces agences peuvent-elles organiser les visites
sur les trois premiers jours de la semaine ?
354
2 Formulation en theorie des graphes
Ce probleme a une formulation dans le langage des graphes : y a-t-il toujours, dans
un graphe planaire, une application de lensemble S des sommets vers un ensemble
de cardinal 4, telle que deux sommets (( adjacents )) admettent toujours des images
distinctes ?
P ROPRI ET E V (T H EOR EME DES QUATRE COULEURS ) : On peut colorer les som-
mets dun graphe planaire (sans boucles) en utilisant au plus quatre couleurs de
telle sorte que toutes les aretes aient des extremites de couleurs differentes.
Cette conjecture a ete formulee pour la premiere fois par lEcossais Francis Guthrie
en 1852. Il etait alors question de coloration de carte de geographie (voir exercice ci-
dessous).
La preuve de ce theoreme narriva quen... 1976, grace a Kenneth Appel et Wolf-
gang Haken. La demonstration fit grand bruit car cest le premier theoreme de lhistoire
des mathematiques qui a necessite lusage systematique de lordinateur.
355
La communaute mathematique se divisa alors en deux camps : ceux pour qui le
theoreme des quatre couleurs etait definitivement demontre, et ceux pour qui tout res-
tait a faire.
3 Exercice
Exercice 9. Prenez une feuille de papier. Tracez une droite quelconque qui traverse
la feuille de part en part. Recommencez loperation n fois. Demontrez que la carte
ainsi obtenue peut etre coloree en deux couleurs.
356
2 Lien avec la coloration des sommets
2.1 Presentation
Pour colorer les aretes dun graphe, on peut se ramener au probleme de la colora-
tion des sommets. Il suffit pour cela de travailler non pas sur le graphe lui-meme, mais
sur le graphe adjoint, note G, et que lon definit ainsi :
a chaque arete de G = (V, E) correspond un sommet de G = (E, F)
deux sommets de G sont relies par une arete si les deux aretes correspondantes
de G sont adjacentes.
On peut ensuite appliquer par exemple lalgorithme de Welsh et Powell sur le
graphe G pour colorer ses sommets. Une fois cela fait, on colorera les aretes de G
de la meme couleur que les sommets correspondants de G.
357
4. Coloration des aretes de G
3 Exercice
Exercice 10. Dans un tournoi dechecs, chaque engage doit rencontrer tous les autres.
Chaque partie dure une heure.
Determiner la duree minimum du tournoi dans le cas ou le nombre dengages est
3, 4, 5 ou 6.
Fin du Chapitre
358
Chapitre 26
Graphes orientes
I. Definitions
1 Digraphe (graphe oriente), sommet, arc
En donnant un sens aux aretes dun graphe, on obtient un digraphe, ou graphe
oriente.
R EMARQUE 1. De langlais directed graph.
359
Exercice 1. Construire un graphe oriente dont les sommets sont les entiers compris
entre 1 et 12 et dont les arcs representent la relation (( etre diviseur de )).
Exercice 2. Quel est le nombre maximal daretes dans un graphe oriente dordre n
qui ne possede pas daretes paralleles ?
2 Exemples
1. le graphe dune relation binaire peut etre assimile a un graphe oriente,
2. les graphes orientes peuvent etre representes graphiquement, ce qui fournit toutes
sortes dexemples :
360
D EFINITION 3 (D EGR E INT ERIEUR ). Le degre interieur du sommet v est le nombre
darcs ayant v comme extremite finale.
P ROPRI ET E I : On a :
d(v) = d+ (v) + d (v)
.
Exercice 3. Soit G un graphe oriente quelconque. Demontrez que la somme des degres
entrants de tous les sommets est egal a la somme de tous les degres sortants.
Reponse : Chaque arete compte une fois dans la somme des degres entrants et une fois
dans la somme des degres sortants...
361
4 Chemins et circuits
4.1 Chemin
E XEMPLE 2. Sur le digraphe ci-dessous, on peut voir par exemple le chemin (v3 , e3 , v4 , e4 , v5 ).
4.2 Distance
362
4.3 Circuit
5 Circuits euleriens
Exercice 7. Les graphes ci-dessous sont-il fortement connexes ? Si non, donnez leurs
composantes fortement connexes.
363
1.2 Composantes connexes
2 Exercices
Exercice 8. On souhaite prelever 4 litres de liquide dans un tonneau. Pour cela, nous
avons a notre disposition deux recipients (non gradues !), lun de 5 litres, lautre de 3
litres.
Comment doit-on proceder ?
Exercice 10. Proposez un algorithme qui determine si un graphe est fortement connexe
ou non.
Exercice 11. Les graphes ci-dessous sont-il fortement connexes ? Si non, donnez leurs
composantes fortement connexes.
364
III. Matrice et listes dadjacences
1 Matrice dincidence
D EFINITION 10. On suppose a nouveau que les aretes et les sommets du graphe
oriente considere ont ete numerotees, et on appelle alors matrice dincidence J de ce
graphe la matrice dont lelement (s, ) vaut :
2 si s est une extremite de , quand est une boucle,
1 si s est une extremite de , quand nest pas une boucle,
0 sinon.
1.1 Remarques
1. se donner un graphe oriente est equivalent a se donner les deux matrices J + et
J .
2. on peut relier d+ (s) (resp. d (s)) au nombre de 1 apparaissant dans J + (resp.
J ).
1.2 Resultats
P ROPRI ET E III : Soient (s1 , . . . , sn ) les sommets dun graphe oriente. Alors
d+ (s1 ) 1 d (s1 ) 1
.. + .. .
.. .
1. = J . et = J ..
.
+
d (sn ) 1 d (sn ) 1
365
d+ (s1 ) 0
2. J + J t =
..
.
0 d+ (sn )
d (s1 ) 0
3. J J +t =
..
.
0 d (sn )
2 Matrice dadjacences
2.1 Definition
2.2 Exemple
Voici la matrice dadjacences du digraphe G :
0 1 0 1 0 1
0 0 0 1 1 0
0 0 0 1 0 0
M =
0 0 0 0 1 0
0 0 0 0 0 0
0 1 0 0 0 0
366
R EMARQUE 5. Se donner un graphe oriente revient a se donner sa matrice dadja-
cence.
2.3 Proprietes
367
Exercice 13. On pose
0 1 0 1
1 0 1 0
A=
0
1 0 1
1 0 1 0
1. Dessinez le graphe oriente ayant A pour matrice dadjacence.
2. Determinez ses matrices dincidences.
3. Verifiez, sur cet exemple, les formules precedentes.
J = J+ + J
368
4 Listes dadjacence
On peut encore representer un digraphe a laide de listes dadjacences : en donnant
pour chacun de ses sommets la liste des sommets quon peut atteindre directement en
suivant un arc (dans le sens de la fleche).
1 : 2, 4, 6
2 : 4, 5
3 : 4
4 : 5
5 : -
6 : 2
P ROPRI ET E IX: Soient (s1 , . . . , sn ) les sommets dun graphe oriente. Alors
d+ (s1 ) 1 d (s1 ) 1
.. .. .
.. t .
= A . et = A ..
.
d+ (sn ) 1 d (sn ) 1
Exercice 15. Decrivez le digraphe G de lexercice precedent par des listes dadja-
cences.
369
IV. Digraphes sans circuits
1 Theoreme
P REUVE 10 :
Si G comporte un circuit C, il nest pas possible de trouver de tels nombres r(i)
car, autrement, considerant r(j) = max{r(i)|i C} et larc (j, k) C on aurait
r(j) 6 r(k) en contradiction avec la definition de r().
Reciproquement, si G na pas de circuits, il existe au moins un sommet
sans predecesseurs dans G (sans cela, en remontant successivement dun som-
met a un predecesseur, on finirait par fermer un circuit). Ainsi, on peut attribuer
sequentiellement des valeurs r() aux sommets du graphe a laide de lalgorithme
qui suit, ce qui conclura la demonstration.
3 Exercice
Exercice 16. Attribuez un rang aux sommets du digraphe ci-dessous en utilisant lal-
gorithme de calcul du rang :
370
Fin du Chapitre
371
Chapitre 27
Problemes de chemin
I. Algorithme de Dijkstra
1 Presentation
Edgser Wybe Dijkstra (1930-2002) a propose en 1959 un algorithme qui permet de
calculer le plus court chemin entre un sommet particulier et tous les autres.
Le resultat est une arborescence.
2 Lalgorithme
1. Numerotons les sommets du graphe G = (V, E) de 1 a n.
2. Supposons que lon sinteresse aux chemins partant du sommet 1.
3. On construit un vecteur l = (l(1); l(2); ...; l(n)) ayant n composantes tel que
l(j) soit egal a la longueur du plus court chemin allant de 1 au sommet j.
On initialise ce vecteur a c1,j , cest-a-dire a la premiere ligne de la matrice des
couts du graphe, definie comme indique ci-dessous :
0 si i = j
+ si i 6= j et (i, j)
/E
(i, j) si i 6= j et (i, j) E
ou (i, j) est le poids (la longueur) de larc (i, j). Les ci,j doivent etre strictement
positifs.
4. On construit un autre vecteur p pour memoriser le chemin pour aller du sommet
1 au sommet voulu.
La valeur p(i) donne le sommet qui precede i dans le chemin.
5. On considere ensuite deux ensembles de sommets, S initialise a {1} et T initia-
lise a {2, 3, ..., n}.
372
A chaque pas de lalgorithme, on ajoute a S un sommet jusqua ce que S = V
de telle sorte que le vecteur l donne a chaque etape le cout minimal des chemins
de 1 aux sommets de S.
4 Exemple
Initialisations S = {1} ;
T = {2, 3, 4, 5} ;
l = (0, 15, , , 4) ;
p = (NIL, 1, NIL, NIL, 1).
Premiere iteration i = 5 car l(5) = min(15, , , 4) = 4 ;
S = {1, 5} ; T = {2, 3, 4} ;
les successeurs de 5 dans T sont 3 et 4 ;
l(3) prend la nouvelle valeur min(; l(5) + d(5; 3)) = min(; 4 + 7) = 11 ;
p(3) = 5 ;
l(4) prend la nouvelle valeur min(; l(5) + d(5; 4)) = 9 ; p(4) = 5 ;
dou les nouveaux vecteurs l = (0, 15, 11, 9, 4) et p = (NIL, 1, 5, 5, 1)
373
Deuxieme iteration i = 4 ; l(4) = 9 ;
S = {1, 5, 4} ; T = {2, 3} ;
le seul successeur de 4 dans T est 2 ;
l(2) prend la nouvelle valeur min(; l(4) + d(4; 2)) = min(15; 9 + 3) = 12 ;
p(2) = 4 ;
dou les nouveaux vecteurs l = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)
Troisieme iteration i = 3 ; l(3) = 11 ;
S = {1, 5, 4, 3} ; T = {2} ;
le seul successeur de 3 dans T est 2 ;
l(2) garde sa valeur car min(12; l(3) + d(3; 2)) = min(12; 11 + 3) = 12 ;
dou les vecteurs inchanges l = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)
Quatrieme iteration i = 2 ; l(2) = 12 ;
S = {1, 5, 4, 3, 2} ; T = {} ; FIN.
l = (0, 12, 11, 9, 4) ;
p = (NIL, 4, 5, 5, 1).
Le chemin minimal de 1 a 4 par exemple est de cout 9. Cest le chemin 1-5-4, car
p(4) = 5 et p(5) = 1.
5 Exercices
Exercice 2. Expliquez pourquoi des arcs avec des poids negatifs pourraient poser
probleme dans la recherche dun plus court chemin dans un graphe.
374
II. Methode PERT
1 Presentation de la methode
Le probleme du plus long chemin dans les digraphes sans circuits trouve une ap-
plication dans lordonnancement et la planification des taches composant un projet
complexe, par exemple la construction dune maison.
On fait correspondre a chaque tache un arc dun digraphe, sa duree dexecution
etant egale au poids de cet arc.
Le digraphe reflete les precedences requises dans lexecution du projet. Ainsi, la
tache correspondant a larc (i, j) ne peut commencer que si toutes les taches correspon-
dant a des arcs (k, i) ont ete completees. Le digraphe peut contenir des taches fictives
de duree nulle afin de forcer certaines precedences.
Les sommets du digraphe representent des evenements, debut (fin) des activites
correspondant aux arcs dont ils sont lextremite initiale (finale). Le fait que le digraphe
est sans circuit est garant de la faisabilite du projet. En effet, lexistence dun circuit
impliquerait une contradiction dans les precedences : une tache devant en meme temps
preceder et succeder une autre !
On supposera dorenavant que les sommets ont deja ete numerotes de 1 a n de
maniere compatible avec leurs rangs, cest-a-dire que r(j) > r(i) implique j > i (voir
lalgorithme de calcul du rang).
En plus, si le digraphe possede plusieurs sommets sans predecesseurs, on sup-
posera avoir introduit un sommet 1 relie par un arc de duree nulle a chacun de ces
sommets. Ce sommet indique le debut du projet.
De meme, si le digraphe possede plusieurs sommets sans successeurs, ceux-ci se-
ront relies par un arc de duree nulle a un dernier sommet n (fin du projet).
Enfin, on supposera elimines les arcs paralleles par lintroduction de taches fictives.
375
Fin.
3 Definitions
D EFINITION 2 (A RC CRITIQUE ). Un arc (i, j) est critique si ses extremites sont des
sommets critiques et dij = dj di .
4 Exemple
Ci-dessous le graphe des precedences obtenu avec lalgorithme du chemin critique.
Les sommets et les arcs critiques sont en rouge.
376
Taches Precedences Duree [jours]
A - 3
B - 9
C - 5
D A 8
E B 4
F B 7
G B 20
H C, F 6
I D, E 5
5 Exercices
377
Taches Precedences Duree [jours]
A Enlevement des portes - 1/2
B Poncage et peinture des portes A 3
C Pose des portes B, J 1/2
D Arrachage des papiers peints - 1
E Tirage des fils electriques D 1
F Pose des prises E, H, I 1/2
G Ragreage des murs E, A 2
H Peinture du plafond G 2
I Pose des papiers peints G 3
J Peinture des cadres H, I 1
K Arrachage de la moquette H, I, J 1/2
L Poncage du parquet K 1
M Impregnation et sechage du parquet L, F 4
N Peinture du balcon - 2
O Changement des protections solaires N 1
Fin du Chapitre
378
Chapitre 28
Chanes de Markov
I. Generalites
1 Presentation
Generalement, un processus stochastique est une suite dexperiences dont le resultat
depend du hasard.
Ici, nous admettrons quen certains temps 0, 1, 2, ..., t, nous observons un systeme.
Celui-ci peut se trouver dans lun des etats dune collection finie detats possibles.
Lobservation du systeme est ainsi consideree comme une experience dont le resultat
(aleatoire) est letat dans lequel se trouve le systeme.
Nous supposons que nous connaissons pour chaque paire detats i et j, et pour
chaque instant t, la probabilite pij (t) que le processus soit dans letat j a linstant t + 1
etant donne quil se trouve dans letat i a linstant t. De plus, la probabilite pij (t) sera
supposee ne pas dependre de t.
2 Definitions
379
3 Exemple
Pour representer le passage dune molecule de phosphore dans un ecosysteme,
nous considererons quatre etats possibles :
1. la molecule est dans le sol,
2. la molecule est dans lherbe,
3. la molecule a ete absorbee par du betail,
4. la molecule est sortie de lecosysteme.
La matrice de transition est la suivante :
3 3 1
0
5 10 10
1 2 1
0
P = 10 5 2
3 1 1
0
4 5 20
0 0 0 1
Remarquez que la somme de chaque ligne vaut 1. Cette matrice correspond au
graphe ci-dessous :
4 Proprietes
P ROPRI ET E I : La probabilite pij (t) que le systeme soit dans letat j au temps t
sachant quil etait dans letat i au temps 0 est donne par (P t )i,j (le terme i, j de la
t-ieme puissance de P ).
380
P ROPRI ET E II : p(t) = p(0)P t
5 Exercice
Exercice 1. Un individu vit dans un milieu ou il est susceptible dattraper une maladie
par piqure dinsecte. Il peut etre dans lun des trois etats suivants : immunise (I),
malade (M), non malade et non immunise (S). Dun mois a lautre, son etat peut
changer selon les regles suivantes :
etant immunise, il peut le rester avec une probabilite 0,9 ou passer a letat S
avec une probabilie 0,1 ;
etant dans letat S, il peut le rester avec une probabilite 0,5 ou passer a letat
M avec une probabilite 0,5 ;
etant malade, il peut le rester avec une probabilite 0,2 ou passer a letat I avec
une probabilite 0,8.
Tracez un graphe probabiliste pour decrire cette situation et ecrivez la matrice de
transition. Calculez letat de probabilite de lindividu au bout de trois mois, de six
mois, dun an, de deux ans, pour chacune des situations suivantes :
au depart, il est immunise (I) ;
au depart, il est non malade et non immunise (S) ;
au depart, il est malade (M).
Pouvez-vous donner des elements sur la proportion dindividus malades dans la
population etudiee ?
D EFINITION 3. Si tel est le cas, on dit que cette derniere definit un regime permanent
du processus stochastique.
381
2 Existence dune distribution limite
3 Exercices
382
Exercice 4. Un service de meteo a constate apres de longues annees que le temps
quil fera demain depend essentiellement du temps quil faisait hier et du temps quil
fait aujourdhui. Les probabilites de transition ont ete etablies ainsi :
Exercice 5. Un ivrogne se deplace dans les quatre bistrots dun village, dune maniere
bien personnelle : en sortant dun bistrot, il lance une piece de monnaie pour savoir
dans lequel des deux autres bistrots les plus proches il entrera.
Ces quatre bistrots forment les sommets dun carre.
1. Modelisez ce processus a laide dune chane de Markov.
2. Montrez que cette chane de Markov na pas de distribution limite.
D EFINITION 4 ( E TAT ABSORBANT ). Un etat absorbant est un etat que lon ne quitte
plus lorsquon y penetre.
383
1. il y a au moins un etat absorbant
2. de tout etat non absorbant, on peut atteindre un etat absorbant.
...est un etat absorbant. Comme on peut atteindre cet etat depuis tous les autres, la
chane de Markov est absorbante.
1.2 Propriete
384
2.2 Forme canonique de P
Si une chane de Markov est absorbante, on placera au debut les etats absorbants ;
on aura alors une matrice de transition de la forme :
I O
R Q
1 0 0 0
1 3 3
0
10 5 10
P = 0 1 2 1
10 5 2
1 3 1
0
20 4 5
2.4 Resultats
385
P ROPRI ET E VI : Le nombre moyen detapes avant absorption sachant que lon
part de letat i (non absorbant) est la somme des termes de la i-eme ligne de N.
Dou le nombre moyen detapes avant absorption en partant de letat 1 : (320 + 160
+ 100) / 37 = 15.67
P ROPRI ET E VII : Dans une chane de Markov absorbante avec P mise sous forme
canonique, le terme bij de la matrice B = NR est la probabilite dabsorption par
letat absorbant j sachant que lon part de letat i.
La probabilite detre absorbe par lunique etat absorbant est 1 quel que soit letat ini-
tial !
386
3 Exercices
Exercice 8. Considerons une serie de jets dune piece de monnaie normale. On notera
P pour pile et F pour face.
1. Quelle est la probabilite dobtenir une sequence PFP avant une sequence PPP ?
2. Quel est le nombre de jets necessaires en moyenne pour realiser lune des deux
sequences PFP et PPP ?
387
Exercice 9 (La parade nuptiale des bourdons). Une seance daccouplement peut se
decomposer en 7 phases :
Depart (D) : mise en contact des bourdons male et des reines.
Approche (App) : un male se dirige vers la reine. Il sapproche a courte distance. Il
est le comportement le plus frequent et souvent suivi dune recidive.
Inspection de la femelle (IF) : le male suit la reine avec ses antennes tendues vers
elle. Il inspecte souvent la reine au niveau de la tete (region ou se trouvent
les glandes produisant les pheromones sexuelles), mais parfois au niveau de
labdomen.
Tentative daccouplement (T) : le male sapproche de la reine, il saccroche a elle.
Il frotte de ses pattes anterieures lextremite de labdomen de la femelle. Il sort
ses genitalias (appareil reproducteur) et tente de penetrer la reine.
Accouplement (Acc) : lors de laccouplement, le comportement du male se caracterise
par des mouvements de battements des pattes sur lextremite de labdomen de la
reine.
Sortie par abandon du male (SA) : lors de la sequence de 15 minutes, le bourdon
male peut adopter un comportement indifferent vis-a-vis de la reine ; il sort de
la parade nuptiale et ny revient jamais.
Sortie pour depassement du temps (ST) : lobservation est limitee a 15 minutes. Apres
cette duree, la probabilite daccouplement peut etre consideree comme presque
nulle.
Voici les statistiques obtenues pour 78 seances daccouplement en laboratoire :
par exemple App suivi de T = 202...
388
5. Cette chane de Markov est une chane absorbante. Quel est le nombre moyen
detapes avant absorption ? Trouvez le resultat theoriquement et par simulation.
Fin du Chapitre
389
Sixieme partie
Annexes
390
Chapitre 29
Annales
Q UESTION 1 : Soit A = {{a, b, }, {c}, {d, e, f }}. Dire si les affirmations suivantes
sont justes ou fausses.
1. a A
2. {c} A
3. {d, e, f } A
4. {{a, b}} A
5. A
6. A
391
Q UESTION 3 : Soit E un ensemble. On note P (E) lensemble de ses parties. Pour
tout A et B, parties de E, on definit un operateur par
(A, B) = (A B) (E \ (A B)).
C (E \ D) = C \ D
E = A B C {h, i}
392
3. (A, B) = (A, C) ssi B = C.
Q UESTION 7 : Soit t1 et t2 deux termes exprimes dans une algebre de Boole munie
des operateurs classiques +, ., et .
Si t1 .t2 = 0 alors...
1. t1 = 0 et t2 = 0.
2. t1 = 0 ou t2 = 0.
3. t1 = t2 .
4. Il existe un terme k tel que t1 = k.t2 .
Q UESTION 10 : On donne une expression E dans une algebre de Boole munie des
operateurs classiques +, ., et .
La version la plus simplifiee de E = a.b + a.c + b.c + c est
1. 1
2. a
3. 0
393
4. une autre expression
394
(n) (2)
Q UESTION 15 : Soit mi le ieme minterme a n variables. Lexpression m0 +
(2) (2) (2)
m1 + m2 + m3 est egale a
1. 0
2. 1
(2)
3. m6
(2)
4. m0
(7) (7)
Q UESTION 16 : Quel est lensemble des (i, j) tels que mi .mj 6= 0
1.
2. N N
3. {(i, i) | i N et i 6}
395
2. une somme de 4 mintermes
3. autre chose
396
Init
e0 a
b
e1 a b
b
e2 a
Q UESTION 25 : Soit lautomate donne a la figure 29.1. Quelle affirmation est fausse ?
1. Lautomate naccepte que les mots dont le nombre de b est un multiple de 3.
2. Le mot vide est reconnu par lautomate.
3. bbbaaa est reconnu par lautomate.
4. Lautomate naccepte que les mots dont la taille est un multiple de 3.
397
e0 0
Init1
Init1
10
e0 Init2 Init1
a, b e1
e0 a
a e1 b e0 a, b
b a 1 0
ba ba
e2 e1 b e2 1 e1 b
(a) (b) (c) (d)
Init1
e0 b
a
e1 a
a
b e2
b
e3
(e)
398
0 1 0 1
A B B {e0 , e1 } {e1 , e2 , e3 } {e1 , e2 , e3 }
B D C {e1 , e2 , e3 } {e2 , e3 } {e1 , e3 }
0 1
C F E {e1 , e3 } {e3 } {e1 }
e0 {e1 , e2 } {e2 , e3 }
D F G {e2 , e3 } {e3 } {e2 }
e1 {e3 } {e1 }
E F E {e1 } {e3 } {e1 }
e2 {e2 } {e3 }
(a) F H H {e3 } F F
G G F {e2 } {e2 } {e3 }
H H H F F F
(b) (c)
0 1
0 1
{e0 , e1 } {e1 , e2 , e3 } {e1 , e2 , e3 }
A B B
{e1 , e2 , e3 } {e2 , e3 } {e1 , e3 }
B C C
{e1 , e3 } {e1 , e3 } {e3 }
C D D
{e2 , e3 } {e3 } {e2 , e3 }
D D D
{e3 } {e3 } {e3 } (e)
(d)
399
3. (c) et (e) reconnaissent le meme langage.
4. (d) est un automate non deterministe.
5. (e) est un automate de Moore.
t a b
e0 e0 e4
e1 e1 e0
e2 e2 e4
e3 e5 e2
e4 e4 e3
e5 e3 e2
Q UESTION 31 : Lorsquun AFND A est defini par une relation de transition t non
deterministe, la methode du dual consiste, dans le pire des cas
1. en trois determinisations et deux inversions.
2. deux determinisations et deux inversions.
3. un nombre de quotients qui depend de R.
4. une determinisation et une inversion.
400
Init1
a
2 b
b
4
aa a
6 b
b b
3
b a
5 b
a
7 a
401
Init1
a
Init1
B
Init1 7 1
a b
8 2
e0 C E a a
9
3
a aa aa a b a
10 4
e1 e3 a a
a D F
11 5
b b 12
e2 G
6
Q UESTION 33 : Cette question est liee a la figure 29.5. Choisir la bonne reponse.
Lexpression reguliere ((aba) | (aa))
1. est reconnue par lautomate 29.5(a).
2. est reconnue par lautomate 29.5(b).
3. est reconnue par lautomate 29.5(c).
4. est reconnue par un autre automate
402
Init1
2 a
a 7
3 b
b 8
4 a
9
5
10
Q UESTION 35 : Cette question est aussi liee a lautomate donne a la figure 29.6.
Combien detats a la forme sans epsilon-transition qui correspond a cet automate.
1. 6.
2. 7.
3. 10.
4. 11.
403
Q UESTION 36 : Cette question est aussi liee a lautomate donne a la figure 29.6.
Combien detats dacceptation a la forme sans epsilon-transition qui correspond a
cet automate.
1. 1.
2. 3.
3. 4.
4. Un autre nombre.
1
0
e0 e1
0,1 0
1
e2 e3
1
0
E a b
A = {e0 , e2 } {e0 , e2 } {e4 }
B = {e1 , e3 , e5 } {e1 , e3 , e5 } {e0 , e2 }
C = {e4 } {e4 } {e1 , e3 , e5 }
404
0 0
1 1 O
0 1 5 2
1
0 1
1 1
3 4
0 0
405
Chapitre 30
Bibliographie
Outils mathematiques pour linformaticien, Michel Marchand [De Boeck ] : les themes
abordes sont proches de ce cours de mathematiques discretes (notre premiere
annee y est plus detaillee que la partie concernant automates, graphes et lan-
gages).
On y trouve des exercices, corriges, parfois repris dans ce support. Cependant, le
formalisme choisi seloigne par moment de celui adopte dans notre document,
ce qui pourrait en destabiliser certains.
Methodes mathematiques pour linformatique, Jacques Velu [Dunod ] : Reprend
une grande partie du cours de mathematiques discretes, et y ajoute un peu de pro-
babilites et dalgebres lineaires. Contient des exercices corriges. Un peu dense
par moment, mais une bonne reference quand meme.
Le magazine Tangente : que lon trouve chaque mois chez les bons marchants de
journaux. Niveau lycee et plus. On y trouve frequemment des articles sur les
graphes, la logique, le cryptage, etc. Ludique et plaisant, pour ceux qui aiment
les mathematiques, veulent les decouvrir. Les hors-series sur la logique, sur les
codes secrets, etc. me servent a trouver des idees de TP, ou a enrichir le cours.
Introduction a la logique, Francois Rivenc [Petite Bibliotheque Payot ] : Pour un
public avertis, souhaitant etudier plus systematiquement la logique, sous ses as-
pects mathematiques et philosophiques.
http ://www.apprendre-en-ligne.net/ Site de Didier Muller, sur lequel jai repris la
partie graphes. A noter une autre partie (tres riche, bien fournie) consacree a la
cryptographie, et un blog tres interessant sur les mathematiques.
406
Chapitre 31
407
Cryptographie (RSA, methode du (( sac a dos )), etc.).
Codes correcteurs et codes detecteurs derreurs.
408
Index
409
codage de Huffman, 343 feuilles, 325
coloration fonction
des sommets, 349 booleenne, 111
complementation, 20 nulle, 111
composant de substitution, 221 de succession, 58
composante fortement connexe, 364 referentiel, 111
composantes connexes fonctions booleennes elementaires, 111
dun graphe, 304 foret, 325
congru, 67 forme canonique
congruence dautomates, 264 conjonctive, 117
consequence logique, 151 disjonctive, 116
consensus, 121 formes equivalentes, 153
contraposee, 170 formes propositionnelles, 143
Corollaire de Dirac, 323 formule, 194
courbe elliptique, 103
critere grammaire, 234
de Pocklington, 97 algebrique, 293
cycle, 248, 301 axiome, 236, 292
contextuelle, 292
decomposition en facteurs premiers, 61 de Chomsky, 292
demonstration, 163 de type 0, 292
degre de type 1, 292
dune region, 320 de type 2, 293
exterieur, 360 de type 3, 293
interieur, 361 non restreinte, 292
digraphe, 359 reguliere, 293
fortement connexe, 363 graphe, 23
distance, 362 biparti, 305
diviseur, 60 complet, 304
division euclidienne, 64 connexe, 304
eulerien, 313
ensemble, 14 hamiltonien, 323
cardinal, 31 non oriente, 298
complementaire, 20 ordre, 298
des parties, 16 oriente, 359
fini, 31 partiel, 315
ordonne, 35 planaire, 303, 318
puissance, 31 regulier, 300
sous-, 16 simple, 301
totalement ordonne, 35 sous-, 316
vide, 15 graphes
entiers naturels, 58 homeomorphes, 321
extremites, 298 groupe operatoire, 188
410
groupe relationnel, 189 maximum, 37
maxterme, 111
image, 25 minimum, 38
inclusion, 16 minorant, 37
indice minterme, 111
dun minterme, 113 modulo, 67
injection, 27 monome, 115
intersection, 18 monomes principaux, 123
involution, 20 monode libre, 291
langage, 291 mot reconnu
alphabet, 292 par etat dacceptation, 285
langages par pile vide, 285
algebrique, 293 par symbole de sommet de pile, 285
contextuels, 292 multigraphe, 303
recursivement enumerables, 292 multiple, 60
reguliers, 293 noeuds, 325
reconnaissables par des automates fi- nombre
nis, 293 chromatique, 349
lexemes, 233 de stabilite, 349
loi de De Morgan, 20 premier, 60
Lukasiewicz, 342 pseudo-premier fort, 96
mecanisme, 248 notation polonaise, 342
methode de construction par sous-ensemble, operation n-aire, 188
258 ordre dun graphe, 298
machine, 247
dacceptation, 253 parcours
de Mealy, 252 en profondeur, 342
machines partie majoree, 37
de Turing partition, 43
deterministes, 292 PGCD, 62
non deterministes a plusieurs bandes, plus grand commun diviseur, 62
292 plus petit commun multiple, 62
majorant, 37 PPCM, 62
matrice predicat, 189
dadjacences, 366 principe
dincidence, 307 de non-contradiction, 135
de transition, 379 du tiers-exclu, 135
fondamentale de la chane absorbante, Principe de la numerotation de position,
385 65
matrice dincidence principe de recurrence, 58
entrante, 365 probleme
sortante, 365 du voyageur de commerce, 324
411
processus stochastique SGBD, 51
regime permanent, 381 sommet, 298
productions, 292 accessible, 300
proposition, 134 adjacent, 298
pseudo-premier, 70 critique, 376
puissance rang, 340
dun ensemble, 31 sommets, 359
du continu, 32 sous-graphe
du denombrable, 32 partiel, 316
stable, 317, 349
quantificateur successeur, 58
champ, 194 surjection, 27
universel, 191 symbole
quotient, 64 de predicat, 190
recurrence, 58 non terminal, 235
generalisee, 59 relationnel, 190
restreinte, 59 terminal, 235
regions, 320 T-flip-flop, 249
reunion, 18 table de transition detats, 250
regle tautologie, 150
de disjonction des cas, 172 test
de reduction a labsurde, 172 de Lucas, 97
rand de Miller-Rabin, 96
dun sommet, 370 theoreme
reconnue, 257 de Bezout, 77
relation de Beth, 180
antisymetrique, 34 de completude, 181
dordre, 34 de la contradiction, 171
partiel, 35 de la contraposee, 170
totale, 35 de la deduction, 167
fonctionnelle, 25 de Ore, 323
reflexive, 33 de substitution, 155
symetrique, 41 Kuratowski, 322
transitive, 34 logique, 163
relation binaire, 23 petit theoreme de Fermat, 95
relation n-aire, 48, 189 Theoreme de falsification, 212
relations n-aires traducteur, 252
egale, 50 transition instantanee, 276
equivalentes, 50 treillis, 40
representation complet, 40
en virgule flottante, 81
reste, 64 unificateur
412
le plus grand, 222
w-compatible, 268
zero, 58
413