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.
![](http://up.wiki.x.io/wikipedia/commons/thumb/d/dd/Term_as_a_tree.jpg/220px-Term_as_a_tree.jpg)
Description
modifierÀ 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 :
- ,
où 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écursive
modifierOn peut définir récursivement l'ensemble des termes ainsi
Définition comme application d'un ensemble de positions vers une signature
modifierLa 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
- est fini et non vide,
- et préfixe de impliquent ,
- 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é
modifierUn 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 exemple
modifierConsidérons la signature
- où
- 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 termes
modifierLe 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 termes
modifierL'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 .
Bibliographie
modifier- (en) Terese, Term Rewriting Systems, Cambridge Tracts in Theoretical Computer Science, 2003 (ISBN 0521391156)
- (en) Franz Baader et Tobias Nipkow, Term Rewriting and All That, Cambridge (GB), Cambridge University Press, (1re éd. 1998), 301 p. (ISBN 0-521-45520-0 et 0521779200, présentation en ligne)
Voir aussi
modifierNotes & Références
modifier- La tradition veut que la racine des arbres soit positionnée en haut!