La logique mathématique

Définitions

Une proposition logique est un énoncé déclaratif qui est soit vrai, soit faux, mais pas les deux à la fois. La valeur de vérité d’une proposition est soit vraie (notée V ou 1), soit fausse (notée F ou 0). Par exemple, « 2 + 2 = 4 » est une proposition logique vraie, tandis que « la lune est faite de fromage » est une proposition logique fausse. Les questions, les exclamations et les ordres ne sont pas des propositions logiques car on ne peut pas leur attribuer une valeur de vérité.

Les connecteurs logiques permettent de combiner des propositions logiques simples pour former des propositions composées. Les principaux connecteurs sont :

  • La négation (non, $\neg$): Si $P$ est une proposition, $\neg P$ est vraie si $P$ est fausse, et fausse si $P$ est vraie.
  • La conjonction (et, $\land$): Si $P$ et $Q$ sont des propositions, $P \land Q$ est vraie si et seulement si $P$ est vraie et $Q$ est vraie. Par exemple, « Le ciel est bleu et l’herbe est verte » est vraie.
  • La disjonction (ou, $\lor$): Si $P$ et $Q$ sont des propositions, $P \lor Q$ est vraie si $P$ est vraie, ou si $Q$ est vraie, ou si les deux sont vraies. Par exemple, « Il pleut ou il neige » est vraie s’il pleut, s’il neige, ou s’il pleut et neige.
  • L’implication (implique, $\Rightarrow$): Si $P$ et $Q$ sont des propositions, $P \Rightarrow Q$ est fausse uniquement si $P$ est vraie et $Q$ est fausse. Dans tous les autres cas, elle est vraie. On lit souvent « $P$ implique $Q$ », « si $P$ alors $Q$ », ou « $P$ est une condition suffisante pour $Q$ ». Par exemple, « S’il pleut, alors le sol est mouillé ».
  • L’équivalence (équivaut à, $\Leftrightarrow$): Si $P$ et $Q$ sont des propositions, $P \Leftrightarrow Q$ est vraie si et seulement si $P$ et $Q$ ont la même valeur de vérité (soit toutes les deux vraies, soit toutes les deux fausses). On lit souvent « $P$ équivaut à $Q$ », « $P$ si et seulement si $Q$ », ou « $P$ est une condition nécessaire et suffisante pour $Q$ ». Par exemple, pour un entier $n$, « $n$ est pair $\Leftrightarrow$ $n$ est divisible par 2 ».

Les quantificateurs permettent d’exprimer la portée d’une propriété. Les deux principaux quantificateurs sont :

  • Le quantificateur universel (pour tout, $\forall$): $\forall x \in E, P(x)$ signifie « pour tout élément $x$ de l’ensemble $E$, la propriété $P(x)$ est vraie ». Par exemple, $\forall n \in \mathbb{N}, n \geq 0$.
  • Le quantificateur existentiel (il existe, $\exists$): $\exists x \in E, P(x)$ signifie « il existe au moins un élément $x$ dans l’ensemble $E$ tel que la propriété $P(x)$ est vraie ». Par exemple, $\exists x \in \mathbb{R}, x^2 = 4$.
On utilise aussi parfois le quantificateur d’unicité $\exists!$, où $\exists! x \in E, P(x)$ signifie « il existe un unique élément $x$ dans l’ensemble $E$ tel que la propriété $P(x)$ est vraie ».

Une fonction propositionnelle (ou prédicat) est un énoncé contenant une ou plusieurs variables, qui devient une proposition logique lorsqu’on substitue ces variables par des valeurs spécifiques. Par exemple, $P(x) : « x > 5″$ est une fonction propositionnelle. Si $x = 7$, alors $P(7)$ est la proposition « 7 > 5 », qui est vraie. Si $x = 3$, alors $P(3)$ est la proposition « 3 > 5 », qui est fausse. Une fonction propositionnelle peut être quantifiée pour former une proposition logique, comme $\forall x \in \mathbb{N}, x > 0$ ou $\exists x \in \mathbb{R}, x^2 < 0$.

La négation d’une proposition inverse sa valeur de vérité.

  • La négation de $\neg P$ est $P$.
  • La négation de $P \land Q$ est $\neg P \lor \neg Q$ (Lois de De Morgan).
  • La négation de $P \lor Q$ est $\neg P \land \neg Q$ (Lois de De Morgan).
  • La négation de $P \Rightarrow Q$ est $P \land \neg Q$. Il est important de noter que la négation de l’implication n’est pas une implication.
  • La négation de $P \Leftrightarrow Q$ est $(P \land \neg Q) \lor (\neg P \land Q)$.
  • La négation de $\forall x \in E, P(x)$ est $\exists x \in E, \neg P(x)$.
  • La négation de $\exists x \in E, P(x)$ est $\forall x \in E, \neg P(x)$.

Raisonnements

Une implication $P \Rightarrow Q$ affirme que si $P$ est vraie, alors $Q$ est nécessairement vraie. Elle ne dit rien sur la valeur de vérité de $Q$ si $P$ est fausse. L’implication est fondamentale dans les preuves mathématiques. On démontre souvent une implication en supposant que $P$ est vraie et en montrant que $Q$ doit alors être vraie. Par exemple, pour prouver que « si $n$ est un entier pair, alors $n^2$ est un entier pair », on suppose que $n$ est pair (donc $n = 2k$ pour un certain entier $k$), et on montre que $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$, qui est bien pair.

Une équivalence $P \Leftrightarrow Q$ signifie que $P$ et $Q$ ont la même valeur de vérité. On la démontre généralement en prouvant deux implications : $P \Rightarrow Q$ et $Q \Rightarrow P$. Par exemple, pour prouver que « un entier $n$ est pair si et seulement si $n+1$ est impair », on montre d’abord que si $n$ est pair, alors $n+1$ est impair, et ensuite que si $n+1$ est impair, alors $n$ est pair.

Une contradiction est une proposition qui est toujours fausse, quelles que soient les valeurs de vérité des propositions qui la composent. Une contradiction prend la forme $P \land \neg P$. Par exemple, l’énoncé « $x > 5$ et $x \leq 3$ » est une contradiction. En mathématiques, une contradiction est souvent le résultat d’une erreur dans un raisonnement, et peut être utilisée dans la preuve par l’absurde.

Un contre-exemple est une instance spécifique qui montre qu’une proposition universelle est fausse. Pour réfuter une affirmation de la forme $\forall x \in E, P(x)$, il suffit de trouver un élément $a \in E$ tel que $P(a)$ est fausse. Par exemple, pour réfuter l’affirmation « tous les nombres premiers sont impairs », on peut donner le contre-exemple du nombre premier 2, qui est pair.

La récurrence (ou induction mathématique) est une méthode de preuve puissante pour démontrer des propriétés qui dépendent d’un entier naturel $n$. Elle repose sur deux étapes :

  1. L’initialisation : On montre que la propriété est vraie pour la première valeur de $n$ (souvent $n=0$ ou $n=1$).
  2. L’hérédité : On suppose que la propriété est vraie pour un entier $k$ quelconque (l’hypothèse de récurrence) et on montre qu’elle est alors vraie pour l’entier suivant $k+1$.
Si ces deux étapes sont prouvées, alors par le principe de récurrence, la propriété est vraie pour tous les entiers naturels à partir de la valeur d’initialisation. Par exemple, pour prouver que la somme des $n$ premiers entiers naturels est $\frac{n(n+1)}{2}$, on vérifie que c’est vrai pour $n=1$, puis on suppose que c’est vrai pour $k$ et on montre que c’est vrai pour $k+1$.

Le raisonnement par l’absurde est une méthode de preuve où l’on suppose que la proposition que l’on souhaite démontrer est fausse, et on montre que cette supposition mène à une contradiction. Si la négation de la proposition conduit à une contradiction, alors la proposition originale doit être vraie. Par exemple, pour prouver que $\sqrt{2}$ est irrationnel, on suppose que $\sqrt{2}$ est rationnel (donc $\sqrt{2} = \frac{p}{q}$ où $p$ et $q$ sont des entiers premiers entre eux), et on déduit de cette supposition une contradiction (par exemple, que $p$ et $q$ doivent tous les deux être pairs).