View
5
Download
0
Category
Preview:
Citation preview
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Programación Lógica
Jaime Sánchez Hernández
Universidad Complutense de MadridDepartamento de Sistemas Informáticos y Programación
Curso 2007-2008
6 de Octubre de 2008
1 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Horario, tutoŕıas, mé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
Tutoŕıas: M y X de 12:00 a 13:00 y de 15:00 a 17:00
Método: clases teó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 (teoŕıa +práctica, 100% de la nota)
2 / 1
http://gpd.sip.ucm.es/jaime/pl
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Contenidos
1 Fundamentos de la programación lógica.
0. Repaso de la lógica de predicados1. Unificación y resolución.2. Cláusulas de Horn. Resolución SLD.
2 Programación en Prolog.
1 Espacios de búsqueda Prolog.2 Programación lógica con números, listas y árboles.3 Control en Prolog.4 Manipulación de términos. Predicados metalógicos.5 Técnicas avanzadas de programación en Prolog.
Utilizaremos el entorno SWI-PROLOG (Open Source; Linux,Windows, MacOS X): http://www.swi-prolog.org/
3 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Bibliograf́ıa
L. Sterling, E. Shapiro. The Art of Prolog. AdvancedProgramming Techniques. The MIT Press, 2a Edició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 Edición, 2003.
A. Apt. From Logic Programming to Prolog. Prentice Hall,1997.
Otros libros interesantes (avanzados):
U. Schöning. Logic for Computer Scientists. Birkhäuser, 1989.
W. F. Clocksin. Clause and Effect. Prolog Programming forthe Working Programmer. Springer, 4a Edición, 2001.
R. A. O’Keefe. The Craft of Prolog. MIT, 2a Edición, 1994.4 / 1
http://www.swi-prolog.org/
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
En programación ló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 asignación!!
... “por debajo” no hay una arquitectura de Von Newman(memoria de almacenamiento para datos y programa, flujo deejecución...)
¿Qué nos queda? : la lógica
5 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
¿Y qué se puede hacer en programación lógica?
Todo: pueden computarse todas las funciones computables (ypuede demostrarse con relativa facilidad).
También puede hacerse esto mismo con máquinas de Turing, conmáquinas de registros ilimitados... o en código máquina.
Pero, ¿es sencillo resolver problemas en programación lógica?
Śı, con el adiestramiento necesario. En general es más sencillo queen lenguajes imperativos, el desarrollo de programas es más rápido,más fiable y, en opinión de muchos, más elegante. También escierto que por regla general, los programas son más ineficientes (ellenguaje está menos próximo a la arquitectura de la máquina).
6 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Oŕıgenes
A partir del trabajo de Herbrand y otros en 1930, J. AlanRobinson publicó “el principio de resolución” en 1965.
En los años 70 hay un gran interés en la construcción dedemostradores automáticos.
En 1972 Robert Kowalski y Alan Colmenauer se plantearonutilizar la lógica como lenguaje de programación.
Aśı surgió PROLOG= PROgramming in LOGic.
La programación lógica utiliza un fragmento de la lógica depredicados y unificación y resolución como mecanismo de cómputo.
7 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Lógica de predicados (breve repaso)
8 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Sintaxis
conjunto (infinito numerable) de variables V: X ,Y ,Z . . . ∈ V
signatura Σ =< SF ,SP >
conjunto de śımbolos de función SF : f , g , h . . . ∈ SF
Escribimos f ∈ SF n ó 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 śımbolos de predicado SP: p, q, r . . . ∈ SP
Escribimos p ∈ SPn ó pn para indicar la aridad como antes,pero ahora exigimos n > 0
Además utilizamos śımbolos auxiliares: paréntesis, comas,puntos, etc
9 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Términos y fórmulas
Té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 también son términos.
Fó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 fórmulas atómicas.
Estas dos definiciones son recursivas. ¿Cuáles son los casos base ycuáles los recursivos? (¿conocemos la inducción estructural?)
10 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Términos y fórmulas. Ejemplos
Suponemos Σ =< {c0, f 1, g2}, {p3, q2} >
Términos:X c f (X ) g(X ,Y ) g(c , g(X ,Y )) f (g(c , f (c)))
¿Por qué f (q(X ,Y )) no es un término?
Fórmulas
Atómicas:q(c , f (c)) p(X ,Y , g(c , g(X ,Y ))) q(f (f (Y )), g(g(c , c), f (Y )))No atómicas:q(X ,Y ) ∨ p(f (c), c , c) ∀X .q(X , c) ∨ ∃Z .p(Z ,Z ,X )
¿Por qué q(q(X ,Y ), c) no es una fórmula?
Dada una signatura Σ, ¿cuántos términos pueden construirse?, ¿ycuántas fórmulas?
11 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Ámbito de los cuantificadores
Dada una fórmula ∀X .ϕ ó ∃X .ϕ diremos que el ámbito delcuantificador es ϕ.
¿Cuál es el ámbito de los cuantificadores en las siguientesfó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 más de una vez la misma variable en unafó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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Variables libres y ligadas
La aparición de una variable X dentro de una fórmula ϕ sedice ligada si está afectada por un cuantificador, o con másprecisión: X aparece ligada en ϕ si está dentro de unasubfórmula de ϕ de la forma ∀X .ψ o ∃X .ψ.La aparición de X en ϕ es libre si no está ligada, i.e., si noestá afectada por ningún cuantificador.
Ejemplo:
∃X .p( X︸︷︷︸ligada
, f ( Y︸︷︷︸libre
)) ∨ ∀Y .q( Y︸︷︷︸ligada
, g( X︸︷︷︸libre
))
Una variable X está libre en ϕ si todas las apariciones de X enϕ son libres.
Una variable X está ligada en ϕ si alguna de las aparicionesde X en ϕ es ligada.
13 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
¿Puede una misma variable aparecer ligada y libre en la mismafó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 tendrán el mismo significado, peropara verlo tendŕıamos que dar semántica o significado a lasfórmulas.
Nos interesará especialmente la semántica de las sentencias:fórmulas cerradas, i.e., sin variables libres.
14 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
La lógica como (un) lenguaje de representaciónde conocimiento
La lógica de predicados permite expresar “sentencias” del lenguajenatural.
“Algunos maḿıferos leen a Quevedo”
Definimos PS = {mamifero1, leerQuevedo1}, FS = ∅ con elsignificado “intuitivo”:
mamifero(X ) ::= X es un maḿıferoleerQuevedo(X ) ::= X lee a Quevedo
Y formalizamos:
∃X .(mamifero(X ) ∧ leerQuevedo(X ))
15 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
O de otro modo: PS = {mamifero1, leer2}, FS = {a} con elsignificado “intuitivo”:
mamifero(X ) ::= X es un maḿıfero
leer(X ,Y ) ::= X lee a Y
a ::= Quevedo
Formalizamos:
∃X .(mamifero(X ) ∧ leer(X , a))
16 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Otro ejemplo: “El producto de cualquier número n por 1 es n”
(Esta es una sentencia “matemática”, pero está expresada enlenguaje natural).
Definimos SP = {=2}, SF = {10, ∗2} con el significado intuitivo:= predicado binario de igualdad (ser iguales)
1 ::= el “uno” de matemáticas
∗ ::= el “producto” en matemáticasy formalizamos
∀X .X ∗ 1 = X
En este ejemplo se pone de manifiesto que las matemáticas están“empapadas” en la lógica (la lógica puede expresar propiedadesmatemáticas... incluso puede expresar cosas acerca de la lógicamisma!).
17 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Semántica de la lógica de predicados
Hemos definido el lenguaje de la lógica de predicados, hemos dadolas reglas sintácticas para construir los distintos elementos de dicholenguaje:
los términos pueden representar valores de nuestro universo
las fórmulas, especialmente las sentencias (fó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 semántica.
18 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Ejemplo
Supongamos V = {X1,X2, . . .} y la signatura:
SF = {c0, suc1, suma2} SP = {par1,menorOigual2}
Sabemos (por construcción sintá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Σ
¿Cómo se puede razonar que los primeros son términos y lassegundas fórmulas? ¿Son sentencias las segundas? ¿Se podŕıahacer un programa para reconocer términos y fórmulas?
¿Tienen algún significado estos términos o estas fórmulas?
19 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Semántica declarativa
Ahora es la lógica la que recurre a las matemáticas: definimos unaestructura
A = (DA, {f A}f ∈SF , {pA}p∈SP)
donde:
DA es el dominio (conjunto cualquiera de valores)
para cada śımbolo de función f ∈ SF n tenemos una función(en el sentido matemático habitual)f A : DA× n. . . ×DA → DA
para cada śımbolo de predicado p ∈ SPn tenemos una relaciónpA ⊆ DA× n. . . ×DA
20 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Ejemplo (cont):
Nótese que las funciones y relaciones que hemos asociado a losśı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 términos, fórmulas ysentencias:
suc(suc(c)), de acuerdo con lo anterior “significa” 2
∀X .par(suma(X ,X )) es “cierto” (significa >)
... pero, ¿cuál es el significado del términosuma(suc(c), suma(X , suc(c))) o de la fórmulamenorOigual(c , suma(X , c))?
Para los términos y las fórmulas abiertas tenemos que dar unvalor a las variables libres.
22 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Valoraciones e interpretaciones
Una valoración en A es una función:
υ : V → DA
(a cada variable le asocia un valor del dominio DA
Y con esto (ahora śı) podremos dar significado a todas lasconstrucciones de nuestro lenguaje.
Una interpretación I es una estructura junto con unavaloración para las variables:
I = (A, υ)
23 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Significado de un término en una interpretación
El significado de un término t en una interpretación I = (A, υ) sedefine sobre la estructura de los té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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Significado de una fórmula
De manera análoga definimos el valor veritativo de una fórmula ϕen una interpretació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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Significado de una fó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 valoración definida como:
υ[X/d ](Y ) =
{d si X = Yυ(Y ) e.o.c.
(La notación [X/d ] es una sustitución. Más adelante lasestudiaremos en detalle, pero por el momento basta la definiciónanterior).¿Cómo se define [[ϕ→ ψ]]Aυ y [[ϕ↔ ψ]]Aυ?
26 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Ejemplo
Calculemos el valor veritativo de la sentencia ∀X .par(suma(X ,X ))en la interpretació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 último es cierto (es una propiedad matemáticaconocida)
27 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Modelos, satisfactibilidad, . . .
Dada una interpretació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 fórmula es satisfactible si admite un modelo, einsatisfactible en otro caso.
Dos fórmulas ϕ y ψ son lógicamente equivalentes (y se escribeϕ ≈ ψ) sii [[ϕ]]Aυ = [[ψ]]Aυ para toda interpretaciónI = (A, υ)ϕ es lógicamente válida sii I |= ϕ para toda interpretación I
28 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Consecuencia lógica
Dadas las fórmulas ϕ1, . . . , ϕn, ψ ∈ LΣ se dice que ψ es unaconsecuencia lógica de {ϕ1, . . . , ϕn} y se escribe:
{ϕ1, . . . , ϕn}︸ ︷︷ ︸hipóteis o premisas
|= ψ︸︷︷︸conclusión
sii para toda interpretación I = (A, υ) se tiene:
I |= ϕ1, . . . , I |= ϕn ⇒ I |= ψ
Teorema
{ϕ1, . . . , ϕn} |= ψ ⇔ {ϕ1, . . . , ϕn,¬ψ} es insatisfactible
29 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Ejemplo
Consideremos la argumentación:
Algunos maḿıferos leen a QuevedoTodos los lectores de Quevedo disfrutan
∴ Algunos maḿı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 interpretación (A, υ) quesatisfaga ϕ1 y ϕ2 satisface ψ? Como todas las fórmulas soncerradas lo que hay que probar es:
A |= ϕ1, A |= ϕ2 ⇒ A |= ψ
30 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Ejemplo (cont)
A |= ϕ1 quiere decir (véase definición de pá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 también disfrutaA(b). En particular setendrá disfrutaA(a)
Aśı 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 demostración es tedioso... además queremos unmecanismo “automatizable”.
31 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Formas normales en lógica de predicados
Para manipular predicados de manera automática (en unordenador) nos interesa que éstos tengan un formato uniforme.
Interesa además que este formato sea lo más simple posible.
La justificación de fondo es que necesitamos tenerlos en formanormal con el fin de poder utilizar el mecanismo de resolución(que veremos más adelante).
32 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Formas normales conjuntivas
Algunos conceptos nuevos:
Un literal es cualquier fórmula atómica (literal positivo) onegación de una fórmula atómica (literal negativo).
Una cláusula disyuntiva es cualquier disyunción de literales.
Una fórmula está en forma normal conjuntiva (FNC) si es unaconjunción de cláusulas disyuntivas.
Por ejemplo, la siguiente fórmula está en FNC:
(r(a,X , f (a))︸ ︷︷ ︸lit. pos.
∨¬p(Y )︸ ︷︷ ︸lit. neg.︸ ︷︷ ︸
disyunción
) ∧ (q(g(X ,Y ), a)︸ ︷︷ ︸lit. pos.
∨¬r(X ,Y ,Z )︸ ︷︷ ︸lit. neg.︸ ︷︷ ︸
disyunción
)
︸ ︷︷ ︸conjunción
33 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Formas prenexas y de Skolem
Una fórmula ϕ ∈ LΣ está 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 núcleode la forma prenexa.
Una fórmula ϕ ∈ LΣ está en forma normal de Skolem siestá en forma prenexa y en su prefijo solo hay cuantificadoresuniversales.
Una fórmula ϕ ∈ LΣ está en forma normal conjuntiva y deSkolem si está en forma normal de Skolem y su núcleo está enFNC.
Por ejemplo:
∀X .∀Y .∀Z .((r(a,X , f (a))∨¬p(Y ))∧(q(g(X ,Y ), a)∨¬r(X ,Y ,Z )))34 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
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 demostración de este teorema es constructiva: nos proporcionaun método efectivo para obtener esa sentencia SKO(ϕ)
35 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Obtención de FNC’s de Skolem
Paso 1: eliminar de ϕ todas las conectivas → y ↔ utilizandolas equivalencias ló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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Obtención de FNC’s de Skolem (cont.)
Paso 4: obtener una forma normal prenexa utilizando lasequivalencias lógicas:
¬∃X .ϕ ≈ ∀X .¬ϕ
¬∀X .ϕ ≈ ∃X .¬ϕ
QX .ϕ ∧ ψ ≈ QX .(ϕ ∧ ψ), con Q ∈ {∃,∀} y X 6∈ var(ψ)
QX .ϕ ∨ ψ ≈ QX .(ϕ ∨ ψ), con Q ∈ {∃,∀} y X 6∈ var(ψ)
ϕ ∧ ψ ≈ ψ ∧ ϕ
ϕ ∨ ψ ≈ ψ ∨ ϕ
37 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Obtención de FNC’s de Skolem (cont.)
Paso 5: eliminar los cuantificadores existenciales aplicando latransformació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 śımbolo de función de aridad n (lasignatura Σ se ampĺıa con nuevos śımbolos de función detalle técnico).
(en el caso n = 0 la función, será en realidad una constante).
Paso 6: transformar el núcleo en una forma normal conjuntiva,utilizando:
ϕ ∨ (ψ ∧ χ) ≈ (ϕ ∨ ψ) ∧ (ϕ ∨ χ)(ψ ∧ χ) ∨ ϕ ≈ (ψ ∨ ϕ) ∧ (χ ∨ ϕ)
38 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
FNC’s de Skolem
A la vista del algoritmo anterior...
¿cómo se obtiene una sentencia (fórmula cerrada) a partir deuna fórmula?, i.e., ¿dónde quedan ligadas las variables libresde la fórmula original?
¿por qué se obtiene una sentencia equisatisfactible y no unalógicamente equivalente?, ¿en qué paso(s) se pierde laequivalencia lógica?
¿por qué no se pierde la equisatisfactibilidad en dichos pasos?
Nótese que una sentencia en FNC de Skolem está uńıvocamentedeterminada por su núcleo.
39 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Ejemplo de obtención de FNC de Skolem
ϕ ≡ ∀X .q(X ,Y ) ∨ ∃X .p(X )→∀Z .r(X ,Y ,Z ) ∧ ∃X .q(X ,Y )
⇓ paso 1, eliminació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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Ejemplo de obtenció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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Ejemplo de obtenció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, eliminació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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Formas clausadas
Sea una fórmula ϕ y su FNC de Skolem
SKO(ϕ) ≡ ∀X1. . . . .∀Xn.((ψ1 ∨ . . . ∨ ψn) ∧ . . . ∧ (φ1 ∨ . . . ∨ φm))
La forma clausada de ϕ, FC (ϕ) es el conjunto
{{ψ1, . . . , ψn}︸ ︷︷ ︸cláusula
, . . . , {φ1, . . . , φm}︸ ︷︷ ︸cláusula
}
SKO(ϕ) está uńıvocamente determinada por su núcleo: lascuantificaciones están impĺıcitas, i.e., todas las variables de lascláusulas (que aparecen como variables libres) están impĺıcitamentecuantificadas universalmente.
43 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Notación de Kowalski para formas clausadas
Según hemos visto que cada clá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 expĺıcitamente. En notación de Kowalski, estacláusula se escribe como:
ϕ1, . . . , ϕn︸ ︷︷ ︸consecuente
← ψ1, . . . , ψm︸ ︷︷ ︸antecedente
Nótese que las “comas” de la izquierda deben interpretarse como∨, mientras que las de la derecha se interpretan como ∧... ¿porqué?Hay tres tipos de cláusulas especiales:
Γ←︸︷︷︸hechos
← ∆︸ ︷︷ ︸objetivos
←︸︷︷︸lógicamente equivalente a ⊥
44 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
Lógica de predicados
Ejemplo
Para la fórmula del ejemplo anterior (pág. 41):
ϕ ≡ ∀X .q(X ,Y ) ∨ ∃X .p(X )→ ∀Z .r(X ,Y ,Z ) ∧ ∃X .q(X ,Y )
obteńı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 notació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 más manejable para la manipulaciónautomática, como veremos)
45 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Se buscan modelos
Recordemos cómo se defińıan las estructuras (pag. 21) y losmodelos (pag. 29) en lógica de predicados.
La definició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 śımbolos de la signatura.
En consecuencia, tampoco tenemos pauta para encontrar losmodelos para las fórmulas (pag. 29).
Pero hay unas estructuras canónicas que facilitarán labúsqueda de modelos: las estructuras de Herbrand.
46 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Universo de Herbrand
Sea ϕ una sentencia en FNC de Skolem. El universo deHerbrand para ϕ, Uϕ es el conjunto de términos cerrados (sinvariables) que pueden construirse con los śımbolos deconstante y función de ϕ. En concreto:
Todo śımbolo de constante que aparece en ϕ está en Uϕ. Si ϕno tiene ningún śımbolo de constante, se añade uno cualquieraa (para evitar que Uϕ = ∅);Para todo śımbolo de función f n que aparece en ϕ y todoconjunto de té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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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 estén autodefinidas(solo son śımbolos, sin otro significado que el del propio śımbolo:la sintaxis coincide con la semántica).Nótese que la elección de pHϕ sigue siendo arbitraria.
48 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Base de Herbrand
Dada una sentencia ϕ en FNC y de Skolem, la base de HerbrandBϕ para ϕ es el conjunto de todos los átomos cerrados construidoscon śı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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Satisfactibilidad y modelos de Herbrand
Teorema
Dada una sentencia ϕ en FNC y de Skolem se tiene
ϕ es satisfactible ⇔ ϕ tiene un modelo de Herbrand
¿Por qué es importante este teorema?
Por definición (pag. 29) dećıamos que una fórmula era satisfactiblesi teńıa un modelo. Este teorema nos permite restringir labúsqueda de esos modelos a modelos de Herbrand.
51 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo
Supongamos:
ϕ ≡ ∀X .∀Y .∀Z .( suma(c ,X ,X )∧(suma(X ,Y ,Z )→ suma(suc(X ),Y , suc(Z )))
(... ¿qué estamos formalizando aqúı?)
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
Nótese que todo t ∈ Uψ será de la forma
t = suc(suc(. . . (suc(c)) . . .))
Abreviamos suc2(c) = suc(suc(c)) y análogo parasuc3(c), suc4(c), . . . , sucn(c), . . .
La base de Herbrand será 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 tambié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 serán los que cumplan n + m = k).
53 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
Ahora buscamos un modelo de Herbrand de ψ.
La estructura de Herbrand ha definido todos los elementos de Hψexcepto el śı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 valoración, porque ψ es cerrada (no contienevariables libres). Olvidandonos de la valoració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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Instancias básicas
Sea ϕ una sentencia en FNC y de Skolem de la forma:
ϕ ≡ ∀X1. . . .∀Xn. C1 ∧ . . . ∧ Cm
donde cada Ci es una cláusula (disyunción de literales).
Definimos el conjunto de instancias básicas de ϕ como:
IB(ϕ) = {Ci [X1/t1, . . . ,Xn/tn]︸ ︷︷ ︸sustitución
| t1, . . . , tn ∈ Uϕ}
Por ejemplo, para la fó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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Acotando el problema de la satisfactibilidad
Teorema (Gödel-Herbrand-Skolem)Dada una sentencia ϕ en FNC y de Skolem:
ϕ es satisfactible ⇔ IB(ϕ) es satisfactible
... ¿por qué es interesante este resultado?
Porque traslada el problema de la satisfactibilidad de la lógica depredicados a la lógica proposicional: IB(ϕ) es una fórmula sinvariables, ni cuantificadores abordable en lógica proposicional.
Pero, a la vista del Teorema de la página 31, más que lasatisfactibilidad nos interesa la insatisfactibilidad de cara a probarla validez de argumentaciones.
En este sentido, tenemos el teorema de la página siguiente...
57 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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 está en que no solo traslada elproblema a la lógica proposicional, lo cual es una tremendasimplificación, sino que permite abordarlo en el ámbito de lafinitud es un paso más para aproximar la lógica a laprogramación lógica
58 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Un ejemplo
Consideremos la fó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 fó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. Fá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 qué es insatisfactible?
59 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
A pesar de todo...(incursiones en computabilidad)
Esta demostrado que:
El problema de la satisfactibilidad para la lógica de predicadoses indecidible: dada una fórmula ϕ, la pregunta ¿es ϕsatisfactible? es indecidible.
El problema de la insatisfactibilidad para la lógica depredicados es semi-decidible:existe un algoritmo P tal que dada una fórmula ϕ:
Si P para actuando sobre ϕ entonces ϕ es insatisfactible
(Este algoritmo se basa en la teoŕıa de Herbrand).
60 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
De la lógica a la programación lógica
Unificación
Resolución
61 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Estado del arte
Sabemos:
Cómo representar conocimiento mediante argumentaciones y cómo formalizarestas argumentaciones en el lenguaje de la lógica.
Cómo transformar las fórmulas lógicas en cláusulas.
Demostrar validez de una argumentación es refutar (demostrar lainsatisfactibilidad) de un conjunto de fórmulas:
premisas + negación de la conclusión
(... quizá sepamos algo de tableaux?)
Queremos saber:
Un método para construir refutaciones utilizando la formaclausal.
Una forma de plasmar ese método en un algoritmo concreto.
Muchas más cosas... ... pero, comencemos con la unificación.
62 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Sustituciones
Una sustitució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 sustitución σ = {X1/t1, . . . ,Xn/tn} a un términot se denota como tσ ó t[X1/t1, . . . ,Xn/tn] y consiste enreemplazar (simultáneamente) en t cada una de lasapariciones de X1 por t1,. . . , cada una de las apariciones deXn por tn (análogo para fórmulas). Las sustituciones puedencomponerse: tσθ = (tσ)θ
Una sustitución σ es idempotente sii σσ = σ.
¿Es idempotente σ = {X/f (X )}? ¿Y θ = {X/f (Y ),Y /a}?63 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Unificadores
Un sistema de ecuaciones S = {s1 = t1, . . . , sn = tn} (consi , ti ∈ TΣ(V)) es unificable sii existe una sustitució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 máxima generalidad (u.m.g) para S sii σ es ununificador para S y para todo θ unificador de S existe unasustitución τ tal que θ = στ (σ es má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... ¿porqué?
64 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Sistemas de ecuaciones en forma resuelta
Un sistema de ecuaciones está 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 está en forma resuelta representala sustitución [X1/t1, . . . ,Xn/tn] y esta sustitución esidempotente... ¿por qué?
Ahora nos interesa un algoritmo de unificació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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Algoritmo de unificació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 (ó 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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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 más reglas, hemos terminado.Si sobre el sistema inicial aplicamos la sustitució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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Unificador para un conjunto de literales
Dado un conjunto finito de literales Γ (fórmulas atómicas osus negaciones), una sustitución σ es unificador de Γ sii paratodo L, L′ ∈ Γ, Lσ = L′σ.
Una sustitución σ es un u.m.g. para Γ si es unificador para Γ yes más general que cualquier otro unificador (pá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 además es idempotente.
La propia demostración proporciona el algoritmo... veamos
68 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Algoritmo de unificación para conjuntos de literales
En Γ todos los literales han de ser positivos o negativos (si no,directamente no seŕıa unificable)
Además todos los literales deben tener en cabeza el mismośımbolo de predicado (si no, no seŕıa unificable)
Aśı 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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Resolución general (hacia el “método”)
Sean dos cláusulas C1 y C2 de la forma (en notación de Kowalski)(Γi ,∆j son conjuntos de literales y + es la concatenació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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Derivaciones y refutaciones
Dado un conjunto de cláusulas S definimos la relación ↪→ comoS ↪→ S ∪ {resol(C1,C2)} siendo C1,C2 ∈ S
Una cláusula C es derivable por resolució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 resolución general si S `RG ⊥ (esdecir se obtiene la cláusula vaćıa ←). En este caso lasecuencia de resolventes constituye una refutación.
73 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Poniendo todo en marcha
formalización + teoremas + FNC’s de Skolem + resolución +unificación
74 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo
Consideremos la argumentación de la pág 31:
Algunos maḿıferos leen a QuevedoTodos los lectores de Quevedo disfrutan
∴ Algunos maḿıferos disfrutan
y su formalizació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 página 31 tenemos:
{ϕ1, ϕ2} |= ψ ⇔ {ϕ1, ϕ2,¬ψ} es insatisfactible
75 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
Buscamos una refutación de {ϕ1, ϕ2,¬ψ}:Primero ¬ψ ≡ ∀X .(¬mam(X ) ∨ ¬dis(X ))
Ahora ponemos las fó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 notación de Kowalski:
mam(a)←lee(a, q)←
dis(X )← lee(X , q)← mam(X ), dis(X )
76 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
Refutemos por resolució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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Otro ejemplo
Todas las porteñas alegres son amigas de algún marinero.Ningún porteño feliz está casado con una porteña triste.Los porteños casados con amigas de marineros son cornudos o marineros.Los marineros casados son infelices.
∴ Los porteños casados con porteñ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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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 ))
Negación de la conclusió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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
Con esto tenemos una refutación, que es una demostración(deducción) de nuestra argumentación, pero ademá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 sustitución:
θ = {Z/f (b),X2/b,X1/b,Y3/b,X4/a,X/a,Y /b,X3/a,Y4/b}
83 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
Si aplicamos la sustitució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 claúsulas utilizadas obtenemos unconjunto de instancias bá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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Otro ejemplo
Pedro es miope.Cuando alguien es miope, o su padre o su madre también es miope.Todo el mundo ama a su padre y a su madre.
∴ Algú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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Otro ejemplo más
Un dragón es feliz si todos sus hijos pueden volar.Los dragones verdes pueden volar.Un dragón es verde si es hijo de algún dragó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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Corrección y completitud de la resolución general
LemaDadas tres cláusulas C , C1 y C2, si C = resol(C1,C2) entonces
{∀C1, ∀C2} |= ∀C
donde ∀C representa el cierre universal de C (análogo para C1 yC2), i.e., la cuantificación universal de todas las variables de C .
Teorema (Corrección y completitud de la RG)Dado un conjunto de cláusulas S se tiene:
S es insatisfactible ⇔ S `RG←
87 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Claúsulas de Horn. Resolución SLD
88 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Refinando la resolución
La resolución general es un mecanismo muy potente dedemostración...
pero tiene un alto grado de indeterminismo:en la selección de las cláusulas con las que hacer resolucióny en la selección de los literales a utilizar en la resolución
Desde el punto de vista computacional es muy ineficiente.
Desde el punto de vista práctico puede sacrificarse algo deexpresividad y obtener un mecanismo más eficiente que sustenteun lenguaje de programación más “realista”:
restringimos la forma de las cláusulas de modo que a lo sumotengan un literal positivo. En notación de Kowalski esto quieredecir que a lo sumo tienen un átomo en el lado izquierdo de ←estudiaremos un método de resolución espećıfico para estetipo de cláusulas.
89 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Cláusulas de Horn
Una cláusula de Horn es una secuencia de literales que contiene alo sumo un literal positivo. Al escribirla en notación de Kowalskitendrá una de estas cuatro formas:
1 Hecho: p ←2 Regla: p︸︷︷︸
cabeza
← q1, . . . , qn︸ ︷︷ ︸cuerpo
3 Objetivo: ← q1, . . . , qn4 Éxito: ←
Los hechos y las reglas se denominan clá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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Cláusulas de Horn (cont.)
Las reglas engloban todos los casos en el siguiente sentido:
un hecho es una regla con cuerpo vaćıo
un objetivo es una regla con cabeza vaćıa
y el éxito es una regla con cabeza y cuerpo vaćıos
Nótese que en las cláusulas de Horn trabajamos con secuencias deliterales en vez de conjuntos (como veńıamos haciendo con lasclá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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Predicados y programas lógicos
Un predicado p queda definido por el conjunto de claúsulas(hechos y reglas) cuyas cabezas tienen ese śımbolo depredicado. Aśı pues la definición de un predicado en generaltendrá 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 lógico es un conjunto de definiciones depredicados (es decir, un conjunto de claúsulas definidas:hechos y reglas).
92 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Un ejemplo
Representació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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
La relación de conexión entre nodos (caminos) puede expresarsemediante reglas:
camino(X ,Y )← X = Ycamino(X ,Y )← arco(X ,Z ), camino(Z ,Y )
(la primera regla, también se podŕı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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
Ahora, se podŕıa plantear un objetivo, i.e., entendiendo los hechosy las reglas que hemos escrito como premisas podŕıamos plantearuna conclusión y tratar de mostrar la validez de la argumentació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.
... ¿qué debeŕıamos obtener (por resolución) en cada caso?95 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Variables lógicas en las cláusulas
Todas las variables lógicas en de una claúsula están cuantificadasuniversalmente de forma impĺıcita. Por ejemplo, en la claúsula:
camino(X ,Y )← arco(X ,Z ), camino(Z ,Y )
impĺıcitamente tenemos:
∀X .∀Y .∀Z .(camino(X ,Y )← arco(X ,Z ), camino(Z ,Y ))
Ahora bien, esta sentencia es lógicamente equivalente a:
∀X .∀Y .(camino(X ,Y )← ∃Z .(arco(X ,Z ), camino(Z ,Y )))
Es decir, las variables que sólo aparecen a la derecha de la claúsulaestán localmente afectadas de una cuantificación existencial. Sedice que son variables existenciales o extra o locales. Interpretarlasexistencialemente facilita la lectura de la clá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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
SLD-Resolución
Selection-rule driven Linear resolution for Definite clauses
Es un caso particular de la resolución general, donde:
Los resolventes son siempre objetivos (cláusulas sin cabeza).
Los programas son conjuntos de claúsulas (de Horn) definidas,i.e., hechos y reglas.
Hay una función de selección que selecciona un átomo delobjetivo a quien aplicar resolución.
98 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
SLD-resolución (cont.)
Formalmente:
Sea un programa lógico P, un par de objetivos G y G ′, y unafunción de selección fs . Una derivación de G a G
′ conSLD-resolució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 resolución general) el literalL = fs(Gi ) con una variante de una regla de P.
Si G ′ ≡←, entonces tenemos una SLD-refutación de G apartir de P.
99 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Respuestas correctas
Dado un programa P y un objetivo G ≡← q1, . . . , qn, diremos queuna sustitución θ es una respuesta correcta para P ∪ {G} si
θ únicamente actúa sobre las variables de G y
P |= ∀X1. . . . .∀Xm(q1 ∧ . . . ∧ qn)θ, siendo {X1, . . . ,Xn} elconjunto de variables de G (notación: P |= [(q1 ∧ . . . ∧ qn)θ]∀)
Por ejemplo, consideremos la siguiente refutación:
G ≡← suma(c, s(A), B) suma(c, Y1, Y1)←
←θ1 = [Y1/s(A), B/s(A)]
La sustitució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 qué?
101 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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 sustitució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 pertenecerá al modelo de la primera claúsula de Py por tanto al modelo de P (recordemos que en la página 53estudiamos un modelo de Herbrand para este programa en elque
sumaH = {(sm(c), sn(c), sk (c)) | m + n = k}
102 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Corección y completitud de la SLD-resolución
TeoremaSea P un programa, fs una función de selección y G un objetivo.Tenemos:
Corrección: Si P ∪ {G} `SLD← en n pasos y θ = θ1 . . . θn esla composición de la secuencia de unificadores usados en laSLD-refutación, entonces:
θ′ = θ |var(G) es una respuesta correcta para P ∪ {G}
Completitud: Sea θ una respuesta correcta para P ∪ {G},entonces existe una SLD-refutación de G a partir de P conuna secuencia de unificadores θ1, . . . , θn tal queθ = (θ1 . . . θn) |var(G).
Nótese que la función de selección concreta que se utilice no esrelevante para los resultados de corrección y completitud.
103 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
Una posible refutación (tomando como función de selecció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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
La composició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 restricción a las variables del objetivo original,es decir, a X tenemos:
θ′ = θ |{X}= [X/a]
Por el teorema de corrección θ′ = [X/a] es una respuestacorrecta para el objetivo original.
Por el teorema de completitud, este mecanismo debe sercapaz de encontrar además otras respuestas. Intuitivamente esfácil ver que serán [X/b], [X/c], [X/d ], [X/e]... cómo seconstruiŕıan las SLD-refutaciones para encontrar estasrespuestas?
107 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Hacia Prolog
La resolución SLD está mucho más próxima a unaimplementación realista de la programación lógica porque haacotado notablemente el indeterminismo con respecto a laresolucion general.
Las claúsulas de Horn son lo suficientemente expresivas parautilizarlas como lenguaje de programación.
Quedan dos cuestiones por resolver:
¿Qué función de selección utilizamos? (esto, según hemos vistono afecta a la corrección y la completitud).¿Qué criterio seguimos para seleccionar una de las reglasaplicables para resolver un objetivo? (esto, está relacionadocon la completitud).En el último ejemplo, utilizando uno u otro criterio se obtienendistintas respuestas.
108 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
PROLOG
109 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Sintaxis de Prolog
Un programa Prolog es un conjunto de cláusulas de Horn (hechosy reglas) donde:
Todas las claúsulas acaban con .El śımbolo ← se escribe como :- que se lee como si(condicional). En los hechos no es necesario (basta poner elátomo y .)Los nombres de predicado y función siguen las pautashabituales de los identificadores pero comienzan conminúscula .Los nombres de variable también siguen esas pautas, perocomienzan por mayúscula .Los á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 notación.110 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Función de selección y búsqueda
La función de selección devuelve siempre el primer átomo delobjetivo empezando por la izquierda.
Para resolver un objetivo G el algoritmo elemental seŕıa:
mientras G no sea ciertoelegir una (variante de una) regla de P aplicable a Greducir G por resolución
Pero en un paso de reducción pueden existir varias (variantesde) claúsulas aplicables a G . Por ello surgue el concepto deárbol de búsqueda: Prolog ensaya las distintas claúsulasaplicables a G de manera secuencial y cada uno de estosensayos da lugar a una rama de dicho árbol.
111 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Árboles de búsqueda
Dado un programa Prolog y un objetivo G (asumimos selección delprimer átomo de la izquierda), el árbol de búsqueda para G es unárbol que:
tiene G como ráız
para cada cláusula C de P aplicable a G existe una ramacorrespondiente al árbol de búsqueda del SLD-resolvente de Gy (una variante cualquiera de) C . Además etiquetaremos lasramas con la sustitución correspondiente y la claúsula Caplicada.
En otras palabras: un árbol de búsqueda es un árbol con objetivosen los nodos y cuyas ramas representan los posibles cómputos, i.e.,las posibles claúsulas a aplicar.Nota: no confundir árbol de búsqueda con los árboles de derivación SLD que hemos
visto anteriormente (los árboles de resolución corresponden solo a una rama de los
árboles de búsqueda).
112 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo
Trabajemos con un grafo más pequeñ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 continuación presentamos el árbol de búsqueda para el objetivocamino(X,d).
113 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Ejemplo (cont.)
camino(X,d)
é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)
éxito
C1
arco(d,Z3),camino(Z3,d)
C2
fallo
camino(d,d)
A3 [X/a,Z1/d]
éxito
C1
arco(d,Z3),camino(Z3,d)
C2
fallo
camino(d,d)
A4,[X/c,Z1/d]
éxito
C1
arco(d,Z3),camino(Z3,d)
C2
fallo
114 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Prolog: el sistema
Disponible en: http://www.swi-prolog.org/ para distintasplataformas.
Posibilidades de interpretación/compilación.
Habitualmente utilizamos el inté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
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Un programa. Parejas de baile
Sabiendo los invitados que vendrá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 elintérprete:
?- [parejas].
o bien
?- consult(parejas). ?- consult(’parejas.pl’).
?- [’/parejas.pl’].
116 / 1
http://www.swi-prolog.org/
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Resolviendo objetivos
Qué respuesta(s) debemos obtenter para los siguientes objetivos:
?- pareja(X,Y).
?- pareja(X,ana).
?- pareja(X,juan).
?- pareja(luis,Y).
Desarrollar el árbol de búsqueda para
?- pareja(X,Y).
117 / 1
Jaime Sánchez HernándezDepartamento de Sistemas Informáticos y Computación
Universidad Complutense de Madridemail: jaime@sip.ucm.es
De la lógica a la programación lógica Poniendo todo en marcha
Operaciones con números naturales
Hemos definido la
Recommended