Una sustitución es una transformación sintáctica de expresiones formales . Aplicar una sustitución a una expresión significa reemplazar de manera consistente sus símbolos variables o de marcador de posición por otros símbolos de expresión.
La expresión resultante se denomina instancia de sustitución , o instancia para abreviar, de la expresión original.
Donde ψ y φ representan fórmulas de lógica proposicional , ψ es una instancia de sustitución de φ si y solo si ψ puede obtenerse a partir de φ sustituyendo fórmulas por variables proposicionales en φ , reemplazando cada ocurrencia de la misma variable por una ocurrencia de la misma fórmula. Por ejemplo:
es una instancia de sustitución de:
y
es una instancia de sustitución de:
En algunos sistemas de deducción para lógica proposicional, una nueva expresión (una proposición ) puede introducirse en una línea de una derivación si es una instancia de sustitución de una línea anterior de la derivación (Hunter 1971, p. 118). Así es como se introducen nuevas líneas en algunos sistemas axiomáticos . En sistemas que utilizan reglas de transformación , una regla puede incluir el uso de una instancia de sustitución con el fin de introducir ciertas variables en una derivación.
Una fórmula proposicional es una tautología si es verdadera bajo cualquier valoración (o interpretación ) de sus símbolos predicativos. Si Φ es una tautología y Θ es una instancia de sustitución de Φ, entonces Θ es nuevamente una tautología. Este hecho implica la solidez de la regla de deducción descrita en la sección anterior.
En lógica de primer orden , una sustitución es una aplicación total σ : V → T de variables a términos ; muchos, [1] : 73 [2] : 445 pero no todos [3] : 250 autores requieren adicionalmente σ ( x ) = x para todas las variables x excepto un número finito . La notación { x 1 ↦ t 1 , …, x k ↦ t k } [nota 1] se refiere a una aplicación de sustitución de cada variable x i al término correspondiente t i , para i = 1, …, k , y cada otra variable a sí misma; los x i deben ser distintos por pares. La mayoría de los autores requieren adicionalmente que cada término t i sea sintácticamente diferente de x i , para evitar infinitas notaciones distintas para la misma sustitución. La aplicación de esa sustitución a un término t se escribe en notación sufija como t { x 1 ↦ t 1 , ..., x k ↦ t k }; significa reemplazar (simultáneamente) cada ocurrencia de cada x i en t por t i . [nota 2] El resultado tσ de aplicar una sustitución σ a un término t se llama una instancia de ese término t . Por ejemplo, aplicar la sustitución { x ↦ z , z ↦ h ( a , y ) } al término
El dominio dom ( σ ) de una sustitución σ se define comúnmente como el conjunto de variables realmente reemplazadas, es decir, dom ( σ ) = { x ∈ V | xσ ≠ x }. Una sustitución se llama sustitución fundamental si asigna todas las variables de su dominio a términos fundamentales , es decir, libres de variables. La instancia de sustitución tσ de una sustitución fundamental es un término fundamental si todas las variables de t están en el dominio de σ , es decir, si vars ( t ) ⊆ dom ( σ ). Una sustitución σ se llama sustitución lineal si tσ es un término lineal para algún (y por lo tanto cada) término lineal t que contiene precisamente las variables del dominio de σ , es decir, con vars ( t ) = dom ( σ ). Una sustitución σ se llama sustitución plana si xσ es una variable para cada variable x . Una sustitución σ se denomina sustitución de cambio de nombre si es una permutación en el conjunto de todas las variables. Como toda permutación, una sustitución de cambio de nombre σ siempre tiene una sustitución inversa σ −1 , tal que tσσ −1 = t = tσ −1 σ para cada término t . Sin embargo, no es posible definir una inversa para una sustitución arbitraria.
Por ejemplo, { x ↦ 2, y ↦ 3+4 } es una sustitución fundamental, { x ↦ x 1 , y ↦ y 2 +4 } no es fundamental ni plana, pero es lineal, { x ↦ y 2 , y ↦ y 2 +4 } no es lineal ni plana, { x ↦ y 2 , y ↦ y 2 } es plana, pero no lineal, { x ↦ x 1 , y ↦ y 2 } es lineal y plana, pero no un cambio de nombre, ya que asigna tanto y como y 2 a y 2 ; cada una de estas sustituciones tiene el conjunto { x , y } como su dominio. Un ejemplo de una sustitución de cambio de nombre es { x ↦ x 1 , x 1 ↦ y , y ↦ y 2 , y 2 ↦ x }, tiene la inversa { x ↦ y 2 , y 2 ↦ y , y ↦ x 1 , x 1 ↦ x }. La sustitución plana { x ↦ z , y ↦ z } no puede tener una inversa, ya que, por ejemplo, ( x + y ) { x ↦ z , y ↦ z } = z + z , y el último término no se puede transformar de nuevo en x + y , ya que se pierde la información sobre el origen del que proviene z . La sustitución fundamental { x ↦ 2 } no puede tener una inversa debido a una pérdida similar de información de origen, por ejemplo en ( x + 2) { x ↦ 2 } = 2+2, incluso si la sustitución de constantes por variables estuviera permitida por algún tipo ficticio de "sustituciones generalizadas".
Dos sustituciones se consideran iguales si asignan cada variable a términos de resultado sintácticamente iguales , formalmente: σ = τ si xσ = xτ para cada variable x ∈ V . La composición de dos sustituciones σ = { x 1 ↦ t 1 , …, x k ↦ t k } y τ = { y 1 ↦ u 1 , …, y l ↦ u l } se obtiene eliminando de la sustitución { x 1 ↦ t 1 τ , …, x k ↦ t k τ , y 1 ↦ u 1 , …, y l ↦ u l } aquellos pares y i ↦ u i para los cuales y i ∈ { x 1 , …, x k }. La composición de σ y τ se denota por στ . La composición es una operación asociativa y es compatible con la aplicación de la sustitución, es decir, ( ρσ ) τ = ρ ( στ ), y ( tσ ) τ = t ( στ ), respectivamente, para cada sustitución ρ , σ , τ , y cada término t . La sustitución identidad , que asigna cada variable a sí misma, es el elemento neutro de la composición de sustitución. Una sustitución σ se llama idempotente si σσ = σ , y por lo tanto tσσ = tσ para cada término t . Cuando x i ≠ t i para todo i , la sustitución { x 1 ↦ t 1 , …, x k ↦ t k } es idempotente si y solo si ninguna de las variablesx i ocurre en cualquier t j . La composición de sustitución no es conmutativa, es decir, στ puede ser diferente de τσ , incluso si σ y τ son idempotentes. [1] : 73–74 [2] : 445–446
Por ejemplo, { x ↦ 2, y ↦ 3+4 } es igual a { y ↦ 3+4, x ↦ 2 }, pero diferente de { x ↦ 2, y ↦ 7 }. La sustitución { x ↦ y + y } es idempotente, p. ej. (( x + y ) { x ↦ y + y }) { x ↦ y + y } = (( y + y )+ y ) { x ↦ y + y } = ( y + y )+ y , mientras que la sustitución { x ↦ x + y } no es idempotente, p. ej. (( x + y ) { x ↦ x + y }) { x ↦ x + y } = (( x + y )+ y ) { x ↦ x + y } = (( x + y )+ y )+ y . Un ejemplo de sustituciones sin conmutación es { x ↦ y } { y ↦ z } = { x ↦ z , y ↦ z }, pero { y ↦ z } { x ↦ y } = { x ↦ y , y ↦ z }.
En matemáticas , hay dos usos comunes de la sustitución: la sustitución de variables por constantes (también llamada asignación para esa variable) y la propiedad de sustitución de la igualdad , [4] también llamada Ley de Leibniz . [5]
Considerando las matemáticas como un lenguaje formal , una variable es un símbolo de un alfabeto , usualmente una letra como x , y y z , que denota un rango de valores posibles . [6] Si una variable es libre en una expresión o fórmula dada , entonces puede ser reemplazada con cualquiera de los valores en su rango. [7] Ciertos tipos de variables ligadas también pueden ser sustituidas. Por ejemplo, los parámetros de una expresión (como los coeficientes de un polinomio ), o el argumento de una función . Además, las variables que se cuantifican universalmente pueden ser reemplazadas con cualquiera de los valores en su rango, y el resultado será una declaración verdadera . (Esto se llama instanciación universal )
En un lenguaje no formalizado, es decir, en la mayoría de los textos matemáticos fuera de la lógica matemática , para una expresión individual no siempre es posible identificar qué variables son libres y cuáles están ligadas. Por ejemplo, en , dependiendo del contexto, la variable puede ser libre y ligada, o viceversa, pero no pueden ser ambas libres. Determinar qué valor se supone que es libre depende del contexto y de la semántica .
La propiedad de sustitución de la igualdad , o Ley de Leibniz (aunque este último término suele reservarse para contextos filosóficos ), generalmente establece que, si dos cosas son iguales, entonces cualquier propiedad de una, debe ser una propiedad de la otra. Puede enunciarse formalmente en notación lógica como: Para cada y , y cualquier fórmula bien formada (con una variable libre x). Por ejemplo: Para todos los números reales a y b , si a = b , entonces a ≥ 0 implica b ≥ 0 (aquí, es x ≥ 0 ). Esta es una propiedad que se utiliza con mayor frecuencia en álgebra , especialmente en la resolución de sistemas de ecuaciones , pero se aplica en casi todas las áreas de las matemáticas que utilizan la igualdad. Esto, tomado junto con la propiedad reflexiva de la igualdad, forma los axiomas de igualdad en la lógica de primer orden. [8]
La sustitución está relacionada con la composición de funciones , pero no es idéntica a ella ; está estrechamente relacionada con la β -reducción en el cálculo lambda . Sin embargo, en contraste con estas nociones, el énfasis en el álgebra está en la preservación de la estructura algebraica mediante la operación de sustitución, el hecho de que la sustitución da un homomorfismo para la estructura en cuestión (en el caso de los polinomios, la estructura de anillo ). [ cita requerida ]
La sustitución es una operación básica en álgebra , en particular en álgebra computacional . [9] [10]
Un caso común de sustitución involucra polinomios , donde la sustitución de un valor numérico (u otra expresión) por el indeterminado de un polinomio univariado equivale a evaluar el polinomio en ese valor. De hecho, esta operación ocurre tan frecuentemente que la notación para polinomios a menudo se adapta a ella; en lugar de designar un polinomio con un nombre como P , como se haría para otros objetos matemáticos, se podría definir
de modo que la sustitución de X se puede designar por reemplazo dentro de " P ( X )", digamos
o
La sustitución también se puede aplicar a otros tipos de objetos formales construidos a partir de símbolos, por ejemplo, elementos de grupos libres . Para que se defina la sustitución, se necesita una estructura algebraica con una propiedad universal apropiada , que afirme la existencia de homomorfismos únicos que envían indeterminados a valores específicos; la sustitución entonces equivale a encontrar la imagen de un elemento bajo tal homomorfismo.
sustitución.
![{\displaystyle (a=b)\implies {\bigl [}\phi (a)\Rightarrow \phi (b){\bigr ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbb9f60581cca4f18a32d9de8da10a1201836afc)
