En logique mathématique, le calcul des prédicats du premier ordre, logique du premier ordre, calcul des relations, logique quantificationnelle, ou tout simplement calcul des prédicats, est un système formel utilisé pour raisonner et décrire des énoncés en mathématiques, informatique, intelligence artificielle, philosophie et linguistique. Il a été proposé par Gottlob Frege comme une formalisation du langage des mathématiques entre la fin du et le début du . La logique du premier ordre comporte deux parties :
la syntaxe définit le vocabulaire symbolique de base ainsi que les règles permettant de construire des énoncés ; la sémantique interprète ces énoncés comme exprimant des relations entre les éléments d'un domaine, également appelé modèle.
Sur le plan syntaxique, les langages du premier ordre opposent deux grandes classes linguistiques :
les constituants servant à identifier ou nommer des éléments du domaine : variables, symboles de constantes, termes ; les constituants servant à exprimer des propriétés ou des relations entre ces éléments : prédicats et formules.
Un prédicat est une expression linguistique qui peut être reliée à un ou plusieurs éléments du domaine pour former une phrase. Par exemple, dans la phrase « Mars est une planète », l'expression « est une planète » est un prédicat qui est relié au nom (symbole de constante) « Mars » pour former une phrase. Et dans la phrase « Jupiter est plus grand que Mars », l'expression « est plus grand que » est un prédicat qui se relie aux deux noms, « Jupiter » et « Mars », pour former une phrase.
Lorsqu'un prédicat est lié à une expression, on dit qu'il exprime une propriété (telle que la propriété d'être une planète), et lorsqu'il est lié à deux ou plusieurs expressions, on dit qu'il exprime une relation (telle que la relation d'être plus grand). Ainsi on peut raisonner sur des énoncés comme « il existe un tel que pour tout , est ami avec », ce qui est exprimé symboliquement par la formule : .
La logique du premier ordre ne contient cependant aucune relation spécifique (comme telle relation d'ordre, d'inclusion ou d'égalité) ; en fait, il ne s'agit que d'étudier la façon dont on doit parler et raisonner avec les expressions du langage mathématique.
Les traits caractéristiques de la logique du premier ordre sont : l'utilisation de variables comme , pour dénoter des éléments du domaine d'interprétation ; l'utilisation de prédicats (ou relations) sur les éléments ; l'utilisation d'opérations logiques (et, ou, implique) ; l'utilisation de quantifications, par exemple, l'une universelle (« Quel que soit », « pour tout » noté ∀) et l'autre existentielle (« il existe au moins un… tel que », noté ∃).
Le calcul des prédicats du premier ordre égalitaire adjoint au calcul des prédicats un symbole de relation, l'égalité, dont l'interprétation est l'affirmation que deux éléments sont les mêmes, et qui est axiomatisée en conséquence. Suivant le contexte, on peut parler simplement de calcul des prédicats pour le calcul des prédicats égalitaire.
On parle de logique du premier ordre par opposition aux logiques d'ordre supérieur, où l'on peut aussi appliquer les quantificateurs et les prédicats aux prédicats ou aux fonctions, en plus des variables. En outre, cet article ne traite que de la logique du premier ordre classique, mais il existe aussi une logique du premier ordre intuitionniste.
Introduction Alors que la logique propositionnelle traite des propositions déclaratives simples, la logique du premier ordre couvre en plus les prédicats et la quantification.
Un prédicat prend en entrée une ou plusieurs entités du domaine du discours et en sortie, il est soit Vrai, soit Faux. Considérons les deux phrases « Socrate est un philosophe » et « Platon est un philosophe ». En logique propositionnelle, ces phrases sont considérées comme non liées et peuvent être désignées, par exemple, par des variables telles que . Le prédicat « est un philosophe » apparaît dans les deux phrases, dont la structure commune est « a est un philosophe ». La variable a est instanciée en tant que « Socrate » dans la première phrase, et est instanciée en tant que « Platon » dans la deuxième phrase. Alors que la logique du premier ordre permet l'utilisation de prédicats, tels que « est un philosophe » dans cet exemple, la logique propositionnelle ne le permet pas.
Les relations entre les prédicats peuvent être énoncées à l'aide de connecteurs logiques. Considérons, par exemple, la formule du premier ordre « si a est un philosophe, alors a est un savant ». Cette formule est un énoncé conditionnel dont l'hypothèse est « a est un philosophe » et la conclusion « a est un savant ». La vérité de cette formule dépend de l'objet désigné par a, et des interprétations des prédicats « est un philosophe » et « est un savant ».
Les quantificateurs peuvent être appliqués aux variables d'une formule. La variable a de la formule précédente peut être quantifiée universellement, par exemple avec la phrase du premier ordre « Pour tout a, si a est un philosophe, alors a est un savant ». Le quantificateur universel « pour chaque » dans cette phrase exprime l'idée que l'affirmation « si a est un philosophe, alors a est un savant » est valable pour tous les choix de a.
La négation de la phrase « Pour tout a, si a est un philosophe, alors a est un savant » est logiquement équivalente à la phrase « Il existe a tel que a est un philosophe et a n'est pas un savant ». Le quantificateur existentiel « il existe » exprime l'idée que l'affirmation « a est un philosophe et a n'est pas un savant » est valable pour un certain choix de a.
Les prédicats « est un philosophe » et « est un savant » prennent chacun une seule variable. En général, les prédicats peuvent prendre plusieurs variables. Dans la phrase du premier ordre « Socrate est le professeur de Platon », le prédicat « est le professeur de » prend deux variables.
Histoire Emmanuel Kant croyait à tort que la logique de son temps, celle d’Aristote, était une science complète et définitivement achevée (préface de la seconde édition de la critique de la raison pure, 1787.). Les logiciens. du se sont rendu compte que la théorie d’Aristote ne dit rien ou presque sur la logique des relations. Gottlob Frege et beaucoup d'autres ont comblé cette lacune en définissant le calcul des prédicats au premier ordre.
Kurt Gödel a démontré en 1929 (dans sa thèse de doctorat) que le calcul des prédicats est complet, au sens où on peut donner un nombre fini de principes (axiomes logiques, schémas d'axiomes logiques et règles de déduction.) qui suffisent pour déduire de façon mécanique toutes les lois logiques (voir le théorème de complétude de Gödel). Il y a équivalence entre la présentation sémantique et la présentation syntaxique du calcul des prédicats. Tout énoncé universellement valide (c'est-à-dire vrai dans tout modèle du langage utilisé) est un théorème (c'est-à-dire qu'il peut être déduit d'un calcul, un système de règles logiques et d'axiomes, de façon équivalente un système à la Hilbert, la déduction naturelle, ou le calcul des séquents), et réciproquement. La logique du premier ordre est donc achevée au sens où le problème de la correction logique des démonstrations y est résolu. Elle continue cependant à faire l’objet d’importantes recherches : théorie des modèles, théorie de la démonstration, mécanisation du raisonnement…
Syntaxe vignette|Exemple d'une formule de la logique du premier ordre. Le schéma montre les quantificateurs, les occurrences des symboles de fonctions et des symboles de prédicats.|292x292px Contrairement à un langage naturel, comme le français, la logique du premier ordre est un langage formel. Cette section donne une brève présentation de la syntaxe du langage formel du calcul des prédicats. Pour cela, on a besoin d'un alphabet, c'est-à-dire un ensemble de symboles utilisées pour écrire les énoncés (ou formules). On se donne un ensemble des symboles appelés variables, toujours infini : , ,
Signature On se donne une signature, c'est-à-dire : un ensemble de symboles de fonctions : , , ; un ensemble de symboles de prédicats : , ,
Chaque symbole de fonction et chaque symbole de prédicat a une arité : il s'agit du nombre d'arguments ou d'objets auxquels il est appliqué. Par exemple, le prédicat pour « est bleu(e) » a une arité égale à 1 (on dit qu'il est unaire ou monadique), tandis que le prédicat pour « être amis » a une arité de deux (on dit qu'il est binaire ou dyadique). Il peut y avoir des symboles de fonction ou de prédicat d'arité 0. Un symbole de fonction d'arité 0 s'appelle une constante. Les constantes se notent généralement , ,
Exemples
Si l'on veut parler de personnes, Bob est un symbole de constante, mère(.) est un symbole de fonction d', amis(., .) est un symbole de prédicats d'. Si l'on veut parler d'entiers naturels, « 0, 1 » sont des symboles de constantes. Les symboles sont des symboles de fonctions d'. Les symboles sont des symboles de prédicats d'.
Termes
Les termes sont définis par induction :
un symbole de variable est un terme ; un symbole de constante est un terme ; si est un symbole de fonctions d'arité n, et que t, …, t sont des termes alors est un terme.
Exemples
Bob, mère(Bob), mère(mère(Bob)), mère(x) sont des termes sont des termes.
Formule Les formules du calcul des prédicats du premier ordre sont définies par induction : si un symbole de prédicat d'arité n et t, …, t sont des termes ¬e si e est une formule ; (e∧e) si e et e sont des formules ; (e∨e) si e et e sont des formules ; (e→e) si e et e sont des formules ; si e est une formule ; si e est une formule. Une formule de la forme s'appelle un atome ou une formule atomique. Les symboles (non), (et), (ou) et (implique), qui sont des connecteurs que possède aussi le calcul des propositions. Les symboles (quel que soit) et (il existe), appelés quantificateurs. On pourrait se contenter d'un seul quantificateur et de deux connecteurs logiques et en définissant les autres connecteurs et quantificateur à partir de ceux-ci. Par exemple est défini comme . Les symboles de parenthèses « ) » et « ( » sont comparables aux symboles de ponctuations dans une langue naturelle. On appelle énoncé une formule dont toutes les variables sont liées par un quantificateur (donc qui n'a pas de variable libre).
Exemples
Exemple 1
Si on se donne pour constantes les deux symboles , pour symboles de fonctions binaires , et pour symboles de prédicats binaires les symboles , alors le langage utilisé peut être interprété comme étant celui de l'arithmétique. désignant des variables, est un terme, est un terme clos, est une formule, est une formule close.
Exemple 2
Si on se donne un ensemble de variables quelconque, une constante notée « e », un symbole de fonction binaire noté « * », un symbole de fonction unaire notée « », un symbole de relation binaire « = », alors le langage utilisé peut être interprété comme étant celui de la théorie des groupes. Si désignent des variables, est un terme, est un terme clos, est une formule, et ( sont des formules closes.
Prédicats, formules closes, formules polies, variables libres, variables liées Lorsqu’une variable appartient à une sous-formule précédée d’un quantificateur, ou , elle est dite liée par ce quantificateur. Si une variable n’est liée par aucun quantificateur, elle est libre.
La distinction entre variable libre et variable liée est importante. Une variable liée ne possède pas d'identité propre et peut être remplacée par n'importe quel autre nom de variable qui n'apparaît pas dans la formule. Ainsi, est identique à mais pas à et encore moins à .
Une formule close est une formule dont toutes les variables sont liées. Un prédicat est une formule qui contient une ou plusieurs variables libres. On peut considérer les prédicats comme des concepts. Ainsi, est une formule close du langage de l'arithmétique. est un prédicat portant sur la variable z.