Eduard Gamonal

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.