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, Las variables son los conceptos que recojen valores concretos y se representan con letras minúsculas
Las variables pueden ser cuantificadas usando los cuantificadores universal
y existencial
, 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:
es un humano
es mortal.
Y con ellos podemos construir el enunciado
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 significa que
es la madre de
. Pero realmente estamos diciendo que
es una de las madres de
, 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
para representar a la madre de
. Veamos la diferencia. Las dos expresiones siguientes:
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
son términos y
es una función de aridad
> 0, entonces
es un término
Fórmulas
- si
es un símbolo de predicado de aridad
y
son términos, entonces
es una f.b.f.
- si
es una f.b.f., también lo es
- si
y
son f.b.f., también lo son
,
- si
es una f.b.f. y
es una variable, entonces
y
también son f.b.f.
Una variable que aparece en una fórmula
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 un conjunto de símbolos de función y
un conjunto de símbolos de predicado. Un modelo
del par
está formado por
- un conjunto
de valores concretos del universo
- para cada símbolo de función 0-ario
, un valor concreto
de
. Nota: una función 0-aria es una constante.
- para cada el resto de símbolos de función
, una función concreta
- para cada símbolo de predicado
un subconjunto
de n-tuplas de
.
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 que asocian a cada variable
un valor
del modelo
Definición 2. Una tabla de búsqueda o un entorno para un universo de valores concretos es una función
definido del conjunto de variables var sobre
. Denotamos con
la tabla que mapea
en
.
Con todo esto ya se puede dar una semántica a la lógica de primer orden. Dado un modelo para un par
y dado un entorno
, se define la satisfacibilidad
para cada f.b.f.
y entorno
.
sii
, donde los términos
se interpretan sobre
reemplazando todas las variables por sus valores de acuerdo con el entorno
.
sii
se cumple para todo
sii
se cumple para algún
sii no se da el caso de que se cumpla
.
sii se cumple
y se cumple
.
-
sii se cumple
o se cumple
.
sii
se cumple siempre que se cumpla
.
El problema que aparece en la lógica de primer orden es que no se puede comprobar mecánicamente que 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.
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.