francebalade.fr Cours de Mathématiques Table des matières Votre avis sur ce site

Logique

Comment la logique est devenue une branche des mathématiques

Pendant plus de vingt siècles, la logique fut une discipline de philosophes : l’art de bien raisonner avec des mots. À partir du milieu du XIXᵉ siècle, et surtout entre 1879 et 1931, elle adopte le langage, les méthodes et la rigueur du calcul mathématique. Cinq planches pour voir ce changement se produire, chiffres à l’appui.

Une même phrase, écrite dans quatre langages

L’idée en une phrase : la logique est devenue mathématique le jour où l’on a cessé de discuter des raisonnements pour les écrire avec des symboles et les calculer. Prenons la phrase « Tous les A sont B » et regardons comment chaque époque l’écrit.

Le point lumineux parcourt les quatre écritures : chacune est plus précise que la précédente, et se prête à un nouveau genre de démonstration.

Ce qui change, concrètement

	Avant : logique philosophique	Après : logique mathématique
Langage	mots de tous les jours, parfois ambigus	symboles, formules, règles d’écriture précises
Méthode	argumentation, exemples, autorité	calcul, définitions, démonstrations vérifiables ligne à ligne
Objet d’étude	l’art de raisonner en général	des objets mathématiques : formules, preuves, théories, modèles
Question typique	« ce raisonnement est-il convaincant ? »	« cet énoncé est-il démontrable ? combien y a-t-il de formules ? »
Juge de la rigueur	le jugement du lecteur	une vérification qu’une machine peut faire

Une précision d’historien. Le basculement n’a pas de date unique. Boole et De Morgan l’amorcent en 1847, Frege lui donne un langage en 1879, Peano, Dedekind et Cantor lui fournissent les objets entre 1874 et 1889, Hilbert, Russell et Gödel l’achèvent autour de 1900–1931. Dire « fin du XIXᵉ siècle » est donc juste : c’est le moment où le mouvement devient irréversible.

Planche 1

Avant : la logique des mots (Aristote)

Question : comment décider qu’un raisonnement écrit en langage courant est correct ? Aristote (IVᵉ siècle av. J.-C.) invente la réponse : le syllogisme, trois phrases (deux prémisses, une conclusion) dont il n’existe que quatre types.

Les quatre phrases permises : A « Tous les X sont Y » · E « Aucun X n’est Y » · I « Certains X sont Y » · O « Certains X ne sont pas Y ». Le moyen terme M figure dans les deux prémisses et disparaît de la conclusion, qui relie S (le sujet) à P (le prédicat). Selon la place de M, il y a quatre figures. En tout : 4 × 4 × 4 × 4 = 256 formes possibles.

Critère de correction : la forme est valide si la conclusion est vraie chaque fois que les prémisses le sont, quel que soit le sens de S, M, P. Pour le tester, on regarde tous les « mondes » possibles : chacune des sept régions des trois cercles du diagramme de Venn est soit habitée, soit vide : cela fait 2⁷ = 128 mondes.

Exemple

Figure

Majeure

Mineure

Conclusion

256formes possibles (4×4×4×4)

24valides chez Aristote (termes non vides)

15valides sans cette hypothèse (lecture moderne)

—verdict de la forme choisie

Les 24 formes valides, par figure

Chaque nom médiéval encode la forme : les voyelles donnent A, E, I, O des trois phrases (Barbara = AAA). Pointillé orange : la forme n’est valide que si les termes désignent des choses qui existent.

Ce qu’il faut retenir. Déjà chez Aristote, la validité ne dépend que de la forme : c’est l’idée fondatrice de la logique formelle. Mais l’outil reste étroit : quatre phrases, des mots, aucun calcul. Augustus De Morgan le montre au XIXᵉ siècle avec un exemple resté célèbre : de « tous les chevaux sont des animaux », on conclut que « toute tête de cheval est une tête d’animal ». Aucun syllogisme ne peut l’écrire, car il faut une relation (« être la tête de »). Il faudra un autre langage.

Planche 2

1847 : Boole met la logique en équations

Question : peut-on calculer un raisonnement comme on résout une équation ? George Boole (1847, puis 1854) répond oui. Il note par une lettre une classe (par exemple les hommes) et par 1 ce qui est vrai, 0 ce qui est faux. Sa loi centrale s’écrit x² = x : une chose est « dans » la classe (1) ou n’y est pas (0), et il n’y a rien entre les deux.

A. La loi x² = x n’a que deux solutions

Bleu : y = x². Rouge : y = x. Elles se coupent exactement en deux points : x = 0 et x = 1. Ce sont les deux « valeurs de vérité ».

x =0,50

0,50x

0,25x²

−0,25x² − x (nul seulement en 0 et en 1)

0 et 1solutions trouvées par balayage puis dichotomie

Toute équation qui ne fait intervenir que 0 et 1 est donc de la logique. Les opérations deviennent des opérations sur les nombres : ET = ab, NON = 1 − a, OU = a + b − ab. Et l’on a le droit de simplifier avec x² = x.

B. Toute fonction logique est un polynôme

Idée : une fonction de trois valeurs de vérité (a, b, c) est déterminée par ses 8 valeurs. Chaque possibilité est un sommet d’un cube. Cliquez sur les sommets pour choisir ceux où la fonction vaut 1 : l’ordinateur écrit le polynôme de Boole correspondant.

Un sommet plein = la fonction vaut 1 ; creux = 0. Les trois bits près d’un sommet se lisent « abc ».

Fonction n°128

ab·cpolynôme de Boole (x² = x)

8 / 8lignes où le polynôme redonne la table

—contrôle exhaustif des 256 fonctions

C. Démontrer par le calcul

Idée : « Tous les A sont B » s’écrit a(1 − b) = 0 (« être A sans être B » n’arrive jamais). Une conclusion se démontre alors comme une identité entre polynômes : on ne discute plus, on développe.

Raisonnement

—lignes où les deux prémisses valent 0

—… dont la conclusion vaut 0 aussi

—contre-exemple(s)

—accord avec la méthode des mondes (planche 1)

Ce qui a changé. Chez Aristote, on reconnaissait une forme valide dans une liste mémorisée. Chez Boole, on la démontre en calculant, et le même calcul traite d’un coup des raisonnements que la liste ne contenait pas. Le raisonnement est devenu de l’algèbre ; la logique, un chapitre des mathématiques.

Planche 3

1879 : Frege invente un langage formel

Question : qu’est-ce qui rend une écriture « rigoureuse » ? Gottlob Frege publie en 1879 son Begriffsschrift (« écriture des concepts ») : un langage artificiel où chaque formule a une structure sans ambiguïté, où les quantificateurs (∀ « pour tout », ∃ « il existe ») permettent d’écrire les relations que les syllogismes ne savaient pas dire, et où démontrer devient appliquer des règles écrites d’avance. Sa notation, dessinée en deux dimensions, ressemble d’ailleurs à un arbre.

A. Une formule est un arbre, sa vérité se calcule de bas en haut

Idée : dans un langage formel, on sait toujours si une suite de signes est une formule « bien formée », et on peut en calculer la valeur sans rien interpréter. Écrivez une formule avec p, q, r et les signes ¬ (non), ∧ (et), ∨ (ou), → (implique), ↔ (équivaut).

Exemples

Valeurs des variables :

Vert : vrai. Rouge : faux. Gris : pas encore calculé. Le calcul part des feuilles (les variables) et remonte vers la racine.

ouiformule bien formée

—valeur de la racine (pour les valeurs choisies)

—lignes vraies de la table

—nature de la formule

—contrôle par un calcul indépendant

B. Une démonstration est une suite finie de lignes que l’on vérifie mécaniquement

Idée : dans un système formel, chaque ligne est soit un axiome (une formule admise), soit une hypothèse, soit obtenue par la règle du modus ponens : de A et de A → B, on tire B. Le vérificateur ci-dessous n’écoute pas les justifications proposées : il reconstitue lui-même si chaque ligne est licite. Puis il contrôle, par une table de vérité, que chaque ligne est bien une conséquence des hypothèses.

Axiome 1 : A → (B → A). Axiome 2 : (A → (B → C)) → ((A → B) → (A → C)). Ici A, B, C sont des formules quelconques, que le vérificateur repère lui-même.

Démonstration

0 / 5lignes examinées

0lignes licites (règle respectée)

0lignes conséquences des hypothèses (table de vérité)

—verdict

Ce qu’a apporté Frege. Pour la première fois, la question « cette démonstration est-elle correcte ? » a une réponse qui ne dépend d’aucune intuition : on regarde les lignes une à une. Et la question « est-ce vrai ? » (table de vérité) est séparée de la question « est-ce démontrable ? » (suite de lignes). Que les deux coïncident pour cette logique est un théorème à démontrer, pas une évidence.

Planche 4

1888–1889 : Dedekind et Peano, les nombres deviennent un calcul sur des signes

Question : peut-on démontrer que 2 + 2 = 4 sans savoir ce qu’est « un nombre » ? Dedekind (1888) et Peano (1889) proposent quelques axiomes : il y a un nombre 0 ; chaque nombre a un successeur S ; 0 n’est le successeur de rien ; deux nombres de même successeur sont égaux ; et un axiome de récurrence. Tout le reste, y compris l’addition et la multiplication, se définit par deux lignes chacune :

A1 x + 0 = x · A2 x + S(y) = S(x + y) · M1 x · 0 = 0 · M2 x · S(y) = x · y + x

A. Calculer, c’est réécrire

Idée : le nombre 3 est simplement S(S(S(0))). Pour calculer, on applique les quatre règles jusqu’à ce qu’il ne reste plus que des S et un 0. Aucun résultat n’est « su à l’avance » : tout sort des règles. Choisissez deux nombres et regardez la machine travailler.

a =3

b =2

Opération

Chaque arc est un pas « successeur ». Pour a + b : b pas à partir de a. Pour a · b : b bonds de longueur a à partir de 0.

—résultat obtenu par réécriture

—valeur attendue (calcul de la machine)

—règles appliquées

—prévision par formule

—contrôle exhaustif

B. Vérifier une infinité de cas n’est pas démontrer

Idée : la propriété « 0 + n = n » ne découle pas directement des règles A1 et A2 (elles simplifient à droite : x + 0, pas 0 + x). Chaque cas particulier se vérifie en n + 1 réécritures, mais « pour tout n » demande l’axiome de récurrence.

n =12

—réécritures pour 0 + Sⁿ(0)

—résultat

—cas vérifiés un à un

Démonstration par récurrence, en deux lignes.
Base : 0 + 0 = 0 (règle A1).
Hérédité : si 0 + n = n, alors 0 + S(n) = S(0 + n) (règle A2) = S(n) (hypothèse).
L’axiome de récurrence conclut : 0 + n = n pour tous les n, y compris ceux qu’aucun ordinateur n’a testés.

Ce qui a changé. Avant Dedekind et Peano, on croyait connaître les nombres par intuition. Ici, les entiers sont une structure décrite par des axiomes, et l’arithmétique un jeu de règles sur des signes : exactement ce qu’il faut pour qu’une logique formelle (planche 3) puisse en parler et qu’on puisse se demander, plus tard, ce que ces règles permettent ou non de démontrer. Whitehead et Russell iront jusqu’à construire, dans les Principia Mathematica (1910–1913), une chaîne de plusieurs centaines de pages avant d’établir 1 + 1 = 2.

Planche 5 · signature

1931–1936 : la logique se retourne sur elle-même

Question : une fois la logique devenue mathématique, peut-on démontrer des théorèmes sur la logique elle-même ? Oui, et c’est là que se voit le mieux la rupture avec la philosophie. Hilbert appelle ce projet la métamathématique : étudier, avec des méthodes mathématiques, ce que peuvent et ne peuvent pas faire les systèmes de preuve. Trois expériences.

Idée : Gödel (1931) attribue à chaque signe un numéro, puis à chaque suite de signes un nombre unique : on met le k-ième signe en exposant du k-ième nombre premier et l’on multiplie. Comme un entier se décompose d’une seule façon en facteurs premiers, on retrouve la formule à partir du nombre. Les formules deviennent des nombres ; les énoncés sur les formules deviennent des énoncés d’arithmétique. C’est le pivot de toute la suite.

Cliquez pour écrire une formule (20 signes au plus) :

Exemples

—la formule

—signes

—chiffres du nombre de Gödel

—décodage du nombre

Décomposition :

Décoder un nombre :

—mots tirés au hasard, décodés à l’identique

—collisions (deux mots, même nombre)

—codes de la table à 17 signes

Pourquoi c’est une révolution. Un système formel qui contient l’arithmétique peut désormais parler de ses propres formules et de ses propres démonstrations, puisque « est le code d’une formule » et « est le code d’une démonstration correcte » deviennent des propriétés de nombres, vérifiables par calcul. La porte est ouverte à l’auto-référence, sans aucun paradoxe de mots.

Idée : le jeu MIU de Douglas Hofstadter (Gödel, Escher, Bach, 1979) est un mini système formel. Un seul axiome : le mot MI. Quatre règles : 1 un mot fini par I peut recevoir un U ; 2 Mx devient Mxx ; 3 III peut être remplacé par U ; 4 UU peut être supprimé. Question : peut-on obtenir MU ? Vous pouvez essayer à la main. Vous n’y arriverez pas, et l’on peut démontrer pourquoi.

Coups possibles depuis le mot courant :

Historique :

Exploration exhaustive : tous les mots atteignables, classés par le reste du nombre de I dans la division par 3. Le reste 0 reste vide.

Longueur maximale explorée12

—nombre de I du mot courant

—reste dans la division par 3 (jamais 0)

—mots atteignables (longueur ≤ maximale)

—mots dont le nombre de I est multiple de 3

—MU parmi eux ?

Le théorème sur le système. Le nombre de I d’un mot atteignable n’est jamais multiple de 3. Preuve : au départ il vaut 1. La règle 1 et la règle 4 ne le changent pas ; la règle 2 le double (si n n’est pas multiple de 3, 2n non plus) ; la règle 3 le diminue de 3. Le reste modulo 3 ne devient jamais 0. Or MU contient zéro I, qui est multiple de 3 : MU n’est atteignable à aucune longueur. L’exploration ci-dessus vérifie ce théorème sur tous les mots atteignables jusqu’à la longueur choisie (plusieurs dizaines de milliers à la longueur 22) ; la preuve le démontre pour tous. Cette démarche, raisonner de l’extérieur sur un système de signes, est celle de la métamathématique. (Le théorème de Gödel est d’une autre profondeur : il s’applique à l’arithmétique tout entière.)

Idée : en 1936, Alonzo Church et Alan Turing démontrent qu’aucune méthode mécanique ne peut décider, pour tout programme et toute donnée, si le programme finira par s’arrêter. Turing le prouve en imaginant une « machine » (aujourd’hui : un programme) et un argument diagonal. Avant de regarder cet énoncé de loin, regardez de près un tout petit programme dont personne ne sait dire s’il s’arrête pour toutes les données : la suite de Collatz. On part de n ; si n est pair on divise par 2, sinon on calcule 3n + 1 ; on s’arrête en arrivant à 1.

n =27

—étapes avant d’atteindre 1

—valeur maximale atteinte

—départs de 1 à 100 000 : tous ont atteint 1

—départ le plus long ≤ 100 000

—contrôle des valeurs connues

Trajectoire du nombre choisi (échelle logarithmique) : des montées brusques, puis la chute vers 1.

Ce que cela illustre, et ce que cela ne prouve pas. Aucun départ testé n’a jamais échappé à 1, y compris parmi des nombres de l’ordre de 10²⁰ testés par ordinateur, et pourtant personne ne sait le démontrer pour tous les n. Cet exemple n’est pas la preuve du théorème de Turing : il montre seulement, sur un cas concret, la différence entre « vérifier jusqu’ici » et « démontrer pour tous ». Ce que Turing établit est plus fort : il n’existera jamais de procédé général qui réponde à coup sûr à la question « s’arrête-t-il ? » pour tous les programmes. Avec Gödel, cela fixe des limites précises à ce que la logique formelle peut faire, et ces limites sont elles-mêmes des théorèmes.

Frise : vingt-trois siècles en onze étapes

IVᵉ s. av. J.-C. AristoteLe syllogisme : la validité tient à la forme, pas au contenu. La logique est une discipline philosophique.

XVIIᵉ siècle LeibnizRêve d’un calcul du raisonnement : « calculons ! », dirait-on pour trancher une dispute. Il ne le réalise pas.

1847–1854 Boole, De MorganLa logique devient une algèbre : x² = x, ET, OU, NON s’écrivent comme des opérations.

1874–1897 CantorLa théorie des ensembles et l’infini actuel : de nouveaux objets, que la logique va devoir décrire.

1879 FregeLe Begriffsschrift : langage formel, quantificateurs, démonstration comme suite de lignes contrôlables.

1888–1889 Dedekind, PeanoLes entiers décrits par des axiomes ; addition et multiplication définies par récurrence.

1900 HilbertParmi ses 23 problèmes : prouver la cohérence de l’arithmétique. La question « le système ne se contredit-il jamais ? » devient centrale.

1902–1908 Russell, ZermeloLe paradoxe de Russell ébranle le système de Frege ; Zermelo répond par des axiomes pour les ensembles.

1910–1913 Whitehead et RussellPrincipia Mathematica : tenter de tout déduire de la logique, en symboles.

1930–1931 GödelThéorème de complétude (1930) puis d’incomplétude (1931) : les limites de la démonstration formelle, démontrées.

1936 Church, TuringLe calcul lui-même devient un objet de théorème : ce qui est calculable, et ce qui ne l’est pas.

Synthèse : trois marques de la logique mathématique

Un langage

Des symboles et une grammaire précise, de Boole (1847) à Frege (1879). Une formule est un objet que l’on peut compter, dessiner en arbre, coder par un nombre.

Une méthode

Le calcul et la démonstration formelle : une preuve est une suite finie de lignes, chacune vérifiable à part. On peut la contrôler sans la comprendre, comme on vérifie une addition.

Des théorèmes sur la logique

Une fois la logique traitée comme objet mathématique, on démontre des résultats sur ce qu’elle peut faire : complétude, incomplétude, indécidabilité. Aujourd’hui on y distingue quatre grands chapitres : théorie des ensembles, théorie des modèles, théorie de la démonstration, théorie de la calculabilité.

Pour aller plus loin

Dans la même série : les pages sur la logique et les ensembles (tables de vérité, quantificateurs), sur les fondements et le paradoxe de Russell, sur les ensembles infinis et l’argument diagonal de Cantor, et les deux pages sur les modes de raisonnement (récurrence, absurde).

Lectures : Jean van Heijenoort (éd.), From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 ; Ernest Nagel et James Newman, Le théorème de Gödel ; Douglas Hofstadter, Gödel, Escher, Bach.