Logique (mathématiques)/Grammaire des prédicats

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Nous allons exposer les principes d’une grammaire à la fois formalisée et universelle, au sens où elle suffit pour faire tous les énoncés dont on a besoin dans les sciences. Nous expliquerons à la fin ce que prédicat veut dire ici.

Il s’agit de dire comment on fait des phrases avec des mots. Les logiciens appellent aussi les phrases des propositions, des énoncés, des assertions, des formules, des thèses, et dans certains cas, des affirmations, des lois, des hypothèses, des axiomes, des théorèmes, des équations…

Les mots

Les mots les plus simples de la logique, ou propositions atomiques, sont tous des symboles qu’ils soient effectivement propre à la notation mathématique comme =, 1, +, ¬, ou qu’ils soient représentés par une lettre courante de la littérature comme f et x.

Les mots usuels des langues naturelles, composés de plusieurs lettres, comme chaton, peuvent être considérés comme des propositions atomiques tant qu’aucune des lettres de celui-ci ne désigne déjà une proposition atomique. Cette technique est très utile pour développer un système formel dans un langage semi-naturel. Beaucoup de traités de logique sont difficiles à lire, même pour un spécialiste, parce qu’il faut se familiariser avec le formalisme parfois très particulier de leurs auteurs. Dans ce cours, on n'introduira pas de symboles logiques particuliers, hormis ceux qui sont bien connus, =, 1, 2,+, × (pour la multiplication), et ≠ (pour n’est pas égal à). Toutes les autres notions fondamentales seront traduites par des expressions naturelles. On se limite cependant à une grammaire simplifiée, celle qui va être exposée. Il est très facile de traduire les règles ou les axiomes que nous énoncerons dans un formalisme plus rigoureusement déterminé, avec des règles pour l’usage des parenthèses. Mais cela présente un véritable intérêt surtout pour les études métamathématiques, où les théories sont considérées comme des objets et pour se faire comprendre par un ordinateur.

Les mots logiquement composés, ou propositions composées, sont obtenus en assemblant plusieurs mots simples. On les appelle aussi des expressions formelles et parfois des formules.

Parmi les ensembles de mots, il y en a un qui a une importance particulière pour le calcul des prédicats, c’est l’ensemble des noms des individus ou des êtres sur lesquels porte la théorie, c’est-à-dire le domaine des noms d’objet, que nous appellerons parfois l’ontologie, ou l’univers, d’une théorie.

Les noms d’opérateurs sont les principaux outils pour former des noms composés à partir de noms simples. Les opérateurs sont aussi appelés des fonctions, au sens mathématique. Nous verrons plus loin que les opérateurs logiques servent à former des phrases composées à partir de phrases simples.

À partir du nom Pierre on peut former beaucoup d’autres noms avec un seul opérateur, le père de : le père de Pierre, le père du père de Pierre, le père du père du père de Pierre, et ainsi de suite. « Le père de » est un opérateur unaire, ou à une place, ou d’arité 1, parce qu’il s’applique à un seul nom d’objet.

À partir de 1 et de l’opérateur binaire +, on peut former de nombreux noms : 1+1, (1+1)+1, (1+1)+1, 1+((1+1)+1)… Le résultat d’un opérateur binaire o appliqué à deux individus x et y est noté :

• de manière préfixe o(x,y) ou oxy (dans la notation de Jan Łukasiewicz) ;
• de manière infixe xoy.

Les noms d’opérateurs peuvent être introduits, dans un langage semi-naturel. Par exemple, « l’enfant de Pierre et Marie » peut être considéré comme obtenu par l’application de l’opérateur binaire « l’enfant de … et » aux deux êtres Pierre et Marie. Il peut être écrit e(P,M) ou ePM ou PeM.

On se sert souvent des parenthèses pour indiquer clairement la façon dont les noms composés sont construits à partir de noms simples. La notation de Lukasiewicz, permet de s’en passer, mais les formules deviennent beaucoup moins lisibles.

Tant que 1 et + ont leur signification ordinaire 1+(1+1) est égal à (1+1)+1 mais ce n’est pas vrai pour tous les opérateurs binaires : l’enfant de (l’enfant de Pierre et Marie) et de Socrate n’est pas égal à l’enfant de Pierre et de (l’enfant de Marie et Socrate), s’il existe. De façon symbolique e(e(P,M),S) est différent de e(P,e(M,S)).

On pourrait se servir de la première notation pour l’addition et dire que +(1,+(1,1)) est égal à +(+(1,1),1). Mais justement parce que ces deux nombres sont égaux, il vaut bien mieux écrire x+y que +(x,y). Cela permet de supprimer toutes les parenthèses, 1+1+1, parce que dans ce cas il n’y a pas d’ambiguïté. Mais on ne peut pas faire la même chose avec l’opérateur « l’enfant de » parce que (PeM)eS est différent de Pe(MeS). La notation xoy permet en général d’économiser des parenthèses et elle est souvent plus lisible mais elle ne va que pour les opérateurs binaires. Pour un opérateur ternaire ou plus, il faut revenir à la première notation, o(x,y,z) , ou oxyz, ou à des formulations plus compliquées.

Les noms simples et les noms d’opérateurs suffisent pour faire tous les noms composés dont on a besoin dans les sciences.

Les prédicats fondamentaux, ou notions premières

Les phrases les plus simples pour le calcul des prédicats sont les formules atomiques. On les obtient en assemblant un nom de prédicat fondamental avec un ou plusieurs noms d’objet. Par exemple avec trois noms d’objet, Socrate, Pierre, Marie, et deux noms de prédicat unaire, est un homme, est une femme, on peut faire six formules atomiques : Socrate est un homme, Marie est une femme, etc. On dit que « … est une femme » est un prédicat unaire parce qu’il s’applique à un individu, c’est une qualité. Dans « un tel est amoureux de un tel», « … est amoureux de… » est un prédicat binaire et une relation binaire, parce qu’il s’applique à deux individus. Il y a aussi des relations ternaires comme « le bloody mary est un mélange de vodka et de jus de tomate », où « le … est un mélange de … et de … » est un prédicat ternaire.

Une règle très généralement acceptée en logique formelle consiste à toujours mettre un prédicat fondamental en premier suivi de ses arguments, c’est-à-dire les objets auxquels il est attribué. C’est ce qu’on nomme la notation préfixée ou notation polonaise. Cela donne humain Socrate pour dire que Socrate est humain et égal x y pour dire que x est égal à y. Pour une relation binaire R on préfère cependant souvent la notation infixée xRy à Rxy.

Les équations ou les égalités sont des phrases simples construites avec un prédicat binaire, noté = , très particulier quant à sa signification, mais qui ne pose pas de difficultés grammaticales.

Les noms d’objet et les prédicats fondamentaux permettent de faire toutes les phrases simples dont on a besoin dans les sciences.

L’algèbre de Boole des phrases complexes

Les opérateurs logiques permettent de faire des phrases complexes à partir de phrases simples.

Les opérateurs booléens sont la négation non, la conjonction et, la disjonction non-exclusive ou, l’implication implique, et quelques autres.

La négation est l’opérateur unaire « non » qui permet de faire la phrase non P à partir d’une phrase P.

Cet usage adopté par les logiciens donne « non Socrate est humain » pour signifier que Socrate n’est pas humain. Cette façon de nier est pratique quand on veut multiplier les négations à l’intérieur d’une phrase complexe. Elle ne pose pas d’autres difficultés que de choquer les habitudes.

Les autres opérateurs booléens sont binaires. La conjonction et la disjonction permettent de faire (P et Q) ainsi que (P ou Q) à partir de P et de Q.

Avec la conjonction on peut rassembler plusieurs assertions relatives à une même situation. Avec la disjonction, on peut rassembler plusieurs assertions relatives à plusieurs situations possibles. Les opérateurs booléens permettent ainsi de construire tout ce qui est dicible à partir d’un nombre fini de phrases simples.

La notion de conséquence peut être exprimée dans l’algèbre de Boole avec l’opérateur d’implication. P implique Q est souvent plutôt dit sous la forme si P alors Q .

L’algèbre de Boole est ainsi nommée parce que Boole a montré qu’on peut écrire certaines lois logiques sous la forme d’équations :

non nonP = P

non(PouQ) = nonP et nonQ

non(si P alors Q) = P et nonQ

et beaucoup d’autres.

Les affirmations d’existence et les lois générales

Il y a de nombreuses façons de formuler des lois et des énoncés d’existence. Celle qui s’est avérée la plus féconde en mathématique consiste à faire usage de noms de variable, ces x et ces y qui torturent parfois les esprits des élèves. Pour les logiciens, les mathématiciens et tous les scientifiques, les noms de variable sont pourtant des outils magnifiques. Toutes les difficultés de la syllogistique d’Aristote deviennent claires comme l’eau de roche dès qu’on a compris ce qu’on peut faire avec des noms de variable.

L’usage des noms de variable est très ancien, au moins aussi ancien que la géométrie. Aristote s’en est même servi pour énoncer les lois de la syllogistique. Mais il n’a pas compris que les règles syllogistiques elles-mêmes peuvent être déduites à partir d’un usage raisonné des noms de variable. Celui-ci a d’abord été développé par des algébristes, parce que les variables sont très utiles dans les équations. Frege et les autres inventeurs de la grande logique des classes et des relations, ceux qui ont réalisé la grande idée de Leibniz, la mathesis universalis, le calcul rationnel universel, qu’on appelle aujourd’hui le calcul des prédicats du premier ordre, ont compris toute l’expressivité que l’on pouvait tirer de l’usage des variables. L’usage des noms de variable, c’est la puissance expressive de la généralité, c’est une des manifestations les plus claires des capacités prédictives que la raison permet d’affiner à partir de la reconnaissances de motifs dans les phénomènes dont la perception suggère l’idée de cycle ou de répétition.

Au point de vue de la grammaire, les variables ne posent au premier abord aucune difficulté particulière. Les noms de variable sont des mots comme les autres. Il suffit de préciser de quoi ils sont des variables, objet, classe, relation, opérateur… On peut utiliser dans une phrase les noms de variable comme tous les autres noms. x est humain.

Les lois et les affirmations d’existence sont faites avec deux types d’opérateurs unaires construits sur les noms de variable. (pour tout x) et (il existe un x tel que) sont deux opérateurs unaires associés au nom de variable x. Le premier est l’opérateur universel en x, ou opérateur de généralisation. Le second est l’opérateur existentiel en x, ou opérateur d’existentiation. On les appelle aussi des quantificateurs. Les formules qui les contiennent sont dites quantifiées.

L’affirmation que tous les humains sont mortels est traduite dans le calcul des prédicats par, pour tout x, si x est humain alors x est mortel. C’est le résultat de l’application de l’opérateur (pour tout x) sur la phrase complexe (si x est humain alors x est mortel). L’affirmation qu’il y a au moins un être humain est traduite de même par, il existe un x tel que x est humain.

Les occurrences d’un nom de variable dans une phrase sont tous les endroits où ce nom apparait. Une occurrence peut être libre ou liée. Quand un opérateur existentiel ou universel en x est appliqué à une phrase complexe, toutes les occurrences de x deviennent liées, ou quantifiées, par cet opérateur. Toutes les occurrences qui ne sont pas ainsi liées sont libres.

Dans les théories du premier ordre, seules les variables d’objet peuvent être liées. Le domaine des objets, ou domaine d'existence, ou univers, ou ontologie, de la théorie, est aussi son domaine de quantification.

La distinction entre variable libre et variable liée est l’une des plus importantes pour la grammaire du calcul des prédicats. Elle est essentielle pour comprendre que les concepts sont des prédicats.

Les opérateurs booléens et les opérateurs universels et existentiels suffisent pour construire à partir des formules atomiques tous les énoncés dont on a besoin dans les sciences.

Les concepts sont des prédicats

Les prédicats d’une théorie sont d’abord ses prédicats fondamentaux, ceux que l’on peut identifier à ses notions premières. À partir d’eux, des objets de base, des variables et des opérateurs, on peut construire de nombreux prédicats dérivés, ou définis, à l’intérieur de la théorie. Il suffit d’écrire des formules qui contiennent des variables libres. Une formule qui contient une seule variable libre se nomme prédicat unaire. C’est un concept qualitatif. Une formule qui contient deux et seulement deux variables libres est appelée prédicat binaire, ou relation binaire, ou concept relationnel binaire. Quel que soit leur nombre de variables libres, pourvu qu’il soit au moins égal à un, les formules nomment des concepts.

Le concept de nombre premier peut être défini par le prédicat suivant, à l’intérieur de la théorie des nombres, supposés ici entiers positifs:

x est un nombre et pour tous nombres y et z, si y et z ne sont pas égaux à 1 alors x n’est pas égal à y fois z.

Dans la formule ci-dessus, les variables y et z sont liées. x est la seule variable libre. Cette formule est vraie si et seulement si x est un nombre premier. On peut donc la considérer comme un nom du concept de nombre premier.

Les concepts sont ou bien des notions premières, être un nombre, être égal à, être un ensemble, être dans… ou bien des notions dérivées, ne pas être égal à, être un nombre premier… Dans tous les cas, ce sont des prédicats. Le calcul des prédicats est le calcul des concepts.

Les concepts les plus fondamentaux sont en général ou bien qualitatifs, c’est-à-dire unaires, ou bien relationnels binaires. La logique d’Aristote est presque exclusivement consacrée aux concepts qualitatifs.

Pour faire la science, il faut faire des concepts. Pour la logique du premier ordre, les matériaux de base sont les notions premières, ou prédicats fondamentaux, les objets de base, les opérateurs d’objet, les variables d’objet, et un petit nombre d’opérateurs logiques, les opérateurs booléens et les opérateurs de généralisation et d’existentiation. Les règles de construction sont simplement celles qui viennent d’être présentées. Toutes les formules grammaticalement correctes de la logique du premier ordre nomment des concepts dès qu’elles contiennent des variables libres. La logique n’impose pas d’autres limites à la pensée que celles de la correction grammaticale. En ce sens, on peut voir le calcul des prédicats comme un chemin de libération intellectuelle, parce qu’il permet de penser tout ce qu’on veut, et de le faire sans tomber dans l’absurdité.

Une présentation plus formelle du calcul des prédicats

On se donne :

• $V$ un ensemble de symboles appelés variables, toujours infini ;
• $C$ un ensemble de symboles appelés constantes, éventuellement vide ;
• $P$ un ensemble de symboles de prédicats ;
• $F$ un ensemble de symboles de fonctions, éventuellement vide.
• une arité pour chaque symbole de prédicat ou de fonction, qui détermine le nombre d'arguments ;
• les symboles $\forall$ (pour tout) et $\exists$ (il existe au moins un), appelés quantificateurs ;
• les symboles $\lnot$ (non), $\wedge$ (et), $\lor$ (ou) et ⇒ (implique), qui sont les connecteurs logiques du calcul des propositions.

Il est toujours possible d’ajouter d'autres objets, on peut notamment enlever des connecteurs pour se contenter de ¬ et $\wedge$, ou d’un autre système minimal. On pourrait se contenter d’un seul quantificateur $\forall$ et de deux connecteurs logiques $\neq$ et $\wedge$ sans perdre en expressivité.

On appellera termes les formules composées ainsi :

• $x\in V$ est un terme ;
• $x\in C$ est un terme ;
• si $f$ est un symbole de fonction n-aire et $t_{1},t_{2},\dots ,t_{n}$ sont des termes, alors $f\;t_{1}t_{2}\dots t_{n}$ est un terme.

Appelons $T$ l’ensemble des termes.

Les énoncés du calcul des prédicats du premier ordre sont les suivants, et uniquement les suivants (appelons $E$ l’ensemble des énoncés):

• $p\;t_{1}t_{2}\dots t_{n}$ si $(t_{1},t_{2},\dots ,t_{n})\in T^{n}$, $p\in P$ et p est n-aire (une telle formule est appelée un atome ou une formule atomique) ;
• $e_{1}\wedge e_{2}$ si $e_{1},e_{2}\in E$ ;
• $e_{1}\lor e_{2}$ si $e_{1},e_{2}\in E$ ;
• $e_{1}\implies e_{2}$ si $e_{1},e_{2}\in E$ ;
• $\neg e$ si $e\in E$ ;
• $\forall x(e)$ si $e\in E$ et $x\in V$ ;
• $\exists x(e)$ si $e\in E$ et $x\in V$.

Ce système très formel peut s'instancier, par exemple en l'arithmétique en prenant pour fonctions 0-aires les nombres (entiers par exemple) pour fonctions binaires les symboles des opérations « + » et « × » et comme prédicats binaires, les symboles « = » et « < ».