La logique : un instrument théorique pour des problèmes pratiques.

Un articlerepris du blog binaire, une publication sous licence CC by

Le mot « logique » en grec ancien signifiait « mot » et « raison » et était utilisé pour désigner l’art de construire des formes de raisonnement correctes (« he logike Aristoteles Louvre.jpgtechnè »). Dans la Grèce antique, l’objectif de la logique d’Aristoteétait « l’élaboration d’un système cohérent […] pour enquêter, classer et évaluer les bonnes et les mauvaises formes de raisonnement« . Vers 1600, Bacon a déclaré que « la logique diffère de la rhétorique … en cela, que la logique de la raison raisonne exactement et en vérité, et la rhétorique la manipule telle qu’elle est implantée dans les opinions et les manières populaires ».

Depuis plus de 2000 ans, la logique est essentiellement utilisée pour « modéliser des arguments exprimés en langage naturel » et pour formaliser le raisonnement : c’est-à-dire que le rôle de la logique est de fournir un moyen de répondre aux ambiguïtés qui surgissent lorsque nous utilisons notre langage. Par exemple, si je dis « je vois un homme sur la colline avec un télescope », cela signifie que j’utilise un télescope pour voir l’homme, ou bien que je vois un homme sur la colline, qui a un télescope : l’utilisation de la logique peut nous permettre de lever cette ambiguïté. On peut probablement résumer cette vision de la logique en disant que la logique peut être un instrument pour fournir un langage bien formalisé et partagé pour élaborer des pensées complexes et pour identifier des formes de raisonnement correctes (et incorrectes).

C’est au XIXe siècle que la logique a considérablement évolué : les travaux de Gottlob Frege et George Boole ont commencé à dessiner les bases formelles de la logique. Ces fondations sont fournies en utilisant le langage des mathématiques : Boole et Frege sont tous deux des philosophes et des mathématiciens. La naissance de la discipline de la logique mathématique peut probablement être attribuée à cette période historique. Encore aujourd’hui, la logique est enseignée en mathématiques, dès l’école primaire, et la logique est également l’un des principaux cours enseignés dans les cursus universitaires de philosophie.

C’est une révolution, vers la fin du XIXe siècle, Frege et autres mathématiciens et philosophes ont proposé un nouveau véhicule pour la logique : au lieu d’essayer de formaliser le raisonnement en langage naturel, ils ont commencé à formaliser le raisonnement avec un langage et au sein mathématique. Cela peut sembler évident pour nous aujourd’hui, parce que nous utilisons la logique pour raisonner sur les mathématiques dès le plus jeune âge, et on utilise quotidiennement la logique si nous écrivons des logiciels. Toutefois, au début du XXe siècle, cette approche était nouvelle et au tout début du XXe siècle, David Hilbert a publié une liste de problèmes, dont l’un était : « Prouvez que les axiomes de l’arithmétique sont cohérents » (vous pouvez considérer la cohérence comme une propriété qui dit « vous ne pouvez pas déduire de contradictions des axiomes »). Le but ici était de fournir une caractérisation de l’arithmétique basée uniquement sur la logique. Et … ce fut une tragédie !

Entre 1930 et 1931, Kurt Gödel a démontré deux théorèmes, appelés théorèmes d’incomplétude de Gödel (à droite), qui se sont révélés catastrophiques pour les objectifs de Frege et le programme de Hilbert. Le premier théorème montre que si un système d’axiomes pour l’arithmétique est cohérent, alors il n’est pas complet. Cela signifie que pour chaque énoncé, ni l’énoncé lui-même, ni sa négation ne peuvent être démontrées. Pire encore, le deuxième théorème montre que tout système axiomatique suffisamment fort pour formaliser l’arithmétique ne peut pas prouver sa propre cohérence. Bref, le défi lancé avec le 2ème problème de Hilbert, sera à tout jamais en échec.

Le théorème d’incomplétude de Gödel a-t-il marqué la fin du mariage entre la logique et les mathématiques ? La logique ne devrait-elle être utilisée que pour formaliser le langage naturel ? Définitivement pas. Peu de temps après le travail de Gödel, une nouvelle discipline, dans laquelle la logique a joué (et joue toujours) un rôle central, a commencé à gagner de plus en plus d’importance : l’informatique. L’idée d’un « ordinateur mécanique » remonte (au moins) à Charles Babbage et Ada Lovelace vers 1840. La première trace d’exécution d’un algorithme publiée, conçu comme une séquence finie d’instructions pouvant être exécutées par une machine appelée « Analytical Engine », est apparu en 1843 et a été écrit par Ada Lovelace pour calculer les nombres de Bernoulli (Voir Vardi, « A Brief History of Logic »).

Entre 1930 et 1950, le travail, entre autres, d’Alan Turing , d’Alonzo Church, et de Claude Shannon a posé les fondations de plusieurs domaines de recherche théorique en informatique. Il a aussi permis de répondre négativement à une autre question posée par Hilbert : il n’est pas possible de construire un algorithme qui puisse prouver un énoncé logique donné, à partir des axiomes de la logique (au sens du calcul des prédicats).

Malgré ce résultat négatif pour le problème de la décision (connu sous le nom de Entscheidungsproblem), le lien entre la logique et l’informatique a permis le développement des premiers ordinateurs réels. De nombreux problèmes sont en effet décidables. Les mathématiciens ont donc pu, en utilisant le langage de la logique, concevoir des machines et des programmes pour résoudre des problèmes pratiques. Par exemple, pendant la seconde guerre mondiale, Alan Turing a conçu « La Bombe« , une machine capable de déchiffrer les messages allemands. Les mathématiciens ont continué à travailler sur les questions de calcul, et ont franchi une étape clé vers la fin de années 50, lorsque les langages de programmation ont commencé à être conçus, permettant ainsi d’écrire des logiciels indépendamment du hardware. Le travail de Grace Hopper) au milieu des années 50 a conduit à la création d’un des premiers langages de programmation dans lequel les instructions pour l’ordinateur sont données en utilisant de la logique, exprimés avec des mots simples. En facilitant l’écriture de programmes informatiques, les langages de programmation ont conduit à l’expansion massive des ordinateurs dans l’industrie.

La logique est un ingrédient fondamental dans tous les langages de programmation utilisés aujourd’hui : il ne serait pas possible d’écrire un logiciel significatif sans utiliser la logique pour coder les conditions et les conditions de sortie de boucle. Mais la logique a des applications dans plusieurs autres domaines : la logique est un instrument théorique qui, aujourd’hui, nous permet de résoudre des problèmes très pratiques. La logique a aussi été utilisée pour modéliser et analyser les circuits électroniques digitaux (ou hardware) : la logique permet aux ingénieurs d’optimiser et de vérifier le comportement d’un circuit avant même qu’il ne soit construit.

Pour être précis, il faut aujourd’hui parler des logiques (au pluriel), plutôt que d’une seule « logique ». Les résultats négatifs mentionnés ci-dessus pour la décidabilité et la complétude se réfèrent principalement à cette logique appelée « calcul des prédicats ». Toutefois, une quantité substantielle de recherches a étudié les restrictions et les variations de cette logique. Par exemple, il existe des logiques pour raisonner sur le temps, exprimant des notions telles que « suivant » ou « dans le futur ». Il existe des logiques qui peuvent modéliser l’échange d’informations entre des agents et leurs obligations. Ces logiques ont servi à modéliser et à vérifier des protocoles de sécurité, et d’autres systèmes complexes, à la fois dans le monde universitaire et dans l’industrie.

La logique a également des liens directs avec l’intelligence artificielle. Vers 1970, Philippe Roussell et Alain Colmerauer ont développé un langage de programmation appelé PROLOG, qui signifie « Programmation en Logique ». Depuis lors, ce langage de programmation et ses variantes ont été largement utilisés dans la prise de décision (decision making) automatisée et la planification automatisée. De même, la logique fournit les instruments théoriques pour étudier et optimiser les structures de données et les langages de requête pour les bases de données, mais aussi pour la planification, le scheduling et l’allocation des ressources.

Un autre domaine important où la logique joue un rôle clé est la vérification des logiciels : au cours des vingt dernières années, il y a eu un énorme progrès dans la vérification automatisée des logiciels basée sur la logique pour raisonner sur l’exécution des programmes. Les entreprise dans des domaines tels que l’aéronautique ou le médical, mais aussi des sociétés comme Microsoft, Facebook, Amazon, Google, Apple et bien d’autres, ont des équipes dédiées travaillant sur les logiques de vérification :.
– https://aws.amazon.com/security/provable-security
– https://fbinfer.com
– https://www.microsoft.com/en-us/research/group/research-software-engineering-rise

Voilà, la logique a non seulement une longue histoire théorique, mais elle a aussi des applications très pratiques de nos jours : à partir de la logique comme instrument initialement développé pour formaliser le raisonnement avec la langue humaine, cet « instrument » a évolué dans la direction des mathématiques, puis est devenu un ingrédient clé pour le développement du hardware et des logiciels. Aujourd’hui, les logiques sont nombreuses et leurs applications ont un impact direct et croissant sur notre vie quotidienne.

Franco Raimondi est professeur d’informatique à Middlesex University, London.

– Il remercie Giuseppe Primiero, Fabio Roda, Francesca Invernizzi and P.B. pour leur aide et leurs commentaires dans la préparation de cet article.
– Le contenu de cet article a été initialement présenté en italien à une conférence organisée par www.libreriaparoleneltempo.it, Lecco, Italie.
– Toutes les opinions sont les siennes.
– Toutes les photos des personnes célèbres sont issues de wikipédia