Término (lógica)

En lógica matemática , un término es una disposición de símbolos interrelacionados que denota un objeto matemático dentro de una expresión o fórmula. En particular, los términos aparecen como componentes de una fórmula. Esto es análogo al lenguaje natural, donde un sintagma nominal se refiere a un objeto y una oración completa se refiere a un hecho.

Un término de primer orden se construye recursivamente a partir de símbolos constantes, símbolos variables y símbolos de función . Una expresión formada al aplicar un símbolo de predicado a un número apropiado de términos se llama fórmula atómica , que se evalúa como verdadera o falsa en lógicas bivalentes , dada una interpretación . Por ejemplo , $(x+1)*(x+1)$ ⁠ es un término construido a partir de la constante 1, la variable $x$ y los símbolos de función binaria ⁠ $+$ y $*$ ; es parte de la fórmula atómica $(x+1)*(x+1)\geq 0$ que se evalúa como verdadero para cadavalor real de $x$ .

Además de en lógica , los términos desempeñan papeles importantes en el álgebra universal y en los sistemas de reescritura .

Definición

Dado un conjunto V de símbolos de variables, un conjunto C de símbolos de constantes y conjuntos F _n de símbolos de funciones n -arias, también llamados símbolos de operadores, para cada número natural n ≥ 1, el conjunto de términos (de primer orden no ordenados) T se define recursivamente como el conjunto más pequeño con las siguientes propiedades: ^{[ 1 ]}

cada símbolo de variable es un término: $V \subseteq T$ ,
cada símbolo constante es un término: $C \subseteq T$ ,
A partir de cada n términos t ₁ ,..., t _n , y cada símbolo de función n -aria $f \in F n$ , se puede construir un término mayor f ( t ₁ , ..., t _{n ).}

Utilizando una notación pseudogramatical intuitiva , a veces se escribe así:

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

La signatura del lenguaje describe qué conjuntos de símbolos de función F _n están presentes. Ejemplos conocidos son los símbolos de función unaria $sin, cos \in F 1$ , y los símbolos de función binaria $+, -, \cdot, / \in F 2$ . Las operaciones ternarias y las funciones de aridad superior son posibles, pero poco comunes en la práctica. Muchos autores consideran los símbolos constantes como símbolos de función 0-aria F ₀ , por lo que no necesitan una clase sintáctica especial.

Un término denota un objeto matemático del dominio del discurso . Una constante c denota un objeto con nombre de ese dominio, una variable x recorre los objetos de ese dominio, y una función n -aria f asigna n - tuplas de objetos a objetos. Por ejemplo, si $n \in V$ es un símbolo de variable, $1 \in C$ es un símbolo de constante, y $add \in F 2$ es un símbolo de función binaria, entonces $n \in T, 1 \in T$ , y (por lo tanto) $add (n, 1) \in T$ según la primera, segunda y tercera regla de construcción de términos, respectivamente. El último término se suele escribir como n +1, utilizando la notación infija y el símbolo de operador más común + para mayor comodidad.

Estructura de términos frente a representación

Originalmente, los lógicos definieron un término como una cadena de caracteres que se adhiere a ciertas reglas de construcción. ^{[ 2 ]} Sin embargo, dado que el concepto de árbol se popularizó en la informática, resultó más conveniente pensar en un término como un árbol. Por ejemplo, varias cadenas de caracteres distintas, como " $(n \cdot(n +1))/2$ ", " $((n \cdot(n +1)))/2$ ", y " ${\frac {n(n+1)}{2}}$ ", denotan el mismo término y corresponden al mismo árbol, a saber, el árbol de la izquierda en la imagen anterior. Al separar la estructura de árbol de un término de su representación gráfica en papel, también es fácil tener en cuenta los paréntesis (que son solo representación, no estructura) y los operadores de multiplicación invisibles (que existen solo en la estructura, no en la representación).

Igualdad estructural

Se dice que dos términos son estructural , literalmente o sintácticamente iguales si corresponden al mismo árbol. Por ejemplo, el árbol izquierdo y el derecho en la imagen anterior son términos estructuralmente desiguales , aunque podrían considerarse " semánticamente iguales " ya que siempre se evalúan al mismo valor en aritmética racional . Si bien la igualdad estructural se puede comprobar sin ningún conocimiento sobre el significado de los símbolos, la igualdad semántica no. Si la función / se interpreta, por ejemplo, no como racional sino como división entera truncada , entonces en n = 2 el término izquierdo y el derecho se evalúan a 3 y 2, respectivamente. Los términos estructuralmente iguales deben coincidir en sus nombres de variables.

En cambio, un término t se denomina renombramiento , o variante , de un término u si este último resulta del renombramiento sistemático de todas las variables del primero, es decir, si u = tσ para alguna sustitución de renombramiento σ. En ese caso, u también es un renombramiento de t , puesto que una sustitución de renombramiento σ tiene un inverso σ ⁻¹ , y t = uσ ⁻¹ . Se dice entonces que ambos términos son iguales módulo el renombramiento . En muchos contextos, los nombres particulares de las variables en un término no importan; por ejemplo, el axioma de conmutatividad para la suma puede enunciarse como x + y = y + x o como a + b = b + a ; en tales casos, toda la fórmula puede renombrarse, mientras que un subtérmino arbitrario generalmente no puede, por ejemplo, x + y = b + a no es una versión válida del axioma de conmutatividad. ^{[ nota 1 ]}^{[ nota 2 ]}

Términos fundamentales y lineales

El conjunto de variables de un término t se denota por vars ( t ). Un término que no contiene ninguna variable se llama término base ; un término que no contiene múltiples ocurrencias de una variable se llama término lineal . Por ejemplo, 2+2 es un término base y, por lo tanto, también un término lineal; x ⋅( n +1) es un término lineal; n ⋅( n +1) es un término no lineal. Estas propiedades son importantes, por ejemplo, en la reescritura de términos .

Dada una signatura para los símbolos de función, el conjunto de todos los términos forma el álgebra de términos libres . El conjunto de todos los términos base forma el álgebra de términos iniciales .

Si se abrevia el número de constantes como f ₀ y el número de símbolos de función i -aria como f _i , el número θ _h de términos básicos distintos de una altura hasta h se puede calcular mediante la siguiente fórmula de recursión:

θ ₀ = f ₀ , ya que un término de suelo de altura 0 solo puede ser una constante,
$\theta _{h+1}=\sum _{i=0}^{\infty }f_{i}\cdot \theta _{h}^{i}$ Dado que un término fundamental de altura hasta h + 1 se puede obtener componiendo cualesquiera i términos fundamentales de altura hasta h , utilizando un símbolo de función raíz i -aria. La suma tiene un valor finito si solo hay un número finito de constantes y símbolos de función, lo cual suele ser el caso.

Construir fórmulas a partir de términos

Dado un conjunto R _n de símbolos de relación n- aria para cada número natural n ≥ 1, se obtiene una fórmula atómica (de primer orden no ordenada) aplicando un símbolo de relación n -aria a n términos. En cuanto a los símbolos de función, un conjunto de símbolos de relación R _n suele ser no vacío solo para n pequeño . En lógica matemática, se construyen fórmulas más complejas a partir de fórmulas atómicas utilizando conectores lógicos y cuantificadores . Por ejemplo, si denotamos por ℝ el conjunto de los números reales , $\forall x : x \in ℝ \Rightarrow (x +1)\cdot(x +1) \geq 0$ es una fórmula matemática que se evalúa como verdadera en el álgebra de los números complejos . Una fórmula atómica se denomina base si se construye completamente a partir de términos base; todas las fórmulas atómicas base componibles a partir de un conjunto dado de símbolos de función y predicado conforman la base de Herbrand para estos conjuntos de símbolos.

Operaciones con términos

{\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}} — Estructura de árbol del término de ejemplo negro ${\frac {a*((a+1)*(a+2))}{1*(2*3)}}$ , con rojo azul ⁠ $x*(y*z)$ ⁠

Dado que un término tiene la estructura de una jerarquía de árbol, a cada uno de sus nodos se le puede asignar una posición o ruta , es decir, una cadena de números naturales que indica su lugar en la jerarquía. La cadena vacía, comúnmente representada por ε, se asigna al nodo raíz. Las cadenas de posición dentro del término negro se indican en rojo en la imagen.
En cada posición p de un término t , comienza un subtérmino único , que se suele denotar por $t | p$ . Por ejemplo, en la posición 122 del término negro de la imagen, el subtérmino a + 2 tiene su raíz. La relación "es un subtérmino de" es un orden parcial sobre el conjunto de términos; es reflexiva, ya que cada término es trivialmente un subtérmino de sí mismo.
El término obtenido al reemplazar en un término t el subtérmino en una posición p por un nuevo término u se denota comúnmente por $t [u] p$ . El término $t [u] p$ también puede verse como el resultado de una concatenación generalizada del término u con un objeto similar a un término $t [.]$ ; este último se llama contexto , o un término con un hueco (indicado por "."; su posición es p ), en el cual se dice que u está incrustado . Por ejemplo, si t es el término negro en la imagen, entonces $t [b +1] 12$ resulta en el término ${\frac {a*(b+1)}{1*(2*3)}}$ . Este último término también resulta de incrustar el término $b +1$ en el contexto ${\frac {a*(\;.\;)}{1*(2*3)}}$ En un sentido informal, las operaciones de instanciación e incrustación son inversas entre sí: mientras que la primera añade símbolos de función en la parte inferior del término, la segunda los añade en la parte superior. El orden de englobamiento relaciona un término con cualquier resultado de las adiciones en ambos lados.
A cada nodo de un término se le puede asignar una profundidad (denominada altura por algunos autores), es decir, su distancia (número de aristas) desde la raíz. En este caso, la profundidad de un nodo siempre es igual a la longitud de su cadena de posición. En la imagen, los niveles de profundidad del término en negro se indican en verde.
El tamaño de un término se refiere comúnmente al número de sus nodos o, de forma equivalente, a la longitud de su representación escrita, contando los símbolos sin paréntesis. Los términos en negro y azul de la imagen tienen un tamaño de 15 y 5, respectivamente.
Un término u coincide con un término t si una instancia de sustitución de u es estructuralmente igual a un subtérmino de t , o formalmente, si $u σ = t | p$ para alguna posición p en t y alguna sustitución σ. En este caso, u , t y σ se denominan, respectivamente , término patrón , término sujeto y sustitución coincidente . En la imagen, el término patrón azul $x*(y*z)$ ⁠ coincide con el término sujeto negro en la posición 1, con la sustitución correspondiente ${x \mapsto a, y \mapsto a +1, z \mapsto a +2 }$ indicada por las variables azules inmediatamente a la izquierda de sus sustitutos negros. Intuitivamente, el patrón, excepto sus variables, debe estar contenido en el sujeto; si una variable aparece varias veces en el patrón, se requieren subtérminos iguales en las posiciones respectivas del sujeto.
términos unificadores
reescritura de términos

Conceptos relacionados

Términos ordenados

Cuando el dominio del discurso contiene elementos de tipos fundamentalmente diferentes, es útil dividir el conjunto de todos los términos en consecuencia. Para ello, se asigna una clasificación (a veces también llamada tipo ) a cada variable y a cada símbolo constante, y una declaración ^{[ nota 3 ]} de clasificaciones de dominio y de rango a cada símbolo de función. Un término clasificado f ( t ₁ ,..., t _n ) puede estar compuesto por subtérminos clasificados t ₁ ,..., t _n solo si la clasificación del $i$ -ésimo subtérmino coincide con la $i$ - ésima clasificación de dominio declarada de f . Dicho término también se denomina bien clasificado ; cualquier otro término (es decir, que solo obedece las reglas de no clasificación ) se denomina mal clasificado .

Por ejemplo, un espacio vectorial viene con un campo asociado de números escalares. Sean W y N el tipo de vectores y números, respectivamente, sean V _W y V _N el conjunto de variables vectoriales y numéricas, respectivamente, y C _W y C _N el conjunto de constantes vectoriales y numéricas, respectivamente. Entonces, por ejemplo, ${\vec {0}}\en C_{W}$ y $0 \in C N$ , y la suma vectorial, la multiplicación escalar y el producto interno se declaran como ⁠ $+:W\times W\to W,*:W\times N\to W$ y $\langle .,.\rangle :W\times W\to N$ ⁠ , respectivamente. Suponiendo símbolos variables ${\vec {v}},{\vec {w}}\en V_{W}$ y $a, b \in V N$ , el término $\langle ({\vec {v}}+{\vec {0}})*a,{\vec {w}}*b\rangle$ está bien ordenado, mientras que ${\vec {v}}+a$ no lo es (ya que + no acepta un término de tipo N como segundo argumento). Para hacer $a*{\vec {v}}$ un término bien ordenado, una declaración adicional $*:N\times W\to W$ ⁠ es obligatorio. Los símbolos de función que tienen varias declaraciones se denominan sobrecargados .

Consulte la lógica de clasificación múltiple para obtener más información, incluidas las extensiones del marco de clasificación múltiple descrito aquí.

Términos Lambda

Motivación

Las notaciones matemáticas que se muestran en la tabla no se ajustan al esquema de un término de primer orden definido anteriormente , ya que todas introducen una variable local o ligada propia que puede no aparecer fuera del ámbito de la notación, por ejemplo $t\cdot \int _{a}^{b}\sin(k\cdot t)\;dt$ No tiene sentido. En cambio, las otras variables, denominadas libres , se comportan como variables de término de primer orden ordinarias, por ejemplo $k\cdot \int _{a}^{b}\sin(k\cdot t)\;dt$ Tiene sentido.

Todos estos operadores pueden considerarse como operadores que toman una función, en lugar de un valor, como uno de sus argumentos. Por ejemplo, el operador lim se aplica a una secuencia, es decir, a una función que asigna valores de enteros positivos a números reales. Como otro ejemplo, una función en C para implementar el segundo ejemplo de la tabla, Σ, tendría como argumento un puntero a función (véase el recuadro inferior).

Los términos lambda se pueden usar para denotar funciones anónimas que se proporcionarán como argumentos a lim , Σ, ∫, etc.

Por ejemplo, la función square del programa C que se muestra a continuación se puede escribir de forma anónima como un término lambda λ i . i ² . El operador de suma general Σ se puede considerar entonces como un símbolo de función ternaria que toma un valor límite inferior, un valor límite superior y una función a sumar. Debido a su último argumento, el operador Σ se denomina símbolo de función de segundo orden . Como otro ejemplo, el término lambda λ n . x / n denota una función que asigna 1, 2, 3, ... a x /1, x /2, x /3, ..., respectivamente, es decir, denota la secuencia ( x /1, x /2, x /3, ...). El operador lim toma dicha secuencia y devuelve su límite (si está definido).

La columna situada más a la derecha de la tabla indica cómo se puede representar cada ejemplo de notación matemática mediante un término lambda, convirtiendo también los operadores infijos comunes a su forma prefija .

// Implementa el operador de suma general int sum ( int lwb , int upb , int fct ( int )) { int res = 0 ; for ( int i = lwb ; i <= upb ; ++ i ) res += fct ( i ); return res ; }// implementa la función anónima (lambda i. i*i); sin embargo, C requiere un nombre para ella int square ( int i ) { return i * i ; }#include <stdio.h> int main ( void ) { int n ; scanf ( " %d" , & n ); printf ( "%d \n " , sum ( 1 , n , square )); // aplica el operador suma para sumar los cuadrados return 0 ; }

Definición

Dado un conjunto V de símbolos de variables, el conjunto de términos lambda se define recursivamente de la siguiente manera:

Cada símbolo de variable x ∈ V es un término lambda;
si x ∈ V es un símbolo de variable y t es un término lambda, entonces λ x . t también es un término lambda (abstracción);
Si t ₁ y t ₂ son términos lambda, entonces ( t ₁t ₂ ) también es un término lambda (aplicación).

Los ejemplos motivadores anteriores también utilizaron algunas constantes como div , power , etc., que, sin embargo, no están admitidas en el cálculo lambda puro.

Intuitivamente, la abstracción λ x . t denota una función unaria que devuelve t cuando se le da x , mientras que la aplicación ( t ₁t ₂ ) denota el resultado de llamar a la función t ₁ con la entrada t ₂ . Por ejemplo, la abstracción λ x . x denota la función identidad, mientras que λ x . y denota la función constante que siempre devuelve y . El término lambda λ x .( x x ) toma una función x y devuelve el resultado de aplicar x a sí misma.

Véase también

Notas

↑ Dado que las fórmulas atómicas también pueden considerarse árboles, y el cambio de nombre es esencialmente un concepto basado en árboles, las fórmulas atómicas (y, en general, las fórmulas sin cuantificadores ) pueden renombrarse de forma similar a los términos. De hecho, algunos autores consideran una fórmula sin cuantificadores como un término (de tipo booleano en lugar de, por ejemplo , entero ; véase #Términos ordenados más adelante).
↑ El cambio de nombre del axioma de conmutatividad puede verse como una alfa-conversión en el cierre universal del axioma: " x + y = y + x " en realidad significa "∀ x , y : x + y = y + x ", que es sinónimo de $\forall a, b : a + b = b + a$ ; ver también los términos #Lambda más abajo.
↑ Es decir, "tipo de símbolo" en la sección Firmas de múltiples tipos del artículo Firma (lógica).

Referencias

Franz Baader ; Tobias Nipkow (1999). Term Rewriting and All That . Cambridge University Press. págs. 1-2 y 34-35. ISBN 978-0-521-77920-3.

↑ CC Chang ; H. Jerome Keisler (1977). Teoría de modelos . Estudios en lógica y fundamentos de las matemáticas. Vol. 73. North Holland. ; aquí: Sec.1.3
↑ Hermes, Hans (1973). Introducción a la lógica matemática . Springer London. ISBN 3540058192ISSN 1431-4657 ; aquí: Sect.II.1.3

[3] Dado que las fórmulas atómicas también pueden considerarse árboles, y el cambio de nombre es esencialmente un concepto basado en árboles, las fórmulas atómicas (y, en general, las fórmulas sin cuantificadores ) pueden renombrarse de forma similar a los términos. De hecho, algunos autores consideran una fórmula sin cuantificadores como un término (de tipo booleano en lugar de, por ejemplo , entero ; véase #Términos ordenados más adelante).

[4] El cambio de nombre del axioma de conmutatividad puede verse como una alfa-conversión en el cierre universal del axioma: " x + y = y + x " en realidad significa "∀ x , y : x + y = y + x ", que es sinónimo de $\forall a, b : a + b = b + a$ ; ver también los términos #Lambda más abajo.

[5] Es decir, "tipo de símbolo" en la sección Firmas de múltiples tipos del artículo Firma (lógica).

[1] CC Chang ; H. Jerome Keisler (1977). Teoría de modelos . Estudios en lógica y fundamentos de las matemáticas. Vol. 73. North Holland. ; aquí: Sec.1.3

[2] Hermes, Hans (1973). Introducción a la lógica matemática . Springer London. ISBN 3540058192ISSN 1431-4657 ; aquí: Sect.II.1.3

[ 1 ]

[ 2 ]

[ nota 1 ]

[ nota 2 ]

[ nota 3 ]