stringtranslate.com

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

Lógica proposicional

Definición

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) y (T → S)

es una instancia de sustitución de:

P y Q

y

(A ↔ A) ↔ (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.

Tautologías

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.

Lógica de primer orden

En lógica de primer orden , una sustitución es una aplicación total σ : VT 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; el x i debe ser distinto por pares. Aplicar esa sustitución a un término t se escribe en notación de sufijo como t { x 1  ↦  t 1 , ..., x k  ↦  t k }; significa (simultáneamente) reemplazar cada ocurrencia de cada x i en t por t i . [nota 2] El resultado de aplicar una sustitución σ a un término t se denomina 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 ( σ ) = { xV | 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 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 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 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 = −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 = para cada variable xV . 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 ( στ ), 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σσ = para cada término t . Cuando x it 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 ) { xy + y }) { xy + y } = (( y + y )+ y ) { xy + y } = ( y + y )+ y , mientras que la sustitución { x  ↦  x + y } no es idempotente, p. ej. (( x + y ) { xx + y }) { xx + y } = (( x + y )+ y ) { xx + 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 }.

Matemáticas

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 ]

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}Álgebra

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

Véase también

Notas

  1. ^ Algunos autores usan [ t 1 / x 1 , …, t k / x k ] para denotar esa sustitución, p. ej . M. Wirsing (1990). Jan van Leeuwen (ed.). Especificación algebraica . Manual de informática teórica. Vol. B. Elsevier. págs. 675–788., aquí: p. 682.
  2. ^ Desde el punto de vista del álgebra de términos , el conjunto T de términos es el álgebra de términos libre sobre el conjunto V de variables, por lo tanto, para cada aplicación de sustitución σ: VT hay un homomorfismo único σ : TT que concuerda con σ en VT ; la aplicación de σ definida anteriormente a un término t se considera entonces como la aplicación de la función σ al argumento t .

Citas

  1. ^ de David A. Duffy (1991). Principios de demostración automática de teoremas . Wiley.
  2. ^ ab Franz Baader , Wayne Snyder (2001). Alan Robinson y Andrei Voronkov (ed.). Unification Theory (PDF) . Elsevier. pp. 439–526. Archivado desde el original (PDF) el 8 de junio de 2015 . Consultado el 24 de septiembre de 2014 .
  3. ^ N. Dershowitz; J.-P. Jouannaud (1990). "Rewrite Systems". En Jan van Leeuwen (ed.). Modelos formales y semántica . Manual de informática teórica. Vol. B. Elsevier. págs. 243–320.
  4. ^ Sobolev, SK (creador). " Axiomas de igualdad" . Enciclopedia de Matemáticas . Springer . ISBN 1402006098.
  5. ^ Deutsch, Harry y Pawel Garbacz, "Identidad relativa", The Stanford Encyclopedia of Philosophy (edición de otoño de 2024), Edward N. Zalta y Uri Nodelman (eds.), próximamente URL: https://plato.stanford.edu/entries/identity-relative/#StanAccoIden
  6. ^ Sobolev, SK (autor). "Variable individual". Enciclopedia de Matemáticas . Springer . ISBN 1402006098. Recuperado el 5 de septiembre de 2024 .
  7. ^ Sobolev, SK (creador). Variable libre. Enciclopedia de Matemáticas . Springer . ISBN 1402006098.
  8. ^ Fitting, M. , Lógica de primer orden y demostración automática de teoremas (Berlín/Heidelberg: Springer, 1990), págs. 198-200.
  9. ^ Margret H. Hoft; Hartmut FW Hoft (6 de noviembre de 2002). Computación con Mathematica. Elsevier. ISBN 978-0-08-048855-4.
  10. ^ Andre Heck (6 de diciembre de 2012). Introducción a Maple . Springer Science & Business Media. ISBN 978-1-4684-0484-5. sustitución.

Referencias

Enlaces externos