Download p ⇒ q

Agentes que razonan de
forma Lógica
M.C. Juan Carlos Olivares Rojas
[email protected]
[email protected]
@jcolivares
http://antares.itmorelia.edu.mx/~jcolivar
Abril, 2010
Outline
Representación del Conocimiento
Lógica de Proposiciones
Lógica de Predicados
Deducción Automática
Outline
Sistemas de Deducción
Sistemas de Reacción
Encadenamiento Progresivo y Regresivo
Modelamiento Cognitivo
Modelos para la Resolución de Problemas
Representación del Conocimiento
• El conocimiento debe estar expresado en un
lenguaje simbólico para que pueda ser
reconocido por una computadora o ‘agente’.
• Los agentes pueden consultar a la base de
conocimientos para resolver problema o bien
agregar nuevos conocimientos.
• Los agentes pueden obtener esta nueva
información a través de la inferencia lógica.
Representación del Conocimiento
• Inicialmente el agente cuenta con unos
conocimientos
básicos
llamados
antecedentes o hechos.
• Se cuenta con una serie de reglas que
definen la forma de deducir conocimiento.
• El agente pregunta a estas reglas y hechos
para poder razonar que opción le conviene
más ejecutar.
El Juejo del Wumpus
Percepciones: (4 sensores)
{Hedor, Brisa, Resplandor, Nada}
El agente no percibe su situación
Acciones:
Ir hacia adelante, girar izda/dcha 90º
Agarrar (estando en la casillla)
Disparar (sólo una flecha)
Objetivo: salir con el oro lo antes posible
1000 ptos: salir con el oro
1 pto penaliza cada acción. Penaliz. Máxima: 10000 ptos
Lógica de Proposiciones
• La sintaxis nos indica cuáles son los
enunciados que se pueden construir.
• Los enunciados atómicos se componen de
una sola proposición.
• Una proposición tiene un solo valor de
verdad: Verdadero o Falso.
Lógica de Proposiciones
• Los enunciados complejos se forman a partir
de enunciados más simples y el empleo de
conectivos lógicos.
• Los Conectivos Lógicos son cinco:
– NO (~) también conocida como Negación.
– Y (^) también conocida como Conjunción.
– O (v) también conocida como Disyunción.
– Implicación (⇒) también conocida como
Condicional.
Lógica de Proposiciones
• Las expresiones que contienen conectivos
lógicos se interpretan siguiendo el orden de
precedencia que corresponde al mostrado en
la tabla anterior.
• Por ejemplo: ~P ^Q v R ⇒ S equivale a:
• (~(P) ^(Q v R)) ⇒ S
• Además, se emplean los paréntesis para
evitar ambigüedades.
Lógica de Proposiciones
• La semántica nos define las reglas que
permiten determinar el valor de verdad de un
enunciado respecto de algún modelo.
• Con dos símbolos proposicionales existen 4
modelos posibles para cada uno de los 5
conectivos lógicos, ¿Cómo quedarían las
tablas de verdad?
Lógica en Wumpus
• Regresemos al mundo del Wumpus para
visualizar la construcción de la base de
conocimiento.
• Notación:
– Bij indica que hay brisa en la celda (i,j).
– Pij indica que hay un pozo en la celda (i,j).
• A partir de un conocimiento inicial:
– E1: ~P11
Lógica en Wumpus
• Cuando hay brisa en una casilla implica que
en una casilla contigua hay un pozo:
• E2: B11 ⇔ P12 v P21
• Ahora agregamos la primera percepción, no
se percibe brisa en la celda (1,1): E3: ~B11
• ¿Cómo relacionar los enunciados 2 y 3 para
obtener nuevo conocimiento?
Lógica de Proposiciones
• Cuando los resultados de una Tabla de
Verdad son todos verdaderos, a esa
proposición
compuesta
se
le
llama
Tautología. Como ejemplo tenemos a: (p v
~p)
• Cuando los resultados de una Tabla de
Verdad son todos falsos, a esa proposición
compuesta se le llama Contradicción. Como
ejemplo tenemos a: (p ^ ~p)
Lógica de Proposiciones
• Básicamente
la
inferencia
es
implementación de una implicación.
la
• Los enunciados conocidos como verdaderos
forman parte del antecedente.
• El consecuente es un nuevo enunciado cuya
veracidad se desprende de los anteriores.
Simbólicamente se representa así:
• antecedente :: consecuente
Lógica de Proposiciones
• La equivalencia lógica se presenta cuando
dos enunciados α y β tienen los mismos
valores de verdad para el mismo conjunto de
modelos.
• A continuación mostramos una tabla con las
equivalencias lógicas más comunes:
• Doble Negación: ~( ~p ) ≡ p
Lógica de Proposiciones
• Leyes Conmutativas
(pvq)≡(qvp)
(p^q)≡(q^p)
• Leyes Asociativas
(pvq)vr≡pv(qvr)
(p^q)^r≡p^(q^r)
Lógica de Proposiciones
• Leyes Distributivas
pv(q^r)≡(pvq)^(pvr)
p^(qvr)≡(p^q)v(p^r)
• Leyes de Idempotencia
(pvp)≡p
(p^p)≡p
Lógica de Proposiciones
• Leyes de DeMorgan
~( p v q ) ≡ ~p ^ ~q
~( p ^ q ) ≡ ~p v ~q
• Leyes de Identidad
( p v ~p ) ≡ t
( p ^ ~p ) ≡ f
(pvf)≡p
(pvt)≡t
Lógica de Proposiciones
• Leyes de Identidad
(pvf)≡f
(pvt)≡p
• Leyes de la Implicación
(p ⇔ q) ≡ (p ⇒ q) ^ (q ⇒ p)
(p ⇒ q) ≡ (~q ⇒ ~p)
(q ⇒ p) ≡ (~p ⇒ ~q)
(p ⇒ q) ≡ (~p v q)
Lógica de Proposiciones
• Reglas de Inferencias
• La siguiente implicación lógica se llama
Modus Ponens y corresponde a la siguiente
inferencia:
p ^ ( p ⇒ q ) :: q
• Ejemplo:
p: Estudio
p ⇒ q: Si estudio aprobaré Matemáticas
Lógica de Proposiciones
• La siguiente implicación lógica se llama
Modus Tollens y corresponde a la siguiente
inferencia:
( p ⇒ q ) ^ ~q :: ~p
• Ejemplo:
p ⇒ q: Si estudio apruebo Matemáticas
~q: No aprobé Matemáticas
~p: Entonces, no Estudié
Lógica de Proposiciones
• La siguiente implicación lógica se llama
Silogismo Hipotético y corresponde a la
siguiente inferencia:
( p ⇒ q ) ^ ( q ⇒ r ) :: ( p ⇒ r )
• Ejemplo:
p ⇒ q: Si estudio apruebo Matemáticas
q ⇒ r: Si apruebo Matemáticas me regalan un
auto
p ⇒ r: Entonces, Si estudio me regalan un auto
Lógica de Proposiciones
• La siguiente implicación lógica se llama
Silogismo Disyuntivo y corresponde a la
siguiente inferencia:
( p v q ) ^ ~p :: q
• Ejemplo:
p v q: Hay que estudiar Francés o Alemán
~p: No estudio Francés
q: Entonces, Estudio Alemán
Lógica de Proposiciones
• La simplificación conjuntiva consiste en
eliminar uno de los términos de una
conjunción:
( p ^ q ) :: q o también: ( p ^ q ) :: p
• Por el otro lado, la amplificación disyuntiva
permite agregar un nuevo término:
p :: ( p v q )
Lógica en Wumpus
• Se tiene que:
• E2: B11 ⇔ P12 v P21
• E3: ~ B11
• Por
lo
que
tenemos
el
siguiente
razonamiento:
• E4: (B11 ⇒ (P12 v P21)) ^ ((P12 v P21) ⇒
B11)
• E5: ((P12 v P21) ⇒ B11)
• E6: ~B11 ⇒ ~(P12 v P21)
Lógica en Wumpus
• Del razonamiento anterior concluimos que no
hay un pozo en la casilla (1,2) ni en la (2,1).
• Ahora veamos el razonamiento cuando el
agente llega a la celda (1,2).
• E9: ~B12
• E10: B12 ⇔ P11 v P13 v P22
• E12: ~P22
Lógica en Wumpus
• Concluimos que no hay pozo ni en la casilla
(1,3) ni en la (2,2).
• E11: ~P13
• E12: ~P22
• Pero cuando el agente visitó la celda (2,1)
percibió una brisa:
• E13: B21
• E14: B21 ⇔ P11 v P31 v P22
Lógica en Wumpus
• Dado que ya verificamos que no hay pozo en
las celdas (1,1) y (2,2), resulta evidente la
conclusión que:
• E15: P31
• Es conveniente que nuestra base de
conocimiento esté basada solamente en
conjunciones y disyunciones.
Lógica Proposicional
• Cualquier enunciado compuesto puede ser
transformado a uno equivalente que esté en
la FNC
• La Forma Normal Conjuntiva es la conjunción
de n disyunciones de k elementos:
( p11 v … v p1k ) ^ … ^ ( pn1 v … v pnk )
Lógica Proposicional
• A continuación se describe un procedimiento
para convertir a nuestra FNC:
• Eliminar ⇔ usando la equivalencia:
(p ⇔ q) ≡ (p ⇒ q) ^ (q ⇒ p)
• Eliminar ⇒ usando la equivalencia:
(p ⇒ q) ≡ (~p v q)
Lógica Proposicional
• Simplificar ~ usando las equivalencias:
~( ~p ) ≡ p
~( p v q ) ≡ ~p ^ ~q
~( p ^ q ) ≡ ~p v ~q
• Finalmente, aplicar la ley distributiva donde
sea necesario.
pv(q^r)≡(pvq)^(pvr)
Lógica Proposicional
• E2: B11 ⇔ (P12 v P21)
(B11 ⇒ (P12 v P21)) ^ ((P12 v P21) ⇒ B11 )
(~B11 v P12 v P21) ^ (~(P12 v P21) v B11 )
(~B11 v P12 v P21) ^ ((~P12 ^ ~P21) v B11 )
(~B11 v P12 v P21) ^ (~P12 v B11) ^ (~P21 v
B11)
Lógica Proposicional
• Para demostrar que una implicación BC :: α
es válida, se utiliza el método de reducción al
absurdo.
• Esto es, probar que su negación: BC ^ ~α es
una contradicción.
• Para ello se lleva a la FNC y luego se prueba
que es equivalente a una cláusula vacía.
Lógica Proposicional
• Probar que: E2 ^ E4 :: ~P12.
• (B11 ⇔ (P12 - P21)) ^ ~B11 :: ~P12
• Se convierte a FNC:
• (~B11 v P12 v P21) ^ (~P12 v B11) ^ (¿P21 v
B11) ^ ~B11 :: ~P12
Lógica Proposicional
• Y para probar por reducción al absurdo,
tenemos la negación:
• (~B11 v P12 v P21) ^ (~P12 v B11) ^ (~P21 v
B11) ^ ~B11 ^ P12
• El proceso de simplificación funciona como
sigue:
• Si tomamos los primeros dos paréntesis,
observamos que contienen a: ~B11 y B11,
Lógica Proposicional
• Como no pueden ser ambos verdaderos
simultáneamente, entonces, o (P12 v P21) o
bien (~P12 ) son verdaderos, lo que se
reduce a la siguiente expresión:
• (P12 v P21 v ~P12)
• Como (P12 v ~P12 ) es una tautología, la
expresión anterior se reduce a: (P21)
Lógica Proposicional
• Similarmente, los dos paréntesis siguientes,
también contienen a: ~B11 y B11, por lo que
la
• expresión simplificada queda: (~P21)
• Como ambas no pueden ser verdaderas, la
conjunción resulta en una expresión nula.
Ejercicios
• (p⇒q)^(q⇒r)
• p^(p⇒q)
• ((p ^ q) ⇔ (p v ~q))
• ((~(p ⇒ q) ^ r ) v ~(p ⇔ ~q))
Lógica de Predicados
• Hay que aprovechar la característica
declarativa y la composicionalidad de la
lógica proposicional. Para ello definimos dos
tipos de elementos:
• Los objetos (Agente, Flecha, Wumpus, Pozo)
• Las relaciones entre ellos, generalmente
vinculadas por un verbo.
• El Agente lanzó una Flecha
Lógica de Predicados
• Las relaciones unitarias también se conocen
como Propiedades y se vincula un objeto con
una característica por el verbo SER:
• La Pelota es roja.
• Las Funciones son un tipo especial de
relación que involucra un solo objeto y
devuelven un valor:
• El padre de
• Uno más que
Lógica de Predicados
• Uno sumado a Dos es igual a Tres
– Objetos: Uno, Dos y Tres.
– Relación: es igual a.
– Función: sumado a; el resultado es un objeto,
llamado: Uno sumado a Dos.
• Las Casillas que rodean al Wumpus apestan.
– Objetos: Casillas y Wumpus.
– Relación: que rodean al.
– Propiedad: apestan.
Lógica de Primer Orden
• La lógica de primer orden se construye sobre:
Hechos, Objetos y Relaciones.
• La lógica de primer orden es universal porque
puede expresar cualquier cosa que pueda ser
programada.
• El dominio de un modelo es el conjunto de
objetos que contiene.
Lógica de Primer Orden
• Una relación binaria es un conjunto de pares
ordenados.
• Por ejemplo, si Hugo, Paco y Luis son
hermanos se denota así:
• H = { (Hugo, Paco), (Hugo, Luis), (Paco,
Luis),
• Por ejemplo, si Pepe es el padre de Hugo,
Paco y Luis, tenemos entonces:
Lógica de Primer Orden
• Padre_de(Hugo) → Pepe
• Padre_de(Paco) → Pepe
• Padre_de(Luis) → Pepe
• Padre_de(Pepe)  ?
• A continuación se muestra la gramática de la
LPO en BNF.
Lógica de Primer Orden
• Los símbolos se agrupan en tres clases:
• Símbolos de constante, que representan a
los Objetos. Cada símbolo constante nombra
a exactamente un objeto en el mundo, no
todos los objetos necesitan tener nombres y
algunos pueden tener más de un nombre.
• Ejemplo: Juan, Casa, Wumpus.
Lógica de Primer Orden
• Símbolos de predicado, que representan a
las Relaciones. Ejemplos: Vecino, Hermano,
…
• Símbolos de función. Ejemplos: Coseno,
Padre_de, Oficina_de
• Los símbolos de predicado y de función
tienen una Aridad que establece el número
de argumentos.
Lógica de Primer Orden
• 〈Enunciado〉 → 〈Sentencia Atómica〉
(〈Enunciado〉〈Conector〉〈Enunciado〉)
〈Cuantificador〉〈Variable〉…〈Enunciado〉
~〈Sentencia〉
|
|
|
• 〈Sentencia
Atómica〉
→
〈Predicado〉(〈Término〉…) | 〈Término〉 =
〈Término〉
• 〈Término〉
→
〈Función〉(〈Término〉…)
|
Lógica de Primer Orden
•
•
•
•
〈Conector〉 → . | - | ⇔ | ⇒
〈Cuantificador〉 → ∀ | ∃
〈Constante〉 → Martin | 59302 | Gato | X | …
〈Variable〉 → a | x | s | …
• 〈Predicado〉 → Previo | Gusta | Llueve | Falla
|…
• 〈Función〉
→
Padre_de
|
Cabello_de
|
Lógica de Primer Orden
• Un término es una expresión lógica que se
refiere a un objeto.
– Los símbolos constantes son términos
– Los símbolos de función son términos.
– Las variables también son términos.
• Una sentencia atómica está formada por un
símbolo predicado seguido por una lista entre
paréntesis de términos.
Lógica de Primer Orden
• Por ejemplo: Hermano(Roberto,Juan) indica
que Roberto es el hermano de Juan.
• Las sentencias atómicas pueden tener
argumentos que son términos complejos:
Casado(Padrede(Roberto),Madrede(Juan))
• Se pueden usar conectores lógicos para
construir sentencias más complejas.
Lógica de Primer Orden
• Ejemplo:
• Hermano(Roberto,Juan)
Hermano(Juan,Roberto)
∧
• Es verdadero si Juan y Roberto son
hermanos, pues la relación es simétrica.
• Los cuantificadores nos permiten expresar
propiedades de colecciones de objetos.
Lógica de Primer Orden
• Hay dos cuantificadores en lógica de primer
orden: universal y existencial.
• Cuando un enunciado abarca a todos los
posibles valores del dominio de una variable,
entonces se emplea el Cuantificador
Universal, que se denota por ∀. El cual se
enuncia con frases similares a: “Para todos
…”, “Todos …”
Lógica de Primer Orden
• Esta proposición es falsa si al menos un solo
valor de la variable no satisface al enunciado.
• La representación simbólica es:
• ∀x Gato(x) ⇒ Mamifero(x)
• Sin embargo, mucha gente cae en el error de
interpretarla como:
• ∀x Gato(x) ∧ Mamifero(x)
Lógica de Primer Orden
• Aparentemente son equivalentes, pero esta
segunda forma es más fuerte que la anterior,
pues la primera será verdadera cuando el
antecedente es falso (v.gr. x es un perro)
• Cuando un enunciado indica que al menos
uno de los posibles valores del dominio de
una variable, entonces se emplea el
Cuantificador Existencial, el cual se denota
por ∃.
Lógica de Primer Orden
• Y se enuncia con frases similares a: “Hay ...”
o “Existe ...” o “Para algunos ...”
• Ejemplo: En mi clase hay mujeres.
• Esta proposición es falsa si no existe ningún
valor de la variable que satisfaga al
enunciado.
• La representación simbólica es:
• ∃x Alumnodemiclase(x) ∧ Mujer(x)
Lógica de Primer Orden
• Semejante al caso anterior, mucha gente cae
en el error de interpretarla como:
• ∃x Alumnodemiclase(x) ⇒ Mujer(x)
• Pero esta segundo enunciado es más débil
que el anterior y sería verdadero para los
estudiantes que no están en mi clase.
• Se pueden realizar afirmaciones
complejas si se anidan cuantificadores.
muy
Lógica de Primer Orden
• Sin mezclar tipos de cuantificadores,
podemos decir cosas como:
• ∀x,y Hermano(x,y) ⇒ Hermano(y,x)
• También podemos mezclar cuantificadores,
• ∀x ∃y Buenopara(x,y) “Todos somos buenos
para alguna cosa"
• ∃y ∀x Buenopara(x,y) “Alguien es bueno para
todo"
Lógica de Primer Orden
• Se pueden cambiar
mediante la negación.
los
cuantificadores
• Considerar la sentencia:
• ∀x ~Gusta(x,Verduras) “Para todo x, x no le
gustan las verduras."
• Es equivalente a decir: “No existe un x que le
gusten las verduras.“
• ~∃x Gusta(x, Verduras)
Lógica de Primer Orden
• Similarmente, los siguientes enunciados son
equivalentes:
• ∃x P = ~∀x ~P
• ∀x P = ~∃x ~P
• ~∀x P = ∃x ~P
• ∀x ~P = ~∃x P
• Con frecuencia el símbolo de igualdad se
incluye como un símbolo especial.
Lógica de Primer Orden
• Ejemplo: Padre(Juan) = José
• Afirmar que el objeto que es padre de Juan
es el mismo que el objeto José.
• Los axiomas capturan los hechos básicos
acerca de un dominio. Ejemplos:
• ∀x,y Padre(x,y) ⇔ Hijo(y,x)
• ∀x,y Abuelo(x,y) ⇔ ∃z Padre(x,z) . Padre(z,y)
Lógica de Primer Orden
• Algunos axiomas son considerados como
Definiciones.
• Los axiomas son luego usados para probar
teoremas.
• FOL en Wumpus:
• El primer paso es definir la interface entre el
agente y el mundo.
FOL Wumpus
• Un ejemplo de percepción sería:
• Percepción([Hedor,Brisa,Brillo,Nada,Nada],5)
• El vector de percepciones contiene 5
elementos que son: Hedor, Brisa, Brillo,
Golpe con un muro y Grito. Además incluye
un sexto elemento para el tiempo.
• Las acciones posibles del agente pueden ser
las siguientes:
FOL Wumpus
•
•
•
•
•
Girar(Derecha)
Girar(Izquierda)
Avanzar
Disparar
Tomar
• Para determinar cuál es la mejor acción, el
agente realiza una petición como esta:
• PREGUNTAR(BC, ∃x MejorAcción(x,5))
FOL Wumpus
• Esta petición retornará una lista de acciones
posibles, tal como: {a/Tomar}.
• Antes de realizar esa acción, el agente
deberá DECIR a la base de conocimiento su
decisión de hacer la acción de Tomar:
• DECIR(BC, Acción(5)=Tomar)
• Reglas de diagnóstico: nos llevan de los
efectos observados a sus causas.
FOL Wumpus
• Por ejemplo: si una casilla tiene brisa
significa que una casilla adyacente tiene un
pozo.
• ∀x Brisa(x) ⇒ ∃y Adyacente(y,x) ∧ Pozo(y)
• Reglas Causales: reflejan conclusiones
respecto de las percepciones y sus causas.
Por ejemplo: un pozo en una casilla provoca
brisa en todas las casillas adyacentes.
• ∀y Pozo(y) ⇒ [∀x Adyacente(x,y) ⇒ Brisa(x)]
Lógica de Primer Orden
• La Ingeniería del Conocimiento es un
proceso general para la construcción de una
base de conocimiento. A continuación se
describen los pasos de este proceso:
•
•
•
•
Identificación de la tarea.
Recopilación del conocimiento.
Decidir el vocabulario.
Codificar el conocimiento.
Deducción Automática
• Para el hecho: Contrata(Telmex,Toño),
podemos construir índices para las siguientes
peticiones:
• Contrata(Telmex,Toño) ¿Contrata Telmex a
Toño?
• Contrata(x,Toño) ¿Quién Contrata a Toño?
• Contrata(Telmex,y) ¿A quién Contrata
Telmex?
• Contrata(x,y) ¿Quién Contrata a quién?
Deducción automática
• El primer paso consiste en transformar los
enunciados en sentencias lógicas.
• Posteriormente se aplican las técnicas
anteriores para convertirlas en un conjunto de
cláusulas positivas de primer orden.
• Luego se encadenan esos conocimientos
para obtener nuevos enunciados.
Deducción Automática
• Pasar a FNC la siguiente base de
conocimientos:
1.Asterix es un galo
2.Los romanos que son amigos de algún galo
odian a César
3.Asterix ayudó a Marco
4.Marco es amigo de quien le ayuda
5.Quien odia a algún romano, lucha contra él
6.Marco es romano
Deducción Automática
1. Asterix es un galo
• galo(Asterix) (en FNC)
1. Los romanos que son amigos de algún galo
odian a César
• ∀x [romano(x) . (∃y galo(y) . amigo(x, y)) ⇒
odia(x,Cesar)]
Deducción Automática
• Reemplazando la cláusula existencial:
• ∀x [romano(x) . (galo(G) . amigo(x, G)) ⇒
odia(x,Cesar)]
3.Asterix ayudó a Marco
• ayuda(Asterix,Marco) (en FNC)
4.Marco es amigo de quien le ayuda
• ∀x [ayuda(x,Marco) ⇒ amigo(Marco, x)]
Deducción Automática
5. Quien odia a algún romano, lucha contra él
• ∀x ∃y [romano(y) . odia(x, y) ⇒ lucha(x, y)]
• Reemplazando la cláusula existencial:
• ∀x [romano(R) . odia(x, R) ⇒ lucha(x, R)]
6. Marco es romano
• romano(Marco) (en FNC)
Deducción Automática
• Los Miembros del equipo de tenis son: Juan,
Sara, Beto y Elena.
• Juan está casado con Sara.
• Beto es hermano de Elena.
• El cónyuge de un miembro del equipo
también es miembro del equipo.
Deducción Automática
• La última reunión fue en casa de Juan.
• Representar los enunciados anteriores en
lógica de predicados. Demostrar que:
• La última reunión fue en casa de Sara.
• Elena no está casada.
• Agregue los hechos que necesite para las
Deducción Automática
• A Paco le gustan los cursos fáciles.
• Los cursos de Física son difíciles.
• Los cursos de Humanidades son fáciles.
• El curso de
Humanidades.
Ética
es
del
área
de
Deducción Automática
• A Beto le gusta la comida italiana.
• En un restaurante hay comida mexicana a no
ser que se anuncie explícitamente lo
contrario.
• En “La Conchita” no anuncian que tipo de
comida sirven.
Deducción Automática
• A las personas no les gusta ir a restaurantes
donde sirven comida que no es de su
preferencia.
• ¿Se puede concluir que a Beto no le gusta ir
a “La Conchita”?
Deducción Automática
• Formaliza los siguientes hechos:
• Todo dragón está feliz si todos sus hijos
pueden volar.
• Los dragones verdes pueden volar. Un
dragón es verde si es hijo de al menos un
dragón verde.
• Demuestra por resolución que la conjunción
de los hechos anteriores implica que:
• Todos los dragones verdes son felices.
Deducción Automática
• Considere las siguientes relaciones:
•
•
•
•
•
•
Feliz(x) para x es feliz.
Volar(x) para x puede volar.
Verde(x) para x es verde.
Dragón(x) para x es dragón
Rojo(x) para x es rojo.
Hijo(x,y) para x es hijo de y.
Sistemas de Deducción
• Los sistemas de deducción pueden variar
dependiendo del problema pero en general
se utiliza el método de resolución visto en la
unidad pasada.
• Los lenguajes utilizados en IA como LISP y
PROLOG tienen su propio motor de
inferencia y están sujetos a reglas muy
particulares.
Sistemas de Deducción
• ¿Cuál es la diferencia entre un hecho y una
afirmación?
• Un hecho es algo que se considera
verdadero, una afirmación es una proposición
afirmativa que necesita ser demostrada.
• Ejemplos de reglas para identificar animales:
Sistemas de Deducción
• Z1 Si X tiene pelo entonces X es mamífero
• Z2 Si X da leche entonces X es mamífero
• Z3 Si X tiene plumas entonces X es ave
• Z4 Si X vuela y X come carne entonces es
mamífero
• Z5 Si X es mamífero y X come carne
entonces X es carnívoro
Sistemas de Reacción
• Los sistemas de reacción permite inferir
conocimiento a través de una concatenación
de reglas, las cuales pueden ser Progresivas
o Regresivas.
• Los sistemas de reacción tratar de anclar
consecuentes con antecedentes de las reglas
teniendo así sistemas más inteligentes.
• Los sistemas de reacción
ejecución de acciones.
implican
la
Sistemas Reacción
B1 Si el paso es la verificación de la orden
Papas fritas se van a empacar
No se va a empacar Pepsi
Entonces pregunte al cliente si no le gustarían
llevar una botella de Pepsi.
• Otras reglas por definir son eliminar y añadir
elementos.
Encadenamiento Progresivo y
Regresivo
• El encadenamiento de reglas puede ser hacia
adelante. En ésta, se inicia con cláusulas
atómicas de la base de conocimiento. Luego
se aplica el modus Ponens Generalizado
hacia delante hasta que ya no se puedan
obtener nuevas cláusulas atómicas.
• Las inferencias realizadas son de la forma:
• Situación ⇒ Respuesta
Encadenamiento Progresivo o
Regresivo
•
•
•
•
Reglas:
R1: si A entonces B.
R2: si B entonces C.
R3: si C entonces Z
• Hechos:
• H1: A (dato de partida)
• H3: Z (objetivo a alcanzar)
Encadenamiento Progresivo y
Regresivo
• En el encadenamiento regresivo se aplica
todo lo contrario; es decir, dado un objetivo
se pretende llegar al hecho para dar una
solución a un problema.
• El encadenamiento regresivo o backtracking
permite regresar a una opción anterior en
caso
de
que
existieran
varios
encadenamientos de regla que no llevan a la
Modelamiento Cognitivo
• Los sistemas basados en reglas pueden
verse como sustratos, de esta forma se
puede tener una forma de introspección del
como obtuvieron la deducción; es decir,
muestran como se formaron las reglas.
• Los sistemas basados en reglas se les
conoce como sabios idiotas, ya que sólo
respondan a preguntas fáciles y carecen de
muchas de las características del experto del
Modelos para la Resolución de
Problemas
• Los sistemas basados en reglas pueden
funcionar como sistemas de producción.
• Siendo sistemas de producción pueden
utilizarse para generar nuevo conocimiento
de las reglas ya existentes.
PROLOG
•
•
•
•
•
•
Hechos:
las aves vuelan
los pingüinos no vuelan
"pichurri" es un ave
"sandokan" es un perro
"alegría" es un ave
PROLOG
• Reglas o Restricciones:
• una mascota vuela si es un ave y no es un
pingüino
• Preguntas
• ¿ "pichurri" vuela ?
• ¿ qué mascotas vuelan ?
PROLOG
• Términos: constantes (a), variables (X),
funciones (f(X, Y ))
pepe, juan, Cliente, cliente-de(X, Y )
• Fórmulas atómicas:
sobre términos
predicados
tipo-cliente(X,bueno)
definidos
PROLOG
• Fórmulas bien formadas (wff): fórmulas
atómicas unidas por conectivas (^, _,!, ¬) y
cuantificadas (1A universal, 1B existencial)
• 1AX, 1BZ cliente(X) ^ compra(X, Z) ^ caro(Z)
 tipo-cliente(X, bueno)
• abuelo(X,Y) :- padre(X,Z), padre(Z,Y).
• 1AX, Y 1BZ padre(X, Z) ^ padre(Z, Y) 
abuelo(X, Y )
PROLOG
• abuelo(X,Y) :- padre(X,Z), madre(Z,Y).
• abuelo(X,Y) :- padre(X,Z), padre(Z,Y).
• abuelo(X, Y) = {(pepe, juan), (pepe, ana), … ,
(luis, javier)}
• progenitor(X, Y ) :- padre(X, Y ).
• progenitor(X, Y ) :- madre(X, Y ).
PROLOG
• abuelo(X,Y) :- padre(X,Z), madre(Z,Y).
• abuelo(X,Y) :- padre(X,Z), padre(Z,Y).
• abuelo(X,Y) :- padre(X,Z), progenitor(Z,Y).
• hechos: A. (A átomo)
• reglas: A :- A1, ..., An. (n>0, y A, A1, ..., An
átomos)
PROLOG
• Hechos:
– padece(jon, gripe).
– padece(jon, hepatitis).
– padece(ana, gripe).
– padece(carlos, alergia).
– es-síntoma(fiebre, gripe).
– es-síntoma(cansancio, gripe).
– es-síntoma(estornudos, alergia).
– suprime(paracetamol, fiebre).
– suprime(antihistamínico, estornudos).
PROLOG
• Reglas:
– debe-tomar(Per, Far)
alivia(Far, Enf).
– alivia(Far,
Enf)
:suprime(Far, Sin).
:-
padece(Per,
es-síntoma(Sin,
• Preguntas:
– ? padece(carlos, gripe).
– ? padece(jon, Z).
– ? alivia(paracetamol, gripe).
Enf),
Enf),
PROLOG
– ? alivia(X, gripe).
– ? debe-tomar(Y, antihistamínico).
– ? alivia(X, Y).
– ? suprime(X, fiebre), suprime(X, estornudos).
• ¿Qué devuelve
resultado?
cada
pregunta
como
PROLOG
• hija (*A, *B) <- mujer (*A), padre (*B, *A).
• hija (*A, *B) <- mujer (*A), madre (*B, *A).
• A continuación se muestra un programa
completo en PROLOG:
%% declaraciones
padrede('juan', 'maria').
padrede('pablo', 'juan').
PROLOG
padrede('pablo', 'marcela').
padrede('carlos', 'debora').
%%Reglas
% A es hijo de B si B es padre de A hijode(A,B)
:- padrede(B,A).
abuelode(A,B) :- padrede(A,C), padrede(C,B).
hermanode(A,B)
:padrede(C,A)
,
padrede(C,B), A \== B.
familiarde(A,B) :- padrede(A,B).
PROLOG
familiarde(A,B) :- hijode(A,B).
familiarde(A,B) :- hermanode(A,B).
%% consultas
% juan es hermano de marcela?
?- hermanode('juan', 'marcela').
Yes
?- hermanode('carlos', 'juan'). No
?- abuelode('pablo', 'maria'). Yes
?- abuelode('maria', 'pablo'). no
PROLOG
%unificación con evaluación.
?- X is 3+5.
X=8
%unificación simbólica
?- X = 3+5.
X = 3+5
PROLOG
%comparación con evaluación
?- 3+5 =:= 2+6.
yes
%comparación simbólica.
?- 3+5 == 2+6.
no
?- 3+5 == 3+5.
yes
PROLOG
• Los programas en PROLOG se definen a
través de Algoritmos, Lógica y Control.
• En caso de que una consulta de más de un
resultado, el prompt no aparece en la shell.
Se puede utilizar el operador . Para terminar
el resultado, o bien, el operador ; para
continuar con los emparejamientos de
resultados.
• Se pueden combinar preguntas para obtener
PROLOG
•
•
•
•
•
•
•
%Combinación de preguntas
legusta(pepe, pesca).
legusta(maria, bailar).
legusta(ana, pesca).
legusta(pepe, musica).
legusta(maria, musica).
legusta(ana, bailar).
• %preguntas
PROLOG
• ¿Le gusta la música a Pepé y a María?
• ?_
legusta(pepe,musica),
legusta(maria,
musica).
• ¿Le gusta bailar a Pepé o le gusta la música
a maria?
• ?_
legusta(pepe,bailar);
legusta(maria,
musica).
• ¿Le gusta bailar a Pepé y a maria no le gusta
la música?
PROLOG
• El portal de redes sociales de la UVAQ desea
diseñar un Sistema Experto para encontrar la
pareja ideal de cada estudiante si es que
existiere. Para lograr esto, se tienen en la
base de conocimientos registrados los gustos
de cada usuario (color de ojos, altura,
complexión, carro, etc.). Se da un punto por
cada coincidencia. Diseñar la regla o reglas
que determinen la mejor pareja de cada
usuario. (Se deben tener al menos 2 hombres
y 2 mujeres con 5 gustos c/u).
PROLOG
• Se puede aplicar recursividad en PROLOG
además de que algunos programas en
programación estructurada pueden ser
implementados.
•
•
•
•
•
%Sucesiones
sucesor(1,2).
sucesor(2,3).
sucesor(3,4).
sucesor(4,5).
PROLOG
• sucesor(6,7).
• suma(1,X,R):-sucesor(X,R).
• suma(N,X,R):-sucesor(M,N), suma(M,X, R1),
sucesor(R1, R).
• %Como se crearía una consulta?
• %¿Qué es lo que el programa haría?
PROLOG
• Una lista es una secuencia lineal de objetos
en donde todas las manipulaciones se hacen
del lado izquierdo de la lista.
• La lista vacía se representa []. Una lista que
no es vacía debe contener al menos dos
elementos, uno del lado izquierdo y otro del
lado derecho. Ejemplo: [X | Y], [X, Y | Z].
PROLOG
• agregar([], L, L).
• agregar([A|R], L, [A|T]):-agregar(R, L, T).
• %Como se realiza la consulta?
• ?- agregar([1,2,3 | [] ], [1, 5,7 | [] ], R).
• Dos predicados com el mismo nombre pero
diferente aridad (numero de argumentos) son
diferentes.
PROLOG
• %Programa aridad
• ama(juan).
• ama(pepe, maria).
• La unificación es el proceso en el cual uma
variable toma un valor.
• Cuando una variable tiene un valor, este no
cambia.
PROLOG
• Dos términos se ejecutan cuando existe una
posible ligadura en sus variables y en sus
valores. Ejemplo: a(X, 3) = a(2, Y).
•
•
•
•
•
•
edad(luis,25).
edad(hugo,32).
edad(paco,29).
edad(jaime,67).
edad(laura,85).
es_viejo(Persona)
valor > 60.
:-
edad(Persona,Valor),
Ejercicio
•
•
•
•
•
•
•
•
•
padre(X,Y) – X es padre de Y
madre(X,Y) – X es madre de Y
es_padre(X) – X es un padre
es_madre(X) – X es una madre
es_hijo(X) – X es un hijo (hombre)
hermana(X,Y) – X es hermana de Y
abuelo(X,Y) – X es abuelo (hombre) de Y
tia(X,Y) – X es tía de Y
primo(X,Y) – X es primo (hombre) de Y
PROLOG
• Prolog tiene la característica de ser
reversible; es decir, los argumentos pueden
ser de entrada y salida. Si se tiene un
predicado abuelo se puede saber quienes
son los nietos de ese abuelo.
• Esto no sucede
aritméticos.
con
los
operadores
• Otro tipo de datos utilizado en Prolog es el
PROLOG
• Por
ejemplo:
‘Cárdenas’, 25)
persona(‘Eva’,
‘López’,
• Define a una persona teniendo como
atributos su nombre, sus apellidos y su edad.
Dado que los términos son anidados se
pueden tener registros como:
• Persona(“Helena”,
dirección(‘Miguel Hidalgo
edad(22),
33’, ‘Centro’,
PROLOG
• Se pueden utilizar estructuras de datos
recurrentes como árboles, en donde el primer
elemento podría ser un nodo, el segundo el
hijo izquierdo y el tercer elemento, el hijo
derecho.
• arbol(dato1, temp, temp)
• arbol(dato1, arbol(dato2, temp, temp), temp)
• En donde temp indica un campo vacío.
PROLOG
• ¿Qué diferencia existe entre las siguientes
listas?
• L= [1, 2, 3, 4, 5],
• M = [0, L].
• L = [1, 2, 3, 4, 5],
• M = [0 | L].
• Las
listas
pueden
ser
de
elementos
PROLOG
• El predicado member nos permite saber si un
elemento existe en la lista
• ?- member(3, [1,2,3,4,5,6]). %regresa true
• El método append/3 sirve para concatenar
listas
• ?- append([1,2,3], [a, b, c], X).
• Las cadenas pueden ser tratadas como listas
cuando se escriben con comillas dobles.
PROLOG
• Por ejemplo la cadena
equivalente a X=[65, 66, 67].
X=“ABC”
es
• Los predicados utilizados para listas, también
nos sirven para cadenas.
• La función number_codes/2 convierte un
número a cadena.
• ? number_codes(12, X). % X=[49, 50].
PROLOG
• La función atom_codes/2 proporciona el
código equivalente de una cadena.
• ?- atom_codes(juan, X).
• X = [106, 117, 97, 110].
• //Comprobación de tipos
• es_lista([]).
• es_lista([_|B]):-es_lista(B).
PROLOG
• ?- es_lista([a]).
• Existen ya predicados definidos para la
comprobación de tipos de datos básicos
como: integer/1, float/1, number/1, atom/1,
var/1, novar/1, ground/1.
PROLOG
•
•
•
•
•
•
•
•
•
% Ejemplo
entrada(paella).
entrada(gazpacho).
entrada(consome).
carne(filete_de_cerdo).
carne(pollo_asado).
pescado(trucha).
pescado(bacalao).
postre(flan).
PROLOG
•
•
•
•
•
•
•
•
•
postre(nueces_con_miel).
postre(naranja).
calorias(paella, 200).
calorias(gazpacho, 150).
calorias(consome, 300).
calorias(filete_de_cerdo, 400).
calorias(pollo_asado, 280).
calorias(trucha, 160).
calorias(bacalao, 300).
PROLOG
•
•
•
•
•
calorias(flan, 200).
calorias(nueces_con_miel, 500).
calorias(naranja, 50).
plato_principal(P):- carne(P); pescado(P).
comida(Entrada,
Principal,
Postre):entrada(Entrada), plato_principal(Principal),
postre(Postre).
• valor(Entrada, Principal, Postre, Valor):calorias(Entrada, X), calorias(Principal, Y),
calorias(Postre, Z), sumar(X, Y, Z, Valor).
PROLOG
• comida_equilibrada(Entrada,
Principal,
Postre):- comida(Entrada, Principal, Postre),
valor(Entrada, Principal, Postre, Valor),
menor(Valor, 800).
• sumar(X, Y, Z, Res):- Res is X + Y + Z.
• menor(X, Y):- X < Y.
• dif(X, Y):- X \==Y.
•
• Encontrar: ¿Cuántas calorías tiene la
combinación paella, trucha, naranja? ¿Qué
PROLOG
• Se pueden definir funciones recursivas como
el factorial:
• fac(0,1).
• fac(N,F) :- N > 0, M is N - 1, fac(M,Fm), F is N
* Fm.
• ¿Cómo se expresa la serie de fibonnaci?
PROLOG
• Algo sumamente importante en cualquier
lenguaje de programación son las interfaces
de E/S y Prolog no es la excepcion.
• Se cuenta con los predicados read/1 para
leer el valor de variables seguidas por un
punto y get para leer carácter por carácter
regresando el código ASCII correspondiente.
Prolog
• Para salida estándar se cuenta con las
funciones write/1 para cualquier valor, put/1
para colocar un carácter. Adicionalmente se
cuenta con las relaciones nl/0 para nueva
línea y display/1 para mostrar mensajes en
pantalla.
• A continuación se muestra el ejemplo de un
programa que utiliza entrada y salida, así
como un manejo estructurado de programa.
PROLOG
• sumar_lista([],Parcial,Parcial).
• sumar_lista([Num|Resto],Parcial,Result)
:NParcial
is
Num+Parcial,
sumar_lista(Resto,NParcial,Result).
• leer_numero(Num)
number(Num).
:-
read(Num),
PROLOG
• suma :-
suma_aux([]).
• suma_aux(Lista) :suma_aux([Num|Lista]).
leer_numero(Num),
• suma_aux(Lista)
sumar_lista(Lista,0,Result),
display('LA SUMA ES : '),
nl.
:nl,
display(Result),
Referencias
• Carreón, J. (2007) Material de la Asignatura
de Inteligencia Artificial, Universidad Vasco
de Quiroga, Morelia, Michoacán, México.
• Nilsson, N. (2001). Inteligencia Artificial. Una
nueva síntesis. McGraw-Hill, España.
• Russel, S. y Norving, P. (2004). Inteligencia
Artificial. Un Nuevo enfoque. Pearson
Prentice Hall, España
Questions?