En lógica matemática , un término denota un objeto matemático mientras que una fórmula denota un hecho matemático. En particular, los términos aparecen como componentes de una fórmula. Esto es análogo al lenguaje natural, donde una frase 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, variables y símbolos de funciones . Una expresión formada aplicando 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ógica bivalente , dada una interpretación . Por ejemplo, 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 que se evalúa como verdadera para cada valor real de x .
Además de en lógica , los términos desempeñan papeles importantes en álgebra universal y sistemas de reescritura .
Dado un conjunto V de símbolos variables, un conjunto C de símbolos constantes y conjuntos F n de símbolos de funciones n -arias, también llamados símbolos de operador, para cada número natural n ≥ 1, el conjunto de términos (sin clasificar de primer orden) T es definido recursivamente como el conjunto más pequeño con las siguientes propiedades: [1]
Usando una notación pseudogramatical intuitiva , esto a veces se escribe como:
La firma del término lenguaje describe qué conjuntos de símbolos de función F n están habitados. Ejemplos bien conocidos son los símbolos de función unaria sin , cos ∈ F 1 y los símbolos de función binaria +, −, ⋅, / ∈ F 2 . Las operaciones ternarias y las funciones de mayor aridad 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 0 , por lo que no necesitan una clase sintáctica especial para ellos.
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 abarca los objetos en ese dominio y una función n -aria f asigna n - tuplas de objetos a objetos. Por ejemplo, si n ∈ V es un símbolo variable, 1 ∈ C es un símbolo constante y sumar ∈ F 2 es un símbolo de función binaria, entonces n ∈ T , 1 ∈ T , y (por lo tanto) sumar ( n , 1) ∈ T por la regla de construcción del primer, segundo y tercer término, respectivamente. El último término generalmente se escribe como n +1, usando notación infija y el símbolo del operador más común + por conveniencia.
Originalmente, los lógicos definieron un término como una cadena de caracteres que seguía ciertas reglas de construcción. [2] Sin embargo, desde que el concepto de árbol se hizo popular en la informática, resultó más conveniente pensar en un término como árbol. Por ejemplo, varias cadenas de caracteres distintas, como " ( n ⋅( n +1))/2 ", " (( n ⋅( n +1)))/2 " y " ", denotan el mismo término y corresponden a el mismo árbol, a saber. el árbol de la izquierda en la imagen de arriba. 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 sólo representación, no estructura) y los operadores de multiplicación invisibles (que existen sólo en la estructura, no en la representación).
Se dice que dos términos son estructural , literal o sintácticamente iguales si corresponden al mismo árbol. Por ejemplo, los árboles izquierdo y derecho en la imagen de arriba son términos estructuralmente desiguales , aunque podrían considerarse " semánticamente iguales ", ya que siempre dan el mismo valor en aritmética racional . Mientras que la igualdad estructural puede comprobarse sin ningún conocimiento del significado de los símbolos, la igualdad semántica no. Si la función / se interpreta, por ejemplo, no como racional sino como una división entera truncada , entonces en n =2 los términos izquierdo y derecho se evalúan como 3 y 2, respectivamente. Los términos estructurales iguales deben coincidir en los nombres de sus variables.
Por el contrario, un término t se denomina cambio de nombre , o variante , de un término u si este último resultó de cambiar consistentemente el nombre de todas las variables del primero, es decir, si u = tσ para alguna sustitución de cambio de nombre σ. En ese caso, u también es un cambio de nombre de t , ya que una sustitución de cambio de nombre σ tiene una inversa σ −1 , y t = uσ −1 . Entonces también se dice que ambos términos tienen un cambio de nombre de módulo igual . En muchos contextos, los nombres de las variables particulares en un término no importan, por ejemplo, el axioma de conmutatividad para la suma se puede expresar como x + y = y + x o como a + b = b + a ; en tales casos se puede cambiar el nombre de toda la fórmula, mientras que un subtérmino arbitrario normalmente no; por ejemplo, x + y = b + a no es una versión válida del axioma de conmutatividad. [nota 1] [nota 2]
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 fundamental ; un término que no contiene múltiples apariciones de una variable se llama término lineal . Por ejemplo, 2+2 es un término fundamental y, por 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 firma para los símbolos de función, el conjunto de todos los términos forma el término álgebra libre . El conjunto de todos los términos fundamentales forma el término inicial álgebra .
Abreviando el número de constantes como f 0 y el número de símbolos de funciones i -arias como f i , el número θ h de términos fundamentales distintos de una altura hasta h se puede calcular mediante la siguiente fórmula de recursividad:
Dado un conjunto R n de n -símbolos de relación aria para cada número natural n ≥ 1, se obtiene una fórmula atómica (sin clasificar de primer orden) 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 generalmente no está vacío solo para n pequeño . En lógica matemática, las fórmulas más complejas se construyen a partir de fórmulas atómicas utilizando conectivos lógicos y cuantificadores . Por ejemplo, dejar denotar el conjunto de números reales , ∀ x : x ∈ ⇒ ( x +1)⋅( x +1) ≥ 0 es una fórmula matemática que se evalúa como verdadera en el álgebra de números complejos . Una fórmula atómica se llama fundamental si está construida enteramente a partir de términos fundamentales; todas las fórmulas atómicas fundamentales que se pueden componer a partir de un conjunto dado de símbolos de función y predicado constituyen la base de Herbrand para estos conjuntos de símbolos.
Cuando el dominio del discurso contiene elementos de tipos básicamente diferentes, resulta útil dividir el conjunto de todos los términos en consecuencia. Con este fin, 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 clasificación de dominio y clasificación de rango a cada símbolo de función. Un término ordenado f ( t 1 ,..., t n ) puede estar compuesto a partir de subtérminos ordenados t 1 ,..., t n solo si el género del i -ésimo subtérmino coincide con el género del i- ésimo dominio declarado de f . Este término también se denomina bien ordenado ; cualquier otro término (es decir, que obedezca únicamente las reglas no ordenadas) se denomina mal ordenado .
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, y 0 ∈ C N , y la suma vectorial, la multiplicación escalar y el producto interno se declaran como , y , respectivamente. Suponiendo símbolos variables y a , b ∈ V N , el término está bien ordenado, mientras que no lo está (ya que + no acepta un término de tipo N como segundo argumento). Para hacer un término bien ordenado, se requiere una declaración adicional. Los símbolos de función que tienen varias declaraciones se denominan sobrecargados .
Consulte la lógica multiclasificada para obtener más información, incluidas las extensiones del marco multiclasificado que se describe aquí.
Las notaciones matemáticas como se muestran en la tabla no encajan en el esquema de un término de primer orden como se define anteriormente, ya que todas ellas introducen una variable local propia , o ligada , que puede no aparecer fuera del alcance de la notación, por ejemplo, no tiene sentido. . Por el contrario, las otras variables, denominadas libres , se comportan como variables ordinarias de términos de primer orden, por ejemplo, tienen sentido.
Se puede considerar que todos estos operadores toman una función en lugar de un término de valor como uno de sus argumentos. Por ejemplo, el operador lim se aplica a una secuencia, es decir, a una aplicación de un entero positivo a, por ejemplo, números reales. Como otro ejemplo, una función C para implementar el segundo ejemplo de la tabla, Σ, tendría un argumento de puntero de función (consulte el cuadro a continuación).
Los términos lambda se pueden utilizar para indicar funciones anónimas que se proporcionarán como argumentos para lim , Σ, ∫, etc.
Por ejemplo, la función cuadrado del siguiente programa en C se puede escribir de forma anónima como un término lambda λ i . yo 2 . El operador de suma general Σ puede considerarse 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 resumir. 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 más a la derecha de la tabla indica cómo cada ejemplo de notación matemática se puede representar mediante un término lambda, y también convierte los operadores infijos comunes en forma de prefijo .
int suma ( int lwb , int upb , int fct ( int )) { // implementa el operador de suma general int res = 0 ; para ( int i = lwb ; i <= upb ; ++ i ) res += fct ( i ); devolver resolución ; } int cuadrado ( int i ) { return i * i ; } // implementa la función anónima (lambda i. i*i); sin embargo, C requiere un nombre para ello #include <stdio.h> int main ( void ) { int n ; scanf ( "%d" , & n ); printf ( "%d \n " , suma ( 1 , n , cuadrado )); // aplica el operador de suma para sumar cuadrados return 0 ; } Dado un conjunto V de símbolos variables, el conjunto de términos lambda se define recursivamente de la siguiente manera:
Los motivadores ejemplos anteriores también utilizaron algunas constantes como div , power , etc. que, sin embargo, no se admiten 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 1 t 2 ) denota el resultado de llamar a la función t 1 con la entrada t 2 . 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í mismo.