Una asignación de variables a términos que, aplicada a un término o fórmula, reemplaza cada variable de su dominio uniformemente por el término correspondiente y se extiende homomórficamente a términos compuestos.

Principio

Una sustitución sigma = { x1 -> t1, ..., xn -> tn } se extiende a términos reemplazando variables y aplicando sigma recursivamente a los argumentos de las funciones; la composición y restricción de sustituciones obedecen leyes algebraicas e interactúan críticamente con el enlace de variables y la captura.

Demostración

Con sigma = { x -> f(a), y -> b }, aplicar sigma a g(x,y,z) da g(f(a), b, z). En unificación se busca una sustitución que haga idénticos dos términos, p. ej. unificar f(x,a) y f(b,y) produce { x->b, y->a }.

Aplicación incorrecta

Aplicar una sustitución en presencia de enlazadores (por ejemplo, abstracciones lambda) sin renombrar variables ligadas conduce a captura de variables; suponer que la composición de sustituciones es conmutativa o que las sustituciones son invertibles sin condiciones es incorrecto.

Consecuencia

Las sustituciones instancian términos esquemáticos en términos concretos, permiten unificación y matching, impulsan la aplicación de reglas en reescritura y son fundamentales en los pasos de inferencia en lógica y razonamiento automático.

Inversión

Considerar la anti-sustitución o abstracción de patrón que extrae una sustitución que produce un término concreto a partir de un patrón; la anti-sustitución suele ser parcial o no única, invertir una sustitución es no trivial frente a su aplicación directa.

Límite

Definida para variables libres de términos y fórmulas de primer orden; la semántica de sustitución debe adaptarse o restringirse cuando hay enlazadores, variables de orden superior o meta-variables, y hay que evitar la captura.

Tensión semántica

Tensión entre la sustitución sintáctica (reemplazo textual en términos) y la asignación semántica (mapear variables a valores en un modelo); la sustitución sintáctica cambia la estructura del término, la asignación semántica se relaciona con valoración y verdad.

Síntesis

Una sustitución es un mapa algebraico de variables a términos extendido homomórficamente a expresiones compuestas; es el mecanismo que instancia variables, sustenta la unificación y la reescritura y requiere disciplina para evitar captura en presencia de enlazadores.