Terme (llògica)

En llògica matemàtica, un terme és una disposició de símbols depenents/vinculats que denota un objecte matemàtic dins d'una expressió/fòrmula. En particular, els térmens apareixen com a components d'una fòrmula. Açò és anàlec al llenguage natural, a on un sintagma nominal es referix a un objecte i una oració completa es referix a un fet.

Un terme de primer orde és construït recursivamente format utilisant símbols de constants, símbols de variables i símbols de funció.

Una expressió formada en aplicar un símbol de predicat a un número apropiat de térmens es denomina fòrmula atòmica, que s'evalua com verdadera o falsa en llògica bivalente, donant una interpretació.

Per eixemple, Plantilla:Tmath és un terme construït a partir de la constant 1, la variable x i els símbols de funció binaria Plantilla:Tmath i Plantilla:Tmath. Forma part de la fòrmula atòmica Plantilla:Tmath, que s'evalua com a verdadera per a cada valor valor real de x.

Ademés d'en llògica, els térmens eixerciten un paper important en àlgebra universal i en reescritura.

Definició

Esquerra i dreta: estructures en arbre del terme (n⋅(n+1))/2 i del terme n⋅((n+1)/2)

Donat un conjunt V de símbols de variables, un conjunt C de símbols de constants i conjunts F_n de símbols de funcions n-àries, també cridats símbols d'operadors, per a cada número natural n = 1, el conjunt de térmens T (de primer orde no ordenats) és definit recursivamente com el conjunt més chicotet en les següents propietats:

• Cada símbol de variable és un terme: V ⊆ T
• Cada símbol de constant és un terme: C ⊆ T
• A partir de cada n térmens t₁,...,t_n, i cada símbol de funció n-ària f ∈ F_n, es pot construir un terme major f(t₁, ..., t_n).

Usant una notació intuïtiva, pseudo-gramatical, açò a voltes s'escriu com:

t ::= x | c | f(t₁, ..., t_n).

La simbologia del llenguage de térmens descriu qué conjunts de símbols de funció F_n estan ocupats. Eixemples coneguts són els símbols de funció unarios sense, cos ∈ F₁ i els símbols de funció binarios +, −, ⋅, / ∈ F₂. Les operacions ternarias i les funcions de aridad superior són possibles, pero poc comunes en la pràctica. Molts autors consideren els símbols constants com a símbols de funció 0-aris F₀, per lo que no requerixen una classe sintàctica especial per a ells.

Un terme denota un objecte matemàtic del domini de discurs. Una constant c denota un objecte en nom d'eixe domini, una variable x recorre els objectes d'eixe domini, i una funció n-ària f mapea n-tuplas d'objectes a objectes. Per eixemple, si n ∈ V és un símbol de variable, 1 ∈ C és un símbol de constant i add ∈ F₂ és un símbol de funció binaria, llavors n ∈ T, 1 ∈ T i (per lo tant) add(n, 1) ∈ T es definixen segons la primera, segona i tercera regla de construcció de térmens, respectivament. L'últim terme se sol escriure com a n+1, utilisant la notació de infijo i l'operador més comú + per a major comoditat.

Estructura de térmens front a representació

Originalment, els llògics definien un terme com una cadena de caràcters que seguia certes regles de construcció. No obstant, des de que el concepte d'arbre es va popularisar en informàtica, va resultar més convenient concebre un terme com un arbre. Per eixemple, vàries cadenes de caràcters distintes, com "(n⋅(n+1))/2", "((n⋅(n+1)))/2" i "$\frac{n(n+1)}{2}$", representen el mateix terme i corresponen al mateix arbre, és dir, l'arbre de l'esquerra en l'image superior.

En separar l'estructura arbòrea d'un terme de la seua representació gràfica en paper, també és fàcil tindre en conte els paréntesis (que són solament representació, no estructura) i els operadors de multiplicació invisibles (que existixen solament en l'estructura, no en la representació).

Igualtat estructural

Es diu que dos térmens són estructuralment, lliteralment o sintácticamente iguals si corresponen al mateix arbre. Per eixemple, els arbres de l'esquerra i la dreta en l'image superior són térmens estructuralment desiguals, encara que podrien considerar-se semánticamente iguals ya que sempre s'evaluen al mateix valor en aritmètica racional. Si be l'igualtat estructural es pot comprovar sense conéixer el significat dels símbols, l'igualtat semàntica no. Si la funció / s'interpreta, per eixemple, no com la divisió racional sino com la divisió truncada a la part sancera, llavors en n=2 els térmens de l'esquerra i la dreta s'evaluen a 3 i 2, respectivament.

Estructuralment, els térmens iguals deuen coincidir en els noms de les seues variables.

En canvi, un terme t es denomina renombrado o variant d'un terme o si este últim resulta del renombrado simultàneu de totes les variables del primer, és dir, si o = tσ per a algun σ d'acort en alguna substitució de noms. En eixe cas, o també és un renombrado de t, ya que una substitució de renombrado σ té un invers σ⁻¹, i t = oσ⁻¹. Abdós térmens es consideren llavors iguals mòdul renombrado. En molts contexts, els noms de les variables en un terme no importen. Per eixemple, l'axioma de conmutatividad per a la suma pot enunciar-se com a x + i = i + x o com a + b = b + a. En tals casos, la fòrmula completa pugues renombrarse, mentres que un subtérmino arbitrari generalment no. Per eixemple, x+i=b+a no és una versió vàlida de l'axioma de conmutatividad.

Térmens bàsics i llineals

El conjunt de variables d'un terme t es denota per vars(t).

Un terme que no conté variables es denomina terme bàsic; un terme que no conté múltiples ocurrències d'una variable es denomina terme llineal.

Per eixemple, 2+2 és un terme bàsic i, per lo tant, també un terme llineal; x·(n+1) és un terme llineal; n·(n+1) és un terme no llineal. Estes propietats són importants, per eixemple, en reescritura.

Donat una simbologia per als símbols de funció, el conjunt de tots els térmens forma el àlgebra de térmens lliure. El conjunt de tots els térmens bàsics forma el àlgebra de térmens inicial.

Si s'abrevia el número de constants com a f₀ i el número de símbols de funció i-ària com a f_i, el número θ_h de térmens fonamentals distints d'altura fins a h es pot calcular per mig de la següent fòrmula de recursión:

• θ₀ = f₀, ya que un terme bàsic d'altura 0 solament pot ser una constant,
• ${\theta }_{h+1}=\sum _{i=0}^{\mathrm{\infty }}{f}_i\cdot {\theta }_h^i$, ya que un terme fonamental d'altura fins a h+1 es pot obtindre component qualssevol i térmens fonamentals d'altura fins a h, utilisant un símbol de funció raïl i-ària. La suma té un valor finito si solament hi ha un número finito de constants i símbols de funció, la qual cosa sol ser el cas.

Construcció de fòrmules a partir de térmens

Donat un conjunt R_n de símbols de relació n-ària per a cada número natural n = 1, s'obté una fòrmula atòmica (de primer orde no ordenada) aplicant un símbol de relació n-ària a n térmens. Sobre els símbols de funció, un conjunt de símbols de relació R_n sol ser no buide solament per a valors menuts de n. En llògica matemàtica, es construïxen fòrmules més complexes a partir de fòrmules atòmiques utilisant conectiva llògica i quantificadorés. Per eixemple, si R denota el conjunt dels número real, ∀x: x ∈ R ⇒ (x+1)⋅(x+1) ≥ 0 és una fòrmula matemàtica que s'evalua com a verdadera en l'àlgebra de número complejo.

Una fòrmula atòmica es denomina bàsica si es construïx completament a partir de térmens bàsics. Totes les fòrmules atòmiques bàsiques que es poden compondre a partir d'un conjunt donat de símbols de funció i predicat conformen la base de Herbrand per a estos conjunts de símbols.

Operacions en térmens

Estructura d'arbre del terme d'eixemple de color negre $\frac{a*((a+1)*(a+2))}{1*(2*3)}$, en Plantilla:Tmath en blava

• Ya que un terme té l'estructura d'una jerarquia d'arbre, a cada u dels seus nodos se li pot assignar una posició o ruta, és dir, una cadena d'número natural que indica la posició del nodo en la jerarquia. La cadena buida, comunament denotada per ε, s'assigna al nodo raïl. Les cadenes de posició dins del terme negre s'indiquen en roig en l'image.

• En cada posició p d'un terme t, comença un únic subtérmino, comunament denotat per t|_p. Per eixemple, en la posició 122 del terme negre en l'image, el subtérmino a+2 té la seua raïl. La relació és un subtérmino de és un conjunt parcialment ordenat en el conjunt de térmens. Es tracta d'una relació reflexiva, ya que cada terme és trivialmente un subtérmino de sí mateixa.

• El terme obtingut en reemplaçar en un terme t el subtérmino en la posició p per un nou terme o es denota comunament per t[o]p. El terme t[o]p també pot considerar-se com el resultat d'una concatenació generalisada del terme o en un objecte similar a un terme t[.]. Este últim es denomina context o terme en un buit (indicat per .; la seua posició és p), en el que es diu que o està incrustat. Per eixemple, si t és el terme negre en l'image, llavors t[b+1]₁₂ dona com resultat el terme $\frac{a*(b+1)}{1*(2*3)}$. Este últim terme també resulta d'incrustar el terme b+1 en el context de $\frac{a*(.)}{1*(2*3)}$. En un sentit informal, les operacions d'instanciación i de incrustación són inverses entre sí: mentres que la primera agrega símbols de funció en la part inferior del terme, la segona els agrega en la part superior. L'operació d'ordenament de abarcación relaciona un terme en qualsevol resultat de agregació en abdós costats.

• A cada nodo d'un terme se li pot assignar la seua profunditat (denominada altura per alguns autors), és dir, la seua distància (número d'arestes) des de la raïl. En este context, la profunditat d'un nodo sempre és igual a la llongitut de la seua cadena de posició. En l'image, els nivells de profunditat del terme negre s'indiquen en vert.

• El tamany d'un terme es referix comunament al número dels seus nodos o, equivalentemente, a la llongitut de la seua representació escrita, contant els símbols sense paréntesis. Els térmens negre i blau de l'image tenen un tamany de 15 i 5, respectivament.

• Un terme o coincidix en un terme t si una instància de substitució de o és estructuralment igual a un subtérmino de t, o formalment, si oσ= t|_p per a alguna posició p en t i alguna substitució σ . En este cas, o, t i σ es denominen, respectivament, terme patró, terme subjecte i substitució corresponent. En l'image, el terme patró blau Plantilla:Tmath coincidix en el terme subjecte negre en la posició 1, i la substitució corresponent {x ↦ a, i ↦ a+1, z ↦ a+2 } s'indica per mig de variables blaves situades immediatament a l'esquerra dels seus substituts negres. Intuitivamente, el patró, llevat les seues variables, deu estar contingut en el subjecte. Si una variable apareix vàries voltes en el patró, es requerixen subtérminos iguals en les posicions corresponents del subjecte.

Vore també

• Equació
• Expressió matemàtica
• Unificació (ciències de la computació)
• Reescritura

Bibliografia

• (1999) Term Rewriting and All That, Cambridge University Press, pp. 1–2 and 34–35. ISBN 978-0-521-77920-3.