La logique mathématique constitue le socle de tout raisonnement scientifique rigoureux. Elle fournit les outils essentiels pour construire des démonstrations valides, analyser la structure des arguments et distinguer le vrai du faux avec précision. Que vous soyez au lycée ou à l’université, maîtriser la logique mathématique transforme votre capacité à résoudre des problèmes complexes et à structurer votre pensée de manière cohérente.
Ce cours explore en profondeur les propositions logiques, les opérateurs fondamentaux, les quantificateurs et les différentes méthodes de raisonnement qui forment l’ossature des mathématiques modernes.
Qu’est-ce qu’une Proposition Logique ?
Une proposition (ou assertion) est un énoncé mathématique qui possède une valeur de vérité unique : elle est soit vraie, soit fausse, mais jamais les deux simultanément.
Cette propriété fondamentale distingue les propositions logiques des phrases du langage courant qui peuvent être ambiguës.
Exemples de propositions
- Vrai : « \( 2 + 3 = 5 \) » est une proposition vraie.
- Faux : « Tous les nombres premiers sont impairs » est une proposition fausse (contre-exemple : 2).
- Non-proposition : « \( x > 0 \) » n’est pas une proposition tant que x n’est pas défini, car sa valeur de vérité dépend de x.
Les propositions constituent les briques élémentaires à partir desquelles on construit des raisonnements mathématiques.
Les Opérateurs Logiques Fondamentaux
En logique mathématique, on combine des propositions simples pour former des propositions composées à l’aide d’opérateurs logiques. Ces opérateurs se comportent selon des règles précises, définies par leurs tables de vérité.
La Conjonction : « et » ∧
La proposition \( P \land Q \) (lire « P et Q ») est vraie uniquement si P et Q sont toutes deux vraies. Elle est fausse dans tous les autres cas.
La conjonction exprime une condition stricte : les deux propositions doivent être simultanément vérifiées.
| P | Q | \( P \land Q \) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
La Disjonction : « ou » ∨
La proposition \( P \lor Q \) (lire « P ou Q ») est vraie si au moins une des deux propositions P ou Q est vraie. Elle n’est fausse que si P et Q sont toutes deux fausses.
En mathématiques, le « ou » n’est pas exclusif : \( P \lor Q \) reste vraie même lorsque P et Q sont toutes deux vraies. Cela diffère du langage courant où « ou » suggère souvent un choix exclusif.
| P | Q | \( P \lor Q \) |
|---|---|---|
| V | V | V |
| V | F | V |
| F | V | V |
| F | F | F |
La Négation : « non » ¬
La proposition \( \neg P \) (ou \( \overline{P} \), lire « non P ») est l’opposé logique de P. Elle est vraie si P est fausse, et fausse si P est vraie.
| P | \( \neg P \) |
|---|---|
| V | F |
| F | V |
L’Implication : « si… alors » ⇒
L’implication logique est l’un des concepts les plus importants et les plus subtils de la logique mathématique.
L’implication \( P \Rightarrow Q \) (lire « P implique Q » ou « si P alors Q ») est définie comme la proposition \( \neg P \lor Q \). Elle est fausse uniquement lorsque P est vraie et Q est fausse. Dans tous les autres cas, elle est vraie.
Cette définition peut sembler contre-intuitive : pourquoi \( P \Rightarrow Q \) est-elle vraie lorsque P est fausse, quelle que soit Q ? En logique mathématique, on considère qu’une hypothèse fausse n’impose aucune contrainte sur la conclusion. C’est le principe de vacuité.
| P | Q | \( P \Rightarrow Q \) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
Vocabulaire associé à l’implication
- Dans \( P \Rightarrow Q \), P est appelée l’hypothèse ou antécédent.
- Q est appelée la conclusion ou conséquent.
- On dit aussi que P est une condition suffisante pour Q.
- Q est une condition nécessaire pour P.
L’Équivalence : « si et seulement si » ⇔
L’équivalence \( P \Leftrightarrow Q \) (lire « P équivaut à Q » ou « P si et seulement si Q ») signifie que P et Q ont toujours la même valeur de vérité. Elle est définie par : \( (P \Rightarrow Q) \land (Q \Rightarrow P) \).
L’équivalence exprime une double implication : P entraîne Q et Q entraîne P. On dit aussi que P et Q sont logiquement équivalentes.
| P | Q | \( P \Leftrightarrow Q \) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | V |
Lois Logiques et Tautologies
Une tautologie (ou loi logique) est une proposition composée qui est toujours vraie, quelles que soient les valeurs de vérité des propositions simples qui la composent.
Les tautologies jouent un rôle central en logique mathématique car elles permettent de transformer et simplifier des expressions logiques de manière systématique.
Lois de Morgan
Les lois de Morgan sont parmi les tautologies les plus utilisées en logique mathématique. Elles décrivent comment la négation se distribue sur les opérateurs « et » et « ou ».
Pour toutes propositions P et Q :
\neg (P \land Q) \Leftrightarrow (\neg P) \lor (\neg Q)
\]
\neg (P \lor Q) \Leftrightarrow (\neg P) \land (\neg Q)
\]
En mots : la négation d’une conjonction est une disjonction de négations, et la négation d’une disjonction est une conjonction de négations.
Autres lois logiques importantes
- Double négation : \( P \Leftrightarrow \neg(\neg P) \)
- Commutativité : \( P \land Q \Leftrightarrow Q \land P \) et \( P \lor Q \Leftrightarrow Q \lor P \)
- Associativité : \( (P \land Q) \land R \Leftrightarrow P \land (Q \land R) \)
- Distributivité : \( P \land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R) \)
- Contraposition : \( (P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P) \)
- Négation d’une implication : \( \neg(P \Rightarrow Q) \Leftrightarrow P \land \neg Q \)
La loi de contraposition est particulièrement utile pour les démonstrations : prouver \( P \Rightarrow Q \) revient à prouver sa contraposée \( \neg Q \Rightarrow \neg P \).
Quantificateurs Logiques : Généraliser les Propositions
Les quantificateurs logiques permettent d’exprimer des propositions portant sur un ensemble d’éléments, sans avoir à les énumérer un par un.
Fonctions Propositionnelles
Une fonction propositionnelle \( P(x) \) est une expression dépendant d’une variable \( x \) (appartenant à un ensemble E) qui devient une proposition (vraie ou fausse) lorsqu’on attribue une valeur spécifique à \( x \).
Exemple : Soit \( P(x) \) la fonction propositionnelle « \( x^2 \geq 0 \) » définie sur \( \mathbb{R} \). Pour \( x = 3 \), \( P(3) \) est vraie car \( 9 \geq 0 \). Pour \( x = -2 \), \( P(-2) \) est également vraie car \( 4 \geq 0 \).
Le Quantificateur Universel : « Pour tout » ∀
La proposition \( \forall x \in E, P(x) \) (lire « pour tout x appartenant à E, P(x) est vraie ») affirme que la propriété P(x) est vérifiée pour chaque élément x de l’ensemble E.
Pour qu’une proposition universelle soit vraie, il faut que P(x) soit vraie pour tous les éléments de E sans exception.
Exemples
- \( \forall x \in \mathbb{R}, x^2 \geq 0 \) est vraie (le carré d’un nombre réel est toujours positif ou nul).
- \( \forall n \in \mathbb{N}, n \geq 0 \) est vraie (par définition des entiers naturels).
- \( \forall x \in \mathbb{R}, x^2 > 0 \) est fausse (contre-exemple : \( x = 0 \)).
Le Quantificateur Existentiel : « Il existe » ∃
La proposition \( \exists x \in E, P(x) \) (lire « il existe (au moins) un x appartenant à E tel que P(x) soit vraie ») affirme qu’on peut trouver au moins un élément x de E pour lequel P(x) est vérifiée.
Pour qu’une proposition existentielle soit vraie, il suffit de trouver un seul élément qui vérifie la propriété.
Exemples
- \( \exists x \in \mathbb{R}, x^2 = 4 \) est vraie (par exemple, \( x = 2 \) ou \( x = -2 \)).
- \( \exists n \in \mathbb{N}, n^2 = n \) est vraie (par exemple, \( n = 0 \) ou \( n = 1 \)).
- \( \exists x \in \mathbb{R}, x^2 = -1 \) est fausse (aucun réel au carré n’est négatif).
L’Unicité : ∃!
Pour exprimer qu’un élément vérifiant une propriété est unique, on utilise le quantificateur \( \exists ! \). Par exemple, \( \exists ! x \in \mathbb{R}, 2x + 3 = 7 \) signifie qu’il existe une unique solution réelle à cette équation (ici, \( x = 2 \)).
Négation des Quantificateurs
La négation des quantificateurs logiques suit des règles précises dérivées des lois de De Morgan :
Pour toute fonction propositionnelle P(x) sur un ensemble E :
- \( \neg (\forall x \in E, P(x)) \Leftrightarrow \exists x \in E, \neg P(x) \)
- \( \neg (\exists x \in E, P(x)) \Leftrightarrow \forall x \in E, \neg P(x) \)
En mots : la négation de « pour tout » devient « il existe » avec négation de la propriété, et inversement.
Exemple
Soit la proposition : « Tous les nombres pairs sont divisibles par 4 ».
Formellement : \( \forall n \in \mathbb{Z}, (n \text{ pair} \Rightarrow n \text{ divisible par } 4) \)
Sa négation est : \( \exists n \in \mathbb{Z}, (n \text{ pair} \land n \text{ non divisible par } 4) \)
Cette négation est vraie (contre-exemple : \( n = 6 \)).
Attention : L’ordre des quantificateurs est crucial ! Les propositions \( \forall x \exists y, P(x,y) \) et \( \exists y \forall x, P(x,y) \) ont des significations très différentes. Dans la première, y peut dépendre de x. Dans la seconde, un même y doit convenir pour tous les x.
Les Méthodes de Raisonnement Mathématique
Un raisonnement est une démarche logique structurée permettant d’établir la vérité d’une proposition. La logique mathématique fournit plusieurs méthodes classiques de démonstration.
Raisonnement Direct
Pour démontrer \( P \Rightarrow Q \), on suppose que P est vraie et on déduit, par une chaîne d’implications logiques, que Q est nécessairement vraie.
C’est la méthode la plus naturelle et souvent la première à essayer.
Exemple : Démontrer que si \( n \) est un entier pair, alors \( n^2 \) est pair.
Démonstration : Supposons que \( n \) est pair. Par définition, il existe un entier \( k \) tel que \( n = 2k \). Calculons \( n^2 \) :
n^2 = (2k)^2 = 4k^2 = 2(2k^2)
\]
En posant \( k’ = 2k^2 \), on obtient \( n^2 = 2k’ \) avec \( k’ \in \mathbb{Z} \). Donc \( n^2 \) est pair par définition. La proposition est démontrée.
Raisonnement par Disjonction de Cas
Pour vérifier une proposition P(x) sur un ensemble E, on divise E en plusieurs sous-ensembles disjoints (cas exhaustifs), et on montre que la proposition est vraie dans chaque cas.
Exemple : Montrer que \( \forall n \in \mathbb{Z}, n(n+1) \) est pair.
Démonstration par disjonction de cas : Tout entier \( n \) est soit pair, soit impair. Examinons les deux cas :
- Cas 1 : Si \( n \) est pair, alors \( n = 2k \) pour un certain \( k \in \mathbb{Z} \). Donc \( n(n+1) = 2k(n+1) = 2k’ \) avec \( k’ = k(n+1) \). Le produit est pair.
- Cas 2 : Si \( n \) est impair, alors \( n+1 \) est pair, donc \( n+1 = 2k \) pour un certain \( k \in \mathbb{Z} \). Ainsi \( n(n+1) = n \cdot 2k = 2(nk) \). Le produit est pair.
Dans tous les cas, \( n(n+1) \) est pair. La proposition est démontrée.
Raisonnement par Contraposition
Pour démontrer \( P \Rightarrow Q \), on utilise la loi de contraposition et on démontre sa contraposée : \( \neg Q \Rightarrow \neg P \).
Cette méthode est particulièrement utile lorsque la négation de la conclusion fournit une hypothèse de travail plus exploitable.
Exemple : Montrer que si \( n^2 \) est impair, alors \( n \) est impair.
Démonstration par contraposition : La contraposée est : « si \( n \) est pair, alors \( n^2 \) est pair ». Nous avons déjà démontré cette implication ci-dessus. Par contraposition, l’implication initiale est vraie.
Raisonnement par l’Absurde
Pour démontrer qu’une proposition est vraie, on suppose le contraire (sa négation) et on cherche à aboutir à une contradiction logique, c’est-à-dire une affirmation impossible.
Le raisonnement par l’absurde est une méthode puissante, souvent utilisée pour démontrer l’inexistence ou l’unicité.
Exemple : Montrer que \( \sqrt{2} \) est irrationnel.
Démonstration par l’absurde : Supposons par l’absurde que \( \sqrt{2} \) est rationnel. Alors il existe deux entiers \( p \) et \( q \) premiers entre eux (c’est-à-dire sans facteur commun autre que 1) tels que :
\sqrt{2} = \frac{p}{q}
\]
En élevant au carré les deux membres :
2 = \frac{p^2}{q^2} \Rightarrow p^2 = 2q^2
\]
Donc \( p^2 \) est pair, ce qui implique que \( p \) est pair (résultat démontré précédemment). Écrivons \( p = 2k \) :
(2k)^2 = 2q^2 \Rightarrow 4k^2 = 2q^2 \Rightarrow q^2 = 2k^2
\]
Donc \( q^2 \) est pair, ce qui implique que \( q \) est pair. Nous obtenons que \( p \) et \( q \) sont tous deux pairs, donc ils ont 2 comme facteur commun. Ceci contredit l’hypothèse qu’ils sont premiers entre eux. Notre supposition était donc fausse. Par conséquent, \( \sqrt{2} \) est irrationnel.
Raisonnement par Contre-exemple
Pour prouver qu’une proposition universelle \( \forall x \in E, P(x) \) est fausse, il suffit de trouver un seul élément \( x_0 \in E \) pour lequel \( P(x_0) \) est fausse. Cet élément \( x_0 \) est appelé un contre-exemple.
Exemple : Montrer que la proposition « \( \forall n \in \mathbb{N}^*, n^2 > n \) » est fausse.
Démonstration par contre-exemple : Il suffit de trouver un entier naturel non nul pour lequel \( n^2 \leq n \). Prenons \( n = 1 \). On a \( 1^2 = 1 \), donc \( n^2 = n \), ce qui contredit \( n^2 > n \). La proposition est donc fausse.
Raisonnement par Récurrence
Le raisonnement par récurrence est une méthode fondamentale pour démontrer des propositions dépendant d’un entier naturel.
Principe de récurrence : Soit \( P(n) \) une propriété dépendant d’un entier \( n \geq n_0 \). Si :
- Initialisation : \( P(n_0) \) est vraie,
- Hérédité : Pour tout \( n \geq n_0 \), si \( P(n) \) est vraie, alors \( P(n+1) \) est vraie,
Alors \( P(n) \) est vraie pour tout \( n \geq n_0 \).
L’analogie classique est celle des dominos : si le premier domino tombe (initialisation) et si chaque domino fait tomber le suivant (hérédité), alors tous les dominos tombent (conclusion).
Exemple : Montrer que \( \forall n \in \mathbb{N}^*, \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \).
Démonstration par récurrence :
Initialisation : Pour \( n = 1 \), on a \( \sum_{k=1}^{1} k = 1 \) et \( \frac{1(1+1)}{2} = \frac{2}{2} = 1 \). Donc \( P(1) \) est vraie.
Hérédité : Supposons que \( P(n) \) est vraie pour un certain \( n \geq 1 \), c’est-à-dire :
\sum_{k=1}^{n} k = \frac{n(n+1)}{2}
\]
Montrons que \( P(n+1) \) est vraie, c’est-à-dire que \( \sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2} \).
Calculons :
\sum_{k=1}^{n+1} k &= \left(\sum_{k=1}^{n} k\right) + (n+1) \\
&= \frac{n(n+1)}{2} + (n+1) \quad \text{(par hypothèse de récurrence)} \\
&= \frac{n(n+1)}{2} + \frac{2(n+1)}{2} \\
&= \frac{n(n+1) + 2(n+1)}{2} \\
&= \frac{(n+1)(n+2)}{2}
\end{align*}
Donc \( P(n+1) \) est vraie.
Conclusion : Par le principe de récurrence, la formule est vraie pour tout \( n \in \mathbb{N}^* \).
Raisonnement par Équivalence
Pour montrer qu’une proposition P est vraie, on peut la transformer en une proposition Q équivalente (\( P \Leftrightarrow Q \)) dont on sait qu’elle est vraie.
Cette méthode utilise une chaîne d’équivalences logiques successives.
Exemple : Montrer que \( \forall x > 0, x + \frac{1}{x} \geq 2 \).
Démonstration par équivalence : Procédons par équivalences successives (puisque \( x > 0 \), on peut multiplier sans changer le sens de l’inégalité) :
x + \frac{1}{x} \geq 2 &\Leftrightarrow \frac{x^2 + 1}{x} \geq 2 \\
&\Leftrightarrow x^2 + 1 \geq 2x \quad \text{(car } x > 0 \text{)} \\
&\Leftrightarrow x^2 – 2x + 1 \geq 0 \\
&\Leftrightarrow (x-1)^2 \geq 0
\end{align*}
La dernière proposition \( (x-1)^2 \geq 0 \) est toujours vraie (un carré est toujours positif ou nul). Puisque nous avons procédé par équivalence, la proposition initiale est également vraie.
Résumé du cours : Logique mathématique
- Une proposition logique est un énoncé qui admet une valeur de vérité unique : vraie ou fausse.
- Les principaux opérateurs logiques sont :
- la conjonction \( \land \) (« et »),
- la disjonction \( \lor \) (« ou » inclusif),
- la négation \( \neg \),
- l’implication \( \Rightarrow \),
- l’équivalence \( \Leftrightarrow \).
- L’implication \( P \Rightarrow Q \) est fausse uniquement lorsque P est vraie et Q est fausse.
- Deux propositions sont logiquement équivalentes si elles ont toujours la même valeur de vérité.
- Une tautologie est une proposition toujours vraie, quelles que soient les valeurs de vérité des propositions simples.
- Les lois de De Morgan permettent de transformer la négation d’une conjonction ou d’une disjonction.
- Une fonction propositionnelle devient une proposition lorsqu’on fixe la valeur de sa variable.
- Le quantificateur universel \( \forall \) signifie « pour tout », tandis que le quantificateur existentiel \( \exists \) signifie « il existe au moins un ».
- La négation d’un quantificateur échange \( \forall \) et \( \exists \) tout en niant la propriété.
- L’ordre des quantificateurs est essentiel et peut changer complètement le sens d’une proposition.
- Les principales méthodes de raisonnement sont :
- le raisonnement direct,
- la disjonction de cas,
- la contraposition,
- le raisonnement par l’absurde,
- le contre-exemple,
- la récurrence,
- le raisonnement par équivalence.
- Un contre-exemple suffit pour réfuter une proposition universelle.
- Le raisonnement par récurrence repose sur une initialisation et une hérédité.