Avís: article orientat a estudiants d’Enginyeries en Informàtica de la FIB – UPC. Basat en les explicacions a classe del professor Enric Rodríguez.

La programació lògica es cursa en les assignatures d’«introducció a la lògica» i a «lògica per a la informàtica». La utilitat directa per un fíber és: calcular respostes pel concurs «Cifras y letras» o trobar una manera de resoldre el problema de missioners i caníbals. També es fa servir per calcular horaris de l’ACB o els mateixos de la FIB.

Problema de concatenació

Inducció per concatenació:

concat([], L, L).
concat([X|Y1], Y2, [X|Y3]) :- concat(Y1, Y2, Y3).

Vegem que si L1, L2 són llistes i L3 és una variable, aleshores la consulta

edu@debian:~$ prolog
GNU Prolog 1.3.0
By Daniel Diaz
Copyright (C) 1999-2007 Daniel Diaz
| ?- concat(L1, L2, L3)

instancia (unifica) L3 amb la concatenació de L1 i L2.

Cas base

L1 és la llista buida []. Per la primera clàusula, tenim que L3 queda instanciada a L2, de manera que L3 s’instancia correctament.

Cas inductiu

Suposem que la llista L1 té almenys un element, és a dir, és de la forma [X | Y1]. Y1 amb longitud n+1. Aleshores, per hipòtesi d’inducció, la consulta

| ?- concat(Y1, L2, L3)

on Y3 és una variable, instancia Y3 a la concatenació de Y1 i Y2. Y1 té longitud n.
Per la segona clàusula, la consulta

| ?- concat([X|Y1], L2, L3).

instancia L3 a [X|Y3], que és la concatenació de X, Y1, Y2. Per tant, L3 queda instanciada correctament.

Avís: article orientat a estudiants d’Enginyeries en Informàtica de la FIB – UPC. Basat en les explicacions a classe del professor Enric Rodríguez.

La programació lògica es cursa en les assignatures d’«introducció a la lògica» i a «lògica per a la informàtica». La utilitat directa per un fíber és: calcular respostes pel concurs «Cifras y letras» o trobar una manera de resoldre el problema de missioners i caníbals. També es fa servir per calcular horaris de l’ACB o els mateixos de la FIB.

Introducció

Avui en dia fem servir les bases de dades relacionals. Tenim diverses taules amb continguts i entre ells diem quina relació tenen. Per exemple, si tenim una taula de ciutats i una altra de codis postals, en lloc de guardar quin codi postal pertany a cada ciutat, diem amb SQL «El codi 08030 i el 08080» pertanyen a Barcelona.

Seguint l’exemple dels apunts de classe, podríem tenir un model de base de dades deductiu en comptes de relacional. Nosaltres definim un concepte, i la base de dades ens dóna les respostes.

Ho aclarim:

Expressem les dades de la nostra base de dades com relacions o tuples:

pare(joan, pere)
pare(maria, pere)
germà(pere, vicent)
germà(pere, albert)
pare(x,y) = ‘y és pare de x’
germà(x,y) = ‘y és germà de x’

Imaginem-nos que volem incloure a la base de dades la relació tiet(x,y), que signifiqui ‘y és tiet de x’. Hi ha dues opcions:

1. Afegir a la base de dades totes les relacions possibles de tiet. Per exemple:
   tiet(joan, vicent); tiet(joan, albert), …Aquest enfocament té l’inconvenient que pot arribar a tenir un nombre quadriàtic de noves relacions i també que es poden introduir inconsistències.
2. Podem afegir una regla deductiva que permeti deduir quan hi ha relació de ‘tiet’ entre dos individus.

Adoneu-vos que la darrera expressió és una clàusula de Horn, que Prolog adora.

Així doncs, podem veure la nostra base de dades com un conjunt de clàusules:

Observació: totes les clàusules de la base de dades són de Horn. A més a més, totes tenen exactament un literal positiu. D’aquest tipus de clàusules se’n diu clàusules de programa.

A la mateixa base de dades vista com un programa prolog, s’escriuria

pere(joan,pere).
pere(maria,pere).
germa(pere, vicenç).
tiet(X,Y) :- pare(X,Z), germa(Z,Y)

Atenció: fixeu-vos que hi ha un punt al final de cada línia.

Les consultes de programes lògics (bases de dades) es fan mitjançant clàusules de Horn amb tots els literals negatius. Per aquest motiu, a aquest tipus de clàusules se les anomena clàusules objectiu.

Per exemple, sigui F la conjunció de les clàusules 1,2,3,4,5 anteriors. Imaginem que estem interessats en fer la següent consulta a la base de  dades:

Aquest problema és equivalent a veure que és insatisfactible.

Vegem amb resolució que el següent conjunt de clàusules és instat:

Resolució:
Clàusules 5+6

amb
Generen la 7:

Resolem la 7 amb la 1

amb

Afegim la clàusula 8:
8.

i resolem la 8 amb la 3

Una resposta a la consulta és u -> joan; v -> vicent.