Terme (logique)

Un terme est une expression de base du calcul des prédicats, de l'algèbre, notamment de l'algèbre universelle, et du calcul formel, des systèmes de réécriture et de l'unification. C'est l'objet produit par une analyse syntaxique. Sa principale caractéristique est d'être homogène (il n'y a que des opérations de base et pas d'opérations logiques) et de décrire l'agencement des opérations de base. Un terme est parfois appelé une formule du premier ordre. Par exemple, (x + f(x,y)) * 3 et *(+(x,f(x,y)),3) et *+xfxy3 et la figure à droite représentent le même terme sous quatre formes externes différentes.

Le terme (x + f(x,y)) * 3 sous forme arborescente

DescriptionModifier

À la base des termes, il y a des opérateurs qui sont répartis dans une signature. Les opérateurs sont les symboles de base, tandis que la signature attribue une arité à chaque opérateur. L'arité est le nombre d'arguments qu'attend un opérateur. Ainsi il y aura des opérateurs unaires (d'arité 1), des opérateurs binaires (d'arité 2), des opérateurs ternaires (d'arité 3) et plus généralement des opérateurs  -aires. Les opérateurs 0-aires sont ceux qui n'attendent pas d'arguments et sont appelés des constantes. Dans le cas où on désire des termes avec des variables on ajoute à l'ensemble   un ensemble dénombrable   dit ensemble des variables. Plus formellement une signature est définie ainsi :

 ,

  est l'ensemble des opérateurs  -aires. Par exemple, dans les groupes, la signature comporte trois ensembles non vides d'opérateurs  ,   et  . Autrement dit, dans les groupes il y a une constante  , un opérateur unaire qui s'écrit   (notation suffixe) quand il est appliqué à un élément   et un opérateur binaire qui s'écrit (notation infixe)   quand il est appliqué à   et  . Notons cependant que la plupart du temps les termes sont écrits en notation préfixée, c'est-à-dire sous la forme  , par exemple   pour un opérateur ternaire. Notons aussi que si l'arité est bien spécifiée, on peut se passer des parenthèses dans une notation dite notation polonaise ou notation de Łukasiewicz

Il y a différentes définitions des termes qui sont équivalentes.

Définition récursiveModifier

On peut définir récursivement l'ensemble   des termes ainsi

 

Définition comme application d'un ensemble de positions vers une signatureModifier

La définition utilisant la notion d'ensemble de positions d'un terme permet de décrire facilement différentes propriétés et différents algorithmes sur les termes.

Un ensemble   de mots sur l'ensemble des entiers positifs est un ensemble de positions si

  1.   est fini et non vide,
  2.   et   préfixe de   impliquent  ,
  3.   et   et   impliquent  .

Un terme   est une application d'un ensemble   de positions dans une signature avec la contrainte que si   alors   si et seulement si  .   est alors appelé l'ensemble des positions du terme   et noté  .

La propriété 2. ci-dessus signifie que si   est une position d'un terme, alors toute position préfixe est aussi une position dans le terme (située au-dessus). La propriété 3. ci-dessus signifie que si   est une position d'un terme, alors toute position située sous le même symbole mais à sa gauche est aussi une position dans le terme. La contrainte ajoutée dit que si un nœud est étiqueté par un symbole d'arité   alors il a exactement   fils.

Définition en tant qu'arbre étiqueté orientéModifier

 
Représentation arborescente des termes (n*(n+1))/2 et n*((n+1)/2)

Un terme peut être vu comme un arbre[1] étiqueté (à chaque nœud est associé une étiquette prise dans la signature) orienté (les fils d'un nœud sont ordonnés de droite à gauche). Il y a de plus une contrainte, à savoir que le nombre de fils d'un nœud est donné par l'arité de l'étiquette du nœud. On parle de représentation arborescente d'un terme.

Un exempleModifier

Considérons la signature

  •   
  •  
  •   pour  .

Soit   le terme tel que   et

  •  
  •  
  •  
  •  
  •  
  •  
  •  .

Il s'agit du terme de gauche de la figure ci-dessus. Il s'écrit   en notation récursive préfixée,   en notation polonaise et   en notation infixe.

Quelques définitions liées aux termesModifier

Le nombre d'éléments de   s'appelle la taille de  . La position   (le mot vide de  ) est la racine et   est le symbole à la racine.

Un terme sans variable est dit clos ou fermé. Un terme qui n'est pas fermé est dit ouvert.

Le symbole à la position   dans   est le symbole de   associé à   par la fonction  . Si   alors  , autrement dit le symbole à la position   dans  , n'est pas défini.

Si   est une position de  , le sous-terme de   à la position   s'écrit   et se définit comme suit. Les positions de   forment l'ensemble des suffixes de   dans  , autrement dit:

 .

Enfin  . La racine de   est le symbole à la position   dans  , autrement dit  . Dans l'exemple ci-dessus,   est le terme  .

Algèbre et algèbre des termesModifier

L'enracinement est l'opération qui consiste à prendre un opérateur   d'arité   et   termes  , ...,   et à créer un terme  . L'enracinement permet de munir l'ensemble des termes d'une structure d'algèbre universelle.

Il existe un morphisme naturel de l'algèbre des termes vers n'importe laquelle des algèbres de même signature. Ce morphisme fait de l'algèbre des termes sur une signature donnée   une algèbre initiale de la catégorie des algèbres de signature  .

BibliographieModifier

Voir aussiModifier

Notes & RéférencesModifier

  1. La tradition veut que la racine des arbres soit positionnée en haut!