Sciences · Mathématiques
La logique mathématique
La logique mathématique étudie la forme des raisonnements valides. Elle manipule des propositions vraies ou fausses, reliées par des connecteurs (non, et, ou, implique) et des quantificateurs (pour tout, il existe).
Mis à jour le 5 min de lecture
« S’il pleut, le sol est mouillé. Le sol est mouillé. Donc il a plu. » Ce raisonnement semble convaincant, et pourtant il est faux : le sol peut avoir été arrosé. La logique mathématique donne les règles qui permettent de distinguer à coup sûr un raisonnement valide d’un raisonnement fautif. Elle est le socle de toute démonstration et de l’informatique.
Les connecteurs logiques
On combine des propositions P et Q à l’aide de connecteurs. Leur sens est fixé par des tables de vérité (V : vrai, F : faux).
| P | Q | non P (¬P) | P et Q (P ∧ Q) | P ou Q (P ∨ Q) | P ⇒ Q | P ⇔ Q |
|---|---|---|---|---|---|---|
| V | V | F | V | V | V | V |
| V | F | F | F | V | F | F |
| F | V | V | F | V | V | F |
| F | F | V | F | F | V | V |
Points d’attention
- Le « ou » mathématique est inclusif : « P ou Q » est vrai si au moins l’une des deux est vraie, y compris les deux. Le « ou » du menu « fromage ou dessert » est exclusif : on parle alors de « ou exclusif ».
- L’implication « P ⇒ Q » (« si P, alors Q ») n’est fausse que dans un seul cas : P vraie et Q fausse. En particulier, si P est fausse, l’implication est vraie quelle que soit Q. « Si 2 + 2 = 5, alors je suis la reine d’Angleterre » est logiquement vraie.
- L’équivalence « P ⇔ Q » (« P si et seulement si Q ») signifie que P et Q ont toujours la même valeur de vérité.
Implication, réciproque et contraposée
À partir de l’implication P ⇒ Q, on forme :
| Énoncé | Forme | Exemple | Même valeur que P ⇒ Q ? |
|---|---|---|---|
| Implication | P ⇒ Q | « Si un nombre est multiple de 4, il est pair » (vrai) | — |
| Réciproque | Q ⇒ P | « Si un nombre est pair, il est multiple de 4 » (faux : 6) | non, pas nécessairement |
| Contraposée | non Q ⇒ non P | « Si un nombre n’est pas pair, il n’est pas multiple de 4 » (vrai) | oui, toujours |
Le raisonnement fautif de l’introduction confond une implication et sa réciproque. C’est l’une des erreurs de raisonnement les plus fréquentes. Le théorème de Pythagore et sa réciproque sont tous deux vrais, mais ce sont deux théorèmes distincts.
Les lois de De Morgan : nier correctement
Pour nier une proposition composée :
- non (P et Q) équivaut à (non P) ou (non Q) ;
- non (P ou Q) équivaut à (non P) et (non Q) ;
- non (P ⇒ Q) équivaut à P et (non Q).
Les quantificateurs
| Symbole | Lecture | Exemple |
|---|---|---|
| ∀ | « pour tout », « quel que soit » | ∀x ∈ ℝ, x² ≥ 0 (vrai) |
| ∃ | « il existe (au moins un) » | ∃x ∈ ℝ, x² = 2 (vrai : √2) |
| ∃! | « il existe un unique » | ∃! x ∈ ℝ, 2x + 1 = 7 (vrai : 3) |
Nier une proposition quantifiée : on échange ∀ et ∃ et on nie la propriété.
- La négation de « ∀x, P(x) » est « ∃x, non P(x) » : pour montrer qu’une affirmation universelle est fausse, il suffit d’un contre-exemple.
- La négation de « ∃x, P(x) » est « ∀x, non P(x) ».
L’ordre compte : « ∀x, ∃y, y > x » (pour tout nombre, il en existe un plus grand) est vrai dans ℕ ; « ∃y, ∀x, y > x » (il existe un nombre plus grand que tous les autres) est faux.
Les principaux types de raisonnement
| Raisonnement | Principe | Exemple typique |
|---|---|---|
| Direct | on déduit Q de P par une suite d’implications | montrer que la somme de deux nombres pairs est paire |
| Par contraposée | pour prouver P ⇒ Q, on prouve non Q ⇒ non P | si n² est pair, alors n est pair |
| Par l’absurde | on suppose le contraire de ce qu’on veut prouver et on aboutit à une contradiction | √2 est irrationnel (voir nombres irrationnels) ; il y a une infinité de nombres premiers |
| Par contre-exemple | un seul cas suffit à réfuter une affirmation universelle | « tout nombre impair est premier » est faux : 9 |
| Par récurrence | on prouve P(0), puis que P(n) entraîne P(n + 1) ; alors P est vraie pour tout entier | 1 + 2 + … + n = n(n + 1)/2 |
| Par disjonction de cas | on examine séparément tous les cas possibles | n(n + 1) est pair : n pair ou n impair |
Ces raisonnements déductifs garantissent la vérité de la conclusion si les prémisses sont vraies, à la différence de l'induction des sciences expérimentales, qui généralise à partir d’observations (voir induction et déduction et méthode scientifique).
Condition nécessaire, condition suffisante
Si P ⇒ Q est vraie :
- P est une condition suffisante pour Q : il suffit que P soit vraie pour que Q le soit ;
- Q est une condition nécessaire pour P : il faut que Q soit vraie pour que P puisse l’être.
« Être un carré » est une condition suffisante pour « être un rectangle », et « être un rectangle » une condition nécessaire pour « être un carré ». Quand P ⇔ Q, la condition est nécessaire et suffisante.
Une brève histoire
- IVe siècle av. J.-C. : Aristote fonde la logique avec la théorie du syllogisme (« Tous les hommes sont mortels ; Socrate est un homme ; donc Socrate est mortel »).
- 1847-1854 : l’Anglais George Boole traite les raisonnements comme des calculs algébriques sur des valeurs 0 et 1 : c’est l'algèbre de Boole, base des circuits électroniques.
- 1879 : l’Allemand Gottlob Frege crée la logique des prédicats, avec les quantificateurs.
- 1901 : Bertrand Russell découvre un paradoxe dans la théorie naïve des ensembles (l’ensemble de tous les ensembles qui ne se contiennent pas eux-mêmes), qui oblige à refonder les mathématiques sur des axiomes précis.
- 1931 : Kurt Gödel démontre ses théorèmes d’incomplétude : dans tout système d’axiomes cohérent assez riche pour contenir l’arithmétique, il existe des énoncés vrais qu’on ne peut pas démontrer, et le système ne peut pas prouver sa propre cohérence.
- 1936 : Alan Turing définit mathématiquement ce qu’est un calcul et montre que certains problèmes sont indécidables par une machine (voir test de Turing et histoire de l’informatique).
Questions fréquentes
Quelle est la différence entre réciproque et contraposée ?
La réciproque de « P ⇒ Q » est « Q ⇒ P », qui peut être fausse même si l’implication est vraie. La contraposée est « non Q ⇒ non P », qui a toujours la même valeur de vérité que l’implication.
Comment montrer qu’une affirmation est fausse ?
Si elle est universelle (« pour tout… »), il suffit d’un contre-exemple. Sinon, on démontre sa négation.
Le « ou » en mathématiques est-il exclusif ?
Non, il est inclusif : « P ou Q » est vrai si P est vraie, si Q est vraie, ou si les deux le sont.
Qu’a démontré Gödel ?
Qu’aucun système d’axiomes cohérent capable d’exprimer l’arithmétique ne peut démontrer tous les énoncés vrais de l’arithmétique, ni prouver sa propre cohérence.