LÓGICA DE PREDICADOS
La lógica de predicados orden constituye una
extensión de la lógica. Esta extensión explicita y sistematiza el proceso
inferencial que se efectúa cuando se trabaja con funciones proposicionales y
cuantificadores, o de manera mas precisa, con un lenguaje de primer orden.
La lógica de predicados se emplea como una técnica de especificación formal
dentro de la metodología de la programación; esto es: se traducen las
especificaciones de los programas a un lenguaje de primer orden con objeto de
que las reglas formales del mismo pongan de manifiesto posibles fallos del
soporte lógico, intentando así aumentar la fiabilidad del diseño del programa.
Estos métodos formales son una técnica más de la ingeniería de la
programación.
1. Introducción
Consideremos el siguiente argumento clásico
Todos los filósofos son sabios,
algunos griegos son
filósofos,
luego algunos griegos son sabios.
Los enunciados contenidos en el argumento precedente son del tipo: Todos los A son B y Algún A es B. Si añadimos a éstos, los enunciados del tipo Ningún A es B y Algún A no es B, todos ellos reciben el nombre de categóricos. La tradición escolástica los ha denotado con las letras A (Universal afirmativo), I (Particular afirmativo), E (Universal negativo) y O (Particular negativo). La clase de argumentos como el considerado arriba reciben el nombre de silogismos desde Aristóteles, que fue el primero en estudiarlos. Se trata de argumentos el los que se obtiene como conclusión un enunciado categórico a partir de otros dos enenciados categóricos considerados como premisas. Usando funciones proposicionales y cuantificadores el argumento anterior se representa por
donde p(x) º x es filósofo, q(x) º x es sabio, y r(x) º x es griego.
Las proposiciones categóricas se usan
frecuentemente en matemáticas, sin embargo ¾ en contra de lo que se
creía hasta épocas relativamente recientes¾ no todos los argumentos que
usan proposiciones categóricas son inferencias directas o cadenas de
silogismos. Consideremos el ejemplo siguiente.
Ejemplo 1. Sean X e Y dos conjuntos, sea f una aplicación de X en Y y sean A y B dos subconjuntos de X. Admitamos como premisas que: (1), f es inyectiva y que, (2), f(A) = f(B). Vamos a concluir que A = B. Para ello es suficiente demostrar que A Í B, ya que para la otra inclusión basta intercambiar los papeles de A y B. Hay que probar pues que
Para
ello elegimos un elemento particular x de A y mostramos en primer
lugar que x pertenece a B. Procediendo por demostración
condicional podemos añadir la proposición (3), x Î A, a las dos premisas anteriores y
deducir de (2) y (3) que f(x) Î f(B). Esto supone que $ y Î B tal que f(x) = f(y), por lo
que, en virtud de (1), x = y. Luego, x Î B. Generalizando el resultado para
cada x Î A
obtenemos la conclusión.
A la vista de las consideraciones anteriores resulta
evidente la necesidad de extender la lógica proposicional para poder incluir
tanto los argumentos silogísticos como el desarrollado en el ejemplo
precedente. Nos limitaremos al caso de proposiciones asertóricas, esto es,
aquellas que son verdaderas o falsas.
2. Funciones proposicionales y predicados
Consideraremos funciones proposicionales x ®
p(x) definidas en un referencial o
universo formado por objetos de la misma naturaleza (lenguaje de primer orden);
es decir, que no contengan objetos formados por conjuntos de objetos (lenguajes
de segundo orden). Una función proposicional de una variable p(x),
o de dos variables q(x,y), expresa una propiedad que se predica
del objeto u objetos del universo que resultan de sustituir la variable
o variables que intervengan en la función proposicional. Así, si s(x)
º x es sabio y h(x) º x
es un hombre, la proposición " x (h(x)
® s(x)) expresa el enunciado todo hombre es
sabio. La fórmula $ x h(x) Ù s(x)
simboliza que existe un hombre sabio. Sin embargo, la fórmula $ x
(h(x) ® s(x)) expresa que existe un objeto que, en
el caso de que fuera un hombre, sería sabio, lo que no garantiza que exista un
hombre sabio. De hecho, mientras que $ x h(x) Ù s(x)
sólo es verdadera si hay algún hombre sabio, $ x (h(x)
® s(x)) puede ser verdadera incluso si no
existe ningún hombre sabio, con tal de que el universo contenga algún objeto
que no sea un hombre. Si g(x,y) º x
es mayor que y, la fórmula $ x g(x,y)
expresa que existe un objeto x que es mayor que y. En este caso
es esencial precisar el universo E en el que estemos trabajando.
Ejemplo 2. Consideremos en un universo formado por el conjunto de los enteros la función proposicional i(x,y) º x es igual a y. La fórmula $ x i(x,0) expresa que existe un entero nulo. El cero juega aquí el papel de una constante.
En las fórmulas " x (h(x) ® s(x)) y $ x h(x) Ù s(x), la única variable que interviene en ambas, la variable x, aparece ligada por un cuantificador, mientras que en la fórmula $ x g(x,y) la variable y no está ligada por el cuantificador existencial, por lo que se dice que se trata de una variable libre.
Ejemplo 3. Sea p(x,y) = x es el padre de y, m(x,y) = x es la madre de y. En un universo formado por personas la fórmula $ z m(x,z) Ù p(z,y) expresa que x es la abuela paterna de y. En ella z es una variable ligada, mientras que x e y son variables libres.
3. Fórmulas bien formadas
En un universo numérico E, la expresión f(x,y)
= x + y no es una función proposicional puesto que no predica
ninguna propiedad del par de números (x,y), se trata en realidad
de una función. Admitiremos el uso de funciones para la definición de funciones
proposicionales.
Ejemplo 4. En el universo del Ejemplo 2, y siendo i(x,y) la función proposicional igualdad, con ayuda de la función suma considerada arriba podemos definir la función proposicional a(x,y) = i(f(x,y),0), que expresa que x + y = 0; en tal caso la fórmula " x$ y a(x,y) establece que cada entero x tiene un opuesto y.
No todas las fórmulas construidas con ayuda de constantes, variables, funciones y funciones proposicionales constituirán nuestro lenguaje de primer orden. Nos limitaremos sólo a una clase de fórmulas, que llamaremos fórmulas bien formadas, o fbfs, y que definimos recursivamente a continuación. Serán fbfs:
1. Las fórmulas atómicas. Es decir, funciones proposicionales constantes o funciones de la forma p(x1, x2, ..., xn); o bien de la forma p(x1, x2, ... , a, ..., xn), siendo a una constante.
2. Si A es una fbf,
entonces Ø A es una fbf.
3. Si A y B
son fbfs, entonces A Ú B, A Ù B, A ® B
y A « B son fbfs.
4. Si A es una fbf
y x es una variable ¾ que puede aparecer en A como variable libre,
ligada, o no aparecer en A¾ , entonces " x A y $ x
A son fbfs.
5. Sólo las fórmulas
obtenidas con el uso reiterado de las reglas anteriores son fbfs.
Si una fbf es verdadera en un cierto universo E diremos que es verdadera en E, mientras que si A es verdadera en cualquier universo no vacío pondremos Ø A.
Ejemplo 5. Sea p(x) = x es múltiplo de 2, y sea q(x) = x es múltiplo de 3. La fórmula " x (p(x) « q(x)) no es válida siempre, pero " x p(x) ® $ x p(x) es verdadera en cualquier universo no vacío y para cualquier p.
Si A y B son fbfs, en el caso de que Ø (A ® B) se escribe A Þ B y se dice que A implica B; en particular, extendiendo el ejemplo anterior, " x A(x) Þ $ x A(x), mientras que si Ø (A « B) se escribe A º B o A Û B, y se dice que A es equivalente a B. Por otro lado, es obvio que si A y B son dos fbfs que no contienen ninguna variable libre, persisten las equivalencias de la lógica proposicional; en particular, Ø Ø A º A, A ® B º Ø A Ù B, A Ú B º B Ú A, (A ® B) Ù (B ® A) º A « B, etc.
Ejemplo 6. Las equivalencias
, 
,
que denominaremos Leyes de De Morgan generalizadas (LMG) son válidas en cualquier universo.
4. Reglas de inferencia
El proceso inferencial ¾
argumento o razonamiento¾ en la lógica de predicados es análogo al de la lógica
proposicional; es decir, se trata de una secuencia finita de proposiciones
obtenidas a partir de las premisas usando las leyes de inferencia, siendo la
conclusión la que ocupa la última posición de la secuencia. Las reglas de
inferencia de la lógica de predicados usa las tres reglas de inferencia de la
lógica proposicional, además de las cuatro siguientes.
Ley de especificación universal (EU). Si en un punto del argumento aparece la proposición " x
A(x) podemos escribir A(x) en el paso siguiente.
Ley de especificación existencial (EE). Si en un punto del argumento aparece la proposición $ x
A(x) podemos escribir A(x) en el paso siguiente
siempre que la x no aparezca como variable libre en alguna de las
proposiciones de los pasos precedentes. Si así ocurriera bastaría usar otra
variable, por ejemplo y, y escribir A(y) en vez de A(x).
Ley de generalización existencial (GE). Del paso A(x) podemos deducir $ x
A(x) en el paso siguiente.
Ley de generalización universal (GU). Del paso A(x) podemos concluir " x
A(x) en el caso de que x no aparezca como variable libre
en ninguna de las premisas y de que la libertad de la variable x no
provenga del uso de la regla de especificación existencial en niguno de los
pasos precedentes.
Ejemplo 7. Vamos a establecer la validez del argumento que fue al principio, a saber:
EE (2)
EU (1)
S (3)
MP (4,5)
P7. r(x)
S (3)
Ley de la unión (6,7)
GE (8)
No podemos concluir que " x r(x) Ù q(x) debido a las restricciones en el uso de la GU.
Ejemplo 8.
Vamos a obtener la conclusión " x r(x) Ù Ø p(x)
de las premisas
para ello razonamos como sigue:
LMG (3)
EU (1)
EU (2)
EU (4)
MP (6,7)
MT (5,7)
Ley de la unión (8,9)
GU (10)
5. Sistemas
formales
En esta sección llamaremos alfabeto a
cualquier conjunto numerable å no vacío cuyos elementos llamaremos símbolos o letras.
Un lenguaje L sobre un alfabeto å es cualquier subconjunto no
vacío del conjunto
A los elementos de L ¾ a las
palabras del lenguaje¾ las llamaremos fórmulas bien formadas fbfs.
Por lo general, el conjunto L viene definido mediante una reglas,
llamadas reglas de formación, que vienen enunciadas en un lenguaje ajeno
al lenguaje L ¾ un metalenguaje¾ y que usualmente no es otro que el lenguaje ordinario.
Estas reglas de formación constituyen la gramática o sintaxis de L.
Ejemplo
9. El lenguaje L de la lógica
proposicional puede definirse de la manera siguiente. Se considera un conjunto
numerable no vacío D de símbolos
adecuado para simbolizar las proposiciones atómicas del lenguaje ordinario,
representadas por letras latinas; y el conjunto finito de símbolos S = {Ø , Ú , Ù , ® , « , (, )}. Se define entonces el alfabeto de la
lógica proposicional como la unión de D y de S. La gramática viene dada por las siguientes reglas:
1. Cada p Î D es una fbf; 2. Si P es una fbf,
entonces Ø P es una fbf; 3. Si P
y Q son fbfs, entonces P Ú Q, P Ù Q, P ® Q y P « Q son fbfs; 4. Cada palabra P obtenida por
aplicación reiterada de las reglas anteriores es una fbf.
Dado un lenguaje L se
considera un conjunto SL ¹ Æ ,
llamado conjunto de los valores semánticos de L. Una interpretación
para L es cualquier aplicación I de L en SL.
Una semantica para un lenguaje L es un conjunto de interpretaciones para
L.
Ejemplo
10. En el lenguaje de la lógica proposicional se toma SL
= {0, 1} y se consideran interpretaciones I definidas como sigue. Dada
una aplicación arbitraria J de D en SL, se toma la extensión natural I
sobre
es decir, tal que por ejemplo, I(p ® q) = 0 si J(p) =1 y J(q)
= 0, mientras que I(p ® q) = 1 en cualquier otro caso. Se extiende entonces I
por recursión finita.
Sea L un lenguaje, SL
el conjunto de sus valores semánticos, D un subconjunto de SL
llamado conjunto de los valores semánticos destacados, y M Í L.
Una interpretación I para L se dice que es un modelo para M
si I(a) Î D para cada a Î M. Una fbf
a se dice válida si cualquier interpretación para L
es un modelo para {a}.
Ejemplo
11. En el lenguaje de la lógica proposicional L con la semántica definida en el ejemplo
anterior se elije {1} como conjunto de los valores semanticos destacados. Si I
es una interpretación tal que I(p) = 1 pero I(q) =
0, entonces I es un modelo para {Ø q, Ø p ® q}, pero no para {q, p
Ú q}. Si M es un conjunto de
tautologías, cualquier interpretación es un modelo para M. En general,
si I es una interpretación para L, cada fbf P Î L tal que I(P)
= 1 se dice verdadera, mientras que si I(P) = 0, se dice
que P es falsa.
Sea M Í L.
Se dice que una fbf a se deduce semánticamente de M, y se denota por M
|= a , si todo modelo para M es un modelo para {a}.
Obviamente, M |= a para cada a Î M. Dos fbfs
a y b se dice que son semánticamente equivalentes si se
cumple que {a} |= b si y sólo si {b} |= a, lo
que se denota por a º b .
Ejemplo
12. En el lenguaje L
de la lógica proposicional con la semántica definida arriba, si p, q
Î D y M = {p
Ú q, Ø p}, es inmediato comprobar que M à q. Si t es cualquier tautología, resulta que M
|= t para cualquier M Í L que admita al menos un modelo; además Æ |= P si y sólo si P es una tautología,
lo que se escribe simplemente |= P.
Un sistema axiomático sobre
un lenguaje L es un conjunto numerable L de fbfs llamadas axiomas
junto con un conjunto no vacío  de reglas de inferencia
que determinan cuándo una fbf a es una consecuencia de un
conjunto dado M de fbfs. Dado un lenguaje L, y un
subconjunto M de L, si a es una consecuencia de M
se pone M |- a. Una inferencia, deducción, argumento o
demostración es una sucesión finita de fbfs en la que la conclusión
ocupa el último lugar y tal que cada fbf es un axioma, un elemento de M
o una consecuencia de una a más fbfs de los términos precedentes. Los
elementos de M son las premisas o hipótesis y a es la
conclusión o la tesis. Cualquier expresión de la forma L |- a, o
equivalentemente, de la forma Æ |- a , se
llama un teorema del sistema y se denota por |- a.
Ejemplo
13. Para la lógica proposicional se considera el siguiente sistema
axiomático, debido a Lukasiewicz.
Axioma I. 
.
Axioma
II. 
.
Axioma
III. 
.
donde P, Q y R son fbfs. El sistema
sólo tiene una regla de inferencia, el modus ponens, es decir, {P,P ® Q} |- Q,
siendo P y Q fbfs.
En el sistema de Lukasiewicz de la
lógica proposicional provista con la semántica definida en los ejemplos
anteriores se verifican los resultados siguientes.
TEOREMA DE DEDUCCIÓN
Si M Í L y P y Q son fbfs, entonces M |- (P ® Q)
si y sólo si M U {P} |- Q. En particular, |- (P
® Q) si y sólo si {P} |- Q.
TEOREMA DE CORRECCIÓN
Si |- P, entonces |= P para cada P
Î L. En otras palabras, cada
teorema del sistema es una tautología.
TEOREMA DE COMPLETITUD
Si
|= P, entonces |- P para cada P Î L. Es decir, cada tautología es un teorema del sistema.
TEOREMA DE CONSISTENCIA
No existe ninguna fbf P tal que
ambas P y Ø P sean teoremas del sistema.
Ejemplo
14. En el sistema de Lukasiewicz para la lógica proposicional vamos a
establecer el teorema |- Ø P ® (P ® Q). En
virtud del teorema de deducción es suficiente establecer que {Ø P,P} |- Q, cosa que
hacemos a continuación.
Premisa
Premisa
Axioma I
MP (1,3)
Axioma III
MP (4,5)
MP (2,6)
Cálculo de Predicados en Inteligencia Artificial
¿Qué es
Inteligencia Artificial?
" Un área
de Ciencias de la Computación que trata de los conceptos y métodos de inferencia
simbólica mediante el computador y la representación simbólica del
conocimiento usado al hacer inferencias".
" Estudia como lograr que las máquinas realicen tareas que,
por el momento, son realizadas mejor por los seres humanos "
Aplicaciones
1. Tareas de
la vida diaria
2. Tareas
Formales
3. Tarea de
los expertos
Lo general es que se
tiene un problema que requiere solución.
IA: Conjunto
de técnicas (reglas de inferencia) independientes del problema mismo, que
permiten llegar a la solución.
Modelo de representación y reglas de inferencia.
El aspecto más
atractivo del formalismo lógico, como representación del conocimiento, es que
proporciona un buen método para la obtención de nuevo conocimiento a partir del
antiguo: la deducción matemática (la consecuencia lógica).
Se puede concluir la verdad de una afirmación sólo demostrando que
es consecuencia de lo ya conocido.
De esta manera se puede extender a la deducción como un medio de
obtener respuestas a preguntas y soluciones a problemas.
A pesar de hechos negativos, como el que no exista un
procedimiento de decisión (no es decidible) a la IA le interesa que haya un procedimiento
que pare para la mayoría de los casos que se presentan en la realidad, por lo
tanto el Cálculo de Predicados de Primer Orden es útil para IA como medio de representación e inferencia.
La IA no garantiza
siempre una respuesta( no es determinista, no representa procedimiento
efectivo)
Resolución
Es una regla de inferencia usada en la deducción computacional, debido a que es
eficiente ya que trabaja sobre sentencias que han sido transformadas a una
forma canónica llamadas cláusulas disyuntivas.
Este proceso de resolución obtiene demostraciones por refutación.
Es decir, para probar una proposición (su validez) se intenta demostrar que su
negación lleva a una contradicción con las proposiciones conocidas (es decir es
insatisfactible).
No hay una atribución de verdad que satisfaga el ejemplo anterior.
Conversión a
cláusulas
Puesto que existe un
algoritmo para convertir cualquier fbf a su FNC (conjunción
cláusulas), también podemos llevarlas a cláusulas disyuntivas.
Definición:Una cláusula es una fbf en FNC que no tiene ningún
conectivo ^.
Para ello se convierte la fbf en FNC y luego cada
componente de la conjunción es una cláusula.
Algoritmo de
conversión de cláusulas
Ejemplo: 
Ejemplo de conversión de cláusulas
Las bases de
la resolución
El procedimiento de resolución es un proceso iterativo en el cual, en cada paso
se comparan dos cláusulas llamadas cláusulas padres produciendo una nueva cláusula que se ha inferido de ellas
llamada resolvente.
Las cláusulas padres deberán ser tales que
tengan ambas un mismo literal, una afirmada y la otra negado.
Ejemplo
