Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Catégories
Techniques
Sciences
Encore plus...
Techno-Science.net
Partenaires
Organismes
 CEA
 ESA
Sites Web
Photo Mystérieuse

Que représente
cette image ?
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Logique mathématique

La logique mathématique est née à la fin du XIXe siècle de la logique au sens philosophique du terme. Ses débuts furent marqués par la rencontre entre deux idées nouvelles :

  • la volonté chez Frege, Russell ou chez Hilbert plus tard de donner une fondation axiomatique aux mathématiques ;
  • la découverte par George Boole (Georges Boole (2 novembre 1815 à Lincoln Royaume-Uni - 8 décembre 1864 à Ballintemple, Irlande) est un logicien, mathématicien et philosophe...) de l'existence de structures algébriques permettant de définir un " calcul de vérité ".

La logique mathématique (La logique mathématique est née à la fin du XIXe siècle de la logique au sens philosophique du terme. Ses débuts furent marqués par la rencontre entre deux idées nouvelles :) a donc repris l'objectif de la logique (La logique (du grec logikê, dérivé de logos (λόγος), terme inventé par Xénocrate signifiant à la fois raison, langage, et raisonnement) est dans une...), étudier le raisonnement, mais en se restreignant au langage des mathématiques qui présente l'avantage d'être extrêmement normalisé. C'est ce qui a rendu (Le rendu est un processus informatique calculant l'image 2D (équivalent d'une photographie) d'une scène créée dans un logiciel de modélisation 3D comportant à la fois des objets et des sources de lumière et vue...) possible la définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) de divers " systèmes logiques " formalisant le raisonnement en mathématique (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures,...) et le développement très rapide de la logique mathématique au cours du XXe siècle (Un siècle est maintenant une période de cent années. Le mot vient du latin saeculum, i, qui signifiait race, génération. Il a ensuite indiqué la durée...).

Avant de trouver son nom actuel, attribué à Giuseppe Peano (Giuseppe Peano (Spinetta di Cuneo, 27 août 1858 - Turin, 20 avril 1932) était un mathématicien italien. Il a inventé une langue artificielle issue du latin : le Latino sine flexione.), la logique mathématique s'est appelée " logique symbolique " (en opposition à la logique philosophique) et " métamathématique " (terminologie de Hilbert). Peano a utilisé ses notations de logique mathématique pour son formulaire de mathématiques, une tentative de formaliser celles-ci.

Au XXIe siècle, la logique mathématique s'est ramifiée en de nombreux sous-domaines, dont la plupart n'ont que très peu à voir avec les objectifs initiaux des mathématiciens du XIXe siècle, mais sont des disciplines mathématiques à part entière. On compte notamment :

  • la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur l’observation ou...) des ensembles ;
  • la théorie de la démonstration ;
  • la théorie des modèles ;
  • la théorie de la calculabilité (La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la notion intuitive de fonction calculable est aussi vieille...).

Cette classification en quatre grands axes, généralement admise, est celle proposée par Jon Barwise dans son ouvrage Handbook of Mathematical Logic. Depuis, un cinquième grand axe (En géométrie, le grand axe d'une ellipse est un paramètre utilisé pour décrire la dimension de cette conique. Le demi-grand axe est la moitié du grand axe.) semble se dessiner avec les travaux sur la théorie des types (La théorie des types est une branche de la logique mathématique : elle fonde la construction des objets sur la notion de fonction et non pas sur...).

Quelques données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) d'histoire

Les premières tentatives de traitement formel des mathématiques sont dues à Leibniz et Lambert ; Leibniz a en particulier introduit une grande partie de la notation mathématique moderne (usage des quantificateurs, symbole d'intégration, etc.). Toutefois on ne peut parler de logique mathématique qu'à partir du milieu du XIXe siècle avec les travaux de George Boole (et dans une moindre mesure de Auguste De Morgan) qui introduit un calcul de vérité où les combinaisons logiques comme la conjonction, la disjonction et l'implication, sont des opérations analogues à l'addition (L'addition est une opération élémentaire, permettant notamment de décrire la réunion de quantités ou l'adjonction de grandeurs extensives de même nature, comme les longueurs, les...) ou la multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division .) des entiers, mais portant sur les valeurs de vérité faux et vrai (ou 0 et 1) ; ces opérations booléennes se définissent au moyen de tables de vérité.

Le calcul de Boole semblait une piste fructueuse afin de résoudre les problèmes de fondation des mathématiques (Cet article discute des fondements des mathématiques. Le problème de la fondation, ou des fondements, des mathématiques est celui des principes et de leur vérité. À partir de quels principes peut-on...) dus à leur complexification et à l'apparition des paradoxes, mais il ne permettait pas de prendre en compte la notion de variable (En mathématiques et en logique, une variable est représentée par un symbole. Elle est utilisée pour marquer un rôle dans une...). Dès lors nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de mathématiciens, ont cherché à l'étendre au cadre général du raisonnement mathématique et l'on a vu apparaître les systèmes logiques formalisés ; l'un des premiers est dû à Frege au tournant du XXe siècle.

En 1900 au cours d'une très célèbre conférence au congrès international de mathématiques (Le congrès international de mathématiques est une manifestation organisée tous les quatre ans par l'Union mathématique internationale.) à Paris (Paris est une ville française, capitale de la France et le chef-lieu de la région d’Île-de-France. Cette ville est construite sur une boucle de la Seine, au centre du bassin parisien, entre les confluents de la...), David Hilbert a proposé une liste des 23 problèmes non résolus les plus importants des mathématiques d'alors. Le deuxième était celui de la cohérence de l'arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes. On l'appelle plus généralement la « science des...), c’est-à-dire de démontrer par des moyens finitistes la non-contradiction des axiomes de l'arithmétique.

Le programme de Hilbert a suscité de nombreux travaux en logique dans le premier quart du siècle, notamment le développement de systèmes d'axiomes pour les mathématiques : les axiomes de Peano (Les axiomes de Peano sont, en mathématiques, un ensemble d'axiomes de second ordre proposés par Giuseppe Peano pour définir l'arithmétique [1].) pour l'arithmétique, ceux de Zermelo complété par Skolem et Fraenkel pour la théorie des ensembles (La théorie des ensembles est une branche des mathématiques créée initialement par le mathématicien allemand Georg Cantor à la fin du XIXe siècle.) et le développement par Whitehead et Russell d'un programme de formalisation des mathématiques, les Principia Mathematica. C'est également la période où apparaissent les principes fondateurs de la théorie des modèles : notion de modèle d'une théorie, théorème de Löwenheim-Skolem (Le théorème de Löwenheim-Skolem fait partie de la théorie des modèles. Sa simplicité et sa puissance en font un théorème majeur — avec le...).

En 1929 Kurt Gödel montre dans sa thèse (Une thèse (du nom grec thesis, se traduisant par « action de poser ») est l'affirmation ou la prise de position d'un locuteur, à...) de doctorat (Le doctorat (du latin doctorem, de doctum, supin de docere, enseigner) est généralement le grade universitaire le plus élevé. Le titulaire de ce grade est le docteur. Selon les pays et les époques, le doctorat peut...) son théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir d'axiomes. Un théorème est à distinguer...) de complétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut lui être ajouté, en...) qui énonce le succès de l'entreprise de formalisation des mathématiques : tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) raisonnement mathématique peut en principe être formalisé dans le calcul des prédicats (Le calcul des prédicats du premier ordre, ou calcul des relations, ou logique du premier ordre, ou tout simplement calcul des prédicats est une formalisation du langage des mathématiques proposée par les logiciens du début du...). Ce théorème a été accueilli comme une avancée notable vers la résolution du programme de Hilbert, mais un an plus tard Gödel démontrait le théorème d'incomplétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut lui être ajouté,...) (publié en 1931) qui montrait irréfutablement l'impossibilité de réaliser ce programme.

Ce résultat négatif n'a toutefois pas arrêté l'essor de la logique mathématique. Les années 30 ont vu arriver une nouvelle génération de logicien anglais et américains, notamment Alonzo Church (Alonzo Church 14 juin 1903 - 11 août 1995 fut un mathématicien (logicien) américain à qui l'on doit certains des fondements de l'informatique théorique.), Alan Turing, Stephen Kleene, Haskell Curry et Emil Post (Emil Leon Post (né le 11 février 1897, mort le 21 avril 1954) était un mathématicien américain né sur le territoire de l'actuelle Pologne dans une famille juive. Il est à l'origine du problème de...), qui ont grandement contribué à la définition de la notion d'algorithme et au développement de la théorie de la complexité algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus systématiques de...). La théorie de la démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées à partir de propositions initiales, en...) de Hilbert a également continué à se développer avec les travaux de Gerhard Gentzen qui a produit la première démonstration de cohérence relative et initié ainsi un programme de classification des théories axiomatiques.

Le résultat le plus spectaculaire de l'après-guerre est dû à Paul Cohen qui démontre en utilisant la méthode du forcing l'indépendance de l'hypothèse du continu en théorie des ensembles, résolvant ainsi le 1er problème de Hilbert. Mais la logique mathématique subit également une révolution due à l'apparition de l'informatique ; la découverte de la correspondance (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le terme désigne des échanges de courrier personnels plutôt qu'administratifs.) de Curry-Howard qui relie les preuves formelles au lambda-calcul (Le lambda-calcul (ou λ-calcul) est un langage de programmation théorique inventé par Alonzo Church dans les années 1930. Ce langage a été le premier utilisé pour définir et caractériser les fonctions récursives et il a eu une grande...) de Church et donne un contenu calculatoire aux démonstrations va déclencher un vaste programme de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique désigne également le...).

Quelques résultats fondamentaux

Quelques résultats importants ont été établis pendant les années 1930 :

  • Le théorème de complétude du calcul des prédicats du premier ordre que Gödel a montré dans sa thèse de doctorat, un an avant son célèbre théorème d'incomplétude de Gödel. Ce théorème énonce que toute démonstration mathématique peut être représentée dans le formalisme du calcul des prédicats (qui est donc complet).
  • L'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme...) des théorèmes du calcul des prédicats n'est pas calculable, c'est-à-dire qu'aucun algorithme ne permet de vérifier si un énoncé donné est prouvable ou non. Il existe, cependant, un semi-algorithme : celui-ci prend en entrée une formule du premier ordre ; il s'interrompt en répondant "oui" si la formule est universellement valide, et continue indéfiniment sinon. Même si ce semi-algorithme s'exécute pendant des milliards d'années, il peut ne pas conclure qu'une proposition n'est pas universellement valide. En d'autres termes, l'ensemble des formules du premier ordre universellement valide est " récursivement énumérable " ; on dit qu'il est " semi-décidable ".
  • La cohérence (non contradiction) d'un système d'axiomes (par exemple : les axiomes de Peano pour l'arithmétique) n'est pas une conséquence de ces seuls axiomes sauf dans des cas triviaux (notamment lorsque les axiomes sont contradictoires entre eux). C'est le fameux second théorème d'incomplétude de Gödel.
  • L'ensemble de toutes les formules universellement valides du second ordre n'est pas énumérable, même récursivement. Ceci est une conséquence du théorème d'incomplétude.
  • Tout théorème purement logique peut être démontré en n'utilisant à tout moment que des propositions qui sont des sous-formules de son énoncé. Connu sous le nom de théorème de la sous-formule, il est une conséquence du théorème d'élimination des coupures en calcul des séquents (En 1935 Gentzen a proposé la déduction naturelle, un formalisme pour décrire les preuves du calcul des prédicats, dont l'idée était de coller au plus près à la manière dont les mathématiciens...) de Gerhard Gentzen.
    • Accessoirement, ce théorème de la sous-formule fournit un théorème de cohèrence pour la logique car interdit la dérivation de la formule vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) (identifiée à l'absurdité).

D'autres résultats importants ont été établis après les années 1930 :

  • Le théorème d'élimination des coupures (dont, cas particulier, d'élimination du modus ponens) qui est à la base de la correspondance de Curry-Howard entre preuves et programmes et fait le lien entre ce qui ce fait en mathématique et ce qui ce fait en informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement...).
    • Une découverte fortuite et majeure dans ce domaine, datant de 1990, est que la loi de Peirce, donc la logique classique et non la seule logique intuitionniste, "passe" cette correspondance et via que la logique classique est constructive.
  • L'indépendance de l'hypothèse du continu par rapport aux autres axiomes de la théorie des ensembles (ZF) est achevée en 1963 par Paul Cohen ce qui lui valu la médaille Field.

Système logique

Définition

Un système logique ou système de déduction est constitué de trois composantes. Les deux premières définissent sa syntaxe, la troisième sa sémantique :

  • Un ensemble de formules, ou faits ; dans les systèmes de logique classique ou intuitionniste, les formules représentent des énoncés mathématiques exprimés formellement. Les formules sont définies par des moyens combinatoires : suites de symboles, arbres étiquetés, graphes...
  • Un ensemble de déductions ; les déductions sont également définies par des moyens combinatoires. Une déduction permet de dériver des formules (les formules prouvables ou théorèmes) à partir de formules de départ (les axiomes) au moyen de règles (les règles d'inférence).
  • Une interprétation des formules ; il s'agit d'une fonction associant à toute formule un objet (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans un espace à trois dimensions, qui a une fonction précise, et qui peut être désigné par une étiquette verbale. Il est défini par les...) dans une structure abstraite appelée modèle, ce qui permet de définir la validité des formules.

Syntaxe et sémantique

La caractéristique principale des formules et des déductions est qu'il s'agit d'objets finis ; plus encore, chacun des ensembles de formules et de déductions est récursif, c'est-à-dire que l'on dispose d'un algorithme qui détermine si un objet donné est une formule correcte ou une déduction correcte du système.

La sémantique, au contraire, échappe à la combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.) en faisant appel (en général) à des objets infinis. Elle a d'abord servi à " définir " la vérité. Par exemple, en calcul des propositions (Le calcul des propositions ou calcul propositionnel, dont le fondateur fut le logicien allemand Frege, version moderne de la logique stoïcienne, est une théorie logique qui définit les...), les formules sont interprétées par des éléments d'une algèbre (L'algèbre est la branche des mathématiques qui étudie les structures algébriques, indépendamment de la notion de limite (rattachée à l'analyse) et de la...) de Boole ; les formules valides sont celles qui sont interprétées par le plus grand élément.

Une mise en garde est de rigueur ici, car Kurt Gödel (suivi par Alfred Tarski) a montré avec son théorème d'incomplétude l'impossibilité de définir mathématiquement la vérité mathématique. C'est pourquoi il est plus approprié de voir la sémantique comme une métaphore : les formules — objets syntaxiques — sont projetées dans un autre monde (Le mot monde peut désigner :), plus abstrait, par exemple les algèbres de Boole. Cette technique — plonger les objets dans un monde plus vaste pour mieux raisonner dessus — est couramment utilisée en mathématique et a amplement démontré son efficacité.

Ainsi la sémantique ne sert pas qu'à " définir " la vérité. Par exemple, la sémantique dénotationnelle est une interprétation, non des formules, mais des déductions visant à capturer leur contenu calculatoire.

Systèmes de déduction

En logiques classique et intuitionniste, on distingue deux types d'axiomes : les axiomes logiques qui expriment des propriétés purement logiques comme par exemple A\lor\lnot A (principe du tiers exclu, valide en logique classique mais pas en logique intuitionniste) et les axiomes extra-logiques qui définissent des objets mathématiques, par exemple les axiomes de Peano qui définissent l'arithmétique ou les axiomes de Zermelo-Fraenkel qui définissent la théorie des ensembles. Quand le système possède des axiomes extra-logiques, on parle de théorie axiomatique. L'étude des différents modèles d'une même théorie axiomatique est l'objet de la théorie des modèles (La théorie des modèles est une théorie de la vérité mathématique. Elle consiste essentiellement à dire qu’une théorie est mathématiquement valide si on peut définir un univers dans lequel elle est vraie.).

Deux systèmes de déduction peuvent être équivalents au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du vieillissement, suivi de...) où ils ont exactement les mêmes théorèmes. On démontre cette équivalence en fournissant des traductions des déductions de l'un dans les déductions de l'autre. Par exemple, il existe (au moins) trois types de systèmes de déduction équivalents pour le calcul des prédicats : les systèmes à la Hilbert, la déduction naturelle (La déduction naturelle est une façon d'exposer les principes de la logique du premier ordre pour les rendre aussi proches que possible des façons naturelles de raisonner) et le calcul des séquents. On y ajoute parfois le style de Fitch qui est une variante de la déduction naturelle dans laquelle les démonstrations sont présentées de façon linéaire.

Alors que la théorie des nombres démontre des propriétés des nombres, on notera la principale caractéristique de la logique en tant que théorie mathématique : elle " démontre " des propriétés de systèmes de déduction dans lesquels les objets sont des " théorèmes ". Il y a donc un double niveau dans lequel il ne faut pas se perdre. Pour clarifier les choses, les " théorèmes " énonçant des propriétés des systèmes de déduction sont parfois appelés des " métathéorèmes ". Le système de déduction que l'on étudie est appelé la " théorie " et le système dans lequel on énonce et démontre les métathéorèmes est appelé la " métathéorie ".

Les propriétés fondamentales des systèmes de déduction sont les suivantes.

  • La correction : La correction énonce que les théorèmes sont valides dans tous les modèles. Cela signifie que les règles d'inférence sont bien adaptées à ces modèles, autrement dit que le système de déduction est une manière de bien raisonner dans ces modèles.
  • La cohérence : Un système de déduction est cohérent (on dit aussi qu'il est consistant par mimétisme (Le mimétisme est une stratégie adaptative d'imitation. Cela permet par exemple à une espèce d'échapper à d'éventuels prédateurs. Les...) avec l'anglais) s'il admet un modèle non trivial, c'est-à-dire un modèle qui a au moins deux éléments. Cela revient à affirmer que dans ce système de déduction, il existe des propositions qui ne sont pas des théorèmes.
  • La complétude : Elle se définit par rapport à une famille de modèles. Un système de déduction est complet par rapport à une famille de modèles, si toute proposition qui est valide dans tous les modèles de la famille est un théorème. En bref, un sytème est complet si tout ce qui est valide est démontrable.

Une autre propriété des systèmes de déduction apparentée à la complétude est la cohérence maximale. Un système de déduction est maximalement cohérent, si l'ajout d'un nouvel axiome (Le mot axiome vient du grec αξιωμα (axioma), qui signifie "qui est considéré comme digne ou convenable" ou "qui est considéré comme évident en soi". Pour certains...) qui n'est pas lui-même un théorème rend le système incohérent.

Affirmer " tel système est complet pour telle famille de modèles " est un exemple typique de métathéorème.

On notera que dans ce cadre, la notion intuitive de vérité donne lieu à deux concepts formels : la validité et la démontrabilité. Les trois propriétés de correction, cohérence et complétude précisent comment ces notions peuvent être reliées, espérant qu'ainsi la vérité, quête du logicien, puisse être cernée.

Le calcul des propositions

Les propositions et les objets mathématiques, sont des assemblages de symboles et de lettres formés en suivant certaines règles de syntaxe. Les principaux symboles de la logique sont appelés connecteurs, ils servent (Servent est la contraction du mot serveur et client.) essentiellement à créer de nouvelles propositions à partir de propositions déjà créées. Dans le calcul des propositions, les propositions de base que l'on appelle aussi les variables propositionnelles n'ont pas de contenu (n'ont pas de signification) a priori. On peut remplacer une variable propositionnelle par "il pleut", mais ce n'est pas le contenu météorologique qui intéresse le logicien, mais la façon dont les propositions de base sont combinées pour construire des raisonnements.

Dans la suite de cette section, on suppose que l'on se place dans la logique classique, car la réduction des connecteurs à un ou deux n'est pas possible en logique intuitionniste et la limitation à une seule disjonction et une seule conjonction n'est pas vraie en logique linéaire.

On peut former toutes les propositions à partir de deux connecteurs : par exemples ∨ et ¬ (ou et non). D'autres choix sont possibles : ainsi, \Rightarrow (implication) et \bot (faux). On sait aussi que l'on peut aussi n'utiliser qu'un seul connecteur, le symbole de Sheffer (Henry M. Sheffer, 1913), appelé Nand par les concepteurs de circuits (et noté " | " — une barre verticale) ; on peut aussi n'utiliser que le connecteur Nor comme noté par Charles Peirce (1880) sans le publier.

La disjonction

La disjonction de deux propositions P et Q est la proposition notée PQ ou " P ou Q " qui est vraie si l’une au moins des deux propositions est vraie, et fausse si les deux propositions sont fausses.

La négation

La négation d’une proposition P, est la proposition notée ¬P, ou " non P " qui est vraie lorsque P est fausse et fausse lorsque P est vraie.

À partir de ces deux connecteurs, on peut construire d’autres connecteurs ou abréviations utiles :

La conjonction

La conjonction de deux propositions P et Q est la proposition suivante :

¬((¬P) ∨ (¬Q)) c'est-à-dire non ( (non P) ou (non Q) )

Celle-ci est notée PQ ou " P et Q " et n’est vraie que lorsque P et Q sont vraies et fausse si l’une des deux propositions est fausse.

L'implication

L'implication de Q par P est la proposition (¬P) ∨ Q, notée " PQ " ou " P implique Q ", et qui est fausse seulement si P est une proposition vraie et Q fausse.

L'équivalence

L'équivalence logique de P et Q est la proposition ( (PQ) ∧ ( QP) ) ( ((P implique Q) et (Q implique P) )), notée " PQ " ou (P est équivalent à Q).

Le ou exclusif

Le ou exclusif ou disjonction exclusive de P et Q est la proposition P | Q qui correspond à (PQ) ∧ ¬(PQ), c'est-à-dire en français: soit P, soit Q (mais pas les deux à la fois). Le ou exclusif de P et Q correspond à P ⇔ ¬Q ou encore à ¬PQ.

Le calcul des prédicats

Substitution

Il est également possible de construire à partir d’une proposition P, d’autres propositions en remplaçant un objet mathématique indéterminé x dans la proposition partout où il intervient, par un autre objet mathématique a.

Par exemple, la proposition P : " 8 est un nombre pair ", peut être représentée sous la forme P{8}, où P est le prédicat (Les prédicats d’une théorie sont les formules qui contiennent des variables libres.) " est un nombre pair ", et 8 est son argument.
Ou par exemple, la proposition " Les droites D et D’ sont parallèles " peut être représentée sous la forme P{D, D’} où P est le prédicat " sont parallèles " et les droites D et D’ sont les arguments.

Si P est une proposition, x un objet indéterminé, et a un objet mathématique, l’assemblage obtenu en remplaçant x par a dans P est encore une proposition notée

(a|x)P

et s’appelle proposition obtenue par substitution de x par a dans P.

Pour mettre en évidence un objet indéterminé x dans une proposition P, on écrit la proposition sous la forme P{x} ; et on note P{a} la proposition (a|x)P.

Soit P une proposition, x un objet indéterminé, et a un objet mathématique donné. Si P est vraie, alors P{a} est vraie.

Et tout cela se généralise au cas de plusieurs objets indéterminés.

Les quantificateurs

Il existe encore un autre procédé logique, permettant de construire d’autres propositions à partir d’une proposition.

Soit une proposition P et x un objet indéterminé. Nous pouvons considérer la proposition :

il existe un objet a, tel que (a|x)P soit vraie

c'est-à-dire

il existe un objet a, tel que P{a} soit vraie

" il existe un objet " signifie intuitivement " nous pouvons trouver au moins un objet ".

Symboliquement, nous écrivons :

a P

ou

a P{a}

ce qui se lit :

" il existe a tel que P "

Ce signe ∃ s’appelle le quantificateur existentiel.

Nous définissons, à partir de ∃ le symbole ∀  :

Soit P une proposition et x un objet indéterminé, la proposition notée ∀ x P est la proposition

¬( ∃x ¬P )

et se lit " pour tout x, P "
ou " quel que soit x, on a P vraie "

∀ s’appelle le quantificateur universel.

Évidemment, la proposition (∀ x P) est fausse si et seulement si (∃ x ¬ P) est vraie.

Utilisation des quantificateurs

Propriétés élémentaires

Soient P et Q deux propositions et x un objet indéterminé.

  • ¬(∃ x P) ⇔ (∀ x ¬ P)
  • (∀ x) (PQ) ⇔ ( (∀ x) P ∧ (∀ x) Q )
  • (∀ x) P ∨ (∀ x) Q ⇒ (∀ x) (PQ )
    (Implication réciproque fausse en général)
  • (∃ x) (PQ) ⇔ ( (∃ x) P ∨ (∃ x) Q )
  • (∃ x) (PQ) ⇒ ( (∃ x) P ∧ (∃ x) Q )
    (Implication réciproque fausse en général)
Propriétés utiles

Soient P une proposition et x et y des objets indéterminés.

  • (∀ x) (∀ y) P ⇔ (∀ y) (∀ x) P
  • (∃ x) (∃ y) P ⇔ (∃ y) (∃ x) P
  • (∃ x) (∀ y) P ⇒ (∀ y) (∃ x) P
    (Implication réciproque fausse en général)

La dernière implication dit que s’il existe un x, tel que pour tout y, on ait P vraie, alors pour tout y, il existe bien un x (celui obtenu avant) tel que P soit vraie.

Intuitivement, l’implication réciproque est fausse en général, parce que si pour chaque y, il existe un x tel que P soit vraie, ce x pourrait dépendre de y et varier suivant y. Ce x pourrait donc ne pas être le même pour tout y tel que P soit vraie.

Quelques systèmes déductifs

  • Les systèmes à la Hilbert ;
  • La déduction naturelle ;
  • Le calcul des séquents ;

La théorie des ensembles

La théorie des ensembles est à la base de nombreuses théories mathématiques. Outre les symboles de logique énumérés précédemment, cette théorie utilise des autres symboles = et ∈ permettant de mettre des objets mathématiques en relation. Les objets mathématiques sont appelés des ensembles.

L’égalité

Le signe de l’égalité se note

=

et représente la relation d’égalité entre objets mathématiques.

Nous nous contenterons de la définition intuitive :

Soient a et b deux objets. a = b signifie que a et b représentent des objets identiques, et se lit " a est égal à b "

≠ est définie par ab si ¬(a = b)

Propriétés :

  • (∀ x) (x = x) vraie (réflexivité de =)
  • (∀ x) (∀ y) ( (x = y) ⇔ (y = x) ) vraie (symétrie de =)
  • (∀ x) (∀ y) (∀ z) ( ((x = y) ∧ (y = z)) ⇒ (x = z) ) (transitivité de =)

La relation = étant réflexive, symétrique et transitive, on dit que la relation = est une relation d'équivalence

  • Soit P{x} une proposition contenant un objet indéterminé x. Soient a et b des objets tels que a = b. Alors les propositions P{a} et P{b} (obtenues en remplaçant respectivement x par a et x par b dans P{x}) sont équivalentes.

L’appartenance

Le signe de l’appartenance se note :

et représente la relation d’appartenance d’un objet à un autre.

Si a et b sont deux objets ab se lit :

a appartient à b "

ou encore

a est élément de b "

∉ se définit par ab si ¬(ab) vraie.

ab se lit " a n’appartient pas à b "

Théorème :

Soient a et b deux objets mathématiques.

a = b ⇔ ( (∀x) (xaxb) )

Pour les règles d'utilisation de ces symboles, reportez-vous à l'article langage formel (Dans de nombreux contextes (scientifique, légal, etc.) l'on désigne par langage formel un mode d'expression plus formalisé et plus précis (les deux n'allant pas...) mathématique.

Bibliographie

  • Alonzo Church, Introduction to mathematical logic, Princeton University Press, ISBN 0691029067
  • Stephen Kleene, logique mathématique, Armand Colin, 1971 ou Gabay 1987, ISBN 2876470055
  • Y. Delmas-Rigoutsos et René Lalement, La Logique ou l'Art de raisonner, Le Pommier-Fayard, 2000, ISBN 2746500353
  • R. David, K. Nour et C. Raffalli, Introduction à la logique. Théorie de la démonstration. Cours et exercices corrigés, Dunod, 2001, ISBN 2100067966
  • Gilles Dowek, La logique, Coll. Dominos, Flammarion (1995).
  • René Cori, Daniel Lascar, Logique mathématique tomes 1 et 2, ISBN 210005452X et ISBN 2100054538
  • René Lalement, Logique, réduction, résolution, Masson, 1990
Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.