Post on 14-Mar-2020
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
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, ..
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: ∀, ∃
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)))
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)
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
Ejemplo de modelo
Dr. Edgard I. Benítez G. 7Inteligencia Artificial
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)
∧ …
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
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)
∨ ...
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 !
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)
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)]
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)
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))
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
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.
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
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)
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 }
Algoritmo de unificación
Dr. Edgard I. Benítez G. 21Inteligencia Artificial
Algoritmo de unificación
Dr. Edgard I. Benítez G. 22Inteligencia Artificial
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
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
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)
Algoritmo de encadenamiento hacia adelante
Dr. Edgard I. Benítez G. 26Inteligencia Artificial
Encadenamiento hacia adelante
Dr. Edgard I. Benítez G. 27Inteligencia Artificial
Encadenamiento hacia atrás
Dr. Edgard I. Benítez G. 28Inteligencia Artificial
Encadenamiento hacia atrás
Dr. Edgard I. Benítez G. 29Inteligencia Artificial
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