ia - tema 4b - reglas de inferencia
DESCRIPTION
fhdfhTRANSCRIPT
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
1 de 110Septiembre de 2007
Datos de la AsignaturaTemarío
2º CuatrimestreSistemas basados en el conocimiento (Cap. 8-12)
– Mediante lógica de predicados.
– Mediante Sistemas de producción.
Tratamiento de la incertidumbre (Cap. 13-15)
– Redes Bayesianas.
– Razonamiento aproximado (lógica difusa).
Universidad de Castilla-La ManchaInteligencia Artificial e Ingeniería del
Conocimiento
Tema4: Sistemas basados en el conocimiento (Agentes Lógicos)
Profesores: Luis Jiménez Linares. Luis Enrique Sánchez Crespo.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
3 de 110Septiembre de 2007
Índice
6.1 Un agente conocimiento-intensivo.
6.2 El ambiente del mundo de wumpus
6.3 Representación, Razonamiento y Lógica
6.4 Lógica propositiva
6.5 Un agente para el mundo de wumpus
6.6 Resumen
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
4 de 110Septiembre de 2007
Búsqueda informada
Agente conocimiento-intensivo
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
5 de 110Septiembre de 2007
Agentes basados en conocimiento
IntroducciónSe introduce el diseño de un agente basado en el conocimiento
Se presenta un lenguaje lógico sencillo pero insuficiente, el de la lógica propositiva,
Se ejemplifica con un agente capaz de desempeñarse bien en el mundo de Wumpus, siendo Wumpus un juego que provoca adicción.
En este capítulo se aprende a diseñar agentes que– construyen representaciones del mundo,
– derivan nuevas representaciones del mundo por inferencia y
– usan esas nuevas representaciones para saber qué hacer
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
6 de 110Septiembre de 2007
Agentes basados en conocimiento
Representación del conocimiento
Foundations of Artificial Intelligence 20
El papel pretendido de la representación del conocimientoen IA es reducir problemas de acción inteligente en meros
problemas de BÚSQUEDAGrinsberg
1 .Crear un algoritmo para resolverel problema
2. Seleccionar un lenguaje de programación para codificar la tarea
3. Capturar el algoritmo comoprograma
4. Ejecutar el programa
1 .Crear un algoritmo para resolverel problema
2. Seleccionar un lenguaje de programación para codificar la tarea
3. Capturar el algoritmo comoprograma
4. Ejecutar el programa
1. Identificar el conocimiento necesario pararesolver el problema
2. Seleccionar el lenguaje con el cual dichoconocimiento pueda ser representado
3. Escribir el conocimiento dentro de eselenguaje
4. Usar las consecuencias del conocimientopara resolver el problema
1. Identificar el conocimiento necesario pararesolver el problema
2. Seleccionar el lenguaje con el cual dichoconocimiento pueda ser representado
3. Escribir el conocimiento dentro de eselenguaje
4. Usar las consecuencias del conocimientopara resolver el problema
Programación Inteligencia Artificial
La BÚSQUEDA aparece en el punto 4
Analogía entre Programación y Problemas de IA
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
7 de 110Septiembre de 2007
Agentes basados en conocimiento
La meta consiste en que …– el conocimiento aparezca explícitamente en una base
– se logren conclusiones del conocimiento declarado en la base
Para ello es indispensable la LÓGICA– Una dada lógica es una notación ( o un lenguaje) matemático
para gestionar el conocimiento
– La principal alternativa que hay para la lógica es el lenguaje natural (español, inglés,...).
– Tanto en el lenguaje natural como en la lógica la unidad es la oración ( “sentence”)
– Sintaxis y Semántica
– Inferencia Lógica
– Lógica sana y completa
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
8 de 110Septiembre de 2007
Agentes Lógicos
Agentes basados en conocimiento
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
9 de 110Septiembre de 2007
Agentes basados en conocimiento
Función [Fig 6.1] a aclarar en temas siguientesbase de conocimiento– declarada
(dicha)– aprendida
- motor de inferencias
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
10 de 110Septiembre de 2007
Agentes basados en conocimiento
Función – Un agente conocimiento-intensivo tiene como
componente seminal una base de conocimientos.
– Una base de conocimientos es un conjunto de representaciones de hechos del mundo.
– Cada una de esas representaciones se llama una “oración”.
– Las oraciones se expresan en un lenguaje representacional del conocimiento.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
11 de 110Septiembre de 2007
Agentes basados en conocimiento
El agente opera como sigue (TELL and ASK)
1. Le dice a la base su PERCEPCIÓN – (añade oraciones a la base)
2. Le pregunta a la base qué ACCIÓN encarar– (contesta preguntas de la base)
– (mientras, opera un MOTOR DE INFERENCIAS)
3. Ejecuta la ACCIÓN
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
12 de 110Septiembre de 2007
Agentes basados en conocimiento
Arquitectura de dos agentes
Foundations of Artificial Intelligence 22
loop foreverInput perceptsstate Update-State(state, percept)rule Rule-Match(state, rules)action Rule-Action[rule]Output actionstate Update-State(state, action)
end
loop foreverInput perceptsstate Update-State(state, percept)rule Rule-Match(state, rules)action Rule-Action[rule]Output actionstate Update-State(state, action)
end
ESTE AGENTE sigue la pista del estado delmundo externo mediante su función“actualizar”.(Update)
ESTE AGENTE sigue la pista del estado delmundo externo mediante su función“actualizar”.(Update)
loop foreverInput perceptsKB tell(KB, make-sentence(percept))action ask(KB, action-query)Output actionKB tell(KB, make-sentence(action))
end
loop foreverInput perceptsKB tell(KB, make-sentence(percept))action ask(KB, action-query)Output actionKB tell(KB, make-sentence(action))
end
ESTE OTRO AGENTE, a cada instante, cualesquiera sean suspercepciones, lo hace en forma de oración. P.ej. “estoy hambriento”
ESTE OTRO AGENTE, a cada instante, cualesquiera sean suspercepciones, lo hace en forma de oración. P.ej. “estoy hambriento”
las dos primeras menciones se refieren a un agente reflejo simple y las otras dos a un agente conocimiento-intensivo .
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
13 de 110Septiembre de 2007
Agentes basados en conocimiento
Arq. de un agente con base de conocimientoNivel de conocimiento
– es el nivel más abstracto - describimos al agente indicando qué conoce
– ejemplo - un taximetrero automático podría saber que desde la playa Bristol a la playa La Perla hay una ruta costanera rápida
Nivel lógico– es el nivel en el cual el conocimiento queda codificado en
oraciones– p.ej.: enlaces (Bristol, La Perla, ruta costanera rápida)
Nivel de implementación– es el nivel en el cual hay una representación física de las oraciones
en el nivel lógico– p.ej.:”enlaces (Bristol, La Perla, ruta costanera rápida)”– conexión{B,P,rcr} = 1– (un 1 en una tabla tridimensional)– (un conjunto de apuntadores dirigidos a los símbolos)
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
14 de 110Septiembre de 2007
Agentes Lógicos
El mundo de Wumpus
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
15 de 110Septiembre de 2007
El mundo de WumpusEl ambiente del mundo de Wumpus
Percepción = [Hedor, Brisa, Resplandor, Golpe, Grito]
El agente no puede percibir su propia ubicación
Acciones = [avanzar, girarizquierda, girarderecha, capturar, dispararflecha, trepar]
Agente muere al entrar a un habitáculo con pozo o con wumpus vivo.
Meta del agente es encontrar oro, volver al habitáculo [1,1] y trepar muro.
Razonamiento– ejemplos de inferencias: ubicación de
• pozos, • wumpus • habitáculos sin riesgo• habitáculo 1-1 al volver
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
16 de 110Septiembre de 2007
El mundo de WumpusEl ambiente del mundo de
WumpusDetalles del ambiente– mundos de wumpus elegidos al azar– agentes múltiples, en comunicación– wumpi móviles– múltiples piezas de oro
Detalles de disponibilidades– lenguaje natural– aprendizaje– visión– habla
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
17 de 110Septiembre de 2007
El mundo de WumpusAyudas en el mundo de Wumpus
[Hedor, Brisa, Resplandor, Golpe, Grito]
[Hedor, Brisa, Resplandor, Golpe, Grito]
[Hedor, Brisa, Resplandor, Golpe, Grito]
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
18 de 110Septiembre de 2007
El mundo de WumpusEl mundo de Wumpus
El agente arranca de (1,1)
La meta es encontrar oro, volver a (1,1) y trepar la pared
No viene mal matar al wumpus con la única flecha, son más bonificaciones y hay un nuevo camino por transitar
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
19 de 110Septiembre de 2007
El mundo de WumpusPercepciones
Las percepciones forman una vector fila de 1x5 del tipo
(Hedor,Brisa,Nada,Nada,Nada)
El primer Nada es resplandor
El segundo es Golpe (contra la pared)
El tercero es Grito
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
20 de 110Septiembre de 2007
El mundo de WumpusPaMA
Percepciones
acciones ..avanzar,girarizq, etc.
Meta - Capturar el oro y volver
Ambiente – mundo de wumpus
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
21 de 110Septiembre de 2007
El mundo de WumpusPrimer Paso
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
22 de 110Septiembre de 2007
El mundo de WumpusSegundo Paso
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
23 de 110Septiembre de 2007
El mundo de Wumpus¿Por qué (x,y) está bien?
(1,1)` Porque el agente está vivo
(1,2) `”No hedor en (1,1)” + “No brisa en (1,1)” + “(1,1) y (1,2) son vecinos””
(2,1) `”no hedor en (1,1)”, + “no brisa en (1,1)” + “(1,1) y (2,1) son vecinos”
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
24 de 110Septiembre de 2007
El mundo de WumpusTercer Paso
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
25 de 110Septiembre de 2007
El mundo de WumpusCuarto Paso
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
26 de 110Septiembre de 2007
El mundo de Wumpus¿Por qué (1,3) = wumpus?
Hedor en (1,2) implica que el wumpus está ya sea en (1,1), ya sea en (2,2), ya sea en (1,3)
(1,1) fue visitado, lo visitado está bien el wumpus no está en (1,1)
(2,1) sin hedor fue visitado el wumpus no está en (2,1)
El wumpus está en (1,3)
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
27 de 110Septiembre de 2007
El mundo de Wumpus¿Por qué (3,1) = pozo?
Brisa en (2,1) implica que hay un pozo ya sea en (1,1), ya sea en (2,2), o ya sea en (3,1)
(1,1) fue visitado, el agente está vivo el pozo no está en (1,1)
(2,1) sin brisa al ser visitado el pozo no está en (2,2)
El pozo está en (3,1)
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
28 de 110Septiembre de 2007
Agentes Lógicos
Representación, razonamiento y lógica
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
29 de 110Septiembre de 2007
Representación, razonamiento y Lógica
Representar: lograr que lo representado sea entendible para una computadora; y que así el agente pueda operar y merecer el nombre de agente – Sintaxis, forma usada para representar oraciones- cómo están
representadas las oraciones
– Semántica, mapeo desde oraciones hacia hechos del mundo, determina los hechos del mundo a los que hacen alusión las oraciones.
– Razonamiento: Simulador del mundo de wumpus• Hechos ”son consecuencia" de hechos
• Oraciones ”son consecuencia” de oraciones
• Conjuntos de oraciones “son consecuencia” de conjuntos de oraciones.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
30 de 110Septiembre de 2007
Representación, razonamiento y Lógica
Razonamiento,– Es el proceso de construir nuevas representaciones, bajo la
forma de oraciones, a partir de representaciones anteriores.
– La existencia de una base de conocimientos - seminal para el agente - le permite la creación de razonamientos, con la ayuda del motor de inferencia.
Requisitos de la Lógica: opera bien si la sintaxis y la semántica están definidas de manera precisa (sin ambigüedades).– Aquí una lógica es una buena notación o un lenguaje
matemático útil para el logro de demostraciones acomodadas a las posibilidades de la computadora.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
31 de 110Septiembre de 2007
Representación
Los lenguajes de programación como el C o el Pascal son idóneos para representar algoritmos y estructuras de datos concretas. Los lenguajes de programación están diseñados para describir cabalmente el estado de la computadora y de cómo cambia ésta conforme al programa que se está ejecutando.
Sin embargo, sería deseable poder contar con otro lenguaje para representar el conocimiento que sirva para el caso cuando no se cuenta con información completa: cuando no hay total certeza de cómo son las cosas, y lo único que se sabe son algunas posibilidades de cómo son. Un lenguaje que no satisface lo anterior tiene el defecto de no ser suficientemente expresivo.
El objetivo de un lenguaje para la representación del conocimiento es el de El objetivo de un lenguaje para la representación del conocimiento es el de expresar los conocimientos en una base manejable por el agente, permitiéndole expresar los conocimientos en una base manejable por el agente, permitiéndole a éste un buen desempeño, p.a éste un buen desempeño, p.ejej. en el mundo de wumpus.. en el mundo de wumpus.
El lenguaje representando conocimiento interno de un agente es distinto del El lenguaje representando conocimiento interno de un agente es distinto del lenguaje externo empleado para comunicarse con otros agentes (JiVE, etc.). En lenguaje externo empleado para comunicarse con otros agentes (JiVE, etc.). En el el ej.ej. se usa sólo interno. se usa sólo interno.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
32 de 110Septiembre de 2007
Representación
Los lenguajes naturales como el inglés o el español indudablemente Los lenguajes naturales como el inglés o el español indudablemente son expresivos. Sin embargo, han experimentado una evoluciónson expresivos. Sin embargo, han experimentado una evolución que que tiende más atiende más a satisfacer las necesidades de la comunicación que las de satisfacer las necesidades de la comunicación que las de la representación.la representación.
En un buen lenguaje para representar el conocimiento se combinan las En un buen lenguaje para representar el conocimiento se combinan las ventajas de los lenguajes naturales y las de los lenguajes formales. ventajas de los lenguajes naturales y las de los lenguajes formales.
Entonces, tratemos de combinar las ventajas de los lenguajes naturales Entonces, tratemos de combinar las ventajas de los lenguajes naturales y las de los lenguajes formales:y las de los lenguajes formales:» a) lo suficientemente expresivo como para representar el conocimiento a) lo suficientemente expresivo como para representar el conocimiento
aún cuando no se cuenta con información completa y no hay total certeza aún cuando no se cuenta con información completa y no hay total certeza de cómo son las cosas.de cómo son las cosas.
» b) lo suficientemente conciso como para evitar ambigüedades, siendo b) lo suficientemente conciso como para evitar ambigüedades, siendo independiente del contexto para su interpretación.independiente del contexto para su interpretación.
» c) apto para un procedimiento de inferencia con el cual obtener nuevas c) apto para un procedimiento de inferencia con el cual obtener nuevas representaciones a partir de las existentes en la base.representaciones a partir de las existentes en la base.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
33 de 110Septiembre de 2007
Representación
Cualquier lenguaje representacional del conocimiento tiene: – Su sintaxis - define todas las posibles configuraciones
(secuencias) de símbolos que constituyen oraciones del lenguaje.
• Ejemplos: – oraciones del texto
– bits de la memoria de la computadora
– Su semántica - determina los hechos del mundo a los cuales se están refieiendo las oraciones. Cada oración argumenta algo del mundo.
• Un agente CREE en las oraciones referidas al mundo.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
34 de 110Septiembre de 2007
Semántica - Lenguajes composicionales
Se llama lenguaje composicional a aquél en que el significado de una oración es la suma de los significados de cada parte. Casi todos los lenguajes tienen una relación sistemática entre las oraciones y los hechos.
Ejemplo de la matemática:– a^2 + b^2
– Su significado es la suma del significado de a^2 más la de b^2
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
35 de 110Septiembre de 2007
Inferencia
RAZONAMIENTO e INFERENCIA: Son los nombres del proceso por el cual se obtienen conclusiones.
INFERENCIA LÓGICA y DEDUCCIÓN: Son los nombres de todo razonamiento o inferencia válidos y confiables. Implantan las relaciones de implicación que existe entre oraciones.– Inferencia:
• Verificar la validez de oraciones que se toman como verdaderas pese a desconocerse su real interpretación.
– Verdad : • Depende del estado del mundo y de la interpretación.
– Validez : • Una oración es válida si es verdadera independientemente del
mundo o de la interpretación.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
36 de 110Septiembre de 2007
Razonamiento
Consecuencias o implicaciones generan nuevas oraciones a partir de otras previas, todas fidedignas.
Teoría de la demostración - conjunto de reglas para deducir las implicaciones de un conjunto de oraciones - dentro de un lenguaje - ella estudia los pasos confiables de un razonamiento – motor de inferencia
Semántica - en lógica el SIGNIFICADO de una oración es aquello que ella afirma del mundo. Restringe a que el mundo sea de la forma expresada y no de otra forma alternativa. Para poder entender lo que SIGNIFICA una oración, quien la compuso debería proporcionar su respectiva INTERPRETACIÓN. Ninguna oración tiene significado por sí misma ni es autoevidente.
Hay inferencias inválidas
– ¿Caso de “Hay una brisa en (3,2) o no hay una brisa en (3,2)”?
– ¿Caso de A = A?
Hay inferencias insatisfactibles si no existe un mundo donde puedan suceder. – ¿Caso de “hay varios wumpi”?
– ¿Caso de “hay un wumpus en (1,1)”?
– ¿Caso de “hay un wumpus en (1,1) y no hay un wumpus en (1,1)”?
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
37 de 110Septiembre de 2007
Lógica
Compromiso ontológico• para el agente, qué existe en el mundo
– en el caso de la lógica propositiva, para el agente existen hechos que serán verdaderos o falsos.
Compromiso epistemológico• para el agente, cuál es la actitud con respecto a los hechos
– en el caso de la lógica propositiva, el agente cree que una oración es verdadera o falsa, o no ha llegado a conclusión alguna
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
38 de 110Septiembre de 2007
Tipos de lógicas y sus preocupaciones
Lenguaje Ontología Epistemología
(lo que existe) (qué cree de los hechos)
-----------------------------------------------------------------------------------
Lógica Propositiva hechos verdadero/falso/no sabe
Lógica de primer hechos, objetos, enlaces
orden verdadero/falso/no sabe
Lógica temporal hechos, objetos,
enlaces, tiempos verdadero/falso/no sabe
Teoría de la
probabilidad hechos grado de certidumbre
Lógica difusa grado de verdad grado de certidumbre
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
39 de 110Septiembre de 2007
Lógica
La meta del agente racional consiste en que:– El conocimiento aparezca explícitamente
– Se logren conclusiones del conocimiento incorporado
– Para ello es indispensable la LÓGICA
– Una dada lógica es una notación matemática (un lenguaje matemático) para declarar el conocimiento
– La principal alternativa que hay para la lógica es el lenguaje natural (español, inglés,...).
– Tanto en el lenguaje natural como en la lógica la principal unidad es la oración
• Sintaxis y Semántica
• Inferencia Lógica
• Lógica sana y completa
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
40 de 110Septiembre de 2007
Agentes Lógicos
Lógica propositiva
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
41 de 110Septiembre de 2007
Lógica proposita
Lógicas y símbolos
Breve detalle de lógica propositiva
Conceptos asociados
Profundización en la Lógica Propositiva
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
42 de 110Septiembre de 2007
Lógica proposita
Proposición es una afirmación que puede ser verdadera o falsa
Conceptos relacionados– Oración atómica
– Literal
– Oración molecular
Una proposición es verdadera– si está de acuerdo con los hechos del mundo real
– si está de acuerdo con otro mundo supuesto con algún motivo, siendo falsa en el otro caso
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
43 de 110Septiembre de 2007
Lógica y símbolos
LPC =LCP Lógica basada en el cálculo propositivo
LI Þ Lógica de primer orden– con dos signos adicionales = cuantificadores
LI I ÞLógica de segundo orden
LIPML Þ Lógica propositiva modal– con dos signos más
Lógica temporal o lógica tiempo lineal temporal– con cuatro signos más
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
44 de 110Septiembre de 2007
Breve concepto de Lógica prepositiva
El ALFABETO consiste de– VARIABLES PROPOSITIVAS P, Q
– CONECTIVOS FUNCIONALES
GRAMÁTICA -sin cuantificadores - con oraciones atómicas y moleculares
SEMANTICA basada en tablas de verdad exhaustivas
TEORIA DE LA DEMOSTRACIÓN con modus ponens y otras reglas familiares
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
45 de 110Septiembre de 2007
Sintaxis en lógica propositiva
La sintaxis de la lógica propositiva es sencilla. Los símbolos utilizados en la lógica propositiva son las constantes lógicas Verdadero y Falso, símbolos de proposiciones tales como P y Q, los conectivos lógicos /\, \/, , => y ¬ y paréntesis ( ). Todas las oraciones se forman combinando los signos anteriores mediante las siguientes reglas:Las constantes lógicas Verdadero y Falso constituyen oraciones en sí mismas.Un símbolo propositivo tal como P y Q es una oración en sí mismo.Encerrar entre paréntesis una oración produce también una oración, por ejemplo (P /\ Q).Una oración molecular se forma combinando oraciones más sencillas o atómicas con uno de los cinco conectores lógicos antes mencionados.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
46 de 110Septiembre de 2007
Gramática BNF
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
47 de 110Septiembre de 2007
Ejemplos de oraciones moleculares
P Q R ( )P Q Q R P ( ) ( )
( ) ( )P Q Q P
( ) ( )P Q P Q
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
48 de 110Septiembre de 2007
Sintaxis y semántica: Oraciones atómicas
Las oraciones atómicas afirman hechos. Una oración atómica está formada por un símbolo de predicado seguido de una lista entre paréntesis de términos. Ejemplo: Hermano(Ricardo,Juan) Afirma que para alguna interpretación Ricardo Corazón de León es hermano del Rey Juan. Es válido que una oración atómica tenga términos complejos como argumentos: Casado(PadreDe(Ricardo), MadreDe(Juan)) Afirma que el padre de Ricardo Corazón de León está casado con la madre del Rey Juan (dentro de una adecuada interpretación). Una oración atómica es verdad si la relación expresada por el símbolo de predicado Casado es verdad para los objetos anotados en los argumentos. La verdad de una oración atómica depende tanto del MUNDO como de la INTERPRETACIÓN.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
49 de 110Septiembre de 2007
Oraciones
Oración Atómica - Es una proposición – sin cuantificadores
• universal---para todo,
• existencial--existe
– ni conectivos booleanos• \/ unión o suma de dos conjuntos
• /\ intersección o parte común de dos conjuntos
Una Literal:– Es una oración atómica P
– o su negación ¬P
Oración Molecular - representada por símbolos propositivos (e.g., P, Q, R, S, etc.)– constantes lógicas: Verdadero,Falso
– Conectivos , , , , • Se usan mucho , ,
– Mediante los conectores lógicos se pueden construir oraciones más complicadas. Ejemplos:
– Hermano(Ricardo,Juan) /\ Hermano(Juan,Ricardo) – Mayor(Juan,30) \/ Menor(Juan, 30)– Mayor(Juan,30) Þ ¬Menor(Juan, 30)– ¬Hermano(Robin, Juan)
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
50 de 110Septiembre de 2007
Modelo
Disponemos de una oración bajo una cierta interpretación. Entonces cualquier mundo desde esa misma interpretación, será un modelo para dicha oración.
Modelos: mundos en los cuales una oración dada es verdad
– En lógica propositiva es un renglón en la tabla de verdad
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
51 de 110Septiembre de 2007
Modelos analizados con un diagrama de Venn
P Q
EJEMPLO:
P Q (todo excepto )
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
52 de 110Septiembre de 2007
Definición semántica
Sean F y G dos fórmulas propositivas y sea M una interpretación cualquiera.– F G será verdad en M si tanto F como G son
verdaderas en M
– F G será verdad en M si por lo menos uno de F o G es verdad en M
F será verdad en M si tanto F como G son falsos en M.
– F G será verdad en M si ya sea F es falso en M o G es verdad en M
– F G será verdad en M si ambos, F y G, son verdad en M o ambos, F y G son falsos en M
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
53 de 110Septiembre de 2007
Verdad
Depende del estado del mundo y de la interpretación de quien construyó las oraciones
Una oración es válida independientemente del mundo o de la semántica
Una oración es insatisfactible si el mundo nunca es igual a lo que ella describe
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
54 de 110Septiembre de 2007
Lógica Propositiva: Semántica
En lógica propositiva, la semántica de los conectivos se especifica mediante tablas de verdad:
Las tablas de verdad también se pueden usar para determinar la validez de las oraciones:
P Q P P Q P Q P Q P QF F T F F T TF T T F T T FT F F F T F FT T F T T T T
P Q P P Q P Q (P Q) ( P Q)F FF TT FT T
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
55 de 110Septiembre de 2007
Inferencia propositivaMétodo de la enumeración
Sea y¿La base de conocimiento garante a a?
– Verificar todos los modelos posibles – en todos ellos a debe ser verdadera siempre que la BC sea verdadera.
– Se puede argumentar que para cualquier modelo M de la BC, M también es modelo de a
A B KB A C B C ( ) ( )
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
56 de 110Septiembre de 2007
Reglas de Inferencia
Modus Ponens
Y--Eliminacióna1 & a2 & a3 & a4 an (n = 1..4)
Y--introduccióna1, a2, a3, a4 a1 & a2 & a3 & a4
O--Introduccióna1 a1 V an
Doble-negación eliminación- (-
Resolución Unitaria V
Resolución (difícil) VVV -
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
57 de 110Septiembre de 2007
Reglas de Inferencia (lógica propositiva)
(MP) Modus Ponens (Implicación-eliminación)
(AI) =(YI) Y-introducción (OI) O-introducción
(AE)=(YE) Y-eliminación
(NE) Negación-eliminación
,
1 2
1 2
, , ,
n
n
1 2 n
i
i
n1 2
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
58 de 110Septiembre de 2007
Reglas de Inferencia (lógica propositiva)
(UR)Resolución Unitaria
(R) Resolución General
Notas:– Resolución es completa en lógica propositiva– Modus Ponens (en su forma general)
– es completa para bases de conocimiento de Horn y puede ser usada en encadenamientos hacia atrás y hacia adelante.
,
,
1 2 1 2, , , , n n
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
59 de 110Septiembre de 2007
Ejemplo: Base de Conocimiento
Ejemplo: construir una base de conocimiento para el mundo Wumpus.– Vocabulario de símbolos proposicionales:
• Hi,j es verdadero si hay un hoyo en la casilla [i,j].
• Bi,j es verdadero si hay brisa en la casilla [i,j].
– Contenido inicial de la BC:• No hay ningún hoyo en la casilla [1,1]:
– R1: H1,1
• En una casilla se siente brisa si y solo si hay un hoyo en una casilla vecina:
– R2: B1,1 (H1,2 H2,1 )
– R3: B2,1(H1,1 H2,2 H3,1)
, , , ,
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
60 de 110Septiembre de 2007
Ejemplo: Base de Conocimiento
– Nuevas reglas al recorrer las 2 primeras casillas:• Percepciones de brisas
– R4: B1,1
– R5: B2,1
• La BC actual estará formada por R1 R2 R3 R4 R5
RAZONAMIENTO e INFERENCIA: Son los nombres del proceso por el cual se obtienen conclusiones.INFERENCIA LÓGICA y DEDUCCIÓN: Son los nombres de todo razonamiento o inferencia válidos y confiables. Implantan las relaciones de implicación que existe entre oraciones.
– Inferencia: Verificar la validez de oraciones que se toman como verdaderas pese a desconocerse su real interpretación.
– Verdad : Depende del estado del mundo y de la interpretación.– Validez : Una oración es válida si es verdadera independientemente
del mundo o de la interpretación.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
61 de 110Septiembre de 2007
Reglas de Inferencia
Reglas explícitas para producir un teorema cuando se proveen dos o más teoremas.
Funciones para secuencias de teoremas hacia teoremas
En sistemas formales tienen que operar independientemente del significado semántico de las cadenas manipuladas
Sinónimo: Reglas de producción
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
62 de 110Septiembre de 2007
Equivalencia, validez, satisfacibilidad
Equivalencia: dos sentencias son equivalente lógicamente cuando si tienen los mismos valores de verdad en el mismo conjunto de modelos.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
63 de 110Septiembre de 2007
Equivalencia, validez, satisfacibilidad
Validez: una sentencia es válida si es verdadera en todos los modelos. Las sentencias validas se conocen como tautologías.
Satisfacibilidad: Una sentencia es satisfactoria si es verdadera para algún modelo.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
64 de 110Septiembre de 2007
Agentes Lógicos
Patrones de razonamiento en lógica proposicional
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
65 de 110Septiembre de 2007
Patrones de razonamiento
Resolución: nos lleva a un algoritmo de inferencia completo cuando se empareja a un algoritmo de búsqueda completo.Forma normal conjuntiva (FNC): es una sentencia representada mediante una conjunción de disyunciones de literales.Algoritmos de resolución: Los procedimientos de inferencia basados en la resolución trabajan mediante el principio de pruebas mediante contradicción. Para demostrar BC |= demostraremos que (BC es insatisfacible.Completitud de la resolución: A partir del teorema fundamental de la resolución, determinamos que si un conjunto de cláusulas es insatisfacible, entonces el cierre de la resolución de esas cláusulas contiene la cláusula vacía.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
66 de 110Septiembre de 2007
Patrones de razonamiento
Encadenamiento hacia delante y hacia atrás:– Cláusulas de Horn: disyunción de literales de los
cuales, como mucho uno es positivo.• Cabeza: literal positivo.
• Cuerpo: disyunción de literales negativos.
• Hecho: cláusula sin literales negativos.
• Restricción de integridad: una cláusula de Horn con solo literales negativos.
• La inferencia de este tipo de cláusulas se realiza mediante algoritmos de encadenamiento hacia delante y hacia atrás.
• Averiguar si hay o no implicación con las cláusulas de Horn se puede realizar en un tiempo que es lineal respecto al tamaño de la base de conocimiento.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
67 de 110Septiembre de 2007
Agentes Lógicos
Inferencia proposicional efectiva
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
68 de 110Septiembre de 2007
Patrones de razonamiento
DPLL - Algoritmo de David y Putnam (basado en Backtracking): Determina si una sentencia de entrada con lógica proposicional es satisfacible.
– Terminación anticipada:Una cláusula es verdadera si cualquier literal es verdadero.
Una cláusula es falsa si algún literal es falso.
– Heurística de símbolo puro:Un símbolo es puro si aparece siempre con el mismo signo en todas las
cláusulas.
Ej., En las 3 cláusulas (A B), (B C), (C A), A y B son puros, C es impuro.
– Heurística de cláusula unitaria:Son aquellas que tienen un solo literal.
Si solo hay un literal en una cláusula unitaria, tiene que ser verdadero.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
69 de 110Septiembre de 2007
Patrones de razonamiento
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
70 de 110Septiembre de 2007
Patrones de razonamiento
WalkSAT - Algoritmo de búsqueda: Determina si una sentencia de entrada con lógica proposicional es satisfacible. Nuestro objetivo es encontrar una asignación que satisfaga todas las cláusulas.
– Algoritmo de búsqueda local incompleto.
– Función de evaluación: Que cuente el número de cláusulas insatisfacibles.
– Debemos encontrar un equilibrio entre el gradiente y la aleatoriedad.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
71 de 110Septiembre de 2007
Patrones de razonamiento
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
72 de 110Septiembre de 2007
Patrones de razonamiento
Problemas duros de satisfacibilidad:– Considerando 3-CNF sentencias. Ej:
(D B C) (B A C) (C B E) (E D B) (B E C)
m = número de cláusulas.
n = número de símbolos.
– Los problemas duros tienen una relación m/n = 4.3 (punto crítico).
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
73 de 110Septiembre de 2007
Patrones de razonamiento
a) Gráfico que muestra la probabilidad de que una sentencia en FNC-3 con n = 50 símbolos sea satisfacible, en función del ratio cláusula/símbolo m/n.
b) Gráfico del tiempo de ejecución promedio del DPLL y del SAT sobre 100 sentencias en FNC-3 aleatorias con n=50 para un rango reducido de valores de m/n alrededor del punto crítico.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
74 de 110Septiembre de 2007
Agentes Lógicos
Agentes basados en lógica proposicional
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
75 de 110Septiembre de 2007
Conclusiones
Un agente del mundo de Wumpus usando lógica proposicional:
P1,1 W1,1 – Bx,y (Px,y+1 Px,y-1 Px+1,y Px-1,y) – Sx,y (Wx,y+1 Wx,y-1 Wx+1,y Wx-1,y)– W1,1 W1,2 … W4,4 W1,1 W1,2 W1,1 W1,3 – …
64 distintos simbolos proposicionales, 155 sentencias.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
76 de 110Septiembre de 2007
Conclusiones
Encontrar hoyos y wumpus utilizando la inferencia lógica.
Guardar la pista acerca de la localización y orientación del agente.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
77 de 110Septiembre de 2007
Conclusiones
Agente basado en circuitos:– Circuito secuencial.
– Puertas.
– Registros.
Comparación: Los agentes basados en inferencia y los basados en circuitos representan los extremos declarativo y procesal en el diseño de agentes. Se pueden comparar según diversas dimensiones:
– Precisión.
– Eficiencia computacional.
– Completitud.
– Facilidad de construcción.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
78 de 110Septiembre de 2007
Agentes Lógicos
Conclusiones
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
79 de 110Septiembre de 2007
Conclusiones
Los agentes inteligentes necesitan el conocimiento acerca del mundo para tomar las decisiones acertadas.
Los agentes contienen el conocimiento en forma de sentencias mediante un lenguaje de representación del conocimiento, las cuales quedan almacenadas en una base de conocimiento.
Un agente basado en conocimiento se compone de una base de conocimiento y un mecanismo de inferencia.
El agente opera almacenando las sentencias acerca del mundo en su base de conocimiento, utilizando el mecanismo de inferencia para inferir sentencias nuevas, y utilizando estas sentencias nuevas para decidir qué acción debe tomar.
Un lenguaje de representación del conocimiento se define por su sintaxis, que especifica la estructura de las sentencias, y su semántica, que define el valor de verdad de cada sentencia en cada mundo posible, o modelo.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
80 de 110Septiembre de 2007
Conclusiones
La relación de implicación entre las sentencias es crucial para nuestro entendimiento acerca del razonamiento. Una sentencia implica otra sentencia sies verdadera en todos los mundos dondelo es. Las definiciones familiares a este concepto son: la validez de la sentencia , y la insatisfacibilidad de la sentencia La inferencia es el proceso que consiste en derivar nuevas sentencias a partir de las ya existentes. Los algoritmos de inferencia sólidos sólo derivan aquellas sentencias que son implicadas; los algoritmos completos derivan todas las sentencias implicadas.
La lógica proposicional es un lenguaje muy sencillo compuesto por los símbolos proposicionales y las conectivas lógicas. De esta manera se pueden manejar proposiciones que se sabe que son ciertas, falsas, o completamente desconocidas.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
81 de 110Septiembre de 2007
Conclusiones
El conjunto de modelos posibles, dado un vocabulario proposicional fijado, es finito, y así se puede comprobar la implicación tan sólo enumerando los modelos. Los algoritmos de inferencia basados en la comprobación de modelos más eficientes para la lógica proposicional, entre los que se encuentran los métodos de búsqueda local y backtracking, a menudo pueden resolver problemas complejos muy rápidamente.
Las reglas de inferencia son patrones de inferencia sólidos que se pueden utilizar para encontrar demostraciones. De la regla de resolución obtenemos un algoritmo de inferencia completo para bases de conocimiento que están expresadas en forma normal conjuntiva. El encadenamiento hacia delante y el encadenamiento hacia atrás son algoritmos de razonamiento muy adecuados para bases de conocimiento expresadas en cláusulas de Horn.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
82 de 110Septiembre de 2007
Conclusiones
Se pueden diseñar dos tipos de agentes que utilizan la lógica proposicional: los agentes basados en inferencia utilizan algoritmos de inferencia para guardar la pista del mundo y deducir propiedades ocultas, mientras que los agentes basados en circuitos representas proposiciones mediante bits en registros, y los actualizan utilizando la propagación de señal de los circuitos lógicos.
La lógica proposicional es razonablemente efectiva para ciertas tareas de un agente, pero no se puede escalar para entornos de tamaño ilimitado, a causa de su falta de poder expresivo para manejar el tiempo de forma precisa, el espacio, o patrones genéricos de relaciones entre objetos.
Inte
lig
en
cia
Art
ificia
l e I
ng
en
ieri
a d
el
Con
ocim
ien
to
83 de 110Septiembre de 2007
Ejercicios
Ejercicio1: Dado el juego del buscaminas con una matriz de 4x4 y 3 minas situadas de forma aleatoria, establecer:
– El modelo REAS del buscaminas.
– Las reglas que componen la BC inicialmente.
– Y una simulación del juego que acabe en éxito, mostrando las reglas que componen la BC final.
Ejercicio2: Dado el párrafo “Si el unicornio es un animal mitológico, entonces es inmortal, pero si no es mitológico, entonces es un mamífero mortal. Si el unicornio es inmortal o mamífero, entonces tiene cuernos. El unicornio es mágico si tiene cuernos”. Demostrar:
– El unicornio es un animal mitológico.
– El unicornio es un animal mágico.
– El unicornio tiene cuernos.
Universidad de Castilla-La Mancha
Luis Jiménez [email protected]
Luis Enrique Sánchez [email protected]