Sustituciones

Ya hablé del álgebra de términos, pero no dije nada de cómo se usaba y para qué servía. En este artículo voy a exponer una de las operaciones sobre esta álgebra: la sustitución.

Definición

Realmente, no debería llamarse sustitución, ya que no es una sustitución de "quito esto y pongo lo otro". Esto es así porque no vamos a cambiar términos por términos sino variables por términos. O sea, una sustitución es una aplicación de las variables en los términos.

[$$ \sigma : V\to T(A,V)
$$]

Lo interesante de esta aplicación es que puede extenderse de forma congruente a todo el álgebra de términos. Para eso introducimos una nueva aplicación extendida

[$$ \bar{\sigma} : T(A,V)\to T(A,V) $$]

Y la definimos para que mantenga la estructura de los términos así:

[$$ \bar{\sigma}(x)=\sigma (x) $$]
[$$ \bar{\sigma}(f(M_1,...,M_n))=f (\bar{\sigma}(M_1),...,\bar{\sigma}(M_n)) $$]

El conjunto de todas las sutituciones en T(A,V) lo escribiremos como S(A,V). Usualmente no se distingue entre la sustitución con y sin barra. En este artículo haremos la distinción para ser formales, pero en otros lugares sólo se usa s.

Dominio y restricción

Llamamos dominio de una sustitución al conjunto de variables que no se sustituyen por ellas mismas.

[$$ dom(\sigma)=\left\{x\in V\mid \sigma(x)=x \right\},\qquad \sigma\in S(A,V) $$]

Cuando el dominio sea infinito, la sustitución se llamará infinita. Generalmente cuando se habla de sustitución, sólo se hace referencia a las sustituciones no infinitas. Nosotros sólo consideraremos las sustituciones no infinitas.

La restricción de una sustitución a un subconjunto (finito) de variables se define así.

[$$ \sigma\mid_W(x)=\left\{\begin{matrix}
\sigma(x) & \Leftarrow x\in W\\
x & \Leftarrow x\not\in W
\end{matrix}\right.\qquad W\subset V
$$]

Para indicar una sustitución lo más sencillo es componer varias sustituciones simples. Una sustitución simple es la que tiene dominio unitario. Representaremos a estas sustituciones así:

[$$ \sigma=\left[ x \mapsto M \right] $$]

Donde

[$$ \sigma(x)=M $$]

Si llamamos "id" a la sustitución identidad, entonces una sustitución arbitraria se representa así:

[$$ id\circ\left[ x_1 \mapsto M_1 \right]\circ\cdots\circ \left[ x_n \mapsto M_n \right] $$]

Donde

[$$ dom(\sigma)=\left\{ x_1,...,x_n\right\} $$]

Edit: Corrección. Una sustitución arbitraria donde todas las variables se renombren. Cuando hay variables comunes entre el dominio y el resultado de la sustitución hay que usar una sustitución simultánea.[$$ \left[ x_1 \mapsto M_1 ,\cdots\circ , x_n \mapsto M_n \right] $$]

Introduciendo la sustitución indefinida

Cuando realizamos un algoritmo muchas veces necesitamos un "valor de error", en el conjunto de sustituciones sobre el álgebra de términos con indefinido se introduce una transformación especial que llamaremos la sustitución indefinida. Su propiedad es que siempre asigna el valor indefinido.

[$$ \omega : T^\Omega(A,V) \to T^\Omega(A,V) $$]
[$$ \omega (M) = \Omega $$]

Al conjunto de sustituciones con sustitución indefinida (sobre el álgebra de términos con indefinido) lo definimos de esta forma:

[$$ S^\omega(A,V)=S(A,V)\cup \left\{ \omega \right\} $$]

Hemos de arreglar un poco las operaciones anteriores de la siguiente forma:

[$$ \bar{\sigma}(\Omega)=\Omega $$]
[$$ \omega\mid_W=\omega $$]

Ahora queda averiguar qué estructura matemática tiene la operación de sustitución sobre el álgebra de términos, pero eso lo dejaré para otro día.