Assertions

On peut voir le langage mathématique comme un jeu de construction, dont le but est de fabriquer des énoncés vrais. La règle de base de ce jeu est qu'un énoncé mathématique ne peut être que vrai ou faux. Il ne peut pas être «presque vrai»  ou «à moitié faux». Une des contraintes sera donc d'éviter toute ambiguïté et chaque mot devra avoir un sens mathématique précis. Selon le cas, un énoncé mathématique pourra porter des noms différents.

$\bullet$

assertion : c'est le terme que nous utiliserons le plus souvent pour désigner une affirmation dont on peut dire si elle est vraie ou fausse.

$\bullet$

théorème : c'est un résultat important, dont on démontre ou on admet qu'il est vrai, et qui doit être connu par cur.

$\bullet$

proposition : nous utiliserons ce terme pour désigner un résultat démontré, moins important qu'un théorème.

$\bullet$

lemme : c'est un résultat démontré, qui constitue une étape dans la démonstration d'un théorème.

$\bullet$

corollaire : c'est une conséquence facile d'un théorème ou d'une proposition.

Dans ce cours les démonstrations se terminent par un carré blanc, plutôt que par le célèbre CQFD («ce qu'il fallait démontrer»). Pour écrire formellement des énoncés mathématiques, on utilise des lettres représentant des concepts (nombres, ensembles, fonctions, vecteurs, matrices, polynômes...) avec des symboles logiques et des relations. Le but de ce chapitre étant d'illustrer la manipulation du langage, il ne comportera aucune difficulté mathématique. Nous en resterons à des énoncés très simples, que l'on prendra soin de toujours traduire en langage courant pour bien les comprendre. Dans ce qui suit les lettres $m$ et $n$ désignent des entiers naturels ( $0,1,2,\ldots$). Nous n'utiliserons que les symboles de comparaison ( $<, >, \leqslant ,\geqslant$) et de divisibilité ($\vert$). Rappelons que $m \vert n$ («$m$ divise $n$») si $n$ est égal au produit $km$ pour un certain entier $k$.

$n<5$	l'entier $n$ est strictement inférieur à 5
$n\geqslant 3$	l'entier $n$ est supérieur ou égal à 3
$n \vert 12$	l'entier $n$ divise 12
$2 \vert n$	l'entier $n$ est divisible par 2 (il est pair)

Pour combiner entre elles des assertions, on utilise les connecteurs de base suivants :

$\bullet$

la négation («non»), notée $\neg$

$\bullet$

la conjonction («et»), notée $\wedge$

$\bullet$

la disjonction («ou»), notée $\vee$.

Le tableau suivant est une table de vérité. Il décrit l'effet des connecteurs sur deux assertions $A$ et $B$, selon qu'elles sont vraies ($V$) ou fausses ($F$), en disant dans chacun des 4 cas si l'assertion composée est elle-même vraie ou fausse.

$$\begin{array}{\vert c\vert c\vert c\vert c\vert c\vert} \hli... ...&V\\ V&F&F&F&V\\ F&V&V&F&V\\ F&F&V&F&F\\ \hline \end{array}$$

Le «ou»  est toujours inclusif : $A$ ou $B$ signifie que l'une au moins des deux assertions est vraie (peut-être les deux). Par opposition, le «ou exclusif»  est vrai quand l'une des deux assertions est vraie mais pas les deux. Voici quelques assertions composées et leur traduction.

$\neg(n<5)$	l'entier $n$ n'est pas strictement inférieur à 5.
$(n<5)\wedge (2 \vert n)$	l'entier $n$ est strictement inférieur à 5 et divisible par 2.
$(2 \vert n)\vee (3 \vert n)$	l'entier $n$ est divisible par 2 ou par 3.

Observez l'usage des parenthèses qui permettent d'isoler des assertions simples au sein d'une assertion composée.

À partir des connecteurs de base, on en fabrique d'autres, dont les plus importants sont l'implication et l'équivalence. Par définition, l'implication $A\Longrightarrow B$ est vraie soit si $A$ est fausse soit si $A$ et $B$ sont vraies toutes les deux. L'écriture $A\Longrightarrow B$ est donc une notation pour $(\neg A)\vee B$ («non $A$ ou $B$»). L'équivalence $A\Longleftrightarrow B$ est une double implication : $\Big((A\Longrightarrow B) \wedge (B\Longrightarrow A)\Big)$ («$A$ implique $B$ et $B$ implique $A$»). Voici les tables de vérité des implications et de l'équivalence entre deux assertions $A$ et $B$. Constatez que l'équivalence $A\Longleftrightarrow B$ est vraie quand $A$ et $B$ sont toutes les deux vraies, ou bien toutes les deux fausses.

$$\begin{array}{\vert c\vert c\vert c\vert c\vert c\vert} \hli... ...&V\\ V&F&F&V&F\\ F&V&V&F&F\\ F&F&V&V&V\\ \hline \end{array}$$

L'implication et l'équivalence sont les outils de base du raisonnement mathématique. Il est essentiel de bien les assimiler, et de comprendre toutes leurs formulations.

$A\; \Longrightarrow\; B$

$A$ implique $B$

$A$ entraîne $B$

si $A$ est vrai alors $B$ est vrai

$B$ est vrai si $A$ est vrai

$A$ est vrai seulement si $B$ est vrai

pour que $B$ soit vrai il suffit que $A$ le soit

$A$ est une condition suffisante pour $B$

pour que $A$ soit vrai il faut que $B$ le soit

$B$ est une condition nécessaire pour $A$

Pour bien comprendre l'implication, reprenez chacune des formulations en remplaçant $A$ par «$n>3$»  et $B$ par «$n>2$».

$A\; \Longleftrightarrow\; B$

$A$ est équivalent à $B$

$A$ équivaut à $B$

$A$ entraîne $B$ et réciproquement

si $A$ est vrai alors $B$ est vrai et réciproquement

$A$ est vrai si et seulement si $B$ est vrai

pour que $A$ soit vrai il faut et il suffit que $B$ le soit

$A$ est une condition nécessaire et suffisante pour $B$

Pour bien comprendre l'équivalence, reprenez chacune des formulations en remplaçant $A$ par « $n\geqslant 3$»  et $B$ par «$n>2$».

Les principales propriétés des connecteurs sont résumées dans le théorème suivant.

Théorème 1   Soient $A$, $B$ et $C$ trois assertions. Les équivalences suivantes sont toujours vraies.

$\bullet$

Commutativité :

$$\Big(A\wedge B\Big) \Longleftrightarrow \Big(B\wedge A \Big)\;.$$ (1)

«$A$ et $B$»  équivaut à «$B$ et $A$».

$$\Big(A\vee B \Big)\Longleftrightarrow \Big(B\vee A\Big)\;.$$ (2)

«$A$ ou $B$»  équivaut à «$B$ ou $A$».

$\bullet$

Associativité :

$$\Big(A\wedge (B\wedge C)\Big) \Longleftrightarrow \Big((A\wedge B)\wedge C \Big)\;.$$ (3)

«$A$ et ($B$ et $C$)»  équivaut à «(A et $B$) et $C$».

$$\Big(A\vee (B\vee C)\Big) \Longleftrightarrow \Big((A\vee B)\vee C \Big)\;.$$ (4)

«$A$ ou ($B$ ou $C$)»  équivaut à «(A ou $B$) ou $C$».

$\bullet$

Distributivité :

$$\Big(A\wedge (B\vee C)\Big) \Longleftrightarrow \Big((A\wedge B)\vee(A\wedge C)\Big)\;.$$ (5)

«$A$ et ($B$ ou $C$)»  équivaut à «($A$ et $B$) ou ($A$ et $C$)».

$$\Big(A\vee (B\wedge C)\Big) \Longleftrightarrow \Big((A\vee B)\wedge(A\vee C)\Big)\;.$$ (6)

«$A$ ou ($B$ et $C$)»  équivaut à «($A$ ou $B$) et ($A$ ou $C$)».

$\bullet$

Négations :

$$\Big(\neg(\neg A)\Big)\Longleftrightarrow A\;.$$ (7)

«non (non $A$)»  équivaut à «$A$».

$$\Big(\neg(A\vee B)\Big) \Longleftrightarrow \Big((\neg A)\wedge (\neg B)\Big)\;.$$ (8)

«non ($A$ ou $B$)»  équivaut à «(non $A$) et (non $B$)».

$$\Big(\neg(A\wedge B) \Big)\Longleftrightarrow \Big((\neg A)\vee (\neg B)\Big)\;.$$ (9)

«non ($A$ et $B$)»  équivaut à «(non $A$) ou (non $B$)».

Il est conseillé de remplacer $A$, $B$ et $C$ par des assertions sur les nombres entiers pour bien comprendre les énoncés de ce théorème (par exemple $A$ par $(n\leqslant 6)$, $B$ par $(2 \vert n)$, $C$ par $(3 \vert n)$). Démonstration : Pour démontrer l'équivalence de deux assertions, nous n'avons pas d'autre moyen pour l'instant que de vérifier que leurs tables de vérité coïncident : les deux assertions sont équivalentes si elles sont toujours soit toutes les deux vraies soit toutes les deux fausses. Voici la vérification pour (5).

$$A\wedge (B\vee C) \Longleftrightarrow (A\wedge B)\vee(A\wedge C)\;.$$

L'équivalence est vraie car dans la table ci-dessous, les colonnes correspondant aux deux assertions sont identiques.

$$\begin{array}{\vert ccc\vert cc\vert ccc\vert} \hline A&B&C&... ...F&F\\ F&F&V&V&F&F&F&F\\ F&F&F&F&F&F&F&F\\ \hline \end{array}$$

Nous laissons au lecteur le soin de vérifier de même chacune des autres équivalences.$\square$

Rares sont les démonstrations mathématiques qui utilisent explicitement les tables de vérité. Une démonstration typique est un enchaînement d'implications ou d'équivalences, partant des hypothèses pour aboutir à la conclusion. Ces enchaînements utilisent la transitivité de l'implication et de l'équivalence.

Proposition 1   Soient $A$, $B$ et $C$ trois assertions. L'énoncé suivant est toujours vrai.

$$\Big((A\Longrightarrow B)\wedge(B\Longrightarrow C)\Big) \;\Longrightarrow\; (A\Longrightarrow C)\;.$$ (10)

Si $A$ implique $B$ et $B$ implique $C$, alors $A$ implique $C$.

On en déduit facilement la transitivité de l'équivalence :

Corollaire 1   Soient $A$, $B$ et $C$ des assertions, l'énoncé suivant est toujours vrai.

$$\Big((A\Longleftrightarrow B)\wedge(B\Longleftrightarrow C)\Big) \;\Longrightarrow\; (A\Longleftrightarrow C)\;.$$

Si $A$ équivaut à $B$ et $B$ équivaut à $C$, alors $A$ équivaut à $C$.

Démonstration : Nous utilisons (une dernière fois) les tables de vérité, pour vérifier que quelles que soient les valeurs de vérité de $A$, $B$ et $C$, l'implication (10) est vraie.
Notons

$\bullet$

$I_1$ l'assertion $A\Longrightarrow B$,

$\bullet$

$I_2$ l'assertion $B\Longrightarrow C$,

$\bullet$

$I_3$ l'assertion $A\Longrightarrow C$.

$$\begin{array}{\vert ccc\vert cc\vert cc\vert c\vert} \hline ... ...V&V\\ F&F&V&V&V&V&V&V\\ F&F&F&V&V&V&V&V\\ \hline \end{array}$$

$\square$

Nous utiliserons des enchaînements d'équivalences pour démontrer le résultat suivant, qui décrit le comportement de l'implication par rapport à la négation.

Proposition 2   Soient $A$ et $B$ deux assertions. Les équivalences suivantes sont toujours vraies.

1. $$\Big(\neg(A\Longrightarrow B)\Big)\;\Longleftrightarrow\; \Big(A\wedge(\neg B)\Big)\;.$$ (11)

   
   
   «L'implication $A\Longrightarrow B$ est fausse si et seulement si $A$ est vrai et $B$ est faux».

2. $$\Big(A\Longrightarrow B\Big) \;\Longleftrightarrow\;\Big(\neg B\Longrightarrow\neg A\Big)\;.$$ (12)

   
   
   «$A$ implique $B$»  est équivalent à «non $B$ implique non $A$».

Démonstration : Nous pourrions démontrer ces équivalences directement à l'aide des tables de vérité (nous conseillons au lecteur de le faire). Nous allons plutôt les déduire du théorème 1. Voici la démonstration de la première équivalence.

$$% latex2html id marker 9725\begin{array}{lcll} \neg(A\Long... ...ghtarrow&A\wedge \neg B &\mbox{par (\ref{negneg}).} \end{array}$$

Voici la démonstration de la seconde équivalence.

$$% latex2html id marker 9727\begin{array}{lcll} \Big(A\Long... ... A)\Big) &\mbox{par d\'efinition de l'implication.} \end{array}$$

$\square$

L'équivalence (11) est la méthode habituelle que l'on utilise pour démontrer qu'une implication est fausse : il suffit d'exhiber une situation où $A$ est vraie et $B$ fausse pour infirmer l'implication $A\Longrightarrow B$. Par exemple, l'implication « $(n\leqslant 3)\Longrightarrow (n \vert 3)$»  est fausse, car on peut trouver un entier $n$ tel que $(n\leqslant 3)$ soit vrai et $(n\vert 3)$ soit faux : 2 est inférieur ou égal à 3 mais ne divise pas 3. On appelle cela «trouver un contre-exemple».

L'équivalence (12) est aussi une technique de démonstration classique. L'implication « $(\neg B)\Longrightarrow (\neg A)$»  («non $B$ implique non $A$») s'appelle la contraposée de l'implication $A\Longrightarrow B$. Par exemple, la contraposée de « $(n>3)\Longrightarrow (n>2)$»  est « $(n\leqslant 2)\Longrightarrow (n\leqslant 3)$». Il est parfois plus facile pour démontrer une implication de démontrer sa contraposée, nous y reviendrons.