![Page 1: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/1.jpg)
Inteligencia Artificial
Conocimiento y razonamiento
3. Lógica de primer orden
Dr. Edgard I. Benítez G. 1Inteligencia Artificial
3. Lógica de primer orden
Dr. Edgard Iván Benítez Guerrero
![Page 2: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/2.jpg)
Lógica de primer orden
� La lógica proposicional asume que el mundo tiene
hechos
� La lógica de primer orden asume que el mundo
contiene:
� Objetos: personas, casas
Dr. Edgard I. Benítez G. 2Inteligencia Artificial
� Objetos: personas, casas
� Relaciones: hermano de, mayor que, parte de, entre, …
� Funciones: suma, ..
![Page 3: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/3.jpg)
Sintaxis
� Constantes: John, 2, Inglaterra,...
� Predicados: Hermano, >,...
� Funciones: RaízCuadrada, PiernaIzquierdaDe,...
� Variables: x, y, a, b,...
� Conectores: ¬, ⇒, ∧, ∨, ⇔
Dr. Edgard I. Benítez G. 3Inteligencia Artificial
� Conectores: ¬, ⇒, ∧, ∨, ⇔� Igualdad: =
� Cuantificadores: ∀, ∃
![Page 4: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/4.jpg)
Sentencias atómicas
� Sentencia atómica
� predicado(término1,...,términon)
� termino1 = termino2
� Término
� Función (término1,...,términon)
Dr. Edgard I. Benítez G. 4Inteligencia Artificial
� Función (término1,...,términon)
� Constante
� Variable
� Por ejemplo:
� Hermano(John, Richard)
� >(Largo(PiernaIzqDe(Richard)),Largo(PiernaIzqDe(John)))
![Page 5: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/5.jpg)
Sentencias compuestas
� Hechas de sentencias atómicas usando conectores
¬S, S1 ∧ S2, S1 ∨ S2, S1 ⇒ S2, S1 ⇔ S2,
� Ejemplos:
� Hermano(John,Richard) ⇒ Hermano(Richard,John)
Dr. Edgard I. Benítez G. 5Inteligencia Artificial
� Hermano(John,Richard) ⇒ Hermano(Richard,John)
� >(1,2) ∨ ≤ (1,2)
� >(1,2) ∧ ¬ >(1,2)
![Page 6: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/6.jpg)
Semántica
� Sentencias son verdaderas con respecto a un modelo y a una
interpretación
� Un modelo contiene objetos (elementos del dominio) y
relaciones entre ellos
� Una interpretación define referentes para
� Símbolos constantes → objetos
Dr. Edgard I. Benítez G. 6Inteligencia Artificial
� Símbolos constantes → objetos
� Símbolos de predicado → relaciones
� Símbolos de función → relaciones funcionales
� Una sentencia atómica predicado(término1,...,términon) es
verdadera sii los objetos a los que se refieren
término1,...,términon están en la relación a la que se refiere
predicado
![Page 7: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/7.jpg)
Ejemplo de modelo
Dr. Edgard I. Benítez G. 7Inteligencia Artificial
![Page 8: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/8.jpg)
Cuantificación universal
� ∀<variables> <sentencia>
Todas las personas en Inglaterra son listas:
∀x En(x, Inglaterra) ⇒ Listo(x)
� ∀x P es verdadera en un modelo m sii P es verdadera
con x siendo cada posible objeto del modelo
Dr. Edgard I. Benítez G. 8Inteligencia Artificial
con x siendo cada posible objeto del modelo
� Vagamente hablando, esto es equivalente a la
conjunción de todas las posibles instanciaciones de PEn(John, Inglaterra) ⇒ Listo(John)
∧ En(Richard, Inglaterra ) ⇒ Listo(Richard)
∧ …
![Page 9: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/9.jpg)
Error común a evitar
� Típicamente, ⇒ es el conector principal para ∀� Error común: usar ∧ como el conector de ∀:
∀x En(x, Inglaterra) ∧ Listo(x)
significa “Todas las personas en Inglaterra y todas las personas
son listas”
Dr. Edgard I. Benítez G. 9Inteligencia Artificial
![Page 10: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/10.jpg)
Cuantificación existencial
� ∃<variables> <sentencia>
Alguien en Inglaterra es listo:
∃x En(x, Inglaterra) ∧ Listo(x)
� ∃x P es verdadera en un modelo m sii P es verdadera
con x siendo algún posible objeto del modelo
Dr. Edgard I. Benítez G. 10Inteligencia Artificial
con x siendo algún posible objeto del modelo
� Vagamente hablando, equivalente a la disyunción de
las instanciaciones de P
En(John, Inglaterra) ∧ Listo(John)
∨ En(Richard, Inglaterra ) ∧ Listo(Richard)
∨ ...
![Page 11: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/11.jpg)
Otro error común a evitar
� Típicamente, ∧ es el conector principal con ∃
� Error común: usar ⇒ como el conectivo principal de ∃:
∃x En(x, Inglaterra) ⇒ Listo(x)
Dr. Edgard I. Benítez G. 11Inteligencia Artificial
es verdadera si hay alguien que no está en Inglaterra !
![Page 12: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/12.jpg)
Propiedades de los cuantificadores� ∀x ∀y es lo mismo que ∀y ∀x
� ∃x ∃y es lo mismo que ∃y ∃x
� ∃x ∀y no es lo mismo que ∀y ∃x
� ∃x ∀y Ama(x,y)� “Hay una persona que ama a todos en el mundo”
Dr. Edgard I. Benítez G. 12Inteligencia Artificial
� “Hay una persona que ama a todos en el mundo”
� ∀y ∃x Ama(x,y)� “Todas las personas del mundo son amadas al menos por una persona”
� Dualidad de los cuantificadores: cada uno puede ser expresado usando elotro� ∀x Gusta(x,Helado) ¬∃x ¬Gusta(x,Helado)
� ∃x Gusta(x,Brocoli) ¬∀x ¬Gusta(x,Brocoli)
![Page 13: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/13.jpg)
Igualdad
� término1 = término2 es verdadera en cualquier
interpretación sii término1 y término2 se refieren al
mismo objeto
� E.g., definición de Hermano en términos de
Progenitor:
Dr. Edgard I. Benítez G. 13Inteligencia Artificial
Progenitor:
∀x,y Hermano (x,y) ⇔ [¬(x = y) ∧ ∃m,f ¬ (m = f) ∧Progenitor(m,x) ∧ Progenitor(f,x) ∧ Progenitor(m,y) ∧Progenitor(f,y)]
![Page 14: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/14.jpg)
Usando lógica de primer orden: el dominio familia
� El marido de una persona es un esposo masculino
∀x,y Marido(x,y) ⇔ (Masculino(x) ∧ Esposo(x,y))
� Una madre es el progenitor femenino de una persona
∀m,c Madre(c) = m ⇔ (Femenino(m) ∧ Progenitor(m,c))
Dr. Edgard I. Benítez G. 14Inteligencia Artificial
∀m,c Madre(c) = m ⇔ (Femenino(m) ∧ Progenitor(m,c))
� El abuelo es el padre del padre de uno
∀x,y Abuelo(x,y) ⇔ ∃z Padre(x,z) ∧ Padre(z,y)
![Page 15: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/15.jpg)
Instanciación universal (IU)
� Toda instanciación de una sentencia cuantificada
universalmente está implicada por ésta
∀v α
Subst({v/g}, α)
para cualquier variable v y término aterrizado g
Dr. Edgard I. Benítez G. 15Inteligencia Artificial
para cualquier variable v y término aterrizado g
� E.g., ∀x King(x) ∧ Greedy(x) ⇒ Evil(x) produce:
� King(John) ∧ Greedy(John) ⇒ Evil(John)
� King(Richard) ∧ Greedy(Richard) ⇒ Evil(Richard)
� King(Father(John)) ∧ Greedy(Father(John)) ⇒ Evil(Father(John))
![Page 16: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/16.jpg)
Instanciación existencial (IE)
� Para cualquier sentencia α, variable v, y símbolo constante k que no aparece
en ningún otro lado (constante de Skolem) en la base de conocimiento:
∃v α
Subst({v/k}, α)
Dr. Edgard I. Benítez G. 16Inteligencia Artificial
� E.g., ∃x Crown(x) ∧ OnHead(x,John) produce:
Crown(C1) ∧ OnHead(C1,John)
dado que C1 sea un nuevo símbolo constante
![Page 17: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/17.jpg)
Reducción a inferencia proposicional
� Supongamos que la BC contiene lo siguiente
∀x King(x) ∧ Greedy(x) ⇒ Evil(x)
King(John)
Greedy(John)
Brother(Richard,John)
� Instanciando la sentencia cuantificada de todas las formas posibles, se obtiene
Dr. Edgard I. Benítez G. 17Inteligencia Artificial
King(John) ∧ Greedy(John) ⇒ Evil(John)
King(Richard) ∧ Greedy(Richard) ⇒ Evil(Richard)
King(John)
Greedy(John)
Brother(Richard,John)
� La nueva BC es reducida a un conjunto de proposiciones
King(John), Greedy(John), Evil(John), King(Richard), etc.
![Page 18: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/18.jpg)
Problemas con la reducción a lógica proposicional
� La reducción genera muchas sentencias irrelevantes
� Por ejemplo, de:
� ∀x King(x) ∧ Greedy(x) ⇒ Evil(x)
� King(John)
Dr. Edgard I. Benítez G. 18Inteligencia Artificial
� ∀y Greedy(y)
� Brother(Richard,John)
puede verse que Evil(John), pero la reducción produce
muchos hechos como Greedy(Richard) que son
irrelevantes
![Page 19: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/19.jpg)
Unificación
� Se puede inferir más rápidamente el hecho si se encuentra una sustitución θ
tal que King(x) y Greedy(x) empaten con King(John) and Greedy(y)
θ = {x/John,y/John}
� Unificar(α,β) = θ si αθ = βθ
p q θ
Dr. Edgard I. Benítez G. 19Inteligencia Artificial
p q θ
Knows(John,x) Knows(John,Jane) {x/Jane}}
Knows(John,x) Knows(y,OJ) {x/OJ,y/John}}
Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)}}
Knows(John,x) Knows(x,OJ) {fail}
� La estandarización de variables elimina traslapes, e.g., Knows(z17,OJ)
![Page 20: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/20.jpg)
Unificación
� Para unificar Knows(John,x) y Knows(y,z)
θ = {y/John, x/z} o bien θ = {y/John, x/John, z/John}
� El primer unificador es más general que el segundo
Dr. Edgard I. Benítez G. 20Inteligencia Artificial
� El primer unificador es más general que el segundo
� Para cada par de expresiones unificable hay un
unificador más general (UMG) que es único respecto al
nombramiento de las variables
UMG = { y/John, x/z }
![Page 21: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/21.jpg)
Algoritmo de unificación
Dr. Edgard I. Benítez G. 21Inteligencia Artificial
![Page 22: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/22.jpg)
Algoritmo de unificación
Dr. Edgard I. Benítez G. 22Inteligencia Artificial
![Page 23: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/23.jpg)
Modus Ponens Generalizado (MPG)
p1', p2', … , pn', ( p1 ∧ p2 ∧ … ∧ pn ⇒q)
qθ
� Ejemplo:
� p1' es King(John) p1 es King(x)
� p2' es Greedy(y) p2 es Greedy(x)
� θ es {x/John,y/John} q es Evil(x)
donde pi‘ θ = pi θ para todo i
Dr. Edgard I. Benítez G. 23Inteligencia Artificial
� θ es {x/John,y/John} q es Evil(x)
� q θ es Evil(John)
� MPG usado con una base de conocimiento de clausulas determinadas
(aquellas que tienen exactamente una literal positiva)
� Se asume que todas las variables están universalmente cuantificadas
![Page 24: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/24.jpg)
Ejemplo de base de conocimiento
� La ley de Estados Unidos dice que es un crimen que un
uno de sus ciudadanos venda armas a naciones
hostiles. El país Nono, un enemigo de EU, tiene
algunos misiles y todos sus misiles fueron vendidos
por el Coronel West, quien es ciudadano
estadounidense
Dr. Edgard I. Benítez G. 24Inteligencia Artificial
estadounidense
� Probar que el Coronel West es un criminal
![Page 25: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/25.jpg)
Base de conocimiento
� ... Es un crimen que un ciudadano de EU venda armas a naciones hostiles:
American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z) ⇒ Criminal(x)
� Nono … tiene misiles, i.e., ∃x Owns(Nono,x) ∧ Missile(x):
Owns(Nono,M1) and Missile(M1)
� … todos sus misiles fueron vendidos por el coronel West
Missile(x) ∧ Owns(Nono,x) ⇒ Sells(West,x,Nono)
� Los misiles son armas:
Dr. Edgard I. Benítez G. 25Inteligencia Artificial
� Los misiles son armas:
Missile(x) ⇒ Weapon(x)
� Un enemigo de Eu es “hostil”:
� Enemy(x,America) ⇒ Hostile(x)
� West, quien es ciudadano de EU …
� American(West)
� El país Nono, un enemigo de EU …
� Enemy(Nono,America)
![Page 26: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/26.jpg)
Algoritmo de encadenamiento hacia adelante
Dr. Edgard I. Benítez G. 26Inteligencia Artificial
![Page 27: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/27.jpg)
Encadenamiento hacia adelante
Dr. Edgard I. Benítez G. 27Inteligencia Artificial
![Page 28: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/28.jpg)
Encadenamiento hacia atrás
Dr. Edgard I. Benítez G. 28Inteligencia Artificial
![Page 29: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/29.jpg)
Encadenamiento hacia atrás
Dr. Edgard I. Benítez G. 29Inteligencia Artificial
![Page 30: Inteligencia Artificial - Universidad Veracruzana · Inteligencia Artificial Conocimiento y razonamiento 3. ... Dr. Edgard I. Benítez G. Inteligencia Artificial 3 Igualdad: = Cuantificadores:](https://reader033.vdocumento.com/reader033/viewer/2022042006/5e700adcf3e3567576126651/html5/thumbnails/30.jpg)
Programación lógica: Prolog
� Algoritmo = Lógica + Control
� Base: encadenamiento hacia atrás con clausulas de Horn
� Programa = conjunto de clausulas = cabeza :- literal1, … literaln.
criminal(X) :- american(X), weapon(Y), sells(X,Y,Z), hostile(Z).
Dr. Edgard I. Benítez G. 30Inteligencia Artificial
� Encadenamiento hacia atrás en profundidad primero y de izquierda a
derecha
� Equipado con
� Predicados aritméticos, e.g., X is Y*Z+3
� Predicados que tienen efectos colaterales (e.g., entrada y salida, assert/retract)
� Suposición del mundo cerrado ("negación como falla")
� e.g., dado alive(X) :- not dead(X).
� alive(joe) es cierto si dead(joe) falla