Introduction à la logique du premier ordre et à la

théorie naïve des ensembles∗

Table des matières

Introduction 2

1 Logique booléenne 3
1.1 Propositions et valeurs de vérité . . . . . . . . . . . . . . . . . . . . 3
1.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Calcul propositionnel . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Implication et preuve . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Lien avec les circuits logiques . . . . . . . . . . . . . . . . . . . . . 12
1.6 Annexe : syntaxe des propositions . . . . . . . . . . . . . . . . . . . 15

2 Théorie naïve des ensembles 16

2.1 Notions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Ensembles de nombres . . . . . . . . . . . . . . . . . . . . . . . . . 32

3 Logique du premier ordre 36

3.1 Le quantificateur universel . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Le quantificateur existentiel . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4 Négation et preuves par l’absurde . . . . . . . . . . . . . . . . . . . 41
3.5 Application aux bases de données . . . . . . . . . . . . . . . . . . . 42
∗ La version la plus récente de ce document est disponible à l’adresse
« [Link] ». Toute critique
constructive — positive ou négative — et toute correction peut être envoyée à [Link]-
tler@[Link].

1
Introduction
Le premier objectif de ces notes est de vous présenter quelques rudiments de logique
mathématique et de théorie des ensembles ainsi que le formalisme qui sert à exprimer
ces différentes idées. Nous avons essayé d’expliquer avec suffisamment de détails les
concepts fondamentaux (qui seront vus au cours de « mathématique élémentaire »).
Nous nous sommes également autorisés à aborder parfois des éléments plus difficiles
(nous pensons par exemple aux formes normales ; voir page 10). Ceci est fait sur un
mode plus informel et est une invitation à prendre un crayon et une feuille — que vous
devez toujours avoir à portée de la main lorsque vous lisez un texte mathématique —
et à essayer de comprendre plus en profondeur (faites des exemples,...). C’est aussi un
rappel que le champ de la logique est loin de s’arrêter à ces quelques feuilles et c’est
donc une incitation à aller consulter des livres (nous pouvons vous en conseiller).
Un second objectif est, lorsque c’est possible, d’esquisser des liens avec d’autres cours.
Les mathématiques et l’informatique ont de nombreuses connections et s’enrichissent
l’une l’autre. C’est pourquoi nous en présentons quelques unes. Bien sûr, il se peut
que ces passages soient d’un premier abord plus difficiles parce que vous n’avez pas
encore vu la matière concernée. Ne vous découragez pas mais au contraire comprenez
que ces liens sont là pour enrichir votre connaissance. Une fois la matière vue dans un
autre cours, nous espérons que vous consulterez à nouveau ces notes et approfondirez
le lien.
Puisque ce texte est sans doute l’un des premiers que vous lisez en mathématique,
plusieurs défis se présentent à vous. Afin de vous aider à les relever, essayons de les
nommer : il vous faut
comprendre ce qui est expliqué ligne par ligne 1 et le faire vôtre, du moins pour la
partie élémentaire ;
résumer les idées essentielles, ce qui doit vous permettre d’avoir une vue plus glob-
ale de la matière ;
essayer de comprendre les parties plus difficiles et, si nécessaire, poser des ques-
tions ;
lire les sections qui établissent des connections et soit les approfondir immédiate-
ment (si elles vous intéressent), soit attendre que la matière soit vue ailleurs et y
revenir (le professeur de la matière concernée doit pouvoir vous aider).
Bien entendu, si vous éprouvez des difficultés, n’hésitez pas à venir nous voir pour
poser vos questions (les séances de remédiation sont un bon endroit pour cela).
R EMERCIEMENTS : Je remercie S. B RIDOUX, R. H INNION, C. M ICHAUX, F. T RI -
HAN et J. W IJSEN pour leur lecture attentive de ces notes.

1. Ces feuilles comportent de nombreux tableaux et figures qui entrecoupent le texte, parfois au
milieu d’une phrase. Il vous suffit de sauter le tableau ou la figure pour continuer votre lecture.

2
1 Logique booléenne

1.1 Propositions et valeurs de vérité

La logique booléenne s’intéresse à la manière dont on peut créer de nouvelles propo-

sitions à partir de propositions « élémentaires » et comment de la vérité ou la fausseté
de ces propositions dites élémentaires on peut déduire la vérité ou la fausseté de la
proposition construite. Explicitons les différents éléments.
I Les propositions élémentaires sont des affirmations telles que « le soleil est
rouge » ou « les hommes sont verts ». En logique booléenne, on n’a aucune manière
de parler du sens de ces propositions ni de savoir si elles sont vraies ou fausses en
elles-mêmes. Tout ce qui va nous intéresser, c’est la vérité ou la fausseté de celles-ci
en relation avec d’autres. Les exemples ci-après clarifieront cela.
I Pour désigner les propositions de manière abstraite, on emploiera en général des
lettres majuscules P, Q,... Les manières de combiner les propositions sont limitées :
on pourra prendre la négation, la conjonction, la disjonction, l’implication et l’équiva-
lence :
Appellation français logique langage C
négation non P ¬P !P
conjonction P et Q P∧Q P && Q
disjonction P ou Q P∨Q P || Q
implication si P alors Q P ⇒ Q
équivalence P ssi 2 Q P⇔Q
Ces divers symboles (¬, ∧, ∨, ⇒, ⇔) sont appelés des connecteurs logiques. Ceux qui
sont intéressés trouveront à la section 1.6 une description formelle de la manière de
former les propositions.
I La valeur de vérité d’une proposition P est « vrai » si P est vraie et « faux »
si P est fausse. Pour la concision, on notera aussi 1 pour vrai et 0 pour faux. Comme
nous l’avons dit précédemment, la logique booléenne s’intéresse à la propagation des
valeurs de vérité au travers des constructions permises. Par exemple, on voudrait savoir
comment la valeur de vérité de P ∧ Q dépend de celles de P et Q. Puisque le sens que
l’on veut donner à « ∧ » est « et », on aura que P ∧ Q sera vrai si P et Q sont vrais et
sera faux dans tous les autres cas. On peut résumer cela par une table de vérité (voir
Tab. 1 où elle est présentée de diverses manières).
Les tables de vérité des autres connecteurs se construisent de la même manière (Tab. 2).

2. « ssi » est l’abréviation de « si et seulement si »

3
 P
Q 0 1 P 0 1 P Q P∧Q
0 0 0 Q 0 1 0 1 0 0 0
1 0 1 P∧Q 0 0 0 1 0 1 0
1 0 0
1 1 1
TABLE 1 – Table de vérité de P ∧ Q (diverses présentations).
P P P
P ¬P Q 0 1 Q 0 1 Q 0 1
0 1 0 0 1 0 1 0 0 1 0
1 0 1 1 1 1 1 1 1 0 1
P∨Q P⇒Q P⇔Q
TABLE 2 – Tables de vérité des divers connecteurs logiques

Quelques remarques sont de rigueur.

Tout d’abord, la proposition P ∨ Q (i.e., « P ou Q ») est vraie dès que l’une des
deux propositions la formant est vraie ou à fortiori si elles le sont toutes les deux.
Cela contraste avec l’usage courant de « ou » par lequel on sous entend souvent
l’exclusion de P et Q : je laverai la voiture (P) ou ferai la vaisselle (Q) (mais pas les
deux !). Avec le « ou logique » cependant, une telle exclusion n’est pas implicite ; la
phrase précédente signifierait donc : des tâches laver la voiture et faire la vaisselle,
j’en accomplirai au moins une. Si on veut dire « mais pas les deux », il faut le faire
explicitement en utilisant le ou exclusif, noté ∨,˙ dont la table de vérité est donnée
par le tableau 3. La proposition P ∨ ˙ Q peut aussi être rendue en français par : soit
P, soit Q.
P
Q 0 1
0 0 1
1 1 0
˙Q
TABLE 3 – Table de vérité de P ∨

L’implication P ⇒ Q est la plus difficile à comprendre lorsqu’on commence à ap-

prendre la logique. Quand est-elle vraie ? Pour le voir, choisissons une phrase sim-
ple. Supposons que j’aie affirmé : « si je gagne au loto, alors je vous offre un pot ».
Symboliquement, cela s’écrit :
(
P = je gagne au loto,
P⇒Q avec
Q = je vous offre un pot.
Quand l’affirmation que j’ai faite est-elle vraie ? Ou, si vous préférez, quand peut-
on dire que j’ai tenu ma promesse ?

4
 Si je gagne au loto (P est vrai) et que j’offre un pot (Q est vrai), j’ai fait ce que
j’ai promis (P ⇒ Q est vrai). Par contre, si je gagne (P est vrai) mais que je n’offre
pas à boire (Q est faux), je suis un menteur (P ⇒ Q est faux). D’autre part, si je ne
gagne pas au loto (P est faux), je ne me suis engagé à rien : que j’offre un pot (Q
est vrai) ou non (Q est faux), j’ai tenu ma promesse (P ⇒ Q est vrai) — on ne peut
pas dire que je suis un menteur.
En rassemblant les quatre cas qu’on vient d’examiner (faites-le !), on obtient la
table de vérité de l’implication (cf. Tab. 2).
Résumons ce que nous avons vu jusqu’à présent.
Nous partons de propositions élémentaires qui peuvent être vraies ou fausses.
à partir de deux propositions P et Q, on peut former d’autres propositions ¬P,
P ∧ Q, P ∨ Q, P ⇒ Q, P ⇔ Q.
Si on connaît les valeurs de vérité de P et Q, on peut déduire celles de ¬P, P∧Q,...

1.2 Exemples

Il est temps maintenant de passer à quelques exemples. Notez que le passage du

français à la forme logique correspondante est un exercice difficile auquel il faut s’en-
traîner. Il convient de le faire tout de suite car nous enrichirons plus tard notre vocab-
ulaire logique, ce qui augmentera la difficulté.
Les exemples simples de phrases qu’on peut traduire sont assez bêtes. On peut sym-
boliser « la terre est ronde ou le soleil est noir » par
(
P := la terre est ronde
P ∨ Q avec
Q := le soleil est noir

En supposant que P est vrai, on a que P ∨ Q est vrai — peu importe si Q est vrai ou
non. Notez que la logique seule ne nous permet pas de savoir si P est vrai ou non.
Considérer P vrai dépend de facteurs extérieurs à celle-ci — le monde physique, nos
connaissances scientifiques,... Autrement dit, la logique peut servir à rassembler divers
éléments qui impliquent que P est vrai mais elle ne peut l’affirmer ex nihilo.
Si ceci ne semble pas d’un grand intérêt, c’est que l’expressivité de notre langage
logique est limitée. Nous pouvons néanmoins déjà jouer au détective ! Voici l’énoncé
du problème :
Un meurtre a été commis. Un inspecteur de passage est appelé à l’aide. Sa
tâche n’est pas facile : seuls les habitants du sud de la ville disent toujours
la vérité. On présente à l’inspecteur trois témoins Alex, Virginie et Carl des
deux parties de la ville. Il commence par les interroger, dans l’espoir de
trouver un habitant du quartier sud (qui lui dise la vérité sur le meurtre).
Voici leur réponses :

5
 Alex : Virginie habite au sud ;
Virginie : Alex et moi habitons ensemble ;
Carl : C’est faux, Virginie ment !
Pouvez vous aider le pauvre policier ?
Formalisons la question. Tout d’abord, il faut discerner quelles sont les propositions
élémentaires qui nous intéressent. Puisque c’est savoir dans quelle partie de la ville
habite chacune des trois personnes, on prend :
P1 = Alex vit au sud de la ville ;
P2 = Virginie vit au sud de la ville ;
P3 = Carl vit au sud de la ville.
Il faut maintenant traduire leurs affirmations sous forme de propositions logiques. In-
téressons nous d’abord à la déposition d’Alex. De deux choses l’une :
Si Alex habite au sud de la ville, il dit la vérité. Or Alex affirme P2 . Donc, si P1 est
vrai, alors P2 l’est également.
Si Alex habite au nord, peut-être dit-il la vérité mais peut-être ment-il. On ne peut
donc rien conclure sur la valeur de vérité de P2 .
Donc P1 ⇒ P2 est vrai. Si vous n’en êtes pas convaincus, comparez ce qui vient d’être
dit à la table de vérité de P1 ⇒ P2 (Tab. 2). On fait un raisonnement analogue pour
Virginie et Carl. Si Virginie vit au sud (si P2 est vrai), elle et Alex vivent ensemble,
c’est-à-dire tous les deux au sud, P1 ∧ P2 , ou tous les deux au nord ¬P1 ∧ ¬P2 . Donc
la proposition (3) ci-dessous est vraie. Si Carl vit au sud, Virginie ment et donc la
négation de ce qu’elle affirme est vraie. Cela dit que (4) est vrai. Enfin, nous savons
que les trois témoins sont des deux parties de la ville, c’est-à-dire que deux habitent
au sud et un au nord, Pi ∧ Pj ∧ ¬Pk , ou l’inverse, ¬Pi ∧ ¬Pj ∧ Pk , pour certains i, j, k
différents deux à deux. En conclusion on obtient les propositions suivantes :
(P1 ∧ P2 ∧ ¬P3 ) ∨ (P1 ∧ P3 ∧ ¬P2 ) ∨ (P2 ∧ P3 ∧ ¬P1 )
(1)
∨ (¬P1 ∧ ¬P2 ∧ P3 ) ∨ (¬P1 ∧ ¬P3 ∧ P2 ) ∨ (¬P2 ∧ ¬P3 ∧ P1 )
P1 ⇒ P2 (2)


P2 ⇒ (P1 ∧ P2 ) ∨ (¬P1 ∧ ¬P2 ) (3)


P3 ⇒ ¬ (P1 ∧ P2 ) ∨ (¬P1 ∧ ¬P2 ) (4)
L’affirmation que toutes les propositions (1)–(4) sont vraies implique certaines restric-
tions sur les valeurs de vérité des propositions élémentaires P1 , P2 , P3 . Pour le voir on
peut construire la table de vérité (Tab. 4). On voit que la seule possibilité pour que
(1)–(4) soient simultanément vraies est que P1 et P2 soient vrais et P3 faux. Il faut
donc interroger Alex ou Virginie. Il existe une alternative à la construction de tables
de vérité. On peut voir (1)–(4) comme des équations logiques dont il faut trouver les
solutions. Pour cela nous allons développer un calcul sur les propositions.

6
 P1 0 1
P2 0 1 0 1
P3 0 1 0 1 0 1 0 1
P1 ∧ P2 0 0 0 0 0 0 1 1
¬P1 ∧ ¬P2 1 1 0 0 0 0 0 0
(P1 ∧ P2 ) ∨ (¬P1 ∧ ¬P2 ) 1 1 0 0 0 0 1 1
(1) 0 1 1 1 1 1 1 0
(2) 1 1 1 1 0 0 1 1
(3) 1 1 0 0 1 1 1 1
(4) 1 0 1 0 1 0 1 1

TABLE 4 – Table de vérité de (1)–(4)

1.3 Calcul propositionnel

Comme nous l’avons déjà dit, la logique booléenne ne s’intéresse pas au sens des
propositions — elle n’est pas outillée pour cela — mais seulement à leurs valeurs
de vérité. C’est le moment d’en tirer toutes les conséquences. Supposons que nous
ayons une proposition P qui dépend des propositions Q1 , . . . , Qn . Pour mettre en év-
idence cette dépendance, nous écrirons P(Q1 , . . . , Qn ). Par exemple, nous pourrions
avoir P(Q) = Q ∨ ¬Q. On dit que P(Q1 , . . . , Qn ) est une tautologie si P est vrai quelles
que soient les valeurs de vérité de Q1 , . . . , Qn . Autrement dit, P est une tautologie si
et seulement si la ligne de P dans la table de vérité n’est composée que de 1. Pour
P(Q) = Q ∨ ¬Q, on constate sur la table 5 que c’est une tautologie. Considérons un

Q 0 1
¬Q 1 0
P 1 1

TABLE 5 – Table de P(Q) = Q ∨ ¬Q

autre exemple. Soit P0 (Q1 , Q2 ) = Q1 ⇒ (Q1 ∨ Q2 ). D’après la table 6 (vérifiez qu’elle

est correcte !), on voit que P0 est aussi une tautologie.

Q1 0 1
Q2 0 1 0 1
Q1 ∨ Q2 0 1 1 1
P0 1 1 1 1

TABLE 6 – Table de P0 (Q1 , Q2 ) = Q1 ⇒ (Q1 ∨ Q2 )

Introduisons maintenant une notion essentielle. Si deux propositions P1 et P2 dépendent

7
des mêmes propositions Q1 , . . . , Qn (ce qui est toujours possible en choisissant Q1 , . . . ,
Qn comme toutes les propositions qui apparaissent dans P1 ou dans P2 vu qu’on peut
considérer que Pi dépend de Q j de manière constante si Q j n’apparaît pas explicite-
ment dans Pi ), on dit qu’elles sont équivalentes si, pour toutes les valeurs de vérité
de Q1 , . . . , Qn , P1 (Q1 , . . . , Qn ) et P2 (Q1 , . . . , Qn ) sont vrais et faux en même temps.
Autrement dit, P1 et P2 sont des propositions équivalentes si leurs tables de vérité sont
identiques. Nous écrirons alors 3
P1 ' P2 .
Par exemple P1 (Q1 , Q2 ) = (Q1 ⇒ Q2 ) et P2 (Q1 , Q2 ) = (¬Q1 ∨ Q2 ) sont équivalentes
au vu des tables 7. De la même manière, on peut voir que Q1 ⇔ Q2 est équivalent à

Q1 0 1
Q2 0 1 0 1
P1 = Q1 ⇒ Q2 1 1 0 1
¬Q1 1 1 0 0
P2 = ¬Q1 ∨ Q2 1 1 0 1

TABLE 7 – Équivalence des formules P1 et P2

(Q1 ⇒ Q2 ) ∧ (Q2 ⇒ Q1 ) (Tab. 8). En fait, comme P1 ⇔ P2 est vrai si et seulement si

Q1 0 1
Q2 0 1 0 1
Q1 ⇔ Q2 1 0 0 1
Q1 ⇒ Q2 1 1 0 1
Q2 ⇒ Q1 1 0 1 1
(Q1 ⇒ Q2 ) ∧ (Q2 ⇒ Q1 ) 1 0 0 1

TABLE 8 – Équivalence de deux formules

les valeurs de vérité de P1 et P2 sont les mêmes, les

deux propositions P1 et P2 sont équivalentes (P1 ' P2 )

si et seulement si
P1 ⇔ P2 est une tautologie.

Cette notion d’équivalence est à la base du calcul sur les propositions. En effet, c’est
elle qui permet de transformer une expression logique (une suite de symboles) en une
autre en préservant ce qui nous importe, c’est-à-dire ses valeurs de vérité. Pour les
3. Il n’y a pas de notation généralement acceptée pour l’équivalence de deux propositions. Le sym-
bole « ' » doit donc être considéré comme spécifique aux présentes notes.

8
propositions, « être équivalentes » est une sorte d’égalité ou, pour être plus précis,
est une relation d’équivalence, ce qui signifie que les trois propriétés suivantes sont
satisfaites : « ' » est
réflexive : P1 ' P1 ;
symétrique : P1 ' P2 si et seulement si P2 ' P1 ;
transitive : P1 ' P2 et P2 ' P3 impliquent P1 ' P3 .
C’est la transitivité spécialement qui permet de faire des calculs « pas à pas » (com-
prenez-vous pourquoi ?). Reste donc à trouver des équivalences utiles pour pouvoir
transformer les propositions. Comme nous venons de le voir, les deux connecteurs
« ⇒ » et « ⇔ » s’expriment en fonction des autres :

P1 ⇒ P2 est équivalent à ¬P1 ∨ P2 , (5)

P1 ⇔ P2 est équivalent à (P1 ⇒ P2 ) ∧ (P2 ⇒ P1 ). (6)

Il en est de même pour le « ou exclusif » :

˙ P2 est équivalent à (P1 ∨ P2 ) ∧ ¬(P1 ∧ P2 ).

P1 ∨ (7)

Pour manipuler les trois connecteurs ¬, ∧, ∨, deux équivalences sont importantes.

Elles sont connues sous le nom de lois de de Morgan et permettent de « distribuer » la
négation sur un ∧ ou ∨ :

¬(P1 ∧ P2 ) est équivalent à ¬P1 ∨ ¬P2 ,

¬(P1 ∨ P2 ) est équivalent à ¬P1 ∧ ¬P2 .

On a aussi les lois de distributivité entre ∧ et ∨ :

P1 ∨ (P2 ∧ P3 ) est équivalent à (P1 ∨ P2 ) ∧ (P1 ∨ P3 ), (8)

P1 ∧ (P2 ∨ P3 ) est équivalent à (P1 ∧ P2 ) ∨ (P1 ∧ P3 ). (9)

Grâce à ces règles (vérifiez qu’elles sont correctes !), on peut mettre les propositions
sous forme canonique. Soit P une proposition qui dépend de Q1 , . . . , Qn . Tout d’abord,
en utilisant (5)–(7), on peut transformer la formule pour que seulement les connecteurs
¬, ∧, ∨ y apparaissent. Ensuite les lois de de Morgan permettent de « coller » les
négations aux propositions Qk , si bien que la formule est composée de Qk et ¬Qk
assemblés grâce à ∧ et ∨. Enfin, on peut utiliser les lois de distributivité entre ∧ et ∨
pour
soit distribuer tous les ∨ sur les groupes de ∧ (eq. (8)), ce qui fait que la formule
finale est une conjonction de disjonctions ;
soit distribuer les ∧ sur les ∨ (eq. (9)), ce qui donne une formule du type disjonction
de conjonctions.

9
En résumé, toute proposition P(Q1 , . . . , Qn ) est équivalente à deux formes normales :
Vm W pi 0
forme normale conjonctive : i=1 j=1 Qi j
Wq Vri 00
forme normale disjonctive : i=1 j=1 Qi j

où Q0i j et Q00i j représentent soit Qk soit ¬Qk pour un certain k ∈ {1, . . . , n} qui dépend
de i et j.
Wq
Remarque 1. Pour le problème du détective, la forme i=1 rj=1 i
Q00 est bien adaptée
V
W V 00 i j
car on y lit directement les solutions. En effet, pour que i j Qi j soit vrai, il faut et
il suffit que j Q00i j soit vrai pour un i et j Q00i j est vrai si et seulement si Q00i j est vrai
V V

pour tout j. Selon que Q00i j représente Qk ou ¬Qk , on en déduit la valeur de vérité de
Qk . Dans le cas particulier des équations (1)–(4), on a (faites les calculs !) :

(1) ∧ (2) ∧ (3) ∧ (4) ' P1 ∧ P2 ∧ ¬P3

d’où on tire qu’il y a une unique solution : P1 , P2 et ¬P3 vrais.

Exercice 1. Prouvez les équivalences suivantes :
(P1 ∧ P2 ) ∧ P3 ' P1 ∧ (P2 ∧ P3 )
(P1 ∨ P2 ) ∨ P3 ' P1 ∨ (P2 ∨ P3 )

1.4 Implication et preuve

Cette section donne un aperçu des preuves du point de vue de la logique booléenne.
Étant donné le peu de familiarité que vous possédez avec le travail de preuve, il est
possible que vous ne puissiez relier certaines affirmations de cette section à votre ex-
périence. Dans ce cas, lisez-là une première fois et revenez y plus tard, lorsque votre
expérience se sera enrichie.
Une preuve consiste à montrer qu’une certaine affirmation est vraie moyennant cer-
taines hypothèses. Autrement dit, on suppose que des hypothèses H1 , H2 ,..., Hn sont
vraies et on en déduit une thèse T . Cela revient à établir (par une preuve mathématique)
que l’implication
(H1 ∧ H2 ∧ · · · ∧ Hn ) ⇒ T (10)
est vraie. Notez que, si une des hypothèses est fausse, peut-être la thèse le devient-
elle aussi ou peut-être reste-elle vraie. Ceci est cohérent avec la table de vérité de
l’implication (vérifiez-le !). Insistons donc que quand une hypothèse n’est pas vérifiée,
on ne peut conclure de (H1 ∧ · · · ∧ Hn ) ⇒ T que la thèse T est fausse, il faut chercher
la valeur de vérité de T par d’autres voies...
De manière générale, le processus de preuve consiste à transformer les hypothèses
pour faire apparaître la conclusion. Plus spécifiquement, on utilise des tautologies pour

10
obtenir une chaîne d’implications Pi ⇒ Pi+1 qui mène des hypothèses H1 ∧ · · · ∧ Hn , qui
est l’étape initiale P0 , à la thèse T :

H1 ∧ · · · ∧ Hn = P0 ⇒ P1 ⇒ P2 ⇒ · · · ⇒ Pk ' T .

Il existe cependant deux autres manières usuelles de procéder que nous allons main-
tenant expliquer.
Faire une preuve par l’absurde signifie qu’on suppose que les hypothèses sont vérifiées
mais que la conclusion est fausse et on en déduit une contradiction. Une contradiction
est quelque chose de manifestement faux et prend souvent la forme P ∧ ¬P pour une
certaine proposition P. En termes de logique booléenne, une preuve par l’absurde se
traduit par le fait que

(H1 ∧ H2 ∧ · · · ∧ Hn ∧ ¬T ) ⇒ (P ∧ ¬P) (11)

est vrai pour un certain P. Notons que ceci est équivalent à (10). Pour la simplicité
d’écriture du calcul ci-après, posons H := H1 ∧ · · · ∧ Hn . On a alors :

(H ∧ ¬T ) ⇒ (P ∧ ¬P) ' ¬(H ∧ ¬T ) ∨ (P ∧ ¬P) ' ¬(H ∧ ¬T )

' ¬H ∨ ¬¬T ' ¬H ∨ T
'H ⇒T

On fait aussi couramment des preuves par contraposition. Cela veut dire qu’au lieu de
prouver H ⇒ T , on établit l’implication équivalente ¬T ⇒ ¬H où, comme précédem-
ment, on a posé H = H1 ∧ · · · ∧ Hn . Notons que ¬H ' ¬H1 ∨ · · · ∨ ¬Hn et donc, pour
que ¬H soit vrai, il suffit que l’un au moins des Hi soit faux. Cette démarche est tout à
fait correcte au vu des équivalences suivantes (vérifiez-les !) :

¬T ⇒ ¬H ' ¬¬T ∨ ¬H ' T ∨ ¬H ' H ⇒ T .

Ceci conclut notre discussion sur les preuves. Divers exemples exploitant ces principes
seront données lorsque nous aurons enrichi notre vocabulaire avec les quantificateurs.
Remarquons pour finir que, si techniquement toutes les preuves sont sensées pouvoir
s’écrire comme une suite de propositions déduites les unes des autres grâce à des tau-
tologies, dans la pratique les démonstrations ne sont jamais faites de manière aussi
formelle. Le seraient-elles qu’elles en deviendraient illisibles ! Les preuves écrites par
les mathématiciens sont un mélange de « formules » liées par des déductions faites en
français. Bien rédiger les phrases qui lient ces formules est donc essentiel puisque ce
sont les enchaînements qu’elles font qui conduisent des hypothèses à la thèse.

11
1.5 Lien avec les circuits logiques

L’électronique des circuits logiques, aussi appelée digitale, n’utilise que deux valeurs
de tension : une valeur haute que nous noterons 1 et une valeur basse, notée 0. Les
portes logiques combinent ces valeurs de tension. Par exemple la porte logique ap-
pelée AND (Tab. 9) possède deux entrées étiquetées par P et Q et une sortie notée R.
L’électronique de AND est conçue pour que la porte donne en sortie une tension haute
si ses deux entrées sont hautes et une tension basse dans tous les autres cas. Cela est
résumé par le tableau 9. Si on remplace « haut » par « 1 » et « bas » par « 0 » comme

P P
Q bas haut Q 0 1
P R R = P∧Q
Q bas bas bas 0 0 0
haut bas haut 1 0 1

TABLE 9 – Porte AND TABLE 10 – Équivalent logique de AND

nous l’avons convenu ci-dessus, on voit (Tab. 10) qu’on obtient la table de vérité de
∧. Autrement dit, plutôt que de décrire le comportement de la porte AND en termes de
tensions, il suffit de dire que la sortie R réalise l’opération logique « et » : R = P ∧ Q.
On peut faire la même chose avec les autres portes logiques. Le tableau 11 donne,
pour chacune des portes logiques usuelles, la proposition correspondante — ce qui
d’ailleurs explique le nom donné aux portes. On peut évidemment le lire dans l’autre
sens et l’utiliser pour passer des propositions aux portes. Puisqu’on peut passer d’une

Nom Porte logique Proposition

inverseur P R R = ¬P

AND
P R R = P∧Q
Q

OR
P R R = P∨Q
Q
P ˙Q
XOR
Q R R = P∨

NAND (not and) P R R = ¬(P ∧ Q)

Q

NOR (not or) P R R = ¬(P ∨ Q)

Q

TABLE 11 – Correspondance entre les portes et les connecteurs logiques

porte logique à une formule booléenne et vice-versa, on peut le faire également pour

12
des circuits plus élaborés. Considérons par exemple le circuit donné par la figure 1.
On peut aisément écrire la proposition qui lie R à Q1 et Q2 . En effet, R = S1 ∨ S2 avec
Q1 S1
Q2
R

S2

F IGURE 1 – Un circuit à simplifier

S1 = Q1 ∧ Q2 et S2 = Q1 ∧ ¬Q2 , ce qui donne

R = (Q1 ∧ Q2 ) ∨ (Q1 ∧ ¬Q2 ).

La règle (9) permet de mettre en évidence Q1 si bien que R est équivalent à Q1 ∧ (Q2 ∨
¬Q2 ). Comme Q2 ∨ ¬Q2 est une tautologie, cette dernière expression est équivalente
à Q1 . En résumé,
R(Q1 , Q2 ) ' Q1
ce qui veut dire que le circuit de la figure 1 fait la même chose qu’un simple fil joignant
Q1 à R !
Cette correspondance entre circuits logiques et propositions est aussi d’une grande
utilité lorsqu’il s’agit de construire des circuits. Supposons que nous voulions constru-
ire un circuit possédant le comportement donné par la table 12. De celle-ci, on déduit

Q1 = entrée 1 0 1
Q2 = entrée 2 0 1 0 1
Q3 = entrée 3 0 1 0 1 0 1 0 1
R = sortie 0 1 0 0 0 1 0 1

TABLE 12 – Table d’un circuit

immédiatement la formule

R ' (¬Q1 ∧ ¬Q2 ∧ Q3 ) ∨ (Q1 ∧ ¬Q2 ∧ Q3 ) ∨ (Q1 ∧ Q2 ∧ Q3 ). (12)

Pour pouvoir dessiner le circuit correspondant, il faut transformer cette formule pour
faire apparaître celles de la table 11. Une possibilité immédiate est de rajouter des
parenthèses, ce qui par exemple donne




R ' (¬Q1 ∧ ¬Q2 ) ∧ Q3 ∨ (Q1 ∧ ¬Q2 ) ∧ Q3 ∨ (Q1 ∧ Q2 ) ∧ Q3 .

13
 Q1
Q2
Q3

F IGURE 2 – Première version d’un circuit donnant le tableau 12

La traduction de cette formule en termes de portes donne le circuit de la figure 2.

Comme celui-ci est assez complexe, nous voudrions simplifier la formule avant de
construire le circuit associé. En mettant Q1 ∧ Q3 en évidence dans les deux derniers
termes de (12), on a (faites les détails !) :

R ' (¬Q1 ∧ ¬Q2 ∧ Q3 ) ∨ (Q1 ∧ Q3 ).

Ensuite, en mettant la négation en évidence, on obtient :

R ' ¬(Q1 ∨ Q2 ) ∧ Q3 ∨ (Q1 ∧ Q3 ),

d’où on tire facilement le circuit de la figure 3. Notons qu’il y a d’autres possibilités.

Q1
Q2

Q3

F IGURE 3 – Un circuit donnant le tableau 12

Par exemple, on peut vérifier (faites-le !) que

R ' (Q1 ∧ Q3 ) ∨ (¬Q2 ∧ Q3 ),

ce qui donne le circuit de la figure 4.

14
 Q1
Q3
R

Q2

F IGURE 4 – Un autre circuit donnant le tableau 12

Logique Électronique
¬P P
P∧Q P·Q
P∨Q P+Q
P∨˙Q P⊕Q
TABLE 13 – Notations en électronique

Remarque 2. En électronique, on a tendance à voir les opérations booléennes comme

des fonctions sur Z2 = {0, 1} ; par exemple ∧ : Z2 × Z2 → Z2 ,... Il est de coutume
aussi de prendre des notations plus proches de l’arithmétique ordinaire (voir Tab. 13).
La raison est que les « + » et « · » du tableau 13 sont les opérations habituelles sur
Z2 (calculs sur Z modulo 2). Concrètement, « · » est la multiplication usuelle sur Z et
« + » est l’addition standard sur Z sauf que 1 + 1 = 0. Avec ces notations, certaines
propriétés vues précédemment semblent évidentes (comme le fait que « · » se distribue
sur « + ») mais d’autres au contraire sont « anti-naturelles » (comme le fait que « + »
se distribue sur « · »).

Nous n’investiguerons pas plus les liens entre le calcul propositionnel et les circuits
logiques. Les questions que vous pouvez vous poser — comme par exemple la manière
de simplifier 4 une proposition afin d’obtenir un circuit avec le moins de portes possi-
bles (utile pour faire des économies sur des circuits comprenant un grand nombre de
portes) — devraient trouver réponse dans d’autres cours.

1.6 Annexe : syntaxe des propositions

Ce paragraphe décrit dans la méta-syntaxe 5 BNF (Backus-Naur Form) la forme des

propositions de la logique booléenne (Tab. 14). Nous ne décrirons pas ici la méta-
4. Pour les plus curieux, citons la méthode des diagrammes de K ARNAUGH et celle de Q UINE-M AC
C LUSKEY qui sont couramment employées.
5. Le terme méta-syntaxe signifie qu’il s’agit d’une « syntaxe pour décrire les syntaxes »...

15
syntaxe BNF elle-même (ceci a plutôt sa place dans un cours d’informatique 6 ), d’au-
tant plus qu’elle est assez facile à lire une fois qu’on sait que « ::= » signifie « est
défini comme » et que « » marque une alternative.

hpropositioni ::= hproposition élémentairei

¬(hpropositioni)
(hpropositioni) ∧ (hpropositioni)
(hpropositioni) ∨ (hpropositioni)
(hpropositioni) ⇒ (hpropositioni)
(hpropositioni) ⇔ (hpropositioni)
TABLE 14 – Syntaxe des propositions

BNF est largement utilisé pour spécifier la syntaxe des langages de programmation
et par les programmes d’analyse syntaxique (parsers) tels que 7 yacc. Notre but en
décrivant les règles de construction des propositions sous la forme BNF est d’insister
sur le fait qu’en logique propositionnelle — comme avec les langages de programma-
tion — on ne peut écrire que des expressions permises par ces règles et rien d’autre (par
exemple P ∧ ∨Q et ∃x : P(x) ne sont pas des propositions de la logique booléenne !).
Comme note finale, remarquons que la définition de hpropositioni est récursive. Ainsi
un algorithme de parsing s’exprimera naturellement sous forme récursive.

2 Théorie naïve des ensembles

2.1 Notions de base

Cette section présente quelques notions de base de la théorie des ensembles. Le style
est informel : poussés dans leurs retranchements, les concepts ci-dessous mènent à des
paradoxes qui nécessitent, pour être levés, une formalisation accrue — et trop lourde
pour une première approche.
Intuitivement, un ensemble est une collection d’objets. Ainsi, la notion fondamentale
est celle d’appartenance 8 : le fait qu’un objet a soit dans un ensemble A sera noté
6. On en parle avec beaucoup plus de détails dans le cours de logique mathématique de C. M ICHAUX
(pour la description des langages du premier ordre) et dans « Algorithme II » de V. B RUYÈRE.
7. En pratique, lorsqu’on veut analyser un langage informatique donné, on utilise d’abord un lexer,
tel lex, pour transformer le texte en tokens — variables, mots réservés, symboles d’opérations,... — et
seulement ensuite yacc afin de déterminer si ceux-ci forment des expressions correctes du langage.
8. D’un point de vue formel, la notion d’ensemble n’est pas définie, la relation « ∈ » est prise comme
primitive et on suppose à son sujet un certain nombre de propriétés (axiomes). De plus, il n’y a plus de

16
a ∈ A (dites « a appartient à A »). La négation de l’appartenance, ¬(a ∈ A), s’abrège
en a ∈
/ A. Deux ensembles (disons A et B) sont les mêmes (A = B) s’ils possèdent les
mêmes éléments (pour tout a, a ∈ A ⇔ a ∈ B).
On peut décrire des ensembles en extension, c’est-à-dire en donnant explicitement tous
leurs éléments. L’ensemble qui contient les objets a1 , . . . , an et uniquement ceux-là est
noté
{a1 , . . . , an }.
Insistons sur le fait que deux ensembles sont égaux dès qu’ils possèdent les mêmes
éléments ; il n’y a pas de relation d’ordre. Ainsi, {1, 2, 3} = {3, 2, 1}. Une autre con-
séquence est que répéter un élément ne modifie pas l’ensemble : {1, 1} = {1}. Un
ensemble particulier est l’ensemble vide ∅ = {} qui ne contient aucun élément. Ainsi,
x ∈ ∅ est une assertion qui est toujours fausse.
On dit qu’un ensemble A est inclus à un autre ensemble B, ce qu’on note A ⊂ B ou
A ⊆ B, si tout élément de A appartient également à B. Il ne faut pas confondre cette
notion avec l’appartenance ; en fait a ∈ A si et seulement si {a} ⊂ A.
Les ensembles peuvent également être décrits en compréhension, c’est-à-dire par une
propriété. L’ensemble des éléments a qui vérifient la propriété P se note 9 ,10 :

{a : a vérifie P}. (13)

Autrement dit, la définition affirme que l’équivalence suivante est vraie :

x ∈ {a : a vérifie P} ⇐⇒ x vérifie P.

Par exemple, {x : x ∈ N ∧ x divise 12} = {1, 2, 3, 4, 6, 12}. Ou encore [a, b] = {x : x ∈

R ∧ a 6 x ∧ x 6 b} est l’intervalle des nombres réels compris entre a et b inclus. Sou-
vent on abrège 11 {a : a ∈ A ∧ . . .} en {a ∈ A : . . .}. Les définitions en compréhension
permettent de faire le lien entre les connecteurs de la logique booléenne et les opéra-
distinction entre objet et ensemble : tout est ensemble. Par la relation a ∈ A, on exprime qu’un ensemble
a est membre de l’ensemble A...
9. L’usage immodéré de ce principe donne lieu à des contradictions. En effet, construisons U := {x :
x∈/ x}. On en déduit qu’on a U ∈ U ⇐⇒ U ∈ / U. Cette dernière affirmation cependant ne peut être
vraie... Cet argument est appelé le paradoxe de Russell.
10 Notons que l’emploi de la lettre « a » dans (13) n’est pas important ; c’est une variable « muette ».

En d’autres termes « a » n’est là que pour donner un nom à l’élément duquel on parle, ce nom n’est pas
connu à l’extérieur des {. . .}. On a donc {a : a vérifie P} = {b : b vérifie P}...
11. L’utilisation exclusive du schéma de compréhension de la forme {a ∈ A : a vérifie P} permet
d’éviter la contradiction ci-dessus. Cependant, cet axiome n’est pas assez puissant ; il ne permet même
pas de définir l’union de deux ensembles,...

17
tions élémentaires sur les ensembles. On a
Nom Définition Opération logique
complémentaire {A = {x : x ∈
/ A} négation

complémentaire relatif {B A = B \ A = x : (x ∈ B) ∧ (x ∈
/ A)

intersection A ∩ B = x : (x ∈ A) ∧ (x ∈ B) « et »

union A ∪ B = x : (x ∈ A) ∨ (x ∈ B) « ou »

différence symétrique ˙ (x ∈ B)
A ∆ B = x : (x ∈ A) ∨ « ou exclusif »

On peut représenter ces opérations par des diagrammes de Venn. Concrètement, il

s’agit de représenter un ensemble par une « patate », les points se situant à l’intérieur
de cette patate symbolisant les éléments de l’ensemble. La figure 5 décrit les opéra-
tions d’union, d’intersection,... sous cette forme. Ce lien entre logique booléenne et

B
{A ←
A A B\A
A

{B A ←
B

B A∪B
A A∩B

A→ ←
B

A∆B

A→ ←
B

F IGURE 5 – Diagrammes de Venn

théorie des ensembles est très utile. Tout d’abord, on vérifie facilement (faites-le !) que
deux formules équivalentes définissent le même ensemble :

si P1 ' P2 , alors {x : x vérifie P1 } = {x : x vérifie P2 }. (14)

Par exemple, la proposition P1 := (x ∈ R ∧ x2 − x = 0) est équivalente à P2 := (x =

0 ∨ x = 1) — puisqu’elles sont vraies et fausses en même temps pour tout x — et
donc {x ∈ R : x2 − x = 0} = {x : x vérifie P1 } = {x : x vérifie P2 } = {x : x = 0 ∨ x =

18
1} = {0, 1}. De (14), on peut déduire de multiples conséquences. Par exemple, puisque
(P ∧ Q) ∧ R ' P ∧ (Q ∧ R), on a (A ∩ B) ∩ C = A ∩ (B ∩ C). Des lois de distributivité
(8)–(9), on conclut que (pouvez-vous faire les détails ?) :
A ∪ (B ∩C) = (A ∪ B) ∩ (A ∪C),
A ∩ (B ∪C) = (A ∩ B) ∪ (A ∩C).
Nous laissons le soin au lecteur d’écrire les identités ensemblistes qui découlent des
autres équivalences vues précédemment.
Les définitions en compréhension permettent de créer beaucoup d’autres ensembles.
Par exemple, l’ensemble des parties de A est
PA := {B : B ⊂ A}.
Une autre opération importante est le produit cartésien. Rappelons que se donner un
couple (x, y), c’est se donner les valeurs x et y et l’ordre dans lequel on les place.
Ainsi, (1, 2) est différent de (2, 1) — au contraire de {1, 2} = {2, 1}. La propriété
fondamentale des couples est donc la suivante 12 :
(x, y) = (x0 , y0 ) si et seulement si x = x0 ∧ y = y0 . (15)
Le produit cartésien de deux ensembles A et B est, par définition,
A × B := {(a, b) : a ∈ A ∧ b ∈ B}.
Plus généralement, on peut considérer des n-uples : le n-uple de composantes x1 , . . . , xn
se note (x1 , . . . , xn ). La propriété fondamentale associée est la suivante 13 :
(x1 , . . . , xn ) = (x10 , . . . , xn0 ) si et seulement si (x1 = x10 ) ∧ · · · ∧ (xn = xn0 ). (16)
De manière analogue à ce qui a été fait ci-dessus, le produit cartésien de n ensembles
A1 , . . . , An est :
n 
A1 × · · · × An = ∏ Ai := (a1 , . . . , an ) : (a1 ∈ A1 ) ∧ · · · ∧ (an ∈ An ) .
i=1
Lorsque tous les Ai sont égaux, on emploie l’abréviation :
n
An := A
| × ·{z
· · × A} = ∏ A.
n fois i=1

Exercice 2. Prouvez que {({A) = A.

Exercice 3. Montrez que les identités {(A ∩ B) = {A ∪ {B et {(A ∪ B) = {A ∩ {B dé-
coulent des lois de Morgan.
12. On peut définir les couples en termes d’ensembles par (x, y) := {{x}, {x, y}} (cette définition est
due à Kuratowski). On peut montrer (essayez !) que cette définition vérifie (15). Dans la suite cependant,
c’est uniquement la propriété (15) qui nous intéressera et non comment (x, y) est défini.
13. On peut définir les n-uples de
manière récursive pour tout n > 1 en posant (x1 ) := x1 et
(x1 , . . . , xn , xn+1 ) := (x1 , . . . , xn ), xn+1 . Cependant, comme précédemment, seule la propriété (16) des
n-uples est utile, pas leur construction.

19
2.2 Relations

Tous les jours, sans même nous en rendre compte, nous faisons usage de relations.
Lorsque par exemple nous disons qu’une pomme est bonne, nous mettons en relation
l’objet « pomme » et le qualificatif « bon ». Quand nous disons qu’une voiture con-
somme plus qu’une autre, nous mettons en relation deux voitures en comparant leurs
consommations. On voit donc que notre discours est parsemé de relations. En fait, si
on y regarde de près, plus que les objets eux-mêmes, ce sont les relations qui sont por-
teuses de sens. Il en est de même en mathématique où les relations sont omniprésentes
sous une multitude de formes. Donnons d’abord une définition précise de la notion de
relation.
Remarquons pour commencer qu’une relation définit un lien entre deux objets de type
connu. Par exemple, si on s’intéresse à la relation « le fruit x peut prendre la couleur y »,
il faut que x désigne un fruit et y une couleur. Il n’est pas question de prendre pour x ou
y une automobile ! Si on désigne par A l’ensemble des fruits et par B l’ensemble des
couleurs, la relation ci-dessus lie des x ∈ A avec des y ∈ B. Notons cette relation R(x, y).
Plus précisément, on dit que R(x, y) est vrai si x ∈ A peut prendre la couleur y ∈ B et
faux sinon. Essayez d’inventer d’autres ensembles A et B et des relations entre eux.
Pour que la définition englobe la variété des possibilités, elle ne peut imposer aucune
règle de construction des relations. Tout ce qu’on peut dire d’une relation dans ce cas
est qu’elle fait la distinction entre les paires d’éléments x et y qui sont liées et celles
qui ne le sont pas. De manière équivalente, on peut dire qu’une relation est la donnée
des couples (x, y) ∈ A × B tels que x et y sont liés, les couples restant étant forcément
ceux pour lesquels x et y ne sont pas en relation. Or, se donner un ensemble de (x, y),
ce n’est rien d’autre que de se donner un sous ensemble de A × B. On a donc,
Définition 3. Une relation entre deux ensembles A et B est la donnée d’un sous-
ensemble R de A × B. On notera souvent R(x, y) au lieu de (x, y) ∈ R.
Lorsqu’une relation R a lieu entre A et lui-même (R ⊂ A × A), on dit que R est une
relation sur A.
Donnons quelques exemples.
Sur un ensemble quelconque A, on a la relation d’égalité qui est donnée par le sous-
ensemble diagonal ∆ := {(x, x) : x ∈ A} de A × A. On utilise la notation x = y au
lieu de (x, y) ∈ ∆.
Sur Z, on a la relation « x est le successeur de y » qui est définie par l’ensemble
{(y + 1, y) : y ∈ Z}.
Si M est un ensemble de magasins et P un ensemble de produits, il est naturel de
considérer la relation R(x, y) donnée par « le magasin x ∈ M possède le produit
y ∈ P ».
Sur N, on a la relation « x divise y » définie par {(x, y) : y = qx pour un certain
q ∈ N}. En général, on emploie la notation x | y pour dire que (x, y) appartient à cet

20
 ensemble.
Si C[X] désigne l’ensemble des polynômes en une variable X à coefficients com-
plexes, la relation naturelle « z est une racine de P » est donnée par {(z, P) ∈
C × C[X] : P(z) = 0}.
Une relation R ⊂ A × B peut se représenter de manière graphique : on déploie 14 sur
une ligne horizontale les éléments de A, sur une ligne verticale les éléments de B, et
on noircit le point de coordonnées (a, b) si et seulement si (a, b) ∈ R (voir Fig. 6). Par

(a, b)
b R

a A
F IGURE 6 – Représentation graphique d’une relation

exemple, pour la relation « x ∈ N divise y ∈ N » vue plus haut, nous avons esquissé à
la figure 7 le début du graphe associé.
Jusqu’à présent, nous avons parlé des des relations entre les éléments de deux ensem-
bles, c’est pourquoi nous les appellerons plus spécifiquement relations binaires. Bien
entendu, rien ne nous limite à de telles relations : nous pouvons considérer des relations
entre n ensembles. La définition suivante possède cette généralité.
Définition 4. Soit n un naturel. Une relation n-aire est un n + 1-uple d’ensembles
(R, A1 , . . . , An ) tel que R ⊂ A1 × · · · × An . Souvent on note R(a1 , . . . , an ) au lieu de
(a1 , . . . , an ) ∈ R.

Donnons quelques explications. Cette définition insiste sur le fait qu’une relation n’est
pas seulement un ensemble R de n-uples « sélectionnés » mais inclut les ensembles
A1 , . . . , An sur lesquels cette relation a lieu. Dans la pratique, ces ensembles sont sou-
vent implicitement donnés et on parle, abusivement, de la relation R au lieu de la rela-
tion (R, A1 , . . . , An ). Comme exemple, considérons les relations R := {(x, y) ∈ N2 : x >
1 et y > 2} et R0 := {(x, y) ∈ Z2 : x > 1 et y > 2}. Celles-ci sont différentes car, bien
14. Lorsque les ensembles A et B ne jouissent pas d’une relation d’ordre naturelle — au contraire de
N, Q et R — on dispose leurs éléments le long des lignes comme on le désire.

21
 y

0
0 1 2 3 4 5 6 x
F IGURE 7 – Relation « x divise y »

que R = R0 , on a implicitement que la première est (R, N, N) et la seconde (R0 , Z, Z).

Insistons également sur le fait qu’une relation n’est pas une formule. En effet, les rela-
tions R := {(x, y, z) ∈ R3 : x + y = z} et R0 := {(x, y, z) ∈ Z3 : x + y = z} sont différentes
bien qu’elles soient toutes deux définies par « x + y = z ».
Une relation unaire (1-aire) sur un ensemble A est simplement une partie de cet en-
semble : R ⊂ A. On peut alors voir R(x) comme une proposition dont la vérité dépend
de x ∈ A ; les propositions considérées précédemment étaient vraies ou fausses, R(x)
est vraie lorsque x ∈ R et fausse sinon.
Terminons par quelques exemples :
la relation unaire « n est une puissance de 2 » est donnée par {n ∈ N : n = 2k pour
un certain k ∈ N} ;
la relation unaire « p est un nombre premier » se définit par {p ∈ N : p > 1 et les
seuls diviseurs de p sont 1 et p} ;
la relation quaternaire « q et r sont respectivement le quotient et le reste de la
division de x par y » correspond à l’ensemble R = {(q, r, x, y) ∈ Z4 : x = qy + r avec
0 6 r < y} ;
la relation {(n, y1 , y2 ) ∈ N3 : n = y1 + y2 avec y1 et y2 deux nombres premiers} est
liée à la conjecture de Goldbach (non prouvée à ce jour) qui dit que tout entier pair
n > 4 est somme de deux nombres premiers.

Exercice 4. Si A et B sont deux ensembles, montrer sur le diagramme de Venn quel

est l’ensemble C := {x : x ∈ A ⇔ x ∈ B}.

22
2.3 Fonctions

2.3.1 Définitions

Dans la vie courante le mot « fonction » est souvent employé avec un sens différent de
celui qu’on lui attribue en mathématique. Quand vous affirmez que vous choisissez un
dessert en fonction de votre humeur, vous mettez en relation votre humeur et le choix
d’un dessert. Cependant, rien ne dit qu’une humeur donnée conditionnera un unique
choix de dessert. C’est pourtant cette dernière interprétation qui serait valable si on
avait dit que le choix d’un dessert est une fonction (mathématique) de l’humeur ! De
fait, d’un point de vue mathématique, les fonctions sont des relations particulières :
lorsqu’on dit que y est une fonction de x, cela signifie que y est univoquement déter-
miné par la connaissance de x.
Une autre vision courante des fonctions est celle en termes de « formules ». Par exem-
ple, la fonction f (x) = sin(1/x) est donnée par la formule « sin(1/x) ». Le problème, si
on veut prendre cette vision comme définition est de répondre à la question : qu’est-ce
qu’une formule ? On veut en effet que la notion de fonction soit suffisamment générale
pour être utile. Voici quelques exemples de difficultés :
les fonctions elliptiques sont des solutions d’équations différentielles mais ne sont
pas définissables en termes de fonctions « usuelles » ;
la fonction qui, à une valeur d’entrée x d’un programme informatique, associe le
résultat y du calcul n’est en général pas donné par une simple « formule » (voir la
figure 8 pour illustration) 15 ;

double f(double x1, int x2)

{
double y;

if (x2 <= 0) y = x1
else y = f(3.9 * x1 * (1 - x1), x2 - 1);
return(y);
}

F IGURE 8 – Programme en C calculant une fonction (x1, x2) 7→ y.

la fonction qui à une courbe γ dans R2 (elle-même définie comme une fonction
γ de [0, 1] vers R2 ) associe sa longueur (voir figure 9) englobe plusieurs éléments
déroutants comme un espace de départ complexe et une « formule » qui fait inter-
venir intégrale et dérivée ;
15. En fait, il existe une théorie de la programmation appelée λ -calcul où tout programme s’écrit

23
 
 courbe γ 
 
 γ γ(0)  Z 1q
 
  7−→ L(γ) := γ1 0 (t)2 + γ2 0 (t)2 dt
0
 
 

 γ(1) 

0 1

F IGURE 9 – La fonction « longueur d’une courbe ».

etc.
On le voit, il n’est pas facile d’englober l’ensemble des cas où on aurait envie de parler
de fonction à moins d’abandonner la définition en termes de « formules ». Il faut donc
rechercher une propriété plus « basique » commune aux exemples ci-dessus. En vérité,
comme nous l’avons déjà remarqué au premier paragraphe, l’essence de la notion de la
dépendance fonctionnelle n’est pas tant une expression qui exprime cette dépendance
qu’un comportement déterministe : si y est une fonction de x, dès que x est connu,
y est univoquement déterminé. Tous les exemples que nous avons donnés ont cette
propriété. Remarquons que, pour accommoder des situations telles que « sin(1/x) »
qui n’a pas de sens pour x = 0, nous admettrons qu’à certains x ne corresponde aucun
y.
En résumé, « y est une fonction de x » exprime une relation entre y et x qui a ceci de
particulier qu’à un x donné il n’y a soit aucun soit un seul y qui lui corresponde. Cela
donne lieu à la définition suivante.
Définition 5. Une fonction f est une relation binaire (G, X,Y ) telle que, pour tout
x ∈ X, il existe au plus un y ∈ Y vérifiant (x, y) ∈ G. L’ensemble des x ∈ X pour
lesquels un tel y ∈ Y existe est appelé le domaine de f et est noté Dom f .
Le fait qu’il n’y a qu’un seul y correspondant à x permet d’employer sans ambiguïté la
notation f (x) pour le désigner. Bien sûr f (x) n’est défini que si x ∈ Dom f . Plutôt que
f = (G, X,Y ), on préfère en général écrire 16

f : X ◦→ Y : x 7→ y
uniquement à l’aide de fonctions. Cette manière de procéder à donné lieu aux langages fonctionnels
parmi lesquels on trouve L ISP, ML,...
16. Le symbole « ◦→ » est propre à ces notes. L’usage courant est d’employer « → ». Quant à nous,
nous restreindrons l’usage de « → » au cas où Dom f = X. Autrement dit, « f : X ◦→ Y » est sensé
attirer votre attention sur le fait qu’il est possible que Dom f 6= X, c’est-à-dire que f (x) n’existe pas
pour certains x ∈ X — comme c’est le cas pour le « sin(1/x) » vu plus haut.

24
où y est le seul élément de Y tel que (x, y) ∈ G. L’ensemble G ⊂ X × Y est appelé
le graphe de f . On le note plus communément Graph( f ). Remarquez que, puisque
(x, y) ∈ G est équivalent à y = f (x), on peut aussi écrire (voyez-vous pourquoi ?) :

Graph( f ) = {(x, y) ∈ X ×Y : x ∈ Dom f ∧ y = f (x)}.

La représentation graphique d’une fonction est en fait la représentation graphique de

la relation Graph( f ). Insistons sur le fait que, comme pour les relations, les ensembles
de départ et d’arrivée font partie de la fonction. Ainsi

f : R → R : x 7→ x + 1 et g : Z → Z : x 7→ x + 1

sont deux fonctions différentes bien qu’elles soient définies par la même formule.
Comme on peut le constater à la figure 10, leurs graphes sont également différents.

y y
6 6
5 5
4 4
3 f : R → R : x 7→ x + 1 3 g : Z → Z : x 7→ x + 1
2 2
1 1
0 0
0 1 2 3 4 5 6 x 0 1 2 3 4 5 6 x
F IGURE 10 – Deux fonctions différentes définies par la même formule.

On représente aussi les fonctions par des flèches entre des « patates ». Plus précisé-
ment, pour symboliser f : X ◦→ Y , on trace une patate pour X et une pour Y et, de
chaque 17 x ∈ Dom f ⊂ X, on trace une flèche pointant vers le y ∈ Y correspondant.
Sur la figure 11, la zone grisée dans X est l’ensemble des points de X d’où une flèche
part, c’est-à-dire le domaine de f . La zone grisée de Y est l’ensemble des points de Y
touchés par une flèche. On l’appelle l’image, Im f , de f :

Im f := y ∈ Y : y = f (x) pour un certain x ∈ Dom f .

2.3.2 Injectivité et surjectivité

Deux notions associées à une fonction quelconque f : X ◦→ Y sont importantes et se

rencontrent dans une multitude de situations. Il s’agit de l’injectivité et de la surjectiv-
ité.
17. En général, on ne le fait que pour peu de x afin de ne pas surcharger le dessin qui doit donner une
idée plus qu’une représentation fidèle de f .

25
 f
X ◦−−−−−−−−−−→ Y

x y
Dom f
Im f

F IGURE 11 – Une autre représentation graphique d’une fonction

La surjectivité s’intéresse au fait que Y soit recouvert par les images f (x) lorsque x
varie dans Dom f . Si c’est le cas, la fonction est dite sujective. Le fait que Y soit
recouvert s’exprime également par Im f = Y . On peut aussi voir la surjectivité de f
comme suit : si on prend un y quelconque dans Y , l’équation f (x) = y admet au moins
une solution x ∈ Dom f . En effet, l’existence d’une solution x ∈ Dom f est équivalente
à y ∈ Im f et le fait que cela ait lieu pour tout y ∈ Y veut dire que Y ⊂ Im f ou encore
Y = Im f (puisque de toutes façons Y ⊃ Im f ).
L’injectivité est concernée avec une autre propriété de l’équation y = f (x), à savoir
l’unicité des solutions. En effet, on dira que f est injective si, quel que soit y ∈ Y , il
existe au plus une solution x ∈ Dom f de l’équation f (x) = y. Autrement dit, pour une
fonction injective f , soit l’équation f (x) = y n’a pas de solution (i.e., y ∈ / Im f ), soit
l’équation f (x) = y possède exactement une solution (lorsque y ∈ Im f ). Une troisième
manière d’exprimer la même chose est : s’il y a deux solutions x1 et x2 , elles doivent
être égales. En d’autres mots : si f (x1 ) = f (x2 ), alors x1 = x2 . Cette notion d’injectivité
est à ne pas confondre avec la définition de fonction. être une fonction veut dire qu’à
un x correspond au plus un y. être injectif est l’« inverse » : un y provient au plus d’un
x. Une représentation graphique de cela est esquissée à la figure 12.
f
X Y X ◦−−−−−−→ Y

x1
x y1 y

y2
x2
Pas une fonction Pas injective

F IGURE 12 – être une fonction v.s. être injectif.

En résumé, nous avons

26
Définition 6. Soit f : X ◦→ Y une fonction. On dit que f est injective si une des
propriétés équivalentes suivantes est vraie :
pour tout x1 , x2 ∈ Dom f , si f (x1 ) = f (x2 ) alors x1 = x2 ;
quel que soit y ∈ Y , l’équation f (x) = y admet au plus une solution x ∈ Dom f .

Définition 7. Soit f : X ◦→ Y une fonction. On dit que f est surjective si une des
propriétés équivalentes suivantes est vraie :
pour tout y ∈ Y , il existe au moins un x ∈ Dom f tel que f (x) = y ;
Im f = Y ;
pour tout y ∈ Y , l’équation f (x) = y possède au moins une solution x ∈ Dom f .
Lorsque ces deux définitions sont satisfaites ensemble pour une même fonction, on a
la notion de bijection :
Définition 8. Soit f : X ◦→ Y une fonction. On dit que f est une bijection si f est à
la fois injective et surjective. Lorsqu’une telle bijection f existe et que Dom f = X,
on dit que X et Y sont en bijection par f et on note f : X ∼ = Y ou simplement X ∼=Y
lorsqu’il est clair de quelle fonction f il s’agit.

2.3.3 Restrictions

Comme on l’a vu, une fonction n’est pas seulement une règle d’association mais aussi
la donnée des ensembles de départ et d’arrivée. Par exemple,

f : N → R : x 7→ x2 et g : R → R : x 7→ x2

sont des fonctions différentes. Le fait qu’elles sont définies par la même expression
algébrique implique que
∀x ∈ N, f (x) = g(x).
En fait, f est « la même chose » que g sauf que sont ensemble de départ est plus petit.
Plus précisément, f est la restriction de g à l’ensemble de départ N. Cette idée peut
être appliquée à une fonction quelconque ce qui donne lieu à la définition suivante :

Définition 9. soit f : X ◦→ Y une fonction et A ⊂ X. La restriction de f à l’ensemble

A, notée f A , est la fonction définie par

f A : A ◦→ Y : x 7→ f (x)

avec Dom(FA ) = (Dom f ) ∩ A.

27
2.3.4 Composition et inverses

Jusqu’à présent, nous nous sommes intéressés aux propriétés concernant une seule
fonction. Il est temps de voir comment on peut combiner plusieurs fonctions pour en
créer de nouvelles.
à cet effet, l’opération fondamentale est la composition. Celle-ci est relativement na-
turelle si on voit une fonction comme un « traitement » appliqué à une donnée. Par
exemple, si f : X ◦→ Y est une fonction, on peut penser f (x) comme le résultat d’une
transformation effectuée sur x par f . Il est alors naturel de vouloir ensuite transformer
ce résultat f (x) grâce à une autre fonction, disons g. Ceci est une manière de regarder
les programmes informatiques : on part d’une donnée x fournie au début du programme
et on la transforme successivement par diverses opérations jusqu’à ce qu’on obtienne
le résultat désiré.
Mais revenons à l’aspect mathématique. Transformer f (x) à l’aide de
g s’écrit g f (x) . Pour que cette expression ait un sens, il faut que f (x) appartienne à
l’ensemble de départ de g. Puisqu’on doit avoir cela pour tout x et de manière à ce que
ce soit valable quelle que soit la fonction f de X vers Y , on va demander que l’ensem-
ble de départ de g soit Y — c’est-à-dire l’ensemble d’arrivée de f . En rassemblant ce
qui vient d’être dit, on en arrive à la définition suivante.

Définition 10. Soit f : X ◦→ Y et g : Y ◦→ Z deux fonctions. La composée g ◦ f de g

et f est la fonction définie par


g ◦ f : X ◦→ Z : x 7→ (g ◦ f )(x) := g f (x)

avec Dom(g ◦ f ) = {x ∈ X : x ∈ Dom f ∧ f (x) ∈ Dom g}.

On peut représenter graphiquement cette situation comme suit :

f
X ◦−−−−−→ Y x 7−−−−−→ f (x)
◦−−−−−→

7−−−−−→
◦−

7−−
−−

−−

g◦ f g
−−

−−
−−

−−
→

Z g f (x)

La composition est une opération associative : si f : X ◦→ Y , g : Y ◦→ Z et h : Z ◦→ W

sont trois fonctions, il est facile de vérifier (faites le !) que h ◦ (g ◦ f ) = (h ◦ g) ◦ f . On
pourra donc employer la notation h ◦ g ◦ f sans ambiguïté. L’opération de composi-
tion possède aussi un neutre à droite et à gauche. Pour un ensemble A, définissons la
fonction identité sur A, notée idA ou 1A , par

idA : A → A : x 7→ x.

28
Le domaine de idA est A. Il est aisé (pouvez-vous faire les détails ?) de voir que, si
f : X ◦→ Y est une fonction, alors f ◦ idX = f (neutre à droite) et idY ◦ f = f (neu-
tre à gauche). L’existence d’un neutre amène naturellement à se poser la question de
l’existence d’inverses. Commençons par définir cette notion.

Définition 11. Soient f : X ◦→ Y et g : Y ◦→ X deux fonctions. On dit que g est un

inverse à gauche (resp. à droite) de f si g ◦ f = idX (reps. f ◦ g = idY ).

Notons que les inverses ne sont pas nécessairement uniques. Par exemple, pour f :
{0, 1} → {0, 1, 2} : x 7→ x, les fonctions
 

 0 →
7 0 0 7→ 0

g1 : {0, 1, 2} → {0, 1} : 1 7→ 1 et g2 : {0, 1, 2} → {0, 1} : 1 7→ 1
 
2 7→ 0 2 7→ 1
 

sont deux inverses à gauche de f (vérifiez le !). Pour f : {0, 1, 2} → {0, 1} définie par
f (0) = 0, f (1) = 1 et f (2) = 0, les fonctions
( (
0 7→ 0 0 7→ 2
g1 : {0, 1} → {0, 1, 2} : et g2 : {0, 1} → {0, 1, 2} :
1 7→ 1 1 7→ 1

sont deux inverses à droite. L’existence d’inverses est liée aux propriétés d’injectivité
et de surjectivité vues plus haut. Voici le résultat.

Proposition 12. Soit f : X ◦→ Y une fonction.

1 f possède un inverse à gauche si et seulement si Dom f = X et f est injective.
2 f possède un inverse à droite si et seulement si f est surjective.

Démonstration. Condition nécessaire pour 1 : Par hypothèse g ◦ f = idX pour un

certain g : Y ◦→ X. Par définition du domaine de la composée de deux fonctions, on
a X = Dom idX = Dom(g ◦ f ) ⊂ Dom f ⊂ X, d’où Dom f = X. Reste à montrer que
f est injective, c’est-à-dire que si f (x1 ) = f (x2 ) pour certains x1 , x2 ∈ Dom f , alors
x1 = x2 . C’est bien le cas car, en appliquant g aux deux membres de f (x1 ) = f (x2 ),
on a g( f (x1 )) = g( f (x2 )) ou encore g ◦ f (x1 ) = g ◦ f (x2 ) et donc, comme g ◦ f = idX ,
x1 = idX (x1 ) = idX (x2 ) = x2 .
Condition suffisante pour 1 : On suppose ici que Dom f = X et que f est injective et
on veut construire un inverse à gauche g : Y ◦→ X. Définissons g par

g : Y ◦→ X : y 7→ x tel que f (x) = y

avec Dom g = Im f . C’est bien une fonction car l’injectivité de f implique l’unicité
du x correspondant à un y donné. Le domaine de g est bien Im f car un tel x existe si

29
et seulement si y ∈ Im f . Resta à montrer que g ◦ f = idX , c’est-à-dire que, pour tout
ξ ∈ X, g( f (ξ )) = ξ . Mais, par définition de g,

g( f (ξ )) = x tel que f (x) = f (ξ ).

Comme ξ est un tel x (et que celui-ci est unique), on a g( f (ξ )) = ξ .

Condition nécessaire pour 2 : Supposons que f ◦ g = idY pour un certain g : Y ◦→ X
et montrons que f est surjective, c’est-à-dire que, quel que soit y ∈ Y , on peut trouver
un x ∈ Dom f tel que f (x) = y. Soit donc y ∈ Y . Prenons x := g(y). Celui-ci est bien
défini car, comme on l’a vu précédemment, f ◦ g = idY implique que Dom g = Y . De
plus x ∈ Dom f . En effet, puisque y ∈ Y = Dom( f ◦ g), par définition de ce dernier,
on a g(y) ∈ Dom f . Reste à voir que f (x) = y. En remplaçant x par sa définition,
f (x) = f (g(y)) = f ◦ g(y) = idY (y) = y, ce qui termine l’argument.
Condition suffisante pour 2 : On suppose maintenant que f est surjective et on veut
construire une fonction g : Y ◦→ X telle que f ◦ g = idY . Définissons g par

g : Y → X : y 7→ un x choisi dans {ξ ∈ Dom f : f (ξ ) = y}.

Ceci fait de g une fonction car, même s’il y a plusieurs ξ tels que f (ξ ) = y, il est dit
qu’il faut en choisir (comme bon vous semble) l’un d’entre eux et que c’est celui-là
qui sera l’unique image de y. Le domaine de g est bien Y grâce à la surjectivité. Il
faut voir que f ◦ g = idY , c’est-à-dire que f (g(y)) = y pour tout y ∈ Y . Soit un y ∈ Y .
Par définition, g(y) est un ξ tel que f (ξ ) = y. Donc f (g(y)) = y. Ceci conclut la
preuve.

En mettant les points 1 et 2 de cette proposition ensemble et au vu de la définition 8,

on a immédiatement le corollaire suivant.

Corollaire 13. Soit f : X ◦→ Y une fonction. f possède une inverse à gauche et à droite
si et seulement si f est un isomorphisme d’ensembles.

Il est à noter que dans le cas où f est un isomorphisme, l’inverse à droite et à gauche
sont les mêmes et sont uniques. Il sont les mêmes car si g ◦ f =∈X et f ◦ h =∈Y , on a
g = g ◦ idY = g ◦ ( f ◦ h) = (g ◦ f ) ◦ h = idX ◦h = h. Cela implique également l’unicité
car si g1 et g2 sont deux inverses à gauche, l’argument précédent montre g1 = h = g2
(et de même pour les inverses à droite).

2.3.5 Exercices

Exercice 5. Montrez qu’une relation R ⊂ A × B peut être donnée de manière équivalente

comme une fonction ρ : A × B → {0, 1} telle que (a, b) ∈ R ⇔ ρ(a, b) = 1.

30
Exercice 6. Soient X et Y deux ensembles. Les projections de X ×Y sur X et Y respectivement
sont les fonctions prX et prY définies par

prX : X ×Y → X : (x, y) 7→ x et prY : X ×Y → Y : (x, y) 7→ y.

Montrez que ces deux fonctions sont surjectives. Sont-elles injectives ?

Exercice 7. Soit f : X ◦→ Y une fonction. Pour tout A ⊂ X, on définit l’image de A par f

comme
f (A) := { f (x) ∈ Y : x ∈ Dom f et x ∈ A}.
Vérifiez que f (X) = Im f et f (∅) = ∅.
Prouvez que si A1 et A2 sont deux sous-ensembles de X, on a

f (A1 ∪ A2 ) = f (A1 ) ∪ f (A2 )

f (A1 ∩ A2 ) ⊂ f (A1 ) ∩ f (A2 )

Trouvez un contre-exemple (concret) qui montre bien qu’on n’a pas nécessairement l’égal-
ité dans la deuxième affirmation ci-dessus.

Exercice 8. Soit f = (G, X,Y ) une fonction et prX , prY les projections de X × Y sur X et
Y respectivement. Vérifiez algébriquement et graphiquement que Dom f = prX (G) et Im f =
prY (G).

Exercice 9. Soit f : X ◦→ Y une fonction. Pour tout B ⊂ Y , on définit l’image inverse de B par
f comme
f −1 (B) := {x ∈ X : x ∈ Dom f ∧ f (x) ∈ B}.
Vérifiez que f −1 (Y ) = Dom f et f −1 (∅) = ∅.
Prouvez que si B ⊂ Y , alors

f −1 {Y B = {X f −1 (B) .

Prouvez que si B1 et B2 sont deux sous-ensembles de Y , on a

f −1 (B1 ∪ B2 ) = f −1 (B1 ) ∪ f −1 (B2 )

f −1 (B1 ∩ B2 ) = f −1 (B1 ) ∩ f −1 (B2 )

Exercice 10. Soient f : X ◦→ Y et g : Y ◦→ Z deux fonctions. Prouvez que

si f et g sont injectives, il en est de même de g ◦ f : X ◦→ Z ;
si f et g sont surjectives, alors g ◦ f : X ◦→ Z l’est aussi.
si f et g sont bijectives, alors g ◦ f : X ◦→ Z l’est également.

Exercice 11. Notons AB l’ensemble des fonctions de B vers A. Prouvez que les fonctions
suivantes sont des bijections.
{0, 1}A → P(A) : f 7→ {x ∈ A : f (x) = 1} ;

31
 AB × AC → AB∪C : ( f , g) 7→ f ∪ g où
(
f (x) si x ∈ B
f ∪ g : B ∪C → A : x 7→
g(x) si x ∈ C

et B, C sont deux ensembles disjoints (B ∩C = ∅) ;

(AB )C → AB×C : f : C → AB 7→ B ×C → A : (x, y) 7→ f (y)(x) ;

AC × BC → (A × B)C : ( f , g) 7→ C → A × B : x 7→ ( f (x), g(x)) (cet isomorphisme dit sim-

plement qu’une fonction h à valeurs dans un produit A × B est la donnée de deux fonctions
à valeurs dans A et B respectivement qu’on appelle les composantes de h).

2.4 Ensembles de nombres

Les ensembles avec lesquels on travaille le plus fréquemment sont des ensembles de
nombres ou des ensembles construits à partir de ceux-ci. Plus précisément, il s’agit de
N, l’ensemble des naturels ;
Z, l’ensemble des entiers ;
Q, l’ensemble des rationnels ;
R, l’ensemble des nombres réels.
Ces quatre ensembles devraient vous avoir été présentés durant vos études secondaires.
Si ce n’est pas le cas ou si vous avez des hésitations, il est impératif d’y remédier au
plus vite. Cette section devrait vous y aider. Cependant, si les explications sont trop
succinctes, n’hésitez pas à demander de l’aide.

2.4.1 Les nombres naturels

Commençons par parler de N, l’ensemble des naturels. Il est composé des nombres 0,
1, 2, 3, 4,... Ce nombres sont ceux que nous utilisons naturellement 18 pour compter.
Pouvoir dénombrer un nombre quelconque d’objets signifie que si l’on en ajoute un,
c’est encore possible. Autrement dit, l’essence même du comptage est de pouvoir faire
« plus un ». Cela veut dire que les nombres naturels, i.e., les éléments de N, sont tous
ceux et uniquement ceux qu’on peut obtenir à partir de zéro en répétant un certain
nombre de fois l’opération « +1 ». à titre d’illustration, constatons que 1 = 0 + 1,
2 = 1 + 1 = (0 + 1) + 1, etc. Une manière plus abstraite mais extrêmement utile de dire
que tous les naturels ne sont que la répétition de l’opération « +1 » à partir de zéro est
le concept de preuve par récurrence. Supposons que nous ayons une propriété P(n)
18. En vérité, le zéro a pris beaucoup de temps pour être reconnu à sa juste valeur et se répandre. Le
zéro est indispensable à notre manière d’écrire les nombres et à la facilité de calcul qui en résulte. Si
vous n’êtes pas convaincus, essayez de calculer en utilisant les chiffres romains...

32
qui dépende de n ∈ N. Pour prouver que P(n) est vrai quel que soit n ∈ N, il faut et
il suffit que P(0) soit vrai et que, sous l’hypothèse P(n), P(n + 1) le soit aussi. Plus
formellement, on a
Axiome (Preuve par récurrence). Soit P une propriété sur N (i.e., P ⊂ N) telle que
P(0) est vrai ;
pour tout n ∈ N, P(n) ⇒ P(n + 1) est vrai.
Alors, pour tout n ∈ N, P(n) est vrai.
Intuitivement, cet axiome est valable car
P(0) est vrai ;
P(0) et P(0) ⇒ P(1) sont tous deux vrais, d’où on déduit que P(1) doit être vrai
(voyez-vous pourquoi ?) ;
P(1) et P(1) ⇒ P(2) sont vrais et donc aussi P(2) ;
de même pour P(3), P(4),...
Les mêmes idées sous-tendent les définitions par récurrence. Techniquement, cela s’-
exprime comme suit :
Axiome (Définition par récurrence). Soit X, Y deux ensembles et f0 : X → Y , F :
N × X ×Y → Y deux fonctions. L’axiome affirme qu’alors il existe une et une seule
fonction f : N × X → Y telle que
f (0, x) = f0 (x) pour tout x ∈ X ;


f (n + 1, x) = F n, x, f (n, x) pour tout n ∈ N et x ∈ X.

La deuxième équation peut paraître paradoxale : elle définit f en termes de f lui-

même alors qu’on ne le connaît pas ! En vérité, elle définit f en n + 1 en fonction de
f en n et, comme chaque naturel n’est que 0 + 1 + 1 + · · · + 1, en utilisant de manière
répétitive cette équation, on arrivera au cas n = 0 que l’on connaît. Pour illustrer cette
idée mettons-la en pratique pour de petits nombres naturels :


f (1, x) = f (0 + 1, x) = F 0, x, f (0, x) = F(0, x, f0 (x)) ;


f (2, x) = f (1 + 1, x) = F 1,
x, f (1, x) et en utilisant le premier calcul, on a
f (2, x) = F 1, x, F(0, x, f0 (x)) ;


f (3, x) = f (2 + 1, x) = F 2, x, f (2, x) et on peut de nouveau utiliser les calculs
ci-dessus pour exprimer f (3, x) en fonction des f0 et F qui sont connus ;
on peut continuer de la sorte avec f (4, x), etc.
Cette manière de définir des fonctions par récurrence peut être généralisée à bien
d’autres structures discrètes que les entiers et est un des concepts clefs de l’infor-
matique moderne.

33
Afin de voir les définitions par récurrence à l’œuvre, employons-les pour définir les
fonctions f (x, y) = x + y et g(x, y) = x · y à partir de l’opération de base « +1 » sur les
naturels :
(
f (0, y) = y
(17)
f (x + 1, y) = f (x, y) + 1
(
g(0, y) = 0

(18)
g(x + 1, y) = g(x, y) + y = f g(x, y), y

Remarquez que les équations ci-dessus ne sont qu’une version stylisée de propriétés
que vous connaissez bien. Pour l’addition, il s’agit juste de l’identité (x + 1) + y =
(x + y) + 1. Pour la multiplication, de

x·y = y+y+···+y,
| {z }
x fois

on tire que (x + 1) · y = x · y + y (voyez-vous pourquoi ?). Une autre manière d’ap-

préhender ceci est de constater que cela découle de la règle de distributivité de la
multiplication sur l’addition : (α + β ) · γ = α · γ + β · γ. Les équations (17) et (18)
ne sont donc que l’expression d’identités que nous connaissons intuitivement sur les
opérations d’addition et de multiplication.
à l’inverse maintenant, si nous prenons (17) et (18) comme définitions de l’addition et
de la multiplication respectivement, il devrait être possible de prouver les propriétés
que nous tenons intuitivement pour vraies (ou alors ces définitions sont « mauvaises »).
C’est bien le cas : on peut établir l’associativité, la commutativité,... de l’addition et de
la multiplication grâce à des preuves par récurrence (voir les exercices 12 et 13). Dans
le même ordre d’idées, on peut définir la fonction exponentielle (x, y) 7→ xy , la relation
d’ordre x 6 y, etc. (voir les exercices 14 et 16).

2.4.2 Les nombres entiers

2.4.3 Les nombres rationnels

(Ces deux sections apparaîtront dans une version ultérieure de ces notes.)

2.4.4 Exercices

Exercice 12. Considérons la fonction f : N × N → N définie par (17). Bien qu’intuitivement

on sait que f (x, y) = x + y, ici on veut définir x + y comme f (x, y) — il n’est donc pas question
d’utiliser des propriétés intuitives de l’addition, il faut tout montrer à partir de (17). Prouvez
par récurrence sur x que

34



1 f f (x, y), z = f x, f (y, z) pour tous les x, y, z ∈ N ;
2 f (x, 0) = x pour tout x ∈ N ;
3 f (x, y + 1) = f (x, y) + 1 pour tous les x, y ∈ N ;
4 f (x, y) = f (y, x) pour tous les x, y ∈ N — utilisez les identités précédentes !
R EMARQUE : Si on note x+y au lieu de f (x, y), on voit que (1) est l’associativité de l’addition :
(x + y) + z = x + (y + z) ; (2) montre que zéro est un neutre à droite (l’est-il à gauche ?) ; et (4)
est la commutativité de l’addition : x + y = y + x.
Exercice 13. Soit g : N × N → N la fonction définie récursivement par l’équation (18). Prouvez
— en général par récurrence sur x — que
1 g(x, 0) = 0 pour tout x ∈ N.
2 g(1, y) = y pour tout y ∈ N.
3 g(x, 1) = x pour tout x ∈ N.
4 g(x + z, y) = g(x, y) + g(z, y) pour tous les x, y, z ∈ N.
5 g(x, y + 1) = g(x, y) + x pour tout x, y ∈ N.
6 g(x, y) = g(y, x) pour tous les x, y ∈ N.



7 g g(x, y), z = g x, g(y, z) pour tous les x, y, z ∈ N.
Vous pouvez bien entendu utiliser les résultats de l’exercice 12. Si on définit x · y := g(x, y),
traduisez les propriétés ci-dessus et dites comment elles se nomment.
Exercice 14. Soit h : N × N → N la fonction définie par
(
h(0, y) = 1
h(x + 1, y) = h(x, y) · y

Couramment, on emploie la notation yx au lieu de h(x, y). Prouvez à partir de la définition

ci-dessus que les identités suivantes sont correctes :
x1 = x ;
xy+z = xy · xz ;
(xy )z = xy·z .
Exercice 15. Prouvez par récurrence que, quel que soit x ∈ N, ou bien x = 0, ou bien il existe
un et un seul y ∈ N tel que y + 1 = x. I NDICATION : considérez la fonction f : N → N définie
par f (0) = 0 et f (x + 1) = x.
Exercice 16. Définissons la fonction f : N × N → N par
(
f (0, y) = f0 (y)


f (x + 1, y) = F x, y, f (x, y)

où ( (
1 si y = 0 1 si z = 1 ou x = y + 1
f0 (y) := et F(x, y, z) :=
0 si y 6= 0 0 sinon
Définissons x 6 y comme une abréviation pour f (x, y) = 1. Prouvez par récurrence que

35
 x 6 x+1;
x 6 x;
x 6 y si et seulement si ∃z ∈ N, y = x + z.
De cette dernière propriété, concluez que 6 est
transitive : si x 6 y et y 6 z, alors x 6 z ;
antisymétrique : si x 6 y et y 6 x, alors x = y.
I NDICATION : utilisez des arguments similaires à ceux de l’exercice 15 pour montrer que
x 7→ x + 1 est injective et déduisez-en que, pour tout k ∈ N, x 7→ x + k l’est également (voir
exercice 10).

3 Logique du premier ordre

Dans les pages précédentes, nous avons rencontré à diverses reprises des expressions
telles que « quel que soit... », « pour chaque... », « pour certains... », « il existe... », etc.
Ces constructions sont extrêmement importantes en mathématique et en informatique.
Pour cette raison, certains symboles ont étés créés afin de les abréger. Il s’agit de
« ∀ » qui représente « pour tout », « quel que soit... »,... et
« ∃ » qui se lit « il existe » mais remplace aussi « pour un certain »,...
Il s’agit de bien comprendre que ce ne sont que des symboles et qu’une suite de sym-
boles ne signifie pas forcément quelque chose. Pour bien les utiliser, il faut comprendre
leur sens — lire une phrase à haute voix peut vous y aider.
Pour employer à bon escient « ∀ » et « ∃ », examinons dans quel type de phrase
ils sont utilisés. Par exemple, on peut dire : quel que soit le naturel n, n 6 2n. Cette
phrase possède la structure suivante : quel que soit un objet une propriété dépendant
de cet objet est vraie. Comme nous l’avons fait ci-dessus, on désigne généralement
l’objet par une lettre (ci-avant n) qui est appelée une variable. En symboles, la phrase
s’écrit ∀n ∈ N, n 6 2n ou, si le contexte rend implicite que n ∈ N, on peut l’abréger
en ∀n, n 6 2n. La propriété sur N, n 6 2n est particulière. Plus généralement, étant
donné une propriété P qui dépend d’une variable x — ce qu’on représente par P(x) —
on peut écrire
∀x, P(x)
ce qui signifie que P(x) est vrai quel que soit x. Si on veut préciser qu’on ne considère
que les x appartenant à un ensemble X, on écrit

∀x ∈ X, P(x).

36
Il est à noter que, techniquement, cette formule est une abréviation de ∀x, x ∈ X ⇒
P(x). De même, les constructions permises avec « ∃ » sont du type

∃x, P(x)

ce qui signifie qu’il existe au moins un x tel que P(x) soit vrai ou, de manière équiva-
lente, que P(x) est vrai pour un certain x. De nouveau, si on veut dire que le x dont on
affirme l’existence se trouve dans un ensemble X, on écrit

∃x ∈ X, P(x).

Ici, cette formule est une abréviation de ∃x, x ∈ X ∧ P(x).

Insistons sur le fait qu’il est important de comprendre que ces phrases symboliques
n’ont rien de mystérieux. Il s’agit simplement d’écritures condensées de phrases françaises.
En principe donc, votre compréhension de la langue française devrait suffire... Comme
cependant l’expérience montre que ce n’est pas le cas, nous allons nous attarder un peu
sur deux situations omniprésentes dans la pratique :
l’utilisation d’une phrase avec quantificateurs dont on sait qu’elle est vraie et
la preuve de la véracité d’une telle formule.

3.1 Le quantificateur universel

3.1.1 Utilisation

Supposons que l’on soit en possession d’une formule ∀x, P(x) dont on sache qu’elle
est vraie. En d’autres termes on sait que P(x) est vrai peu importe la valeur que l’on
donne à x. Ainsi la manière d’utiliser ceci dans un argument est de donner des valeurs
particulières à x. Par exemple, si x peut prendre des valeurs entières, on pourra dire
« ... en prenant x = 24 dans ∀x, P(x), on déduit que P(24) est vrai... ». Il n’est pas
nécessaire bien sûr de prendre des x « concrets » tels 24. Par exemple, si on a un g qui
donne des x en fonction d’une autre variable u, x = g(u), on peut affirmer : « ... grâce
à ∀x, P(x) avec x = g(u), on a que ∀u, P(g(u))... ». L’essence même de l’utilisation
du quantificateur universel est donc de substituer certaines valeurs à la variable sur
laquelle on quantifie pour obtenir la vérité de la proposition qui suit le quantificateur
pour ces valeurs particulières.

3.1.2 Preuve

Qu’en est-il maintenant si nous devons établir qu’un proposition du type ∀x, P(x)
est vraie ? Cela revient à établir que P(x) est vrai quelle que soit la valeur que x peut

37
prendre. Pour ce faire, nous prenons un x arbitraire, sans aucune restriction sur ses
valeurs possibles, et nous cherchons à produire un argument général (qui dépend de x
mais marche dans tous les cas de figure) qui montre P(x). Dans la pratique, le fait de
se donner un x arbitraire est souvent écrit sous la forme « Soit x » que l’on rencontre
à loisir dans les textes mathématiques. Il est important de comprendre que, puisqu’on
veut construire un argument qui fonctionne quelle que soit la valeur particulière que x
peut prendre,
on doit laisser x sous forme de lettre de manière justement à pouvoir plus tard
remplacer cette lettre par la valeur qui nous intéresse (comme nous l’avons expliqué
dans la première partie de cette section) ;
il n’est pas question de ne vérifier P(x) que pour certains exemples de x — en effet,
un nombre même élevé d’exemples 19 ne peut couvrir l’infinité de valeurs possibles
qu’en général x peut prendre.

3.2 Le quantificateur existentiel

Nous allons maintenant examiner les deux mêmes questions pour les propositions du
type ∃x, P(x).

3.2.1 Utilisation

Premièrement, supposons que nous sachions que la formule ∃x, P(x) soit vraie et
que nous voulions l’utiliser dans un argument. Tout ce que la formule ∃x, P(x) nous
dit c’est que P(x) est vrai pour au moins un x. Dans la pratique, on dit par exemple
« ... prenons un x tel que P(x)... » et on continue l’argumentation avec ce x. Il faut bien
comprendre qu’on ne sait à priori rien d’autre sur x que le fait qu’il satisfasse P(x). Le
plus souvent, on ne peut déterminer sa valeur précise (ou elle ne nous est pas donnée).
On doit donc le laisser sous forme de lettre. Les déductions ultérieures qui font appel
à x se basent donc sur le fait que P est vrai en x.
19. Avant l’invention du « calcul symbolique », les mathématiciens faisaient leurs preuves sur des ex-
emples. Cependant, il faut réaliser que le but n’était pas de résoudre le problème dans un cas particulier
mais d’offrir une solution générale en employant le cas particulier comme véhicule des idées — à dé-
faut d’avoir la notion de variable pour le faire explicitement. C’était donc difficile à lire puisqu’il fallait
par soi-même inférer les principes généraux à partir de l’exemple. Aujourd’hui, si on veut prouver que
quelque chose est vrai pour n’importe quel objet, on ne fait plus la démonstration en donnant des valeurs
particulières à l’objet mais on le symbolise par une lettre... Cette qualité d’abstraction symbolique est
également au cœur de l’informatique où un programme doit résoudre une classe de problèmes dont une
instanciation particulière est décrite par des valeurs données aux variables d’entrée.

38
3.2.2 Preuve

La deuxième situation est celle où l’on veut établir qu’une formule du type ∃x, P(x)
est vraie. Il faut donc maintenant montrer qu’on peut trouver un x qui satisfait P.
Argumenter qu’il est plausible qu’un tel x existe ne suffit pas, il faut en exhiber ex-
plicitement 20 un et prouver que celui-ci vérifie la propriété P. Souvent bien sûr, il y a
plusieurs x possibles — la loi du moindre effort voulant qu’on recherche le plus sim-
ple possible ! D’autre part, ce x dépend en général d’autres variables y, z, t,... On ne
recherche donc pas, sauf dans des cas simples, une valeur « concrète » de x comme
x = 1 mais plutôt une manière de construire x en fonction des valeurs des autres vari-
ables (en distinguant différents cas de figure si nécessaire, etc.).

3.3 Exemples

Après avoir expliqué les principes généraux de manipulation des quantificateurs,

voyons-les à l’œuvre sur quelques exemples.
Considérons la formule ∀x ∈ R, x2 + x + 1 > 0. Comment prouver 21 qu’elle est vraie ?
Une preuve pourrait être écrite comme suit :
Soit x ∈ R. On doit montrer que x2 + x + 1 > 0. Puisque x2 + x + 1 = (x +
1/2)2 + 3/4 et qu’un carré est toujours > 0, on en déduit que x2 + x + 1 >
3/4 > 0.
Remarquez qu’on n’a pas vérifié l’inégalité x2 + x + 1 > 0 sur des exemples. Ceci a sa
place dans une investigation préliminaire afin d’explorer un peu le problème mais pas
dans une preuve. En effet, quelques exemples ne peuvent en aucun cas épuiser l’infinité
des nombres réels. En fait, se baser uniquement sur des exemples sans en comprendre
le mécanisme peut mener à penser qu’une propriété est exacte alors que ce n’est pas
vrai.
Prenons maintenant un exemple avec un quantificateur existentiel : ∃x ∈ R, x2 − 2x +
1 = 0. Pour prouver que c’est vrai, il faut exhiber un tel x. On pourrait donc donner
l’argument :
Il suffit de prendre x = 1. En effet, en remplaçant x par 1 dans x2 = 2x + 1
on constate que c’est bien égal à zéro.
20. Ceci est valable lorsqu’on cherche à faire une démonstration directe de ∃x, P(x). Nous verrons à
la section 3.4 une autre manière de procéder qui consiste à supposer qu’on ne peut trouver de tel x et à
en dériver une contradiction.
21. Nous ne nous intéresserons pas ici aux moyens d’avoir une idée de la vérité ou de la fausseté
d’une proposition et ainsi de la manière de la prouver ou de la contredire. Ce que nous voulons mettre
en évidence ici est la structure des arguments qui transforment ces arguments en preuves solides.

39
Ici on a pu présenter un x concret (à savoir 1) car la proposition est fort simple. Il suffit
de modifier un peu l’énoncé pour que ce ne soit plus possible. C’est le cas par exemple
pour ∃x ∈ R, ex = −x. Montrer que cette dernière propriété est vraie est bien plus
difficile et demande des procédés de construction qui font partie du cours d’analyse
mathématique. Vous pouvez cependant être convaincus que c’est le cas en traçant les
graphes des fonctions R → R : x 7→ x et R → R : x 7→ ex et en constatant qu’ils ont un
point d’intersection (voyez-vous où est le x cherché ?).
Terminons par un exemple qui fait intervenir plusieurs quantificateurs dans une même
proposition. Comment fait-on pour montrer que
∀b, c ∈ R, ∃R ∈ R, ∀x ∈ R, −x2 + bx + c 6 R (19)
est vrai ? Intéressons nous d’abord à la structure de la preuve avant de la faire en
détail. Cette structure résulte juste des principes précédents. En effet, (19) est de la
forme ∀b, c ∈ R, P(b, c) et, par conséquent, la preuve commencera par « Soit b et c
deux nombres réels. » suivi d’un argument qui montrera P(b, c) — sans imposer de
restriction sur b et c. Comme P(b, c) est de la forme ∃R ∈ R, Q(b, c, R), pour prouver
P(b, c), il faudra exhiber un R. Ce R pourra bien entendu dépendre de b et c. Ensuite,
une fois ce R déterminé, il faudra montrer qu’il satisfait ∀x ∈ R, −x2 + bx + c 6 R.
Pour résumer, la forme de la preuve sera
Soit c, b ∈ R.
On donne une valeur (bien choisie) à R qui dépendra en général de b et c.
Soit x ∈ R.
Un argument montre que −x2 + bx + c 6 R — en conséquence du bon choix
de R.
En voici une rédaction complète :
Soit b, c ∈ R. Choisissons R := 14 b2 +c. Il faut montrer que −x2 +bx+c 6 R
quel que soit x ∈ R. Soit x ∈ R. On a
 b 2 b2 b2
−x2 + bx + c = − x − + + c 6 + c = R,
2 4 4
ce qui termine la preuve.
Il est important que R puisse dépendre de b et c. Si une telle dépendance n’était pas
permise, on aurait écrit ∃R ∈ R, ∀b, c ∈ R, ∀x ∈ R, −x2 + bx + c 6 R (noter la per-
mutation des deux quantificateurs). Cette dernière proposition est fausse. (Une inter-
prétation graphique des propositions ci-dessus peut aider à comprendre comment nous
avons trouvé les arguments que nous avons présentés.)
Comme ces exemples le montrent, il est possible de se poser beaucoup de questions
à propos d’une simple inégalité du type −x2 + bx + c 6 R. Ces questions sont ex-
primées par la manière dont les quantificateurs précèdent l’égalité. Il est donc impor-
tant, lorsqu’on a à justifier une proposition, que l’articulation du raisonnement soit
clairement en relation avec l’ordre des quantificateurs.

40
3.4 Négation et preuves par l’absurde

Quelle est la négation de ∀x, P(x) ? Autrement dit, quand ∀x, P(x) est-il faux ? Puisque
∀x, P(x) dit que P(x) est vrai pour tout x, cela sera faux dès qu’un x ne satisfait pas
P, ou encore, s’il existe (au moins) un x tel que ¬P(x) soit vrai. Un résumé de la
discussion précédente en symboles donne


¬ ∀x, P(x) ' ∃x, ¬P(x). (20)

On peut refaire un raisonnement similaire pour la négation de ∃x, P(x). En effet, s’il
est faux qu’on ne peut trouver de x qui satisfasse P(x), cela veut dire que P(x) ne peut
jamais être satisfait pour aucun x, ou encore que ¬P(x) est vrai quel que soit x. La
traduction de ceci en symboles donne


¬ ∃x, P(x) ' ∀x, ¬P(x). (21)

On peut aussi prendre une route différente pour montrer (21) et l’obtenir comme con-
séquence de (20).
Supposons donc que (20) soit vrai quel que soit P et montrons
que ¬ ∃x, Q(x) ' ∀x, ¬Q(x) (nous avons pris la lettre Q au lieu de P pour dis-
tinguer plus facilement

(21) de (20)). En considérant (20) avec P := ¬Q, on obtient
¬ ∀x, ¬Q(x) ' ∃x, ¬¬Q(x). Maintenant, en prenant la négation des deux membres
de cette équivalence (qui restent donc équivalents) et en utilisant le fait que ¬¬R ' R
quelle que soit la proposition R, on obtient (pouvez-vous justifier en détail ?)


∀x, ¬Q(x) ' ¬¬ ∀x, ¬Q(x)


' ¬ ∃x, ¬¬Q(x)


' ¬ ∃x, Q(x)

ce qui est l’équivalence recherchée.

Appliquons ce que nous venons d’établir aux preuves par l’absurde. Nous avons vu à
la section 1.4 (page 10) qu’une preuve par l’absurde consiste à supposer que les hy-
pothèses H sont vraies, que (malgré cela) la thèse T est fausse — i.e., ¬T est vrai — et
à en déduire une contradiction. Puisque nous savons maintenant nier des propositions
contenant des quantificateurs, nous pouvons aussi prouver par l’absurde des thèses en
contenant. Il en va de même des preuves par contraposition.
Faisons un exemple pour illustrer cela. Nous allons montrer que


∀x ∈ R, (∀ε ∈ R, ε > 0 ⇒ |x| 6 ε) ⇒ x = 0 .

Voici comment on pourrait en rédiger une preuve par contraposition :

41
 Soit x ∈ R. Au lieu de montrer (∀ε > 0, |x| 6 ε) ⇒ x = 0, nous allons
montrer sa contraposée, à savoir ¬(x = 0) ⇒ ¬(∀ε > 0, |x| 6 ε) ou encore

x 6= 0 ⇒ (∃ε > 0, |x| > ε).

Supposons donc que x 6= 0. Il faut exhiber un ε > 0 qui satisfasse |x| > ε.
Prenons ε := |x|/2. Puisque x 6= 0, on a bien que ε > 0. De plus, de nouveau
parce que x 6= 0, |x| > |x|/2 = ε, ce qui termine l’argument.

3.5 Application aux bases de données

Si la lecture de ces quelques notes ne vous a pas convaincu que la logique a non seule-
ment une grande importance en mathématique mais a également des connections avec
d’autres disciplines, voici un dernier exemple. 22
De nombreux problèmes pratiques requièrent le stockage et l’analyse efficace d’une
quantité importante de données. Par exemple, on peut imaginer que la police a besoin
de savoir, à partir de la plaque d’une voiture, sa marque et son propriétaire. Si l’on avait
à organiser ces choses sur papier, on le ferait naturellement dans un tableau tel que le
tableau 15. D’un point de vue mathématique, ce tableau décrit un ensemble d’éléments

Plaque Marque Propriétaire

XTC-157 Opel Vectra Pol Lenoir
CRT-143 Mitsubishi Space Star Élodie Detor
RTE-666 Mercedes Rob Vilain
.. .. ..
. . .
TABLE 15 – Organisation de données

en relation. Si on appelle D1 l’ensemble des plaques, D2 l’ensemble des marques et

D3 l’ensemble des propriétaires, ce tableau donne l’ensemble des triplets en relation,
c’est-à-dire qu’il décrit une relation R ⊂ D1 × D2 × D3 . Par exemple, la première ligne
dit que (XTC-157, Opel Vectra, Pol Lenoir) ∈ R.
Ainsi la théorie des bases de données organise ses informations en relations. Diverses
notions qu’on y rencontre ne sont que des reformulations de concepts vus précédem-
ment. Par exemple, la première colonne de la table 15 sera appelée une clé car il ne
peut exister deux triplets dont la valeur dans la première colonne (la plaque) est la
même mais celle des autres colonnes diffèrent. Cela ne veut rien dire d’autre que le
fait que la projection pr1 : D1 × D2 × D3 → D1 : (v1 , v2 , v3 ) 7→ v1 est injective sur R
22. Vous aurez l’occasion d’approfondir les idées qui suivent dans le cours de Jef Wijsen intitulé
« Fichiers et Bases de Données ».

42
(pouvez-vous faire les détails ?). Comme on sait qu’une fonction injective admet un
inverse à droite, il existe une fonction

f : D1 ◦→ D2 × D3 avec Dom f = pr1 (R)

telle que, pour tout v1 ∈ Dom f , (v1 , f (v1 )) ∈ R. Cette application donne juste les at-
tributs v2 et v3 correspondant à un v1 . En bases de données, on développe aussi une
manière de calculer avec les relations qu’on appelle l’« algèbre relationnelle » et qui
se reformule directement en termes des opérations ensemblistes vues ci-avant.
Par ailleurs, lorsqu’on a des données, on souhaite également pouvoir les explorer, c’est-
à-dire poser des questions à leur sujet. Par exemple, l’ensemble des voitures que Pol
Lenoir possède est donné par

(v1 , v2 ) : (v1 , v2 , Pol Lenoir) ∈ R .

Si on veut savoir combien de personnes possèdent au moins deux voitures, il suffit de

regarder le nombre d’éléments de l’ensemble

v3 ∈ D3 : ∃v1 , v2 , v01 , v02 , v1 6= v01 ∧ (v1 , v2 , v3 ) ∈ R ∧ (v01 , v02 , v3 ) ∈ R .



Si nous avons une autre relation A(w1 , w2 ) exprimant le fait que la voiture de plaque w1
a eu un accident à la date w2 , on peut se demander quels sont les conducteurs qui n’ont
jamais fait d’accident (avec aucune de leurs voitures). L’ensemble de ces conducteurs
est donné par (voyez-vous pourquoi ?) :


v3 ∈ D3 : ∀v1 , v2 , R(v1 , v2 , v3 ) ⇒ ∀t, ¬A(v1 ,t) .

Comme ces exemples le mettent en évidence, les questions, encore appelées requêtes,
à une base de données s’expriment naturellement par des formules avec des quantifi-
cateurs où les relations qui peuvent y figurer sont celles qui sont présentes dans la base
de données.
Bien que l’aperçu des bases de données que nous avons présenté ici soit essentielle-
ment théorique, il faut savoir que ces principes sont implémentés dans toutes les bases
de données modernes.
Ainsi, une bonne compréhension de la logique et de la théorie des ensembles vous sera
d’une grande aide pour aborder une multitude d’autres sujets.

43