Miguel Rebollo

Abr 29

Lógica de predicados

La lógica proposicional falla cuando desaeamos expresar cosas como todos…, sólo…, existe… La lógica de predicados, o lógica de primer orden, incluye los conceptos de predicado, variable y cuantificadores para poder representar con mayor exactitud enunciados declarativos, extendiendo así la lógica proposicional. Los predicados representan propiedades que son ciertas y se representan con letras mayúsculas, $P, Q, R, \ldots$ Las variables son los conceptos que recojen valores concretos y se representan con letras minúsculas $x, y, z, \ldots$ Las variables pueden ser cuantificadas usando los cuantificadores universal $\forall$ y existencial $\exists$ , que se leen “para todo” y “existe” respectivamente.

Por ejemplo, para expresar el típico enunciado lógico (y políticamente correcto ;-) “Los humanos son mortales” necesitamos dos predicados:

$H(x): x$ es un humano

$M(x): x$ es mortal.

Y con ellos podemos construir el enunciado

$\forall x(H(x) \to M(x))$

que se leería “para todo x, si x es humano entonces x es mortal”.

Además de los símbolos de predicado, es posbible emplear otros símbolos adicionales, llamados funciones, que permiten escribir expresiones más compactas y más sencillas de comprender. Las funciones se representan mediante letras minúsculas. Por ejemplo, el predicado $M(x,y)$ significa que $x$ es la madre de $y$ . Pero realmente estamos diciendo que $x$ es una de las madres de $y$ , lo cual no es muy elegante porque sabemos que una persona sólo puede tener una madre (biológica). En ese caso, puede emplearse un símbolo de función $m(x)$ para representar a la madre de $x$ . Veamos la diferencia. Las dos expresiones siguientes:

$\forall x \forall y (H(x) \land M(x,y) \to J(x,y))$

$\forall x (H(x) \to J(x, m(x)))$

se leen igual: un hijo -H(x)- es más joven -J(x,y)- que su madre -M(x,y) o m(x)-.

Esta representación es válida sólo para denotar un único objeto; no podría usarse, por ejemplo, para representar el concepto de “hermano”. H(x) es un predicado unario (sólo tiene un argumento) y J(x,y) es un predicado binario. En general, los predicados (y también las funciones) pueden tener n argumentos. Al número de argumentos se le denomina aridad.

Las reglas de formación de las expresiones en lógica de primer orden son las siguientes

Términos

una variable es un término
una constante es un término
si $t_1, t_2, \ldots, t_n$ son términos y $f$ es una función de aridad $n$ > 0, entonces $f(t_1, t_2, \ldots, t_n)$ es un término

Fórmulas

si $P$ es un símbolo de predicado de aridad $n \geq 1$ y $t_1, t_2, \ldots, t_n$ son términos, entonces $P(t_1, t_2, \ldots, t_n)$ es una f.b.f.
si $\phi$ es una f.b.f., también lo es $(\neg \phi)$
si $\phi$ y $\psi$ son f.b.f., también lo son $(\phi \land \psi)$ ,
si $\phi$ es una f.b.f. y $x$ es una variable, entonces $(\forall x \phi)$ y $(\exists x \phi)$ también son f.b.f.

Una variable $x$ que aparece en una fórmula $\phi$ es una variable ligada si y sólo si están dentro del ámbito de un cuantificador. En otro caso diremos que es una variable libre.

De la misma forma que la semántica de la lógica proposicional se daba mediante tablas de verdad, en el caso de la lógica de predicados se hace necesario un mecanismo diferente debido a la existencia de las varaibles y la necesidad de realizar sustituciones. De manera que los símbolos de predicado y de función no se pueden evaluar simplemente a verdadero o falso, sino que es necesario disponer de un modelo.

Definición 1. Sea $F$ un conjunto de símbolos de función y $Pred$ un conjunto de símbolos de predicado. Un modelo $M$ del par $(F,Pred)$ está formado por

un conjunto $A$ de valores concretos del universo
para cada símbolo de función 0-ario $f \in F$ , un valor concreto $f^M$ de $A$ . Nota: una función 0-aria es una constante.
para cada el resto de símbolos de función $f \in F$ , una función concreta $f^M:A^n \to A$
para cada símbolo de predicado $P \in Pred$ un subconjunto $P^M \subseteq A^n$ de n-tuplas de $A$ .

De esta forma podemos calcular el valor de verdad de cualquier f.b.f. compuesta por símbolos de función y de predicado, pero todavía no podemos analizar qué ocurre cuando aparecen variables cuantificadas, que nos obligan a interpretar fórmulas de forma relativa a un entorno. Lo haremos mediante tablas de búsqueda $l$ que asocian a cada variable $x$ un valor $l(x)$ del modelo

Definición 2. Una tabla de búsqueda o un entorno para un universo $A$ de valores concretos es una función $l:var \to A$ definido del conjunto de variables var sobre $A$ . Denotamos con $l[x \mapsto a]$ la tabla que mapea $x$ en $a$ .

Con todo esto ya se puede dar una semántica a la lógica de primer orden. Dado un modelo $M$ para un par $(F,Pred)$ y dado un entorno $l$ , se define la satisfacibilidad $M \models_l \phi$ para cada f.b.f. $\phi$ y entorno $l$ .

$M \models_l P(t_1,t_2,\ldots,t_n):$ sii $P(a_1,a_2,\ldots,a_n) \in P^M$ , donde los términos $t_1,t_2,\ldots,t_n$ se interpretan sobre $A$ reemplazando todas las variables por sus valores de acuerdo con el entorno $l$ .
$M \models_l \forall x \phi:$ sii $M \models_{l [x\mapsto a]} \phi$ se cumple para todo $a \in A$
$M \models_l \exists x \phi:$ sii $M \models_{l [x\mapsto a]} \phi$ se cumple para algún $a \in A$
$M \models_l \neg \phi:$ sii no se da el caso de que se cumpla $M \models_l \phi$ .
$M \models_l \phi_1 \land \phi_2:$ sii se cumple $M \models_l \phi_1$ y se cumple $M \models_l \phi_2$ .
$M \models_l \phi_1 \lor \phi_2:$ sii se cumple $M \models_l \phi_1$ o se cumple $M \models_l \phi_2$ .
$M \models_l \phi_1 \to \phi_2:$ sii $M \models_l \phi_2$ se cumple siempre que se cumpla $M \models_l \phi_1$ .

El problema que aparece en la lógica de primer orden es que no se puede comprobar mecánicamente que $\phi_1, \phi_2, \ldots, \phi_n \models \psi$ en el caso general (sí que puede hacerse cuando los predicados son sólo unarios). Por eso se dice que la lógica proposicional es indecidible., porque no hay un algoritmo que tome come entrada una f.b.f. $\phi$ y termine siempre con una respuesta correcta que sea verdadero si la f.b.f. es correcta (se evalua a cierto) o falso en caso contrario.

Este mismo problema de indecidibilidad es el que tienen RDF y OWL-Full: no se puede garantizar que un proceso de razonamiento que trata de determinar la veracidad de una fórmula termine en todos los casos. Por eso se emplea habitualmente OWL-DL para razonar en la web semántica y porque la prefiero personalmente: porque es una lógica decidible y suple la pérdida de expresividad (que yo no he notado hasta ahora) con algoritmos de razonamiento que garanbtizan su terminación.

Lógica de predicados

Post relacionados

Leave a Reply

Qué hago ahora...

Categorías

Enlaces - Sitios relacionados

Blogroll - Sitios que leo

Otros sitios de interés

Archivos

Últimas anotaciones

Comentarios recientes

Contacto