Sustitución (lógica)

Una sustitución es una transformación sintáctica de expresiones formales. Aplicar una sustitución a una expresión significa reemplazar consistentemente sus símbolos variables o de marcador de posición con otras expresiones.

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:

(R → S) " (T → S)

es una instancia de sustitución de:

P ' Q

y

(A ↔ A)

es una instancia de sustitución de:

(A ↔ A)

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 autores, pero no todos, requieren además σ(x) = x para todas las variables x, excepto un número finito. La notación { x₁ ↦ t₁, …, x_k ↦ t_k } se refiere a una sustitución que asigna cada variable x_i al término correspondiente t_i, para i=1,…,k, y cada otra variable a sí misma; las x_i deben ser distintas por pares. La aplicación de esa sustitución a un término t se escribe en notación sufija como t { x₁ ↦ t₁,..., x_k ↦ t_k }; significa reemplazar (simultáneamente) cada ocurrencia de cada x_i en t por t_i. El resultado tσ de aplicar una sustitución σ a un término t se llama instancia de ese término t. Por ejemplo, aplicando la sustitución { x ↦ z, z ↦ h(a,y) } al término

f()	z	, a, g()	x	), Sí.)	rendimientos
f()	h()a,Sí.)	, a, g()	z	), Sí.)	.

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 denomina 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 denomina sustitución lineal si tσ es un término lineal para algún término lineal (y por lo tanto para cada uno) t que contenga precisamente las variables del dominio de σ, es decir, con vars(t) = dom(σ). Una sustitución σ se denomina 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 σ⁻¹, tal que tσσ⁻¹ = t = tσ⁻¹σ 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₁, y ↦ y₂+4 } no es fundamental ni plana, sino lineal, { x ↦ y₂, y ↦ y₂+4 } no es lineal ni plana, { x ↦ y₂, y ↦ y₂ } es plana, pero no lineal, { x ↦ x₁, y ↦ y₂ } es a la vez lineal y plana, pero no un cambio de nombre, ya que asigna tanto y como y₂ a y₂; 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₁, x₁ ↦ y, y ↦ y₂, y₂ ↦ x }, tiene la inversa { x ↦ y₂, y₂ ↦ y, y ↦ x₁, x₁ ↦ 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 a 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 se permitiera reemplazar constantes por variables mediante 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₁ ↦ t₁, …, x_k ↦ t_k } y τ = { y₁ ↦ u₁, …, y_l ↦ u_l } se obtiene quitando de la sustitución { x₁ ↦ t₁τ, …, x_k ↦ t_kτ, y₁ ↦ u₁, …, y_l ↦ u_l } aquellos pares y_i ↦ u_i para los cuales y_i ∈ { x₁, …, 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 de identidad, que asigna cada variable a sí misma, es el elemento neutro de la composición de la 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₁ ↦ t₁, …, x_k ↦ t_k } es idempotente si y solo si ninguna de las variables x_i ocurre en ningún t_j. La composición de la sustitución no es conmutativa, es decir, στ puede ser diferente de τσ, incluso si σ y τ son idempotentes.

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 no conmutativas 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, también llamada Ley de Leibniz.

Si consideramos las matemáticas como un lenguaje formal, una variable es un símbolo de un alfabeto, normalmente una letra como x, y y z, que denota un rango de valores posibles. Si una variable es libre en una expresión o fórmula dada, entonces puede ser reemplazada por cualquiera de los valores en su rango. También se pueden sustituir ciertos tipos de variables ligadas. 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 se pueden reemplazar por cualquiera de los valores en su rango, y el resultado será una declaración verdadera. (Esto se llama instanciación universal)

Para 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 ligadas. Por ejemplo, en ${\textstyle \sum ¿Qué?$, dependiendo del contexto, la variable ${\textstyle i}$ puede ser libre y ${\textstyle k}$ atado, o viceversa, pero ambos no pueden ser libres. Determinar qué valor se supone libre depende del contexto y la semántica.

El propiedad de la igualdado Ley de Leibniz (aunque este último término se reserva generalmente para contextos filosóficos), generalmente declara que, si dos cosas son iguales, entonces cualquier propiedad de uno, debe ser una propiedad de la otra. Puede ser declarado formalmente en la notación lógica como:$${\displaystyle (a=b)\implies {\bigl [}\phi (a)\ Rightarrow \phi (b){\bigr]}$$Por todos ${\textstyle a}$ y ${\textstyle b}$, y cualquier fórmula bien formada ${\textstyle \phi (x)}$ (con una variable x gratuita). Por ejemplo: Para todos los números reales a y b, si a = bEntonces a ≥ 0 implicación b ≥ 0 (aquí, ${\displaystyle \phi (x)}$ es x ≥ 0). Esta es una propiedad que se utiliza más a menudo en el álgebra, especialmente en la solución de sistemas de ecuaciones, pero se une en casi cada área de matemáticas que utiliza la igualdad. Esto, unido a la propiedad reflexiva de la igualdad, forma los axiomas de la igualdad en la lógica de primer orden.

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).

La sustitución es una operación básica en álgebra, en particular en álgebra computacional.

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

${\displaystyle P(X)=X^{5}-3X^{2}+5X-17}$

de modo que la sustitución de X se puede designar mediante reemplazo dentro de "P(X)", digamos

${\displaystyle P(2)=13}$

o

${\displaystyle P(X+1)=X^{5}+5X^{4}+10X^{3}+7X^{2}+4X-14.}$

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íen indeterminados a valores específicos; la sustitución entonces equivale a encontrar la imagen de un elemento bajo tal homomorfismo.

• Integración por sustitución
• Lambda cálculo § Substitution
• Interpolación de cuerdas
• Bienes de sustitución de la igualdad
• Sustitución trigonométrica
• Instantiación universal

• Crabbé, M. (2004). Sobre el concepto de sustitución. Diario Lógico del IGPL, 12, 111–124.
• Curry, H. B. (1952) Sobre la definición de sustitución, sustitución y nociones aliadas en un sistema formal abstracto. Revue philosophique de Louvain 50, 251–269.
• Hunter, G. (1971). Metalogic: Introducción a la metateoría de la lógica de primera orden estándar. University of California Press. ISBN 0-520-01822-2
• Kleene, S. C. (1967). Lógica Matemática. Reimpreso 2002, Dover. ISBN 0-486-42533-9

• Sustitución en el nLab