Logica de Predicados
Logica de Predicados
Logica de Predicados
Representaci
on del Conocimiento
Francisco Jose Ribadas Pena
INTELIGENCIA ARTIFICIAL
5 Informatica
ribadas@uvigo.es
13 de noviembre de 2009
3.2.2 L
ogica de Predicados
B
C
A
sobre C B
sobre A C
sobre B A
sobre B C
sobre C A
sobre A B
...
sobre
sobre
sobre
sobre
...
...
...
C
C
B
B
B
A
A
C
libre
libre
libre
libre
C
C
B
B
(a) SINTAXIS
ELEMENTOS
T
erminos: Representan objetos del dominio
Constantes: Representan un objeto individual en concreto
n: cadenas de caracteres, comienzan en may
notacio
usculas
Ejemplos: Juan, M i coche, ...
Funciones: Representan (implcitamente) un objeto individual que
esta relacionado con los n objetos que participan en la funci
on
n: smbolo de funci
notacio
on (cadena, comienza con Mays.)
con aridad n + n argumentos (terminos) entre parentesis
Ejemplos: P adre de(Juan), Hijo de(P edro, Ana), Coseno(45)...
Variables:
Representan objetos sin indicar cuales
referirse a un objeto especfico no identificado
Uso:
referirse a un conjunto de objetos
n: cadenas de caracteres en min
notacio
usculas
Ejemplos: x, y, padre, hijo, ...
Predicados: Representan una propiedad de un termino (si aridad 1)
o relaciones entre k terminos (si aridad k > 1)
n: cadenas de caracteres +
notacio
k terminos (variables, constantes, funciones) entre parentesis
Atomos:
formulas bien formadas (f.b.f.) compuestas por un u
nico
predicado
Literales: Atomo
o negaci
on de un atomo.
Ejemplos: Asesina(Juan, x), Es alto(Juan),
V ive con(Juan, P adre de(Juan)), ...
FORMULAS
BIEN DEFINIDAS (oraciones l
ogicas)
Formadas a partir de atomos (=predicados) aplicando conectivas
logicas y cuantificadores
Conectivas: , , , ,
IDEM que en logica proposicional
Ejemplos:
Hermano(Juan, Luis)Hijo(Luis, P edro) T io(Juan, P edro)
(b) SEMANTICA
Representamos un mundo donde hay:
Un no infinito de objetos individuales representados por smbolos de
constantes y variables
Pueden ser entidades concretas (personas, cosas) o abstractas
(n
umeros, eventos)
Un no infinito de objetos definidos en funci
on de otros objetos,
representados por smbolos de funci
on
Relaciones entre los objetos del dominio, representadas por smbolos
de predicado
Si la aridad es 1, se habla de propiedades de objetos
INTERPRETACIONES:
Una interpretacion establece las relaciones anteriores entre los smbolos de la logica y los elementos del mundo real
asocia a las constantes objetos del mundo
asocia a las funciones relaciones funcionales entre objetos
asocia a los predicados relaciones entre objetos
Mas compleja que en logica de proposiciones
SATISFACTIBILIDAD
Asignaci
on de variables(A): Funci
on que asina a objetos de U con
las variables de una f.b.f.
Los atomos (predicados) pueden tener variables. S
olo se pueden
asignar valores de verdad a una f
ormula at
omica si todas sus
variables estan asignadas
El valor de verdad de un atomo con todas sus variables asignadas,
es verdadero si y solo si los objetos del dominio cumplen la relaci
on
que representa ese predicado
el valor de verdad de una interpretacion i depende de la asignacion de variables
considerada
interpretaci
on (i)
La asignacion de verdad es relativa a:
asignac. de variables (A)
nota: Una f.b.f. puede ser V o F en una misma conceptualizaci
on
dependiendo de la interpretaci
on y la asignaci
on de variables
Def.:sactisfactibilidad
En una conceptualizacion, una interpretaci
on i y una asignaci
on de
variables A, satisfacen una f.b.f. si hacen V a esa f.b.f.
Notacion: |=iA ( se satisface para i y A)
MODELOS
Una interpretacion i es modelo de (respectivamente de ) si
se satisface con esa i para todas las posibles asignaciones de
variables
Notaci
on: |=i
modelo mnimo: Ning
un subconjunto de esa interpretaci
on es un
modelo
n: Inaplicable tabla de verdad exhaustiva como mecaconclusio
nismo de evaluacion
LOGICA
EQUIVALENCIA E IMPLICACION
1 y 2 son l
ogicamente equivalentes si sus valores de verdad son
identicos bajo todas las interpretaciones y asignaciones de variables.
1 2
Implicaci
on l
ogica
|= si y solo si interpretacion i y asignacion A para las
cuales se satisface , tambien se satisface
|= sii |=iA i A
Equivalencias Logicas (sobre cuantificadores)
(x ) x
Leyes de DeMorgan:
(x ) x
conjuncion infinita, disyuncion infinita
x y
Renombrado de variables:
x y
xy yx x, y
Ordenacion cuantificadores:
xy yx x, y
SUSTITUCION
v
sust({v/g}, )
Ejemplo: Usando la sustituci
on {x/BillGates}
x T ieneDinero(x) EsRico(x)
T ieneDinero(BillGates) EsRico(BillGates)
v sust({g/v}, )
Ejemplo: Usando la sustituci
on {Juan/x}
Casados(Juan, Ana)
x Casados(x, Ana)
hay alguien casado con Ana
EN LOGICA
RESOLUCION
DE PREDICADOS
Unificaci
on
Procedimiento sintactico mediante el cual, dadas dos f.b.f. y
se encuentra una sustituci
on que aplicada sobre ellas, ambas
resultan identicas, esto es
10
PROCEDIMIENTO DE REFUTACION
Al igual que en log. proposicional, el conocimiento tiene que estar
representado en forma de clausulas (F.N.C.)
Conjuncion de disyunciones (clausulas)
S
olo hay cuantificadores universales
Paso a Forma Normal Conjuntiva
1. Eliminar implicaciones
Usar relaciones:
( ) ( )
2. Reducir ambito de las negaciones 8
< x x
Usar DeMorgan + doble neg.:
x x
:
3. Independizar variables cuantificadas (renombrar variables ligadas)
Asegurar que cada smbolo de variable este ligado a un u
nico
cuantificador
Ejemplo: xP (x) xQ(x) x1P (x1) x2Q(x2)
4. Eliminar cuantificadores existenciales (skolemizaci
on)
Las ocurrencias de variables cuantificadas existencialmente se
sustituyen por:
a) Una constante (Sk ) no presente en la f.b.f. si el aparece
al principio de la expresi
on
xP (x) Q(x)
P (Sk ) Q(Sk )
{x/Sk }
b) Una funcion (Sk (...)) con tantos argumentos como cuantificadores universales () haya antes del que cuantifica la
variable
xyzP (x)Q(y, z)
11
( ) = ( ) ( )
7. Abandonar cuantificadores universales
8. Renombrar variables (si es necesario) para que ninguna variable
aparezca en mas de una clausula
Ejemplo 1:
Pasar {xP (x)} {xyz[P (x, y, z) wR(x, y, z, w)]} a FNC
1.
2.
3.
4.
5.
6.
7.
8.
12
MEDIANTE RESOLUCION
(como en l
REFUTACION
og. proposicional)
1. Convertir f.b.f. de a FNC
2. Negar f.b.f. a demostrar y convertir a FNC
3. Unir clausulas resultantes de y en
4. Aplicar de forma exhaustiva la regla de resoluci
on para l
ogica de
predicados sobre .
Seleccionar un par de clausulas con dos atomos p y q tales que
unifiquen con = m.g.u.(p, q)
A
nadir resolvente a
Parar si:
Se generar la clausula vaca (hay contradiccion)
Se verifica: |=
No hay resolventes nuevos (no contradiccion)
Se verifica: |=
/
nota: Ademas de comprobar si una f.b.f. es consecuencia l
ogica de
o no, la refutacion mediante resoluci
on permite responder preguntas
mediante las sustituciones que dan lugar a la clausula vaca.
13
Asterix es un galo
Los romanos que son amigos de alg
un galo odian a C
esar
Asterix ayud
o a Marco
Marco es amigo de quien le ayuda
Quien odia a alg
un romano, lucha contra
el
Marco es romano
14
PROPIEDADES PROCEDIMIENTO DE REFUTACION
Refutacion mediante resoluci
on en l
ogica de predicados es s
olida
(correcta)
Si se llega a la clausula vaca ( `REFUTACION) entonces |= .
Refutacion mediante resoluci
on en l
ogica de predicados es completa
Si |= , el procedimiento de refutacion por resolucion generara la clausula vaca
Refutacion mediante resoluci
on en l
ogica de predicados no es decidible
Si |=
/ el procedimiento de refutacion mediante resolucion
puede no terminar (bucle infinito)
Siempre parara si |= , pero puede no parar si /|=
No existe un metodo que nos pueda decir siempre si |=
/
Se dice que la logica de proposiciones es semidecidible
Se puede determinar |= , pero a veces no se puede
probar |=
/
soluciones:
Renunciar a la solidez o a la completitud
Utilizar un lenguaje de representacion menos expresivo
clausulas de Horn
15
CLAUSULAS
DE HORN
Todas las variables estan cuantificadas universalmente ( implcito)
Clausulas que tienen como maximo un literal positivo (sin negar)
Todas las variables se suponen cuantificadas universalmente
Clausulas de Horn pueden escribirse como implicaciones
Consecuente: literal atomico positivo
Antecedente: conjuncion de literales positivos (DeMorgan)
p1 p2 ...pn q p1 p2 ... pn q
Distinguimos
reglas: q p1 p2 ... pn
hechos: h
objetivos: o1 o2 ... ok
Regla de resoluci
on para clausulas de Horn
Si b y di unifican mediante = unif icador(b, di), inferimos:
b a1 a2 ... am
( b a1 ... am )
c d1 d2 ... dn
( c d1 ... dn )
sust(, (c d1 ... di1 a1 ... am di+1 ... dn ))
16
3.2.4 Representaci
on del conocimiento en l
ogica de
predicados
Fases generales en
base de conocimientos
la
construcci
on
utilizaci
on
de
una
1. Conceptualizaci
on
Decidir que conceptos son relevantes en el dominio
identificar objetos, propiedades y relaciones relevantes
Definir un vocabulario para asignar smbolos a los conceptos
relevantes
vocabulario de predicados, funciones y constantes
Se tratara de construir una ontologa: conjunto, normalmente
estructurado, de terminos relevantes en un dominio
2. Codificaci
on
Traduccion, de acuerdo al vocabulario, de todo el conocimiento
considerado de interes a su representaci
on en l
ogica de predicados
Se construyen los axiomas del dominio (conjunto de f.b.f. )
Formulas que se consideran ciertas en el dominio actual
(Base de Conocimiento)
17
3. Actualizaci
on del conocimiento y consulta
Durante la ejecucion del sistema inteligente
Se consulta/desencadena el procedimiento de inferencia
(modus ponens, resoluci
on, ...) para obtener respuestas
Distintas alternativas:
Sistemas que solo usan modus ponens, bien de forma progresiva (razonamiento hacia adelante) o regresiva (razonamiento hacia atras)
Sistemas que solo usan resoluci
on y refutaci
on
Etc,...
Se actualiza el conocimiento
introducir nuevos hechos
modificar hechos existentes
Sus valores de verdad deben estar respaldados por el mundo
real
Pasos comunes a los demas mecanismos de representaci
on del conocimiento
En general es un proceso largo, que se suele hacer de forma iterativa
se ampla y refina de forma iterativa la representacion
Suele necesitar la intervencion de expertos del dominio (entrevistas,
etc...)
18