Publicado en

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.

Publicado en

Lógica proposicional

Empecemos por el principio. La lógica proposicional es la más sencilla. El lenguaje está basado en proposiciones o enunciados declarativos que  son enunciados que pueden evaluarse como ciertos o falsos. Normalmente, se emplean símbolos distintos p, q, r,... para cada enunciado y a partir de ellos se pueden generar expresiones más complejas con operadores lógicos de la forma habitual, usando \land, \lor, \neg, \to. Por ejemplo, (p \land q) \to (\neg r \lor q). Una fórmula bien formada (f.b.f.) se construye empleando exclusivamente las reglas siguientes:

  • cualquier átomo p, q, r, \ldots es una f.b.f.
  • si \phi es una f.b.f., también lo es (\neg\phi)
  • si \phi, \psi son f.b.f., también lo es (\phi \land \psi )
  • si \phi, \psi son f.b.f., también lo es (\phi \lor \psi )
  • si \phi, \psi son f.b.f., también lo es (\phi \to \psi )

Otra forma de indicar estas reglas de construcción es usar una gramática BNF, de la forma

\phi ::= p \mid (\neg \phi) \mid (\phi \land \phi) \mid (\phi \lor \phi)\mid (\phi \to \phi)

La semántica de las expresiones anteriores viene dada por la tabla de verdad correspondiente, que examina el valor de verdad de la expresión \phi a partir de todas las combinaciones posibles de los valores de verdad de las proposiciones atómicas. Por ejemplo, para la expresión anterior  (p \land q) \to (\neg r \lor q), la tabla de verdad equivalente sería [table id=1 /]

Las reglas de deducción nos permiten construir sistemas de argumentación basados en la lógica, de modo que podemos llegar a una conclusión \psi (podemos deducir \psi) a partir de una serie de proposiones \phi_1, \phi_2,\ldots,\phi_n . Lo representaremos como 

\phi_1, \phi_2,\ldots,\phi_n \vdash \psi

Por otro lado, si además para todas las valuaciones en las que las proposiciones \phi_1, \phi_2,\ldots,\phi_n se evalúan a T, \psi también se evalúa a T, entonces se cumple 

\phi_1, \phi_2,\ldots,\phi_n \models \psi

donde \models es la relación de equivalencia semántica. A partir de estos dos conceptos, deducción y equivalencia semántica, puede estudiarse la corrección (soundness) y la completitud (completeness) de la lógica proposicional. Suelen definirse a partir de estos teoremas

Teorema 1 (corrección). Sean \phi_1, \phi_2,\ldots,\phi_n y \psi fórmulas proposicionales. Si \phi_1, \phi_2,\ldots,\phi_n \vdash \psi es válido entonces se cumple \phi_1, \phi_2,\ldots,\phi_n \models \psi.

Básicamente, el Teorema 1 quiere decir que todo aquello que se puede deducir a partir de las proposiciones utilizando las reglas de inferencia mantiene el valor de verdad de las proposiciones. O dicho de otra manera, todo lo que se puede deducir es cierto.

Teorema 2 (completitud). Sean \phi_1, \phi_2,\ldots,\phi_n y \psi  fórmulas proposicionales. Si se cumple \phi_1, \phi_2,\ldots,\phi_n \models \psi entonces existe una prueba que permite deducir \phi_1, \phi_2,\ldots,\phi_n \vdash \psi.

De la misma forma, el Teorema 2 quiere decir que si dos expresiones tienen el mismo valor de verdad, podríamos encontrar una argumentación que nos permita deducir una de la otra. O dicho de otra forma, todo lo que es cierto puede deducirse.