Roberto Ricci
Liceo Scientifico "A.Righi", Bologna
Uno degli argomenti più astratti dei programmi di matematica è la cosiddetta "insiemistica" che oggi, esauriti gli entusiasmi che ne avevano accompagnato l'ingresso nelle scuole di ogni grado, viene sempre più considerata un mezzo piuttosto che un fine, un insieme di termini e di concetti che servono per parlare di altri concetti, come quello di numero cardinale o quello di funzione, e per aiutare a capirli, piuttosto che un altro settore disciplinare della matematica. Se consideriamo l'introduzione dell'informatica nell'insegnamento della matematica soltanto per sottolinearne gli aspetti algoritmici, l'insiemistica risulta sfuggire facilmente alla applicazione di tale metodologia. In questo lavoro si vuole mostrare un esempio di programmazione Prolog relativamente a questo argomento, evidentenziando come sia possibile insegnare all'automa Prolog alcuni concetti, e non soltanto procedimenti, di insiemistica, da applicare a insiemi concreti. Risulterà chiaro soprattutto come l'obiettivo di fornire l'automa Prolog di una base di conoscenza adatta sia di concreto stimolo per un'approfondita analisi dei concetti in esame.
Un insieme può essere descritto per elencazione dei suoi elementi solamente se finito, ed in pratica solo se è ragionevolmente poco numeroso. Altrimenti è necessario descriverlo per caratterizzazione, cioè mediante un attributo "a" tale che la proposizione 'x è a' sia vera per tutti e solo gli elementi dell'insieme. Quell'attributo può anche essere considerato un nome dell'insieme. Ad esempio consideriamo la definizione, per elencazione, dell'insieme delle cifre. In linguaggio Prolog possiamo scrivere:
elem(0,cifre). elem(1,cifre). elem(2,cifre). elem(3,cifre). elem(4,cifre). elem(5,cifre). elem(6,cifre). elem(7,cifre). elem(8,cifre). elem(9,cifre).
dove il predicato 'elem(...,...)' può essere anche letto '... è l'elemento dell'insieme ... '. L'automa Prolog può così essere interrogato sia in forma chiusa
?- elem(10,cifre).
per ottenere una risposta binaria del tipo si/no, sia in forma aperta
?- elem(C,cifre).
per ottenere in riposta tutti i termini che sostituiti a C rendono vero l'enunciato. Un altro esempio, questa volta per caratterizzazione, è una definizione dell'insieme dei numeri naturali
elem(0,naturali). elem(N,naturali) :- elem(N1,naturali), N is N1+1.
essendo '...is ...' un predicato predefinito che può essere letto come '... è risultato dell'espressione ...'. Tale definizione mette l'automa nella condizione di generare in successione i numeri naturali, o meglio il sottoinsieme finito dei naturali noto come INTEGER positivo, e riconoscere che dato un numero di quel tipo esso vi appartiene effettivamente. Tuttavia una interrogazione del tipo
?- elem(1.5,naturali).
oppure
?- elem(pippo,naturali).
costringerebbe l'automa ad una ricerca inefficace. Nel seguito si eviteranno interrogazioni di quest'ultimo tipo. In conseguenza alla definizione precedente possiamo precisare il concetto seguente:
elem(N,pari) :- elem(N,naturale), N mod 2 = 0.
dove l'operatore 'mod' produce il resto della divisine intera tra i due operandi. Tale descrizione consente all'automa Prolog sia di riconoscere se un dato numero naturale è un numero pari oppure no
?- elem(7,pari).
sia di rispondere a domande che abbiano forma di enunciati aperti
?- elem(N,pari).
interrompendo ad un certo punto la generazione delle infinite soluzioni. Ancora un esempio di definizione di un insieme, anzi di una classe di insiemi, è, per caratterizzazione:
elem(X,tra(A,B)) :- elem(X,naturale), X > A, X < B.
oppure, ricorsivamente:
elem(A,tra(A,B)) :- A =< B. elem(X,tra(A,B)) :- A < B, A1 is A+1, elem(X,tra(A1,B)).
corrispondente ad una qualsiasi lista di termini, dove il simbolo '_' ha in Prolog significato di variabile per la quale non occorre servirsi di un nome particolare:
elem(X,[X|_]) :- !. elem(X,[_|L]) :- elem(X,L).
dove il simbolo '!', da leggere 'cut' ovvero "taglia le altre parti della definizione dello stesso predicato", ha solo la funzione di rendere più efficiente la definizione senza modificarne la logica. Ad esempio si potrebbe avere il colloquio:
?- elem(X,[a,b,a]). X=a X=b no
Possiamo cominciare ora a definire, in linguaggio comprensibile all'automa Prolog, alcune di quelle proprietà elementari degli insiemi o quelle relazioni tra più insiemi che si insegnano agli studenti fin dalla scuola media. Potremo tradurre la definizione: 'Un insieme è vuoto se non ha elementi', nelle forma:
vuoto(A) :- not elem(_,A).
Per quanto riguarda il concetto di uguaglianza tra insiemi, cioè la definizione: 'Due insiemi sono uguali se ogni elemento dell'uno è anche elemento dell'altro e viceversa', si verifica che far capire all'automa Prolog l'uso del quantificatore universale 'ogni' presenta difficoltà analoghe a quelle incontrate da un insegnante di matematica con gli studenti. L'esperienza gli suggerisce che è utile ripetre quella definizione facendo uso del quantificatore esistenziale per definire magari la relazione opposta: 'Due insiemi sono diversi se esiste in uno di essi almeno un elemento che non appartiene all'altro'. Tradotta in linguaggio Prolog si avrà:
diversi(A,B) :- elem(X,A), not elem(X,B). diversi(A,B) :- elem(X,B), not elem(X,A).
e quindi:
uguali(A,B) :- not diversi(A,B).
In conseguenza si potrà avere il seguente colloquio:
?- uguali(cifre,tra(0,9)). yes ?- uguali(tra(1,10),cifre). no ?- uguali([a,a,b],[b,a]). yes
A questo punto possiamo passare a definire, usando direttamente il linguaggio Prolog
intersecati(A,B) :- elem(X,A), elem(X,B). disgiunti(A,B) :- not intersecati(A,B).
e inoltre
nonSottinsieme(A,B) :- elem(X,A), not elem(X,B). sottinsieme(A,B) :- not nonSottinsieme(A,B).
in modo da rendere possibile un colloquio come
?- intersecati(tra(5,9),tra(9,20)). yes ?- sottinsieme(vuoto, cifre). yes
Le seguenti definizioni descrivono invece, per caratterizzazione, gli insiemi intersezione, differenza, unione.
elem(X,intersezione(A,B)) :- elem(X,A), elem(X,B). elem(X,differenza(A,B)) :- elem(X,A), not elem(X,B). elem(X,unione(A,B)) :- elem(X,A). elem(X,unione(A,B)) :- elem(X,B), not elem(X,A).
Dopo di che si potranno formulare interrogazioni come
?- elem(X,differenza(tra(3,8),tra(5,7)).
oppure
?- elem(X,intersezione(cifre,pari)).
mentre è da evitare una interrogazione del tipo
?- elem(X,intersezione(pari,cifre)).
poiché la ricerca per enumerazione dei numeri pari che siano anche cifre termina, a rigore, una volta esaminati tutti i numeri pari. Naturalmente è possibile anche un colloquio del genere
?- sottinsieme(intersezione(cifre,pari),cifre). yes
Per arrivare infine al concetto di numerosità di un insieme si può passare attraverso quello di equipotenza, che è definibile ricorsivamente con
equipotenti(A,B) :- vuoto(A), vuoto(B). equipotenti(A,B) :- elem(X,A), elem(Y,B),!, equipotenti(differenza(A,[X]),differenza(B,[Y])).
dove il cut, anche in questo caso, serve soltanto per questioni di efficienza ma non alla logica della definizione. La cardinalità di un insieme, o potenza, può essere allora definita nel modo seguente
potenza(A,N) :- elem(N,naturali), equipotenti(A,tra(1,N)), !.
Alternativamente
potenza(A,0) :- vuoto(A). potenza(A,N) :- elem(X,A), !, potenza(differenza(A,[X]),N1), N = N1 + 1.
oppure, con una notazione numerica primitiva,
potenza(A,[]) :- vuoto(A). potenza(A,[i|N]) :- elem(X,A), potenza(differenza(A,[X]),N).
consentendo un colloquio come
?- potenza([a,a,b],N). N=[i,i] ?- potenza([tra(5,7),N). N=[i,i,i]
Una relazione binaria è un sottinsieme di un insieme prodotto cartesiano, definibile con:
elem(coppia(X,Y),prodottoCartesiano(A,B)) :- elem(X,A), elem(Y,B).
Alcuni esempi di relazioni sono:
elem(coppia(1,a),r). elem(coppia(2,b),r). elem(coppia(3,c),r).
essendo 'r' il nome scelto per la relazione descritta.
elem(coppia(X,S),appartiene) :- elem(X,S). elem(coppia(S,N),numeroDiElementi) :- potenza(S,N). elem(coppia(X,Y),d) :- elem(X,tra(0,15)), Y is 2*X.
Si possono definire così dominio e codominio di una relazione:
elem(X,dominio(Rel)) :- elem(coppia(X,_),Rel). elem(Y,codominio(Rel)) :- elem(coppia(_,Y),Rel).
ed inoltre proprietà delle relazioni come
nonRiflessiva(Rel) :- elem(X,dominio(Rel)), not elem(coppia(X,X),Rel). riflessiva(Rel) :- not nonRiflessiva. nonSimmetrica(Rel) :- elem(coppia(X,Y),Rel), not elem(coppia(Y,X),Rel). simmetrica(Rel) :- not nonSimmetrica. nonTransitiva(Rel) :- elem(coppia(X,Y),Rel), elem(coppia(Y,Z),Rel), not elem(coppia(X,Z),Rel). transitiva(Rel) :- not nonTransitiva.
e inoltre
diEquivalenza(Rel) :- riflessiva(Rel), simmetrica(Rel), transitiva(Rel).
Un'altra importante proprietà di cui può godere una relazione tra due insiemi è quella di essere una funzione. Una relazione da un insieme A ad un insieme B si chiama funzione quando: i. ad ogni elemento di A associa un elemento di B, ii. ad ogni elemento di A è associato un solo elemento di B. Considerando la solita difficoltà di comunicare al Prolog un concetto definito mediante il quantificatore universale 'ogni' converrà passare attraverso la definizione della negazione di quel concetto. Spiegheremo quindi che la relazione non è una funzione quando: i. esiste anche un solo elemento di A che non viene associato ad elementi di B, oppure ii. esiste un elemento di A che viene associato a due elementi diversi di B. In linguaggio Prolog scriveremo:
nonFunzione(Rel,A,B) :- elem(X,A), not elem(coppia(X,_),Rel). nonFunzione(Rel,A,B) :- elem(coppia(X,Y1),Rel), elem(coppia(X,Y2),Rel), Y1 \= Y2.
e infine:
funzione(F,A,B) :- not nonFunzione(F,A,B).
Anche le proprietà fondamentali delle funzioni possono essere definite in modo da essere comunicate all'automa Prolog, ad esempio come nel seguito.
nonIniettiva(Rel,A,B) :- elem(coppia(X1,Y),Rel), elem(coppia(X2,Y),Rel), X1 \= X2. iniettiva(Rel,A,B) :- not nonIniettiva(Rel,A,B). nonSuriettiva(Rel,A,B) :- elem(Y,B), not elem(coppia(_,Y),Rel). suriettiva(Rel,A,B) :- not nonSuriettiva(Rel,A,B).
Infine possiamo dire che
biiettiva(F,A,B) :- funzione(F,A,B), iniettiva(F,A,B), suriettiva(F,A,B).