programación para la inteligencia artificial ...programaciónparalainteligenciaartiﬁcial...

Programación para la Inteligencia ArtificialProgramación Lógica

Dr. Alejandro Guerra-Hernández

Universidad VeracruzanaCentro de Investigación en Inteligencia Artificial

Sebastián Camacho 5, Xalapa, Ver., México 91000mailto:[email protected]

https://www.uv.mx/personal/aguerra/pia

Maestría en Inteligencia Artificial 2018

Dr. Alejandro Guerra-Hernández (UV) Programación para la Inteligencia Artificial MIA 2018 1 / 101

mailto:[email protected]

https://www.uv.mx/personal/aguerra/pia

Lógica de Primer Orden Introducción

Objetivo

I A la programación lógica le concierne el uso de la Lógica de PrimerOrden para representar y resolver problemas.

I Usamos una lógica de primer orden restringida a cláusulas de Horn yresolución-SLD [2].

I Hoy revisaremos algunos conceptos preliminares de la Lógica dePrimer Orden, necesarios para formalizar los conceptos citados.



Representación

I Cuando describimos situaciones de nuestro interés, usamosenunciados declarativos.

I Expresiones del lenguaje natural que son o bien verdaderas, o bienfalsas (a diferencia de interrogativas, admirativas, etc.).

I Las proposiciones representan hechos que se dan o no en la realidad.I La Lógica de Primer Orden tienen un compromiso ontólogico más

fuerte [3], donde la realidad implica además, objetos y relacionesentre ellos.



Razonamiento

I Consideren los siguientes enunciados declarativos:1. Julia es madre y Luis es hijo de Julia.2. Toda madre ama a sus hijos.

I Conociéndolas es posible inferir:3. Julia ama a Luis.

I Para ello asumimos un conjunto de reglas de inferencia.I Ejemplo: Modus Ponens

P,P → QQ (M.P.)



Componentes de un Sistema Formal

Sistema Formal

Sintáxis

Semantica

Alfabeto

Reglas sintácticas

Teoría del Modelo

Teoría de PruebaAxiomas

Reglas de Inferencia

Universo de Discurso

Intepretación


Lógica de Primer Orden Lenguaje (informal)

El mundo de los bloques [1]

Mesa

B

A

C

D

E

Brazo robótico

I Necesitaremos símbolospara:I ObjetosI RelacionesI FuncionesI Variables



Universo de discurso

Mesa

B

A

C

D

E

Brazo robótico

I Se denota como U y es elconjunto de todos objetos sobrelos cuales queremos expresarnos.

I Para el mundo de los bloques:

U = {a, b, c, d , e, brazo,mesa}

I Seguiré la notación usada porProlog, las constantes soncadenas que inician conminúscula.



Funciones

Mesa

B

A

C

D

E

Brazo robótico

I Son relaciones especiales entrelos miembros de U . Mapean unconjunto de objetos de entradaa un objeto único de salida.

I La función parcial sombrero ={(b, a), (c, d), (d , e)}:

sombrero(b) 7→ a

I Base funcional es el conjuntode todas las funcionesconsideradas.



Predicados

I Denotan relaciones entre losmiembros de U . Mapean a falso overdadero.

I El predicadosobre = {(a, b), (d , c), (e, d)}:

sobre(a, b) 7→ true

I El predicado libre = {a, e}:

libre(d) 7→ false

I Base relacional es el conjunto detodos los predicados considerados.

Mesa

B

A

C

D

E

Brazo robótico



Predicados y Funciones

Mesa

B

A

C

D

E

Brazo robótico

I sobre = base = {(a, b), . . . }I Los predicados pueden verse

como funciones booleanas:

sobre(a, b) 7→ true

I Las funciones en este contexto,tienen su codomino en algúnsubconjunto de U :

base(a) 7→ b



Extensión de un predicado

I Para universos de discurso finitos, existe un límite superior en elnúmero posible de predicados n-arios.

I Para un universo de discurso de cardinalidad b , existen bn distintasn-tuplas.

I Cualquier predicado n-ario es un subconjunto de estas bn tuplas.I Por lo tanto, un predicado n-ario debe corresponder a uno de máximo

2(bn) conjuntos posibles.



Variables y cuantificadores

I Toman valores de U .I El cuantificador “para todo” (∀)

expresa hechos acerca de todos losobjetos en U , sin necesidad deenumerarlos:

∀X libre(X )⇐ . . .

I El cuantificador “existe” (∃) expresa laexistencia de un objeto en U concierta propiedad en partícular:

∀X ∃Y ocupado(X )⇐ sobre(Y ,X )

Mesa

B

A

C

D

E

Brazo robótico


Lógica de Primer Orden Sintaxis

Alfabeto de la Lógica de Primer Orden

Const El conjunto de símbolos de constantes;Var El conjunto de símbolos de variables;Pred El conjunto de símbolos de predicados;Func El conjunto de símbolos funcionales (Const ⊂ Func);¬ El operador monario de negación;∨ El operador binario de disyunción;∀ El símbolo de cuantificación universal;() Los paréntesis.



Reglas sintácticas (términos)

1. Si α ∈ Const entonces α ∈ Term;2. Si α ∈ Var , entonces α ∈ Term;3. Si α/n ∈ Func, entonces α(φ1, . . . , φn) ∈ Term si y sólo siφ1≤i≤n ∈ Term.

4. Ninguna otra expresión es un término.

I Ejemplos:I a, b, c,mesa, . . .I X ,Y ,Z ,Cubo1,Cubo2, . . .I base(b), sombrero(X ), . . .



Reglas sintácticas (fórmulas bien formadas)

1. Si α/n ∈ Pred , entonces α(φ0, . . . , φn) ∈ LFOL si y sólo siφi ∈ Term, i = 0 . . . n;

2. Si α ∈ LFOL, entonces ¬α ∈ LFOL;3. Si α ∈ LFOL y β ∈ LFOL, entonces (α ∨ β) ∈ LFOL

4. Si α ∈ LFOL y X ∈ Vars es una variable que ocurreen α, entonces ∀X α ∈ LFOL

5. Nada más es una fórmula bien formada (fbf).

I Ejemplos:I sobre(a, b), libre(X ), ama(X , hijo(X )), . . .I ¬libre(a),¬libre(Y ), . . .I sobre(X ,Y ) ∧ ¬libre(X ), . . .I ∀X ama(X , hijo(X )), . . .



Definiciones auxiliares

Conjunción. (α ∧ β) =def ¬(¬α ∨ ¬β);Implicación material. (α→ β) =def (¬α ∨ β);Equivalencia material. (α ≡ β) =def ((α→ β) ∧ (β → α));

Falso. f =def ¬α ∧ α;Verdadero. t =def ¬f

Cuantificador existencial. ∃X α =def ¬(∀X ¬α)



Términos BNF

I Un término se define como:

t ::= x | c | f (t, . . . , t)

donde x ∈ Var ; c ∈ Func tal que |c| = 0; y f ∈ Func tal que |f | > 0.



Fórmulas bien formadas BNF

I Las fbf del lenguaje de la Lógica de Primer Orden se construye apartir de las variables Var , los functores Func y los predicados Predcomo sigue:

φ ::= P(t1, . . . , tn) | ¬(φ) | (φ ∧ φ) | (φ ∨ φ) | (φ→ φ) | (∀x φ) | (∃x φ)

donde P ∈ Pred es un símbolo de predicado de aridad n ≥ 1; tidenota términos; y x ∈ Var .



Notación extra

I En una fbf de la forma ∀X α, se dice que la fbf α está bajo el alcancedel cuantificador ∀X .

I En tal caso, se dice que la ocurrencia de X en α está acotada, encaso contrario se dice que la ocurrencia de la variable es libre.

I Ejemplo. En ∃X sobre(X ,Y ) la variable X está acotada, mientras queY está libre.

I Un término sin variables se conoce como término de base.I Ejemplo. sobre(a, b).


Lógica de Primer Orden Interpretaciones y Modelos

Interpretación

I Para expresar que al menos hay un bloque que no tiene nada encima,escribimos: ∃X bloque(X ) ∧ libre(X ).

I Cuando usamos cuantificadores siempre tenemos en mente al U , eneste caso {a, b, c, d , e, brazo,mesa}.

I Una interpretación de esta expresión es un subconjunto de U tal quelos miembros de ese subconjunto satisfacen el significado esperado dela expresión. En este caso {a, e}.



Teoría del modelo

I Para obtener un modelo para el lenguaje LFOL formamos el parM = 〈D,V 〉, donde D es el universo de discurso y la interpretación Ves una función, tal que:I Para cualquier predicado α de aridad n ≥ 1, V (α) regresa las n-tuplas

que corresponden a la interpretación esperada del predicado.I Para una constante, la función V regresa la misma constante, ej.

V (c) = c.I Algunas veces la expresión V (α) se abrevia αV .



Interpretación para el mundo de bloques

aV = abV = bcV = cdV = deV = e

sobreV = {(a, b), (e, d), (d , c)}enLaMesaV = {b, c}

libreV = {a, e}porEncimaV = {(a, b), (e, d), (e, c), (d , c)}

Mesa

B

A

C

D

E

Brazo robótico


Lógica de Primer Orden Semántica

Interpretación y asignación de variables

I Una interpretación V , con respecto a un dominio de discurso D, esuna función que satisface las siguientes propiedades:I Si α ∈ Const, entonces V (α) = α;I Si α/n ∈ Pred , tal que n ≥ 1, entonces V (α) ⊆ Dn.

I Ejemplo: libreV ⊂ {a, b, c, d , e,mesa,mano}.I Ejemplo: sobreV ⊂ D × D.I Decimos que U es una asignación de variables basada en el modelo

M = 〈D,V 〉 si para todo α ∈ Var , U(α) ∈ D.



Asignación de términos

I La asignación de términos T , dadas la interpretación V y laasignación de variables U, es un mapeo de términos a objetos deluniverso de discurso que se define como sigue:I Si α ∈ Const, entonces TVU(α) = V (α).I Si α ∈ Var , entonces TVU(α) = U(α).I Si α ∈ Term y es de la forma α(φ1, . . . , φn); y V (α) = g ; y

TVU(φi) = xi , entonces TVU(α(φ1, . . . , φn)) = g(x1, . . . , xn).



Satisfacción

I El hecho de que el enunciado α sea satisfecho bajo una interpretaciónV y una asignación U, se escribe:

|=V α[U]

I Entonces podemos escribir M |= VU(α) para expresar que α esverdadera en el modelo M = 〈D,V 〉 cuando las variables en α tomanvalores de acuerdo a la asignación U.

I Ejemplo. M |= VU(sobre(X , b)) si X\a ∈ U.



Definiciones complementarias

I Si una interpretación V safisface a un enunciado α para todaasignación de variables, se dice que V es un modelo de α.

I Un enunciado se dice satisfacible si existe alguna interpretación yasignación de variables que lo satisfaga.

I De otra forma, se dice que el enunciado es insatisfacible.I Se dice que una fbf α es válida, si y sólo si se satisface en toda

intepretación y asignación de variables.I Las fbf válidas lo son en virtud de su estructura lógica, por lo que no

proveen información acerca del dominio descrito.I Ejemplo: p(X ) ∨ ¬p(X ) es una fbf válida.


Lógica de Primer Orden Inferencia

Mi mamá me ama

I Retomemos el ejemplo de la introducción:1. Toda madre ama a sus hijos.2. Julia es madre y Luis es hijo de Julia.3. Julia ama a Luis.

I Se puede formalizar como:1. ∀X ∀Y madre(X ) ∧ hijo_de(Y ,X )→ ama(X ,Y )2. madre(julia) ∧ hijo_de(luis, julia)3. ama(julia, luis)



Reglas de inferencia

I La inferencia puede verse como un proceso de manipulación de fbf,donde a partir las premisas, se producen las conclusiones.I Modus Ponens. O de eliminación de la implicación:

α α→ β

β(→ E )

I Eliminación de cuantificador universal.:

∀Xα(X )α(t) (∀E )

I Introducción de conjunción.:

α β

α ∧ β(∧I)



Ejemplo de derivación

I Inicio:1. ∀X∀Ymadre(X ) ∧ hijo_de(Y ,X ) =⇒ ama(X ,Y )2. madre(julia) ∧ hijo_de(luis, julia)

I Al aplicar la eliminación de cuantificador universal (∀E ) a (1)obtenemos:3. ∀Y (madre(julia) ∧ hijo_de(Y , julia) =⇒ ama(julia,Y )

I Al aplicar nuevamente (∀E ) a (3) obtenemos:4. madre(julia) ∧ hijo_de(luis, julia) =⇒ ama(julia, luis)

I Finalmente, al aplicar Modus Ponens a (2) y (4):5. ama(julia, luis)



Solidez y robustez

I Un conjunto de reglas de inferencia se dice sólido, si para todoconjunto de fbf cerradas (sin ocurrencia de variables libres) ∆ y cadafbf cerrada α, siempre que ∆ ` α se tiene que ∆ |= α.

I Las reglas de inferencia se dicen completas si ∆ ` α siempre que∆ |= α.


Programas definitivos Lenguaje

Enunciados declarativos

I Describen relaciones positivas entre elementos de U :I Incondicionadas (hechos) y Condicionadas (reglas).

1. Antonio es hijo de Juan.

2. Ana es hija de Antonio.

3. Juan es hijo de Marcos.

4. Alicia es hija de Juan.

5. El nieto de una persona es elhijo del hijo de esa persona.

1. hijo_de(antonio, juan)

2. hijo_de(ana, antonio)

3. hijo_de(juan,marcos)

4. hijo_de(alicia, juan)

5. ∀X∀Y (nieto_de(X ,Y )←∃Z (hijo_de(Z ,Y ) ∧hijo_de(X ,Z )))



Formas alternativas para una regla

I La fórmula:

∀X∀Y (nieto_de(X ,Y )← ∃Z (hijo_de(Z ,Y ) ∧ hijo_de(X ,Z )))

I Se puede escribir como:I ∀X∀Y (nieto_de(X ,Y ) ∨ ¬∃Z (hijo_de(Z ,Y ) ∧ hijo_de(X ,Z )))I ∀X∀Y (nieto_de(X ,Y ) ∨ ∀Z¬(hijo_de(Z ,Y ) ∧ hijo_de(X ,Z )))I ∀X∀Y ∀Z (nieto_de(X ,Y ) ∨ ¬(hijo_de(Z ,Y ) ∧ hijo_de(X ,Z )))I ∀X∀Y ∀Z (nieto_de(X ,Y )← (hijo_de(Z ,Y ) ∧ hijo_de(X ,Z )))

I Con equivalencias como:I α→ β ≡ ¬α ∨ β óI ∀Xα ≡ ¬∃X¬α.



Literales

I Una literal es un átomo o la negación de un átomo.I Una literal positiva es un átomo.I Una literal negativa es la negación de un átomo.I Ejemplos:

I hijo_de(juan,marcos).I ¬hijo_de(juan, alicia).

I Son los bloques de construcción αi en:

α0 ← α1 ∧ · · · ∧ αn (n ≥ 0)



Cláusulas

I Una cláusula es una disyunción finita de cero o más literales.I Una cláusula se dice definitiva, si tiene exactamente una literal

positiva.α0 ∨ ¬α1 ∨ · · · ∨ ¬αn (n ≥ 0)

I Lo cual es equivalente a la forma general de fbf que nos interesaba:

α0 ← α1 ∧ · · · ∧ αn (n ≥ 0)

I La cláusula vacía (sin literales) se denota como � y es equivalente a�← � (en nuestra notación previa ⊥ ← >).



Hechos y reglas revisitados

I En α0 ← α1 ∧ · · · ∧ αn (n ≥ 0), tenemos que:I Si n = 0, la literal α0 será positiva, por lo que la cláusula definitiva será

un hecho.I Si n > 0 la cláusula definitiva toma la forma de una regla, donde α0 es

la cabeza de la regla; y la conjunción α1 ∧ · · · ∧ αn su cuerpo.

I Una forma restringida de cuantificación:

∀X∀Y (nieto_de(X ,Y ) ∨ ¬∃Z (hijo_de(Z ,Y ) ∧ hijo_de(X ,Z ))).



Programa y Meta Definitivos

I Un programa definitivo es un conjunto finito de cláusulas definitivas.I Una cláusula sin literales positivas es una meta definitiva.

← α1 ∧ · · · ∧ αn (n ≥ 1)



Ejemplo

I Considere las siguientes consultas:

Consulta Meta definitiva¿Es Ana hija de Antonio? ← hijo(ana, antonio)¿Quién es nieto de Ana? ← nieto(X , ana)¿De quién es nieto Antonio? ← nieto(antonio,X )¿Quién es nieto de quién? ← nieto(X ,Y )

I ¿Cuales serían las respuestas computadas?



Respuestas obtenidas

I Puesto que la primer meta no contiene variables, la respuesta sería Si(Yes).

I Puesto que el programa no contiene información sobre los nietos deAna, la respueta a la segunda consulta es No (o ninguno).

I Puesto que Antonio es nieto de Marcos, la respuesta obtenida seríaX = marcos.

I La consulta final obtiene tres respuestas: X = antonio Y = alicia,X = alicia Y = marcos, X = ana Y = juan.



Cláusulas de Horn

I Una cláusula de Horn es una cláusula ó una meta definitivas.I La cláusula vacía � es una meta definitiva y, por lo tanto, una

cláusula de Horn.I Las cláusulas de Horn implican restricciones expresivas. Por ejemplo,

no podemos expresar p(a) ∨ p(b)I Debido a su estructura restringida, las cláusulas de Horn

son más fáciles de manipular que las cláusulas generales.



Significado lógico de las metas

I El significado lógico de las metas puede explicarse haciéndo referenciaa la fbf equivalente cuantificada universalmente:

∀X1 . . .Xm¬(α1 ∧ · · · ∧ αn)

donde todas las Xi ocurren en la meta. Equivale a:

¬∃X1 . . .Xm(α1 ∧ · · · ∧ αn)

I Prolog tratará de encontrar términos ti . . . tm tales que las fbfobtenidas a partir de α1 ∧ · · · ∧ αm al remplazar la variableXi por ti (1 ≤ i ≤ m) son verdaderas en todo modelodel programa (contra ejemplo).


Programas definitivos Modelo de Herbrand

Conocimiento positivo

I Los programas definitivos solo pueden expresar conocimiento positivo,tanto los hechos, como las reglas, nos dicen que elementos de unaestructura están en una relación, pero no nos dicen cuales no.

I Por lo tanto, al usar el lenguaje de los programas definitivos, no esposible construir descripciones contradictorias, i.e. conjuntos de fbf nosatisfacibles.

I Todo programa definitivo tiene un modelo.



Modelos e interpretaciones (recordatorio)

I Sea α una fbf y V una intepretación. V es un modelo de α si |=V α.I Sea ∆ un conjunto finito de fbf y V una interpretación. V es un

modelo de ∆ si |=V α para toda α ∈ ∆.I Una clase interesante de modelos para los programas definitivos se

conoce como interpretaciones de Herbrand.



Universo y Base de Herbrand

I Sea L un alfabeto extraído de un programa definitivo ∆, donde|Const| ≥ 1.

I El Universo de Herbrand (UL) es el conjunto de todos los términosformados con las constantes y functores de L.

I La Base de Herbrand (BL) es el conjunto de todos los átomos quepueden formarse con los predicados y los términos en UL.



Ejemplo: impar

I Sea ∆ = {impar(s(0)), impar(s(s(X )))← impar(X )}.I [UL = {0, s(0), s(s(0)), s(s(s(0))), . . . }I BL = {impar(0), impar(s(0)), impar(s(s(0))), . . . }



Otro ejemplo

I Sea ∆ = {p(a), q(a, f (b)), q(X ,X )← p(X )}I UL = {a, b, f (a), f (b), f (f (a)), f (f (b)), . . . }I BL = {p(a), p(b), p(f (a)), p(f (b)), . . . }



Interpretación de Herbrand

I Sea ∆ un programa definitivo y L el alfabeto compuesto por lossímbolos de ∆.

I V es una interpretación de Herbrand de ∆, si y sólo si:I El dominio de V es UL.I Para cada constante c ∈ L, cV = c.I Para cada functor f /n ∈ L, f V : Un

L 7→ UL.I Para cada predicado p/n ∈ L, pV ⊆ Un

L .



Modelo de Herbrand

I Sea ∆ un programa definitivo; L el alfabeto compuesto por lossímbolos en ∆; y V una interpretación de Herbrand de ∆. Si V es unmodelo de toda fbf en ∆, se dice que es un modelo de Herbrand de ∆.



Ejemplo: impar

I Consideren el programa ∆ en el ejemplo impar/1.I Una posible interpretación de este programa es

imparV = {s(0), s(s(s(0)))}

I Una intepretación de Herbrand se puede especificar mediante unafamilia de tales relaciones (una por cada símbolo de predicado).



Otro ejemplo

I Consideren ahora algunas interpretaciones de Herbrand de∆ = {p(a), q(a, f (b)), q(X ,X )← p(X )}:

V1 = {p(a), p(b), q(a, b, ), q(b, b)}V2 = {p(a), q(a, a), q(a, f (b))}V3 = {p(f (f (a))), p(b), q(a, a), q(a, f (b))}V4 = {p(a), p(b), q(a, a), q(b, b), q(a, f (b))}

I V2 y V4 son modelos de Herbrand de ∆I V1 y V3 no lo son.


Programas definitivos Propiedades

Resultados de interés

I Para poder determinar si una interpretación de Herbrand V es unmodelo de una fbf cuantificada universalmente ∀α, es suficienteverificar si α es verdadera en V , para todas las asignaciones posiblesde las variables de α.

I Para el lenguaje restringido de cláusulas definitivas, si queremosverificar que una fbf atómica α es consecuencia de un programadefinitivo ∆ basta con verificar que todo modelo de Herbrand de ∆ estambién un modelo de Herbrand de α.



Programa definitivo extendido con meta definitiva

I Sea ∆ un programa definitivo y γ una meta definitiva. Sea L unalfabeto compuesto por los símbolos en el programa y la metadefinitivos.

I Si V ′ es un modelo de ∆ ∪ {γ}, entonces V = {α ∈ BL| |=V ′ α} esun modelo de Herbrand de ∆ ∪ {γ}.



Consistencia

I Sea ∆ un programa definitivo y α una cláusula definitiva. Sea∆′ = ∆ ∪ {¬α}. Entonces ∆ |= α si y sólo si ∆′ no tiene modelo deHerbrand.

I Esto es, si ∆′ es no satisfacible, lo cual es cierto sólo si ∆′ no tienemodelos y por lo tanto, no tiene modelo de Herbrand.



Intersección de modelos de Herbrand

I Sea M una familia no vacía de modelos de Herbrand de un programadefinitivo ∆. Entonces la intersección V =

⋂M es un modelo de

Herbrand de ∆.I Al tomar la intersección de los modelos de Herbrand de un programa

definitivo (todos tienen al menos un modelo, e.g., B∆), obtenemos elmodelo mínimo de Herbrand.



Ejemplo

I Sea ∆ el programa definitivo {masculino(adan), femenino(eva)} consu interpretación obvia. ∆ tiene los siguientes modelos de Herbrand:1. {masculino(adan), femenino(eva)}2. {masculino(adan),masculino(eva), femenino(eva)}3. {masculino(adan),masculino(eva), femenino(eva)}4. {masculino(adan),masculino(eva), femenino(eva), femenino(adan)}

I La intersección de los modelos nos lleva a un modelo de Herbrand.I El modelo mínimo es el único que corresponde con el modelo

pretendido del programa.



Consecuencia Lógica

I El modelo mínimo de Herbrand de un programa definitivo ∆, M∆, esel conjunto de todas las consecuencias lógicas atómicas de base delprograma. Esto es: M∆ = {α ∈ B∆|∆ |= α}.

I La prueba de este teorema pasa por demostrar queM∆ ⊇ {α ∈ BL|∆ |= α} y que M∆ ⊆ {α ∈ B∆|∆ |= α}.


Programas definitivos Modelo mínimo de Herbrand

Operador de consecuencia inmediata

I Sea base(∆) el conjunto de todas las cláusulas de base en ∆. T∆ esuna función sobre las interpretaciones de Herbrand de ∆ definidacomo sigue:

T∆(V ) = {α0 | α0 ← α1, . . . , αn ∈ base(∆) ∧ {α1, . . . , αn} ⊆ V }

I Se puede demostrar que existe un punto fijo T∆(V ) = V y que V esidéntica al modelo mínimo de Herbrand de ∆!



Notación

I Existe una notación estándar para denotar a los miembros de estasecuencia de interpretaciones construídas a partir de ∆:

T∆ ↑ 0 = ∅T∆ ↑ (i + 1) = T∆(T∆ ↑ i)

T∆ ↑ n =∞⋃i=0

T∆ ↑ i

I el conjunto construído de esta manera es identico al modelo mínimode Herbrand de ∆.



Ejemplo

I Tomando ∆ como el programa de impar/1 tenemos:

T∆ ↑ 0 = ∅T∆ ↑ 1 = {impar(s(0))}T∆ ↑ 2 = {impar(s(0)), impar(s(s(s(0))))}

...T∆ ↑ m = {impar(sn(0)) | n ∈ {1, 3, 5, . . . }}



Fin

I Sea ∆ un programa definitivo y V∆ su modelo mínimo de Herbrand.Entonces, V∆ es la interpretación mínima de Herbrand, tal que:I T∆(V∆) = V∆.I V∆ = T∆ ↑ n.


Resolución-SLD Una estrategia de razonamiento

Programas y metas definitivos

I Consideren el siguiente programa definitivo ∆:

papa(juan,marta).recien_nacido(marta).

orgulloso(X ) ← padre(X ,Y ), recien_nacido(Y ).padre(X ,Y ) ← papa(X ,Y ).padre(X ,Y ) ← mama(X ,Y ).

I ¿Cómo interpretamos la meta ← orgulloso(Z ). ?



Metas

I En realidad la meta ← orgulloso(Z ).I Es una abreviatura de ∀Z¬orgulloso(Z )I Que a su vez es equivalente a ¬∃Z orgulloso(Z ).I Si demostramos que ese enunciado es contradictorio en ∆, entonces

sabremos que ∆ |= ∃Z orgulloso(Z ). Pero eso solo respondería si , ala pregunta original.

I El objetivo en realidad es encontrar una substitución θ tal que elconjunto ∆ ∪ {¬orgulloso(Z )θ} sea insatisfacible, lo que equivale aque ∆ |= orgulloso(Z )θ.Ejemplo: ∆ ∪ ¬orgulloso(Z ){Z/juan}



Razonamiento

I Asumimos la meta G0 – Para cualquier Z , Z no está orgulloso.I La inspección del programa ∆ revela que una regla describe una

condición para que alguién esté orgulloso:

orgulloso(X )← padre(X ,Y ), recien_nacido(Y ).

I Lo cual es lógicamente equivalente a:

∀(¬orgulloso(X )→ ¬(padre(X ,Y ) ∧ recien_nacido(Y )))



Estrategia

I Partiendo de:

∀(¬orgulloso(X )→ ¬(padre(X ,Y ) ∧ recien_nacido(Y )))

I Al renombrar X por Z , eliminar el cuantificador universal y usarmodus ponens con respecto a G0, obtenemos G1:

¬(padre(Z ,Y ) ∧ recien_nacido(Y ))

I o su equivalente:

← padre(Z ,Y ), recien_nacido(Y ).

I G1 que es verdadera en todo modelo ∆ ∪ {G0}.



Resolución

I Ahora solo queda probar que ∆ ∪ {G1} es no satisfacible. Observenque G1 es equivalente a la fbf:

∀Z∀Y (¬padre(Z ,Y ) ∨ ¬recien_nacido(Y ))

I G1 no es satisfacible para ∆, si en todo modelo de ∆ hay una personaque es padre de un recién nacido:

padre(X ,Y )← papa(X ,Y ).

I Por lo que G1 se reduce a G2:

← papa(Z ,Y ), recien_nacido(Y ).



Estretegia recursiva

I El programa declara que juan es padre de marta:

papa(juan,marta).

I Así que sólo resta probar que “marta no es una recién nacida” no sepuede satisfacer junto con ∆:

← recien_nacido(marta).

I pero el programa contiene el hecho:

recien_nacido(marta).

I equivalente a ¬recien_nacido(marta)→ �I lo que conduce a una refutación �.



Resumiendo

I Para probar la existencia de algo:I Suponer lo opuestoI y usar modus ponens y la regla de eliminación del cuantificador

universal,I para encontrar un contra ejemplo al supuesto.



Unificador

I Una meta es un conjunto de átomos a ser probados.I Seleccionamos un átomo de la meta p(s1, . . . , sn) y una cláusula del

programa con la forma p(t1, . . . , tn)← A1, . . .AnI Si encontramos una substitución θ que hace que p(s1, . . . , sn)θ y

p(t1, . . . , tn)θ sean idénticos. Tal substitución se conoce comounificador.

I La nueva meta se construye remplazando el átomo seleccionado en lameta original, por los átomos de la cláusula seleccionada, aplicando θa todos los átomos obtenidos de esta manera.



Resolución-SLD

I La regla de inferencia principio de resolución SLD combina modusponens, eliminación del cuantificador universal y en el paso final unreductio ad absurdum.

I Si se prueba en k pasos que la meta definitiva en cuestión no puedesatisfacerse, probamos que:

← (α1, . . . αm)θ1 . . . θk

I es una instancia que no puede satisfacerse. Por tanto:

∆ |= (α1 ∧ · · · ∧ αm)θ1 . . . θk



Observaciones

I Esta computación no es determinista: cualquier átomo de la metapuede ser seleccionado y pueden haber varias cláusulas del programaque unifiquen con el átomo seleccionado.

I Pueden existir unificadores alternativos para dos átomos.I Por otra parte, es posible también que el atomo seleccionado no

unifique con ninguna cláusula en el programa: No es posible construirun contra ejemplo para la meta definida inicial.

I La computación puede caer en un ciclo y de esta manera no producirsolución alguna.


Resolución-SLD Substitución

Substitución

I Una substitución θ es un conjunto finito de la forma:

{X1/t1, . . . ,Xn/tn}, (n ≥ 0)

donde las Xi son variables, distintas entre si, y los ti son términos.Decimos que ti substituye a Xi . La forma Xi/ti se conoce comoligadura de Xi . La substitución θ se dice se dice de base (grounded) sicada término ti es un término base.

I La substitución vacía se conoce como substitución de identidad y sedenota por ε.



Caso (expresiones)

I Sea θ = {X1/t1, . . . ,Xn/tn} una substitución y α una expresión.Entonces αθ, el caso (instance) de α bajo θ, es la expresión obtenidaal substituir simultáneamente Xi por ti para 1 ≤ i ≤ n.

I Si αθ es una expresión de base, se dice que es un caso base y se diceque θ es una substitución de base para α.

I Si Σ = {α1, . . . , αn} es un conjunto finito de expresiones, entoncesΣθ denota {α1θ, . . . , αnθ}.



Ejemplo

I Sea α la expresión p(Y , f (X )) yI sea θ la substitución {X/a,Y /g(g(X ))}.I El caso de α bajo θ es αθ = p(g(g(X )), f (a).I Observen que X e Y son simultáneamente remplazados por sus

respectivos términos, lo que implica que X en g(g(X )) no es afectadapor X/a.



Composición de substituciones

I Sean θ = {X1/s1, . . . ,Xm/sm} y σ = {Y1/t1, . . .Yn/tn} dossubstituciones. Consideren la secuencia:

X1/(s1σ), . . . ,Xm/(smσ),Y1/t1, . . . ,Yn/tn

I Si se borran de esta sencuencia las ligaduras Xi/siσ cuando Xi = siσy cualquier ligadura Yj/tj donde Yj ∈ {X1, . . . ,Xm}, obtenemos lacomposición de θ y σ denotada por θσ.



Ejemplo

I Sea θ = {X/f (Y ),Z/U} y σ = {Y /b,U/Z}.I Construimos la secuencia de ligaduras

X/(f (Y )σ),Z/(U)σ,Y /b,U/Z lo cual es X/f (b),Z/Z ,Y /b,U/Z .I Al borrar la ligadura Z/Z obtenemos la secuencia

X/f (b),Y /b,U/Z = θσ.



Caso (substituciones)

I Sean θ y σ dos substituciones. Se dice que θ es un caso de σ, si existeuna substitución γ, tal que σγ = θ.

I La substitución θ = {X/f (b),Y /a} es un caso deσ = {X/f (X ),Y /a}, puesto que σ{X/b} = θ.



Propiedades de las substituciones

I Sea α una expresión, y sea θ, σ y γ substituciones. Las siguientesrelaciones se cumplen:1. θ = θε = εθ2. (αθ)σ = α(θσ)3. (θσ)γ = θ(σγ)


Resolución-SLD Unificación

Unificación

I Uno de los pasos principales en el cómputo de una meta, es que dosfbf atómicas se vuelvan sintácticamente equivalentes.

I Este proceso se conoce como unificación y posee una soluciónalgorítmica.

I Sean α y β términos. Una substitución θ tal que α y β sean idénticos(αΘ = βΘ) es llamada unificador de α y β.

I unifica(conoce(juan,X ), conoce(Y ,Z )) = {Y /juan,X/Z}



Unificador más general (MGU)

I Una substitución θ se dice más general que una substitución σ, si ysólo si existe una substitución γ tal que σ = θγ.

I Un unificador θ se dice el unificador más general (MGU: Most GeneralUnifier) de dos términos, si y sólo si θ es más general que cualquierotro unificador entre esos términos.



Forma resuelta y MGU

I Un conjunto de ecuaciones {X1 = t1, . . . ,Xn = tn} está en formaresuelta, si y sólo si X1, . . . ,Xn son variables distintas que no ocurrenen t1, . . . , tn.

I Sea {X1 = t1, . . . ,Xn = tn} un conjunto de ecuaciones en formaresuelta. Entonces {X1/t1, . . . ,Xn/tn} es un MGU (idempotente) dela forma resuelta.



Equivalencia

I Dos conjuntos de ecuaciones E1 y E2 se dicen equivalentes, si tienenel mismo conjunto de unificadores.

I Para computar el MGU de dos términos α y β, primero intentetransformar la ecuación {α = β} en una forma resuelta equivalente.Si esto falla, entonces mgu(α, β) = fallo. Sin embargo, si una formaresuelta {X1 = t1, . . . ,Xn = tn} existe, entoncesmgu(α, β) = {X1/t1, . . . ,Xn/tn}.



Algoritmo de unificación

1: function Unifica(E) . E es un conjunto de ecuaciones2: repeat3: (s = t)← seleccionar(E)4: if f (s1, . . . , sn) = f (t1, . . . , tn) (n ≥ 0) then5: remplazar (s = t) por s1 = t1, . . . , sn = tn6: else if f (s1, . . . , sm) = g(t1, . . . , tn) (f /m 6= g/n) then7: return(fallo)8: else if X = X then9: remover la X = X

10: else if t = X then11: remplazar t = X por X = t12: else if X = t then13: if subtermino(X ,t) then14: return(fallo)15: else remplazar todo X por t16: end if17: end if18: until No hay accion posible para E19: end function



Ejemplo 1

I El conjunto {f (X , g(Y )) = f (g(Z ),Z )} tiene una forma resuelta,pues:

{f (X , g(Y )) = f (g(Z ),Z )} → {X = g(Z ), g(Y ) = Z}→ {X = g(Z ),Z = g(Y )}→ {X = g(g(Y ),Z = g(Y )}



Ejemplo 2

I El conjunto {f (X , g(X ), b) = f (a, g(Z ),Z )} no tiene forma resuelta,puesto que:

→ {X = a, g(X ) = g(Z ), b = Z}→ {X = a, g(a) = g(Z ), b = Z}→ {X = a, a = Z , b = Z}→ {X = a,Z = a, b = Z}→ {X = a,Z = a, b = a}→ fallo



Ejemplo 3

I El conjunto {f (X , g(X )) = f (Z ,Z )} no tiene forma resuelta, puestoque:

→ {X = Z , g(X ) = Z}→ {X = Z , g(Z ) = Z}→ {X = Z ,Z = g(Z )}

→ fallo



Consideraciones

I Este algoritmo termina y regresa una forma resuelta equivalente alconjunto de ecuaciones de su entrada, o bien regresa fallo si la formaresuelta no existe.

I Sin embargo, el computar subtermino(X , t) (verificación deocurrencia) hace que el algoritmo sea altamente ineficiente.

I El standard ISO Prolog (1995) declara que el resultado de launificación es no decidible.

I Al eliminar la verificación de ocurrencia es posible que al intentarresolver X = f (X ) obtengamos X = f (f (X )) · · · = f (f (f . . . )).



Como búsqueda en un latice de generalización

?

>

f(X, Y )

f(X, b) f(a, Y ) f(X, c)

......

......

......

...

f(a, b) f(a, c)...

...


Resolución-SLD Resolución-SLD

Formalizando

I El método de razonamiento descrito informalmente al inicio de estasesión, puede resumirse con la siguiente regla de inferencia:

∀¬(α1 ∧ · · · ∧ αi−1 ∧ αi ∧ αi+1 ∧ · · · ∧ αm) ∀(β0 ← β1 ∧ · · · ∧ βn)∀¬(α1 ∧ · · · ∧ αi−1 ∧ β1 ∧ · · · ∧ βn ∧ αi+1 ∧ · · · ∧ αm)θ

I donde:1. α1, . . . , αm son fbf atómicas.2. β0 ← β1, . . . , βn es una cláusula definitiva en el programa ∆ (n ≥ 0).3. MGU(αi , β0) = θ.



Observaciones

I La regla tiene dos premisas: una meta y una cláusula definitivas.I El alcance de los cuantificadores es disjunto.I Solo hay un cuantificador universal para la conclusión. Por lo tanto,

se requiere que el conjunto de variables en las premisas sea disjunto.I Puesto que todas las variables en las premisas están cuantificadas, es

siempre posible renombrar las variables de la cláusula definitiva paracumplir con esta condición.



S de selección

I La meta definida puede incluir muchas fbf atómicas que unifican conla cabeza de alguna cláusula en el programa.

I En este caso, es deseable contar con un mecanismo determinista paraseleccionar un átomo αi a unificar.

I Se asume una función que selecciona una submeta de la metadefinida (función de selección).



Usando la resolución-SLD

I El punto de partida es una meta definida G0:

← α1, . . . , αm (m ≥ 0)

I Una submeta αi será seleccionada. Una nueva meta G1 se construyeal seleccionar una cláusula del programa β0 ← β1, . . . , βn (n ≥ 0)cuya cabeza β0 unifica con αi , resultando en θ1. G1 tiene la forma:

← (α1, . . . , αi−1, β1, . . . , βn, . . . , αm)θ1

I Ahora es posible aplicar el principio de resolución a G1 para obtenerG2, y así sucesivamente.



Terminación

I El proceso puede terminar o no. Hay dos situaciones donde no esposible obtener Gi+1 a partir de Gi :1. cuando la submeta seleccionada no puede ser resuelta (no es unificable

con la cabeza de una cláusula del programa).2. cuando Gi = � (meta vacía = f).



Derivación-SLD

I Sea G0 una meta definitiva, ∆ un programa definitivo y R unafunción de selección. Una derivación SLD de G0 (usando ∆ y R) esuna secuencia finita o infinita de metas:

G0α0 G1 . . .Gn−1

αn−1 Gn

I αi ∈ ∆. Las variables en αi se renombran con subíndices i .



Substitución computada

I Cada derivación SLD nos lleva a una secuencias de MGUs θ1, . . . , θn.La composición

θ ={θ1θ2 . . . θn si n > 0ε si n = 0

de MGUs se conoce como la substitución computada de la derivación.



Ejemplo

I Consideren la meta definida ← orgulloso(Z ) y el programa del iniciode esta clase. Entonces

G0 = ← orgulloso(Z ).α0 = orgulloso(X0)← padre(X0,Y0), recien_nacido(Y0).

I La unificación de orgulloso(Z ) y orgulloso(X0) nos da el MGUθ1 = {X0/Z}. Asumamos que nuestra función de selección es tomarla submeta más a la izquierda:

G1 = ← padre(Z ,Y0), recien_nacido(Y0).α1 = padre(X1,Y1)← papa(X1,Y1).

con θ2 = {X1/Z ,Y1/Y0}.



Ejemplo

I La derivación continua como sigue:

G2 = ← papa(Z ,Y0), recien_nacido(Y0).α2 = papa(juan,marta).G3 = ← recien_nacido(marta).α3 = recien_nacido(marta).G4 = �

I la substitución computada para esta derivación es:

θ1θ2θ3θ4 = {X0/Z}{X1/Z ,Y1/Y0}{Z/juan,Y0/marta}ε= {X0/juan,X1/juan,Y1/marta,

Z/juan,Y0/marta}



Refutación-SLD y derivación fallida

I Una derivación SLD finita:

G0α0 G1 . . .Gn−1

αn−1 Gn

donde Gn = �, se llama refutación SLD de G0.I Una derivación de la metaG0 cuyo último elemento no es la meta

vacía y no puede resolverse con ninguna cláusula del programa, esllamada derivación fallida.



Arbol-SLD

I Sea ∆ un prog. definitivo, G0 una meta definitiva, y R una función deselección. El árbol-SLD de G0 (usando ∆ y R) es un árboletiquetado, posiblemente infinito, que cumple con:I La raíz del árbol está etiquetada por G0.I Si el árbol contiene un nodo etiquetado como Gi y existe una cláusula

renombrada αi ∈ ∆ tal que Gi+1 es dervidada de Gi y αi via R,entonces el nodo etiquetado como Gi tiene un hijo etiquetado Gi+1 Elarco entre ambos es αi .



Ejemplo

← orgulloso(Z )

← padre(Z ,Y0), recien_nacido(Y0)

← papa(Z ,Y0), recien_nacido(Y0)

← recien_nacido(marta)

�

← mama(Z ,Y0), recien_nacido(Y0)



Propiedades de la resolución-SLD

Correctez Sea ∆ un programa definitivo, R una función de selección, yθ una substitución de respuesta computada a partir de ∆ yR para una meta ← α1, . . . , αm. Entonces∀((α1 ∧ · · · ∧ αm)θ) es consecuencia lógica del programa ∆.

Completez Sea ∆ un programa definitivo, R una función de selección y← α1, . . . , αm una meta definitiva. Si∆ |= ∀((α1 ∧ · · · ∧ αm)σ), entonces existe una refutación de← α1, . . . , αm vía R con una substitución de respuestacomputada θ, tal que (α1 ∧ · · · ∧ αm)σ es un caso de(α1 ∧ · · · ∧ αm)θ.



Referencias I

M Genesereth y N Nilsson. Logical Foundations for Artificial Intelligence. Palo Alto, CA.,USA: Morgan Kauffman Publishers, Inc., 1987.

S-H Nienhuys-Cheng y R de Wolf. Foundations of Inductive Logic Programming. Ed. porJG Carbonell y J Sickmann. Vol. 1228. Lecture Notes in Artificial Intelligence. BerlinHeidelberg: Springer-Verlag, 1997.

S Russell y P Norvig. Artificial Intelligence: A Modern Approach. Tercera. Prentice HallSeries in Artificial Intelligence. USA: Prentice Hall, 2009.


programación para la inteligencia artificial ...programaciónparalainteligenciaartiﬁcial...

Documents