Lógica Computacional
Nota 08. Semántica de la lógica de predicados.¹¹El material aquí presentado se basa el libro de Huth y Ryan, Logic in Computer Science; en las notas del prof. Francisco Hernández Q.; y en las notas del prof. Favio Miranda.

Noé Salomón Hernández S

1 Semántica de la lógica de predicados

La semántica de la lógica de predicados es más complicada que la de la lógica proposicional ya que contamos con términos y fórmulas. La verdad de una fórmula de la lógica de predicados depende de los valores de los términos, los cuales a su vez dependen del universo de discurso. En lógica de predicados tendremos un número infinito de evaluaciones, llamadas modelos, a considerar.

En la nota pasada estudiamos al sistema de deducción natural para la lógica de predicados, la semántica provee una caracterización de la lógica diferente pero equivalente. Al decir que son equivalentes queremos decir que podemos demostrar para el sistema de deducción natural los teoremas de correctud y completud.

En el sistema de deducción natural, el objeto básico es una demostración. La deducción natural da una caracterización positiva de la lógica, pero no es útil para obtener evidencia sobre afirmaciones de la forma ‘ $\Gamma\vdash\psi$ no es válida’. La semántica, por otro lado, opera en la dirección opuesta. Demostrar que $\psi$ no es una consecuencia de $\Gamma$ es sencillo. Es decir, la semántica ofrece una caracterización negativa de la lógica, así obtener evidencia sobre afirmaciones de la forma ‘ $\Gamma\not\models\psi$ ’ es más sencillo que llegar a $\Gamma\models\psi$ .

Es importante que estudiemos tanto el sistema de deducción natural como la semántica.

1.1 Modelos

Tenemos que reflexionar sobre el significado de $\forall x$ y $\exists x$ , sus dependencias y los valores concretos de los argumentos en los predicados $P(t_{1},t_{2},\ldots,t_{n})$ . El problema es que las variables son posiciones para cualquier, o algún, valor no especificado. Tales valores pueden ser de cualquier clase.

Si nos encontramos con una fórmula $\exists y\,\psi$ , tratamos de encontrar alguna instancia de $y$ tal que $\psi$ se cumpla. Si tenemos éxito, $\exists y\,\psi$ se evalúa a $\top$ ; de otro modo, regresa $\bot$ . Evaluar $\forall x\,\psi$ consiste en demostrar que $\psi$ se evalúa a $\top$ para todo valor posible de $x$ ; si tenemos éxito, $\forall x\,\psi$ se evalúa a $\top$ ; de otro modo, regresa $\bot$ . Tales evaluaciones requieren de un universo fijo de valores concretos. El valor de verdad de una fórmula en lógica de predicados depende de la elección específica de valores y el significado de los símbolos de predicados y de función involucrados, esto constituye un modelo.

Definición 1.1.

Sea $\mathcal{F}$ un conjunto de símbolos de funciones y $\mathcal{P}$ un conjunto de símbolos de predicado. Un modelo $\mathcal{M}$ del par $(\mathcal{F},\mathcal{P})$ consiste de:

1.

Un conjunto no vacío $A$ , el universo de valores concretos.
2.

Para cada símbolo de función nula, i.e., símbolo de constante, $c\in\mathcal{F}$ , un elemento concreto $c^{\,\mathcal{M}}$ de $A$ .
3.

Para cada símbolo $f\in\mathcal{F}$ con aridad $n>0$ , una función concreta $f^{\mathcal{M}}:A^{n}\rightarrow A$ .
4.

Para cada $P\in\mathcal{P}$ con aridad $n>0$ , un subconjunto $P^{\mathcal{M}}\subseteq A^{n}$ de tuplas de $n$ elementos sobre $A$ .

Los símbolos $c$ , $f$ y $P$ son sólo símbolos, mientras que $c^{\,\mathcal{M}}$ , $f^{\mathcal{M}}$ y $P^{\mathcal{M}}$ denotan un elemento constante, una función concreta y una relación específica en un modelo $\mathcal{M}$ , respectivamente.

Es crucial darse cuenta de que la noción de modelo es extremadamente flexible y abierta. Todo lo que se necesita es elegir un conjunto no vacío $A$ , cuyos elementos modelan objetos concretos o reales, y un conjunto de funciones y relaciones, una para cada símbolo de función y predicado, respectivamente. Si acaso se restringe a que las funciones y relaciones concretas sobre $A$ tengan el mismo número de argumentos que sus correspondientes símbolos sintácticos.

Como diseñadores de modelos, tenemos la responsabilidad de escoger nuestros modelos sabiamente, ya que deben representar de manera precisa lo que deseamos modelar, pero deben ignorar aspectos del mundo que son irrelevantes.

Interpretamos fórmulas con relación a un ambiente. Intuitivamente, un ambiente es una tabla de búsqueda para todas las variables; una tabla de búsqueda $l$ asocia a cada variable $x$ una valor $l(x)$ del modelo.

Definición 1.2.

Un ambiente para un universo $A$ es una función $l:\mathsf{var}\rightarrow A$ del conjunto $\mathsf{var}$ de variables en $A$ . Denotamos por $l[x\mapsto a]$ el ambiente en el que a $x$ le corresponde $a$ , y a cualquier otra variable $y$ le corresponde $l(y)$ .

Definición 1.3.

Dado un modelo $\mathcal{M}$ para un par $(\mathcal{F},\mathcal{P})$ y un ambiente $l$ , definimos la relación de satisfacción $\mathcal{M}\models_{l}\varphi$ , para cada fórmula $\varphi$ definida sobre el par $(\mathcal{F},\mathcal{P})$ y ambiente $l$ , por inducción sobre $\varphi$ como se ilustra abajo. Si se cumple $\mathcal{M}\models_{l}\varphi$ , decimos que $\varphi$ se evalúa a $\top$ en el modelo $\mathcal{M}$ con respecto al ambiente $l$ .

$P$ :	Si $\varphi$ es de la forma $P(t_{1},\ldots,t_{n})$ , entonces interpretamos los términos $t_{1},\ldots,t_{n}$ en el universo $A$ al reemplazar símbolos de constantes y funciones por los valores asignados en $\mathcal{M}$ , y todas las variables por sus valores correspondientes en $l$ . Así encontramos valores concretos $a_{1},\ldots,a_{n}$ de $A$ para cada uno de estos términos. De modo que $\mathcal{M}\models_{l}P(t_{1},\ldots,t_{n})$ se satisface syss $(a_{1},\ldots,a_{n})$ está en el conjunto $P^{\mathcal{M}}$
$\forall x$ :	La relación $\mathcal{M}\models_{l}\forall x\,\varphi$ se satisface syss $\mathcal{M}\models_{l[x\mapsto a]}\varphi$ se satisface para toda $a\in A$ .
$\exists x$ :	La relación $\mathcal{M}\models_{l}\exists x\,\varphi$ se satisface syss $\mathcal{M}\models_{l[x\mapsto a]}\varphi$ se satisface para alguna $a\in A$ .
$\neg$ :	La relación $\mathcal{M}\models_{l}\neg\varphi$ se satisface syss no es el caso que $\mathcal{M}\models_{l}\varphi$ se satisface.
$\vee$ :	La relación $\mathcal{M}\models_{l}\varphi_{1}\vee\varphi_{2}$ se satisface syss $\mathcal{M}\models_{l}\varphi_{1}$ o $\mathcal{M}\models_{l}\varphi_{2}$ se satisface.
$\wedge$ :	La relación $\mathcal{M}\models_{l}\varphi_{1}\wedge\varphi_{2}$ se satisface syss $\mathcal{M}\models_{l}\varphi_{1}$ y $\mathcal{M}\models_{l}\varphi_{2}$ se satisfacen.
$\rightarrow$ :	La relación $\mathcal{M}\models_{l}\varphi_{1}\rightarrow\varphi_{2}$ se satisface syss $\mathcal{M}\models_{l}\varphi_{2}$ se satisface siempre que $\mathcal{M}\models_{l}\varphi_{1}$ se satisface.
$\leftrightarrow$ :	La relación $\mathcal{M}\models_{l}\varphi_{1}\leftrightarrow\varphi_{2}$ se satisface syss $\mathcal{M}\models_{l}\varphi_{1}$ y $\mathcal{M}\models_{l}\varphi_{2}$ ambos se satisfacen o ambos no se satisfacen.

Se puede demostrar por inducción estructural que $\mathcal{M}\models_{l}\varphi$ syss $\mathcal{M}\models_{l^{\prime}}\varphi$ , siempre que $l$ y $l^{\prime}$ sean dos ambientes idénticos sobre el conjunto de variables libres de $\varphi$ .

Definición 1.4.

Sea $\varphi$ una fórmula de la lógica de predicados. Si $\varphi$ no tiene variables libres, entonces es un enunciado

Con el enunciado $\varphi$ concluimos que $\mathcal{M}\models_{l}\varphi$ se satisface, o no, sin importar la elección de $l$ . Así que para enunciados $\varphi$ excluimos al ambiente $l$ , ya que es irrelevante, y escribimos $\mathcal{M}\models\varphi$ . Por lo anterior, la utilidad de un ambiente es latente cuando se requiere conocer el valor de las variables libres. Así que podemos restringir los ambientes para que asignen valores únicamente a variables libres dentro de la fórmula.

2 Consecuencia lógica

Definición 2.1.

Sea $\Gamma$ un conjunto (posiblemente infinito) de fórmulas en lógica de predicados y $\psi$ una fórmula en dicha lógica.

1.

La fórmula $\psi$ es satisfacible syss hay un modelo $\mathcal{M}$ y un ambiente $l$ tal que $\mathcal{M}\models_{l}\psi$ se satisface. Por ejemplo, la fórmula $\psi\stackrel{{\scriptstyle\mathrm{def}}}{{=}}P(a,y)$ se satisface tomando como modelo a $\mathcal{M}$ , donde $A^{\mathcal{M}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathbb{N}$ , $a^{\mathcal{M}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}0$ y $P^{\mathcal{M}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{(x,y)\,|\,\ x\leq y\}$ ; además, $l(y)=100$ .
2.

La fórmula $\psi$ es verdadera en $\mathcal{M}$ syss para todo ambiente $l$ se satisface $\mathcal{M}\models_{l}\psi$ . Por ejemplo, la fórmula $\psi\stackrel{{\scriptstyle\mathrm{def}}}{{=}}P(a,y)$ es verdadera en el mismo modelo que el del punto 1, ya que se satisface $\mathcal{M}\models_{l}\psi$ para todo ambiente $l$ .
3.

La fórmula $\psi$ es válida syss $\mathcal{M}\models_{l}\psi$ se satisface para todos los modelos $\mathcal{M}$ y ambientes $l$ en los cuales podemos darle sentido a $\psi$ , en tal caso escribimos $\models\psi$ . La fórmula $\psi\stackrel{{\scriptstyle\mathrm{def}}}{{=}}P(a,y)$ no es válida, pero las fórmulas $\neg\exists x\,\varphi\leftrightarrow\forall x\,\neg\varphi$ , $\exists x\,(B(x)\rightarrow\forall y\,B(y))$ y $\big{(}\forall x\;(P(x)\rightarrow\exists y\;Q(y))\big{)}\rightarrow\big{(}% \forall x\;\exists y\;(P(x)\rightarrow Q(y))\big{)}$ sí lo son, como se mostrará en los ejemplos al final de la nota.
4.

El conjunto $\Gamma$ es consistente o satisfacible syss existe un modelo $\mathcal{M}$ y un ambiente $l$ tal que $\mathcal{M}\models_{l}\varphi$ se satisface para todo $\varphi\in\Gamma$ .
5.

La consecuencia lógica $\Gamma\models\psi$ se cumple syss para todo modelo $\mathcal{M}$ y ambiente $l$ , si $\mathcal{M}\models_{l}\varphi$ se satisface para toda $\varphi\in\Gamma$ , entonces también $\mathcal{M}\models_{l}\psi$ se satisface.

Observe que el símbolo $\models$ está sobrecargado: denota la satisfacción de una fórmula por algún modelo ‘ $\mathcal{M}\models\varphi$ ’ y la consecuencia lógica ‘ $\varphi_{1},\ldots,\varphi_{n}\models\psi$ ’.

Además, considere que al verificar $\varphi_{1},\varphi_{2},\dots,\varphi_{n}\models\psi$ , hay que comprobarlo para todos los posibles modelos, es decir, todos los modelos que tienen la estructura adecuada (funciones y predicados con el número correcto de argumentos). Esta tarea es imposible de realizar mecánicamente. Esto se debe contrastar con la situación en lógica proposicional, donde las tablas de verdad de las proposiciones involucradas fueron la base para determinar la consecuencia lógica.

Sin embargo, a veces podemos argumentar que ciertas consecuencias lógicas son válidas. Hacemos esto proporcionando un argumento que no depende del modelo en cuestión. Por supuesto, esto funciona solo para un número muy limitado de casos. Veamos un ejemplo.

Ejemplo 2.2.

Justifique la siguiente consecuencia lógica:

\forall x(P(x)\to Q(x))\models\forall xP(x)\to\forall xQ(x)

Sea $\mathcal{M}$ un modelo que satisface $\forall x(P(x)\to Q(x))$ . Por demostrar que $\mathcal{M}$ satisface $\forall xP(x)\to\forall xQ(x)$ . Analicemos los siguiente casos:

No todo elemento de nuestro modelo satisface $P$ , entonces $\mathcal{M}$ satisface $\forall xP(x)\to\forall xQ(x)$ pues el antecedente de la implicación es falso.
Todo elemento de nuestro modelo satisface $P$ , como $\mathcal{M}$ satisface $\forall x(P(x)\to Q(x))$ , se tiene que cada elemento del modelo satisface $Q$ también.

Por consiguiente, $\mathcal{M}$ satisface $\forall xP(x)\to\forall xQ(x)$ .

¿Qué hay de la consecuencia lógica inversa? ¿Es $\forall xP(x)\to\forall xQ(x)\models\forall x(P(x)\to Q(x))$ válido también? No es el caso, supongamos que $\mathcal{M}^{\prime}$ es un modelo que satisface $\forall xP(x)\to\forall xQ(x)$ . Si $A^{\prime}$ es el universo, y $P^{\mathcal{M}^{\prime}}$ y $Q^{\mathcal{M}^{\prime}}$ son las interpretaciones correspondientes de $P$ y $Q$ , entonces $\mathcal{M}^{\prime}\models\forall xP(x)\to\forall xQ(x)$ dice que si $P^{\mathcal{M}^{\prime}}$ es igual a $A^{\prime}$ , entonces $Q^{\mathcal{M}^{\prime}}$ también debe ser igual a $A^{\prime}$ . Sin embargo, si $P^{\mathcal{M}^{\prime}}$ no es igual a $A^{\prime}$ , entonces esta implicación es trivialmente verdadera. Como no se cuentan con restricciones adicionales sobre nuestro modelo $\mathcal{M}^{\prime}$ , podemos construir el contraejemplo siguiente: sea $A^{\prime}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{a,b\}$ , $P^{\mathcal{M}^{\prime}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{a\}$ y $Q^{\mathcal{M}^{\prime}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\{b\}$ . Entonces $\mathcal{M}^{\prime}\models\forall xP(x)\to\forall xQ(x)$ es cierto, pero $\mathcal{M}^{\prime}\models\forall x(P(x)\to Q(x))$ no lo es.

A continuación se presentan algunas ideas y definiciones que serán útiles en notas futuras.

Definición 2.3.

Sean $\mathcal{M}$ un modelo y $\psi$ una fórmula de la lógica de predicados. Decimos que $\psi$ es falsa en $\mathcal{M}$ syss $\neg\psi$ es verdadera en $\mathcal{M}$ .

Así, una fórmula $\psi$ no es verdadera si es insatisfacible en algún ambiente, es decir, $\psi$ no es verdadera si $\neg\psi$ es satisfacible en ‘algún’ ambiente. Pero para afirmar que $\psi$ es falsa tendríamos que demostrar que $\neg\psi$ es satisfacible en ‘todos’ los ambientes posibles. Por lo tanto, la noción de falsedad es más fuerte que la noción de no ser verdad.

Proposición 2.4.

Sean $\mathcal{M}$ un modelo y $\varphi$ una fórmula de la lógica de predicados. Escribimos $\forall\varphi$ como la cerradura universal de $\varphi$ , es decir, la fórmula obtenida al ligar mediante cuantificadores universales a todas las variable libres de $\varphi$ . Entonces,

$\varphi$ es verdadera en $\mathcal{M}$ syss $\forall\varphi$ es verdadera en $\mathcal{M}$ .

La cerradura universal de una fórmula es un enunciado, por lo que razonar sobre su verdad es más simple puesto que los enunciados se comportan del mismo modo que las fórmulas proposicionales, como lo indica la siguiente proposición:

Proposición 2.5.

Sean $\varphi$ un enunciado y $\mathcal{M}$ un modelo. Entonces, se cumple una y sólo una de las siguientes condiciones:

1.

$\varphi$ es verdadera en $\mathcal{M}$ .
2.

$\varphi$ es falsa en $\mathcal{M}$ .

Corolario 2.6.

Si $\varphi$ es un enunciado, entonces $\varphi$ es falso si y sólo si $\varphi$ no es verdadero en $\mathcal{M}$ .

Por último, notemos los siguiente referente a la validez en lógica de predicados: Dada una fórmula $\varphi$ en lógica de predicados, ¿se satisface $\models\varphi$ , sí o no?

Teorema 2.7.

El problema de decisión de la validez en lógica de predicados es indecidible: no existe un algoritmo (o programa) tal que, dada cualquier $\varphi$ , decida si $\models\varphi$ .

Ejemplo 2.8.

$\models\neg\exists x\,\varphi\leftrightarrow\forall x\,\neg\varphi$

Sea $\mathcal{M}$ un modelo y $\ell$ un ambiente.

\begin{array}[]{lcl}\mathcal{M}\models_{\ell}\neg\exists x\,\varphi&% \Leftrightarrow&\mathcal{M}\not\models_{\ell}\exists x\,\varphi\\ &\Leftrightarrow&\text{no existe $a$ en el universo tal que }\mathcal{M}% \models_{\ell[x\mapsto a]}\varphi\\ &\Leftrightarrow&\text{para todo $a$ en el universo tenemos }\mathcal{M}\not% \models_{\ell[x\mapsto a]}\varphi\\ &\Leftrightarrow&\text{para todo $a$ se cumple }\mathcal{M}\models_{\ell[x% \mapsto a]}\neg\varphi\\ &\Leftrightarrow&\mathcal{M}\models_{\ell}\forall x\,\neg\varphi\mathchar 46% \relax\end{array}

Ejemplo 2.9.

Vamos a demostrar la existencia del dios Baco quien tiene la propiedad de que si él bebe, entonces todos beben, es decir, $\models\exists x\,(B(x)\rightarrow\forall y\,B(y))$ . Sea $\mathcal{M}$ un modelo y $\ell$ un ambiente, veamos que se satisface $\mathcal{M}\models_{\ell}\exists x\,(B(x)\rightarrow\forall y\,B(y))$ , es decir, se cumple $\mathcal{M}\models_{\ell[x\mapsto b]}(B(x)\rightarrow\forall y\,B(y))$ para algún $b$ en el universo $A$ . Tenemos dos casos:

$B^{\mathcal{M}}=A$ . Se tiene $\mathcal{M}\models_{\ell[y\mapsto a]}B(y)$ para toda $a\in A$ . Así, $\mathcal{M}\models_{\ell}\forall y\,B(y)$ . Como $\forall y\,B(y)$ es un enunciado, tenemos que $\mathcal{M}\models_{\ell[x\mapsto b]}\forall y\,B(y)$ con $b$ un elemento del universo, sabemos que hay al menos uno porque el universo no es vacío. Así se cumple $\mathcal{M}\models_{\ell[x\mapsto b]}(B(x)\rightarrow\forall y\,B(y))$ .
$B^{\mathcal{M}}\neq A$ . Se tiene un individuo del universo que no cumple $B$ . Sea $b$ tal individuo, de modo que $\mathcal{M}\not\models_{\ell[x\mapsto b]}B(x)$ , en tal caso $\mathcal{M}\models_{\ell[x\mapsto b]}(B(x)\rightarrow\forall y\,B(y))$ , pues el antecedente de la implicación se evalúa a falso.

Por lo tanto, se satisface $\mathcal{M}\models_{\ell}\exists x\,(B(x)\rightarrow\forall y\,B(y))$ .

Ejemplo 2.10.

Demuestre que la fórmula $\big{(}\forall x\;(P(x)\rightarrow\exists y\;Q(y))\big{)}\rightarrow\big{(}% \forall x\;\exists y\;(P(x)\rightarrow Q(y))\big{)}$ es válida.

Sea $\mathcal{M}$ un modelo y $\ell$ un ambiente. Supongamos $\mathcal{M}\models_{\ell}\forall x\,(P(x)\rightarrow\exists y\,Q(y))$ , es decir, para toda $a\in A$ se cumple $\mathcal{M}\models_{\ell[x\mapsto a]}P(x)\rightarrow\exists y\,Q(y)$ .

Vamos a suponer además que $\mathcal{M}\models_{\ell[x\mapsto a]}P(x)$ , entonces $\mathcal{M}\models_{\ell[x\mapsto a]}\exists y\,Q(y)$ . Así, hay una $b\in A$ tal que $\mathcal{M}\models_{\ell[x\mapsto a,y\mapsto b]}Q(y)$ , luego $\mathcal{M}\models_{\ell[x\mapsto a]}Q(b)$ . Llegamos a que si $\mathcal{M}\models_{\ell[x\mapsto a]}P(x)$ , entonces $\mathcal{M}\models_{\ell[x\mapsto a]}Q(b)$ , esto es $\mathcal{M}\models_{\ell[x\mapsto a]}P(x)\rightarrow Q(b)$ .

Actualizando el ambiente con $y\mapsto b$ , tenemos $\mathcal{M}\models_{\ell[x\mapsto a,y\mapsto b]}P(x)\rightarrow Q(y)$ . Por lo tanto, $\mathcal{M}\models_{\ell[x\mapsto a]}\exists y\,(P(x)\rightarrow Q(y))$ . Esto se vale para toda $a\in A$ , de manera que $\mathcal{M}\models_{\ell}\forall x\;\exists y\;(P(x)\rightarrow Q(y))\big{)}$ .

Ejercicio

Considere los siguientes tres enunciados:

\begin{array}[]{lll}\varphi_{1}&\stackrel{{\scriptstyle\mathrm{def}}}{{=}}&% \forall x\,P(x,x)\\ \varphi_{2}&\stackrel{{\scriptstyle\mathrm{def}}}{{=}}&\forall x\,\forall y\,(% P(x,y)\rightarrow P(y,x))\\ \varphi_{3}&\stackrel{{\scriptstyle\mathrm{def}}}{{=}}&\forall x\,\forall y\,% \forall z\,((P(x,y)\wedge P(y,z))\rightarrow P(x,z))\end{array}

los cuales expresan que el predicado $P^{(2)}$ es reflexivo, simétrico y transitivo, respectivamente. Muestre que ninguno de estos enunciados es consecuencia lógica de los otros dos, escogiendo para cada par de enunciados un modelo que los satisfaga, pero no al tercer enunciado. Es decir, se pide encontrar tres relaciones binarias, cada una satisfaciendo solo dos de estas propiedades.

Lógica Computacional Nota 08. Semántica de la lógica de predicados.11El material aquí presentado se basa el libro de Huth y Ryan, Logic in Computer Science; en las notas del prof. Francisco Hernández Q.; y en las notas del prof. Favio Miranda.