Source: http://slideplayer.es/slide/92109/
Timestamp: 2017-11-24 23:17:04+00:00

Document:
Publicada porPiedad Alejo Modificado hace 3 años
Sistemas Basados en Conocimiento Mg. Samuel Oporto Díaz
3 LOGICA PROPOSICIONAL Agentes Basados en Conocimiento.
Representación del Conocimiento. Sintaxis y Semántica de un Lenguaje Sintaxis Semántica Bibliografía
4 Objetivo Presentar a los agentes basados en conocimiento.
Exponer los conceptos acerca de la representación del conocimiento y el proceso de razonamiento. Exponer las técnicas para el diseño de agentes capaces de elaborar representaciones del mundo. Presentar los conceptos básicos de la lógica proposicional.
5 AGENTES BASADOS EN CONOCIMIENTO
6 Agentes Basado en Conocimiento
Un agente basado en conocimiento (ABC) es aquel sistema que posee conocimiento de su mundo y que es capaz de razonar sobre las posibles acciones que puede tomar para cambiar el estado de su mundo. El agente es un conjunto de sentencias, representado mediante un lenguaje de representación de conocimiento.
7 Agentes Basado en Conocimiento
8 Lenguaje + Inferencia = Lógica
Elementos Lenguaje de representación de conocimiento. Lenguaje formal de representación, se usará la lógica proposicional y más adelante la lógica de predicados. El conocimiento se representa mediante sentencias. Inferencia. Es la derivación de nuevas sentencias a partir de las sentencias almacenadas y nuevas percepciones. Adición de nuevo conocimiento (TELL) Consultas a la BC (ASK) Lenguaje + Inferencia = Lógica
9 Base de Conocimiento (KB)
Es la representación de un conjunto de hechos acerca del mundo. Cada hecho está representado por una sentencia u oración. LA BC tiene conocimiento previo, que corresponde al conocimiento no aprendido. Siempre que se ejecuta el programa del ABC, sucede dos cosas: El programa informa a la BC lo que percibe. El programa pregunta a la BC qué hacer, luego grabar la respuesta. La pregunta se responde mediante el razonamiento lógico.
10 Niveles de un ABC Nivel de conocimiento o epistemológico.
Es el nivel abstracto, describe qué es lo que el agente sabe. Corresponde al dominio del conocimiento (objeto de conocimiento). Nivel lógico. Es donde el conocimiento se codifica mediante oraciones o sentencias. Nivel de implementación. Es el que opera la arquitectura del sistema. Es donde se encuentra las representaciones físicas de las oraciones correspondientes al nivel lógico
11 Agentes Lógicos Se puede construir un agente basado en el conocimiento INFORMÁNDOLE todo lo que necesita saber. Si el lenguaje de representación facilita expresar este conocimiento mediante oraciones, el problema de la construcción se simplifica enormemente. A esto se le llama enfoque declarativo de la construcción de un sistema Prolog es un lenguaje declarativo que facilita la representación del conocimiento mediante oraciones. Es posible diseñar también mecanismos de aprendizaje que, dado un conjunto de percepciones, producen un conocimiento general del ambiente.
12 Ejercicio 1 Los agentes lógicos son automáticos, autónomos o ambos, explique su respuesta. ¿Qué lenguaje de representación de conocimiento existe? Indique cuatro ejemplos de representación de conocimiento mediante un lenguaje. ¿Qué conocimiento no es posible representar mediante un lenguaje? ¿Qué otro mecanismo de representación de conocimiento existe? Defina el concepto de sistemas conexionistas, en relación a los sistemas simbólicos.
13 REPRESENTACION DEL CONOCIMIENTO
14 Representación del Conocimiento
Expresar el conocimiento de forma que sea manejable por el computador, de modo que pueda ser utilizado como auxiliar para el desempeño de los agentes.
16 Representación del Conocimiento
El lenguaje consta de dos aspectos: Sintaxis. Explica las posibles configuraciones mediante las cuales se forma las oraciones o sentencias (lenguaje). La semántica. Determina los hechos del mundo a los que se hace alusión en las oraciones o sentencias. Si la semántica y la sintaxis están definidas de manera precisa, se dice que el lenguaje es una lógica.
17 Representación del Conocimiento
La conexión entre oraciones y hechos es algo que se establece mediante la semántica del lenguaje. La propiedad de que un hecho es decir la consecuencia de otros hechos, se refleja en la propiedad de que una oración es consecuencia de otras oraciones. La inferencia lógica genera nuevas oraciones que son consecuencia de oraciones ya existentes. implican Oraciones Oraciones Representación Semántica Semántica Mundo Hechos Hechos producen
18 SINTAXIS Y SEMANTICA DE UN LENGUAJE (Lógica Proposicional)
19 Sintaxis Un buen lenguaje de representación de conocimiento debe de combinar las ventajas de los lenguajes naturales y lenguajes formales: Debe ser lo suficiente expresivo y conciso para que nos permita expresar de manera sucinta todo lo que hay que decir. Debe ser inequívoco (no ambiguo) e independiente del contexto para su interpretación. Debe ser eficiente en el sentido de que debe existir un procedimiento de inferencia que permita obtener nuevas inferencias a partir de oraciones en nuestro idioma.
20 Ejemplos de Lenguajes Lenguajes de programación (C, Pascal, Lisp, etc.) Son idóneos para representar algoritmos y estructuras de datos concretas: Mundo[2,2]  precipicio. El problema es que están diseñados para describir cabalmente el estado de la computadora y de cómo cambiar ésta conforme el programa se va ejecutando ¿Qué pasa cuando la información es incompleta o hay incertidumbre? En estos casos estos lenguajes no son lo suficientemente expresivos. Lenguajes naturales (español, inglés, francés, quechua….) Son expresivos El significado de una oración depende tanto de la oración como del contexto en que se produce. Son ambiguos : “pequeños perros y gatos” vs. “-d + c”.
21 mensajes en código enviados de un espía a otro.
Semántica En lógica, el significado de una oración es aquello que se afirma del mundo, que el mundo sea de una forma. Para entender una oración, quien la escriba tiene que proporcionar su respectiva interpretación. Ninguna oración tiene significado por sí misma. mensajes en código enviados de un espía a otro. Los lenguajes que nos interesan son todos compositivos o de composición: el significado de una oración es función del significado de sus partes. El significado de “x2+y2” está relacionado con los significados de x2 y y2 Una vez que mediante la semántica se interpreta una oración, ésta puede ser cierta o falsa. Una oración es cierta dentro de una interpretación deter-minada si el estado de asuntos que representa es cierta.
22 Sintaxis y Semántica Sintaxis Semántica Conjunción (Λ).
Disyunción (V) Implicación Premisas Conclusión. Equivalencia Negación. Sentencias Atómicas Sentencias Completas Semántica Tabla de verdad. Validez e inferencia Modelos Reglas de inferencia
23 SINTAXIS     
24 Símbolos Los símbolos usados en la lógica propositiva son:
25 Oraciones Un conjunto de palabras con sentido gramatical.
La oración es la mínima unidad comunicacional, con significado completo. Esto significa que es el fragmento más pequeño del enunciado que comunica una idea total, y posee independencia (es decir, podría sacarse del contexto y seguir comunicando, no lo mismo, pero algo). En la lógica, es la unidad de análisis fundamental.
26 Ejercicio 3 Diga cuales de las siguientes expresiones son oraciones:
Luís y Marta van de pesca. ¡siéntate! ¡siéntate! Le dijo Yaku a su maquisapa. El autobús pasa a las seis Mañana lloverá. ¡Llovió! Llovió pregunto Julia a su padre Luís llamó a Marta para salir. ¿cuándo sale el autobús? ¿fueron a pescar Luis y Marta finalmente?
27 Sintaxis Conjunción (Λ) (y). A la oración cuyo conector principal es  (y) se le llama conjunción, y a sus partes se les llama coyuntos. Disyunción (V) (o). A la oración cuyo conector principal es  (o) se le llama disyunción, y a sus partes se les llama disyuntos. Implicación (). Una oración como P  R se conoce como implicación (o condicional), su premisa o antecedente es P y su conclusión o consecuente es Q. A las implicaciones también se les llama reglas o aseveraciones si-entonces. Premisas. Son los antecedentes de una implicación. Premisa1:	Si un libro es sobre ordenadores entonces es terriblemente aburrido Premisa2:	Éste es un libro sobre ordenadores Conclusión:	Este libro es terriblemente aburrido
28 Sintaxis Conclusión. Equivalencia. Negación  (no).
29 Ejercicio 4 Formaliza las siguientes proposiciones:
30 Ejercicio 4 [B me gusta bailar]. ¬(¬B)
[B me gusta bailar. C me gusta leer libros de ciencia ficción]. B Λ C [G los gatos de mi hermana sueltan pelo. A me gusta acariciar los gatos ]. ¬G  A [M ver un marciano con mis propios ojos. E creer en los extraterrestres ]. M ⇔ E [P salir a dar un paseo. E estudiar como un energúmeno]. P V E [E los elefantes vuelan. T los elefantes tocan él acordeón. L estar loco. P internar en un psiquiátrico ]. ( E V T ) ⇒ ( l Λ P) [ V ir de vacaciones. N no hacer nada. T tener tiempo. I ir a trabajar]. (T Λ ¬I ) →(V V N )
31 Ejercicio 5 Formaliza la siguientes proposición:
32 [(J Λ T)  (I  N)] Λ [(-I  -J) V D]
Ejercicio 5 J. Justificar hechos T. Enorme tradición. I. hechos inofensivos y respetan a todo ser vivo y al medio ambiente N. no hay problema D. dignos de nuestro tiempo [(J Λ T)  (I  N)] Λ [(-I  -J) V D]
33 Ejercicio 6 Formaliza la siguientes proposición:
Mary puede escribir el programa en Fortran o Pascal o de plano no escribirlo. Si no escribe el programa sacará cero y reprobará el curso. Si reprueba el curso será puesta en el padrón de jalados y si se saca cero su novio la dejará. Si Mary escribe el programa en Fortran reprobará el curso pero si lo escribe en Pascal pasará.
34 (PVQVR) Λ (PVQ¬R) Λ(R(S ΛT) Λ(TU) Λ(QT) Λ(P¬T)
Ejercicio 6 P: Mary escribe el programa en Pascal Q: Mary escribe el programa en Fortran R: Mary no escribe el programa S: Mary saca un cero T: Mary reprueba el curso U: Mary es puesta en el padrón de jalados V: El novio de Mary la deja. (PVQVR) Λ (PVQ¬R) Λ(R(S ΛT) Λ(TU) Λ(QT) Λ(P¬T)
35 Ejercicio 7 Traduce los siguientes razonamientos a lógica proposicional y luego intenta demostrar si la conclusiones son o no consecuencia lógica de las premisas. Tendremos clases solo si el profesor ha venido y si hay proyector de transparencias o si hay tiza en la sala No hay proyector de transparencias y María no trajo tiza No tendremos clases Si crío ñus entonces si estos salen ágiles, aprenderé chino Los ñus no salen ágiles a menos que pasten junto a las vacas Nunca aprenderé chino No crío ñus
36 Ejercicio 7 Si manejo ebrio a las 6:00 PM en la Vía Expresa y no choco, los políticos serán honestos. Si los políticos son honestos entonces DEVIDA es buena eliminando la cocaína del mercado NNAA. DEVIDA es malísima eliminando la cocaína del mercado NNAA Los políticos son honestos O bien Toledo deja el gobierno o bien las protestas aumentan. Si las protestas aumentan, los políticos se esconden o Susy Díaz toma el poder. Para que Susy Díaz tome el poder es necesario que todos los alumnos aprueben el curso de IA o que Toledo deje el poder. Toledo deja el poder Susy Díaz toma el poder
37 SEMÁNTICA α β
38 Tablas de Verdad P Q P P  Q P  Q P  Q P  Q F V
39 Validez e inferencia Se puede obtener la validez de una oración compleja de la siguiente manera: P H P  H (P  H)  P ((P  H)  P )  P F V
40 Validez, Satisfabilidad, Contradicción
Si en la tabla de verdad se obtiene todas VERDAD Contradicción. Si en la tabla de verdad se obtiene todas FALSE Satisfabilidad. Si en la tabla de verdad se obtiene al menos una VERDAD Contingencia. Si no se tiene suficiente información para llegar a una conclusión
41 Modelo Un mundo en el que una oración es verdadera de acuerdo con determinada interpretación se denomina modelo de dicha oración bajo tal interpretación. Los modelos son muy importantes para la lógica, puesto que una oración  es implicación de una base de conocimientos BC cuando los modelos de BC también son todos modelos de . Siendo este el caso, siempre que BC sea verdadera, también  será verdadera.
42 Reglas de Inferencia La inferencia lógica es un proceso mediante el que se implanta la relación de implicación que existe entre dos oraciones. Existen ciertos patrones de inferencia que se presentan una y otra vez, lo que permite establecer de una vez por todas su confiabilidad. La regla permite evitar pasar por las tablas de verdad. α |= β, que significa que β se puede obtener desde α mediante inferencia.
43 Reglas de Inferencia Modus Ponens Y-Eliminación Y-Introducción.
44 Ejercicio 8 Use la tabla de verdad para determinar si las siguientes expresiones son validas, contradictorias o satisfactibles o contingentes. (p → q) ↔ ¬p V q ¬(p Λ q) ↔ ¬p V ¬q ¬(p V q) ↔ ¬p Λ ¬q (p → q) → (q → p) (p → q) → (¬q → ¬p) (q → ((p Λ ¬p) → ¬r)) → ((q → (p Λ ¬p)) → (q → ¬r)) (p V (p Λ q)) ↔ p (p Λ (p V q)) ↔ ¬p (p Λ (p → q)) ↔ p
45 Bibliografía AIMA. Capítulo 6, primera edición.
46 INFERENCIA EN LÓGICA PROPOSICIONAL
Reglas de Inferencia Formas Canónicas Probador de Teoremas Ejercicios Anexo Bibliografía
47 Objetivos Exponer los mecanismos de inferencia
Presentar las reglas de inferencia. Presentar el concepto del probador de Teoremas
48 INFERENCIA ¿y ahora qué hago?
49 Inferencia Según la filosofía existen tres modos básicos de razonamiento: Deducción. inferencia desde las causas hacia los efectos, o desde lo universal hacia lo particular. Inducción. Recorre el camino inverso. Abducción o retroducción. Relacionado con la génesis de la hipótesis Inferencia Deductiva o analítica Sintética Inducción Hipótesis
50 Mecanismo de Inferencia
51 Inferencia Razonamiento “robusto”, inferencia lógica, deducción Procedimiento que calcula la validez de sentencias Una sentencia es valida si y solo si es verdadera para todas las interpretaciones en todos los mundos posibles (sentencias analíticas, tautologías) No hay limite en la complejidad de las sentencias No importa la interpretación que se este utilizando Un proceso de inferencia confiable se denomina demostración Δ |=ρ ω desde Δ se obtiene ω ρ : reglas de inferencia Δ : conjunto de fórmulas bien formada Ω: teoremas que se pueden deducir desde Δ
52 Regla de inferencia Patrón de inferencias que se presenta constantemente Si se prueba su robustez una vez, se puede extender a cualquier caso Se utilizan para hacer inferencias sin tener que construir tablas de verdad
53 REGLAS DE INFERENCIA Reglas + Observaciones Δ |=ρ ω
54 Reglas de inferencia Modus Ponens : a  b, a b
Modus Tollens: a  b, -b -a Eliminación-y : a1  a2 …. an ai Introducción-y: a1, a2, ….,an a1  a2 …. an Introducción-o:_____ai_________ a1  a2  ….  an Eliminación-doble-negación: ~~a a Resolución Unitaria: a b, ~b Resolución: a b, ~b  c	~a  b, b c a  c ~a  c
55 Ejercicio 1 ¿Cómo se puede demostrar que una nueva regla de inferencia es válida?
56 FORMAS CANONICAS
57 Forma Normal Clausal Un literal es una variable proposicional o una variable proposicional negada (o sea, con el símbolo ¬ delante). En el primer caso diremos que es un literal positivo, y, en el segundo, que es un literal negativo. Una cláusula es una sentencia de la forma: L1 V L2 V Ln donde los Li son literales y están unidos por disyunciones. Una sentencia está en forma clausulada si tiene la forma: (L11 V L12 V...) Λ (L21 V L22 V..) Λ ...
58 Conversión a Forma Clausal
1.	Eliminar condicionales y bicondicionales: A  B ≡ ¬A V B A  B ≡ (A  B) Λ (B  A) ≡ (¬A V B) Λ (¬B V A) 2.	Introducir negaciones mediante las equivalencias (1) (doble negación), (2) y (3) (de Morgan): ¬(¬A) ≡ A ¬(A V B) ≡ ¬A Λ ¬B ¬(A Λ B) ≡ ¬A V ¬B 4.	Distribuir las Λ con la equivalencia: L1 V (L2 Λ L3) ≡ (L1 V L2) Λ (L1 V L3)
59 Ejemplo G Λ (R => F) Paso 1: G Λ (¬R V F) Paso 2: no es necesario
Paso 2:	¬(G Λ ¬(R Λ ¬F)) ¬G V ¬¬(R Λ ¬F) ¬G V (R Λ ¬ F) Paso 3:	(¬G V R) Λ (¬G V ¬F)
60 Ejercicio 2 Convertir a la FNC las siguientes expresiones:
(A Λ (B V C) Λ (EA)) V D [(A(BVE)) Λ (C(DVF))] V [((AVB)E) Λ ((CVD)F)] (A Λ B Λ C Λ D) V (B Λ C Λ D Λ E ) S  (P  (Q V R)) (P  (Q V R)) Λ (P V Q) Λ R (R V Q V P)  (P Λ Q) (R Λ (Q V P))  (P  Q)
61 PROBADOR DE TEOREMAS
62 Probador de Teoremas [BD Λ ¬P(x)  Falso]  [BD  P(x)] Conocido como:
Refutación. Demostración por contradicción Reducción al absurdo Consiste en que para demostrar P(x), suponemos que P(x) es falsa (se añade –P(x) a la BD) y se demuestra la contradicción [BD Λ ¬P(x)  Falso]  [BD  P(x)]
63 Ejemplo Supongamos que tu me quieres, si me quieres entonces debemos ser fieles, pero no me has sido fiel, por lo tanto no me quieres. Supongamos que eres un excelente congresista, si eres un excelente congresista entonces debes plantear leyes de alcance nacional, pero siempre te preocupas de los problemas eventuales, entonces eres un pésimo congresista. Si eres un buen hijo, entonces siempre debes de hacerle caso a la mamá, pero nunca le haces caso a la mamá, por lo tanto no eres un buen hijo.
65 Ejercicio 3 Si pedro le apostó a Pittsburg, entonces se gastó el dinero. Si Pedro se gastó el dinero entonces su esposa no compra joyas y su esposa pide divorcio. Si su esposa no compra joyas, entonces los niños no comen o la esposa está enojada. Pedro le apostó al Pittsburg Los niños comen por lo tanto su esposa está enojada.
66 Ejercicio 3 P: Pedro le apostó a Pittsburg
Q: Pedro se gastó el dinero. R: Su esposa no compra joyas S: Su esposa pide divorcio T: Los niños comen U: Su esposa está enojada 1.	PQ 2.	QR Λ S 3.	R¬T V U 4.	P 5.	T  U 7.	Q	modus ponens (1, 4) 8.	R Λ S	modus ponens (2, 7) R	y – eliminación (8) ¬T V U	modus pones (3, 9) 11.	T  U	ley implicación
67 Ejercicio 4 Establezca la siguiente expresión en lógica proposicional y diga si es posible llegar a la conclusión indicada: Para que el país salga adelante, se requiere de empresas. Para hacer una empresa se requiere inversión. Para invertir se requiere dinero Si tengo una empresa entonces tengo dinero Si eres peruano no tienes dinero Si eres extranjero tienes dinero Soy peruano El país no sale adelante
68 Ejercicio 5 Establezca la siguiente expresión en lógica proposicional y diga si es posible llegar a la conclusión indicada: Si quiero bajar de peso, debo comer a la hora, hacer ejercicio, dormir bien y no ver TV más de 1 hora al día. Para dormir bien, debo hacer ejercicios. Para ver TV 1 hora, debo dormir bien. Siempre hago ejercicios No bajo de peso
69 Ejercicio 6 Establezca la siguiente expresión en lógica proposicional y diga si es posible llegar a la conclusión indicada: Para que la USMP salga adelante se requiere de buenos profesores y de buenos alumnos. Los buenos profesores aparecen si hay buenos sueldos, buenos laboratorios y capacitación constante. Para tener capacitación constante se requiere buenos profesores. Los buenos profesores generan nuevos proyectos Los nuevos proyectos generan recursos propios Los recursos propios generan buenos sueldos Todos los alumnos son buenos Hay capacitación constante. La USMP sale adelante
70 Ejercicio 7 Establezca la siguiente expresión en lógica proposicional y diga si es posible llegar a la conclusión indicada: Para terminar la USMP, debo aprobar todos mis cursos. Para aprobar mis cursos, debo estudiar y ser inteligente. Para estudiar debo tener dinero y tiempo. Soy inteligente Tengo dinero pero no tiempo Termino la USMP
71 Ejercicio 8 Establezca la siguiente expresión en lógica proposicional y diga si es posible llegar a la conclusión indicada: Si la banda no toca Rock and Roll, o las bebidas no llegan a tiempo, entonces la fiesta se cancela y Alicia está enojada. Si la fiesta se cancela entonces hay que regresar el dinero de las entradas. No se regresó el dinero de las entradas. Por lo tanto, la banda toca Rock and Roll.
72 Ejercicio 9 Dado los siguientes axiomas: (1). P (2). (P  Q)  R
(3). (S  T)  Q (4). T Probar por refutación: R
73 Ejercicio 9 Convirtiendo a la forma canónica FNC (1). P P
(2). (P  Q)  R	P  Q  R (3). (S  T)  Q	S  Q (4). T  Q (5). T	T Introduciendo la proposición a probar (6) ¬R
74 Ejercicio 9 Aplicando reglas de inferencia (resolución) P  Q  R R
T  Q Q  T T nil
75 Ejercicio 10 Demostrar que (τΛχ),(τν),(χω) |= (vΛω)
76 Ejercicio 10
77 Ejercicio 11 ~S11 ~S21 S12 ~B11 B21 ~B12 R1: ~S11  ~W11  ~W12  ~W21
78 ANEXO
79 Forma Normal Conjuntiva
Se supone que todas las disyunciones (V) de la BC se agrupan en una conjunción (Λ) implícita grande, por lo que a esta forma se le denomina forma normal conjuntiva (CNF), aún cuando cada oración en particular es una disyunción (V) Forma Normal Conjuntiva ¬P V Q P Forma Normal Implicativa P  Q Verdad  P
80 Formas Canónicas Forma normal conjuntiva (CNF). Disyunción de literales. Forma normal implicativa (INF). Conjunciones en la izquierda que implica las disyunciones en el derecho. La CNF es más común, pero la INF es más "natural" para el análisis humano. Original KB CNF INF " x P(x) Þ Q(x) ØP(w)Ú Q(w) P(w) Þ Q(w) " x ØP(x) Þ R(x) P(x) Ú R(x) True Þ P(x) Ú R(x) " x Q(x) Þ S(x) ØQ(y)Ú S(y) Q(y) Þ S(y) " x R(x) Þ S(x) ØR(z)Ú S(z) R(z) Þ S(z) A, A Þ B Û True Þ A, A Þ B B True Þ B
81 Bibliografía AIMA. Capítulo 6, primera edición.
82 LOGICA DE PREDICADOS Lógica de Predicados. Sintaxis
Fórmulas Bien Configuradas Bibliografía
83 Objetivos Presentar los conceptos básicos de la lógica de predicados.
84 LOGICA DE PREDICADOS Lógica de Primer Orden
85 Lógica de Predicados Lógica de primer orden.
86 Lógica de Predicados Está basada en la idea de que las sentencias realmente expresan relaciones entre objetos, así como también cualidades y atributos de tales objetos. Los objetos pueden ser personas, objetos físicos, o conceptos. Las cualidades, relaciones o atributos, se denominan predicados. Los objetos se conocen como argumentos o términos del predicado. Al igual que las proposiciones, los predicados tienen un valor de veracidad, pero a diferencia de las preposiciones, su valor de veracidad, depende de sus términos. Un predicado puede ser verdadero para un conjunto de términos, pero falso para otro.
87 Ejercicio 1 Para las siguientes oraciones indique donde existe una relación y donde un atributo. Aijo vive en la misma casa que Chucho. Tuka y Pika vuelvan. Yaku y Amarú vuelan juntos. A + B A + B = C f(A) f(A) = φ, f(B) = Φ y f(C) = Ω Ana 17 años, Erika 19 años, Julia 18 años Ana, Erika y Julia van a la universidad Edo administra la empresa donde Rai trabaja.
88 Predicado Un predicado es lo que se afirma del sujeto. Predicado.
89 Proposiciones y Predicados
90 Ejemplos Objetos: personas, casas, números, la SUNAT, USMP, colores, guerras, siglos, Relaciones: diferente_que, hermano-de, cerca_de, amigo_de, de_color, hijo_de_y_padre_de, vive_en, es_el_dueño. Propiedades: Rojo, redondo, pisos, Funciones: el_siguiente, mayor_que, sumatoria,
91 Ejercicio 2 Identifique para las siguientes expresiones el sujeto y el predicado. Indique el tipo de predicado: Uno más dos es igual a tres Los cuadros cercanos al wumpus apestan Wayra vive en la provincia de condorcanqui y chaccha coca. Todos los gatos comen ratones y los ratones comen quesos. Ayer, hoy y mañana son días festivos.
92 Aplicaciones Especificación formal de programas, la cual permite describir lo que el usuario desea que un programa realice, mediante piezas de código. Verificación formal de programas, las piezas de código son acompañadas por pre y post condiciones, las cuales se escriben como fórmulas del Cálculo de Predicados.
93 SINTAXIS       
94 Sintaxis (1) El alfabeto está formado por: Sentencia atómica:
95 Sintaxis constantes lógicas: Verdadero, Falso
96 Sintaxis Oraciones atómicas
97 Sintaxis Oraciones Mediante los conectores lógicos se pueden construir oraciones más complicadas, ejemplo: Hermano (Ricardo, Juan)  Hermano (Juan, Ricardo) Mayor (Juan, 30)  Menor (Juan, 30) Mayor (Juan, 30)  Menor (Juan, 30) Hermano (Robin, Juan)
98 Sintaxis Términos. Es una expresión lógica que se refiere a un objeto.
99   Cuantificadores Cuantificadores
100 Cuantificación universal ()
101 Ejercicio 3 Representa en LP1 las siguientes expresiones:
102 Cuantificación existencial ()
103 Ejercicio 4 Representa en LP1 las siguientes expresiones:
104 Cuantificadores anidados
105 Ejercicio 5 Representa en LP1 las siguientes expresiones:
106 Ejercicio 6 Algunos estudiantes llevaron Chino en el verano
107 Solución  x [estudiante(x)  llevo_curso (x, Chino, Verano)]
108 FORMULAS BIEN CONFIGURADAS
109 Fórmula bien configurada
110 Bibliografía AIMA. Capítulo 7, primera edición.
111 INFERENCIA EN LOGICA DE PREDICADOS
Sustitución. Unificación Reglas de Inferencia con Cuantificadores Resolución Ejercicios Bibliografía
112 Objetivos Exponer los mecanismos de inferencia en lógica de Predicados. Presentar los conceptos de Sustitución y Unificación. Ampliar la técnica de Resolución a la Lógica de Predicados Exponer las reglas de inferencia con cuantificadores. Exponer las formas canónicas de la resolución. Exponer los conceptos del probador de teoremas (refutación)
113 SUSTITUCION
114 Término Base (Ground term)
El término base es: Una constante Taki Al-Sadar Mallcu Al-Kadem El resultado de una función donde todas sus entradas son términos base. loriana(Lunes) policia(Asiri)
115 Sustitución Se utilizará la notación SUST(, ) para representar el resultado de aplicar la sustitución (o lista de enlace)  a la oración , por ejemplo:  = {x/Juan, y/CursoIA}  = ConcurreA(x, y)  GustaDe(x, y) subst( {x/Juan, y/CursoIA} , ConcurreA(x, y)  GustaDe(x, y) ) ≡ ConcurreA(Juan, CursoIA)  GustaDe(Juan, CursoIA) Juan concurre a curso de IA y Juan gusta de curso de IA.
116 Sustitución Dadas las variables x1, x2, ..., xn y los términos t1, t2, .., tn (sin variables), la sustitución θ es un conjunto de pares ordenados: θ = {x1/t1, x2/t2,..,xn/tn} (x/t se lee sustituir x por t) La operación consiste en, dado un literal α que contiene x1, x2, .., xn, y una sustitución θ, reemplazar en todos los lugares de α donde aparezca xi por ti. Ejemplo: subst({X/george, Y/tony} , likes(X,Y)) = likes(george, tony) Los términos de θ no pueden contener símbolos de constantes ni de función que ya estén en α
117 Sustitución Sustitución vacía {}, cuando no modifica la expresión.
Composición de la sustitución. Es una sustitución tal que αθ1 θ2=(αθ1) θ2. La composición de sustituciones es asociativa (θ1 θ2)θ3 = θ1(θ2 θ3) Pero no conmutativa θ1θ2≠θ2θ1 No se puede calcular la composición resultante uniendo simplemente los conjuntos θ1 y θ2, hemos de aplicar primero θ2 a los términos de θ1 y después añadir los pares de θ2 cuyas variables no están entre los de θ1.
118 Ejercicio 1 Diga que se obtiene al aplicar SUST(, ) en los siguientes casos:  = monopolio(M) penalizado(M)  = {M/LosGarcia}  = realiza(M,W)  feo(W)  odiado(M)  = {M/Hormel, W/Spam}  = presidente(X)inteligente(X)  = {X/Bush}
119 Ejercicio 1 subst( {M/LosGarcia}, monopolio(M)  penalizado(M) )
subst( {M/Hormel,W/Spam},realiza(M,W)feo(W)odiado(M)) subst( {X/Bush}, presidente(X)inteligente(X))
120 Ejercicio 2 Sean: α = F1(x,y), F2(y,w), F3(x,y,z,r)
θ1 = (x/a, y/b, z/w), θ2 = (w/c), θ3 = (r/b) Calcular: αθ1θ2θ3 αθ1 = F1(a, b), F2(b,w), F3(a, b, w, r) αθ1θ2	= F1(a, b), F2(b,c), F3(a, b, c, r) αθ1θ2θ3	= F1(a, b), F2(b,c), F3(a, b, c, c)
121 Ejercicio 2 Calcular: θ4 = (θ1θ2)θ3 y luego αθ4
θ1 = (x/a, y/b, z/w), θ2 = (w/c), θ3 = (r/b) θ12= (x/a, y/b, z/c) θ4 = (x/a, y/b, z/c, r/b) αθ4 = F1(a,b), F2(b,w), F3(a,b,c,b) Calcular: θ4 = θ1(θ2θ3) y luego αθ4 θ23= (w/c, r/b)
122 UNIFICACION
123 Unificación Lo que hace la rutina de unificación UNIFICAR es convertir dos oraciones α y β en una sustitución mediante la cual α y β resultan idénticas. De no existir tal unificación, UNIFICAR produce una falla. Formalmente: UNIFICAR(α, β) = , donde SUST(, α) = SUST(, β)  se conoce como el unificador de las dos oraciones.
124 Unificación Supongamos que tenemos la regla
conoce(juan,X)  odia(juan,X) “Juan odia a todos los que conoce” Y la queremos utilizar como regla de inferencia de Modus Ponens y poder saber a quién odia Juan. Es decir, tenemos que saber a qué oraciones de la base de conocimiento se unifican a conoce(juan,X). Supongamos que nuestra base de conocimiento contiene: conoce(juan,jane)	▪ conoce(Y,leónidas) conoce(Y,madre(Y))	▪ conoce(X, isabel)
125 Unificación Al unificar el antecedente de la regla con cada una de las oraciones de la BC obtenemos: conoce(juan,X)  odia(juan,X) UNIFICAR(conoce(juan, X),conoce(juan, jane)) = {X/jane} UNIFICAR(conoce(juan, X),conoce(Y, leónidas)) = {X/leónidas, Y/Juan} UNIFICAR(conoce(juan, X),conoce(Y, madre(Y))) = {Y/juan, X/madre(juan)} UNIFICAR(conoce(juan, X),conoce(X, isabel))= falla conoce(juan,jane) conoce(Y,leónidas) conoce(Y,madre(Y)) conoce(X, isabel)
126 Unificación La última unificación falla, porque X no puede tomar el valor de juan e isabel al mismo tiempo. De manera intuitiva, sabemos que Juan odia a todos los que conoce, y que todos conocen a Isabel, por lo que podríamos inferir que Juan odia a Isabel. Para resolver este problema, se pueden normalizar por separado las dos oraciones que se van a unificar, lo que significa renombrar las variables de una de ellas (o de ambas) para evitar que haya repetición de nombres: UNIFICAR(conoce(juan,x1),conoce(x2,isabel))={x1/isabel, x2/juan}
127 Ejercicio 3 Unifique y resuelva. femenino(ana) padre (juan, ana)
femenino(X) Λ padre (Y, X)  hija(X, Y)
128 Ejercicio 3 femenino(ana) padre (juan, ana)
femenino(X) Λ padre (Y, X)  hija(X, Y) femenino(ana) femenino(X) Λ padre (Y, X)  hija(X, Y) θ1 = {X/ana} padre (juan, ana) padre(Y,ana)  hija(ana,Y) θ2 = {Y/juan} hija(ana, juan)
129 Ejercicio 4 Para cada uno de los siguientes pares de oraciones, indique el unificador más general, o diga que no existe y explique por qué. El unificador más general es el que permite que pocas variables o funciones no sean cambiadas a constantes como sea posible. P(x, y, y) y P(A, f(B), f(z)) P(x, F(x), A) y P(y, y, z) P(x, y, z) y Q(A, B, B) Q(x, F(y, A), z) y Q(A, F(A, A), x) Q(x, G(y, y), w, F(z, z)) y Q(H(u, v), v, A, F(x, y))
130 Ejercicio 5 Intente unificar los siguientes pares de expresiones, use el unificador más general y explique en los casos que no se pueda, ¿por qué no se pueden unificar? p(X, Y, Z) p(X, a, b) p(X, Y, Z, c) p(X, a, b, W) P(X, Y, Z, W)	p(Y, Y, W, Z) q(X, Y, c)	q(Y, Y, X) p(X, Y) ¬ p(X, Z) p(X, Y, Z, W, a) p(b, X, d, a, Y) r(X, G(X), Y, P(Y)) r(Y, G(X), Z, W)
131 REGLAS DE INFERENCIA CON CUANTIFICADORES
132 Reglas de Inferencia en LP1
Reglas de inferencia utilizadas en lógica proposicional: También son válidas en la lógica de primer orden, pero se requieren reglas de inferencias adicionales para manejar las oraciones de lógica de primer orden con cuantificadores: Eliminación Universal Eliminación Existencial Introducción Existencial. Modus ponens Y-eliminación Y-introducción O-introducción Doble negación eliminación Resolución unitaria Resolución Modus Tollens
133 Eliminación Universal
Para toda oración , variable v y una variable v: Por ejemplo, en x le_gusta(x, helado), podemos utilizar la sustitución {x/x} e inferir que: le_gusta(x, helado). Permite eliminar el cuantificador  v  SUST({v/v},)
134 Eliminación Existencial
Para toda oración , variable v y símbolo constante k que no aparezca en ninguna parte de la base de conocimientos: Por ejemplo, en x matar(x, víctima), podemos inferir que matar(asesino, víctima) en tanto que asesino no aparezca en ninguna parte de la base de conocimientos. v  SUST({v/k},) Es importante que la constante k usada para la sustituir la variable sea una variable nueva
135 Introducción Existencial
Para toda oración , variable v que no esté en  y término de base g que no esté presente en : Por ejemplo, en le_gusta(jerry,helado) podemos inferir que X le_gusta(X, helado).  v SUST({g/v},)
136 RESOLUCION
137 Resolución forma clausal = forma clausulada
Es un mecanismo de prueba que opera sobre estatutos que han sido convertidos a forma clausal y produce pruebas por refutación, es decir que para probar si un estatuto es verdadero (demostrar que es válido ) intenta mostrar que la negación de ese estatuto produce una contradicción. forma clausal = forma clausulada CNF : conjuntive normal form
138 Resolución La resolución fue introducida como una regla de inferencia
Resume muchos esquemas de inferencia clásicos. Es un procedimiento completo de inferencia, por que solo con ella pueden diseñarse sistemas deductivos consistentes y completos. Se aplica a sentencias que tienen que estar escritas forma clausulada. Para toda sentencia se puede encontrar una sentencia equivalente en forma clausulada.
139 Aplicación de la regla de resolución
Si recordamos la regla de inferencia de resolución: a V b, ~b V c a V c Se puede aplicar a dos cláusulas cualesquiera que compartan un literal con distinto signo. Estas cláusulas le llaman generatrices (padre), y la conclusión, cláusula resultante de la disyunción del resto de literales, resolvente. Todas las sentencias deben estar en forma clausulada. Si hay n premisas inicialmente en Δ0, al ponerlas en forma clausulada resultarán m cláusulas (m > n), y la estrategia de control se reduce al problema de decidir, en cada Δi, a qué pareja de cláusulas aplicar una regla de resolución única, la regla de resolución.
140 Aplicación de la regla de resolución
La propiedad extraordinaria de la regla de resolución es que casi todas las reglas de inferencia se reducen a ella si previamente se escriben las premisas en forma clausulada. Forma Normal Implicativa Modus Ponens P  Q P	Q Modus Tollens	P  Q ¬Q ¬P Encadenamiento	P  Q Q  R P  R Forma Normal Conjuntiva Modus Ponens ¬P V Q P Q Modus Tollens	¬ P V Q ¬Q ¬P Encadenamiento	¬P V Q ¬Q V R ¬P V R
141 Aplicación de la regla de resolución
Asumir que se tienen un conjunto de cláusulas F y el estatuto a probar P Convertir todos los estatutos de F a la Forma clausal Negar P y convertirla a forma clausal. Agregar al conjunto de cláusulas obtenidas en el paso anterior Repetir hasta que una contradicción sea alcanzada: Seleccionar dos cláusulas y llamarlas cláusulas padre Resolverlas. Para obtener la cláusula llamada resolvente. Buscar en las cláusulas padre un par de literales T1 y T1 de tal forma que T1 pertenece a una y T1 a la otra, eliminar ambas literales y crear el resolvente. Si el resolvente es la cláusula vacía (FALSE), la contradicción ha sido encontrada. De otra manera el resolvente se agrega al conjunto de cláusulas.
142 Ejemplo Axiomas: Es ilegal que un turista venda huacos en Rusia
x,y Turista(x) Λ huacos(y) Λ Vender(x,y)=>Infractor(x) Sumac es un turista en Rusia Turista(Sumac) Cada uno de los turistas en Rusia venden algunos huacos x,y Turista(x) Λ Huacos(y) Λ Vende(x,y) ¿Es Sumac un infractor? Infractor(Sumac)
143 Ejemplo 1. Eliminación Universal
x,y Turista(x) Λ Huacos(y) Λ Vender(x,y)=>Infractor(x) Turista(x) Λ Huacos(y) Λ Vender(x,y)=>Infractor(x) x,y Turista(x) Λ Huacos(y) Λ Vende(x,y) Turista(x) Λ Huacos(y) Λ Vende(x,y)
144 Ejemplo 2. Aplicando resolución
Turista(x) Λ Huacos(y) Λ Vender(x,y)=>Infractor(x) Turista(x) Λ Huacos(y) Λ Vende(x,y) Turista(Sumac) Infractor(x) ¬Infractor(Sumac) FALSE
145 EJERCICIOS
146 Ejercicio 6 Unificar y resolver por Resolución. P(w) Q(w) Q(y)  S(y)
True  P(x) V R(x) R(z)  S(z)
147 Ejercicio 6 P(w) Q(w) Q(y)  S(y) True  P(x) V R(x) R(z)  S(z)
148 Ejercicio 7 Unificar y resolver por Resolución. -PhD(x) V HQ(x)
-HQ(x) V Rich(x) PhD(x) V ES(x) -ES(x) V Rich(x) Probar Rich(Me)
149 Ejercicio 7 -PhD(x) V HQ(x) -HQ(x) V Rich(x) PhD(x) V ES(x)
-ES(x) V Rich(x) Probar Rich(Me)
150 Ejercicio 8 x [y animal (y)  ama(x,y)]  [y ama(y,x)]
x [y animal (y) Λ mata(x,y)]  [z ¬ama(z,x)] x animal (x)  ama(Bush,x) mata(Bush,Fido) V mata(Wolfowitz,Fido) perro(Fido) x perro(x)  animal (x) Probar: mata(Wolfowitz, Fido) 7.	¬mata(Wolfowitz, Fido)
151 Ejercicio 8 Convirtiendo a lógica de predicados:
[animal (y)  ama(x,y)]  ama(G, x) [animal (H) Λ mata(x, H)]  ¬ama(z,x) animal (x)  ama(Bush,x) mata(Bush,Fido) V mata(Wolfowitz,Fido) perro(Fido) perro(x)  animal (x) 7.	¬mata(Wolfowitz, Fido)
152 Ejercicio 8 Convirtiendo a CNF: animal (y) V ama(G, x)
- ama(x, y) V ama(G, x) -animal (H) V -mata(x, H) V ¬ama(z, x) -animal (x) V ama(Bush, y) mata(Bush, Fido) V mata(Wolfowitz, Fido) perro(Fido) - perro(x) V animal (x) 8.	¬mata(Wolfowitz, Fido)
153 Ejercicio 8 perro(Fido) - perro(x) V animal (x)
- ama(x, y) V ama(G, x) -animal (x) V ama(Bush, x) animal (y) V ama(G, x) ¬mata(Wolfowitz, Fido) mata(Bush, Fido) V mata(Wolfowitz, Fido) -animal (H) V -mata(x, H) V ¬ama(z, x)
154 Ejercicio 9 man(Marcus) Pompeian(Marcus) x Pompeian(x)  Roman(x)
ruler(Caesar) x Roman(x)  loyalto(x, Caesar)  hate(x, Caesar) x y loyalto(x, y) xy man(x)  ruler(y) tryassassinate(x, y)¬loyalto(x, y) tryassassinate(Marcus, Caesar) ¿Marcus era fiel a César?
155 Bibliografía AIMA. Capítulo 8, primera edición.
AIMA. Chapter 9, second edition.

References: Resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 resolución 
 resolución

 resolución 
 resolución

 resolución 
 resolución

 resolución