Sustitución lógica

Definición

Una sustitución es un mapeo finito de variables a términos. Se escribe, por ejemplo, $\theta =\{x/a,y/f(z)\}$. Aplicar la sustitución a una expresión reemplaza simultáneamente las variables indicadas: $P(x,y)\theta =P(a,f(z))$. Las variables no incluidas quedan intactas.

En la notación de estas notas, $Subst(\theta ,E)$ significa aplicar $\theta$ a la expresión $E$. La sustitución permite instanciar fórmulas y registrar el resultado de la unificación.

Aplicación y composición

Si $\theta =\{x/f(y),y/a\}$, la aplicación simultánea a $P(x,y)$ da $P(f(y),a)$: el $y$ que aparece dentro del término insertado no se vuelve a sustituir en esa misma aplicación. Al componer sustituciones, en cambio, la segunda puede aplicarse a los términos producidos por la primera. Por ejemplo, aplicar primero ${\theta }_1=\{x/y\}$ y después ${\theta }_2=\{y/a\}$ equivale a la composición ${\theta }_1{\theta }_2=\{x/a,y/a\}$ (la convención de orden debe declararse; aquí se lee de izquierda a derecha en el tiempo).

La sustitución debe respetar el alcance de cuantificadores: al sustituir dentro de fórmulas cuantificadas se evita capturar variables libres. En los algoritmos de unificación de términos, esta precaución se simplifica usando variables y términos explícitos, mientras que al instanciar fórmulas se debe renombrar una variable ligada si colisiona con una variable libre del término insertado.

Ejemplo en inferencia

Para resolver $\neg Humano(x)\vee Mortal(x)$ con $Humano(S\acute{o}crates)$, el unificador $\theta =\{x/S\acute{o}crates\}$ se aplica a la cláusula restante completa: $Mortal(x)\theta =Mortal(S\acute{o}crates)$. Después se elimina el par de literales complementarios. Véase resolución de primer orden.

flowchart LR
  A["Cláusula: ¬Humano(x) ∨ Mortal(x)"] --> B["Aplicar θ = {x/Sócrates}"]
  C["Hecho: Humano(Sócrates)"] --> D["Unificar átomos complementarios"]
  B --> D
  D --> E["Eliminar el par complementario"]
  E --> F["Resolvente: Mortal(Sócrates)"]

Referencias

• Clase: Inferencia en lógica de primer orden, diapositiva 8.
• Russell, S. J. y Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4.ª ed.), §9.2; sitio del libro.
• Genesereth, M. R. y Nilsson, N. J. (1987). Logical Foundations of Artificial Intelligence, capítulo 3. DOI/editorial.