Logique et raisonnement

1Assertions et connecteurs logiques

Définition. Une assertion (ou proposition) est un énoncé mathématique dont on peut dire, sans ambiguïté, s’il est vrai ou s’il est faux. « $2+2=4$ » est une assertion vraie, « $\sqrt{2}\in\Q$ » une assertion fausse. Aucune définition formelle du vrai et du faux n’est donnée : toute étude systématique de la logique est hors programme. Les mots « assertion », « vrai », « faux » sont ici des mots du langage courant, employés avec rigueur.

Notation. On note $P$, $Q$, $R$ des assertions. Une assertion peut dépendre d’une ou plusieurs variables : on écrit alors $P(x)$, et l’on parle de prédicat. « $x^{2}\geq x$ » n’a de valeur de vérité qu’une fois $x$ fixé (et une fois précisé l’ensemble où il varie) : c’est vrai pour $x=2$, faux pour $x=\frac12$.

Définition. À partir de $P$ et $Q$ on construit :

• la négation de $P$, notée $\lnot P$ ou « non $P$ » : vraie lorsque $P$ est fausse, fausse lorsque $P$ est vraie ;
• la conjonction « $P$ et $Q$ » : vraie lorsque $P$ et $Q$ sont toutes deux vraies ;
• la disjonction « $P$ ou $Q$ » : vraie lorsque au moins l’une des deux est vraie.

Propriété — table de vérité. Les valeurs de vérité des assertions composées se lisent dans le tableau suivant, où $V$ signifie « vraie » et $F$ « fausse ».

Propriété — lois de De Morgan. Pour toutes assertions $P$ et $Q$ :

Idée de preuve. On compare les deux colonnes correspondantes de la table de vérité, ligne par ligne : les quatre cas $(V,V)$, $(V,F)$, $(F,V)$, $(F,F)$ donnent les mêmes valeurs.

2Implication, contraposée, équivalence

Définition. L’implication $P\Longrightarrow Q$ est l’assertion « $\left(\lnot P\right)$ ou $Q$ ». Elle se lit « $P$ implique $Q$ », ou « si $P$ alors $Q$ ». On dit alors que $P$ est une condition suffisante pour $Q$, et que $Q$ est une condition nécessaire pour $P$.

Propriété. Pour toutes assertions $P$ et $Q$ :

Idée de preuve (exigible). $P\Longrightarrow Q$ est par définition « $\left(\lnot P\right)$ ou $Q$ », et $\left(\lnot Q\right)\Longrightarrow\left(\lnot P\right)$ est « $Q$ ou $\left(\lnot P\right)$ » : c’est la même assertion, la disjonction étant symétrique. Pour la négation, $\lnot\left(\left(\lnot P\right)\text{ ou }Q\right)$ vaut « $P$ et $\lnot Q$ » par De Morgan et double négation.

Définition. L’équivalence $P\Longleftrightarrow Q$ est l’assertion « $\left(P\Longrightarrow Q\right)$ et $\left(Q\Longrightarrow P\right)$ ». On dit que $P$ est une condition nécessaire et suffisante pour $Q$, ou que $P$ et $Q$ sont équivalentes.

Méthode — démontrer une équivalence. deux stratégies. Par double implication : on démontre $P\Longrightarrow Q$, puis $Q\Longrightarrow P$ (c’est toujours possible, et c’est la méthode sûre). Par équivalences successives : on écrit une chaîne $P\iff P_{1}\iff\dots\iff Q$, mais il faut alors vérifier que chaque étape est une équivalence — élever au carré, multiplier par une quantité de signe inconnu, composer par une fonction non injective ne sont que des implications.

3Quantificateurs

Définition. Soient $E$ un ensemble et $P(x)$ un prédicat portant sur $x\in E$.

• « $\forall x\in E,\ P(x)$ » — quantificateur universel — signifie : $P(x)$ est vraie pour tous les éléments $x$ de $E$ ;
• « $\exists x\in E,\ P(x)$ » — quantificateur existentiel — signifie : il existe au moins un élément $x$ de $E$ tel que $P(x)$ soit vraie ;
• « $\exists!\,x\in E,\ P(x)$ » signifie : il existe un unique élément $x$ de $E$ tel que $P(x)$ soit vraie.

La variable $x$ est muette : on peut la renommer sans changer l’assertion, et elle n’a aucun sens en dehors de la portée du quantificateur.

Notation. Si $E=\varnothing$, l’assertion « $\forall x\in E,\ P(x)$ » est vraie et « $\exists x\in E,\ P(x)$ » est fausse. Une assertion universelle portant sur un ensemble vide est vraie « par vacuité ».

Théorème — négation d’une assertion quantifiée. Pour tout ensemble $E$ et tout prédicat $P$ :

Méthode — nier une assertion quantifiée. on parcourt l’assertion de gauche à droite : chaque $\forall$ devient $\exists$, chaque $\exists$ devient $\forall$, les ensembles ne changent pas, et l’on nie in fine la conclusion. Par exemple, la négation de

On n’oublie pas de nier la conclusion elle-même : la négation de $\leq$ est $>$, celle de $=$ est $\neq$.

4Les modes de raisonnement

Méthode — déduction directe. pour démontrer $P\Longrightarrow Q$ : on suppose $P$ vraie (« supposons $P$ », « soit $x$ tel que… ») et l’on enchaîne des implications jusqu’à $Q$. Pour démontrer « $\forall x\in E,\ P(x)$ », on commence par « soit $x\in E$ » : $x$ est alors fixé quelconque.

Méthode — contraposition. pour démontrer $P\Longrightarrow Q$, on démontre $\left(\lnot Q\right)\Longrightarrow\left(\lnot P\right)$, qui lui est équivalente. À utiliser quand $\lnot Q$ est une hypothèse plus maniable que $P$ : « si $n^{2}$ est impair alors $n$ est impair » se démontre en supposant $n$ pair.

Méthode — raisonnement par l’absurde. pour démontrer une assertion $A$, on suppose $\lnot A$ et l’on aboutit à une contradiction (une assertion et sa négation simultanément vraies) ; on conclut que $A$ est vraie. C’est la méthode reine pour démontrer une non-existence (« il n’existe pas de rationnel de carré $2$ »).

Méthode — disjonction de cas. pour démontrer $A$, on partage la situation en cas dont on vérifie qu’ils recouvrent tous les possibles, et l’on démontre $A$ dans chacun. Les cas peuvent se chevaucher ; ils ne doivent rien laisser de côté. Exemples : $n$ pair ou impair ; $x\geq a$ ou $x<a$ pour lever une valeur absolue ; $x=0$ ou $x\neq0$ avant de diviser.

Méthode — contre-exemple. pour démontrer que « $\forall x\in E,\ P(x)$ » est fausse, il suffit d’exhiber un $x_{0}\in E$ tel que $P(x_{0})$ soit fausse : c’est exactement la négation. Réciproquement, un exemple ne démontre jamais une assertion universelle.

Méthode — analyse-synthèse. pour résoudre un problème d’existence et d’unicité (« montrer qu’il existe un unique objet tel que… »). Analyse : on suppose le problème résolu et l’on en tire des conditions nécessaires, jusqu’à ne plus avoir qu’un seul candidat — ce qui démontre l’unicité. Synthèse : on vérifie que ce candidat convient effectivement — ce qui démontre l’existence. Les deux temps sont indispensables : l’analyse seule ne prouve pas l’existence.

Méthode — double implication, double inclusion. pour une équivalence, deux implications ; pour une égalité d’ensembles, deux inclusions ; pour une égalité de réels, deux inégalités. Même schéma, trois usages.

5Raisonnement par récurrence

Théorème — propriété fondamentale de $\N$ — admise. Toute partie non vide de $\N$ admet un plus petit élément. Toute partie non vide et majorée de $\N$ admet un plus grand élément. Toute construction et toute axiomatique de $\N$ sont hors programme : cette propriété est admise et sert de point de départ.

Théorème — principe de récurrence. Soit $P(n)$ un prédicat portant sur $n\in\N$. Si

alors $P(n)$ est vraie pour tout $n\in\N$.

Démonstration (exigible). Par l’absurde, soit $A=\ens{n\in\N,\ \lnot P(n)}$ et supposons $A\neq\varnothing$. Alors $A$ admet un plus petit élément $n_{0}$. Comme $P(0)$ est vraie, $0\notin A$, donc $n_{0}\geq1$ et $n_{0}-1\in\N$. Par minimalité de $n_{0}$, $n_{0}-1\notin A$, c’est-à-dire $P(n_{0}-1)$ est vraie ; l’hypothèse (ii) appliquée à $n=n_{0}-1$ donne alors $P(n_{0})$ vraie, donc $n_{0}\notin A$ : contradiction. Donc $A=\varnothing$.

Méthode — rédiger une récurrence. quatre temps, toujours les mêmes.

1. Énoncer la propriété : « pour $n\in\N$, notons $P(n)$ la propriété … ». Elle doit dépendre de $n$ et de rien d’autre.
2. Initialisation : vérifier $P(n_{0})$ pour le premier rang utile, en calculant les deux membres séparément.
3. Hérédité : « soit $n\geq n_{0}$ tel que $P(n)$ soit vraie ; montrons $P(n+1)$ ». On indique où l’hypothèse de récurrence est utilisée.
4. Conclusion : « par récurrence, $P(n)$ est vraie pour tout $n\geq n_{0}$ ».

Théorème — variantes. Soit $n_{0}\in\N$ et $P(n)$ un prédicat.

Idée de preuve. On les déduit du principe de récurrence appliqué à une propriété auxiliaire : $Q(n)=$ « $P(n+n_{0})$ » pour la première, $Q(n)=$ « $P(n)$ et $P(n+1)$ » pour la récurrence double, $Q(n)=$ « $P(k)$ est vraie pour tout $k\in\intent{n_{0}}{n}$ » pour la récurrence forte.

Méthode — choisir sa récurrence. récurrence double lorsque $u_{n+2}$ s’exprime à l’aide de $u_{n+1}$ et $u_{n}$ ; récurrence forte lorsque le passage au rang $n+1$ utilise un rang antérieur inconnu (décomposition d’un entier, division, algorithme glouton). Lorsque l’hérédité échoue de peu, essayer de renforcer la propriété : une propriété plus forte peut être plus facile à hériter.