Cálculo de Predicados
Fundamentos
Inteligencia Artificial
Luis Villaseñor Pineda
Algunas características deseables

Verificabilidad


La representación debe permitirnos determinar el valor de verdad
de lo representado
Evitar la ambigüedad


No hay manera de encontrar una interpretación alterna
Cuidado: la vaguedad no es ambigüedad


Quiero comer comida china
Forma canónica

Nos ayude a evitar expresar el mismo contenido de diferentes
maneras
Representando el conocimiento


El lenguaje es el instrumento ideal pero su uso es
imposible (?) por medios automáticos
Estudiaremos otra representación y buscaremos los
medios para ir del conocimiento “real” a esta nueva
representación


Dado que el conocimiento “real” es fácilmente expresado por el
lenguaje ¿porqué no retomar las nociones de su estructura ?
Así que esta transformación la veremos como una traducción del
contenido del lenguaje (su contenido semántico) a otra
representación
Llevando del lenguaje a CP

Básicamente nos apoyaremos en la estructura
Predicado-Argumento



Capturan las relaciones de los conceptos subyacentes de los
constituyentes de una oración
Se dice algo de alguien
Ejemplos de esta estructura



Oración declarativa
Determinadores
Preposiciones
Ejercicio

restringe verbo sus un argumentos
Ejercicio

restringe verbo sus un argumentos


¿Cuáles son los argumentos?
¿Cuál es la relación existente entre ellos?
Ejercicio

restringe verbo sus un argumentos



¿Cuáles son los argumentos?
¿Cuál es la relación existente entre ellos?
Sin embargo, no se trata de una transferencia directa
es sólo una sugerencia

depende de nuestro objetivo final
Cálculo de Predicados

Cálculo de predicados de primer orden





Flexible
Bien entendido
Computacionalmente tratable
Satisface muchos de los requerimientos que vimos
Su principal atractivo: facilidad de representar el mundo

El mundo consiste de objetos, propiedades de los objetos y relaciones entre
objetos
Fundamentos

Término: el elemento más básico

Constantes – los objetos de nuestro dominio


Predicados – las relaciones o propiedades de los objetos



quiere(Luis, Cachivache)
Funciones – mapean de objetos a objetos


Cachivache
casa-de(Luis)
Variables
Predicados


Fórmula Atómica: predicados simples
Fórmula: predicados o predicados complejos
Términos

Constantes: objetos específicos del mundo (letras
mayúsculas o palabras en mayúsculas)



El mismo concepto que en un lenguaje de programación
Pedro - Puebla
Funciones: conceptos expresados por su descripción



Convenientes para cuando tenemos muchos objetos nombrados
y todos ellos con un concepto asociado común
La casa de Pedro - LaCasaDe(Pedro)
CUIDADO: tienen la apariencia de predicados pero son Términos
se refieren a objetos únicos
Términos

Variables: mecanismo para referirse a objetos del
mundo (usaremos las letras minúsculas)

Con ellas podemos realizar afirmaciones y realizar inferencias
sobre objetos sin tener una referencia a un objeto en particular
Predicados


Es el mecanismo para establecer relaciones entre
objetos
Son símbolos que se refieren a relaciones que se
presentan sobre un número fijo de objetos en un
dominio dado.


Tengo cinco pesos
O propiedades de un objeto

La luna es un satélite
Antes de seguir recordemos


Un predicado siempre tiene un valor de verdad
¿Estas expresiones tienen un valor de verdad?





La casa de Manuel
La casa de Manuel está hasta el quito infierno
El perro de mi amigo
La Zanahoria es un restaurante vegetariano
La Zanahoria es un buen restaurante vegetariano
Más ejemplos




Este lugar es un paraíso
Todos los perros me muerden
Está lloviendo a cántaros en Puebla
Mañana lloverá a cántaros en Puebla
Ejemplos ¿?


quiere(Luis, mascota-de(Luis))
quiere(Luis, mascota-de(Luis)) Y
quiere(Luis, auto-de(Pedro))
quiere((Luis, mascota-de(Luis) Y auto-de(Aurelio))
Regresando

Los predicados se pueden asociar a través de
conectores lógicos y calificar sus términos a través de
cuantificadores

Un predicado sin conectores ni cuantificadores es llamado
fórmula atómica
Semántica de FOPC


¿Cómo determinamos el valor de verdad de una
fórmula lógica?
Consideremos un enfoque de “base de datos” para
determinar el valor de verdad


Las fórmulas atómicas serán consideradas verdaderas si éstas
están presentes en la base de conocimiento o pueden inferirse de
otras fórmulas que están presentes en la base de conocimientos
Las interpretaciones de las fórmulas con conectores se basan en
el significado de sus componentes y el significado de los
conectores.
Variables y cuantificadores

Variables nos sirven para:



Referirse particularmente a un objeto anónimo
Referirse genéricamente a todos los objetos en la colección
Cuantificadores


Existencial – debe haber al menos una substitución que resulte
en una interpretación verdadera
Universal – debe ser verdadera bajo cualquier substitución
posible
Ejemplos

Todo restaurante vegetariano sirve comida
vegetariana


x RestauranteVegetariano(x)  Sirve(x,ComidaVegetariana)
La Zanahoria es un restaurante vegetariano

RestauranteVegetariano(Zanahoria)
Ejemplos ¿?

En que difieren estos dos ejemplos:


x Restaurante(x)  Sirve(x,ComidaVegetariana)
x Restaurante(x)  Sirve(x,ComidaVegetariana)
f. (gato(f)  gusta(Luis, f) )
 Cuidado:

gusta( Luis, f.gato(f) )
Inferencia


Conjunto de reglas que nos permiten llegar a concluir el valor
de verdad de un predicado en función de otros
Regla modus ponens
Ejemplo

Dado estos axiomas

Concluir:
Ejemplo
Forward chaining

Cada vez que agregamos un predicado a nuestra base
de conocimientos, usamos modus ponens para
disparar todas las reglas asociadas.



Al disparar las reglas el nuevo conocimiento generado es añadido
a nuestra base de conocimientos
Este proceso continua de forma exhaustiva
Siempre contamos con todo el conocimiento derivado
Backward chaining

Funciona a la inversa, en este caso tenemos un query
que deseamos probar



Primero revisamos si se encuentra en la base de conocimientos
Si no es el caso, buscamos por reglas de implicación presentes
en la base de conocimientos que involucren el query como
consecuente
Probaremos el consecuente si podemos probar el antecedente
Demostración

Lo que acabamos de hacer es una demostración

A partir de un conjunto de premisas concluimos un
nuevo predicado con ayuda de una regla de inferencia
Fórmula bien formadas
Objetos (A)
Variables (x)
Términos
Predicados (Vuela)
Formulas atómicas
(Vuela (x))
Formulas atómicas
Negación ()
Literales
Conectivos (,,,)
Formulas bien formadas
Cuantificadores (,)
x(Vuela(x)  Pájaro(x))
Demostración

Una secuencia de FBFs {w1,w2,…,wn} se
denomina demostración de wn a partir de un
conjunto de premisas (FBFs) sii cada wi de la
secuencia pertenece a las premisas, o puede ser
inferida utilizando las reglas de inferencia.
Reglas de inferencia
Reglas de inferencia (de remplazo)
Resolución

En particular es de interés para IA una regla de
inferencia llamada Resolución
Dado que B no puede ser tanto verdadera como falsa, el
valor de verdad recae sobre las otras premisas

o podemos verla como la transitividad de la implicación
La regla de Resolución

De forma más general tenemos

Donde dj = ai
Usando resolución
Para utilizar resolución

Es necesario dejar las formulas en una forma normal

O en un forma más estricta, una cláusula de Horn
Ejemplo
Si la casa de Juan es grande entonces es mucho trabajo mantenerla, a menos
que tenga servicio de limpieza y no tenga jardín.
grande(H) y casa(H,J)  muchotrabajo(H) o ( servico(H,A) y no( jardín(H)) )
no( grande(H) y casa (H,J)) o muchostrabajo(H) o (servicio(H,A) y no( jardín(H))
no (grande(H)) o no(casa(H,J)) o muchostrabajo(H) o (servicio(H,A) y no( jardín(H))
[no (grande(H)) o no(casa(H,J)) o muchostrabajo(H) o (servicio(H,A) ] y
[no (grande(H)) o no(casa(H,J)) o muchostrabajo(H) o no( jardín(H)) ]
[no (grande(H)) o no(casa(H,J)) o muchostrabajo(H) o (servicio(H,A) ]
[no (grande(H)) o no(casa(H,J)) o muchostrabajo(H) o no( jardín(H)) ]
no ( grande(H) y casa(H,J) ) o muchostrabajo(H) o (servicio(H,A)
no( (grande(H) y casa(H,J) y jardín(H) ) o muchostrabajo(H)
grande(H) y casa(H,J)  (muchostrabajo(H) o servicio(H,A))
grande(H) y casa(H,J) y jardín(H)  muchostrabajo(H)
Unificación


¿Qué hacer con las variables?
Necesitamos un mecanismo de substitución,


si tenemos variables debemos tener un modo de asociarlas a
individuos
Para ello tendremos una lista de ataduras


Una lista de ataduras es un conjunto de entradas s de la forma
v=e donde v es una variable y e es un objeto en nuestro dominio.
Mascota(X, luis) | s == Mascota(barril, luis) donde s ={X=barril}
Unificación

Dadas dos expresiones p y q, un unificador de p y q es una
lista de ataduras s tal que p|s = q|s


Q(z,V) ¿Cuál es su unificador?
Si s1 y s2 son dos listas de ataduras, s1 es más general que s2
si para cada expresión p, p|s2 es una instancia de p|s1




P(X,c) -
f(X)
f(X)
c(H,X)
s2={X=2}
s1={X=Y}
s1={X=f(G)}
s2={X=f(2)}
s1={H=3, X=f(G)} s2={X=f(2)}
La unificación es el proceso de búsqueda del unificador más
general para p y q.
Para calcular el mgu “most general unifier” para
dos expresiones p y q:

Si p o q son ya sea un objeto constante o una variable, entonces:




Si p=q, p y q unifican y podemos regresar {}.
Si alguna de las dos, p o q es una variable, regresamos el resultado de atar esa
variable a la otra expresión.
Si p es diferente de q, p y q no unifican, regresamos fracaso.
Si ni p ni q son objetos constantes o variables, entonces deben estar
compuestos de expresiones de algún tipo –conjunciones, disyunciones,
expresiones relacionales o funcionales. En ese caso, el tipo de la expresión
debe ser el mismo y deben ser de la misma aridad, en caso contrario
regresar fracaso. Para cada argumento p1...pn y q1...qn,


Sea s={}
Invoque el algoritmo recursivamente para encontrar el mgu de pi|s y qi|s. Añada las
nuevas ataduras a s añadiendo el nuevo mgu calculado a s, repita para cada
argumento i. Si fallamos al unificar pi|s y qi|s fracaso.
Ejemplos

Dé el mgu para p y q




p == X q == juan
p ==X q == casa_de(Juan)
p == gusta(X,chocolate) q == gusta(pepe, Y)
p == f(x,y) q == f(y,a)
Resolución c/unificación

Donde ai y dj unifican con el mgu 
Resolución con Unificación
Proposición
1
work(X)  F
2
big(H5) ٨ house(H5, P5)  work(H5)
3
big(H5) ٨ house(H5, P5)  F
4
T  house(house_of(P3), P3)
5
big(house_of(P3))  F
6
house(H4,P4) ٨ rich(P4)  big(H4)
7
Ataduras
Query negado
Resolve 1,2
X = H5
Resolve 3,4
H5 = house_of(P3),
P5 = P3
house(house_of(P3),P4) ٨ rich(P4)  F
Resolve 5,6
H4= house_of(P3)
8
rich(P3)  F
Resolve 7,4
P4 = P3
9
lawyer(P2)  rich(P2)
10
lawyer(P3)  F
Resolve 8, 9
P2=P3
11
T lawyer(Juan)
12
TF
Resolve 10, 11
P3=Juan
Para la forma normal con variables
Descargar

Diapositiva 1