QUE SAIS-JE ?

La logique

PIERRE WAGNER

Maître de conférences à l’université Paris-I

Panthéon-Sorbonne

Deuxième édition mise à jour

4e mille

Remerciements

Tous mes remerciements aux amis et collègues qui ont accepté de lire une première version de ce livre. Leurs commentaires m’ont permis d’apporter de nombreuses améliorations au texte initial.

Bibliographie thématique « QUE SAIS-JE ? »

Dominique Lecourt, La Philosophie des sciences, n° 3624.

Jean-Paul Resweber, La Philosophie du langage, n° 1765.

Pierre Oléron, Le Raisonnement, n° 1671.

Jean-Michel Besnier, Les Théories de la connaissance, n° 3752.

Patrice Hernert, Les Algorithmes, n° 2928.

978-2-13-060984-1

Dépôt légal – 1re édition : 2007

2e édition mise à jour : 2011, mars

© Presses Universitaires de France, 2007
6, avenue Reille, 75014 Paris

Chapitre I

La logique : directions, orientation

Qu’est-ce que la logique ? Quel est son objet ? Quelles sont sa fonction, ses frontières, son histoire ? Sur ces questions, il existe des opinions diverses dont plusieurs sont assez largement répandues.

Pour les uns, la logique est la science du raisonnement correct. Non une science empirique qui aurait pour objet de recenser, décrire et analyser les raisonnements réels, qu’ils soient écrits, exprimés verbalement ou pensés, mais une science des règles que tout raisonnement doit respecter afin d’être valide. À supposer qu’il existe de telles règles et que la logique en soit la science, elle est beaucoup plus qu’une science parmi les sciences. Car son but est alors d’étudier les présupposés communs à toutes les connaissances auxquelles on accède au moyen du raisonnement. Ainsi comprise, la logique n’a pas pour seule fonction de contrôler la validité des inférences ; elle a également pour tâche de structurer l’ensemble de notre savoir. Aussi lui accorde-t-on parfois une fonction constitutive pour la connaissance en général et pour notre système du monde.

Pour d’autres, la logique énonce les lois les plus générales de la pensée, en tant que celle-ci vise le vrai. Indépendantes de tout contenu, de tout objet particulier, ces lois valent alors non seulement pour tout ce qui est, mais également pour tout ce qui peut être pensé en général. Le principe du tiers exclu, par exemple, comme toutes les autres vérités logiques, s’applique à tout énoncé : selon ce principe, soit l’énoncé lui-même, soit sa négation est vrai. Soit il pleut, soit il ne pleut pas, il n’y a pas de troisième possibilité. Selon un autre principe logique, le principe de non-contradiction, un énoncé et sa négation ne sont pas l’un et l’autre vrais. En sorte que si quelqu’un affirmait à la fois que le monde a une fin et que le monde n’a pas de fin, nous serions conduits à penser soit qu’il ne donne pas le même sens à « monde » ou à « avoir une fin » dans les deux énoncés, soit qu’il donne à l’expression « ne… pas », en cette occurrence, un sens différent du sens usuel.

Sur l’histoire de la logique voici ce qu’on entend souvent dire. La logique remonte à l’Antiquité, aux travaux d’Aristote et des stoïciens, et résulte d’un travail de codification des procédés d’argumentation et de raisonnement en usage à cette époque. Au Moyen Âge, elle a fait partie intégrante des études scolastiques, à côté de la rhétorique et de la grammaire. Au XVIIe siècle, Descartes a critiqué son caractère formel et sa stérilité alors que Leibniz a cherché à en faire une science générale, applicable à tous les raisonnements, ainsi qu’un art d’inventer pour trouver la vérité dans les sciences. Au XIXe siècle, des auteurs comme Boole ont commencé à lui appliquer les techniques de l’algèbre, avant que la crise des fondements des mathématiques ne précipite son évolution et ne lui fasse connaître une véritable révolution. Les pères fondateurs de la logique moderne – Frege, Peano, Russell et d’autres – ont alors fait d’elle une logique symbolique, d’une nature comparable à celle des mathématiques, dont elle a fini par constituer l’une des branches. Essentiellement orientée, dans la première moitié du XXe siècle, vers le problème du fondement des mathématiques, elle a ensuite trouvé des applications inattendues en informatique et dans l’étude des langues naturelles, domaines dans lesquelles elle fait aujourd’hui florès.

Jadis pensée et enseignée par les philosophes, la logique est donc, selon une opinion courante, devenue une science dont les théorèmes et les démonstrations sont tout aussi peu discutables que ceux de l’arithmétique ou de la géométrie, et son caractère technique la rend difficilement accessible au profane. Comme toute science, elle a ses revues spécialisées, sa communauté de scientifiques et ses programmes de recherche. La logique ainsi comprise est parfois divisée en quatre grandes orientations principales : la théorie de la démonstration, la théorie des modèles, la théorie des ensembles et la théorie de la calculabilité. Comme la plupart des sciences, ses bases sont exposées dans des manuels d’introduction dont les titres précisent, le plus souvent, qu’il y est question de la logique mathématique, symbolique ou formelle.

Que penser d’un tel tableau, qui regroupe quelques-unes des représentations les plus communes touchant la nature, la fonction et l’histoire de la logique ? Bien que les opinions de ce genre soient souvent exposées comme des vérités sur la logique, chacune soulève davantage de questions qu’elle n’apporte de réponse. Leur vraisemblance dépend tantôt de l’état des connaissances à une époque donnée, tantôt de convictions philosophiques qui méritent d’être discutées.

En parlant de la logique, par exemple, on sous-entend qu’elle possède une unité qui traverse l’histoire depuis l’Antiquité. Il existe certes une tradition logique dont certains auteurs font incontestablement partie ; mais on serait bien en peine de trouver une définition que chacun d’eux eût jugée acceptable. Aristote, Leibniz, Kant et Frege ne se sont pas seulement fait de la logique des idées très diverses ; ils ne la définissaient tout simplement pas à partir du même projet intellectuel. Aristote, du reste, utilisait l’adjectif logikos, mais il ne disposait d’aucun substantif pour désigner quelque chose comme la logique, et la question de savoir quels traités, parmi ceux dont il est l’auteur, il convient d’inclure dans ce que nous appelons « la logique aristotélicienne » n’est rien moins qu’évidente. Leibniz, pour sa part, ambitionnait de réaliser une langue logique qui permette non seulement de formaliser les raisonnements mais également de trancher les disputes métaphysiques et théologiques. Quant à la distinction kantienne entre logique formelle et logique transcendantale, elle trouve sa justification dans le projet d’une philosophie générale de la connaissance. Les travaux logiques de Frege ont un sens encore différent puisqu’ils ont pour origine le projet d’un fondement de l’arithmétique qui ferait l’économie de tout recours à l’intuition. La logique qu’on trouve aujourd’hui dans les manuels d’introduction, quant à elle, est extrêmement éloignée, par son esprit comme par son contenu, de la logique telle que la comprenait chacun des auteurs qu’on vient de citer.

Si, pour la recherche d’une définition de la logique et de son unité, on laisse maintenant de côté la perspective historique pour se tourner vers la logique contemporaine, on s’aperçoit rapidement que les questions suivantes sont parmi les plus controversées : y a-t-il une ou plusieurs logiques ? Y a-t-il un critère de la « logicité », c’est-à-dire de ce qui relève de la logique proprement dite, par opposition à ce qui tombe en dehors de son domaine ? Comment définir le concept fondamental de conséquence logique, qui met en relation les prémisses et la conclusion d’un raisonnement ? Sur la question de la définition de la logique, on ne peut donc certainement pas se satisfaire de la réponse naïve qui consisterait à dire que la logique, c’est ce que font les logiciens « professionnels », membres d’une même communauté scientifique car, d’une part, la question de savoir qui fait partie de cette communauté n’admet pas de réponse simple, et, d’autre part, ceux qui en font indiscutablement partie ne sont d’accord entre eux ni sur la définition de la logique, ni sur son unité, ni sur la nature du projet intellectuel qui oriente leur travail, ni même sur l’intérêt qu’il pourrait y avoir à délimiter clairement la province de la logique.

La logique est souvent définie comme la science de l’inférence formellement valide. Mais cette expression est tellement générale qu’elle ne nous apprend pratiquement rien tant qu’on n’a pas expliqué ce qu’on entend par « inférence », par « formel » et par « valide » et tant qu’on n’a pas dit à quoi pourrait ressembler une telle science. Or, il s’agit là de questions qui dépassent la logique en tant que science, car toute esquisse de réponse présuppose qu’une solution a déjà été apportée à d’autres problèmes touchant la pensée, le langage, le jugement, la signification, la psychologie ou l’esprit. La logique telle que la concevaient Descartes, Leibniz ou Kant était non seulement indissociable de leur philosophie de la connaissance mais également ancrée dans leur système philosophique tout entier.

Il pourrait sembler, à première vue, qu’il en va différemment de la logique telle qu’on la trouve introduite dans les ouvrages contemporains de logique mathématique car ceux-ci se présentent souvent comme l’exposé d’une science indépendante de tout engagement philosophique. En réalité, cela vient seulement de ce que la plupart de ces ouvrages évitent tout simplement de discuter ce genre de question ; tout au plus mentionnent-ils, dans quelques paragraphes liminaires, un ensemble de présupposés qu’ils demandent au lecteur d’accepter. Fort heureusement, tous les logiciens ne sont pas partisans de ce genre d’économie intellectuelle, et les fondateurs de la logique moderne ont même consacré des ouvrages entiers à des recherches logico-philosophiques par lesquelles ils exposaient et justifiaient les travaux et programmes dans lesquels ils s’engageaient. Ce que montrent ces textes, cependant, comme ceux des auteurs contemporains qui traitent des mêmes sujets, c’est qu’il n’existe pas, aujourd’hui, de conception de la logique sur laquelle la communauté des logiciens soit entièrement d’accord, pas de définition universellement acceptée. Il existe au contraire des opinions divergentes touchant son extension, son unité, son but et son orientation.

Corrélativement, l’époque contemporaine connaît une prolifération de ce qu’on appelle des logiques, auxquelles sont attribués des noms plus ou moins évocateurs : logique intuitionniste, logique modale, logique déontique, logique temporelle, logique quantique, logique pertinente, logique IF, etc. Elles se présentent souvent comme des systèmes de signes qui permettent de former des expressions, de leur donner une interprétation, de définir un concept de conséquence logique et surtout de formaliser certains types de raisonnements afin d’en caractériser les règles. Mais l’usage du mot « logique » au pluriel suggère que ce mot reçoit ici une signification différente de celle qu’il a lorsqu’il est question de la logique, car l’article défini suppose évidemment qu’il y en a une et non plusieurs. Lorsqu’on donne à cet article son sens le plus fort, on ne pense pas à un ensemble de techniques de formalisation des raisonnements dans des domaines circonscrits ; ce qui est visé, ce sont les règles qui, au-delà des apparences du langage ordinaire, structurent la pensée ou le système de nos connaissances. Il reste à savoir s’il existe effectivement de telles règles universelles – et dans ce cas, quelles sont ces règles – ou si les recherches logiques ainsi comprises ne relèvent pas d’un mythe universaliste.

S’il existe de telles différences de points de vue et de sens, comment la logique peut-elle être couramment considérée comme une science, qui plus est comme l’une des branches de la science la plus assurée de toutes : les mathématiques ? Paradoxalement, l’absence d’accord sur la définition de la logique, sur son orientation générale et ses principes fondamentaux n’enlève rien au caractère scientifiquement contraignant des théorèmes qu’elle démontre, qui ne sont pas moins certains que des théorèmes mathématiques. Il existe effectivement quelque chose comme une doctrine logique commune dont la plupart des manuels exposent les concepts, les techniques et les résultats de base sous des formes variables. On y trouve généralement une définition de ce que les logiciens entendent aujourd’hui par variable, constante, connecteur, quantificateur, relation, fonction, formule, axiome, système formel, dérivabilité formelle, structure d’interprétation, vérité dans une structure, satisfaisabilité, théorie formelle, modèle d’une théorie, conséquence logique, cohérence, complétude, compacité, décidabilité, définissabilité, syntaxe, sémantique, métalangage, logique du premier ordre, logique d’ordre supérieur, pour ne citer que quelques-uns des concepts de base de la logique contemporaine ; on y trouve également la démonstration d’une série de théorèmes fondamentaux : théorèmes de complétude, de compacité, de Löwenheim-Skolem, etc. Mais que penser d’un tel appareillage conceptuel, si hautement technique ? Est-il de nature à répondre aux questions que nous nous posons touchant ce qu’est fondamentalement la logique ?

D’un côté, les résultats qui ont été obtenus en logique mathématique par la voie démonstrative laissent ouvertes un grand nombre de questions, notamment celles qui sont relatives à l’unité de la logique, à son fondement, à sa fonction dans le système du savoir ou à l’interprétation épistémologique des vérités logiques ; d’un autre côté, ces résultats sont si contraignants qu’ils ont effectivement mis en échec les conceptions de la logique qui avaient été défendues par certains des plus grands logiciens ; on pense au logicisme de Frege, à celui de Russell, ainsi qu’au programme de Hilbert dont la réalisation possible fut rendue extrêmement peu vraisemblable par les théorèmes d’incomplétude que Gödel publia en 1931. Aucune réflexion sur la logique ne peut donc ignorer les développements techniques de la logique contemporaine, bien qu’une connaissance de ces développements ne suffise certainement pas à répondre à toutes les questions susceptibles d’être soulevées relativement à ce qu’est la logique.

Ces quelques remarques devraient suffire à convaincre le lecteur qu’il est aujourd’hui difficile de prétendre connaître ne serait-ce qu’une petite partie de la logique si l’on ne maîtrise pas au moins certains de ses concepts de base et si l’on ignore tout de résultats comme les théorèmes de complétude, d’incomplétude, de compacité, de Löwenheim-Skolem, d’indécidabilité et d’indéfinissabilité du prédicat de vérité, pour ne citer que quelques exemples, parmi les plus fondamentaux. D’un autre côté, une étude non critique des bases de la logique mathématique dans un manuel qui en introduit les concepts, les méthodes et les théorèmes ne permet généralement pas d’apercevoir ce qui fait de la logique une discipline non seulement ouverte, vivante et féconde, mais également indéterminée dans sa définition, sa signification et son orientation générale.

Dans ce livre, nous n’aurons l’ambition ni de donner une définition dogmatique de la logique, ni d’ajouter, sur cette question, une nouvelle opinion à celles qui existent déjà. Il ne s’agit pas non plus d’une introduction à la logique mathématique, ni d’une histoire de la logique des origines à nos jours. Nous nous proposons plutôt de donner au lecteur une idée du genre de questions que se posent ou que se sont posés les logiciens, du genre de certitudes qu’ils ont acquises, des projets qui animent leurs recherches, des problèmes sur lesquels ils s’opposent et des raisons pour lesquelles il n’est pas facile de s’entendre sur ce qu’est la logique. On aura compris qu’un tel programme exige l’impossible : sans présupposer aucune connaissance de la part du lecteur, sans l’entraîner non plus dans une exposition formelle des techniques que les logiciens ont mises au point ou des résultats que leurs méthodes leur ont permis d’obtenir, lui donner une idée aussi précise que possible des bases de la logique contemporaine et de ses origines historiques, afin qu’il puisse distinguer quelques-unes des certitudes acquises et des questions ouvertes, et s’interroger lui-même sur ce qu’il est permis d’entendre par « logique ». L’exposition rigoureuse des concepts et théorèmes fondamentaux de la logique contemporaine exigerait un degré de précision et donc une prolixité qu’il est impossible de satisfaire dans un ouvrage de cette nature, qui n’a pas pour vocation de se substituer aux ouvrages d’introduction à la logique proprement dits¹.

On ne pourra évidemment pas discuter tous les usages qui sont faits du mot « logique » aujourd’hui, et certains de ces usages seront délibérément ignorés, par exemple dans des expressions comme « logique de l’économie de guerre », « logique de la découverte scientifique » ou même « logique inductive ». L’examen de ces différents cas, comme celui de bien d’autres, nous entraînerait dans des questions particulières trop éloignées de la logique en général. On ne pourra pas non plus espérer donner un panorama de l’ensemble des recherches qui sont menées dans la logique contemporaine. Nous présenterons tout au plus quelques questions choisies parmi celles qui peuvent être rendues accessibles au néophyte en un nombre limité de pages, en commençant par quelques-unes des transformations qui ont conduit à la logique contemporaine. Les concepts et théorèmes qui seront introduits appartiennent tous aux connaissances communes des logiciens contemporains. Sans qu’il soit question d’en retracer l’histoire, nous prenons le parti d’indiquer, autant qu’il est possible, le contexte dans lequel ils se sont imposés comme tels.

Malgré toutes les réserves qui ont été émises dans ce premier chapitre, nous n’hésiterons pas à faire précéder le mot « logique » de l’article défini, en gardant présent à l’esprit que ce présupposé d’unicité n’est rien moins que problématique.

Chapitre IV

Vérité, conséquence logique, théorie des modèles

Après les travaux de Gödel sur la complétude sémantique et l’incomplétude syntaxique, la distinction entre syntaxe et sémantique s’est imposée comme l’une des plus fondamentales en logique, alors qu’elle n’était pas clairement perçue comme telle auparavant. Dans son orientation syntaxique, la logique conduit à la théorie de la démonstration, à l’étude des propriétés des preuves et des systèmes de dérivation formelle ; dans son orientation sémantique, à la théorie des modèles, à l’étude des structures d’interprétation des langages, au concept d’énoncé vrai dans une structure, et à l’étude des relations entre des ensembles d’énoncés et les structures d’interprétation qui rendent ces énoncés vrais.

La formalisation de l’arithmétique telle que l’avait conçue Frege ne reposait nullement sur l’opposition entre syntaxe et sémantique. Cette opposition appelait en effet une distinction entre langage et métalangage que le point de vue universaliste excluait. Pour Frege, cette opposition n’était donc pas tant inutile que dépourvue de sens. Les axiomes du système frégéen devaient être vrais, chaque nouvelle étape d’une démonstration devait préserver la vérité des propositions précédentes et le système dans son ensemble devait permettre de prouver formellement tous les théorèmes de l’arithmétique. Contrairement à Frege, Hilbert adoptait ce qu’on allait nommer ultérieurement le « point de vue syntaxique », écartant le point de vue sémantique qui contredisait les exigences finitistes de la métamathématique. Il espérait pouvoir construire un système formel non interprété, adéquat pour l’arithmétique, et dont on puisse prouver qu’il était cohérent et complet. Les théorèmes d’incomplétude syntaxique mirent cependant en évidence que les concepts syntaxiques de preuve (« … est démontrable ») et de dérivation formelle (« … est formellement dérivable à partir de… ») ne pouvaient pas servir de substituts aux concepts sémantiques de vérité (« … est vrai ») et, respectivement, de conséquence logique (« … est conséquence logique de… »). Ces théorèmes montrent en effet que, dans tout système formel cohérent (dans lequel une partie de l’arithmétique est formalisable), il existe des formules indémontrables qui représentent pourtant des énoncés vrais. En ce sens précis, le concept sémantique de vérité n’a pas la même extension que le concept syntaxique de démontrabilité. Par ailleurs, une propriété des entiers naturels, exprimable par une formule φ[x] où x est une variable libre, peut être formellement démontrable pour n’importe quel entier n sans que ∀xφ[x] le soit, bien que d’un point...