Roberto Ricci
Liceo Scientifico "A.Righi" di Bologna
1.
Il problema seguente è tratto da un esercizio proposto da Nils J. Nilsson in 'Metodi per la risoluzione dei problemi nella intelligenza artificiale' ( 1984, Franco Angeli editore ) a pag. 259: "Tino, Marco e Gianni sono soci del Club Alpino; tutti i soci del Club Alpino sono sciatori o scalatori o ambedue le cose; a nessuno scalatore piace la pioggia e a tutti gli sciatori piace la neve; a Marco non piace tutto ciò che piace a Tino e piace tutto ciò che non piace a Gianni; a Tino piacciono la pioggia e la neve; c'è un socio del Club Alpino che sia scalatore ma non sciatore? Chi è?" Posto che siano scalatori tutti e soli coloro a cui piace scalare, e così anche per gli sciatori, il problema può essere riformulato nel linguaggio Prolog nella maniera seguente:
socio(tino). socio(marco). socio(gianni). deduzione:- socio(X), piace(sciare,X,no),not piace(scalare,X,si), assert(piace(scalare,X,si)). deduzione:- socio(X), piace(scalare,X,no), not piace(sciare,X,si), assert(piace(sciare,X,si)). deduzione:- piace(pioggia,X,si), not piace(scalare,X,no), assert(piace(scalare,X,no)). deduzione:- piace(sciare,X,si), not piace(neve,X,si), assert(piace(neve,X,si)). deduzione:- piace(X,tino,si), not piace(X,marco,no), assert(piace(X,marco,no)). deduzione:- piace(X,gianni,no), not piace(X,marco,si), assert(piace(X,marco,si)). piace(pioggia,tino,si). piace(neve,tino,si). risoluzione:- ripeti, not deduzione. ripeti. ripeti :- ripeti.
Si tratta di una base di conoscenza iniziale che consente all'automa Prolog di incrementa di fatti espliciti non già noti la sua base di dati mediante il predicato predefinito assert(...). Le deduzioni hanno tutte la stessa struttura: ammesso siano noti alcuni fatti, ad esempio che X è socio e ad X non piace sciare, e che la conseguenza deducibile non è già nota, ad esempio che ad X piace scalare, viene aggiunta alla base di dati quella conseguenza. Il predicato predefinito 'not', che ha come argomento un enunciato predicativo e che non va interpretato come la solita negazione, consente appunto di costruire enunciati verificati solo nel caso in cui l'argomento non è un fatto noto. La risoluzione al problema è descritta come una ripetizione di deduzioni fintantoche è possibile effettuarne, e termina dunque quando non è possibile trovare nuove conseguenze con le regole di deduzione consentite. L'interrogazione per mettere in moto il processo di risoluzione del problema è la seguente:
?- risoluzione.a cui l'automa Prolog risponde, al termine:
yes.Un'interrogazione appropriata per formulare la questione posta dal problema è:
?- socio(X), piace(scalare,X,si), piace(sciare,X,no).a cui l'automa Prolog rispoderà
X= marco. no
2.
Consideriamo ora il problema seguente. "In tre cestini vuoti sono contenuti tre diversi tipi di frutta, in uno mele, in uno banane,e in uno albicocche, e i tre cestini hanno delle etichette non però corrispondenti al reale contenuto; il fruttivendolo ci dice che nel cestino etichettato 'banane' sono in realtà contenute albicocche; è possibile indovinare il contenuto esatto dei cestini ?". Questo problema è descritto come esempio didattico tipico da Gabriele Lolli in 'La logica tra mente e macchine', su Epsilon 5; esso viene esaminato, tradotto in forma logico-predicativa e risolto per via deduttiva applicando, come regola di inferenza, sostanzialmente il modus ponens. Un programma Prolog che risolve il problema è il seguente:
cestino(albicocche). cestino(banane). cestino(mele). frutta(albicocche). frutta(banane). frutta(mele). contenuto(cestino(banane),frutta(albicocche),si). deduzione :- cestino(X), not contenuto(cestino(X),frutta(X),no), assert(contenuto(cestino(X),frutta(X),no)). deduzione :- frutta(Y), not contenuto(_,frutta(Y),si), cestino(X), not contenuto(cestino(X),frutta(Y),_), not ( cestino(Z), Z \= X, not contenuto(cestino(Z),frutta(Y),_)), assert(contenuto(cestino(X),frutta(Y),si)). deduzione :- contenuto(cestino(X),_,si), frutta(Y), not contenuto(cestino(X),frutta(Y),_), assert(contenuto(cestino(X),frutta(Y),no)). risoluzione :- ripeti, not deduzione. ripeti. ripeti :- ripeti.
Un problema analogo è tratto da Martin Gardner in 'Enigmi e giochi matematici' ( 1973, Sansoni editore ), vol. 3 pag. 27: "Tre persone i cui cognomi erano Bianchi, Neri e Rossi pranzavano insieme. Una di loro era una signora. « Non è strano» osservò la donna « che i nostri cognomi corrispondano ai colori di capelli e che tra noi ci sia una persona con i capelli neri, una con i capelli rossi e l'altra bianchi ?». «E` davvero strano» osservò la persona con i capelli neri «e non avete notato che nessuno di noi ha i capelli si accordano con il proprio nome?». «Avete proprio ragione !» esclamò Bianchi. Se i capelli della signora non sono rossi, qual'è il colore dei capelli di Neri ?". In questo problema può essere fuorviante l'informazione che uno di essi è una signora e che non ha i capelli rossi, informazioni ridondanti. I due problemi possono essere visti come algebrico-combinatori. In questi termini la questione consiste nel trovare una corrispondenza biunivoca antiriflessiva di un insieme S in sé essendo data una delle corrispondenze. Diviene quindi ovvio come generalizzare il problema. Una base di conoscenze in Prolog per risolvere il problema generalizzato è la seguente:
elem(a). elem(b). elem(c). rel(b,a,si). deduzione :- elem(X), not rel(X,X,no), assert(rel(X,X,no)). deduzione :- elem(Y), not rel(_,Y,si), elem(X), not rel(X,Y,_), not ( elem(Z), Z \= X, not rel(Z,Y,_)), assert(rel(X,Y,si)). deduzione :- rel(X,_,si), elem(Y), not rel(X,Y,_), assert(rel(X,Y,no)). risoluzione :- ripeti, not deduzione. ripeti. ripeti :- ripeti.