Terme (logique)

On peut définir récursivement l'ensemble ${\displaystyle T}$ des termes ainsi

${\displaystyle T=\bigcup _{i=0}^{\infty }\bigcup _{f\in \Sigma _{i}}f(T,...i~fois...,T)}$

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 ${\displaystyle {\mathit {P}}}$ de mots sur l'ensemble des entiers positifs est un ensemble de positions si

1. ${\displaystyle {\mathit {P}}}$ est fini et non vide,
2. ${\displaystyle p\in {\mathit {P}}}$ et ${\displaystyle q}$ préfixe de ${\displaystyle p}$ impliquent ${\displaystyle q\in {\mathit {P}}}$,
3. ${\displaystyle pi\in {\mathit {P}}}$ et ${\displaystyle j\in \mathbb {N} -\{0\}}$ et ${\displaystyle j<i}$ impliquent ${\displaystyle pj\in {\mathit {P}}}$.

Un terme ${\displaystyle s}$ est une application d'un ensemble ${\displaystyle {\mathit {P}}}$ de positions dans une signature avec la contrainte que si ${\displaystyle s(p)=f\in \Sigma _{n}}$ alors ${\displaystyle pi\in {\mathit {P}}}$ si et seulement si ${\displaystyle i\leq n}$. ${\displaystyle {\mathit {P}}}$ est alors appelé l'ensemble des positions du terme ${\displaystyle s}$ et noté ${\displaystyle {\mathit {Pos}}(s)}$.

La propriété 2. ci-dessus signifie que si ${\displaystyle p}$ 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 ${\displaystyle p}$ 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é ${\displaystyle n}$ alors il a exactement ${\displaystyle n}$ fils.

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.

Considérons la signature

• ${\displaystyle \Sigma _{0}=X\cup \{0,1,2,...\}}$ où ${\displaystyle X=\{n,m,n',m'\}}$
• ${\displaystyle \Sigma _{2}=\{+,*,/\}}$
• ${\displaystyle \Sigma _{i}=\emptyset }$ pour ${\displaystyle 0\neq i\neq 2}$.

Soit ${\displaystyle t}$ le terme tel que ${\displaystyle {\mathit {Pos}}(t)=\{\varepsilon ,1,2,11,12,121,122\}}$ et

• ${\displaystyle t(\varepsilon )=/}$
• ${\displaystyle t(1)=*}$
• ${\displaystyle t(2)=2}$
• ${\displaystyle t(11)=n}$
• ${\displaystyle t(12)=+}$
• ${\displaystyle t(121)=n}$
• ${\displaystyle t(122)=1}$.

Il s'agit du terme de gauche de la figure ci-dessus. Il s'écrit ${\displaystyle /(*(n,+(n,1)),2)}$ en notation récursive préfixée, ${\displaystyle /*+n1n2}$ en notation polonaise et ${\displaystyle (n*(n+1))/2}$ en notation infixe.

Le nombre d'éléments de ${\displaystyle {\mathit {Pos}}(s)}$ s'appelle la taille de ${\displaystyle s}$. La position ${\displaystyle \varepsilon }$ (le mot vide de ${\displaystyle (\mathbb {N} -\{0\})^{*}}$) est la racine et ${\displaystyle s(\varepsilon )}$ 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 ${\displaystyle p}$ dans ${\displaystyle t}$ est le symbole de ${\displaystyle \mathbf {\Sigma } }$ associé à ${\displaystyle p\in {\mathit {Pos}}(t)}$ par la fonction ${\displaystyle t:{\mathit {Pos}}(t)\rightarrow \mathbf {\Sigma } }$. Si ${\displaystyle p\notin {\mathit {Pos}}(t)}$ alors ${\displaystyle t(p)}$, autrement dit le symbole à la position ${\displaystyle p}$ dans ${\displaystyle t}$, n'est pas défini.

Si ${\displaystyle p}$ est une position de ${\displaystyle t}$, le sous-terme de ${\displaystyle t}$ à la position ${\displaystyle p}$ s'écrit ${\displaystyle t_{|p}}$ et se définit comme suit. Les positions de ${\displaystyle t_{|p}}$ forment l'ensemble des suffixes de ${\displaystyle p}$ dans ${\displaystyle Pos(t)}$, autrement dit:

${\displaystyle Pos(t_{|p})=\{q\in (\mathbb {N} -\{0\})^{*}\mid pq\in Pos(t)\}}$.

Enfin ${\displaystyle t_{|p}(q)=t(pq)}$. La racine de ${\displaystyle t_{|p}}$ est le symbole à la position ${\displaystyle p}$ dans ${\displaystyle t}$, autrement dit ${\displaystyle t_{|p}(\varepsilon )=t(p)}$. Dans l'exemple ci-dessus, ${\displaystyle t_{|p}}$ est le terme ${\displaystyle n+2}$.