Langues

• English
• Français

Introduction aux mathématiques

• Partie I : Présentation, plan et motivations
• Partie II : Bases de la logique mathématique
• Partie III : Éléments de la théorie des ensembles
• Partie IV : Relations, applications et suites
• Partie V : Domaines majeurs des mathématiques

Partie II : Bases de la logique mathématique

Contents
Contents
 1.  Introduction
 2.  Propositions
 3.  Tables de vérité
 4.  Connecteurs logiques
 5.  Tautologies et antilogies
 6.  Suffisance et nécessité
 7.  Prédicats et quantificateurs
 8.  Méthodes de démonstration
 9.  Récapitulatif

1. Introduction

Dans ce document nous allons présenter les éléments de base de la logique mathématique : les propositions, les connecteurs logiques et les quantificateurs. Ensuite nous discuterons des méthodes principales de démonstration. Aucun prérequis n’est nécessaire : ceci est une introduction intuitive et que nous espérons accessible aux lecteurices avec pas ou peu de connaissances en maths. Une exception est le concept de nombres entiers que nous utiliserons dans certains exemples.

Le but de ce document est d’introduire le vocabulaire principal, les notations et les notions élémentaires de la logique mathématique.

Auront une réponse les questions suivantes : Qu’est-ce qu’une proposition ? Comment construit-on des propositions ? Comment sait-on si une proposition est vraie ?

2. Propositions

Les maths, comme la plupart des sciences, tentent d’établir des assertions, c’est-à-dire, des énoncés qui sont vérifiés dans le contexte dans lequel ils sont donnés. Ici, ce que nous voulons dire par énoncé est n’importe quelle phrase grammaticalement correcte dans un langage donné, que ce soit du français ou un autre langage naturel ou encore un langage formel. En logique mathématique classique, nous travaillons avec un type spécial d’énoncés : les propositions. Par définition, une proposition est un énoncé auquel on peut associer exactement une valeur de vérité : soit vrai, soit faux. En d’autres termes, une proposition décrit quelque chose qui est soit vrai, soit faux et il n’y a pas de troisième option.

Parmi les exemples de propositions exprimées en français on peut citer “Il pleut dehors” ou encore “Pierre ne sera pas là à la soirée”. Cependant, puisque beaucoup de nuances et, surtout, beaucoup d’ambiguïtés naissent lorsqu’on s’exprime en langages naturels comme le français, nous ferons le choix d’utiliser un langage spécialisé pour parler de maths. Ce langage appartient à la catégorie des “langages formels”. On pourrait par exemple débattre à propos du premier exemple donné s’il s’agit bien d’une proposition : en effet, “dehors” n’étant pas défini de manière précise, on pourrait dire qu’il existe un autre endroit qui peut être qualifié également comme étant “dehors” où il ne pleut pas. Ainsi nous arriverions à la conclusion qu’à la fois il pleut et qu’il ne pleut pas “dehors” ce qui entrerait en contradiction avec la définition de proposition. Pour éviter ce genre de problème, nous nous restreindrons aux concepts que nous aurons explicitement définis d’une manière non ambiguë, à l’aide d’un langage formel par exemple. Des propositions exprimées dans un langage plus mathématique pourraient être “$1 = 1$” ou encore “$1 = 2$”. Le langage formel en lui-même ne sera pas défini de manière extensive dans ce document.

Comme il est de coutume en maths, afin de pouvoir étudier ce nouveau concept, nous allons introduire des “variables” qui feront référence à des propositions, mais de manière à ce que la nature de la proposition en elle-même disparaisse face à cette abstraction : nous appelerons variable propositionnelle tout symbole (tels que $P$, $Q$, $R$…) que nous pourrions remplacer par n’importe quelle proposition.

3. Tables de vérité

Introduisons à présent un outil bien pratique : les tables de vérité. Elles décrivent les valeurs de vérité (“vrai” ou “faux”) d’une proposition $Q$ selon les valeurs de vérité d’un ensemble fixé de $n$ autres propositions $P_1, \ldots, P_n$. À gauche, nous listerons toutes les combinaisons possibles de valeurs de vérité pour les $n$ propositions $P_1, \ldots, P_n$ (à raison d’une combinaison par ligne). À droite, pour chaque ligne, on indiquera la valeur de vérité que prend la proposition $Q$ lorsqu’on suppose que les propositions $P_1, \ldots, P_n$ prennent les valeurs de vérité inscrites sur la même ligne.

Considérons l’exemple suivant :

\[ \begin{array}{|c|c||c|}\hline \text{“Il pleut dehors”} & \text{“Alice a un parapluie”} & \text{“Alice est mouillée”} \\\hline\hline Faux & Faux & Faux \\\hline Faux & Vrai & Faux \\\hline Vrai & Faux & Vrai \\\hline Vrai & Vrai & Faux \\\hline \end{array} \]

Ici, il y a $n = 2$ propositions : $P_1$ est “Il pleut dehors” et $P_2$ est “Alice a un parapluie”. La proposition $Q$ est “Alice est mouillée”.

Chaque ligne doit se lire de la manière suivante (où $V_1$, $V_2$ et $V$ sont des valeurs de vérité) : si $P_1$ est $V_1$ et $P_2$ est $V_2$, alors $Q$ est $V$. Par exemple, pour la troisième ligne on lirait : si “Il pleut dehors” est vraie et “Alice a un parapluie” est fausse alors “Alice est mouillée” est vraie.

Cependant, cet exemple n’est pas vraiment satisfaisant car on pourrait faire plusieurs remarques comme quoi cette table de vérité ne reflète pas la réalité. Par exemple, Alice pourrait être en train de prendre une douche et donc être mouillée sans qu’il pleuve nécessairement dehors. En d’autres termes, cela signifierait que la proposition $Q$ dépend d’autres propositions qui ne se trouvent pas parmi $P_1$ et $P_2$. Cela étant dit, on fera confiance à lae lecteurice pour comprendre que cet exemple a été donné simplement pour aider notre intuition à propos des tables de vérité. En pratique, nous utiliserions notre langage mathématique et nos définitions non ambiguës pour surmonter ces obstacles.

Il est facile de généraliser l’idée des tables de vérité pour décrire les valeurs de vérité à un nombre $m$ arbitraire de propositions $Q_1, \ldots, Q_m$ selon les valeurs de vérité des $n$ propositions $P_1, \ldots, P_n$. En effet, il suffit d’ajouter des colonnes à droite dans la table pour chaque nouvelle proposition $Q_i$ et indiquer la valeur de vérité qu’elle prend pour chaque ligne selon les valeurs de vérité des propositions $P_1, \ldots, P_n$ sur cette même ligne.

4. Connecteurs logiques

Un connecteur logique (ou opérateur logique) peut être défini intuitivement comme le “procédé” à appliquer sur une ou plusieurs propositions pour retourner une nouvelle proposition dont la valeur de vérité sera déterminée par celles des propositions en question. Si le connecteur s’applique sur une seule proposition, on parle de connecteur unaire ; s’il s’applique sur deux propositions, on dit qu’il est binaire. Un exemple d’un tel connecteur logique binaire en français est le mot “et” : étant donné deux propositions exprimées en français, par exemple “Il pleut dehors” et “Pierre ne sera pas là à la soirée”, on peut construire un nouvel énoncé “Il pleut dehors et Pierre ne sera pas là à la soirée” qui s’avère être lui-même une proposition. Cela étant dit, nous ne nous intéresserons pas aux connecteurs logiques en français, mais bien à des connecteurs pour notre langage mathématique.

Les tables de vérité sont un outil formidable pour décrire les valeurs de vérité des propositions construites par moyen de connecteurs logiques d’une manière évidente et non ambiguë. Cela est dû au fait que la valeur de vérité de la nouvelle proposition est complètement déterminée par celles des propositions préexistantes sur lesquelles on applique le connecteur logique.

Soient $P$ et $Q$ deux variables propositionnelles.

Il est important de noter qu’établir que l’implication $P \Rightarrow Q$ est vraie ne signifie pas nécessairement qu’il y a un lien de cause à effet entre $P$ et $Q$. En effet, considérons les propositions “$1 = 2$” et “Le ciel est bleu”. L’implication [“$1 = 2$” $\Rightarrow$ “Le ciel est bleu”] est vraie (car $1 = 2$ est fausse) alors qu’il n’y pas de lien entre $1$ d’être égal à $2$ et le ciel d’être bleu. De manière similaire, l’implication [“$1 = 1$” $\Rightarrow$ “Le ciel est bleu”] est vraie (car les deux propositions sont vraies) mais il n’y pas de causalité entre $1$ d’être égal à lui-même et le ciel d’être bleu.

En pratique, si $A$ et $B$ sont des propositions équivalentes, alors toutes les occurrences de $A$ peuvent être remplacées par $B$ en conservant le sens de ce qui est affirmé : en ce sens, l’équivalence logique joue le rôle de la relation “d’égalité” pour les propositions logiques.

Nous sommes à présent dans la capacité de combiner des propositions préexistantes pour en former de nouvelles. Maintenant, comment savoir qu’une proposition donnée est vraie ou fausse ?

Avant de répondre à cette question il y a une différence importante sur laquelle nous voudrions insister : la différence entre une proposition “atomique” et une proposition “composée”. Une proposition atomique est une proposition dans laquelle aucun connecteur logique n’apparaît (par exemple, $1 = 2$) alors qu’une proposition composée est construite à partir d’autres propositions mises en relation au moyen de connecteurs logiques. (e.g. “$(1 = 1) \lor (1 = 2)$”). La différence que nous souhaitons mettre en lumière est la suivante : démontrer qu’une proposition atomique est vraie revient à montrer que le contenu de la proposition est vérifié ; alors que démontrer qu’une proposition composée est vraie revient à montrer que la relation exprimée par le connecteur logique est bien vérifiée. Par exemple, soit $P$ et $Q$ des variables propositionnelles. Montrer que $Q$ est vraie signifie montrer que ce qu’elle affirme est vrai. Maintenant, montrer que $P \Rightarrow Q$ est vraie consiste à montrer que si $P$ est vraie alors $Q$ est vraie : l’accent ici est mis sur la relation entre $P$ et $Q$ et non pas sur le contenu de ces propositions. Ainsi, montrer qu’une implication $P \Rightarrow Q$ est vraie ne nécessite pas de connaître si la proposition $P$ est en réalité vraie ou non mais exprime que s’il advenait qu’elle l’était, alors $Q$ serait également vraie. Cela veut dire que nous pouvons établir les conséquences d’une proposition sans savoir si cette proposition est vraie. Ceci est particulièrement utile lorsqu’aucune démonstration n’est connue pour une proposition ; de telles propositions sont ce qu’on appelle en maths des “problèmes ouverts”.

5. Tautologies et antilogies

Une tautologie est une proposition $Q$ dont la valeur de vérité est toujours vraie ($V$) indépendamment de n’importe quelle autre proposition. En d’autres termes, cela signifie que la colonne pour la proposition $Q$ dans une table de vérité est remplie de $V$, et ce, peu importe quelles sont les propositions $P_1, \ldots, P_n$ que l’on considère.

Exemple : Un exemple d’une telle tautologie est “$A \Leftrightarrow A$ où $A$ est une variable propositionnelle. En effet, si on dresse la table de vérité en fonction de la proposition $A$, on obtient : \[ \begin{array}{|c||c|c|}\hline A & A & A \Leftrightarrow A \\\hline\hline F & F & V \\\hline V & V & V \\\hline \end{array} \]

Pour de telles propositions, aucune démonstration (autre que simplement dresser la table de vérité et remarquer en effet qu’il s’agit d’une tautologie) n’est requise pour affimer qu’elles sont vérifiées, puisqu’elles le sont toujours.

Naturellement, il existe ce qu’on appelle des antilogies : des propositions qui sont toujours fausses ($F$).

Exemple : Par exemple $A \land \neg A$, où $A$ est une variable propositionnelle, est une antilogie puisque sa table de vérité est donnée par : \[ \begin{array}{|c||c|c|}\hline A & \neg A & A \land \neg A \\\hline\hline F & V & F \\\hline V & F & F \\\hline \end{array} \]

De nouveau, aucune démonstration supplémentaire n’est nécessaire pour montrer que ces propositions sont en effet fausses.

Pour des propositions qui ne sont ni des tautologies ni des antilogies, une démonstration est requise pour montrer qu’elles sont vraies ou fausses. Nous allons parler des différentes façons de construire de telles démonstrations dans la suite de ce document.

Pour l’instant, listons des propositions notables pour lesquelles l’on peut montrer qu’il s’agit de tautologies. Lae lecteurice est invité’e à dresser les tables de vérité pour se convaincre qu’en effet ce sont bien des tautologies. Nous utiliserons des parenthèses pour éviter les ambiguïtés (les opérations suivent la règle de profondeur dans les parenthèses : l’opération la plus profondément entre parenthèses est la première à être appliquée et ainsi de suite). Soit $A$ et $B$ des variables propositionnelles :

1. $\fP{A \Leftrightarrow B} \Leftrightarrow \fP{\fP{A \Rightarrow B} \land \fP{B \Rightarrow A}}$ : montrer une équivalence logique revient à montrer une double implication, une dans chaque sens.

2. $\fP{A \Rightarrow B} \Leftrightarrow \fP{\neg B \Rightarrow \neg A}$ : cette proposition à droite est appelée contraposée de celle à gauche. Montrer qu’une est vraie (respectivement fausse) revient exactement à montrer que l’autre est vraie (respectivement fausse).

3. $A \Leftrightarrow \neg (\neg A)$ : La négation de la négation d’une proposition à la même valeur de vérité que la proposition originale.

4. $A \lor \neg A$ : étant donné une proposition $A$, la proposition $A$ ou sa négation est vraie

5. $\neg(A \land \neg A)$ : étant donné une proposition $A$, $A$ et sa négation ne peuvent jamais être vraies (ou fausses) en même temps. En utilisant l’item précédent, on arrive à la conclusion que, pour toute proposition $A$, exactement un seul des cas suivants est vérifié : ou bien $A$ est vraie ou bien $\neg A$ est vraie. Ainsi, montrer que $A$ est vraie revient exactement à montrer que sa négation $\neg A$ est fausse et vice versa.

6. $\neg(A \lor B) \Leftrightarrow (\neg A \land \neg B)$ and $\neg(A \land B) \Leftrightarrow (\neg A \lor \neg B)$ : on appelle ces tautologies lois de De Morgan. Elles expriment la dualité entre les connecteurs $\land$ et $\lor$ lorsque l’on considère leurs négations.

Exercice : Montrer que les propriétés suivantes sur $\lor$ et $\land$ sont des tautologies :

\[ \begin{array}{ccc} A \Leftrightarrow (A \land A) && A \Leftrightarrow (A \lor A) \\ (A \land B) \Leftrightarrow (B \land A) && (A \lor B) \Leftrightarrow (B \lor A) \\ ((A \land B) \land C) \Leftrightarrow (A \land (B \land C)) && ((A \lor B) \lor C) \Leftrightarrow (A \lor (B \lor C)) \\ (A \land (B \lor C)) \Leftrightarrow ((A \land B) \lor (A \land C)) && (A \lor (B \land C)) \Leftrightarrow ((A \lor B) \land (A \lor C)) \\ \end{array} \]

La troisième de ces tautologies dans chaque colonne signifie que l’ordre dans lequel se font les opérations logiques n’impacte pas la valeur de vérité de la proposition. Ainsi, on peut définir sans ambiguïté la disjonction et conjonction pour n’importe quel nombre $n$ arbitraire de variables propositionnelles $\DOTS{A_1, A_2}{A_n}$ :

\begin{align*} \bigvee_{k = 1}^{n} A_k &\overset{\mathrm{def}}{\SSI} A_1 \lor A_2 \lor \cdots \lor A_n & \bigwedge_{k = 1}^{n} A_k &\overset{\mathrm{def}}{\SSI} A_1 \land A_2 \land \cdots \land A_n \end{align*}

(Ici le symbole $\overset{\mathrm{def}}{\Leftrightarrow}$ signifie que le membre de gauche dans l’équivalence est défini comme une “abbréviation” du membre de droite.)

Exercice : Montrer que les propriétés suivantes de l’implication logique sont des tautologies :

\[ \begin{array}{ccc} A \Rightarrow A && ((A \Rightarrow B) \land (B \Rightarrow C)) \Rightarrow (A \Rightarrow C) \\ (A \Rightarrow B) \Leftrightarrow (\neg A \lor B) && \neg(A \Rightarrow B) \Leftrightarrow (A \land \neg B) \\ (A \Rightarrow B) \Rightarrow ((A \land C) \Rightarrow B) && (A \Rightarrow B) \Rightarrow (A \Rightarrow (B \lor C)) \\ (A \Rightarrow (B \Rightarrow C)) \Leftrightarrow ((A \land B) \Rightarrow C) && (A \Rightarrow (B \Rightarrow C)) \Leftrightarrow ((A \Rightarrow B) \Rightarrow (A \Rightarrow C)) \\ \end{array} \]

Exercice : Montrer que les propriétés suivantes de l’équivalence logique sont des tautologies :

\[ \begin{array}{ccc} (A \Leftrightarrow B) \Leftrightarrow (B \Leftrightarrow A) && ((A \Leftrightarrow B) \land (B \Leftrightarrow C)) \Rightarrow (A \Leftrightarrow C) \\ (A \Leftrightarrow B) \Leftrightarrow (\neg A \Leftrightarrow \neg B) && \neg(A \Leftrightarrow B) \Leftrightarrow ((A \land \neg B) \lor (\neg A \land B)) \\ \end{array} \]

6. Suffisance et nécessité

Introduisons à présent du vocabulaire. Supposons que nous avons établi que la proposition $P \Rightarrow Q$ est vraie, où $P$ et $Q$ sont des variables propositionnelles. Alors, en français, on dirait que $P$ est une condition suffisante pour $Q$ ou, de manière équivalente, que $Q$ est une condition nécessaire pour $P$. On parle de condition suffisante car il suffit que $P$ soit vraie pour affirmer que $Q$ est vraie. On parle de condition nécessaire car pour que $P$ soit vraie il faut que $Q$ soit vraie ou, en d’autres termes, par contraposition, il suffit que $Q$ soit fausse pour que $P$ soit également fausse. Si $P \Rightarrow Q$ est vraie, on dit que $P$ est une condition plus forte que $Q$ ou, de manière équivalente, que $Q$ est une condition plus faible que $P$. On appelle aussi la proposition $P$ l’hypothèse et la proposition $Q$ la conclusion.

Une autre manière d’exprimer en français que cette l’implication $P \Rightarrow Q$ est vraie est de dire : $Q$ si $P$, ou, de manière équivalente, $P$ seulement s} $Q$. De même, on peut dire pour que $Q$ soit vraie il suffit que $P$ soit vraie, ou encore, pour que $P$ soit vraie il faut que $Q$ soit vraie. Ainsi, comme nous avons déjà établi que les propositions $(P \Leftrightarrow Q)$ et $((P \Rightarrow Q) \land (Q \Rightarrow P))$ sont équivalentes, cela signifie que la proposition $P \Leftrightarrow Q$ peut se lire : $P$ si et seulement si $Q$, souvent abrégée en $P$ ssi $Q$. D’autres manières d’exprimer que $P$ et $Q$ sont équivalentes sont de dire que $P$ est caractérisée par $Q$ (et vice versa), ou de dire que $P$ est une condition nécessaire et suffisante pour $Q$ (et vice versa), ou encore de dire que, pour que $P$ soit vraie, il faut et il suffit que $Q$ soit vraie (et vice versa).

Enfin, la proposition $Q \Rightarrow P$ est appelée réciproque de la proposition $P \Rightarrow Q$. C’est souvent qu’après avoir démontré que la proposition $P \Rightarrow Q$ est vraie nous nous demandions si sa réciproque $Q \Rightarrow P$ est également vraie. Si tel est le cas, alors on conclut que $P$ et $Q$ sont équivalentes (ce qui est une affirmation plus forte que simplement dire que $P \Rightarrow Q$ est vraie).

7. Prédicats et quantificateurs

Des variables peuvent entrer en jeu dans une phrase : ce sont des symboles qui peuvent être remplacés par des valeurs constantes prises dans une certaine collection d’éléments. Par exemple, dans l’énoncé “$x = 2$”, le symbole $x$ joue le rôle de variable et peut être remplacé par n’importe quel nombre. On peut distinguer deux classes de variables : les variables libres et les variables muettes (ou variables liées).

Les variables muettes sont le résultat d’une application de ce que l’on appelle un mutificateur. En un certain sens, les variables muettes sont “déclarées” par ce mutificateur et l’entièreté de leur signification est restreinte à ce mutificateur. Parmi ces mutificateurs, on peut citer les quantificateurs que nous allons introduire plus tard dans ce document. Une propriété importante de ce type de variables est que, si l’on remplace toutes les occurrences du symbole représentant la variable par un autre symbole (qui n’apparaît pas déjà dans l’expression), alors le sens de la phrase restera inchangé. C’est ce qui les différencie des variables libres : ce sont les symboles de variables tels que, si toutes leurs occurrences venaient à être remplacées par un autre symbole qui n’apparaît pas déjà dans l’expression, alors l’énoncé n’affirmerait plus la même chose. Par exemple, soit $x$ et $y$ deux nombres, considérons l’énoncé “$x = 2$”. Sa signification est que la variable dénotée par $x$ prend la valeur constante $2$. On affirme que $x$ est ici une variable libre. En effet, si nous changions le symbole $x$ par un autre symbole, disons $y$, on obtiendrait un nouvel énoncé “$y = 2$” qui ne voudra pas dire la même chose que l’énoncé initial (puisque dire que $y$ est égal à $2$ ne nous informe en aucun cas de la possible valeur de $x$). Notons qu’ici les seules variables en jeu ($x$ et $y$) sont des variables libres. Cependant, une expression peut très bien consister d’un mélange de variables muettes et libres.

Une restriction contraignante des propositions est qu’aucune variable libre n’est autorisée à apparaître. En d’autres termes, les propositions décrivent des énoncés constants qui ne dépendent d’aucune entité externe. Par exemple, “$x$ est un nombre pair” ne peut pas être considéré comme une proposition car $x$ représente ici une variable et n’a donc pas une valeur fixe. Les énoncés dans lesquels apparaissent des variables libres et auxquels exactement une valeur de vérité (vrai ou faux) peut être associée si on remplaçait toutes les variables par des valeurs constantes sont appelés prédicats. Ils peuvent être vus comme des “propositions incomplètes” dans lesquelles des symboles de variables interviennent.

La notation que nous allons introduire dans ce paragraphe n’est pas conventionnelle mais elle permet d’éviter une ambiguïté avec la notation du paragraphe suivant. Si $P$ est un prédicat et $x_1, \ldots, x_n$ sont des variables, alors on écrit $P[x_1, \ldots, x_n]$ pour indiquer que les variables libres du prédicat $P$ sont parmi $x_1, \ldots, x_n$ (insistons sur le fait que les variables libres de $P$ sont parmi $x_1, \ldots, x_n$ mais cela ne signifie pas que les variables $x_1, \ldots, x_n$ sont forcément libres dans $P$). Par exemple, considérons le prédicat $P$ donné par “$x^2 = 2$”. On pourra alors écrire $P[x]$ car $P$ a une seule variable libre, à savoir $x$. Si $y$ n’apparaît pas déjà dans $P$, on pourrait également écrire $P[x, y]$ parce que les variables libres de $P$ (ici dans notre cas, $x$) sont bien parmi $x$ et $y$. Cependant, nous ne pouvons pas écrire $P[y]$ car la variable libre $x$ de $P$ n’est pas $y$. De même, nous ne pouvons pas écrire $P[y, z]$, etc. Dans les documents de cette série, nous utiliserons en général seulement des prédicats qui dépendent d’au plus une variable libre, afin éviter des notations trop lourdes qui rendent la lecture compliquée. La plupart des résultats peuvent facilement se généraliser pour n’importe quel nombre de variables libres.

Pour que l’on puisse associer une valeur de vérité à un prédicat, il faut le “transformer” en une proposition : les variables libres doivent être remplacées par des valeurs constantes. Par exemple l’énoncé “$x$ est un nombre pair” où $x$ est indéterminé ne peut pas être associé à une valeur de vérité, tandis que “$2$ est un nombre pair” où on a remplacé $x$ par la constante $2$ est bien une proposition et admet donc une valeur de vérité. La collection de toutes les valeurs constantes que nous pouvons utiliser pour remplacer des variables libres est appelée univers de discours. Il contient toutes les valeurs possibles des variables libres. Supposons maintenant que nous avons un prédicat $P[x]$ avec $x$ une variable libre de $P$. Pour indiquer que l’on remplace la variable libre $x$ par une valeur constante, disons $a$, nous écrivons $P(a)$ : il s’agit donc d’une proposition car la variable libre a été remplacée par une valeur constante.

Une autre manière d’associer une valeur de vérité à un prédicat consiste à transformer les variables libres en variables muettes à l’aide de mutificateurs comme par exemple les quantificateurs. Il existe deux quantificateurs :

• le quantificateur universel, écrit $\forall$, lire “pour tout”,
• le quantificateur existentiel, écrit $\exists$, lire “il existe”.

Si $P[x]$ est un prédicat, alors on peut construire une proposition à l’aide de chacun des quantificateurs qui transforment la variable libre $x$ en variable muette :

• “$\forall x, P(x)$” est une proposition dont la valeur de vérité est vraie si, et seulement si la proposition $P(a)$ est vraie pour n’importe quelle valeur constante $a$ prise dans l’univers de discours.
• “$\exists x, P(x)$” est une proposition dont la valeur de vérité est vraie si, et seulement s’il existe une valeur constante $a$ dans l’univers de discours pour laquelle $P(a)$ est une proposition vérifiée.

La notation $P(x)$ ici est à comprendre comme la substitution de la variable $x$ par chacune des valeurs constantes prises dans une collection de valeurs qui dépend du mutificateur. Pour les quantificateurs, cette collection est l’univers de discours. Pour les autres mutificateurs, la collection est donnée explicitement.

On peut construire des propositions plus complexes en plaçant successivement des quantificateurs. Par exemple on peut écrire la proposition $\forall x, \exists y, x = 2y$.

Il est d’importance capitale de bien remarquer que l’ordre dans lequel apparaissent les quantificateurs affecte grandement le sens de la proposition. Par exemple, considérons que l’univers de discours est un sous-ensemble des nombres rationnels : les nombres qui peuvent s’exprimer comme une fraction de deux nombres entiers.

• La proposition $\forall x, \exists y, x = 2y$ signifie que pour n’importe quel $x$ dans l’univers de discours on peut trouver un élément $y$ de l’univers de discours tel que $x = 2y$. Si on suppose que l’univers de discours comprend un nombre rationnel $x_0$ non nul, alors cela implique que l’univers de discours contient une infinité de nombres puisque $x_0$ étant dans l’univers de discours implique que $\frac{x_0}{2}$ l’est également, puis $\frac{x_0}{4}$ aussi, et ainsi de suite.
• Considérons à présent la proposition $\exists y, \forall x, x = 2y$. Elle signifie qu’il existe un nombre rationnel $y$ dans l’univers de discours tel que tous les nombres rationnels de l’univers de discours est égal à $2y$. Cela implique que l’univers de discours ou bien se résume à seulement $0$ ou bien est vide. En effet, si l’on suppose qu’il y a un nombre rationnel $x_0$ non nul dans l’univers de discours, alors $x_0 = 2y$ donc $y$ est non nul. Mais puisque $y$ est dans l’univers de discours, on a $y = 2y$ ce qui contredit $y$ non nul.

Nous arrivons donc à deux sens radicalement différents juste en intervertissant l’ordre des quantificateurs. La règle générale à suivre est que lorsqu’un quantificateur existentiel $\exists y$ apparaît près un quantificateur universel $\forall x$, l’élément $y$ peut dépendre de la valeur que $x$ prend. Alors que si le quantificateur existentiel $\exists y$ précède le quantificateur universel $\forall x$ alors la valeur de $y$ ne peut pas dépendre des valeurs que prend $x$.

Enfin, remarquons que ces soucis d’ordre des quantificateurs n’ont lieu que lorsque l’on a affaire à un mélange de quantificateurs universels et existentiels : si l’on a seulement des quantificateurs universels (ou seulement existentiels) l’ordre dans lequel ils apparaissent n’importe pas. À présent, considérons un prédicat $P[x]$. Essayons de réfléchir à ce que signifierait prendre la négation de la proposition $\forall x, P(x)$. Cette proposition affirme que pour toutes valeurs $a$ pour la variable $x$ la proposition $P(a)$ est vraie. Affirmer que sa négation est vraie revient à dire que la proposition est fausse. Donc, affirmer que sa négation est vraie signifie qu’il existe une valeur $a$ telle que la proposition $P(a)$ est fausse. En d’autres termes, on a l’équivalence :

\[ \neg (\forall x, P(x)) \SSI (\exists x, \neg P(x)) \]

Réciproquement, par un raisonnement similaire, on peut montrer que :

\[ \neg (\exists x, P(x)) \SSI (\forall x, \neg P(x)) \]

Ce qu’il faut retenir de ces équivalences est que les quantificateurs $\forall$ et $\exists$ peuvent être considérés comme étant la négation l’un de l’autre. De plus, on retiendra que, pour démontrer que la proposition $\forall x, P(x)$ est fausse, il suffit de trouver une valeur $a$ pour $x$ telle que la proposition est fausse : une telle valeur $a$ est appelée contre-exemple.

Exemple : La négation de la proposition “$\forall x, \exists y, x = 2y$” est “$\exists x, \forall y, x \neq 2y$”.

Par défaut, dans l’expression $\exists x, P(x)$, le quantificateur existentiel $\exists$ affirme l’existence d’au moins un élément satisfaisant le prédicat $P[x]$. C’est souvent que l’on souhaite savoir si cet élément est unique, c’est-à-dire que c’est le seul élément qui satisfait le prédicat $P[x]$. Pour indiquer qu’il s’agit en effet de l’unique élément satisfaisant $P[x]$ on utilise la notation spéciale $\exists! x, P(x)$ et on dit que $x$ est caractérisé par $P$.

8. Méthodes de démonstration

Une démonstration formelle (ou preuve formelle) consiste en une succession de propositions telles que chaque proposition est :

• soit un axiome (c’est-à-dire les propositions que l’on accepte comme vraies sans preuves),
• soit une hypothèse (c’est-à-dire les propositions supposées vraies pour la démonstration de ce théorème),
• soit une proposition qui est une conséquence des propositions précédentes selon une règle d’inférence.

La dernière proposition d’une démonstration formelle est appelé théorème.

En pratique, une démonstration est écrite en français (ou dans un autre langage naturel) et justifie en quoi les propositions sont les conséquences des précédentes. Le but d’une démonstration est de convaincre lae lecteurice que les déductions sont en effet bien correctes. Par ailleurs, le mot théorème est réservé aux propositions importantes ; on utilise d’autres noms pour d’autres types de propositions :

• lemme pour une proposition qui est d’utilité dans la démonstration d’une autre proposition mais pas suffisamment importante lorsque l’on sort de ce contexte,
• corollaire pour une proposition qui est une conséquence directe ou un cas particulier d’une certaine proposition,
• ou simplement proposition pour toute autre proposition qui ne rentre pas dans les cas précédents.

Nous nous contenterons d’une seul règle d’inférence : celle appelée “modus ponens”. Elle affirme que, pour toutes propositions $P$ et $Q$, si l’implication $P \Rightarrow Q$ est vraie et que la proposition $P$ est vraie, alors on peut inférer que la proposition $Q$ est également vraie. C’est pour cela que l’implication joue un rôle central dans l’établissement de nouveaux théorèmes. Pour cette raison, nous nous allons dans la suite énoncer des méthodes de démonstration pour les propositions qui se présentent sous la forme d’une implication. Soit $P$ et $Q$ deux propositions. Différentes méthodes de démonstration existent pour montrer que l’implication $P \Rightarrow Q$ est vraie :

• Démonstration directe : on commence par supposer que $P$ est vraie ; ensuite, en utilisant le contenu de la proposition $P$, on montre que $Q$ est nécessairement vraie. La justifictation derrière cette méthode est que : premièrement, l’implication $P \Rightarrow Q$ est toujours vraie si $P$ est fausse donc nous n’avons pas besoin de nous soucier de ce cas. Ensuite, si $P$ est vraie, alors l’implication $P \Rightarrow Q$ n’est vraie que si et seulement si $Q$ est vraie également. Ainsi, si l’on montre que le contenu de $P$, quand supposé vrai, implique que le contenu de $Q$ est également vrai, alors on a montré que le cas $P$ vraie et $Q$ fausse est impossible, et donc que l’implication $P \Rightarrow Q$ est bien vérifiée.

  Exemple : Montrons par une démonstration directe que, pour tout nombre entier $n$, si $n$ est un multiple de $6$ alors c’est un nombre pair. Considérons donc l’univers de discours composé des nombres entiers, nous traduirons mathématiquement cette phrase par l’implication suivante : \[ \forall n \vir \fP{\exists m, n = 6m} \ALORS \fP{\exists k, n = 2k} \] Démonstration : Soit $n$ un nombre entier. Supposons que $n$ est un multiple de $6$. Alors il existe un nombre entier $m$ tel que $n = 6m$. Or, puisque $6 = 2 \times 3$, alors $n = 2 \times (3m)$. Mais puisque $m$ et $3$ sont tous deux des nombres entiers, leur produit $3m$ l’est également. Si l’on pose $k = 3m$ alors on a bien montré qu’il existe un nombre entier tel que $n = 2k$. En conclusion, $n$ est un nombre pair.

• Démonstration par contraposée : On rappelle que la contraposée de $P \Rightarrow Q$ est la proposition $\neg Q \Rightarrow \neg P$ et qu’elles sont logiquement équivalentes. Ainsi, montrer qu’une est vraie (respectivement fausse) est équivalent à montre que l’autre est vraie (respectivement fausse). Pour montrer que la contraposée est vraie, on commence par supposer que $\neg Q$ est vraie (ou, de manière équivalente, que $Q$ est fausse), puis, en utilisant le contenu de la proposition $Q$, on montre que la proposition $P$ est nécessairement fausse (donc $\neg P$ est vraie), ainsi montrant (par une démonstration directe) que l’implication $\neg Q \Rightarrow \neg P$ est bien vraie. Ensuite, par modus ponens, il s’ensuit que $P \Rightarrow Q$ est également vraie.

  Exemple : Montrons par contraposée que si $n$ est un nombre entier et que $n \times n$ est pair, alors $n$ est également pair. Mathématiquement, nous traduisons comme suit, où l’univers de discours sont les nombres entiers : \[ \forall n \vir \fP{n \times n \text{ est pair}} \Rightarrow \fP{n \text{ est pair}} \] Démonstration : Soit $n$ un nombre entier. Supposons que $n$ n’est pas pair. Il est donc impair. Mais le produit de deux nombres impairs est impair. Donc $n \times n$ ne peut pas être pair. Nous avons donc montré que si $n$ n’est pas pair, alors $n \times n$ n’est pas pair non plus. Par contraposée on a bien montré l’implication souhaitée.

• Démonstration par l’absurde : Cette méthode est plus générale que les précédentes en ce sens que l’on peut l’utiliser pour montrer que n’importe quelle proposition est vraie, pas uniquement celles exprimées sous forme d’une implication. Fixons-nous alors l’objectif de montrer que la proposition $P$ est vraie. Pour cela, on commence par supposer que $\neg P$ est vraie (ou, de manière équivalente, que $P$ est fausse). Ensuite, on essaie de montrer que le contenu de $\neg P$ implique une certaine antilogie, que l’on note $R$. On aura ainsi montré que l’implication $\neg P \Rightarrow R$ est vraie. Par contraposée et puisque $P \Leftrightarrow \neg (\neg P)$, on pourra alors affirmer que l’implication $\neg R \Rightarrow P$ est vraie. Mais $R$ est toujours fausse par définition d’une antilogie. Donc sa négation $\neg R$ est une tautologie : elle est toujours vraie. Alors, d’une part on a montré que l’implication $\neg R \Rightarrow P$ est vraie et d’autre part on sait que $\neg R$ est vraie, il s’ensuit grâce à modus ponens que $P$ est vraie. En pratique, l’antilogie $R$ que l’on obtient est souvent de la forme $Q \land \neg Q$ où $Q$ est une certaine proposition que l’on montre être à la fois vraie et fausse. Pour utiliser la méthode de démonstration par l’absurde dans le but de montrer que l’implication $P \Rightarrow Q$ est vraie, on commence par supposer que $P$ est vraie et que $Q$ est fausse, puis on montre que cela implique une certaine antilogie. Ensuite, d’une manière similaire à celle expliquée juste avant, on conclut que $Q$ est vraie et donc que $P \Rightarrow Q$ est vraie.

  Exemple : Montrons que le produit de deux nombres impairs est impair. Fixons l’univers de discours aux nombres entiers. On veut montrer : \[ \forall n, \forall m \vir \fP{\fP{n \text{ impair}} \land \fP{m \text{ impair}}} \Rightarrow \fP{n \times m \text{ est impair}} \] Démonstration : Soient $n$ et $m$ deux nombres entiers. Supposons que $n$ et $m$ sont impairs. Alors il existe deux nombres entiers $a$ et $b$ tels que $n = 2a + 1$ et $m = 2b + 1$. À present supposons que $n \times m$ est pair. Il existe alors un nombre entier $c$ tel que $n \times m = 2c$. Cependant, on calcule $n \times m = (2a + 1)\times(2b + 1) = 4ab + 2(a + b) + 1 = 2(2ab + a + b) + 1$. Or $2ab + a + b$ est un entier, notons-le $d$. Donc on a montré qu’il existe $c$ et $d$ tels que $n \times m = 2c$ et $n \times m = 2d + 1$ ce qui est une contradiction. Par l’absurde, on déduit donc que $n \times m$ est nécessairement impair.

Les exemples de démonstration donnés ci-avant sont très simples donc il est facile de trouver des démonstrations pour chacun d’entre eux en utilisant différentes méthodes. Cependant, pour des problèmes plus complexes, on peut parfois connaître une démonstration suivant une méthode spécifique, par exemple une démonstration par l’absurde, alors qu’aucune démonstration directe ou par contraposée n’est connue. De tels exemples requièrent des connaissances plus avancées en maths donc ne seront pas abordés ici mais cela montre que les différentes méthodes de démonstration offrent des avantages et des inconvénients selon la situation.

Dans les exemples de démonstration donnés ci-avant, nous avons débuté par “Soit $\ldots$”. À chaque fois que l’on veut prouver une proposition qui comprend un quantificateur universel nous devons utiliser une telle expression. Traduire $\forall x$ en “Soit $x$ $\ldots$” transforme la variable $x$ en une valeur constante également notée $x$. Oui cette valeur est arbitraire dans l’univers de discours mais elle est fixée pour le reste de la démonstration et n’est plus à considérer comme une variable.

Similairement, si l’on considère une proposition dans laquelle entre en jeu un quantificateur existentiel, disons par exemple $\exists x, P(x)$, alors la démonstration devra commencer par “Posons $x = \ldots$. Montrons alors que la proposition $P(x)$ est vraie.”.

9. Récapitulatif

Dans ce document, nous avons discuté des notions de proposition et de valeurs de vérité. Nous avons introduit un outil appelé tables de vérité qui nous a permis de décrire explicitement les valeurs de vérité de n’importe quelle proposition par rapport à d’autres propositions.

Nous avons ensuite utilisé les tables de vérité pour définir des connecteurs logiques : ces éléments syntactiques qui s’appliquent sur des propositions préexistantes pour en former une nouvelle dont la valeur de vérité dépendra exclusivement des propositions originales. Nous avons mentionné la négation, la disjonction, la conjonction, l’implication et l’équivalence logiques.

Nous avons parlé de ce que sont les tautologies et les antilogies : ces types de propositions qui sont soit toujours vraies soit toujours fausses. Nous avons ensuite listé certaines tautologies importantes.

Nous avons par la suite introduit du vocabulaire important. Si $P \Rightarrow Q$ est vraie, on peut dire, depuis le point de vue de l’hypothèse $P$ :

• $P$ est une condition suffisante pour $Q$,
• $P$ est plus forte que $Q$,
• $P$ seulement si $Q$,
• pour que $P$ soit vraie, il faut que $Q$ soit vraie,

et depuis le point de vue de la conclusion $Q$ :

• $Q$ est une condition nécessaire pour $P$,
• $Q$ est plus faible que $P$,
• $Q$ si $P$,
• pour que $Q$ soit vraie, il suffit que $P$ soit vraie.

Si $P \Leftrightarrow Q$ est vraie, on dit que $P$ et $Q$ sont équivalentes, que l’une caractérise l’autre, que l’une est une condition nécessaire et suffisante pour l’autre, ou encore que, pour que $P$ soit vraie, il faut et il suffit que $Q$ soit vraie, ou enfin que $P$ si et seulement si $Q$.

Ensuite, nous avons défini les concepts de variables libres et muettes ainsi que les notions d’univers de discours et de prédicats. De plus, nous avons discuté des deux types de quantificateurs : universel et existentiel.

Enfin, nous avons décrit trois méthodes importantes de démonstration : la démonstration directe, la démonstration par contraposée et la démonstration par l’absurde.

Lae lecteurice devrait à présent, on l’espère, être apte à comprendre des démonstrations mathématiques élémentaires et à continuer de construire ses connaissances mathématiques à partir de là.