jaime sánchez hernández horario, tutor´ıas, método,...

Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación

Universidad Complutense de Madridemail: [email protected]

Programación Lógica

Jaime Sánchez Hernández

Universidad Complutense de MadridDepartamento de Sistemas Informáticos y Programación

Curso 2007-2008

6 de Octubre de 2008

1 / 1



Horario, tutoŕıas, método, examenes

Horario:

Grupos A, C: L-M-X de 13:00 a 13:50Grupo B: L de 15:00 a 15:50, M-X de 17:00 a 17:50

Tutoŕıas: M y X de 12:00 a 13:00 y de 15:00 a 17:00

Método: clases teóricas y de problemas

Material de la asignatura (transparencias, ejercicios...)http://gpd.sip.ucm.es/jaime/pl

IMPORTANTE: las transparencias no son un manualcompleto de la asignatura (se completan con las clases,bibliograf́ıa, ejercicios, etc)

Examenes: Finales en Febrero y en Septiembre (teoŕıa +práctica, 100% de la nota)

2 / 1

http://gpd.sip.ucm.es/jaime/pl



Contenidos

1 Fundamentos de la programación lógica.

0. Repaso de la lógica de predicados1. Unificación y resolución.2. Cláusulas de Horn. Resolución SLD.

2 Programación en Prolog.

1 Espacios de búsqueda Prolog.2 Programación lógica con números, listas y árboles.3 Control en Prolog.4 Manipulación de términos. Predicados metalógicos.5 Técnicas avanzadas de programación en Prolog.

Utilizaremos el entorno SWI-PROLOG (Open Source; Linux,Windows, MacOS X): http://www.swi-prolog.org/

3 / 1



Bibliograf́ıa

L. Sterling, E. Shapiro. The Art of Prolog. AdvancedProgramming Techniques. The MIT Press, 2a Edición, 1994.

K. Doets. From Logic to Logic Programming. The MIT Press,1994.

W. F. Clocksin, C.S. Mellish. Programming in Prolog usingthe ISO Standard. Springer Verlag, 5a Edición, 2003.

A. Apt. From Logic Programming to Prolog. Prentice Hall,1997.

Otros libros interesantes (avanzados):

U. Schöning. Logic for Computer Scientists. Birkhäuser, 1989.

W. F. Clocksin. Clause and Effect. Prolog Programming forthe Working Programmer. Springer, 4a Edición, 2001.

R. A. O’Keefe. The Craft of Prolog. MIT, 2a Edición, 1994.4 / 1

http://www.swi-prolog.org/



Lógica de predicados

En programación lógica...

no hay tipos de datos en el sentido habitual

≡ dominio de valores + operaciones

(ni enteros, ni reales...)

no hay bucles (ni for, ni while, ni repeat...)

no hay funciones, ni procedimientos

no hay ni siquiera asignación!!

... “por debajo” no hay una arquitectura de Von Newman(memoria de almacenamiento para datos y programa, flujo deejecución...)

¿Qué nos queda? : la lógica

5 / 1




¿Y qué se puede hacer en programación lógica?

Todo: pueden computarse todas las funciones computables (ypuede demostrarse con relativa facilidad).

También puede hacerse esto mismo con máquinas de Turing, conmáquinas de registros ilimitados... o en código máquina.

Pero, ¿es sencillo resolver problemas en programación lógica?

Śı, con el adiestramiento necesario. En general es más sencillo queen lenguajes imperativos, el desarrollo de programas es más rápido,más fiable y, en opinión de muchos, más elegante. También escierto que por regla general, los programas son más ineficientes (ellenguaje está menos próximo a la arquitectura de la máquina).

6 / 1




Oŕıgenes

A partir del trabajo de Herbrand y otros en 1930, J. AlanRobinson publicó “el principio de resolución” en 1965.

En los años 70 hay un gran interés en la construcción dedemostradores automáticos.

En 1972 Robert Kowalski y Alan Colmenauer se plantearonutilizar la lógica como lenguaje de programación.

Aśı surgió PROLOG= PROgramming in LOGic.

La programación lógica utiliza un fragmento de la lógica depredicados y unificación y resolución como mecanismo de cómputo.

7 / 1




Lógica de predicados (breve repaso)

8 / 1




Sintaxis

conjunto (infinito numerable) de variables V: X ,Y ,Z . . . ∈ V

signatura Σ =< SF ,SP >

conjunto de śımbolos de función SF : f , g , h . . . ∈ SF

Escribimos f ∈ SF n ó f n para indicar que f tiene aridad n(opera sobre n argumentos). Si n = 0 hablaremos deconstantes (a, b, c ∈ SF 0)

conjunto de śımbolos de predicado SP: p, q, r . . . ∈ SP

Escribimos p ∈ SPn ó pn para indicar la aridad como antes,pero ahora exigimos n > 0

Además utilizamos śımbolos auxiliares: paréntesis, comas,puntos, etc

9 / 1




Términos y fórmulas

Términos TΣ(V)t ≡ X | f (t1, . . . , tn)

siendo X ∈ V, f ∈ SF n y t1, . . . , tn ∈ TΣ(V).

En particular, las constantes a ∈ FS0 también son términos.

Fórmulas LΣ

ϕ ≡ > | ⊥ | p(t1, . . . , tn) | ¬ψ | ψ1 ∧ ψ2 | ψ1 ∨ ψ2 |

ψ1 → ψ2 | ψ1 ↔ ψ2 | ∀X .ψ | ∃X .ψ

siendo p ∈ SPn, t1, . . . , tn ∈ TΣ(V), X ∈ V, ψ,ψ1, ψ2 ∈ LΣ.Las de la forma p(t1, . . . , tn) se llaman fórmulas atómicas.

Estas dos definiciones son recursivas. ¿Cuáles son los casos base ycuáles los recursivos? (¿conocemos la inducción estructural?)

10 / 1




Términos y fórmulas. Ejemplos

Suponemos Σ =< {c0, f 1, g2}, {p3, q2} >

Términos:X c f (X ) g(X ,Y ) g(c , g(X ,Y )) f (g(c , f (c)))

¿Por qué f (q(X ,Y )) no es un término?

Fórmulas

Atómicas:q(c , f (c)) p(X ,Y , g(c , g(X ,Y ))) q(f (f (Y )), g(g(c , c), f (Y )))No atómicas:q(X ,Y ) ∨ p(f (c), c , c) ∀X .q(X , c) ∨ ∃Z .p(Z ,Z ,X )

¿Por qué q(q(X ,Y ), c) no es una fórmula?

Dada una signatura Σ, ¿cuántos términos pueden construirse?, ¿ycuántas fórmulas?

11 / 1




Ámbito de los cuantificadores

Dada una fórmula ∀X .ϕ ó ∃X .ϕ diremos que el ámbito delcuantificador es ϕ.

¿Cuál es el ámbito de los cuantificadores en las siguientesfórmulas?

∀X .∃Y .(r(X , f (Y )) ∧ ∀Z .¬(r(Z ,Z ) ∨ q(Y )))∀X .(∃Y .r(X ,Y )→ ∀Z .(q(Z ) ∨ r(Y ,Y )))

¿Puede cuantificarse más de una vez la misma variable en unafórmula?

∀X .(p(X ,Y )→ ∃X .r(X ,Y ,Y ))Para evitar confusiones, renombramiento:

∀X .(p(X ,Y )→ ∃Z .r(Z ,Y ,Y ))12 / 1




Variables libres y ligadas

La aparición de una variable X dentro de una fórmula ϕ sedice ligada si está afectada por un cuantificador, o con másprecisión: X aparece ligada en ϕ si está dentro de unasubfórmula de ϕ de la forma ∀X .ψ o ∃X .ψ.La aparición de X en ϕ es libre si no está ligada, i.e., si noestá afectada por ningún cuantificador.

Ejemplo:

∃X .p( X︸︷︷︸ligada

, f ( Y︸︷︷︸libre

)) ∨ ∀Y .q( Y︸︷︷︸ligada

, g( X︸︷︷︸libre

))

Una variable X está libre en ϕ si todas las apariciones de X enϕ son libres.

Una variable X está ligada en ϕ si alguna de las aparicionesde X en ϕ es ligada.

13 / 1




¿Puede una misma variable aparecer ligada y libre en la mismafórmula?

ϕ ≡ ∀X .r( X︸︷︷︸ligada

, Y︸︷︷︸libre

) ∧ ∀Y .p( X︸︷︷︸libre

, Y︸︷︷︸ligada

,Z )

Para evitar confusiones, renombramiento:

ϕ′ ≡ ∀X ′.r(X ′,Y ) ∧ ∀Y ′.p(X ,Y ′,Z )

¿Son iguales ϕ y ϕ′?

“Iguales” no son... parece que tendrán el mismo significado, peropara verlo tendŕıamos que dar semántica o significado a lasfórmulas.

Nos interesará especialmente la semántica de las sentencias:fórmulas cerradas, i.e., sin variables libres.

14 / 1




La lógica como (un) lenguaje de representaciónde conocimiento

La lógica de predicados permite expresar “sentencias” del lenguajenatural.

“Algunos maḿıferos leen a Quevedo”

Definimos PS = {mamifero1, leerQuevedo1}, FS = ∅ con elsignificado “intuitivo”:

mamifero(X ) ::= X es un maḿıferoleerQuevedo(X ) ::= X lee a Quevedo

Y formalizamos:

∃X .(mamifero(X ) ∧ leerQuevedo(X ))

15 / 1




O de otro modo: PS = {mamifero1, leer2}, FS = {a} con elsignificado “intuitivo”:

mamifero(X ) ::= X es un maḿıfero

leer(X ,Y ) ::= X lee a Y

a ::= Quevedo

Formalizamos:

∃X .(mamifero(X ) ∧ leer(X , a))

16 / 1




Otro ejemplo: “El producto de cualquier número n por 1 es n”

(Esta es una sentencia “matemática”, pero está expresada enlenguaje natural).

Definimos SP = {=2}, SF = {10, ∗2} con el significado intuitivo:= predicado binario de igualdad (ser iguales)

1 ::= el “uno” de matemáticas

∗ ::= el “producto” en matemáticasy formalizamos

∀X .X ∗ 1 = X

En este ejemplo se pone de manifiesto que las matemáticas están“empapadas” en la lógica (la lógica puede expresar propiedadesmatemáticas... incluso puede expresar cosas acerca de la lógicamisma!).

17 / 1




Semántica de la lógica de predicados

Hemos definido el lenguaje de la lógica de predicados, hemos dadolas reglas sintácticas para construir los distintos elementos de dicholenguaje:

los términos pueden representar valores de nuestro universo

las fórmulas, especialmente las sentencias (fórmulas sinvariables libres), permiten expresar propiedades de loselementos de ese universo

Pretendemos que este lenguaje nos permita razonar acerca de laverdad o falsedad de las propiedades que expresa y que nospermita hacer deduciones acerca del universo que representa...tenemos que dotar a este lenguaje de significado, de semántica.

18 / 1




Ejemplo

Supongamos V = {X1,X2, . . .} y la signatura:

SF = {c0, suc1, suma2} SP = {par1,menorOigual2}

Sabemos (por construcción sintáctica):

suc(suc(c)) ∈ TΣ(V),suma(suc(c), suma(X , suc(c))) ∈ TΣ(V)par(suc(suc(c))) ∈ LΣ, ∀X .par(suma(X ,X )) ∈ LΣ,∀X .∃Y .menorOigual(suma(X ,X ), suma(Y ,Y )) ∈ LΣ

¿Cómo se puede razonar que los primeros son términos y lassegundas fórmulas? ¿Son sentencias las segundas? ¿Se podŕıahacer un programa para reconocer términos y fórmulas?

¿Tienen algún significado estos términos o estas fórmulas?

19 / 1




Semántica declarativa

Ahora es la lógica la que recurre a las matemáticas: definimos unaestructura

A = (DA, {f A}f ∈SF , {pA}p∈SP)

donde:

DA es el dominio (conjunto cualquiera de valores)

para cada śımbolo de función f ∈ SF n tenemos una función(en el sentido matemático habitual)f A : DA× n. . . ×DA → DA

para cada śımbolo de predicado p ∈ SPn tenemos una relaciónpA ⊆ DA× n. . . ×DA

20 / 1




Ejemplo (cont):

Para la signatura de nuestro ejemplo

SF = {c0, suc1, suma2} SP = {par1,menorOigual2}

definimos:

A = (IN, {cA, sucA, sumaA}, {parA,menorOigualA})

donde:

cA : INcA = 0

sucA : IN→ INsucA(n) = n + 1

sumaA : IN× IN→ INsumaA(n,m) = n + m

parA ⊆ INparA = {n ∈ IN | n es par}

menorOigualA ⊆ IN× INmenorOigualA = {(n,m) | n,m ∈ IN, n ≤ m}

21 / 1




Ejemplo (cont):

Nótese que las funciones y relaciones que hemos asociado a losśımbolos son arbitrarias: podriamos haber definido parA = {1, 3}

Lo importante es que al definir tales funciones y relaciones ahorapodemos interpretar o dar significado a términos, fórmulas ysentencias:

suc(suc(c)), de acuerdo con lo anterior “significa” 2

∀X .par(suma(X ,X )) es “cierto” (significa >)

... pero, ¿cuál es el significado del términosuma(suc(c), suma(X , suc(c))) o de la fórmulamenorOigual(c , suma(X , c))?

Para los términos y las fórmulas abiertas tenemos que dar unvalor a las variables libres.

22 / 1




Valoraciones e interpretaciones

Una valoración en A es una función:

υ : V → DA

(a cada variable le asocia un valor del dominio DA

Y con esto (ahora śı) podremos dar significado a todas lasconstrucciones de nuestro lenguaje.

Una interpretación I es una estructura junto con unavaloración para las variables:

I = (A, υ)

23 / 1




Significado de un término en una interpretación

El significado de un término t en una interpretación I = (A, υ) sedefine sobre la estructura de los términos como:

[[X ]]Aυ = υ(X )

[[f (t1, . . . , tn)]]Aυ = f A([[t1]]

Aυ, . . . , [[tn]]Aυ)

Por ejemplo, si definimos υ(Xi ) = i tendremos:

[[suc(X7)]]Aυ = sucA([[X7]]

Aυ) = sucA(υ(X7)) = sucA(7) = 7+1 = 8

[[suma(suc(X7),X8)]]Aυ = sumaA([[suc(X7)]]

Aυ, [[X8]]Aυ) =

sumaA(sucA([[X7]]Aυ), υ(X8)) = suma

A(sucA(7), 8) =

sumaA(7 + 1, 8) = sumaA(8, 8) = 16

24 / 1




Significado de una fórmula

De manera análoga definimos el valor veritativo de una fórmula ϕen una interpretación I = (A, υ):

[[>]]Aυ = cierto[[⊥]]Aυ = falso[[p(t1, . . . , tn)]]

Aυ =

{cierto si ([[t1]]Aυ, . . . , [[tn]]Aυ) ∈ pAfalso e.o.c.

[[¬ϕ]]Aυ ={

cierto si [[ϕ]]Aυ =falsofalso e.o.c.

[[ϕ ∨ ψ]]Aυ ={

falso si [[ϕ]]Aυ = [[ψ]]Aυ =falsocierto e.o.c.

[[ϕ ∧ ψ]]Aυ ={

cierto si [[ϕ]]Aυ = [[ψ]]Aυ =ciertofalso e.o.c.

25 / 1




Significado de una fórmula (cont)

• [[∀X .ϕ]]Aυ ={

cierto si para todo d ∈ DA se tiene [[ϕ]]Aυ[X/d ] =ciertofalso e.o.c.

• [[∃X .ϕ]]Aυ ={

cierto si existe d ∈ DA tal que [[ϕ]]Aυ[X/d ] =ciertofalso e.o.c.

donde υ[X/d ] es una valoración definida como:

υ[X/d ](Y ) =

{d si X = Yυ(Y ) e.o.c.

(La notación [X/d ] es una sustitución. Más adelante lasestudiaremos en detalle, pero por el momento basta la definiciónanterior).¿Cómo se define [[ϕ→ ψ]]Aυ y [[ϕ↔ ψ]]Aυ?

26 / 1




Ejemplo

Calculemos el valor veritativo de la sentencia ∀X .par(suma(X ,X ))en la interpretación vista anteriormente:

sera cierto

sii para todo n ∈ IN. [[par(suma(X ,X ))]]Aυ[X/n] =ciertosii para todo n ∈ IN. [[suma(X ,X )]]Aυ[X/n] ∈ parA

sii para todo n ∈ IN.sumaA([[X ]]Aυ[X/n], [[X ]]Aυ[X/n]) ∈ parA

sii para todo n ∈ IN. sumaA(υ[X/n](X ), υ[X/n](X )) ∈ parA

sii para todo n ∈ IN. sumaA(n, n) ∈ parA

sii para todo n ∈ IN. n + n ∈ parA

sii para todo n ∈ IN. 2n ∈ {m ∈ IN | m es par}y esto último es cierto (es una propiedad matemáticaconocida)

27 / 1




Modelos, satisfactibilidad, . . .

Dada una interpretación I = (A, υ), si [[ϕ]]Aυ = cierto se diceA satisface ϕ en el estado υ o que I satisface ϕ o bienI es un modelo de ϕ y se nota como:

A |= ϕυ

(En el caso de que [[ϕ]]Aυ = falso se dice que I no satisface ϕy se denota como A 6|= ϕυ)

Una fórmula es satisfactible si admite un modelo, einsatisfactible en otro caso.

Dos fórmulas ϕ y ψ son lógicamente equivalentes (y se escribeϕ ≈ ψ) sii [[ϕ]]Aυ = [[ψ]]Aυ para toda interpretaciónI = (A, υ)ϕ es lógicamente válida sii I |= ϕ para toda interpretación I

28 / 1




Consecuencia lógica

Dadas las fórmulas ϕ1, . . . , ϕn, ψ ∈ LΣ se dice que ψ es unaconsecuencia lógica de {ϕ1, . . . , ϕn} y se escribe:

{ϕ1, . . . , ϕn}︸︷︷︸hipóteis o premisas

|= ψ︸︷︷︸conclusión

sii para toda interpretación I = (A, υ) se tiene:

I |= ϕ1, . . . , I |= ϕn ⇒ I |= ψ

Teorema

{ϕ1, . . . , ϕn} |= ψ ⇔ {ϕ1, . . . , ϕn,¬ψ} es insatisfactible

29 / 1




Ejemplo

Consideremos la argumentación:

Algunos maḿıferos leen a QuevedoTodos los lectores de Quevedo disfrutan

∴ Algunos maḿıferos disfrutan

Formalizada:ϕ1 ≡ ∃X .(mamifero(X ) ∧ lee(X , q))ϕ2 ≡ ∀X .(lee(X , q)→ disfruta(X ))

∴ ψ ≡ ∃X .(mamifero(X ) ∧ disfruta(X ))

¿{ϕ1, ϕ2} |= ψ?, es decir, ¿cualquier interpretación (A, υ) quesatisfaga ϕ1 y ϕ2 satisface ψ? Como todas las fórmulas soncerradas lo que hay que probar es:

A |= ϕ1, A |= ϕ2 ⇒ A |= ψ

30 / 1




Ejemplo (cont)

A |= ϕ1 quiere decir (véase definición de página 27) queexiste un a ∈ DA tal que mamiferoA(a) y lee(a, qA)

A |= ϕ2 quiere decir que cualquier b ∈ DA que verifiqueleeA(b, cA) verifica también disfrutaA(b). En particular setendrá disfrutaA(a)

Aśı hemos encontrado un a ∈ DA que verifica mamiferoA(a) ydisfrutaA(a)

Por lo tanto (pag. 27) A |= ∃X .(mamifero(X ) ∧ disfruta(X ))

Este “metodo” de demostración es tedioso... además queremos unmecanismo “automatizable”.

31 / 1




Formas normales en lógica de predicados

Para manipular predicados de manera automática (en unordenador) nos interesa que éstos tengan un formato uniforme.

Interesa además que este formato sea lo más simple posible.

La justificación de fondo es que necesitamos tenerlos en formanormal con el fin de poder utilizar el mecanismo de resolución(que veremos más adelante).

32 / 1




Formas normales conjuntivas

Algunos conceptos nuevos:

Un literal es cualquier fórmula atómica (literal positivo) onegación de una fórmula atómica (literal negativo).

Una cláusula disyuntiva es cualquier disyunción de literales.

Una fórmula está en forma normal conjuntiva (FNC) si es unaconjunción de cláusulas disyuntivas.

Por ejemplo, la siguiente fórmula está en FNC:

(r(a,X , f (a))︸︷︷︸lit. pos.

∨¬p(Y )︸︷︷︸lit. neg.︸︷︷︸

disyunción

) ∧ (q(g(X ,Y ), a)︸︷︷︸lit. pos.

∨¬r(X ,Y ,Z )︸︷︷︸lit. neg.︸︷︷︸

disyunción

)

︸︷︷︸conjunción

33 / 1




Formas prenexas y de Skolem

Una fórmula ϕ ∈ LΣ está en forma prenexa si es de la forma

ϕ ≡ Q1X1.Q2X2. . . . .QnXn.ψ

donde Q1, . . . ,Qn ∈ {∃,∀} y ψ no tiene cuantificadores.Diremos que Q1X1.Q2X2. . . . .QnXn. es el prefijo y ψ el núcleode la forma prenexa.

Una fórmula ϕ ∈ LΣ está en forma normal de Skolem siestá en forma prenexa y en su prefijo solo hay cuantificadoresuniversales.

Una fórmula ϕ ∈ LΣ está en forma normal conjuntiva y deSkolem si está en forma normal de Skolem y su núcleo está enFNC.

Por ejemplo:

∀X .∀Y .∀Z .((r(a,X , f (a))∨¬p(Y ))∧(q(g(X ,Y ), a)∨¬r(X ,Y ,Z )))34 / 1




Existencia de FNC’s de Skolem

Antes de nada:

ϕ y ψ son equisatisfactibles si y solo si

ϕ es satisfactible ⇔ ψ es satisfactible

Y ahora el resultado que buscamos:

Teorema

Para toda ϕ ∈ LΣ existe una sentencia SKO(ϕ) en forma normalconjuntiva y de Skolem tal que ϕ y SKO(ϕ) son equisatisfactibles.

La demostración de este teorema es constructiva: nos proporcionaun método efectivo para obtener esa sentencia SKO(ϕ)

35 / 1




Obtención de FNC’s de Skolem

Paso 1: eliminar de ϕ todas las conectivas → y ↔ utilizandolas equivalencias lógicas:

ϕ→ ψ ≈ ¬ϕ ∨ ψϕ↔ ψ ≈ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ)

Paso 2: renombrar las variables ligadas (de dentro haciaafuera) para evitar la “captura de variables” de modo que

ninguna variable tenga apariciones libres y ligadastodos los cuantificadores se refieran a variables distintas

Paso 3: hacer el cierre existencial de todas las variables libres

Si Y1, . . . ,Yn son las variables libres de ϕ, el cierre existenciales ∃Y1. . . . .∃Yn.ϕ

36 / 1




Obtención de FNC’s de Skolem (cont.)

Paso 4: obtener una forma normal prenexa utilizando lasequivalencias lógicas:

¬∃X .ϕ ≈ ∀X .¬ϕ

¬∀X .ϕ ≈ ∃X .¬ϕ

QX .ϕ ∧ ψ ≈ QX .(ϕ ∧ ψ), con Q ∈ {∃,∀} y X 6∈ var(ψ)

QX .ϕ ∨ ψ ≈ QX .(ϕ ∨ ψ), con Q ∈ {∃,∀} y X 6∈ var(ψ)

ϕ ∧ ψ ≈ ψ ∧ ϕ

ϕ ∨ ψ ≈ ψ ∨ ϕ

37 / 1




Obtención de FNC’s de Skolem (cont.)

Paso 5: eliminar los cuantificadores existenciales aplicando latransformación siguiente hasta que no queden cuantificacionesexistenciales:

∀X1. . . . .∀Xn.∃Y .QY1. . . . .QYm.ϕ (n ≥ 0)⇓

∀X1. . . . .∀Xn.QY1. . . . .QYm.ϕ[Y /f (X1, . . . ,Xn)]donde f es un nuevo śımbolo de función de aridad n (lasignatura Σ se ampĺıa con nuevos śımbolos de función detalle técnico).

(en el caso n = 0 la función, será en realidad una constante).

Paso 6: transformar el núcleo en una forma normal conjuntiva,utilizando:

ϕ ∨ (ψ ∧ χ) ≈ (ϕ ∨ ψ) ∧ (ϕ ∨ χ)(ψ ∧ χ) ∨ ϕ ≈ (ψ ∨ ϕ) ∧ (χ ∨ ϕ)

38 / 1




FNC’s de Skolem

A la vista del algoritmo anterior...

¿cómo se obtiene una sentencia (fórmula cerrada) a partir deuna fórmula?, i.e., ¿dónde quedan ligadas las variables libresde la fórmula original?

¿por qué se obtiene una sentencia equisatisfactible y no unalógicamente equivalente?, ¿en qué paso(s) se pierde laequivalencia lógica?

¿por qué no se pierde la equisatisfactibilidad en dichos pasos?

Nótese que una sentencia en FNC de Skolem está uńıvocamentedeterminada por su núcleo.

39 / 1




Ejemplo de obtención de FNC de Skolem

ϕ ≡ ∀X .q(X ,Y ) ∨ ∃X .p(X )→∀Z .r(X ,Y ,Z ) ∧ ∃X .q(X ,Y )

⇓ paso 1, eliminación de →

¬(∀X .q(X ,Y ) ∨ ∃X .p(X )) ∨ (∀Z .r(X ,Y ,Z ) ∧ ∃X .q(X ,Y ))

⇓ paso 2, renombramiento

¬(∀X1.q(X1,Y ) ∨ ∃X2.p(X2)) ∨ (∀Z .r(X ,Y ,Z ) ∧ ∃X3.q(X3,Y ))

⇓ paso 3, cierre existencial

∃X .∃Y .¬(∀X1.q(X1,Y )∨∃X2.p(X2))∨(∀Z .r(X ,Y ,Z )∧∃X3.q(X3,Y ))

40 / 1




Ejemplo de obtención de FNC de Skolem (cont.)

∃X .∃Y .¬(∀X1.q(X1,Y )∨∃X2.p(X2))∨(∀Z .r(X ,Y ,Z )∧∃X3.q(X3,Y ))

⇓ paso 4, forma prenexa

∃X .∃Y .(∃X1.¬q(X1,Y )∧∀X2.¬p(X2))∨(∀Z .r(X ,Y ,Z )∧∃X3.q(X3,Y ))

⇓ paso 4, forma prenexa cont

∃X .∃Y .∃X1.∀X2.∀Z .∃X3︸︷︷︸en cualquier orden

.(¬q(X1,Y )∧¬p(X2))∨(r(X ,Y ,Z )∧q(X3,Y ))

41 / 1




Ejemplo de obtención de FNC de Skolem (cont.)

∃X .∃Y .∃X1.∀X2.∀Z .∃X3.(¬q(X1,Y )∧¬p(X2))∨(r(X ,Y ,Z )∧q(X3,Y ))

⇓ paso 5, eliminación de ∃{

X/a Y /b X1/cX3/f (X2,Z )

∀X2.∀Z .(¬q(c , b) ∧ ¬p(X2)) ∨ (r(a, b,Z ) ∧ q(f (X2,Z ), b))

⇓ paso 6, FNC

SKO(ϕ) ≡ ∀X2.∀Z . (¬q(c , b) ∨ r(a, b,Z ))∧ (¬p(X2) ∨ r(a, b,Z ))∧ (¬q(c , b) ∨ q(f (X2,Z ), b))∧ (¬p(X2) ∨ q(f (X2,Z ), b))

42 / 1




Formas clausadas

Sea una fórmula ϕ y su FNC de Skolem

SKO(ϕ) ≡ ∀X1. . . . .∀Xn.((ψ1 ∨ . . . ∨ ψn) ∧ . . . ∧ (φ1 ∨ . . . ∨ φm))

La forma clausada de ϕ, FC (ϕ) es el conjunto

{{ψ1, . . . , ψn}︸︷︷︸cláusula

, . . . , {φ1, . . . , φm}︸︷︷︸cláusula

}

SKO(ϕ) está uńıvocamente determinada por su núcleo: lascuantificaciones están impĺıcitas, i.e., todas las variables de lascláusulas (que aparecen como variables libres) están impĺıcitamentecuantificadas universalmente.

43 / 1




Notación de Kowalski para formas clausadas

Según hemos visto que cada cláusula es un conjunto de literales(positivos o negativos), que puede expresarse de la forma:

{ϕ1, . . . , ϕn,¬ψ1, . . . ,¬ψm}donde ahora los ϕi y ψj son todos literales positivos (lasnegaciones se ponen expĺıcitamente. En notación de Kowalski, estacláusula se escribe como:

ϕ1, . . . , ϕn︸︷︷︸consecuente

← ψ1, . . . , ψm︸︷︷︸antecedente

Nótese que las “comas” de la izquierda deben interpretarse como∨, mientras que las de la derecha se interpretan como ∧... ¿porqué?Hay tres tipos de cláusulas especiales:

Γ←︸︷︷︸hechos

← ∆︸︷︷︸objetivos

←︸︷︷︸lógicamente equivalente a ⊥

44 / 1




Ejemplo

Para la fórmula del ejemplo anterior (pág. 41):

ϕ ≡ ∀X .q(X ,Y ) ∨ ∃X .p(X )→ ∀Z .r(X ,Y ,Z ) ∧ ∃X .q(X ,Y )

obteńıamos la FNC de Skolem:

∀X2.∀Z . (¬q(c , b) ∨ r(a, b,Z )) ∧ (¬p(X2) ∨ r(a, b,Z ))∧ (¬q(c , b) ∨ q(f (X2,Z ), b)) ∧ (¬p(X2) ∨ q(f (X2,Z ), b))

La forma clausada en notación de Kowalski es:

r(a, b,Z ) ← q(c , b)r(a, b, z) ← p(X2)

q(f (X2,Z ), b) ← q(c , b)q(f (X2,Z ), b) ← p(X2)

(Este formato es mucho más manejable para la manipulaciónautomática, como veremos)

45 / 1



De la lógica a la programación lógica Poniendo todo en marcha

Se buscan modelos

Recordemos cómo se defińıan las estructuras (pag. 21) y losmodelos (pag. 29) en lógica de predicados.

La definición de estas estructuras admite conjuntos arbitrarioscomo universo: no hay una pauta para determinar los valoresdel dominio; y tampoco las funciones y relaciones que sedefinen asociadas a los śımbolos de la signatura.

En consecuencia, tampoco tenemos pauta para encontrar losmodelos para las fórmulas (pag. 29).

Pero hay unas estructuras canónicas que facilitarán labúsqueda de modelos: las estructuras de Herbrand.

46 / 1




Universo de Herbrand

Sea ϕ una sentencia en FNC de Skolem. El universo deHerbrand para ϕ, Uϕ es el conjunto de términos cerrados (sinvariables) que pueden construirse con los śımbolos deconstante y función de ϕ. En concreto:

Todo śımbolo de constante que aparece en ϕ está en Uϕ. Si ϕno tiene ningún śımbolo de constante, se añade uno cualquieraa (para evitar que Uϕ = ∅);Para todo śımbolo de función f n que aparece en ϕ y todoconjunto de términos t1, . . . , tn ∈ Uϕ, se tienef (t1, . . . , tn) ∈ Uϕ.

Por ejemplo:

Si ϕ = ∀X .∀Y .p(X , f (Y )) entoncesUϕ = {a, f (a), f (f (a)), . . .} = {f n(a) | n ≥ 0}Si ϕ = ∀X .∀Y .q(c, f (X ), h(Y , b)) entoncesUϕ = {c, b, f (c), f (b), h(c, c), h(c, b), h(b, c), h(b, b), f (f (c)), f (f (b)), f (h(c, c)), . . .}

47 / 1




Estructura de Herbrand

Sea ϕ una sentencia en FNC de Skolem. Toda estructura:

Hϕ = (DHϕ , {f Hϕ | f ∈ SF aparece en ϕ},{pHϕ | p ∈ SP aparece en ϕ})

tal que:

DHϕ = Uϕ

f Hϕ(t1, . . . , tn) = f (t1, . . . , tn) para todo f ∈ SF n queaparece en ϕ y t1, . . . , tn ∈ Uϕ

es una estructura de Herbrand.

La idea es que las constantes y las funciones estén autodefinidas(solo son śımbolos, sin otro significado que el del propio śımbolo:la sintaxis coincide con la semántica).Nótese que la elección de pHϕ sigue siendo arbitraria.

48 / 1




Ejemplo

Para ϕ = ∀X .∀Y .p(X , f (Y )) tenemos Hϕ = (Uϕ, {aHϕ , fHϕ }, {pHϕ })donde:

aHϕ = a

f Hϕ (t) = f (t) para todo t ∈ UϕpHϕ ⊆ (Uϕ × Uϕ)

Para ϕ = ∀X .∀Y .q(c, f (X ), h(Y , b)) tenemos:Hϕ = (Uϕ, {cHϕ , bHϕ , fHϕ , hHϕ }, {qHϕ })

donde:

bHϕ = b cHϕ = c

f Hϕ (t) = f (t) para todo t ∈ UϕhHϕ (t, s) = h(t, s) para todo t, s ∈ UϕqHϕ ⊆ (Uϕ × Uϕ × Uϕ)

49 / 1




Base de Herbrand

Dada una sentencia ϕ en FNC y de Skolem, la base de HerbrandBϕ para ϕ es el conjunto de todos los átomos cerrados construidoscon śımbolos de predicado de ϕ con elementos del universo deHerbrand como argumentos:

Bϕ = {p(t1, . . . , tn) | p ∈ SPn que aparece en ϕ y t1, . . . , tn ∈ Uϕ}

Por ejemplo, para ϕ = ∀X .∀Y .p(X , f (Y )) tenemos

Bϕ = {p(a, a), p(a, f (a)), p(f (a), a), p(f (a), f (a)), . . .}

50 / 1




Satisfactibilidad y modelos de Herbrand

Teorema

Dada una sentencia ϕ en FNC y de Skolem se tiene

ϕ es satisfactible ⇔ ϕ tiene un modelo de Herbrand

¿Por qué es importante este teorema?

Por definición (pag. 29) dećıamos que una fórmula era satisfactiblesi teńıa un modelo. Este teorema nos permite restringir labúsqueda de esos modelos a modelos de Herbrand.

51 / 1




Ejemplo

Supongamos:

ϕ ≡ ∀X .∀Y .∀Z .( suma(c ,X ,X )∧(suma(X ,Y ,Z )→ suma(suc(X ),Y , suc(Z )))

(... ¿qué estamos formalizando aqúı?)

Tenemos

ψ ≡ SKO(ϕ) ≡ ∀X .∀Y .∀Z .( suma(c ,X ,X )∧(¬suma(X ,Y ,Z ) ∨ suma(suc(X ),Y , suc(Z )))

Uψ = {c , suc(c), suc(suc(c)), . . .}Hψ = ({c , suc(c), suc(suc(c)), . . .}, {sucHψ}, {sumaHψ})

tal que: sucHψ(t) = suc(t), para todo t ∈ Uψ

52 / 1




Ejemplo (cont.)

Nótese que todo t ∈ Uψ será de la forma

t = suc(suc(. . . (suc(c)) . . .))

Abreviamos suc2(c) = suc(suc(c)) y análogo parasuc3(c), suc4(c), . . . , sucn(c), . . .

La base de Herbrand será el conjunto:

Bϕ = {suma(sucn(c), sucm(c), suck(c)) | n,m, k ≥ 0}

Por ejemplo:

suma(suc2(c), suc3(c), suc5(c)) ∈ Bϕpero también suma(suc2(c), suc4(c), c) ∈ Bϕ

En el modelo nos interesa el subconjunto de Bϕ formado por loselementos de la forma suma(sucm(c), sucn(c), suck(c)) que hagancierta ψ (que intuitivamente serán los que cumplan n + m = k).

53 / 1




Ejemplo (cont.)

Ahora buscamos un modelo de Herbrand de ψ.

La estructura de Herbrand ha definido todos los elementos de Hψexcepto el śımbolo de predicado sumaHψ . Lo definimos delsiguiente modo:

sumaHψ = {(sucm(c), sucn(c), suck(c)) | m + n = k}Veamos que Hψ es un modelo de ψ. De hecho, no tenemos quedefinir ninguna valoración, porque ψ es cerrada (no contienevariables libres). Olvidandonos de la valoración tenemos que probar:

Hψ |= ψes decir,

Hψ |= ∀X .∀Y .∀Z .suma(c, X , X )∧(¬suma(X , Y , Z)∨suma(suc(X ), Y , suc(Z)))

54 / 1




Ejemplo (cont.)

Calculemos el valor veritativo de ψ en la estructura Hψ:[[ψ]]Hψ = cierto sii

para todo u1, u2, u3 ∈ Uψ.[[suma(c , u1, u1) ∧(¬suma(u1, u2, u3) ∨ suma(suc(u1), u2, suc(u3))]]Hψ = ciertosii

para todo u1, u2, u3 ∈ Uψ se tiene[[suma(c , u1, u1)]]

Hψ = cierto y[[¬suma(u1, u2, u3) ∨ suma(suc(u1), u2, suc(u3))]]Hψ = ciertosii

para todo u1, u2, u3 ∈ Uψ se tiene (c , u1, u1) ∈ sumaHψ y(u1, u2, u3) 6∈ sumaHψ ∨ (suc(u1), u2, suc(u3)) ∈ sumaHψ siipara todo n1, n2, n3 ∈ IN se tiene 0 + n1 = n1 yn1 + n2 = n3 ⇒ (n1 + 1) + n2 = n3 + 1cierto

55 / 1




Instancias básicas

Sea ϕ una sentencia en FNC y de Skolem de la forma:

ϕ ≡ ∀X1. . . .∀Xn. C1 ∧ . . . ∧ Cm

donde cada Ci es una cláusula (disyunción de literales).

Definimos el conjunto de instancias básicas de ϕ como:

IB(ϕ) = {Ci [X1/t1, . . . ,Xn/tn]︸︷︷︸sustitución

| t1, . . . , tn ∈ Uϕ}

Por ejemplo, para la fórmulaψ ≡ ¬suma(X ,Y ,Z ) ∨ suma(suc(X ),Y , suc(Z )) tenemos:

IB(ψ) = { ¬suma(c, c, c) ∨ suma(suc(c), c, suc(c)),¬suma(suc2(c), suc4(c), suc6(c) ∨ suma(suc3(c), suc4(c), suc7(c)), . . .¬suma(suc1(c), suc5(c), suc3(c)) ∨ suma(suc2(c), suc5(c), suc4(c)), . . .}

56 / 1




Acotando el problema de la satisfactibilidad

Teorema (Gödel-Herbrand-Skolem)Dada una sentencia ϕ en FNC y de Skolem:

ϕ es satisfactible ⇔ IB(ϕ) es satisfactible

... ¿por qué es interesante este resultado?

Porque traslada el problema de la satisfactibilidad de la lógica depredicados a la lógica proposicional: IB(ϕ) es una fórmula sinvariables, ni cuantificadores abordable en lógica proposicional.

Pero, a la vista del Teorema de la página 31, más que lasatisfactibilidad nos interesa la insatisfactibilidad de cara a probarla validez de argumentaciones.

En este sentido, tenemos el teorema de la página siguiente...

57 / 1




Acotando el problema de la insatisfactibilidad

Teorema (Herbrand)Dada una sentencia ϕ en FNC y de Skolem:

ϕ es insatisfactible ⇔ existe un subconjunto finitode IB(ϕ) que es insatisfactible

La importancia de este teorema está en que no solo traslada elproblema a la lógica proposicional, lo cual es una tremendasimplificación, sino que permite abordarlo en el ámbito de lafinitud es un paso más para aproximar la lógica a laprogramación lógica

58 / 1




Un ejemplo

Consideremos la fórmula ψ con la que venimos trabajando:

ψ ≡ ∀X .∀Y .∀Z .( suma(c,X ,X )∧(¬suma(X ,Y ,Z) ∨ suma(suc(X ),Y , suc(Z)))

Y una nueva fórmula:φ ≡ suma(suc(c), suc2(c), suc3(c))

Intuitivamente parece razonable pensar que {ψ} |= φ, o de maneraequivalente (teorema de la pag. 31) {ψ,¬φ} es insatisfactible, oequivalentemente ψ ∧ ¬φ es insatisfactiblePor el teorema anterior basta con encontrar un subconjunto finitode IB(ψ ∧ ¬φ) que sea (proposicionalmente) insatisfactible. Fácil:{ suma(c, suc2(c), suc2(c)),

suma(suc(c), suc2(c), suc3(c)) ∨ ¬suma(c, suc2(c), suc2(c)),¬suma(suc(c), suc2(c), suc3(c)) } ...por qué es insatisfactible?

59 / 1




A pesar de todo...(incursiones en computabilidad)

Esta demostrado que:

El problema de la satisfactibilidad para la lógica de predicadoses indecidible: dada una fórmula ϕ, la pregunta ¿es ϕsatisfactible? es indecidible.

El problema de la insatisfactibilidad para la lógica depredicados es semi-decidible:existe un algoritmo P tal que dada una fórmula ϕ:

Si P para actuando sobre ϕ entonces ϕ es insatisfactible

(Este algoritmo se basa en la teoŕıa de Herbrand).

60 / 1




De la lógica a la programación lógica

Unificación

Resolución

61 / 1




Estado del arte

Sabemos:

Cómo representar conocimiento mediante argumentaciones y cómo formalizarestas argumentaciones en el lenguaje de la lógica.

Cómo transformar las fórmulas lógicas en cláusulas.

Demostrar validez de una argumentación es refutar (demostrar lainsatisfactibilidad) de un conjunto de fórmulas:

premisas + negación de la conclusión

(... quizá sepamos algo de tableaux?)

Queremos saber:

Un método para construir refutaciones utilizando la formaclausal.

Una forma de plasmar ese método en un algoritmo concreto.

Muchas más cosas... ... pero, comencemos con la unificación.

62 / 1




Sustituciones

Una sustitución σ es un conjunto de ligaduras de la forma:

σ = {X1/t1, . . . ,Xn/tn}

donde X1, . . . ,Xn ∈ V, t1, . . . , tn ∈ TΣ(V), Xi 6= Xj para todoi 6= j y Xi 6= ti para todo i ∈ {1..n}

Aplicar una sustitución σ = {X1/t1, . . . ,Xn/tn} a un términot se denota como tσ ó t[X1/t1, . . . ,Xn/tn] y consiste enreemplazar (simultáneamente) en t cada una de lasapariciones de X1 por t1,. . . , cada una de las apariciones deXn por tn (análogo para fórmulas). Las sustituciones puedencomponerse: tσθ = (tσ)θ

Una sustitución σ es idempotente sii σσ = σ.

¿Es idempotente σ = {X/f (X )}? ¿Y θ = {X/f (Y ),Y /a}?63 / 1




Unificadores

Un sistema de ecuaciones S = {s1 = t1, . . . , sn = tn} (consi , ti ∈ TΣ(V)) es unificable sii existe una sustitución σ talque s1σ = t1σ, . . . , snσ = tnσ.En tal caso se dice que σ es un unificador para S .

Dado un sistema de ecuaciones S , diremos que σ es ununificador de máxima generalidad (u.m.g) para S sii σ es ununificador para S y para todo θ unificador de S existe unasustitución τ tal que θ = στ (σ es más general que θ).

Por ejemplo, si S = {f (X ,Y ) = f (Z , a), g(Z ) = W }

σ = {X/Z ,Y /a,W /g(Z )} θ = {X/b,Y /a,Z/b,W /g(b)}

ambos son unificadores de S , σ es un u.m.g. y θ no lo es... ¿porqué?

64 / 1




Sistemas de ecuaciones en forma resuelta

Un sistema de ecuaciones está en forma resuelta si es de laforma

{X1 = t1, . . . ,Xn = tn}

siendo Xi ∈ V para todo i ∈ {1..n}, Xi 6= Xj para todo i 6= j yXi no aparece en tj para todo i , j ∈ {1..n}

Si el sistema de ecuaciones está en forma resuelta representala sustitución [X1/t1, . . . ,Xn/tn] y esta sustitución esidempotente... ¿por qué?

Ahora nos interesa un algoritmo de unificación que tome comoentrada un sistema de ecuaciones y obtenga un sistema deecuaciones en forma resuelta que represente un u.m.g. para elsistema de entrada; o bien que produzca fallo en el caso de que elsistema inicial no sea unificable.

65 / 1




Algoritmo de unificación de Martelli-Montanari

Aplicar alguna de las siguientes reglas mientras sea posible:

1 S ∪ {X = X} S

2 S ∪{f (t1, . . . , tn)= f (s1, . . . , sn)} S ∪{t1 =s1, . . . , tn =sn}

3 S ∪ {f (t1, . . . , tn) = g(s1, . . . , sm)} FALLO,si f 6= g (ó n 6= m)

4 S ∪ {X = t} S [X/t] ∪ {X = t},si X 6∈ var(t), X ∈ var(S), X 6= t

5 S ∪ {X = t} FALLO, si X ∈ var(t)

6 S ∪ {t = X} S ∪ {X = t}, si t 6∈ V

Este algoritmo proporciona u.m.g.’s idempotentes

66 / 1




Ejemplo

{f (X ,Y ) = f (Z , g(b)), g(Z ) = g(W ), h(Y ) = X} 2 {X = Z ,Y = g(b),Z = W , h(Y ) = X} 6 {X = Z ,Y = g(b),Z = W ,X = h(Y )} 4 {X = Z ,Y = g(b),Z = W ,Z = h(Y )} 4 {X = Z ,Y = g(b),Z = W ,Z = h(g(b))} 4 {X = W ,Y = g(b),Z = W ,W = h(g(b))} 4 {X = h(g(b)),Y = g(b),Z = h(g(b)),W = h(g(b))}

No se pueden aplicar más reglas, hemos terminado.Si sobre el sistema inicial aplicamos la sustituciónσ = [X/h(g(b)),Y /g(b),Z/h(g(b)),W /h(g(b))] obtenemos:

{f (X ,Y )= f (Z , g(b)), g(Z)=g(W ), h(Y )=X}σ={f (h(g(b)), g(b))= f (h(g(b)), g(b)), g(h(g(b)))=g(h(g(b))), h(g(b))=h(g(b))}

67 / 1




Unificador para un conjunto de literales

Dado un conjunto finito de literales Γ (fórmulas atómicas osus negaciones), una sustitución σ es unificador de Γ sii paratodo L, L′ ∈ Γ, Lσ = L′σ.

Una sustitución σ es un u.m.g. para Γ si es unificador para Γ yes más general que cualquier otro unificador (pág. 65).

Teorema (J.A. Robinson 1965)Dado un conjunto de literales Γ existe un algoritmo que decide si Γes o no unificable, y en caso afirmativo devuelve un u.m.g. para Γque además es idempotente.

La propia demostración proporciona el algoritmo... veamos

68 / 1




Algoritmo de unificación para conjuntos de literales

En Γ todos los literales han de ser positivos o negativos (si no,directamente no seŕıa unificable)

Además todos los literales deben tener en cabeza el mismośımbolo de predicado (si no, no seŕıa unificable)

Aśı pues, se trata de encontrar un u.m.g. para

{p(t11 , . . . , t1n), . . . , p(tM1 , . . . , tMn )}o para

{¬p(t11 , . . . , t1n), . . . ,¬p(tM1 , . . . , tMn )}En definitiva, se trata de encontrar un u.m.g. para el sistema

{t ji = tki | i ∈ {1..n}, j , k ∈ {1..M}}

para lo cual se puede utilizar el algoritmo deMartelli-Montanari, que proporciona un u.m.g. idempotente.

69 / 1




Ejemplo

Buscamos un umg paraΓ = {p(f (Z , g(a,Y )), h(Z )), p(f (f (U,V ),W ), h(f (a, b)))}

Planteamos el sistema correspondiente y aplicamos el algoritmo deMartelli-Montanari:

S = {f (Z , g(a,Y )) = f (f (U,V ),W ), h(Z ) = h(f (a, b))}

2 {Z = f (U,V ), g(a,Y ) = W , Z = f (a, b)}

4 {Z = f (U,V ), g(a,Y ) = W , f (U,V ) = f (a, b)}

2 {Z = f (U,V ), g(a,Y ) = W , U = a, V = b}

6 {Z = f (U,V ), W = g(a,Y ), U = a, V = b}

4 {Z = f (a, b), W = g(a,Y ), U = a, V = b}

El umg buscado es [Z/f (a, b), W /g(a,Y ), U/a, V /b]

70 / 1




Un ejemplo de fallo

Γ = {p(f (X ,Y ), g(X ,Y )), p(f (h(U),V ), g(U, h(V )))}Planteamos sistema y aplicamos algoritmo de MM:

S = {f (X ,Y ) = f (h(U),V ), g(X ,Y ) = g(U, h(V ))}

2 {X = h(U), Y = V , X = U, Y = h(V )}

4 {X = h(U), Y = V , h(U) = U, Y = h(V )}

6 {X = h(U), Y = V , U = h(U), Y = h(V )}

5 FALLO

Esto es lo que se llama fallo de “occur-check”.

71 / 1




Resolución general (hacia el “método”)

Sean dos cláusulas C1 y C2 de la forma (en notación de Kowalski)(Γi ,∆j son conjuntos de literales y + es la concatenación)

C1 ≡ Γ1 ← ∆1 + L1, . . . , Ln C2 ≡ L′1, . . . , L′m + Γ2 ← ∆2

tales que

var(C1) ∩ var(C2) = ∅ (si no renombramiento){L1, . . . , Ln, L′1, . . . , L′m} son unificables

Un resolvente (general) C3 = resol(C1,C2) se obtiene como:

C1 ≡ Γ1 ← ∆1 + L1, . . . , Ln C2 ≡ L′1, . . . , L′m + Γ2 ← ∆2

C3 ≡ (Γ1 + Γ2 ← ∆1 + ∆2)θθ = umg({L1, . . . , Ln, L′1, . . . , L′m})

72 / 1




Derivaciones y refutaciones

Dado un conjunto de cláusulas S definimos la relación ↪→ comoS ↪→ S ∪ {resol(C1,C2)} siendo C1,C2 ∈ S

Una cláusula C es derivable por resolución general a partir deS si existe k ∈ IN tal que

S ↪→ S1 ↪→ k. . . ↪→ Skde modo que C ∈ Sk . En ese caso escribiremos S `RG C .

S es refutable mediante resolución general si S `RG ⊥ (esdecir se obtiene la cláusula vaćıa ←). En este caso lasecuencia de resolventes constituye una refutación.

73 / 1




Poniendo todo en marcha

formalización + teoremas + FNC’s de Skolem + resolución +unificación

74 / 1




Ejemplo

Consideremos la argumentación de la pág 31:

Algunos maḿıferos leen a QuevedoTodos los lectores de Quevedo disfrutan

∴ Algunos maḿıferos disfrutan

y su formalización:ϕ1 ≡ ∃X .(mam(X ) ∧ lee(X , q))ϕ2 ≡ ∀X .(lee(X , q)→ dis(X ))

∴ ψ ≡ ∃X .(mam(X ) ∧ dis(X ))

Por el teorema de la página 31 tenemos:

{ϕ1, ϕ2} |= ψ ⇔ {ϕ1, ϕ2,¬ψ} es insatisfactible

75 / 1




Ejemplo (cont.)

Buscamos una refutación de {ϕ1, ϕ2,¬ψ}:Primero ¬ψ ≡ ∀X .(¬mam(X ) ∨ ¬dis(X ))

Ahora ponemos las fórmulas en FNC’s de Skolem:

SKO({ ∃X .(mam(X ) ∧ lee(X , q)),∀X .(lee(X , q)→ dis(X )),∀X .(¬mam(X ) ∨ ¬dis(X ))})

={mam(a) ∧ lee(a, q)),¬lee(X , q) ∨ dis(X )),¬mam(X ) ∨ ¬dis(X ))}

La forma clausal es:{{mam(a)}, {lee(a, q))}, {¬lee(X , q) ∨ dis(X ))}, {¬mam(X ) ∨ ¬dis(X ))}}

Y en notación de Kowalski:

mam(a)←lee(a, q)←

dis(X )← lee(X , q)← mam(X ), dis(X )

76 / 1




Ejemplo (cont.)

Refutemos por resolución general:

Programa:

mam(a)←lee(a, q)←dis(X )← lee(X , q)← mam(X ), dis(X )

mam(a)← ← mam(X ), dis(X )

← dis(a)

θ1 = [X/a]

dis(Y )← lee(Y , q) (renombr.)

θ2 = [Y /a]← lee(a, q) lee(a, q)←

←θ3 = [ ]

77 / 1




Otro ejemplo

Todas las porteñas alegres son amigas de algún marinero.Ningún porteño feliz está casado con una porteña triste.Los porteños casados con amigas de marineros son cornudos o marineros.Los marineros casados son infelices.

∴ Los porteños casados con porteñas con cornudos o infelices.

Formalizada:ϕ1 ≡ ∀X .((pa(X ) ∧ al(X ))→ ∃Y .(mr(Y ) ∧ am(X ,Y )))ϕ2 ≡ ∀X .∀Y .((po(X ) ∧ fl(X ) ∧ pa(Y ) ∧ cs(X ,Y ))→ al(Y ))ϕ3 ≡ ∀X .∀Y .∀Z .((po(X )∧cs(X ,Y )∧am(Y ,Z)∧mr(Z))→(cr(X )∨mr(X )))ϕ4 ≡ ∀X .∀Y .((mr(X ) ∧ cs(X ,Y ))→ ¬fl(X ))

∴ ψ ≡ ∀X .∀Y .((po(X ) ∧ cs(X ,Y ) ∧ pa(Y ))→ (cr(X ) ∨ ¬fl(X )))

78 / 1




Ejemplo (cont.)

FNC’s de Skolem:

SKO(ϕ1) ≡ ∀X .((¬pa(X ) ∨ ¬al(X ) ∨mr(f (X )))∧ (¬pa(X ) ∨ ¬al(X ) ∨ am(X , f (X ))))

SKO(ϕ2) ≡ ∀X .∀Y .(¬po(X )∨¬fl(X )∨¬pa(Y )∨¬cs(X ,Y )∨al(Y ))SKO(ϕ3) ≡ ∀X .∀Y .∀Z .(¬po(X )∨¬cs(X ,Y )∨¬am(Y ,Z )∨¬mr(Z )∨cr(X )∨mr(X ))SKO(ϕ4) ≡ ∀X .∀Y .(¬mr(X ) ∨ ¬cs(X ,Y )) ∨ ¬fl(X ))

Negación de la conclusión:

¬ψ ≡ ∃X .∃Y .¬((po(X ) ∧ cs(X ,Y ) ∧ pa(Y ))→ (cr(X ) ∨ ¬fl(X )))≡ ∃X .∃Y .(po(X ) ∧ cs(X ,Y ) ∧ pa(Y )) ∧ ¬cr(X ) ∧ fl(X )))

SKO(¬ψ) ≡ po(a) ∧ cs(a, b) ∧ pa(b) ∧ ¬cr(a) ∧ fl(a)

79 / 1




Ejemplo (cont.)

Forma clausal (not de Kowalski):

C1 ≡ mr(f (X ))← pa(X ), al(X )C2 ≡ am(X , f (X ))← pa(X ), al(X )

}(de SKO(ϕ1))

C3 ≡ al(Y )← po(X ), fl(X ), pa(Y ), cs(X ,Y ) (de SKO(ϕ2))C4 ≡ cr(X ),mr(X )← po(X ), cs(X ,Y ), am(Y ,Z ),mr(Z ) (de SKO(ϕ3))C5 ≡← mr(X ), cs(X ,Y ), fl(X ) (de SKO(ϕ4))C6 ≡ po(a)←C7 ≡ cs(a, b)←C8 ≡ pa(b)←C9 ≡← cr(a)C10 ≡ fl(a)←

(de SKO(¬ψ))

80 / 1




Ejemplo

C4 ≡ cr(X ),mr(X )← po(X ), cs(X ,Y ),am(Y ,Z),mr(Z)

C1 ≡ mr(f (X1))← pa(X1), al(X1)

cr(X ),mr(X )← po(X ), cs(X ,Y ), am(Y , f (X1)),pa(X1), al(X1)

θ1 = [Z/f (X1)]

C2 ≡ am(X2, f (X2))← pa(X2), al(X2)

cr(X ),mr(X )← po(X ), cs(X ,Y ), pa(Y ), al(Y )

θ2 = [ X2/Y ,X1/Y ]

C3 ≡ al(Y3)← po(X3), fl(X3),pa(Y3), cs(X3,Y3)

cr(X ),mr(X )← po(X ), cs(X ,Y ), pa(Y ),po(X3), fl(X3), cs(X3,Y )

θ3 = [Y3/Y ]

C5 ≡← mr(X4), cs(X4,Y4), fl(X4)

cr(X )← po(X ), cs(X ,Y ), pa(Y ), po(X3),fl(X3), cs(X3,Y ), cs(X ,Y4), fl(X )

θ4 = [ X4/X ]

81 / 1




Ejemplo (cont)

cr(X )← po(X ), cs(X ,Y ), pa(Y ), po(X3),fl(X3), cs(X3,Y ), cs(X ,Y4), fl(X )

C7 ≡ cs(a, b)←

cr(a)← po(a), pa(b), fl(a)θ5 = [X/a,Y /b,X3/a,Y4/b]

C6 ≡ po(a)←

cr(a)← pa(b), fl(a) C8 ≡ pa(b)←

cr(a)← fl(a) C10 ≡ fl(a)←

cr(a)← C9 ≡← cr(a)

←

82 / 1




Ejemplo (cont.)

Con esto tenemos una refutación, que es una demostración(deducción) de nuestra argumentación, pero además:

Hemos obtenido una secuencia de sustituciones θ1, . . . , θ5.Si planteamos el sistema de ecuaciones asociado a ellastenemos:

{Z = f (X1),X2 = Y ,X1 = Y ,Y3 = Y ,X4 = X ,X = a,Y = b,X3 = a,Y4 = b}

Si lo resolvemos mediante el algoritmo MM:

{Z = f (b),X2 = b,X1 = b,Y3 = b,X4 = a,X = a,Y = b,X3 = a,Y4 = b}

Que corresponde a la sustitución:

θ = {Z/f (b),X2/b,X1/b,Y3/b,X4/a,X/a,Y /b,X3/a,Y4/b}

83 / 1




Ejemplo (cont.)

Si aplicamos la sustitución

θ = {Z/f (b),X2/b,X1/b,Y3/b,X4/a,X/a,Y /b,X3/a,Y4/b}

a los renombramientos de las claúsulas utilizadas obtenemos unconjunto de instancias básicas que son proposicionalmenteinsatisfactibles:

C1θ ≡ mr(f (b))← pa(b), al(b)C2θ ≡ am(b, f (b))← pa(b), al(b)C3θ ≡ al(b)← po(a), fl(a), pa(b), cs(a, b)C4θ ≡ cr(a), mr(a)← po(a), cs(a, b), am(b, f (b)), mr(f (b))C5θ ≡← mr(a), cs(a, b), fl(a)C6θ ≡ po(a)←C7θ ≡ cs(a, b)←C8θ ≡ pa(b)←C9θ ≡← cr(a)C10θ ≡ fl(a)← ...de verdad son proposicionalmente insatisfactibles??

84 / 1




Otro ejemplo

Pedro es miope.Cuando alguien es miope, o su padre o su madre también es miope.Todo el mundo ama a su padre y a su madre.

∴ Algún miope es amado por alguien.

Formalizada:ϕ1 ≡ miope(p)ϕ2 ≡ ∀X .(miope(X )→ (miope(padre(X )) ∨miope(madre(X ))))ϕ3 ≡ ∀X .(ama(X , padre(X )) ∧ ama(X ,madre(X )))

∴ ψ ≡ ∃X .(miope(X ) ∧ ∃Y .ama(Y ,X ))

... demostrar la validez

85 / 1




Otro ejemplo más

Un dragón es feliz si todos sus hijos pueden volar.Los dragones verdes pueden volar.Un dragón es verde si es hijo de algún dragón verde.

∴ Los dragones verdes son felices.

Formalizada:ϕ1 ≡ ∀X .(∀Y .(hijo(Y ,X )→ vol(Y ))→ fel(X ))ϕ2 ≡ ∀X .(ver(X )→ vol(X ))ϕ3 ≡ ∀X .(∃Y .(hijo(X ,Y ) ∧ ver(Y ))→ ver(X ))

∴ ψ ≡ ∀X .(ver(X )→ fel(X ))

... demostrar la validez

86 / 1




Corrección y completitud de la resolución general

LemaDadas tres cláusulas C , C1 y C2, si C = resol(C1,C2) entonces

{∀C1, ∀C2} |= ∀C

donde ∀C representa el cierre universal de C (análogo para C1 yC2), i.e., la cuantificación universal de todas las variables de C .

Teorema (Corrección y completitud de la RG)Dado un conjunto de cláusulas S se tiene:

S es insatisfactible ⇔ S `RG←

87 / 1




Claúsulas de Horn. Resolución SLD

88 / 1




Refinando la resolución

La resolución general es un mecanismo muy potente dedemostración...

pero tiene un alto grado de indeterminismo:en la selección de las cláusulas con las que hacer resolucióny en la selección de los literales a utilizar en la resolución

Desde el punto de vista computacional es muy ineficiente.

Desde el punto de vista práctico puede sacrificarse algo deexpresividad y obtener un mecanismo más eficiente que sustenteun lenguaje de programación más “realista”:

restringimos la forma de las cláusulas de modo que a lo sumotengan un literal positivo. En notación de Kowalski esto quieredecir que a lo sumo tienen un átomo en el lado izquierdo de ←estudiaremos un método de resolución espećıfico para estetipo de cláusulas.

89 / 1




Cláusulas de Horn

Una cláusula de Horn es una secuencia de literales que contiene alo sumo un literal positivo. Al escribirla en notación de Kowalskitendrá una de estas cuatro formas:

1 Hecho: p ←2 Regla: p︸︷︷︸

cabeza

← q1, . . . , qn︸︷︷︸cuerpo

3 Objetivo: ← q1, . . . , qn4 Éxito: ←

Los hechos y las reglas se denominan cláusulas definidas:

los hechos representan “hechos acerca de los objetos” (denuestro universo de discurso), relaciones elementales entreestos objetos

las reglas expresan relaciones condicionales entre los objetos,dependencias.

90 / 1




Cláusulas de Horn (cont.)

Las reglas engloban todos los casos en el siguiente sentido:

un hecho es una regla con cuerpo vaćıo

un objetivo es una regla con cabeza vaćıa

y el éxito es una regla con cabeza y cuerpo vaćıos

Nótese que en las cláusulas de Horn trabajamos con secuencias deliterales en vez de conjuntos (como veńıamos haciendo con lascláusulas generales). Esto implica dos cosas:

los literales pueden aparecer repetidos en el cuerpo

hay un orden en los literales del cuerpo (podemos hablar delprimer literal, segundo literal, etc).

91 / 1




Predicados y programas lógicos

Un predicado p queda definido por el conjunto de claúsulas(hechos y reglas) cuyas cabezas tienen ese śımbolo depredicado. Aśı pues la definición de un predicado en generaltendrá el aspecto:

p(t1, . . . , tn) ←p(s1, . . . , sn) ←. . .p(u1, . . . , un) ← q1(. . .), . . . , qm(. . .)p(u1, . . . , un) ← r1(. . .), . . . , rk(. . .). . .

(puede haber solo hechos, solo reglas o ambos tipos).

Un programa lógico es un conjunto de definiciones depredicados (es decir, un conjunto de claúsulas definidas:hechos y reglas).

92 / 1




Un ejemplo

Representación de un grafo mediante hechos:

a b

c d

e

arco(a, b)←arco(a, c)←arco(b, d)←arco(c , d)←arco(c , e)←arco(d , e)←

93 / 1




Ejemplo (cont.)

La relación de conexión entre nodos (caminos) puede expresarsemediante reglas:

camino(X ,Y )← X = Ycamino(X ,Y )← arco(X ,Z ), camino(Z ,Y )

(la primera regla, también se podŕıa haber escrito como un hecho:camino(X ,X )← )La lectura de estas dos resglas es:

hay un camino de un nodo a otro, si son el mismo

hay un camino de un nodo X a otro Y si existe un nodo Z talque hay arco entre X y Z , y hay camino entre Z e Y

94 / 1




Ejemplo (cont.)

Ahora, se podŕıa plantear un objetivo, i.e., entendiendo los hechosy las reglas que hemos escrito como premisas podŕıamos plantearuna conclusión y tratar de mostrar la validez de la argumentación.Por ejemplo, podemos plantear los objetivos (o preguntas):

← arco(b, d)← camino(a, d)← camino(a,X )← camino(e,Y )← camino(X ,Y )← camino(X , b), camino(X , d)

los dos primeros son objetivos cerrados porque no contienenvariables, mientras que los restantes son objetivos abiertos.

... ¿qué debeŕıamos obtener (por resolución) en cada caso?95 / 1




Variables lógicas en las cláusulas

Todas las variables lógicas en de una claúsula están cuantificadasuniversalmente de forma impĺıcita. Por ejemplo, en la claúsula:

camino(X ,Y )← arco(X ,Z ), camino(Z ,Y )

impĺıcitamente tenemos:

∀X .∀Y .∀Z .(camino(X ,Y )← arco(X ,Z ), camino(Z ,Y ))

Ahora bien, esta sentencia es lógicamente equivalente a:

∀X .∀Y .(camino(X ,Y )← ∃Z .(arco(X ,Z ), camino(Z ,Y )))

Es decir, las variables que sólo aparecen a la derecha de la claúsulaestán localmente afectadas de una cuantificación existencial. Sedice que son variables existenciales o extra o locales. Interpretarlasexistencialemente facilita la lectura de la cláusula:

Para todo X y todo Y , hay un camino entre X e Y si existe Z talque hay arco de X a Z y hay camino entre Z e Y

96 / 1




Otro ejemplo

Podemos definir la suma de naturales (representados como c y s)mediante un hecho y una regla:

suma(c ,X ,X ) ←suma(s(X ),Y , s(Z )) ← suma(X ,Y ,Z )

y plantear distintos objetivos:

← suma(s(c), s(s(c)), s(s(s(c))))← suma(X , s(c), s(s(c)))← suma(s(c),Y ,Z )← suma(X ,Y ,Z )← suma(X ,X ,Z ), suma(Z ,Z ,H)

97 / 1




SLD-Resolución

Selection-rule driven Linear resolution for Definite clauses

Es un caso particular de la resolución general, donde:

Los resolventes son siempre objetivos (cláusulas sin cabeza).

Los programas son conjuntos de claúsulas (de Horn) definidas,i.e., hechos y reglas.

Hay una función de selección que selecciona un átomo delobjetivo a quien aplicar resolución.

98 / 1




SLD-resolución (cont.)

Formalmente:

Sea un programa lógico P, un par de objetivos G y G ′, y unafunción de selección fs . Una derivación de G a G

′ conSLD-resolución (P ∪ {G} `SLD G ′) es una secuencia deobjetivos G0,G1, . . . ,Gk tal que:

G0 = GGk = G

′

para todo i ∈ {0, ..., k − 1}, Gi+1 de obtiene a partir de Gi“resolviendo” (en el sentido de la resolución general) el literalL = fs(Gi ) con una variante de una regla de P.

Si G ′ ≡←, entonces tenemos una SLD-refutación de G apartir de P.

99 / 1




Ejemplo

Supongamos el programa (c representa cero y s sucesor):

suma(c ,Y ,Y ) ←suma(s(X ),Y , s(Z )) ← suma(X ,Y ,Z )

y el objetivo ← suma(s(c), s(c), s(s(c))) (asumimos que fsselecciona el primer objetivo por la izquierda).

← suma(s(c), s(c), s(s(c))) suma(s(X1), Y1, s(Z1))← suma(X1, Y1, Z1)

← suma(c, s(c), s(c))

θ1 = [X1/c, Y1/s(c), Z1/s(c)]

suma(c, Y2, Y2)←

←

θ2 = [Y2/s(c)]

100 / 1




Respuestas correctas

Dado un programa P y un objetivo G ≡← q1, . . . , qn, diremos queuna sustitución θ es una respuesta correcta para P ∪ {G} si

θ únicamente actúa sobre las variables de G y

P |= ∀X1. . . . .∀Xm(q1 ∧ . . . ∧ qn)θ, siendo {X1, . . . ,Xn} elconjunto de variables de G (notación: P |= [(q1 ∧ . . . ∧ qn)θ]∀)

Por ejemplo, consideremos la siguiente refutación:

G ≡← suma(c, s(A), B) suma(c, Y1, Y1)←

←θ1 = [Y1/s(A), B/s(A)]

La sustitución obtenida, θ1, restringida a las variables del objetivo original G esθ1 |var(G)= [B/s(A)] (la variable Y1 no aparece en en G).θ = [B/s(A)] es una respuesta correcta para G ... por qué?

101 / 1




Respuestas correctas (cont.)

θ = [B/s(A)] es una respuesta correcta para P ∪ {G}:por un lado, aplicando θ tenemos suma(c , s(A), s(A))

y ahora, si consideramos cualquier otra sustitución σtendremos que

P |= suma(c , s(A), s(A))σ

o lo que es lo mismo (ver pag. 27):P |= ∀A.suma(c , s(A), s(A))P |= [suma(c , s(A), s(A))]∀

Intuitivamente, si reemplazamos A por cualquier valor lo queobtenemos pertenecerá al modelo de la primera claúsula de Py por tanto al modelo de P (recordemos que en la página 53estudiamos un modelo de Herbrand para este programa en elque

sumaH = {(sm(c), sn(c), sk (c)) | m + n = k}

102 / 1




Corección y completitud de la SLD-resolución

TeoremaSea P un programa, fs una función de selección y G un objetivo.Tenemos:

Corrección: Si P ∪ {G} `SLD← en n pasos y θ = θ1 . . . θn esla composición de la secuencia de unificadores usados en laSLD-refutación, entonces:

θ′ = θ |var(G) es una respuesta correcta para P ∪ {G}

Completitud: Sea θ una respuesta correcta para P ∪ {G},entonces existe una SLD-refutación de G a partir de P conuna secuencia de unificadores θ1, . . . , θn tal queθ = (θ1 . . . θn) |var(G).

Nótese que la función de selección concreta que se utilice no esrelevante para los resultados de corrección y completitud.

103 / 1




Ejemplo

Consideremos el programa de los caminos en un grafo:

arco(a, b)←arco(a, c)←arco(b, d)←arco(c , d)←arco(c , e)←arco(d , e)←camino(X ,X )←camino(X ,Y )← arco(X ,Z ), camino(Z ,Y )

Y consideremos el objetivo ← camino(X , e)

104 / 1




Ejemplo (cont.)

Una posible refutación (tomando como función de selección la quetoma el primer literal por la izquierda):

← camino(X , e) camino(X1, Y1)← arco(X1, Z1), camino(Z1, Y1)

← arco(X , Z1), camino(Z1, e)

θ1 = [X1/X , Y1/e]

arco(a, c)←

← camino(c, e)

θ2 = [X/a, Z1/c]

105 / 1




Ejemplo (cont.)

← camino(c, e) camino(X3, Y3)← arco(X3, Z3), camino(Z3, Y3)

← arco(c, Z3), camino(Z3, e)

θ3 = [X3/c, Y3/e]

arco(c, e)←

← camino(e, e)

θ4 = [Z3/e]

camino(X4, X4)←

←

θ5 = [X4/e]

106 / 1




Ejemplo (cont.)

La composición de sustituciones obtenidas es:

θ = θ1 . . . θ5 = [X/a,X1/a,Y1/e,Z1/c ,X3/c ,Y3/e,Z3/e,X4/e]

Si consideramos la restricción a las variables del objetivo original,es decir, a X tenemos:

θ′ = θ |{X}= [X/a]

Por el teorema de corrección θ′ = [X/a] es una respuestacorrecta para el objetivo original.

Por el teorema de completitud, este mecanismo debe sercapaz de encontrar además otras respuestas. Intuitivamente esfácil ver que serán [X/b], [X/c], [X/d ], [X/e]... cómo seconstruiŕıan las SLD-refutaciones para encontrar estasrespuestas?

107 / 1




Hacia Prolog

La resolución SLD está mucho más próxima a unaimplementación realista de la programación lógica porque haacotado notablemente el indeterminismo con respecto a laresolucion general.

Las claúsulas de Horn son lo suficientemente expresivas parautilizarlas como lenguaje de programación.

Quedan dos cuestiones por resolver:

¿Qué función de selección utilizamos? (esto, según hemos vistono afecta a la corrección y la completitud).¿Qué criterio seguimos para seleccionar una de las reglasaplicables para resolver un objetivo? (esto, está relacionadocon la completitud).En el último ejemplo, utilizando uno u otro criterio se obtienendistintas respuestas.

108 / 1




PROLOG

109 / 1




Sintaxis de Prolog

Un programa Prolog es un conjunto de cláusulas de Horn (hechosy reglas) donde:

Todas las claúsulas acaban con .El śımbolo ← se escribe como :- que se lee como si(condicional). En los hechos no es necesario (basta poner elátomo y .)Los nombres de predicado y función siguen las pautashabituales de los identificadores pero comienzan conminúscula .Los nombres de variable también siguen esas pautas, perocomienzan por mayúscula .Los átomos en el cuerpo de las reglas se separan mediantecomas , que se leen como y.Ejecutar un programa no tiene sentido como tal (en principio).Lo que se hace es plantear objetivos a resolver.

A partir de ahora utilizaremos esta notación.110 / 1




Función de selección y búsqueda

La función de selección devuelve siempre el primer átomo delobjetivo empezando por la izquierda.

Para resolver un objetivo G el algoritmo elemental seŕıa:

mientras G no sea ciertoelegir una (variante de una) regla de P aplicable a Greducir G por resolución

Pero en un paso de reducción pueden existir varias (variantesde) claúsulas aplicables a G . Por ello surgue el concepto deárbol de búsqueda: Prolog ensaya las distintas claúsulasaplicables a G de manera secuencial y cada uno de estosensayos da lugar a una rama de dicho árbol.

111 / 1




Árboles de búsqueda

Dado un programa Prolog y un objetivo G (asumimos selección delprimer átomo de la izquierda), el árbol de búsqueda para G es unárbol que:

tiene G como ráız

para cada cláusula C de P aplicable a G existe una ramacorrespondiente al árbol de búsqueda del SLD-resolvente de Gy (una variante cualquiera de) C . Además etiquetaremos lasramas con la sustitución correspondiente y la claúsula Caplicada.

En otras palabras: un árbol de búsqueda es un árbol con objetivosen los nodos y cuyas ramas representan los posibles cómputos, i.e.,las posibles claúsulas a aplicar.Nota: no confundir árbol de búsqueda con los árboles de derivación SLD que hemos

visto anteriormente (los árboles de resolución corresponden solo a una rama de los

árboles de búsqueda).

112 / 1




Ejemplo

Trabajemos con un grafo más pequeño y el correspondienteprograma Prolog:

a b

c d

A1 : arco(a,b).A2 : arco(a,c).A3 : arco(a,d).A4 : arco(c,d).

C1 : camino(X,X).C2 : camino(X,Y):- arco(X,Z), camino(Z,Y).

A continuación presentamos el árbol de búsqueda para el objetivocamino(X,d).

113 / 1




Ejemplo (cont.)

camino(X,d)

éxito

C1, [X/d, X1/d]

arco(X,Z1), camino(Z1,d)

C2, [X1/X, Y1/d]

camino(b,d)

A1,[X/a,Z1/b]

arco(b,Z2),camino(Z2,d)

fallo

camino(c,d)

[X/a,Z1/c] A2

arco(c,Z2),camino(Z2,d)

camino(d,d)

éxito

C1

arco(d,Z3),camino(Z3,d)

C2

fallo

camino(d,d)

A3 [X/a,Z1/d]

éxito

C1


C2

fallo

camino(d,d)

A4,[X/c,Z1/d]

éxito

C1


C2

fallo

114 / 1




Prolog: el sistema

Disponible en: http://www.swi-prolog.org/ para distintasplataformas.

Posibilidades de interpretación/compilación.

Habitualmente utilizamos el intérprete. Consola con:

Welcome to SWI-Prolog (Multi-threaded, Version 5.6.14)...For help, use ?- help(Topic). or ?- apropos(Word). ?-

Desde este prompt se lanzan objetivos terminados en .

Para salir

?- halt.

115 / 1




Un programa. Parejas de baile

Sabiendo los invitados que vendrán a una fiesta, determinar posiblesparejas de baile chico/chica.

Escribimos en un archivo de texto ’parejas.pl’:

chica(rosa).

chica(laura).

chica(ana).

chico(pedro).

chico(juan).

chico(pablo).

pareja(X,Y):- chico(X), chica(Y).

Guardamos el archivo y lo consultamos (cargamos) desde elintérprete:

?- [parejas].

o bien

?- consult(parejas). ?- consult(’parejas.pl’).

?- [’/parejas.pl’].

116 / 1

http://www.swi-prolog.org/




Resolviendo objetivos

Qué respuesta(s) debemos obtenter para los siguientes objetivos:

?- pareja(X,Y).

?- pareja(X,ana).

?- pareja(X,juan).

?- pareja(luis,Y).

Desarrollar el árbol de búsqueda para

?- pareja(X,Y).

117 / 1




Operaciones con números naturales

Hemos definido la

jaime sánchez hernández horario, tutor´ıas, método,...

Documents