ENCICLOPEDIA TASCABILE. IL SAPERE.
GIULIANO SPRITO.
MATEMATICA SENZA NUMERI.

INTRODUZIONE.
 Anche tra persone colte avviene spesso che la matematica non
sia amata; guardata con stupore, a volte con timore reverenziale,
sempre con rispetto, ma proprio amata non si pu dire...
 In realt, gran parte di questa awersione dipende da un'imma-
gine riduttiva della matematica, conseguente anche ad una tradi-
zione didattica che mortifica gli aspetti creativi e problematici
della materia, privilegiando tecniche e procedimenti meccanici e
ripetitivi; tant' che il sapere matematico viene spesso identifica-
to con la precisione, la scioltezza e la rapidit nel far calcoli. Ma
se dawero cos fosse, il pi abile matematico sarebbe... il compu-
ter!
 C' dunque un equivoco sulla natura della matematica; ai mate-
matici il compito di rimuovere i preconcetti e di combattere le
prevenzioni! Un modo - forse provocatorio, ma certo efficace -
per farlo  quello di parlare di matematica senza numeri; il che
vuol dire penetrare in quei territori della matematica che sono i
pi lontani dalla pratica del far di conto e che hanno acquista-
to, nel tempo, importanza sempre maggiore.
 In questo libro ci sono solo alcuni tra i tanti possibili esempi di
matematica senza numeri (e, si potrebbe aggiungere, senza le
abituali figure geometriche); essi sono tuttavia sufficienti a mo-
strare come essa non sia una sorta di gioco di prestigio, n un eser-
cizio di stile fine a se stesso.
 Il nostro percorso inizia andando a vedere cosa succede se stabi-
liamo opportuni collegamenti tra gli elementi di un insieme di na-
tura qualsiasi: ebbene, dove c'erano solo disordine e caos (muc-
chi di oggetti alla rinfusa, senza n capo n coda), ecco emergere
una fonna (elementi disposti secondo un preciso ordine o armo-
nicamente ripartiti in classi). Se poi le connessioni riguardano
elementi di due insiemi diversi, il loro esame rende possibile af-
frontare problemi inusuali (ad esempio, il confronto tra le gran-
dezze di due insiemi infiniti), pervenendo a conclusioni spesso
sorprendenti. Si entra cos nel cuore della teoria degli insiemi,
la teoria pi generale di tutta la matematica, una specie di capi-
tolo zero che funge da premessa comune alle singole e particolari
teorie di cui si compone l'edificio di questa scienza.
 Un'altra tappa fondamentale del nostro itinerario ci conduce
su un terreno scivoloso e infido, che costringe matematici, logici
e filosofi a mettere in comune le loro forze: awiene quando pro-
viamo a porci in modo critico il problema di valutare se una frase
 vera o falsa, e, ancor di pi, quando tentiamo di mettere a pun-
to un piccolo galateo del buon ragionare per essere certi di opera-
re deduzioni corrette. Si tratta di questioni fondamentali per una
scienza - la matematica - che non trae la sua legittimit dallo stu-
dio della natura, ma dalla coerenza e dall'eleganza della sua co-
struzione.
 Ed eccoci infine al termine del percorso: la nostra attenzione si
concentra sui linguaggi artificiali (ad esempio i linguaggi che usia-
mo per impartire istruzioni al calcolatore). Cosa significa e in
quanti modi  possibile controllare e possedere un linguaggio
artificiale? Vedremo che vi sono almeno due punti di vista diver-
si sulla questione: il primo, utilizzando anche i risultati ottenuti
dagli studiosi di linguistica, ci conduce alla considerazione delle
cosiddettegrammatichegenerative, meccanismi automatici per la
produzione di frasi del linguaggio; il secondo, legato pi diretta-
mente allo sviluppo dell'informatica, si basa sulla nozione di au-
toma riconoscitore, macchina ideale in grado di distinguere ci
che appartiene ad un linguaggio da ci che ad esso  estraneo.
 Si scopre cos che le tematiche di quella che abbiamo chiamato
la matematica senza numeri sono tutt'altro che marginali:
esse, chiamando in causa la logica, la scienza del calcolatore, la
linguistica, i fondamenti stessi della costruzione matematica,
evocano panorami vasti e poco esplorati, in cui saperi diversi si
incontrano producendo risultati imprevisti e suggestivi.

1. La teoria degli insiemi.


1. I Perch e in quali modi dare una struttura a un insieme.

 Per cominciare il nostro cammino attraverso la matematica
senza numeri dobbiamo in primo luogo abituarci a ragionare su
insiemi (aggregati, raccolte, gruppi, collezioni) costituiti da og-
getti di natura qualsiasi (oggetti concreh, come alberi, penne, perso-
ne, oppure oggetti mentali come parole, triangoli, numeri). Se riu-
sciremo a dire qualcosa di significativo - anzi, di matematicamente
significativo - a proposito di insiemi di questo tipo, ebbene, allo-
ra avremo vinto la scommessa:  possibile, sensato, utile far ma-
tematica senza mettere i numeri (e le abituali figure geometri-
che) al centro della nostra attenzione!
 Dunque: riferiamoci, per fissare le idee, a un determinato in-
sieme, quello costituito dalle parole della lingua italiana. Queste
parole le possiamo pensare come un insieme confuso, una specie
di mucchio indistinto da cui attingere ogni volta che ne abbiamo
bisogno.


                              maccheroni
                         bellezza porta gatto
                   circolo casale strano cera volo
               sosia mano libro podere tenero rete vino
           gigante dente archetipo filo bevanda cinese zio
         parallelo asino bere tavola casacca zuzzurellone mio
         gelato peso zuava casa forse immagine arco terno ala


Ecco le parole della lingua italiana ammucchiate disordinatamente.

 Per, per poter svolgere qualche attivit significativa con gli ele-
menti di questo insieme,  conveniente pensarli organizzati in qual-
che modo e in qualche senso. Cosa vogliamo dire? Vogliamo dire
che, ad esempio, per controllare l'esistenza del vocabolopedisse-
quamente, la sua scrittura corretta, il suo significato, ricorreremo
ad un vocabolario, in cui le parole sono disposte - per facilitare la
ricerca - in un preciso ordine. Mentre invece, in altre situazioni -
ad esempio per analizzare la correttezza grammaticale della fra-
se un bacio  un apostrofo rosa messo tra le parole t'amo - giocher
un ruolo fondamentale la ripartizione in classi dei vocaboli secon-
do la loro funzione: aggettivi, sostantivi, forme verbali, ecc.
 Ordinamento e ripartizione in classi: ecco due modi di proiettare
un principio organizzatore su un insieme - owero, come anche si
dice, di strutturare un insieme - che ci permettono di lavorare
meglio con i suoi oggetti. Dunque  l'introduzione di un criterio
organizzatore nell'insieme considerato a dargli una forma meno
confusa e indistinta.
 Ebbene, se ci fermiamo un momento a riflettere - scelta sem-
pre piuttosto saggia, tanto pi nella nostra societ frenetica e con
il mito della velocit! -, scopriamo che l'introduzione di un prin-
cipio o criterio organizzatore  conseguente alla considerazione
di una determinata relazione tra coppie di elementi dell'insieme.
Nel primo esempio (organizzazione delle parole in un vocabola-
rio), la relazione  quella di precedere in ordine alfabetico, nel
secondo caso (organizzazione delle parole in una grammatica) la
relazione  quella di appartenere alla stessa forma grammatica-
le. E in virt di una relazione che gli oggetti che compongono l'in-
sieme smettono di apparirci come elementi isolati, privi di legami
l'uno con l'altro (finch restavano tali erano necessariamente con-
fusi in un tutto indistinto); essi, al contrario, vengono ora ad essere
collegati attraverso una fitta rete di connessioni. E sono proprio
queste connessioni a dare all'insieme una determinata struttura.
 Ad esempio, nel primo caso (vocabolario) la relazione prece-
dere in ordine alfabetico ha stabilito di fatto dei collegamenti
tra parole: per ciascuna coppia di parole presa in esame, la prima ri-
sulta congiunta con la seconda se la precede in ordine alfabetico,
non risulta congiunta se non la precede in ordine alfabetico. La pa-
rolacasa  quindi connessa con le parole casacca e casale (che la se-
guono da vicino in ordine alfabetico), ma anche con le parole
zuava e zuzzureUone (che sono piuttosto lontane, ma pur sempre
seguenti nell'ordinamento alfabetico); mentre la parola casale non
 connessa con le parole casa e casacca, poich non le precede in or-
dine alfabetico. Ovviamente ci non significa escludere sempre e in
tutti i casi l'esistenza di ogni e qualsiasi collegamento che parte dal-
la parola casale e la congiunge, ad esempio, con la parola casa. Ci li-
mitiamo ad affermare che la particolare relazione che stiamo con-
siderando (precedere in ordine alfabetico) non stabilisce una
connessione tra casale e casa; mentre, se consideriamo la relazio-
ne inversa (seguire in ordine alfabetico), il collegamento tra casa-
1e casa esiste di sicuro! Insomma, per evitare di far confusione oc-
corre sempre aver chiaro qual  la relazione su cui stiamo concen-
trando - in un determinato momento - la nostra attenzione.




               casa        casale           zuava
         casacca            zuzzurellone


Relazione ..precedere in ordine alfabetico: le frecce collegano ciascuna parola con lut-
te le parole che la seguono in ordine alfabetico.

 Analogamente, nel secondo caso (grammatica) la relazione ap-
partenere alla stessa forma grammaticale ha stabilito alcuni col-
legamenti tra parole: per ciascuna coppia di vocaboli presi in
considerazione, il primo risulta congiunto al secondo se e solo se
il primo appartiene alla stessa forma grammaticale del secondo.
La parolapane, che  un sostantivo,  quindi connessa con tutti
gli altri sostantivi, mentre la parola caro, che  un aggettivo, 
connessa con tutti gli altri aggettivi della lingua italiana.



                   fiore     casa    bello     debole



                                    pI~e~cQ;~
                                naso               mite


Le frecce collegano ciascuna parola con tutte le parole che appartengono alla stessa for-
ma grammaticale.

Dunque, le nostre relazioni, creando dei collegamenti tra gli
elementi all'interno dell'insieme, I'hanno dotato di una struttu-
ra. E quanto detto non vale solo per l'insieme (parole della lin-
gua italiana) e le relazioni considerate (precedere in ordine al-
fabetico e appartenere alla stessa forma grammaticale). Qual-
che ulteriore esempio potr convincerci di ci:

 - I'insieme degli alunni di una classe e la relazione essere pi
alto; in questo caso la relazionefornisce un ordinamento (dal pi
alto al pi basso) degli alunni della classe;
 - I'insieme degli alunni di una scuola e la relazione appartene-
re alla stessa sezione; in questo caso la relazione determina una
ripartizione (alunni della st~ssa sezione nello stesso gruppo);
 - I'insieme delle citt italiane e la relazione essere pi vicino a
Roma; in questo caso la relazione fomisce un ordinamento (Fi-
renze  pi vicina a Roma di Milano, Viterbo  pi vicina a Roma
di Firenze, ecc.);
 - I'insieme delle citt italiane e la relazione essere nella stessa
regione; in questo caso la relazione determina una nipartizione
(citt della stessa regione nello stesso gruppo).

 Ricapitoliamo le nostre scoperte:

 a. Si pu pensare ad un insieme in due modi diversi: come ad un
mucchio indistinto di oggetti, o come ad una entit organizzata
secondo qualche criterio.
 b. Per introdurre un criterio organizzatore in un insieme occor-
re considerare una relazione tra i suoi elementi.
 c. Considerare una relazione in un insieme significa smettere di
pensare i suoi elementi come atomi isolati, per cominciare a pen-
sarli come connessi da una fitta rete di collegamenti.
 d. Vi sono due tipi di relazioni particolarmente importanti al fine di
dare una struttura ad un insieme: le relazioni che producono un or-
dinamento e le relazioni che producono una ripartizione (in classi).

 Per il momento ci fermiamo qui: di carne al fuoco ce n' gi ab-
bastanza. Non rinunciamo per a far notare che stiamo man-
tenendo la nostra promessa: lasciare da parte numeri e calcoli.


1.2. Che cosa  un ordinamento?

 Mettere in ordine. Sicuramente  un'attivit che consente di or-
ganizzare in qualche modo e in qualche senso un insieme di oggetti.
E dunque , a pieno titolo, all'interno del programma che ci era-
vamo proposti.
 Ma i problemi nascono adesso... Perch a questo punto  neces-

sario capire cosa vuol dire un ordinamento. Un filosofo cerche-
rebbe di farlo attraverso un'opportuna definizione, un letterato
si metterebbe ad elencare parole di significato analogo; il ma-
tematico si limita a cercare di individuare le propriet che caratte-
rizzano una relazione che produce un ordinamento (la definizio-
ne tecnica per questo tipo di relazioni  relazioni d'ordine), cio
quelle propriet che una relazione deve possedere perch i colle-
gamenti tra elementi dell'insieme che si vengono a realizzare costi-
tuiscano un ordinamento dell'insieme stesso.
 Riprendiamo pazientemente in esame lo schema (il termine tecni-
co  grafo) che illustrava le parole del vocabolario dopo l'introdu-
zione della relazione d'ordine precedere in ordine alfabetico:

                   casacca           zuzzureUone
e confrontiamolo, ad esempio, con lo schema (grafo) che illustra
la relazione (che certamente non  una relazione d'ordine) es-
sere innamorato di nell'insieme dei protagonisti di una qualche
telenovela:
Samantha       Paul

Deborah/Jessica

Alonzo      Gordon  Manuela
Roderigo

 Saltano agli occhi alcune differenze. Intanto: nel primo grafo le
frecce hanno tutte una sola punta (se casa precede zuzurellone,
zuzzurellone non pu certo precedere casa), mentre nel secondo
esistono anche frecce a due punte (Jessica e Gordon - beati loro!
- si amano a vicenda; e stesso fortunato destino lega la dolce Sa-
brina e il virile Roderigo). E poi: nel primo grafo, se esiste una
freccia che collega il vocabolo a al vocabolo b, e un'altra freccia
che collega il vocabolo b al vocabolo c, allora esiste anche una frec-
cia che collega a con c (se casa precede casale e casale precede zua-
va, certamente casa precede zuava); niente di tutto questo accade
nel secondo: Samantha ama Paul e Paul ama Deborah, ma, come si
pu ben immaginare, Samantha non ama Deborah (tutt'altro!).
 Bene, I'analisi di queste differenze ci permette di definire con pre-
cisione quali sono le propriet che caratterizzano, nel mucchio del-
le relazioni, quelle particolari relazioni che si dicono relazioni d 'or-
dine. Per dirla nel linguaggio della matematica, una relazione d'or-
dine  una relazione anti-simmetrica (ogni freccia del grafo che la
rappresenta ha una sola punta) e transitiva (se a  connesso con
b e b  connesso con c, allora a  certamente connesso con c).

Propriet anti-sirnrnetnica: ogni freccia
ha una sola punta; owero, se c' la
punta pi rnarcata, non ci pu essere
la punta pi sottile.

Propriet transitiva: se ci sono le due
frecce pi marcate, ci deve essere an-
che la freccia pi sottile.


 Una conferma del fatto che la propriet anti-simmetrica e la pro-
priet transitiva sono caratteristiche delle relazioni d'ordine si ot-
tiene ripensando alle altre due relazioni che producevano ordina-
menti precedentemente incontrate (la relazione essere pi alto
nell'insieme degli alunni di una classe; la relazione essere pi vici-
no a Roma nell'insieme delle citt italiane): un rapido controllo
ci permette di stabilire che anch'esse godono delle due propriet
appena citate. Insomma, abbiamo individuato le propriet carat-
teristiche delle relazioni d'ordine, le uniche, nel mare delle rela-
zioni, che producono un ordinamento nell'insieme considerato!
 A questo punto un'osservazione attenta potrebbe portare ad una
scoperta (un evviva per chi osserva con attenzione!): I'insieme di
frecce che illustra la relazione d'ordine nel vocabolario ha altre
caratteristiche significative (ad esempio, date due parole, o c'
una freccia che collega la prima alla seconda o c' una freccia che
collega la seconda alla prima - giacch date due parole una delle
due precede certamente l'altra in ordine alfabetico). Ed ecco al-
lora spuntare fuori un'ipotesi awentata (un abbasso per chi ipo-
tizza awentatamente!): forse tutte le relazioni d'ordine devono
sottostare a questa ulteriore condizione... Abbiamo definito av-
ventata questa ipotesi perch un rapido controllo sugli altri due
ordinamenti considerati  sufficiente a smentirla ingloriosamen-
te: infatti, nell'esempio di ordinamento per altezza della classe,
pu ben succedere che gli alunni Bassetti e Gigante abbiano la
stessa altezza - e dunque n Bassetti precede Gigante, n Gi-
gante precede Bassetti; cos, nel caso delle citt ordinate per
distanza da Roma, pu awenire che due di esse abbiano la stessa
distanza da Roma - e dunque, n la prima precede la seconda,
n la seconda precede la prima. La nostra conclusione  che
una relazione d'ordine deve godere necessariamente almeno
delle propriet anti-simmetrica e transitiva; se gode di altre pro-
priet... buon per lei!
 Ci non toglie che siamo sempre pronti a rendere onore al me-
rito: ad esempio, una relazione d'ordine in cui, per di pi, dati
due elementi uno dei due precede necessariamente l'altro ( il
caso de11'ordinamento alfabetico del vocabolario) avr il privile-
gio di essere citata come una relazione d'ordine totale.
 Un'ultima osservazione prima di ripercorrere rapidamente i
momenti pi significativi di questo paragrafo: dobbiamo toglier-
ci dalla testa l'idea che un insieme nasca, per cos dire, gi ordi-
nato. L'operazione di attribuzione di un ordinamento  un'opera-
zione che facciamo noi, con ampi margini di libert. Tanto  vero
che, dato un determinato insieme, ad esempio l'insieme degli abi-
tanti di un palazzo, ci pu venire in mente di ordinarlo in pi
modi (secondo il piano a cui abitano, secondo l'ordine alfabetico
dei loro cognomi, secondo la data di nascita, secondo il numero
di automobili possedute dalla famiglia, ecc.). Non solo: nel mo-
mento in cui decidiamo di organizzare un insieme secondo un
determinato ordinamento, stiamo implicitamente organizzando
l'insieme anche rispetto ad un altro ordinamento, quello inverso,
come abbiamo visto a proposito della relazione precedere in or-
dine alfabetico, a cui  naturalmente associata la relazione se-
guire in ordine alfabetico; quindi non  possibile inventare un
ordinamento senza dar vita - volenti o nolenti! - almeno ad un al-
tro, I'ordinamento inverso.

Siamo ormai pronti per la ricapitolazione finale:

 a. Una relazione d'ordine produce un ordinamento dell'insie-
me.
 b. Una relazione d'ordine  caratterizzata da due propriet, la
propriet anti-simmetrica e la propriet transitiva.
 c. La propriet anti-simmetrica consiste nel fatto che dati due
elementi qualsiasi dell'insieme a e b, se a  in relazione con b, b
non  certamente in relazione (in quella relazione!) con a.
 d. La propriet transitiva consiste nel fatto che dati tre elementi
qualsiasi dell'insieme a, b e c, se a  in relazione con b e b  in re-
lazione con c, certamente a  in relazione con c.
 e. Una relazione d'ordinepu godere anche di altre propriet,
in particolare, se dati due elementi qualsiasi dell'insieme a e b Si
ha necessariamente che a  in relazione con b o b  in relazione
con a, si parla di relazione d'ordine totale.


 1.3. Che cosa  una ripartizione in classi?

 Abbiamo visto che un altro modo di organizzare un insieme 
quello di ripartirlo in classi.
 Abbiamo anche visto che tale ripartizione  conseguente all'in-
troduzione di una relazione appartenente ad una specifica cate-
goria di relazioni (il nome tecnico  relazioni di equivalenza),
che, di fatto, determinano una classificazione degli elementi del-
I'insieme.
 Come per le relazioni d'ordine, anche in questo caso cerchlamo
di individuare quali sono le propriet che caratterizzano le rela-
zioni di equivalenza nel mucchio delle relazioni. Riprendiamo
dunque in esame il grafo (ormai sappiamo che si chiama cos) che
illustrava la relazione appartenere alla stessa forma grammati-
cale:


          fioret      casia    bello     debole
naso

e confrontiamolo, di nuovo, con il grafo relativo alla relazione di
innamoramento nell'insieme dei protagonisti della telenovela
relazione, quest'ultima, che certamente non produce un'ordina-
ta divisione in classi dei nostri eroi:


                       Samantha    Paul


                      Deborah       Jessica


Alonzo      Gordon

                              Sabrina


                              Rodaigo


- Mianuela


 Anche in questo caso salta agli occhi che il grafo relativo alla re-
lazione di equivalenza (appartenere alla stessa forma gramma-
ticale) ha delle propriet che non ritroviamo nel secondo grafo
relativo ad una relazione qualsiasi (la relazione essere inna-
morato di non produce n ordinamento, n ripartizione in clas-
si). Nel primo grafo, infatti, osserviamo che ogni elemento  col-
legato con se stesso - il che  owio, poich la parolapane appar-
tiene alla stessa forma grammaticale a cui appartiene la parola
pane -, mentre nel secondo ci  vero solo per Alonzo, che passa
intere giornate davanti allo specchio essendo perdutamente in-
namorato di se medesimo! Inoltre, nel primo grafo ogni freccia
ha due punte: sepane appartiene alla stessa forma grammaticale
a CUI appartiene naso, naso appartiene alla stessa forma grammati-
cale a cui appartienepane; mentre, ad esempio, I'amore di Saman-
tha per Paul non  - purtroppo! - minimamente corrisposto
Infine, per la relazione illustrata dal primo grafo vale la proprie
t transitiva: sepane appartiene alla stessa forma grammaticale a
CUl appartiene naso e naso appartiene alla stessa forma gramma-
ticale a cui appartiene casa, certamente pane appartiene alla stes-
sa forma grammaticale a cui appartiene casa; mentre non  cos
per la relazione illustrata dal secondo, dato che, come gi segna-
lato, I amore di Samantha per Paul e di Paul per Deborah non fa-
vorisce la nascita di sentimenti affettuosi da parte di Samantha
verso Deborah.
 Dunque, una relazione di equivalenza  una relazione riflessiva
(ogni elemento dell'insieme  punto di partenza e punto di arri-
vo di una stessa freccia) e simmetrica (ogni freccia ha due pun-
 e), o trec e transitiva.

Propriet riflessiva: ogni Propriet simmetrica: ogni Propriet transitiva. se ci
elernento ha una freccia a freccia ha d, olPPpaunPtUa piu cate, ci deve essere anche

rnarcata ci deve essere an- la freccia plu sotle.
che la punta pi sottile.

E opportuno aprire una piccola parentesi per prevenire un pos-
sibile errore. Abbiamo visto che esistono relazioni simmetriche
(ad esempio, sono simmetriche tutte le relazioni di equivalenza)
e relazioni anti-simmetriche (ad esempio, sono anti-simmetriche
tutte le relazioni d'ordine); si potrebbe pensare che non ci sia
una possibilit intermedia. Niente di pi falso: esistono infinite
relazioni che non sono n simmetriche n anti-simmetnche. Cio
dipende dal fatto che i matematici sono estremamente esigenti e
si degnano di attribuire ad una relazione il titolo di simmetrica
solo se essa lo  dappertutto (nel grafo di una relazione sim-
metrica ogni freccia deve avere due punte); analogamente per i1
titolo di anti-simmetrica (nel grafo di una relazione anti-simme-
trica ogni freccia deve avere una sola punta). La maggior parte
delle relazioni soddisfa solo localmente ciascuna di queste due
condizioni; e quindi ci sono &ite relazioni che sono localmen-
te simmetriche e, per, anche localmente anti-simmetriche.
Ma ci comporta che, essendo in qualche punto simmetnche,
non possano essere classificate come anti-simmetnche, e, essen-
do in qualche punto anti-simmetriche, non possano essere classi-
ficate come simmetriche. Ad esempio, la relazione di innamo-
ramento tra i protagonisti della telenovela  localmente anti-
simmetrica (Samantha ama Paul, che per non ama Samantha),
e, al tempo stesso, localmente simmetrica (Jessica e Gordon,
come gi osservato, si amano a vicenda); quindi non , nel com-
plesso, n simmetrica n anti-simmetrica. Analogamente, esisto-
no infinite relazioni localmente riflessive che per non sono
globalmente riflessive, cos come esistono infinite relazioni lo-
calmente transitive senza per questo essere dawero transitive.
Insomma: agli esseri umani piace pensare che il mondo sia in
bianco e nero, ma la verit  che il colore pi diffuso nella realt
 il grigio!
 Ma torniamo alle relazioni di equivalenza. E passato del tempo
da quando abbiamo portato altri esempi di relazioni che produce-
vano una ripartizione in classi; vale quindi la pena di citarli di
nuovo, per controllare che anche in questi casi risultino verificate
le condizioni che deve soddisfare una relazione per poter ambire
al titolo di relazione di equivalenza. Avevamo parlato della rela-
zione appartenere alla stessa sezione come di una relazione
che induce una ripartizione nell'insieme degli alunni di una scuo-
la: ebbene, effettivamente ogni alunno, anche il pi distratto, sa
di appartenere ad una determinata sezione (e quindi Aldo ap-
partiene alla stessa sezione a cui appartiene Aldo, Bruno appar-
tiene alla stessa sezione a cui appartiene Bruno, e cos via - dun-
que la relazione  riflessiva); inoltre se Carlo appartiene alla stes-
sa sezione a cui appartiene Davide,  vero anche che Davide ap-
partiene alla stessa sezione a cui appartiene Carlo (dunque la
relazione  simmetrica); infine, se Ettore appartiene alla stessa
sezione a cui appartiene Franco, e Franco appartiene alla stessa
sezione a cui appartiene Giulio, possiamo esser certi che Ettore
appartiene alla stessa sezione a cui appartiene Giulio (dunque la
relazione  transitiva). Insomma, riflessivit, simmetria e transi-
tivita sono assicurate!
 Analogamente, la relazione appartenere alla stessa regio-
ne, che induce una ripartizione in classi nell'insieme delle cit-
t italiane,  una relazione riflessiva, simmetrica e transitiva (il
ragionamento  identico a quello visto per gli allievi della scuo-
 Eccoci allora pronti per l'ormai abituale ricapitolazione di fine
paragrafo:

 a. Una relazione di equivalenza determina una ripartizione in
classi di un insieme.
 b. Una relazione di equivalenza  caratterizzata da tre proprie-
ta: la propriet riflessiva, la propriet simmetrica e la propriet
transitiva.
 c. La propriet riflessiva consiste nel fatto che dato un elemen-
to qualsiasi dell'insieme a, a  certamente in relazione con se
stesso.
 d. La propriet simmetrica consiste nel fatto che dati due ele-
menti qualsiasi dell'insieme a e b, se a  in relazione con b, b 
certamente a sua volta in relazione con a.
 e. La propriet transitiva - come gi detto - consiste nel fatto
che dati tre elementi qualsiasi dell'insieme a, b e c, se a  in rela-
zione con b e b  in relazione con c, certamente a  in relazione
con c.


1.4. Importanza nella matematica delle relazioni d 'ordine e
     delle relazioni di equivalenza

 E venuto il momento di affrontare il dubbio che probabilmen-
te agita il nostro lettore: d'accordo, le reazioni d'ordine e
quelle di equivalenza sono interessanti; ed  vero, il discorso
ha rigorosamente evitato ogni riferimento agli universi nume-
rici; ma insomma, cosa ha a che fare tutto ci con la matema-
tica?.
 Cosa si pu rispondere ad un'obiezione che sembra a prima vi-
sta tanto fondata?
 Intanto, vogliamo sottolineare che le relazioni d'ordine e le re-
lazioni di equivalenza sono solo un'esigua minoranza privile-
giata nel mare sconfinato delle possibili relazioni - owero: quasi
tutte le relazioni non sono n d 'ordine n di equivalenza. Abbiamo
gi detto che esistono relazioni che sono qua e l riflessive senza
essere nel complesso riflessive, cos come esistono relazioni a
tratti transitive senza esserlo nella loro globalit; abbiamo anche
mostrato, addirittura con un esempio suggestivo (la telenovela e
gli amori in essa narrati), che esistono relazioni che non sono n
simmetriche, n anti-simmetriche. Dunque non c' da sorprendersi
se sottolineiamo che le relazioni d'ordine e le relazioni di equiva-
lenza costituiscono delle eccezioni degne di nota in un panorama
generale di mediocrit!
 Eccezioni, quindi, e degne di note: infatti esse - anche questo lo
abbiamo gi detto - sono le uniche relazioni che producono, ri-
spettivamente, ordinamenti e ripartizioni in classi; e non vi  dub-
bio che ordinamenti e ripartizioni in classi siano strumenti a cui
facciamo continuamente ricorso nell'organizzazione del sapere.
 Resta da evidenziare l'importanza che essi rivestono in ambito
matematico, numerico o non numerico;  giunto il momento di
accingersi a questo compito.
 Concentriamo innanzitutto la nostra attenzione sugli ordina-
menti (e quindi sulle relazioni d~ordine). Il primo universo nu-
merico in cui impariamo a muoverci - quando siamo ancora fan-
ciulli spensierati che nella loro vita non hanno incontrato la ma-
tematica! -  costituito dall'insieme dei numeri naturali (gli interi
da zero in poi). Ebbene, I'approccio ai naturali awiene attraver-
so l'attivit del contare, che  basataUlfatto di pensare questo in-

sieme numerico come ordinato. La stessa costruzione dei naturali
attraverso il meccanismo di generazione del successivo  intrin-
secamente connessa con l'ordinamento - non l'unico, ma quello
pi spontaneo e importante - dell'insieme (si parte da O; si cos-
truisce il successivo di O aggiungendo 1, e si ottiene 1; si costrui-
sce il successivo di 1 aggiungendo ancora 1, e si ottiene 2; si co-
struisce il successivo di 2 aggiungendo sempre 1, e si ottiene 3;
ecc.). Dunque l'ordinamento  una caratteristica cos essenziale
dell'insieme numerico pi familiare (I'insieme dei naturali) da
rendere difficile anche concepire questo insieme prescindendo da
esso.
 Per chi desiderasse poi un esempio di ordinamento significativo
in ambito matematico ma non numerico, ecco l'esempio dell'in-
sieme di tutte le figure del piano, ordinate a partire dalla con-
siderazione della relazione di inclusione: che si tratti di un ordi-
namento discende dal fatto che la relazione di inclusione - cio la
relazione essere sottoinsieme (owero parte) di -  evidentemen-
te anti-simmetrica e transitiva.

 Ma c' di pi: la nostra riflessione pi generale sugli ordina-
menti ci permette ora di relativizzare anche gli ordinamenti
pi abituali degli insiemi pi consueti. L'ordinamento crescente
 solo uno dei possibili ordinamenti dei numeri naturali, suscet-
tibili di altri e diversi ordinamenti: ad esempio, essi possono es-
sere leggittimamente ordinati secondo la precedenza alfabetica
(per cui due precede quattro, ma dieci precede sei! ). Analogamen-
te, I'ordinamento delle figure secondo il criterio dell'inclusione
pu essere affiancato senza scandalo dal loro ordinamento se-
condo la misura dell'area, e cos via...

 Messi a posto gli ordinamenti, dedichiamoci alle ripartizioni in
classi. Sono anch'esse dawero cos importanti in matematica?
La risposta a questo legittimo dubbio  positiva. Le ripartizioni
in classi sono degne di interesse per tante ragioni; la principale 
collegata al fatto che la considerazione di una relazione di equi-
valenza (cio di una relazione che produce una ripartizione del-
I'insieme) finisce per deterrninare un nuovo insieme, diverso da
quello di partenza.
 Vediamo la faccenda con calma, dato che, fino ad ora, di questo
nuovo insieme non si era fatta parola. Partiamo da un esempio:
consideriamo tutte le rette di un piano e la relazione di paralle-
lismo. Si tratta di una relazione di equivalenza: essa  evidente-
mente simmetrica e transitiva;  anche riflessiva, se definiamo la
coincidenza come un caso particolare di parallelismo. Ebbene, la
relazione di parallelismo suddivide le rette del piano in classi,
ciascuna caratterizzata da una specifica direzione, e quindi d
luogo ad un nuovo insieme, I'insieme delle direzioni del piano.
Ogni elemento di questo nuovo insieme (cio ogni direzione) 
costituito da una classe di elementi equivalenti dell'insieme di
partenza (cio da tutte le rette parallele aventi quella direzione).
 Il nuovo insieme, determinato dalla relazione di equivalenza e
avente come elementi le classi di elementi equivalenti dell'in-
sieme di partenza, si dice insieme quoziente. Nel caso delle rette
di un piano e della relazione di parallelismo, I'insieme quoziente
 l'insieme delle direzioni possibili sul piano.
 Il passaggio dall'insieme dato all'insieme quoziente - passaggio
che awiene attraverso una relazione di equivalenza -  molto
importante in matematica, poich consente di ragionare con-
siderando tutti gli elementi di una classe come un unico oggetto
(tutte le rette del piano tra loro parallele corrispondono a un'u-
nica direzione nel piano); si tratta dunque di un processo di astra-
zione e la matematica ... il regno dell'astrazione! Ricordiamoci,
infatti, che persino un semplice numeretto  un'astrazione (non
esistono 3 che passeggiano per strada, essendo il numero 3 la no-
zione astratta che sintetizza tutte le terne concrete di oggetti),
esattamente nel senso appena detto: nell'insieme dei raggruppa-
menti di oggetti, la relazione avere la stessa quantit di elemen-
ti  una relazione di equivalenza che ripartisce tutti i raggruppa-
menti in classi; I'insieme quoziente  costituito da tutti i numeri,
giacch il numero 3, ad esempio,  la classe di tutti i raggrup-
pamenti contenenti tre oggetti. Insomma, la relazione di e-
quivalenza ha a che fare con il passaggio concreto-astratto, che 
uno dei passaggi caratteristici dell'intera costruzione matema-
tica, in ambito numerico e non numerico.

TEORIA DEGLI INSIEMI               25





Dall'insierne dei raggruppamenti di oggetti...





.. attraverso la relazione .<avere lo stesso numero di elementi~>...





                             3 23 4


... all 'insieme quoziente dei numen.

 Ci fermiamo qui, nella speranza di aver sufficientemente giusti-
ficato l'importanza, in matematica, dello studio delle relazioni
(e, in particolare, delle relazioni d'ordine e delle relazioni di equi-
valenza), pur apparentemente cos lontane dalle problematiche
di questa materia.

 Ci resta solo il compito di effettuare la ormai consueta breve ri-
capitolazione di fine paragrafo:

 a. Le relazioni d'ordine e le relazioni di equivalenza sono solo
una piccola parte di tutte le possibili relazioni.
 b. Le relazioni d'ordine e le relazioni di equivalenza produco-
no, rispettivamente, ordinamenti e ripartizioni in classi, cio due
modalit eminentemente matematiche per strutturare insiemi
che costituiscono importanti strumenti di organizzazione delle
conoscenze.
 c. Le relazioni d'ordine sono importanti in ambito matemati-
co; in particolare, per quanto riguarda gli insiemi numerici, sia-
mo abituati a pensarli come insiemi ordinati; ora, per, pos-
siamo divertirci anche a inventare nuovi e vari ordinamenti di que-
sti insiemi a partire da relazioni d'ordine diverse da quelle con-
suete.
 d. Le relazioni di equivalenza sono importantissime in ambito
matematico perch consentono il passaggio da un insieme di
partenza all'insieme delle sue classi (insieme quoziente).
 e. Il passaggio da un insieme all'insieme quoziente corrisponde
ad un meccanismo di progressiva astrazione che  alla base della
matematica: ad esempio, ciascuna direzione nel piano  l'astrat-
to di tutte le rette parallele che hanno quella direzione; e, anco-
ra, ciascun numero  l'astratto di tutti i raggruppamenti di og-
getti concreti che hanno quel numero di elementi.


1.5. Corrispondenzeperfette tra elementi di due insiemi

 Sulle relazioni all'interno di un insieme si potrebbe parlare
ancora a lungo. Ma ci basta che il lettore si sia convinto del ca-
rattere fondante delle nozioni incontrate: non solo ordina-
menti e ripartizioni sono strumenti fondamentali di organizza-
zione del sapere, ma l'intero edificio della matematica con i nu-
meri poggia sulla considerazione di relazioni privilegiate di que-
sto tipO.
 Avendo scoperto che  interessante e utile considerare i collega-
menti tra elementi all'interno di un singolo insieme,  logico e
naturale - a questo punto - provare a vedere cosa succede colle-
gando elementi appartenenti ad insiemi diversi. E il lettore ci
scuser se utilizzeremo, per illustrare efficacemente la situa-
zione, un linguaggio un po' immaginifico, raccontando una storia
che parla di arcieri che scoccano frecce e di bersagli colpiti. Nien-
te a che vedere, owiamente, con cowboy e pellerossa, ma sempli-
cemente un modo efficace per descrivere i collegamenti tra ele-
menti di due insiemi.
 Immaginiamo, dunque, un insieme A di arcieri e un insieme B
di bersagli. La situazione pi semplice che si pu presentare  que-
sta: (a) ogni arciere lancia esattamente una freccia; (b) ogni ber-
saglio viene colpito esattamente da una freccia.
 Le condizioni a e b riassumono sinteticamente quattro vincoli:

 - non ci sono arcieri sfaticati
 - non ci sono arcieri super-lavoratori
 - non ci sono bersagli disoccupati
 - non ci sono bersagli super-colpiti

e dalle due condizioni (owero dai quattro vincoli) consegue un
fatto fondamentale: i bersagli sono tanti quanti gli arcieri.
 E il caso della corrispondenza perfetta tra due insiemi, che
viene detta corrispondenza biunivoca. In una corrispondenza
biunivoca tra l'insieme A e l'insieme B ad ogni elemento di A corri-
sponde uno e un solo elemento di B (da ogni arciere parte esatta-
mente una freccia) e, viceversa, ogni elemento di B  il corrispon-
dente di uno e un solo elemento di A (ad ogni bersaglio arriva esat-
tamente una freccia).


   Toscana -                 Firenze

    Marche -                 Ancona

    Umbria -                 Perugia

        l~zio



Insierne deUe regioni del-  Insierne dei ca~i di
l'ltalia centrale           reg~one deU'ltalia centn71e

 Per apprezzare la nozione di corrispondenza biunivoca, biso-
gna aver chiaro che le corrispondenze biunivoche sono eccezioni
in un mare di corrispondenze che biunivoche non sono (proprio
come accadeva alle relazioni d'ordine e alle relazioni di equiva-
lenza nel mucchio delle possibili relazioni). Spesso ci sono arcieri
sfaticati o super-lavoratori; e altrettanto spesso ci sono bersagli
disoccupati o super-colpiti. Ed  sufficiente che si verifichi una di
queste quattro eventualit perch non si possa pi parlare di cor-
rispondenza biunivoca.
 Un esempio di corrispondenza particolarmente infelice  quel-
la tra l'insieme dei ragazzi che abitano in via delle Biade 14 e l'in-
sieme dei partecipanti al prossimo festival di Sanremo (ogni gio-
vane  un potenziale arciere che scocca frecce verso tutti i can-
tanti che ama):


     Paolo -

     Silvia 
     Aldo --
     L.i~a -
     Carla  '


Insieme dei giovani

; Margheritello

~I  Ignacio Da Silva
 Nadia Raglio

 Silvesbo

 Stonab~cci

 Laura Stecca

 _

Insieme dei cantanti

 In effetti il mondo  vario: Paolo ha gusti precisi, Silvia adora
quasi tutti i cantanti (tranne il romantico Ignacio Da Silva e la
promettente Laura Stecca), Aldo non sopporta la musica leg-
gera, e cos via. E, guardando le cose dal punto di vista dei
partecipanti alla rassegna canora, Margheritello, per motivi a
noi misteriosi, gode di grande popolarit, mentre, all'estremo
opposto, la povera Laura Stecca non ha nessun fan (almeno
tra la popolazione giovanile di via delle Biade 14). La corri-
spondenza che ne risulta non soddisfa neanche uno dei quat-
tro requisiti necessari per essere definita biunivoca: ci sono ar-
cieri sfaticati (Aldo) e super-lavoratori (Silvia), bersagli che re-
stano intatti (Laura Stecca) e bersagli super-colpiti (Margheri-
tello).
 Altre volte la corrispondenza si colloca a livelli intermedi tra
la perfezione della corrispondenza biunivoca e la disastrosi-
t di corrispondenze come quella ragazzi-cantanti: I'abbia-
mo gi detto, che ci piaccia o no il colore predominante  il gri-
giO...
 Esaminiamo dunque alcune corrispondenze, e, per ciascuna di
esse, determiniamo se si tratta di corrispondenze biunivoche e,
nel caso non sia cos, quale (quali) dei vincoli previsti non risulti
rispettato:

 A = insieme delle persone; B = insieme delle lettere dell'alfabe-
to; la corrispondenza associa ad ogni persona la lettera iniziale
del suo nome. Non  una corrispondenza biunivoca, poich a
Carlo e Carmine, ad esempio, corrisponde la lettera C (bersaglio
super-colpito); le altre tre condizioni sono invece tutte rispet-
tate.
 A = insieme delle note musicali; B = insieme dei numeri da 1 a 7;
la corrispondenza associa ad ogni nota la sua posizione nella sca-
la. E una corrispondenza biunivoca (ogni nota ha uno e un solo
numero corrispondente e viceversa).
 A = insieme delle automobili; B = insieme dei proprietari di auto-
mobili; la corrispondenza associa ad ogni automobile il suo (o i
suoi) proprietari. Non  una corrispondenza biunivoca perch ci
sono automobili che hanno pi di un proprietario (e quindi ci
sono arcieri super-lavoratori che scoccano pi di una freccia) e ci
sono proprietari che hanno pi di un'automobile (e quindi ci
sono bersagli super-colpiti, corrispondenti a pi automobili). Le
altre due condizioni, invece, sono verificate.
 A = insieme delle regioni; B = insieme dei capoluoghi di regione~;
la corrispondenza associa ad ogni regione il suo capoluogo. E
una corrispondenza biunivoca (ogni regione ha uno e un solo ca-
poluogo che gli corrisponde e viceversa).

 Potremmo fermarci qui, se non fosse per una legittima curiosit
che qualche lettore potrebbe nutrire: nel caso in cui l'insieme di
partenza A e l'insieme d'arrivo B coincidano, quali sono le pa-
rentele tra la nozione di relazione e la nozione di corrispon-
denza? (Infatti, in questo caso, i collegamenti si giocano tutti
all'interno dello stesso insieme, come quando parlavamo di
relazioni). Ebbene, nel caso in cui l'insieme di partenza e l'in-
sieme di arrivo delle frecce coincidano, le corrispondenze non
sono nient'altro che delle relazioni. Pensiamo ad esempio al
caso in cui abbiamo A = B = insieme delle persone, e la corri-
spondenza  quella che collega ad una persona il suo coniuge;
essa coincide, owiamente, con la relazione essere coniuge
di. Dunque le nozioni di relazione e di corrispondenza sono
strettamente connesse: la relazione  il caso particolare di cor-
rispondenza in cui gli insiemi di partenza e di arrivo coincidono.
In definitiva, quando siamo davanti a connessioni tra elementi di
un unico insieme,  nelle nostre mani la scelta se guardare ad
esse come ad una relazione o come ad una corrispondenza: se
l'obiettivo  quello di strutturare l'insieme (per esempio ordi-
nando i numeri naturali) privilegeremo un'ottica relazionale; se
l'obiettivo  quello di evidenziare il rapporto che lega gli elemen-
ti di un insieme ad altri elementi dello stesso insieme (per esem-
pio associando ad ogni punto del piano il suo trasformato dopo
un movimento rotatorio) assumeremo il punto di vista delle cor-
rispondenze.

Breve ricapitolazione finale:

 a. Una corrispondenza tra gli insiemi A e B  un insieme di col-
legamenti tra elementi di A e elementi di B (tali collegamenti si
possono rappresentare attraverso frecce).
 b. Una corrispondenza si dice biunivoca se ogni elemento di A
ha esattamente un elemento corrispondente in B, e, viceversa
ogni elemento di B  il corrispondente di esattamente un elemen-
to diA (da ogni elemento di A parte una e una sola freccia, ad ogni
elemento di B arriva una e una sola freccia).


1.6. Comspondenze e confron~i tra insiemi infiniti

 Si ripropone il solito problema: perch sono importanti - dal
punto di vista matematico - le corrispondenze? Un primo moti-
vo ce lo fornisce la considerazione di quelle particolari corrispon-
denze che sono le corrispondenze biunivoche: esse permettono
difare confronti tra insiemi rispetto alla loro grandezza.
 La questione merita un chiarimento: se due insiemi sono finiti,
per confrontare la loro grandezza  sufficiente contare il numero
degli elementi dell'uno e dell'altro; in particolare, se uno dei due
insiemi messi a confronto  incluso nell'altro, allora non occorre
neanche far la fatica di contare, giacch ci significa che il primo
 certamente meno numeroso del secondo. In ogni caso - aven-
do a che fare con insiemi finiti - non abbiamo dawero bisogno di
scomodare le corrispondenze biunivoche! Ma se gli insiemi a
c~onfronto sono infiniti, come si fa a stabilire qual  il pi grande?
E evidente che non possiamo metterci a contare; ma - e questo 
meno evidente - non possiamo neanche basarci sul criterio che
uno dei due sia incluso nell'altro per concludere che  meno nu-
meroso...
 Per rendercene conto, prendiamo in considerazione, ad esem-
pio, I'insieme A di tutti i punti di una circonferenza e l'insieme B
di tutti i punti di una retta. Si tratta di due insiemi infiniti (sia la
circonferenza che la retta sono costituite da infiniti punti), di cui
il primo  incluso nel secondo dal momento che una circonferen-
za non  altro che un segmento incurvato e quindi i suoi punti
sono una parte dei punti di una retta.

                                   c)

 La tentazione di affermare - in analogia con quanto si farebbe
avendo di fronte insiemi finiti - che la circonferenza, in quanto
parte della retta,  costituita da un'infinit di punti meno nu-
merosa rispetto all'infinit dei punti della retta, entra in con-
traddizione con il fatto che esiste una corrispondenza perfetta
- quella che abbiamo chiamato una corrispondenza biunivoca -
tra i punti della circonferenza e i punti della retta (e quindi, in
quest'ottica,  ragionevole sostenere che i punti della circonfe-
renza sono tanti quanti i punti della retta!).





          p


La corrispondenza che assocua ad ogni punto P della circonferenza il punto P che  la
sua .<prouezionesulla retta dal punto O  biunivoca: ogni punto della circonferenza ha
uno e un solo corrispondente; e, viceversa, ogni punto della retta  il corrispondente di
uno e un solo punto della circonferenza!

 Dunque, pur essendo la circonferenza opportunamente rad-
drizzata solo una parte della retta,  possibile porre in corri-
spondenza biunivoca i punti della circonferenza con i punti della
retta (il che ci spingerebbe ad affermare che punti della circonfe-
renza e punti della retta sono ugualmente numerosi).
 Si tratta di una situazione paradossale che non pu certo verifi-
carsi se gli insiemi confrontati sono finiti: se un insieme finito A 
parte di un altro insieme finito B, allora A contiene meno ele-
menti di quanti ne contenga B, e quindi  impossibile che una
qualsiasi corrispondenza tra A e B sia biunivoca perch necessa-
riamente qualche elemento di B non sarebbe corrispondente di
alcun elemento di A. Ma nel caso infinito, in cui possono coesiste-
re inclusione e corrispondenza biunivoca, dobbiamo decidere qua-
le delle due circostanze privilegiare nel confronto tra le grandez-
ze degli insiemi. Un grande matematico vissuto a cavallo tra Otto-
cento e Novecento, Georg Cantor, ha proposto di scegliere la
nozione di corrispondenza biunivoca come chiave universale per
il confronto tra le grandezze di insiemi, siano essi finiti o infiniti:
due insiemi A e B si devono considerare ugualmente grandi (il
termine tecnico  equipotenti) se  possibile porli in corrispon-
denza biunivoca.
 La proposta di Cantor funziona a condizione di non farsi distrar-
re dal fatto che uno dei due insiemi possa essere incluso nel-
I'altro. Il collegamento tra inclusione e minore numerosit esi-
ste tra insiemi finiti; smette di essere valido se gli insiemi messi a
confronto sono infiniti. E ragionevole - sostiene Cantor - accet-
tare di fare questa distinzione tra il caso finito (dove se A  parte
di B, allora A  meno numeroso di B) e il caso infinito (dove pu
succedere che A sia parte di B, e contemporaneamente, A e B sia-
no ugualmente numerosi), pur di avere un criterio universale
di confronto tra insiemi, il criterio basato sull'esistenza di una
corrispondenza biunivoca, che stabilisca inequivocabilmente l'e-
quipotenza, owero l'uguale numerosit, tra due insiemi.
 La scelta della corrispondenza biunivoca come evidenziatore
dell'equipotenza si rivela proficua: una volta posta in questi ter-
mini la questione, Cantor riesce a stabilire una gerarchia (ricca
di sorprese, ma perfettamente coerente) tra insiemi infiniti. Ecco
quindi la dimostrazione inconfutabile che i numeri interi (pur es-
sendo nient'altro che casi particolarissimi di frazioni, esattamen-
te quelle frazioni in cui il numeratore  un multiplo del denomi-
natore, come ad esempio 10/2 o 9/3) sono tanti quante sono le
frazioni! Ed ecco la dimostrazione - pi prevedibile, ma a questo
punto estremamente opportuna per evidenziare che non tutti gli
insiemi infiniti sono equipotenti - che i numeri interi sono per
meno numerosi dei numeri decimali illimitati (con infinite ci-
fre dopo la virgola).
 Il punto di vista di Cantor consente di fare un salto di qualit ri-
spetto all'impotenza che - sul tema del confronto tra grandez-
ze di insiemi infiniti - aveva paralizzato anche i pi grandi pen-
satori. Lo stesso Galileo, nei suoi Discorsi e dimostrazioni mate-
matiche intomo a due nuove scienze, avendo compreso che il con-
fronto tra insiemi infiniti dava luogo a situazioni paradossali,
concludeva in modo rinunciatario: Queste son di quelle diffi-
colt che derivano dal discorrer che noi facciamo col nostro in-
telletto finito intorno a gl'infiniti, dandogli quelli attributi che
noi diamo alle cose finite e terminate; il che penso che sia incon-
veniente, perch stimo che questi attributi di maggioranza, mi-
norit ed egualit non convenghino a gl'infiniti, de i quali non si
pu dire, uno esser maggiore o minore o eguale all'altro. Per
evitare di cadere in contraddizioni - diceva dunque Galilei - 
opportuno evitare di applicare ad insiemi infiniti i concetti e le
tecniche che si usano per gli insiemi finiti; in particolare occorre
rinunciare all'idea di poter confrontare insiemi infiniti. Questo
punto di vista - presentato da Galilei con tanta efficacia -  stato
assunto e condiviso fino al termine del secolo scorso. La mate-
matica moderna - anche grazie alla nozione di corrispondenza
biunivoca - azzarda di pi: vale la pena di sottolinearlo, giacch
capita raramente di sorpassare uno come Galileo Galilei in fatto
di ardimento intellettuale!

 Bene, possiamo ormai procedere, senza ulteriori esitazioni, alla
tradizionale ricapitolazione di fine paragrafo:

 a. Il confronto tra insiemi (dal punto di vista della loro gran-
dezza), facile per gli ipsiemi finiti, si presenta piuttosto proble-
matico per gli insiemi infiniti.
 b. Il fatto che un insieme sia parte di un altro - decisivo nel caso
di confronto tra insiemi finiti per stabilire che il primo  meno
grande del secondo - non risulta essere un criterio deter-
minante nel caso di insiemi infiniti.
 c. Il criterio che si usa per confrontare insiemi infiniti (in parti-
colare per decidere che due insiemi sono equipotenti, e cio
ugualmente grandi)  quello della possibilit di porli in corri-
spondenza biunivoca.
 d. Con questa tecnica Georg Cantor dimostra, ad esempio, che
gli interi sono tanti quante sono le frazioni, ma meno dei decimali
illimitati.


1.7. La teoria degli insiemi

 Le nozioni di relazione e corrispondenza si collocano all'inter-
no di quello che si potrebbe definire il capitolo zero della ma-
tematica, la premessa e il fondamento dell'intera costruzione: la
teoria degli insiemi.
 Ci non significa che lo sviluppo della matematica sia comincia-
to solo nel momento in cui  stata messa a punto un'adeguata
teoria degli insiemi (opera, essenzialmente, del gi citato Georg
Cantor): la storia della scienza non  un cammino lineare, in cui
vengono elaborati in sequenza, ordinatamente e sistematicamen-
te, i vari segmenti e le varie tappe. Lo studio delle possibili ca-
ratteristiche e propriet di insiemi di natura qualsiasi, che dal
punto di vista logico precede l'analisi delle caratteristiche e pro-
priet di singoli insiemi (quali, ad esempio, I'insieme dei numeri
naturali o l'insieme delle figure del piano) si sviluppa, in realt,
solo agli albori del Novecento, come coronamento e sistemazio-
ne di un lungo lavorio su insiemi particolari. Ma quando l'atten-
zione si sposta dai singoli insiemi, in qualche misura concreti, al-
I'insieme pi astratto che tutti li rappresenta, ecco che il nuovo
punto di vista - aiutandoci a cogliere analogie e a stabilire colle-
gamenti - consente di pervenire ad una teoria pi generale, che
riordina e riorganizza le conoscenze precedenti: la fondazione di
una teoria generale degli insiemi ci fornisce un linguaggio e alcu-
ni concetti chiave che risultano preziosi per gettare luce sulle
particolari teorie matematiche, relative a particolari insiemi (di
numeri, di figure, ecc.).
 Dunque in principio c' l'insieme, di natura imprecisata, che si
presenta, in un primo momento, privo di ogni e qualsiasi struttu-
ra; il passaggio successivo consiste appunto nel dare una struttura
di qualche tipo a questo generico insieme che ci serve da modello
per i nostri ragionamenti. Ed  di questo passaggio - legato al
nome di Geog Cantor e fondamentale nella moderna teoria de-
gli insiemi - che ci siamo occupati nelle pagine precedenti.
 Infatti, dare una struttura ad un insieme significa in primo luo-
go - lo abbiamo visto - considerare delle relazioni su di esso; or-
mai sappiamo che se caliamo sull'insieme oggetto delle nostre
attenzioni quel determinato tipo di relazione che abbiamo chia-
mato relazione d'ordine, l'insieme acquister una precisa forma,
presentandosi ai nostri occhi ben ordinato; mentre un altro tipo
di relazione, che abbiamo definito relazione di equivalenza, pro-
durr una strutturazione dell'insieme in termini di suddivisione
in classi dei suoi elementi.
 Non abbiamo detto, invece, che esiste un altro modo per dare
una struttura ad un insieme: l'insieme prende una forma pi d-
finita nel momento in cui consideriamo delle operazioni che
coinvolgono i suoi elementi. Anche cos si tendono fili, si stabili-
scono collegamenti, si attribuisce una ben determinata struttura
all'insieme considerato. Ma- ecco un motivo di grande soddisfa-
zione per noi - le operazioni, a pensarci bene, non sono nient'altro
che particolari corrispondenze. Per mostrare la fondatezza di que-
sta affermazione  conveniente ragionare su un esempio speci-
fico. Prendiamo dunque in esame l'operazione di addizione nel-
l'insieme dei numeri naturali: noi sappiamo che 3+6=9, che
7+5=12, e cos via. Ebbene, ci equivale a dire che esiste una
corrispondenza tra l'insieme delle coppie di numeri e l'insieme dei
numeri che fa corrispondere alla coppia (3,6) il numero 9, alla
coppia (7,5) il numero 12, e cos via.

   9




. 12


Insieme dei numeti na-
tutali

 Un'operazione  quindi una corrispondenza tale che ad ogni ar-
ciere  associato un unico bersaglio (il~che non esclude che pi ar-
cieri possano colpire lo stesso disgrazito bersaglio!).
 Possiamo allora affermare, con legittimo orgoglio, di non aver
trascurato niente di essenziale in fatto di strutturazione di insie-
mi; l'apparente lacuna (il non aver menzionato le operazioni) 
ampiamente giustificata dal desiderio di fornirci di uno strumen-
to (la nozione di corrispondenza) ben pi generale e potente.
 Dunque, in principio c' l'insieme; e subito dopo c' l'insieme
strutturato - ormai possiamo dirlo - attraverso la considerazione
delle relazioni e di quelle particolari corrispondenze che sono le
operazioni. Ecco le basi della teoria degli insiemi, la teoria che
attraverso lo studio delle propriet generali degli insiemi struttu-
rati si pone a fondamento della matematica moderna.

 Ricapitolando:

 a. La teoria degli insiemi, pur elaborata tardivamente (solo tra
la fine dell'Ottocento e l'inizio del Novecento), costituisce l'in-
troduzione naturale e necessaria alla conoscenza matematica.
 b. La teoria degli insiemi studia in generale, lavorando su in-
siemi indeterminati e astratti, tutte le caratteristiche e le proprie-
t che i singoli insiemi concreti possono avere o non avere.
 c. La teoria degli insiemi parte dalla considerazione di insiemi
 privi di struttura per passare poi all'esame di insiemi strutturati.
 d. Gli insiemi possono essere forniti di struttura attraverso rela-
 zioni e operazioni (le operazioni sono particolari corrisponden-
 ze)
2. La logica matematica





2.1. Sottoinsiemi e predicati

 Iniziamo con una nota scherzosa l'impegnativo cammino che
ha l'obiettivo di mostrare l'essenziale rapporto che lega tra loro
matematica e logica.
 Immaginiamo dunque che una fortunata ed efficace campagna
pubblicitaria abbia convinto molti italiani ad acquistare un'elegante
enciclopedia (in 24 volumi) sulla storia della cravatta. E imma-
giniamo che tra gli acquirenti dell'enciclopedia ci sia Amedeo
Astanti, alto un metro e novantaquattro, magro come un grissino
innamorato delle donne brune e delle passeggiate in montagna, e ci
sia anche Bartolo Bonucci, alto un metro e sessantadue, piuttosto
rotondetto, amante delle bionde e sofferente di vertigini Insomma
Amedeo e Bartolo sono certo diversi, anzi diversissimi, tra loro; ep-
pure li unisce la stessa curiosit per la storia della cravatta, curiosit
che si concretizza nel possesso dell'originale enciclopedia.
 Bene, una carattercstica relativa ad alcuni elementi di un insieme
si dice - nel linguaggio della logica matematica - un predicato; e
si dice che un elemento dell'insieme che possiede la caratteri-
stica richiesta soddisfa il predicato. Dunque la nostra storia pu
essere raccontata cos: nell'insieme I dei cittadini italiani, Ame-
deo e Bartolo soddisfano il predicato essere in possesso dell'en-
ciclopedia sulla storia della cravatta. Ma c' un altro modo equi-
valente di descrivere la situazione: possiamo dire anche che nel-
l'insieme I dei cittadini italiani esiste un sottoinsieme E formato
da coloro che hanno acquistato l'enciclopedia, sottoinsieme a cui
Amedeo e Bartolo hanno il privilegio di appartenere.
 Quale insegnamento si pu trarre da questa vicenda? Il fatto
che esiste un forte collegamento tra la nozione di predicato defi-
nito su un insieme e la nozione di sottoinsieme di un insieme. Ov-
vero: dato un insieme I (formato dai cittadini italiani), un pre-
dicato (essere in possesso dell'enciclopedia) definito su I indi-
vidua un sottoinsieme E (formato dai possessori dell'enciclo-
pedia) dell'insieme di partenza I; e, viceversa, la scelta di un

sottoinsieme di I (il sottoinsieme E dei possessori dell'enciclope-
dia) rimanda ad un predicato definito su I (il predicato essere in
possesso dell'enciclopedia).
Qualche ulteriore esempio getta maggiore luce sulla vicenda:

 - nell'insieme dei teleutenti, il predicato amare Mike Bongior-
no individua il sottoinsieme formato dai Mike-dipendenti;
 - nell'insieme formato da Aldo, Bruno, Carla, Daniela, Ester,
Francesca e Giulio, il predicato essere di sesso femminile indivi-
dua il sottoinsieme formato da Carla, Daniela, Ester e Francesca;
 - nell'insieme delle regioni italiane, il predicato non essere ba-
gnata dal mare individua il sottoinsieme formato da Valle d'Ao-
sta, Piemonte, Lombardia, Trentino Alto Adige e Umbria;
 - nell'insieme dei poligoni, il predicato avere tre lati individua
il sottoinsieme dei triangoli;

e vlceversa:

 - nell'insieme dei teleutenti, il sottoinsieme formato dagli abbo-
nati rimanda al predicato essere in regola con l'abbonamento;
 - nell'insieme formato da Aldo, Bruno, Carla, Daniela, Ester,
Francesca e Giulio, il sottoinsieme formato da Bruno, Carla e Ester
rimanda al predicato avere il nome composto di 5 lettere;
 - nell'insieme delle regioni italiane, il sottoinsieme formato da
Sardegna e Sicilia rimanda al predicato essere un'isola;
 - nell'insieme dei poligoni, il sottoinsieme dei rettangoli riman-
da al predicato avere quattro lati e avere gli angoli uguali.


                Bruno /\ B
                           Carla \


   , Daniela

    \ A   G
\/                 `           '

I sottoinslemA e B rimandano, nispettivamente, ai predicati.essere di sesso femmini-
le e .<avere il nome di 5 lettere.

 Insomma, abbiamo scoperto che definire un predicato o indivi-
duare un sottoinsieme sono due operazioni sostanzialmente equi-
valenti, e quindi la differenza tra parlare di predicati definiti su
un insieme e parlare di sottoinsiemi di un insieme sembra consi-
stere essenzialmente in una questione di linguaggio. Occorre
per precisare che il collegamento tra predicati e sottoinsiemi 
univoco, cio perfettamente determinato, solo in un senso: vale a
dire che mentre un predicato individua uno e un solo sottoinsieme
corrispondente (quello formato dagli elementi dell'insieme che
soddisfano quel predicato), la scelta di un sottoinsieme rimanda
ad un predicato in modo molto meno preciso e stringente. Ad
esempio, nell'insieme delle regioni italiane, il sottoinsieme for-
mato da Sardegna e Sicilia rimanda altrettanto legittimamente
al predicato essere un'isola come al predicato avere il nome
che comincia con la lettera S.
 Per il momento ci fermiamo qui, pur consapevoli della spro-
porzione tra l'obiettivo di partenza (illustrare il rapporto che
lega tra loro la matematica e la logica) e quanto siamo riusciti a
fare (mostrare che c' un nesso forte tra la nozione di sottoin-
- sieme, tipicamente matematica - anche se della matematica sen-
  za numeri ! -, e la nozione d i predicato, appartenente a pieno tito-
  lo al misterioso universo della logica).

 Dunque abbiamo fatto solo un primo piccolo passo, ma ritenia-
mo che sia opportuno procedere comunque ad una breve ricapi-
tolazione:

 a. Dato un insieme I, un predicato individua un sottoinsieme
(quello formato dagli elementi dell'insieme che soddisfano il
predicato). Ad esempio, nell'insieme dei numeri interi positivi, il
predicato essere pari individua il sottoinsieme contenente i
numeri 2, 4, 6, ecc.
 b. Viceversa, dato un insieme ambiente I, un suo sottoinsieme
rimanda ad un predicato (quello che  soddisfatto da tutti e soli
gli elementi del sottoinsieme). Ad esempio, nell'insieme degli in-
teri positivi pari, il sottoinsieme formato dai numeri 12,14,16,
ecc. rimanda al predicato essere maggiore di 10.
 c. Mentre un predicato individua perfettamente, in modo uni-
  voco, un sottoinsieme dell'insieme ambiente, la scelta di un sot-
  toinsieme non comporta in modo automatico e univoco l'indivi-
  duazione del predicato corrispondente.


  2.2. Dai predicati alle proposizioni atomiche

 Ci sono frasi poetiche, suggestive, commoventi, elaborate (del
tipO: Ginevra rimembr le agognatestanze) e ci sono frasi prosaiche
ebanali(comeadesempio:Irigatonisonoscotti).Dalpuntodivi-
sta della logica, per, esse hanno pari dignit; quell~o che conta 
stabilire - per ciascuna frase - se sia vera o falsa. E il problema
della valutazione della verit, a prima vista semplice e privo di in-
teresse, ma in realt - lo vedremo subito - complesso e ricco di
spunti di riflessione.
 Intanto cominciamo col dire che non tutte le frasi si prestano al
gioco del vero o falso. Ad esempio, Viva l'Italia!  una frase che
testimonia un encomiabile patriottismo; non  per, dispiace dir-
lo, n vera n falsa. E cos, Stai dormendo?  una domanda che
lascia intrawedere una affettuosa (anche se contraddittoria)
sollecitudine; non  per, in quanto domanda, n vera n falsa,
sia che il destinatario stesse dormendo, sia che fosse gi sveglio.
Anche nel linguaggio della matematica troviamo frasi di cui non
ha senso chiedersi se siano vere o false: Addiziona 5 e 3 , alla fin
fine, la richiesta di effettuare una determinata prestazione; si pu
esaudirla o non esaudirla, ma, proprio in quanto  una richiesta,
non  in ogni caso n vera n falsa.
 Dunque, una prima scoperta  quella che non tutte le frasi do-
tate di senso si prestano al gioco del vero o falso: le frasi accet-
tabili per tale gioco sono solo quelle che asseriscono un fatto, vero
o falso che sia; tali frasi vengono dette proposizioni. Il nostro pri-
mo risultato  quindi l'aver individuato, nell'insieme di tutte le
frasi, il sottoinsieme delle proposizioni, e cio il sottoinsieme nel
cui ambito  significativo ilproblema della valutazione della verit.
 Ma allora sorge naturale la domanda: come  fatta una propo-
sizione, owero qual , in generale, la sua struttura? Cominciamo
con l'osservare che le proposizioni pi semplici, vere o false che
siano, sono sempre del tipo: l'oggetto a soddisfa ilpredicato P. Ad
esempio, La Sardegna  un 'isola, Aldo ha un nome di 4 lettere, op-
pure Pescasseroli  la capitale d'Italia, Dante Alighieri  un noto
cantautore, dove gli oggetti coinvolti sono, di volta in volta, la
Sardegna, Aldo, Pescasseroli e Dante Alighieri, mentre i predicati
coinvolti sono, rispettivamente, essere un'isola, avere un
nome di 4 lettere, essere la capitale d'Italia ed essere un noto
cantautore. I predicati, quindi, costituiscono un materiale
fondamentale per costruire frasi; a questo scopo sono stati intro-
dotti, per questo motivo abbiamo dedicato loro un intero para-
grafo. Ora sappiamo che essi intervengono in modo essenziale
nella struttura delle proposizioni pi elementari, che hanno ap-
punto la forma oggetto soddisfa predicato, e che diremo proposi-
zioni atomiche.
 L'idea che viene spontanea  quella di limitare, inizialmente, il
gioco del vero o falso alle proposizioni atomiche; almeno per esse
la valutazione di verit dovrebbe risultare facile. Purtroppo non
 cos: in primo luogo, la valutazione della verit o meno di una
proposizione atomica  tutt'altro che semplice, risultando, in ge-
nerale, pi complessa e compromettente di quanto potrebbe ap-
parire ad un esame frettoloso e superficiale; e, comunque, non 
la logica ad aiutarci a dirimere dubbi e incertezze
 Vediamo come si presenta la questione partendo da un paio di
esempi. Leonardo nella sua vita ha dipinto 12 quadri: vero o falso?
Basta consultare un libro di storia dell'arte per rispondere con
sicurezza, eppure... Eppure, se dalla correttezza della risposta ne
andasse della nostra vita, probabilmente prenderemmo una se-
rie di precauzioni: il Leonardo di cui si parla  proprio Leonardo
da Vinci, quello della Gioconda? Gli affreschi vanno calcolati tra
i quadri o no? E cos via... Ecco che una frase apparentemente in-
nocua si rivela ambigua e piena di insidie! Ancora: una frase
come n 3  il successore immediato del 2  vera o falsa? La risposta
corretta : dipende dall'insieme numerico su cui ragioniamo; in-
fatti se consideriamo solo gli interi l'affermazione  sacrosanta,
mentre, se consideriamo anche i decimali, ci sono infiniti numeri
in mezzo tra 2 e 3!
 La conclusione  che la possibilit di dare una valutazione di ve-
rit assoluta e sieura di una proposizione atomica dipende spes-
so dall'interpretazione dei termini coinvolti e dal contesto al cui
interno si opera. E, d'altra parte, il processo di accertamento del-
la verit non risulta avere a che fare con la logica: nei due esempi
considerati, esso riguarda, rispettivamente, la sfera della storia
dell'arte e quella della teoria dei numeri. Compito della logica,
dunque, non , e non pu essere, quello di stabilire la verit o fal-
sit di proposizioni atomiche; questa amara constatazione ci
spinge a spostare ilproblema della valutazione della verit a livello
di proposizioni non atomiche: forse in quell'ambito sar possibi-
le conseguire qualche risultato significativo...

 E giunto di nuovo il momento di ricapitolare brevemente:

 a. Esistono frasi del tipo vero o falso (ad esempio Milano si trova
in Lombardia, 5  un numero pari, ecc.) e frasi che non rientrano
in questo tipo (ad esempio Fai il bravo, Sogno o son desto?, ecc).
Le frasi del tipo vero o falso si dicono proposizioni.
 b. Le proposizioni pi semplici sono quelle della forma l'og-
getto a soddisfa il predicato P (ad esempio Platone  un calciato-
re, Giuliano  molto bello, ecc.). Esse si dicono proposizioni atomi-

 c La possibilit di dare una valutazione di verit assoluta di una
proposizione atomica dipende spesso dall'interpretazione dei ter-
mini coinvolti e dal contesto al cui interno si opera, e, comunque,
non ha a che fare con la logica.


2.3. Dalle proposizioni atomiche alle proposizioni non
     atomiche

 La definizione di proposizione atomica non va presa in senso
restrittivo; ad esempio facciamo rientrare tra le proposizioni
atomiche anche frasi del tipo Franco e Roberto sono fratelli. In
questo caso il predieato (essere fratelli) si riferisce necessa-
riamente a due oggetti (la frase Franco  fratello non ha alcun
senso se non si specifica qual  l'altro oggetto coinvolto nella
.vicenda); si tratta quindi di un tipo di predieato diverso rispetto a
quelli finora esaminati: non  mono-argomentale (eio non fa ri-
ferimento ad una caratteristica di singoli oggetti), bens bi-ar-
gomentale (cio fa riferimento ad una caratteristica di coppie di
oggetti). Altri esempi di predicati bi-argomentali sono essere
perpendicolari se stiamo parlando di rette, avere lo stesso nu-
mero di cifre se stiamo parlando di numeri, e cos via. Ebbene,
la frase Franco e Roberto sono fratelli  certamente una proposi-
zione (infatti  vera o falsa); e nulla ci proibisce di considerarla
atomica, giacch essa - nella sostanza - rientra nello schema og-
getto soddisfa predicato (anche se, in questo caso, sarebbe pi pre-
ciso dire oggetti soddisfano predicato).
 Ma - anche con queste estensioni della nozione di predicato, e
quindi della nozione di proposizione atomica - sarebbe dawero
riduttivo pensare che le uniche proposizioni, cio le uniche frasi
adatte al gioco del vero o falso (che, oltretutto, si rivela per loro
poco fecondo!), siano quelle atomiche. Sono le pi semplici, ma
non le uniche e basta qualche esempio per rendersene conto:

 Tutte le ciambelle riescono col buco. In questo caso il predicato
(riuscire col buco)  facilmente individuabile e persino mono-
argomentale, ma la frase non predica rispetto ad un singolo
oggetto, ma rispetto a tutti gli individui di una comunit (la
mai abbastanza lodata comunit delle ciambelle). Conclusione:
Tutte le ciambelle riescono col buco  una proposizione (infatti 
una frase falsa, come sanno anche i pi sproweduti), ma non
rientra nello schema oggetto soddisfa predicato, poich la sua ve-
rit o falsit non dipende dal comportamento di un singolo spe-
cifico oggetto, bens dal comportamento di un'intera colletti-
vit.
 Nell 'aula c' qualcuno che  addormentato. In questo caso il pre-
dicato (essere addormentato)  di nuovo immediatamente in-
dividuabile e, per di pi, monoargomentale, ma la frase afferma
l'esistenza di un oggetto che lo soddisfa, senza specificare di chi
esattamente si stia parlando.
 Conclusione: Nell'aula c' qualcuno che  addorrnentato  una
proposizione (infatti  una frase vera o falsa), ma la sua verit o
falsit non dipende dal comportamento di un determinato e parti-
colare oggetto, ma dall'esistenza o meno di un qualche indivi-
duo (si chiami Pierino o Genoveffa) che soddisfi il predicato coin-
volto.

 Si potrebbe continuare a lungo; ci sembra, per, che il punto sia
stato sufficientemente chiarito: non tutte le proposizioni (cio le
frasi che sono vere o false) rientrano nel semplice schema oggetto
soddisfa predicato, e dunque non tutte le proposizioni sono ato-
miche.
 C', per, un tipo di proposizione non atomica che merita qual-
che ulteriore parola di commento. Consideriamo la frase Rober-
to Baggio  nato a mezogiorno e in aprile. Essa proviene dalla
composizione delle due frasi Roberto Baggio  nato a mezzogiomo
e Roberto Baggio  nato in aprile - ciascuna del tipo oggetto soddi-
sfa predicato - connesse attraverso la parolina e (che viene de-
finita, appunto, connettivo).
 La frase Roberto Baggio  nato a mezzogiomo e in aprile  certa-
mente una proposizione (infatti  una frase vera o falsa, anche se
per poter stabilire la sua verit occorre nutrire una tale passione
per Baggio da aver studiato a fondo la sua biografia), ma non 
una proposizione atomica.
 Il fatto interessante  che, in questo caso,  possibile andare un
po' oltre la semplice constatazione che la frase  vera o falsa. In-
fatti, possiamo proclamare ad alta voce, senza tema di smentita,
che  vera nell'ipotesi che sia vero che Roberto Baggio  nato a
mezzogiorno e che sia anche vero che Roberto Baggio  nato in
aprile;  falsa in ogni altro caso.
 Questa situazione - legata al significato della parolina e - si pu
schematizzare attraverso un'opportuna tabella:

dove A sta per Roberto Baggio  nato a mezzogiomo e B sta per
Roberto Baggio  nato in aprile, mentre v ef stanno rispettivamente
per vero e falso.
 Fermiamoci un momento a riflettere: per la prima volta riuscia-
mo a dire qualcosa di certo sulla verit di una frase (finora aveva-
mo potuto affermare, al massimo, che si trattava di una proposi-
zione, e cio di una frase o vera o falsa, ma avevamo rinviato il
giudizio di verit ad un ambito non logico). Ma questo  stato
possibile a costo di due scelte molto precise:

 1. Abbiamo dovuto spostare la nostra attenzione su una proposi-
zione non atomica, frutto della connessione tra proposizioni pi
semplici; abbiamo con ci implicitamento preso atto che il pro-
blema della valutazione della verit  irrisolubile - con strumenti
puramente logici - per le proposizioni atomiche. Paradossal-
mente:  possibile lavorare su ci che  complesso, ma non su ci
che e semplice.
 2. Abbiamo ridimensionato l'obiettivo: non siamo pi alla ricer-
ca di verit assolute, ma di eventuali verit di frasi complesse in
relazione alla verit o falsit delle frasi componenti ( vero che il
noto calciatore  nato a mezzogiomo e in aprile se  vero che 
nato a mezzogiomo ed  altres vero che  nato in aprile). Le scelte
compiute hanno un'importante conseguenza. A questo punto, il
discorso della verit diventa una specie di gioco formale, in cui
possiamo lasciare da parte ogni preoccupazione di congruenza
tra le frasi che componiamo: dal punto di vista dell'utilizzo della
tabella del connettivo e - e quindi della valutazione della verit
di una frase composta del tipo A e B - la proposizione Evaristo
Bottiglioni  astemio e il triangolo T equilatero va altrettanto bene
della frase precedente: anche in questo caso essa  vera se e solo
se Evaristo - nonostante il suo cognome! - odia gli alcolici ed  al-
tres vero che il triangolo T ha i lati di identica lunghezza .

 Possiamo ora riprendere il nostro cammino. Avevamo osserva-
to che la tabella considerata si rivela adeguata per lo studio della
verit o falsit di proposizioni complesse, ottenute dalla con-
nessione - attraverso la parolina e - di proposizioni pi semplici
(non necessariamente atomiche). E chiaro che qualcosa di ana-
logo si pu escogitare per altre paroline che fungono da connet-
tivi tra proposizioni.
 Vediamo, ad esempio, cosa si pu fare rispetto alla parolina o.
In questo caso occorre, in primo luogo, mettersi d'accordo sul si-
gnificato che attribuiamo al connettivo o, dato che nella nostra
lingua esso presenta qualche ambiguit: i logici hanno deciso di
usare questo connettivo nel significato di una doppia possibilit,
         44                     MATEMATICA SENZA NUMERI

e non di una alternativa. Vale a dire: la frase Paolo mangia il ge-
lato o Carmela legge ..I promessi sposi viene assunta come vera
non solo quando si verifichi una delle due cose, ma anche nel
caso si verifichino entrambe (permettendo a Paolo di soddisfa-
re la sua golosit e a Carmela di soddisfare la sua sete di cultu-
ra)-
 Chiarito questo punto,  del tutto immediato quale debba esse-
re la tabella relativa al connettivo o:





 Vogliamo occuparci ancora di un connettivo, piuttosto eccen-
trico e originale, ma importante, come vedremo tra poco, per
fare dei passi avanti rispetto al problema della valutazione della
verit di una frase. Ci riferiamo al connettivo non, che, in real-
t, non meriterebbe il nome di connettivo, poich non connette
due frasi; lo chiamiamo lo stesso connettivo, per, dal momento
che ha in comune con le paroline e e o il fatto di permettere di co-
struire, a partire da frasi pi semplici (nel suo caso: a partire da
una singola frase pi semplice), una frase pi complessa. Infatti
Paolo non mangia il gelato  la frase pi complessa che si ottiene
dalla frase pi semplice Paolo mangia il gelato attraverso il
connettivo non.
 La tabella relativa al nostro nuovo connettivo  del tutto im-
mediata, dal momento che la parolina non inverte il valore di
verit della frase di partenza (se A  vera, la sua negazione non A
e falsa; viceversa, se A  falsa, la sua negazione non A  vera):

                              | non A




 Possiamo prendere in considerazione altri connettivi (ad esem-
plO iI connettivo oppure, corrispondente all'alternativa secca)?
S, sarebbe possibile; ma non risulta particolarmente utile e signi-

          LA LOGICA MATEMATICA                         45

ficativo, a causa di una propriet dei tre connettivi appena con-
siderati (e, o, non), propriet che li rende - oltrech i connettivi
pi naturali - anche gli unici dawero indispensabili: tutti gli altri
connettivi che potremmo prendere in considerazione, di uso co-
mune o del tutto cervellotici che siano, sono ottenibili attraverso
opportune combinazioni di essi.
 Piuttosto, vale la pena di riflettere sulle tabelle presentate a
proposito dei connettivi e, o, non.
 In primo luogo awertiamo che queste tabelle vengono dette ta-
vole di verit; si tratta di una denominazione che appare piutto-
sto ragionevole, poich esse descrivono appunto il funzio-
namento (in termini di verit o falsit) di proposizioni com-
plesse a partire dalla verit o falsit di proposizioni pi ele-
mentari.
 In secondo luogo diciamo che le tavole di verit sembrano co-
stituire uno strumento generale ed efficace per calcolare la ve-
rit di frasi complesse a partire dalla verit di frasi pi semplici.
Almeno questo obiettivo - dopo che abbiamo dovuto rinunciare
a stabilire la verit assoluta di frasi semplici - sembra ora a por-
tata di mano.

 Ricapitoliamo:

 a. Esistono proposizioni non atomiche, owero frasi certamente
vere o false che non rientrano nello schema oggetto soddisfa pre-
dicato (ad esempio Tutti i gatti sono grigi, Qualcuno  addormenta-
to, ecc.).
 b. Tra le proposizioni non atomiche, soffermiamo la nostra
attenzione sulle proposizioni che si ottengono da proposizioni
pi semplici facendo uso di opportune paroline di connessione,
quali e, o, ecc.
 c. Per queste proposizioni complesse sembra essere possibile
una valutazione automatica della verit dell'intera proposizione
in funzione della verit delle frasi pi semplici che le compongo-
no; lo strumento per questa valutazione  costituito dalle tavole
di verit dei connettivi.
 d. Le tavole di verit dei connettivi e, o e non sono le seguenti
46

2.4. n calcolo della verit di una proposizione complessa

 Abbiamo concluso il paragrafo precedente su una promettente
prospettiva:  possibile calcolare - attraverso le tavole - la verit
o falsit di una proposizione complessa a partire dalla verit o
falsit delle proposizioni pi semplici di cui essa si compone. Eb-
bene, la promettente prospettiva  del tutto reale, come mostra il
seguente esempio.
 Si consideri la proposizione La casa  bella e grande o Giuliano
non si trasferir; indichiamo con A, B e C le tre proposizioni ato-
miche coinvolte, rispettivamente La casa  bella, La casa  gran-
de, Giuliano si trasferir. La proposizione si pu ora scrivere nella
forma

A e B o non C.

 Il nostro obiettivo  quello di valutare la sua verit in tutti i casi
che si possono presentare, e cio quando sia A che B che C sono
vere, quando A e B sono vere e C  falsa, quando A e C sono vere
e B  falsa, ecc.
 Predisponiamo, dunque, una maxi-tavola della verit cos fat-
ta:





 Abbiamo lasciato un certo spazio perch la compilazione dell'ul-
tima colonna  successiva alla compilazione di una serie di altre
colonne che rappresentano risultati parziali del calcolo (owero
il calcolo della verit di una parte della proposizione).
 Alla fine del procedimento di calcolo la situazione si presenter
cos:

 Giustifichiamo solo la prima riga della tavola, lasciando al let-
tore il controllo delle altre sette.
 Dunque, siamo nel caso in cui sia A, che B, che C sono vere; ma
allora anche A e B  vera (ce lo dice la prima riga della tavola del
connettivo e) e quindi possiamo inserire v nella quarta colonna,
mentre non C  falsa (ce lo dice la prima riga del connettivo non)
e quindi possiamo inseriref nella quinta colonna; ne consegue
che la proposizione complessa A e B o non C  vera (ce lo dice la
seconda riga della tavola del connettivo o, che prevede, in corri-
spondenza alla prima componente vera e alla seconda falsa, di
attribuire alla frase composta il valore vero) e quindi possiamo
inserire v nell'ultima colonna.
 La conclusione che scaturisce dall'esame della maxi-tavola 
che la nostra proposizione (La casa  bella e grande o Giuliano
non si trasferir) e ogni altra proposizione avente la stessa strut-
tura  falsa in tre casi (quando assumiamo come vero che la casa
sia bella, come vero che Giuliano si trasferir e come falso che la
casa sia grande; quando assumiamo come falso che la casa sia
bella, come vero che sia grande e come vero che Giuliano si tra-
sferir; quando assumiamo come falso che la casa sia bella, come
falso che sia grande e come vero che Giuliano si trasferir); in
tutti gli altri casi  vera.
 Abbiamo cos visto come un sapiente uso delle tavole ci consen-
te la valutazione della verit di una frase complessa. Questo risul-
tato, unito al fatto - gi enunciato in precedenza - che tutti i con-
nettivi possono ridursi ai tre di cui abbiamo costruito la tavola, ci
permette di concludere, con legittima soddisfazione, che abbia-
mo in mano un procedimento automatico per calcolare la verit
di una qualsiasi proposizione complessa.
49
 Per, attenzione: ci che si calcola con le tavole non  la verit
o falsit in assolto della frase, bens, pi modestamente, il modo
in cui eventuali e ipotetiche verit o falsit parziali, relative alle
frasi elementari che vi compaiono, si riflettono sulla verit o fal-
sit della frase composta.
 Compito della logica rispetto alproblema della valutazione della
verit,  dunque solo - dovrebbe essere ormai chiaro, ma, per evi-
tare equivoci, non ci stanchiamo di ripeterlo - quello di studiare
la verit di frasi complesse a partire da ipotesi intorno alla verit
o falsit di frasi pi semplici.
 Questo non significa che il lavoro che stiamo facendo sia inutile
o irrilevante, anche se, in generale, si limita a stabilire delle veri-
t che dipendono da altre verit.
 Vale comunque la pena di segnalare che in alcuni casi particola-
ri la tecnica del calcolo attraverso le tavole consente di raggiun-
gere dei risultati assoluti. Esistono, infatti, proposizioni com-
plesse vereper motivi strutturali, e quindi vere indipendentemen-
te dalla verit o falsit (spesso opinabile) delle proposizioni pi
semplici coinvolte. Evaristo Bottiglioni  astemio o non  astemio,
ad esempio,  una proposizione certamente vera. Infatti, se la pro-
posizione A  falsa, la proposizione non A  vera, e viceversa
quindi una delle due frasi componenti (la proposizione Evaristo
Bottiglioni  astemio e la proposizione Evaristo Bottiglioni non 
astemio)  necessariamente vera; e, d'altra parte, una proposizio-
ne del tipo A o B  vera, purch sia vera una delle due proposizio-
ni componenti.
 La conclusione (la proposizione Evaristo Bottiglioni  astemio o
non e astemio  certamente vera, sia che Evaristo non si awicini
mai ad una bottiglia, sia che tracanni litri di vino ogni giorno!)
era ottenibile in modo pi formale dalla considerazione della se-
guente tabella, costruita a norma delle tavole di verit dei con-
nettivi coinvolti non e o:

                        A non A A o non A |





 Nella tabella, A sta per l'unica proposizione elementare coinvol-
ta, vale a dire Evaristo Bottiglioni  astemio. Se A  vera, allora la
sua negazione non A  falsa, se A  falsa, allora la sua negazione
non A  vera; in ogni caso (cio sia nell'ipotesi vf, sia nell'ipotesi
f v) la frase composta risulta vera (a norma delle righe due e tre
della tavola del connettivo o).
 Le particolarissime proposizioni complesse vere per motivi strut-
turali (owiamente una proposizione atomica non pu essere n
vera n falsa in nome di soli motivi di struttura), cio vere per
qualsiasi valore di verit (vero o falso) di ciascuna delle propo-
sizioni pi semplici che in essa compaiono, si dicono tautologie;
ogni proposizione della forma A o non A costituisce dunque un
esempio di tautologia.
 Analogamente, esistono proposizioni non atomiche false per
motivi strutturali, e quindi sempre e comunque false, qualun-
que sia il valore di verit delle proposizioni pi semplici coin-
volte.
 Un esempio di questo tipo di proposizioni (che si dicono anti-
tautologie o contraddizioni)  costituito dalla frase La vita 
generosa e non generosa (A e non A), accettabile nel linguaggio
quotidiano, ma - secondo i logici - assolutamente depreca-
bile. . .


A non A A e non A
f v .f


Tavola della verit di ogni proposizione del hpo A e non A.

 Fermiamoci qui, e procediamo ad una veloce ricapitolazione di
quanto visto in questo paragrafo:

 a. Il tentativo di automatizzare il calcolo della verit di una pro-
posizione - inteso come tentativo di automatizzare lo studio del-
la verit di frasi complesse a partire da ipotesi intorno alla verit
o falsit di frasi pi semplici - ha successo nel caso di proposizio-
ni complesse.
 b. Bisogna comunque tener sempre presente che si tratta di una
valutazione della verit relativa (dipendente dalla verit di altre
frasi pi elementari) e non assoluta.
 c. Esistono, per, delle proposizioni complesse vere per motivi
strutturali, e quindi vere indipendentemente dalla verit o falsit
(spesso opinabile) delle proposizioni pi semplici coinvolte. Tali
proposizioni complesse, vere per qualsiasi valore di verit delle
proposizioni componenti, si dicono tautologie.
 d. Analogamente, esistono delle proposizioni complesse false
per motivi strutturali. Tali proposizioni complesse, false per qual-
siasi valore di verit delle proposizioni componenti, si dicono anti-
tautologie o contraddizioni.


2.5. Da Euclide alla matematica moderna

 Il gioco del vero o falso applicato a singole frasi  solo una pale-
stra preparatoria per una prova pi impegnativa: l'analisi di
come si perviene a conclusioni vere a partire da premesse vere.
Non ci basta pi stabilire la verit di singole proposizioni; quello
a cui aspiriamo  il perfetto controllo del meccanismo della dedu-
zione.
 Bene, cominciamo col dire che la storia della matematica ci ha
insegnata ridimensionare, anche in questo caso, le nostre aspet-
tative: infatti - a voler essere precisi - la matematica moderna
non si propone di ricavare nuove verit da premesse che sappia-
mo essere vere, ma, pi modestamente, di stabilire quali conse-
guenze si possono dedurre da premesse che supponiamo essere
vere.
 Cosa ci ha spinto a ridimensionare l'obiettivo? Una complessa
vicenda che vale la pena di ripercorrere dall'inizio e con ordine,
come un racconto a puntate.

 Prima puntata: Euclide si mette al lavoro. Euclide  il primo ma-
tematico che si propone di costruire una teoria geometrica com-
pleta, organica, solidamente fondata, in cui tutto ci che si ricava
 assolutamente certo in virt del fatto che le premesse iniziali
sono assolutamente indiscutibili e i procedimenti di deduzione
sono altrettanto assolutamente rigorosi. Una teoria di questo
tipo doveva dunque partire da alcuni postulati, di carattere geo-
metrico, e da alcune nozioni, di carattere pi generale, che fun-
zionassero da premesse a tutta la costruzione (per semplicit
riassumeremo nella parola postulati gli uni e le altre); doveva poi
prevedere, al suo interno, la possibilit di ricavare teoremi (le
conseguenze deducibili dai postulati). Insomma: se una determi-
nata propriet geometrica  vera, essa compare o nei postulati
(quando la sua verit  del tutto evidente) o nei teoremi (quando
la sua verit non  del tutto evidente; allora servir un ragiona-
mento rigoroso, owero una dimostrazione, che, a partire dai po-
stulati, permetta di convincersi della verit dell'assunto).

Postulato l `
Postulato 2
Postulato 3
Postulato 4 -
Postulato 5
Postulato 6

            | dimostrazion~i





Schema proposto da Euclide.

Teorema l
Teorema 2
Teorema 3
Teorema 4
Teorema 5
Teorema 6




 Seconda puntata: Qualcuno osa dubitare di Euclide. Tra i postu-
lati posti da Euclide a fondamento del sistema deduttivo della
sua geometria, ce n'era uno, il quinto (dato un punto e una retta,
esiste una e una sola retta passante perquelpunto e parallela a quel-
la retta), che non apparve abbastanza evidente agli studiosi di
geometria dei secoli successivi. Ecco perch i pi scrupolosi tra
loro pensarono di escludere questo postulato dalle basi della co-
struzione geometrica, ritenendo di poterlo ricavare come teore-
ma dalle altre premesse elencate da Euclide. Si sforzarono cos
di sviluppare una geometria pi rigorosa, che facesse a meno, tra
le sue premesse, del quinto postulato; e tentarono quindi, nel
corso dei secoli, di fornire una dimostrazione del quinto postula-
to come teorema, a partire dagli altri postulati euclidei.


                             Postulato 1

                             Postulato 2

                             Postulato 3

                             Postulato 4

                             Postulato 6

| dimostrazion|



    ..............

    ..............

Schema di Euchde n~eduto e corretto.

Postulato 5
Teorema 1
Teorema 2
Teorema 3
Teorema 4
Teorema 5




 Terza puntata: Ma Euclide aveva ragione. Intorno alla met del
diciannovesimo secolo si perviene alla dimostrazione (dovuta a
Bolyai e Lobacevskij) che il quinto postulato non  ricavabile come
teorema a partire dagli altri postulati: aveva avuto ragione Eucli-
de a collocarlo, appunto, tra i postulati!

 Quarta puntata: Per anche i suoi oppositori non hanno lavorato
invano. Gli studi condotti dai matematici che cercavano di cor-
reggere e perfezionare l'opera di Euclide avevano mostrato che
molte affermazioni geometriche erano dimostrabili anche sen-
za inserire tra le premesse il quinto postulato. Questo fatto
produsse - proprio nel momento del massimo trionfo di Eucli-
de - la proposta di un radicale mutamento di ottica:  possibi-
le giocare a costruire geometrie che non partano dagli stessi
postulati scelti da Euclide. Ma, accettando di giocare a questo
gioco, succede che accanto alla tradizionale Geometria (con la
g maiuscola), fioriscano pigeometrie (con lag minuscola): ol-
tre quella euclidea, anche una geometria euclidea in versione
ridotta, privata del quinto postulato, e varie geometrie non-
euclidee - sviluppate ad esempio da Riemann e da Klein - in
cui il quinto postulato viene sostituito da asserzioni ad esso op-
poste (ad esempio: dato un punto e una retta, non esiste nessuna
retta passante per quel punto e parallela a quella retta); o, perch
no, geometrie ancora pi strambe, purch fondate su premesse
coerenti. Quindi non pi la Geometria, unica, assoluta, specchio
idealizzato della Realt, bens pi geometrie, ciascuna con un
rapporto con la realt fisica evidentemente pi complesso e con-
troverso, ma spesso utili (a volte, addirittura, pi della stessa
geometria euclidea!) per affrontare specifici problemi teorici o
pratici.

 Quinta puntata: Siamo tutti pi liberi, ma a costo di essere tutti
pi rigorosi. L'emancipazione dalla pretesa (e dall'illusione) di una
geometria e, pi in generale, di una matematica assolute ha com-
portato un vertiginoso sviluppo di nuove teorie matematiche.
Ecco i vantaggi della libert! Ma la libert  anche faticosa: se
sembra indifferente partire da una premessa o dal suo opposto,
chi ci garantisce che le conseguenze che deduciamo (dall'una e
dall'altra) siano vere? L'esistenza di una pluralit di presunte ve-
rit in concorrenza tra loro ci spinge a guardare con sospetto e
diffidenza ai risultati che, via via, vengono raggiunti. Ogni teoria
sembra diventare incerta e discutibile; e la preoccupazione mag-
giore  quella che salti fuori qualche contraddizione all'interno
della teoria alla quale si sta lavorando: va bene la massima liber-
t, ma di una teoria contenente anche solo una contraddizione
non sappiamo che farcene (i logici - malignamente e, purtroppo,
a piena ragione - sostengono che in tal caso, in quella teoria 

vero tutto e il contrario di tutto!). Cos,  awenuto che il periodo
che va dalla met dell'Ottocento ai primi decenni del nostro se-
colo sia stato attraversato da grandi dubbi, crisi e incertezze (ci
succedeva, pi o meno contemporaneamente, anche per altre di-
scipline scientifiche, come ad esempio la fisica). Lo sviluppo del-
la logica matematica (collegato a sua volta con la nascita delle
geometrie non euclidee),  la risposta al problema dell'insicurez-
za:  possibile dare fondamenta ragionevolmente solide alle dot-
trine matematiche, riducendo al minimo la possibilit di trovarsi
davanti a contraddizioni, purch si abbia consapevolezza dei li-
miti delle nostre costruzioni (non verit assolute, ma sviluppi
coerenti di determinate premesse), e purch si esplicitino le rego-
le della corretta deduzione (una sorta di galateo del buon ragionare,
elaborato sotto la supervisione dei logici).

 La morale della storia appena narrata  profonda e severa. In
una scienza come la matematica - in cui quello che decide non 
tanto il confronto con la realt fisica, quanto la coerenza e l'elegan-
za della costruzione - occorre essere duttili e liberali quanto alle
premesse e rigidi e restrittivi quanto agli schemi di ragionamento.
Ci significa accettare che i risultati abbiano un carattere relati-
vo: essi discendono da premesse, che chiamiamo assiomi, a cui
non chiediamo pi di essere vere - come si pretendeva dai postu-
lati -, ma solo di essere tra loro compatibili. E significa, al tempo
stesso, attribuire un carattere assoluto al metodo di deduzione: i
procedimenti e gli schemi di ragionamento ammissibili vengono
precisati ed esplicitati una volta per tutte, superando quella che -
agli occhi dei logici moderni - appare una certa vaghezza presen-
te non solo nella trattazione di Euclide, ma anche nelle opere dei
matematici dei secoli successivi.

 E giunto il momento di procedere alla consueta breve ricapitola-
zione:

 a. La geometria di Euclide costituisce il primo tentativo di edi-
ficare una costruzione avente alcune delle caratteristiche che i
logici moderni esigono dalle teorie matematiche.
 b. Euclide pone alla base della sua costruzione alcune afferma-
zioni (i postulati) e dimostra i teoremi a partire da esse attra-
verso ragionamenti. Poich i postulati sono evidentemente veri,
anche I teoremi sono veri.
 c. Il punto di vista moderno - conseguente alla crisi dei fonda-
menti della matematica awenuta a cavallo tra Ottocento e Nove-
cento -  pi articolato: esistono molte geometrie, ognuna con
un suo interesse e un suo ambito di validit; dunque non c' una
sola verit, assoluta, ma tante verit relative.
 d. Quanto detto a proposito della geometria  alla base di tutte
le teorie matematiche moderne. Esse consistono nella libera scel-
ta di un pacchetto di assiomi (con l'unico vincolo che gli as-
siomi prescelti non siano in contraddizione tra loro), e nella deri-
vazione da essi di una serie di conseguenze logiche secondo preci-
se e rigorose regole di deduzione.


2.6. Deduzione e induzione

 Dunque, una volta sgomberato il campo dalla pretesa di rag-
giungere verit assolute e definitive, la logica matematica si  as-
sunta il modesto ma fondamentale compito di precisare come
debba essere condotta una deduzione per avere la garanzia che
sia corretta e rigorosa (abbiamo chiamato tale compito la messa
a punto di un galateo del buon ragionare). Di questo galateo ci
limiteremo a fornire qualche esempio; ma prima ci sembra op-
portuno indicare una possibile obiezione al lavoro paziente di
definizione esatta delle regole della deduzione operato dai logici
matematici.
 Partiamo da un esempio di corretta deduzione che definire ce-
lebre  ancora poco. Infatti, chi non ha sentito citare almeno una
volta il famoso sillogismo di Aristotele (Gli uomini sono mortali
Socrate  un uomo, e dunque Socrate  mortale)? Ecco un cele-
brato esempio di passaggio da premesse che consistono in infor-
mazioni e notizie gi possedute (la mortalit degli esseri umani,
I'appartenenza di Socrate al genere umano) ad una conclusione
inedita (la mortalit di Socrate). Per, qualcuno particolarmente
lucido e poco incline a farsi prendere dall'entusiasmo potrebbe
obiettare che quella che abbiamo chiamato conclusione inedita
(la mortalit di Socrate) non  poi cos nuova e sorprendente:
essa era implicita nelle premesse, owero nelle notizie gi in no-
stro possesso. Ebbene, questo qualcuno avrebbe perfettamente
ragione; ogni galateo del buon ragionare, persino quello suffra-
gato dall'autorevolezza di Aristotele, rischia di risultare poco
produttivo dal punto di vista della scoperta di verit che ci faccia-
no fare passi avanti sostanziali.
 La deduzione, attivit logica per eccellenza,  insomma viziata
da un'insuperabile sterilit, giacch si limita a tirare tutte le con-
seguenze da alcune premesse, e dunque a esplicitare quanto im-
plicitamente gi contenuto in esse.

     A                      Mort~li
      B                 Uomini
          Ic           soI





La rappresen~azione insiemistica del sillogismo di Aristotele evidenzia come ci che
viene dedotto dalle premesse discenda immediatamente dalla propnet translt~va della
relazione di inclusione (se B  incluso in A e C  incluso in B, allora C  incluso neces-
sariamente in A).

 L'irrilevanza della deduzione nella ricerca e nella costruzione
di nuova conoscenza dipende dal fatto che il processo deduttivo
, in definitiva, un passaggio dal generale al particolare: una con-
seguenza della validit di una o pi premesse non pu che essere
la validit di un caso meno generale. Da questo punto di vista, 
possibile assumere come esempio e simbolo dell'intero processo
deduttivo un ragionamento avente la forma: se supponiamo che
tutti gli elementi di un certo insieme soddisfino un determinato pre-
dicato, allora ne deduciamo che tuttigli elementi di un qualsiasi suo
sottoinsieme soddisfano sicuramente anch'essi quel predicato (se
supponiamo che gli italiani siano amanti della musica, allora i to-
scani sono amanti della musica).





Il processo deduttivo  un passaggio dal generale al particolare: se tuni gli elemen~i di A
soddisfano un certo predicato, ne deduciamo che tutti gli elementi di B soddisfano an-
ch'essi quel predicato.
56 MATEMATICA SENZA NUMERI               I  LA LOGICA MATEMATICA                 57

 E chiaro che un processo di costruzione di nuove conoscenze
deve essere fondato proprio su un percorso in senso inverso (dal
particolare al generale): se supponiamo che tutti gli elementi di un
certo sottoinsieme di un insieme soddisfino un determinato pre-
dicato, allora azzardiamo la tesi che tutti gli elementi dell'intero
insieme soddisfano anch'essi quel predicato (Se supponiamo che
i toscani siano taciturni, allora gli italiani sono taciturni). Questo
procedimento spericolato, questo volo senza rete, questo ardito
salto nel buio si chiama induzione. L'induzione s che - sia pure
a rischio di errori - ci fa fare dei passi avanti!





ll processo induttivo  un passaggio dal particolare al generale: se tutti gli elementi di B
soddisfano un certo predicato, induciamo che tutti gli elementi di A soddisfino an-
ch 'essi quel predicato.

 Allora, dopo aver constatato che la deduzione  sicura, ma non
 portatrice di conoscenze dawero nuove, mentre l'induzione 
incerta, ma consente di compiere reali passi avanti, resta da chia-
rire qual  la parte che recitano nella matematica.
 Persino i logici, grandi sostenitori della deduzione, non arriva-
no a sostenere che i teoremi della matematica siano inventati
grazie ad un processo deduttivo; il primo passo  la percezione -
sulla base di alcuni esempi dove le cose funzionano in una cer-
ta maniera - che, forse, vale una certa propriet: in questa fase,
dunque, I'induzione gioca un ruolo fondamentale e inelimina-
bile. I logici, per, richiedono con insistenza che - ad evitare pos-
sibili errori, contraddizioni ed altri guai di questo tipo - le teorie
matematiche, giunte all'et della maturit, vengano riorganizzate
entro un rigido schema che dia il massimo di garanzie ( il mo-
mento d'oro della de`duzione!); la propriet prima intuita deve
rientrare - per poter essere accettata - tra le conseguenze che 
possibile dedurre dalle premesse della teoria. Come dire: un pres-
sante invito alla prudenza, giustificato da incidenti e disillusioni
di cui la storia della matematica non  priva. Lo schema rigido
che prevede che le teorie matematiche abbiano la struttura di un
insieme di assiomi e di un insieme di deduzioni condotte a norma
di precise regole fissate una volta per tutte,  quello che pi met-
te al riparo da possibili contraddizioni.
 Dunque possiamo concludere questa piccola divagazione in cui
abbiamo messo a confronto processo deduttivo e processo indut-
tivo con la seguente meditazione. L'intuizione, la sensazione che
le cose stiano in un modo invece che in un'altro, le illuminazioni
improwise che ci suggeriscono che una propriet scoperta e veri-
ficata localmente ha validit generale, sono cose molto belle e
preziose che spesso ci guidano nella vita, con risultati a volte non
disprezzabili. Anche il matematico - quando deve scegliere una
strada di ricerca invece che un'altra - si lascia spesso guidare da
spinte di questo genere; ma quando si propone di sviluppare una
teoria in modo convincente e incontrovertibile, ecco che allora
usa -  costretto ad usare! - altri strumenti per sistemare le sue
conoscenze. Su questi strumenti torneremo nel prossimo para-
grafo.

 Intanto, ci sia consentito, nelle migliori tradizioni, un momento
di ricapitolazione:

 a. La deduzione  un processo che non produce conoscenze
dawero nuove, poich non si pu dedurre altro che quello che 
implicitamente contenuto nelle premesse che si assumono.
 b. La deduzione  dunque, nella sostanza, un percorso dal genera-
le al particolare, che pu essere simbolizzato dal seguente sche-
ma: se tutti gli elementi di un insieme soddisfano un determinato
predicato, tutti gli elementi di un qualsiasi sottoinsieme dell'in-
sieme di partenza soddisfano quel predicato.
 c. Un processo che produce conoscenze dawero nuove  l'in-
duzione, consistente nell'ipotizzare che una scoperta locale si
possa generalizzare.
 d. L'induzione  dunque, nella sostanza, un percorso dal partico-
lare al generale, che pu essere simbolizzato dal seguente sche-
ma: se tutti gli elementi di un sottoinsieme di un insieme soddi-
sfano un determinato predicato, si suppone che tutti gli elementi
dell'intero insieme in cui il sottoinsieme di partenza  incluso sod-
disfino quel predicato.
 e. Sia l'induzione che la deduzione giocano un ruolo importante
nella costruzione matematica; I'induzione  lo strumento attra-
verso cui si sceglie di procedere in una data direzione di ricerca;
la deduzione  lo strumento che si utilizza per sistemare le teo-
~Q MATEMATICA SENZA NUMERI              |                       --

rie matematiche in una forma che dia il massimo di garanzie sul
piano logico.


2.7. Un'occhiatina al galateo del buon ragionare

 L'avevamo promesso: pur non potendo presentare - per owi
motivi di tempo e di spazio - I'intero galateo del buon ragionare,
avremmo mostrato qualche esempio, sufficiente a dare un'idea
del suo contenuto. Il momento  giunto.
 Un chiarimento preliminare: nel nostro galateo  ragionevole
pensare di trovare due tipi di oggetti. Da una parte alcuni assio-
mi indipendenti dalle particolari teorie matematiche (tali assiomi si
dicono assiomi logici); essi sono assiomi universali, premesse
che utilizziamo in ogni teoria matematica insieme agli assiomi
particolari, specifici della singola teoria che stiamo di volta in
volta considerando. Dall'altra alcune regole (che vengono dette
regole di deduzione) che ci consentano di operare deduzioni da-
gli assiomi; infatti in una teoria matematica costruita secondo le
raccomandazioni dei logici, la dimostrazione di teoremi consiste
nella costruzione di catene deduttive aventi come anelli iniziali
degli assiomi (siano essi assiomi logici universali o assiomi della
specifica teoria considerata); gli ulteriori anelli - fino a giungere
al teorema oggetto della dimostrazione - sono affermazioni de-
dotte dalle precedenti. Dunque, per attivare il meccanismo della
dimostrazione occorrono delle regole - appunto le regole di de-
duzione - che chiariscano come  possibile aggiungere nuovi anel-
li alla catena.
 Cominciamo quindi con il presentare un paio di assiomi logici.
Il primo  un principio fondamentale su cui si basa ogni ragiona-
mento in ambito matematico (e non solo): il principio di non
contraddizione. La vezzosa Zerlina, indimenticabile perso-
naggio del Don Giovanni di Mozart, pu permettersi, indotta
in tentazione dal gentiluomo, di rispondere: Vorrei e non vor-
rei. A chi si occupa di matematica questo non  dato; ci sem-
bra di vedere l'anziano e severo studioso di teoremi irrompere
in scena e intimare a Zerlina: Poche storie, se vuoi - come mi
sembra di capire -, non puoi affermare contemporaneamente
di non volere!. Del resto, sappiamo gi che le contraddizioni
sono l'incubo ricorrente dei matematici! In matematica (in
nessuna teoria matematica) pu succedere impunemente che
il triangolo T sia rettangolo e non rettangolo allo stesso tem-
po Per evitare situazioni incresciose di questo tipo si  deciso
di porre come assioma logico, e quindi come premessa univer-
sale, vincolo onnipresente, il principio di non contraddizione, che
scritto nel linguaggio della logica, diventa la proposizione com-
plessa

                            non (A e non A)

 Essa si legge non  possibile che sia A e non A. In particola-
re, quindi, non ( possibile che) T (sia) rettangolo e non rettan-
golo.
 Un secondo assioma logico del nostro galateo  il principio che
garantisce il carattere binario della logica matematica: il prin-
cipio del terzo escluso. Non ci fa piacere che il controllore, men-
tre cerchiamo affannosamente in tutte le tasche, affermi O ha
fatto il biglietto o non lo ha fatto; eppure, egli si limita ad appli-
care gli inesorabili principi del ragionar matematico. E dunque,
delle due l'una (o il biglietto  stato acquistato o no); non solo
non  possibile che siano successe entrambe le cose (ce lo garan-
tisce il principio di non contraddizione); non  possibile neanche
che non sia accaduta nessuna delle due cose: s o no, e non  data
una terza alternativa! In matematica - proprio come sul treno -
non si accettano mezze misure: o S  l'unico numero compreso tra
4 e 6 o non lo . E si badi che i logici vogliono garantirsi la verit
dell'assunto in ogni teoria dei numeri, sia nell'ambito dei numeri
naturali, dove  verificata la prima alternativa, sia nell'ambito
dei numeri decimali, dove  verificata la seconda; infatti ci che
hanno a cuore non  l'unicit o non unicit del S come valore in-
termedio tra 4 e 6, bens la validit di una delle due alternative,
senza lasciar spazio ad altre possibilit. A questo scopo si  deci-
so di porre tra gli assiomi logici, cio tra le premesse universali
comuni ad ogni teoria matematica, il principio del terzo escluso,
che, scritto nel linguaggio della logica, diventa la proposizione
complessa
A o non A

 In particolare, quindi,  certamente vero che o 5  l 'unico nume-
ro compreso tra 4 e 6 o 5 non  l'unico numero compreso tra 4 e 6.
 Ecco, infine, un paio di esempi di regole di deduzione (senza le
regole di deduzione il meccanismo della dimostrazione di teore-
mi non si metterebbe mai in moto, e saremmo costretti a limitar-
ci a contemplare gli assiomi senza poter ricavare da essi nessuna
conseguenza). La prima regola di deduzione di cui parleremo 
quella che meglio testimonia il carattere di passaggio d al generale
alparticolare tipico d el processo d i deduzione. Tuttigli esseri uma-
ni hanno dei difetti: chi non sarebbe pronto a sottoscrivere questa
affermazione? Ma se diciamo Salvatore Esposito ha dei difetti 
~n MATEMATICA SENZA NUMERI               r  LA LOGICA MATEMATICA                 61

probabile che qualcuno (forse lo stesso Salvatore) si ribelli. Ep-
pure nel ragionamento matematico l'imperfezione del signor
Esposito  ineliminabile conseguenza dell'imperfezione univer-
sale! Questo collegamento tra universale e particolare assume, in
logica, la seguente forma:

Regola di particolarizzazione

dalla premessa         per tutti gli x vale A
si trae la conseguenza     per un particolare t vale A

(dove la t sta ad indicare un qualsiasi elemento particolare che
ha preso il posto dell'elemento indeterminato x). Vale a dire: il
fatto che A vale per ogni x ha come conseguenza che A vale per
un particolare t.
 Siamo cos garantiti di poter dedurre - in ambito geometrico,
ma a norma di una regola di deduzione esplicitata e di validit
universale - dalla premessa ogni retta contiene infiniti punti la
conseguenza la retta r contiene infiniti punti; cos come - in ambi-
to numerico - possiamo affermare che 24  divisibile per I conse-
gue dalla premessa ogni numero  divisibile per 1; e ci sentiremo
autorizzati a comportarci nello stesso modo rispetto a situazioni
analoghe, qualsiasi sia la teoria matematica al cui interno ci si
trova ad operare.
 Il secondo esempio di regola di deduzione su cui ci soffermere-
mo ha a che fare con una tecnica di dimostrazione molto usata in
matematica (e non solo in matematica): la tecnica di dimostrazio-
ne per assurdo. Dice il centravanti Romolo Piedoni: Se io saressi
un brocco, come dicheno alcuni tifosi cattivi, non avrei fatto
manco un gol; siccome ho fatto un gol, non sono un brocco!.
Ora, si pu discutere l'italiano in cui si esprime Romolo, per
non gli si pu dare completamente torto - almeno se si accetta
l'idea che essere brocchi comporti inesorabilmente la conse-
guenza di non aver realizzato nessun goal -: se da una premessa
A (Romolo  un brocco) scaturisce una conseguenza sbagliata
non B (Romolo non ha segnato mai), allora possiamo concludere
che c'era qualcosa che non andava nella premessa; e dunque, per
il principio del terzo escluso, possiamo ricavarne addirittura la
validit di non A (Romolo non  un brocco). E vero che la logica
quotidiana  molto pi vaga e inafferrabile della logica della
matematica (per cui qualche tifoso continua impavidamente a
sostenere che Piedoni brocco  e brocco resta, anche se ha fatto
un goal), ma, insomma, abbastanza spesso, anche nel ragionare
comune, si esclude qualcosa mostrando che l'assumerla per buo-
na condurrebbe a conseguenze assurde.

 Questa tecnica di argomentazione prende in logica la seguente
forma:

Regola della dimostrazione indiretta

se A ha come conseguenza non B
e vale B
allora vale non A

 Vale a dire: il fatto che A ha come conseguenza una negazione
che  in contraddizione con un'acquisizione precedente compor-
ta che vale non A.
 Osserviamo che con questa regola ci siamo garantiti di poter
dedurre, all'interno di una teoria matematica, la negazione di
una proposizione mostrando che la proposizione produrrebbe
una conseguenza che contrasta con un'altra premessa: ad esem-
pio, sapendo che due rette r e s si incontrano (B), poich dal-
I'ipotesi che r e s siano parallele (A) si potrebbe dedurre che r e
s non si incontrano (non B), ne consegue che r e s non sono pa-
rallele (non A).
 Ci fermiamo qui con gli esempi di assiomi logici e regole di de-
duzione, perch il nostro obiettivo non  di esaurire le basi logi-
che del ragionamento matematico, ma solo quello di mostrare
quale lavoro paziente di precisazione  stato compiuto da logici
e matematici per garantire il massimo di attendibilit ai risultati
della loro ricerca; ci sembra di poter dire che l'obiettivo  stato
raggiunto. Resta solo da ribadire che il lavoro dei logici nel pe-
riodo finale dell'Ottocento e poi nei primi decenni del Novecen-
to, mentre ha consentito di fondare le teorie matematiche su basi
molto pi solide e sicure, ha anche mostrato che  illusorio pen-
sare di stabilire verit assolute in modo meccanico, a maggior ra-
gione  illusorio pensare di poter ridurre completamente il ragiona-
mento a calcolo. Il tentativo pi estremo in questa direzione fu
compiuto dal geniale filosofo e matematico Leibniz, vissuto a ca-
vallo tra il Seicento e il Settecento. L'idea dawero ambiziosa di
Leibniz era quella di costruire un linguaggio universale e di mec-
canizzare, attraverso di esso, ogni tipo di ragionamento, mate-
matico e non. Quando sorgano controversie... - diceva Leibniz
_ baster sedersi davanti all'abaco (lo strumento di calcolo in
uso ai suoi tempi) e dirsi a vicenda: calcoliamo!. Solo in questo
secolo, che pure  il secolo del calcolo automatico, dell'informa-
tica e del computer, il logico tedesco Godel ha dimostrato come
tale obiettivo fosse sovradimensionato persino nell'ambito pi li-
mitato della sola matematica; anche in ambito strettamente
matematico, infatti, non tutto ci che  vero in una teoria  dimo-
          62                      MATEMATICA SENZA NUMERI

strabile con metodi automatici. Rimane, dunque, un'incomple-
tezza ineliminabile nel nostro modo di costruire conseguenze da
premesse.

Breve ricapitolazione:

 a. Nel galateo del buon ragionare ci sono: assiomi !ogici, cio
proposizioni che vengono assunte come premesse umversali, co-
muni a tutte le teorie matematiche (poi, ogni singola teoria avr
anche degli assiomi specifici, relativi alle particolari propriet
degli oggetti di quella teoria; questi assiomi non rientrano nel
nostro galateo) e regole di deduzione (norme che stabiliscono
come  possibile ricavare correttamente conseguenze da premes-
se)
 b. Esempi di assiomi logici sono il principio di non contraddizio-
ne (non (A e non A)) e il principio del terzo escluso (A o non A).
 c. Primo esempio di regola di deduzione  la regola di particola-
rizzazione (dalla premessa per tutti gli x vale A si trae la con-
seguenza per un particolare t vale A).
 d. Secondo esempio di regola di deduzione  la regola della
dimostrazione indiretta (se non B  conseguenza di A, allora la
validit di B comporta la validit di non A). Vale a dire: il fatto
che A porta ad una contraddizione con un'acquisizione prece-
dente ha come conseguenza che vale non A.
 e. Il meccanismo di deduzione garantita messo in piedi dai lo-
gici permette di sviluppare le teorie matematiche su basi molto
pi solide; ci non significa, per, avere in mano un meccanismo
esaustivo di dimostrazione per tutto ci che  vero all'interno di
una teoria matematica.

3. Grammatiche e linguaggi





3.1. n calcolatore modifica ilpunto di vista dei matematici

 Immaginiamo un labirinto complicato (da un punto di partenza
P si dipartono decine di strade, e ad ogni successivo snodo ci sono
decine di alternative diverse, ecc.). Forse (ma solo forse) sce-
gliendo ogni volta in modo opportuno l'alternativa giusta, si
arriver alla meta M. Come fare per stabilire se esiste il collega-
mento (bench tortuoso) tra P e M, e eventualmente esista, qual
? Un bel problema, non c' che dire, che pu condurre alla di-
sperazione lo sfortunato individuo che in esso si imbatta (il no-
stro amico Sigismondo - appassionato di viaggi esotici - si  tro-
vato a viverlo all'areoporto di una cittadina della Cina, dove i
cartelli esplicativi, abbondanti e vivacemente colorati, avevano il
sorprendente difetto di essere scritti... in cinese).
 Un problema arduo, dunque, ma che non ha nulla a che fare con
la matematica... E, in effetti, fino a qualche anno fa un matemati-
co non si sarebbe mai sporcato le mani con questioni di questo
tipo; se si fosse trovato nell'imbarazzante situazione in cui si 
trovato l'amico Sigismondo, avrebbe reagito come qualsiasi altra
persona, scoppiando, probabilmente, in un pianto dirotto e scon-
solato! Ma oggi non  pi cos; la novit dipende dall'entrata in
campo di un nuovo protagonista, il calcolatore, capace di fare
molto velocemente numerosissime operazioni, rendendo con ci
possibile affrontare e risolvere in tempi ragionevoli il problema
della ricerca di un percorso utile in un labirinto. A questo punto
il matematico ha trovato un compito da svolgere: costruire stra-
tegie efficienti di esplorazione di tutti i percorsi possibili (il che
vuol dire procedere con metodo, evitando di ripetere tentativi
gi dimostratisi vani, ecc.). Dunque il calcolatore non deve esse-
re visto semplicemente come una macchina che permette di fare
molto pi velocemente le stesse cose che prima richiedevano un
tempo maggiore;  vero, ma non  tutto. Il calcolatore ha pro-
dotto un cambiamento (parziale, ma significativo) del punto di
vista dei matematici, spingendoli a comprendere nell'ambito di
questa disciplina nuove tipologie di situazioni problematiche (ad
esempio, la ricerca in un labirinto); e, anche, stimolandoli ad ela-
borare nuovi strumenti teorici di analisi (ad esempio, le tecniche
di esplorazione di un labirinto). E cos la matematica moderna si
trova a non poter prescindere dal calcolatore; e, pi in generale,
 costretta a tener conto dello sviluppo dell'info~7natica, la scien-
za che nasce con la sperimentazione dei primi computer e che
studia teoricamente potenzialit e limiti dei procedimenti auto-
matici di risoluzione dei problemi.

                              \>~

                                             T


Un esempio di strategia di ricerca di un tesoro T in un labirinto .~ad albero binario 
costituito dalla seguente lista di istruzioni:
1. Se nel nodo in cui ti trovi c' T, fermati: la ricerca finita.
2. Se dal nodo in cui ti trovi scende un ramo sinistro inesplorato, seguilo e toma all'~-

3. Se dal nodo in cul h trovi scende un ramo destro inesplorato, seguilo e toma aU'istru-
zione 1.
4. Risall al nodo immediatamente supenore a quello in cui ti trovi e toma all'istnuz~one 1.

 Dunque, la matematica - a contatto con l'informatica - si tra-
sforma, amplia il suo ambito di interesse, si arricchisce di nuovi
territori di ricerca.
 Un ulteriore significativo esempio di problema che acquista cit-
tadinanza in matematica  costituito dalla ricerca di modalit di
ottimizzazione dei procedimenti risolutivi. Il termine ottimiz-
zazione pu incutere un po' di spavento, ma ci che si intende
 piuttosto semplice, anche se del tutto inedito per i matemati-
ci: ci si pone l'obiettivo di imparare a confrontare (dal punto di
vista della convenienza, e cio della massima economia di tempo
- owero del minimo numero di operazioni elementari necessarie -
e dal punto di vista della sinteticit e linearit della procedura)
strade diverse che conducono alla soluzione di uno stesso proble-
ma.

7~J3 2 8          7 13 2 8

 - confronto e eventuale scambio tra
    7 e 13: si ottiene
7 13 2 8

                J
I - confronto e eventuale scambio tra
    13 e 2: si ottiene
7 2 1~J8

- confronto e eventuale scambio tra
  13 e 8: si ottiene
7~J2 8 13

- confronto e eventuale scambio tra
  7 e 2: si ottiene
2 7 8 13
- ulteriori tentativi di scarnbio non
  conducono a modifiche e quindi
  l'ordinamento dei quattro numeri
   il seguente:
         2 7 8 13

- individuazione minimo tra 7, 13,
  2, 8: si ottiene 2


- individuazione minimo tra 7, 13,
  8: si ottiene 7


- individuazione minimo tra 13, 8
  si ottiene 8


- I'ordinamento dei quattro numeri
   il seguente:
       2 7 8 13





Due strategie diverse per disporre in ordine crescente quattro numen. La pnma, basata
sul confronto tra termini adiacenti e suU'eventuale scambio tra essi, ha termine quan-
do, scorrendo la sequenza dall'inizio alla fine, non occorre operare pi alcuno scam-
bio, e nchiede - se i numen sono 4 - da un minimo di 3 confronti (nel caso in cui i
numen siano gi ordinati) ad un massimo di 4 3 confronti (nel caso in cui i numen
siuno in ordine inverso); se i numen coinvolh sono n, si va da r~n minimo di n-l con-
fionti ad un massimo di n(n-1) confronti. La seconda, basata sulla ricerca del mini-
mo, e poi del minimo tra i <~superstiti e cosi via, ha termine quando resfa un solo su-
perstite e nchiede - se i numen sono 4 - esattamente 3+2 confronti; se i numen coin-
volti sono n occorreranno (n-1)+... +2 confronti (infatti, per cercare il minimo tra 3
numen,  sufficiente confrontare il pnmo con il secondo, e il minore tra i due con il
terzo - e quindi occorrono 2 confronh -, in generale, procedendo cos~, per cercare il
minimo tra n numen occorreranno n-1 confronti).

 Non ci interessa, in questa sede, esaminare le tecniche che si
utilizzano per confrontare l'efficienza di strategie diverse mi-
ranti a risolvere lo stesso problema; e, d'altra parte, sarebbe ben
difficile farlo senza mettere in mezzo la matematica con i nu-
meri. Ci preme, invece, sottolineare il radicale cambiamento di
ottica che le problematiche dell'ottimizzazione introducono nel-
la ricerca matematica: per la prima volta il tempo (inteso come
lunghezza del procedimento risolutivo) diventa un fattore signi-
ficativo nei ragionamenti dei matematici. Laddove prima l'inte-
resse era concentrato principalmente sull'interrogativo esiste o
non esiste una soluzione? (per i matematici puri aveva spesso
un rilievo secondario - una volta stabilita l'esistenza della solu-
zione - persino il problema di trovarla effettivamente!), ora, in
svariate situazioni, ci si pone il problema in termini pi articolati:
esiste o non esiste una soluzione, e - se esiste - qual  la strada
pi efficiente per trovarla?. Insomma: non  pi solo questione
di esistenza della soluzione, ma anche di sua raggiungibilit in
tempi di calcolo pi o meno brevi; il mutamento di ottica indotto
dall'ingombrante presenza del computer non  da poco!

Eccoci pronti alla tradizionale, breve ricapitolazione:

 a. Il calcolatore  una macchina capace di eseguire in tempi ra-
pidi moltissime operazioni; la sua straordinaria velocit di esecu-
zione ha sollecitato i matematici ad affrontare problemi prece-
dentemente esclusi dall'ambito della loro disciplina (ad esem-
pio, la ricerca di un percorso utile in un labirinto).
 b. Il calcolatore, e, pi in generale, I'informatica (e cio la scien-
za che studia teoricamente potenzialit e limiti dei procedimenti
automatici di risoluzione dei problemi), hanno stimolato i mate-
matici ad elaborare nuovi strumenti di analisi (ad esempio, le
tecniche di esplorazione di un labirinto).
 c. Inoltre, dal contatto con il computer  sorta l'esigenza di con-
frontarsi con l'obiettivo di ottimizzare (in termini di numero di
operazioni elementari necessarie e di linearit del procedimento)
la strategia risolutiva di un problema; questo fatto segna l'ingres-
so del parametro tempo nella matematica.


3.2. Linguaggi naturali e linguaggi artificiali

 Non si deve pensare che la l~elocit di esecuzione sia l'unica carat-
teristica del calcolatore che modifica e amplia gli orizzonti della
ricerca matematica. La dote del computer che lo rende dawero
una macchina alquanto speciale  la sua duttilit, cio la sua
capacit di affrontare e risolvere, se debitamente guidato e istrui-
to, situazioni problematiche varie, diverse, sempre nuove. Ma
proprio perch esso non si limita a prestazioni standardizzate e
sempre uguali - in virt del fatto di possedere una sorta di capa-
cit di apprendimento -,  necessario disporre, da parte nostra,
di strumenti per dialogare con la macchina.
 La verit  che il computer sa compiere pochissimi tipi di opera-
zioni elementari; ma, in compenso, e in grado di memorizzare
lunghe sequenze di istruzioni relative a tali operazioni elementa-
ri che, opportunamente concatenate, danno luogo a prestazioni

complesse e sofisticate. Non possiamo, quindi, limitarci ad accen-
dere la macchina e a dare un qualche tipo di segnale di awio; 
necessario, ogni volta, comunicare al computer la particolare li-
sta di istruzioni predisposta per la specifica prestazione che ci
interessa in un quel determinato momento (sia essa la ricerca di
un dato in un archivio, la soluzione di un'equazione, il disegno di
un grafico, I'ordinamento alfabetico di parole, o altro). Ci signi-
fica che occorre disporre di un linguaggio per comunicare con la
macchina; la lista di istruzioni corrispondenti alla performance
che vogliamo ottenere sar scritta in tale linguaggio.
 Ecco dunque che i matematici (per colpa in generale dell'in-
formatica, e in particolare del calcolatore!) sono costretti a fer-
marsi a riflettere su un problema del tutto inedito: la costruzione
di nuo~i linguaggi. Infatti, essendo evidente che non  possibile -
anche se qualcuno non esita a farlo! - rivolgersi ad un computer
con le stesse frasi che si riservano ad un intimo amico o ad un'at-
traente fidanzata, sar necessario costruire linguaggi ad hoc per
comunicare con il computer (tali linguaggi vengono detti lin-
guaggi di programmazione).
 I linguaggi di programmazione rientrano nella classe dei lin-
guaggi artificiali e presentano delle caratteristiche che li rendo-
no piuttosto diversi dai linguaggi parlati (linguaggi naturali),
quali l'italiano, I'inglese, lo spagnolo, ecc.; in primo luogo si trat-
ta di linguaggi semplici e poveri, dimensionati sull'esigenza di
impartire un numero ridotto di tipi di istruzioni (mentre la lingua
parlata deve riuscire ad esprimere una comunicazione ricca e va-
riegata, che - oltretutto - non si limita a prescrizioni del tipo: se
ti trovi in questa situazione fai cos); in secondo luogo si tratta
di linguaggi del tutto privi di ambiguit (ad ogni istruzione deve
corrispondere una e una sola azione; d'altra parte il computer
non  certo l'ideale per cogliere allusioni e apprezzare sfumature
che, al contrario, sono importanti risorse per le lingue parlate);
infine, i linguaggi di programmazione (come tutti i linguaggi ar-
tificiali) sono progettati a tavolino e disciplinati da rigide regole
stabilite a priori (laddove le lingue parlate presentano norme pi
elastiche e instabili, in gran parte determinate a posteriori dal-
I'uso che si afferma nel tempo tra i parlanti).
 Ma sono proprio gli studiosi dei linguaggi naturali ad indicare
(nell'opera del linguista americano Noam Chomsky) un punto di
contatto significativo di questi con i linguaggi artificiali: entram-
be le tipologie di linguaggi obbediscono ad alcune regole struttu-
rali comuni, che sono in qualche modo predeterminate dal modo
di organizzare ilpensiero attraverso le parole caratteristico degli es-
seri umani; ad esse non sfuggiamo quando parliamo tra noi; ad
esse non riusciamo a sfuggire neanche nel momento in cui creia-
mo dei nuovi linguaggi!
 E dunque i matematici e gli informatici, che sono sollecitati dal
computer a occuparsi di nuovi linguaggi, finiscono per occuparsi
anche dei fondamenti delle grammatiche delle lingue parlate; e,
viceversa, gli studiosi dei linguaggi naturali, riflettendo sul modo
in cui tali linguaggi sono strutturati, finiscono per darci preziose
indicazioni sulle regole che devono governare i linguaggi artifi-
ciali. Si viene cos a creare un'interazione proficua e feconda tra
matematica, informatica e linguistica.

 Procediamo ad una breve ricapitolazione:

 a. Il repertorio di azioni elementari che il calcolatore sa compiere
 molto ristretto; ci nonostante il calcolatore  in grado di fornire,
se debitamente guidato, prestazioni molto differenziate, in virt
della sua capacit di memorizzare lunghe liste di istruzioni.
 b. La necessit di comunicare al calcolatore queste liste di i-
struzioni ha costretto i matematici e gli informatici (cio coloro
che studiano potenzialit e limiti dei procedimenti automatici di
risoluzione dei problemi) ad elaborare specifici linguaggi; i lin-
guaggi per comunicare con il computer si chiamano linguaggi di
programmazione e appartengono alla pi generale categoria dei
linguaggi artificiali.
 c. Alcune caratteristiche che differenziano i linguaggi di pro-
grammazione da!le lingue parlate (linguaggi naturali) sono le se-
guenti: i linguaggl di programmazione sono semplici e poveri, sono
del tutto privi di ambiguit, sono (come tutti i linguaggi artificiali)
progettati a tavolino e disciplinati da rigide regole stabilite a priori.


3.3. Semplicigrammatiche pergenerare linguaggi

 La nozione che lega tra loro matematica, informatica e linguistica
 quella di grammatica generativa; nella linea indicata da Chom-
sly - il gi citato studioso di linguistica a cui si deve il maggior con-
tributo allo studio della struttura dei linguaggi -, le grammatiche
generative regolamentano sia i linguaggi naturali che i linguaggi ar-
tificiali. Cosa  una grammatica generativa? Nella sostanza  una
specie di meccanismo adeguato allo scopo di costruire tutte le
frasi (strutturalmente corrette) di una lingua e solo quelle.
 Quando un linguaggio  particolarmente semplice, la gramma-
tica che lo genera si dice grammatica a stati finiti, e pu essere
rappresentata attraverso... alcune frecce che collegano alcuni nodi.
Ancora una volta - come gi nelle rappresentazioni delle relazioni
- ci troviamo davanti a dei grafi, con la particolarit, in questo
caso, che essi indicano un percorso (o meglio, un insieme di pos-
sibili percorsi) che ha un inizio e una fine. Questi particolari grafi
orientati vengono detti diagrammi sintattici, in quanto evi-
denziano la struttura delle frasi generate dalla grammatica.
 Per inciso: il lettore ha il diritto di lamentare una certa monoto-
nia nelle nostre rappresentazioni.
 Ma la faccenda pu essere vista - senza allontanarsi dal vero -
anche in positivo: abbiamo messo in campo degli strumenti di rap-
presentazione cos duttili da adattarsi a molte situazioni; e inol-
tre, al di l delle forme dissimili, molti concetti matematici
rivelano parentele inaspettate.
 Torniamo alle nostre grammatiche a stati finiti: nulla pi di un
esempio tratto dalla vita di tutti i giorni pu chiarire questa no-
zione. Consideriamo dunque la seguente rappresentazione:



     Grammatlca Gl





       -


 Essa descrive la grammatica che genera il linguaggio L1- invero
pluttosto povero - in CUI Sl esprime, da alcune settimane a questa
parte, I'impiegato Paride Sebastiani, follemente innamorato della
sua collega Gilda Comparelli. Questo linguaggio, tenero ed essen-
ziale,  costituito da tutte le frasi che si riescono a comporre metten-
do in fila le parole che si incontrano percorrendo il diagramma da
sinistra verso destra lungo un qualsiasi percorso indicato dalle
frecce.
 Ad esempio, la lettura del diagramma ci dice che  possibile
generare la frase Gilda  molto molto cara: la frase inizia con la
parola Gilda, che  contenuta nel primo nodo che si incontra
dopo l'awio, e prosegue con la parola , contenuta nel secondo
nodo; scegliendo poi (per due volte) di deviare verso l'alto si ot-
tengono le parole molto molto; infine, andando dritti verso
l'uscita si incontra il nodo contenente la parola cara.
 A questo punto il cammino  terminato, avendo prodotto la fra-
se attesa.
 Dovrebbe essere ormai chiaro che l frasi del linguaggio L1
generato dalla grammatica G1 sono:

Gilda  cara
Gilda  molto cara
Gilda  molto molto cara
Gilda  molto molto molto cara
ecc.

fino ad esaurimento delle forze del passionale Paride!
 Qualche parola di commento. Intanto, abbiamo riconosciuto
che il linguaggio L1  piuttosto miserello (consiste in un sottoin-
sieme dawero ridotto dell'insieme delle frasi della lingua italia-
na!); per si tratta di un linguaggio composto da infinite frasi, e
quindi non sarebbe possibile descriverlo attraverso un elenco di
tutte le frasi che contiene. Dunque, il modo pi semplice di de-
finire un linguaggio, consistente appunto nell'esplicitare tutte le
frasi di cui  formato,  perfettamente adeguato ad ogni linguaggio
finito, ma non  adeguato a L1, linguaggio povero quanto si vuo-
le, ma comunque linguaggio infinito (l'infinit di L1  conseguen-
te all'esistenza di un ciclo, cio di un sotto-percorso che torna nel
punto in cui  cominciato dopo un giro pi o meno tortuoso). E
poi, pur continuando ad essere vero che il linguaggio L1 non 
molto creativo,  pur vero che la grammatica G1 che lo genera 
simile a grammatiche piuttosto importanti in matematica e in in-
formatica. Una di queste  la grammatica G2 che genera tutti i
numeri maggiori di 0 scritti in base 2, cio rappresentati nella
forma in cui i numeri sono memorizzati all'interno del calcolato-
re (i numeri maggiori di 0 scritti in base 2 sono sequenze di 0 e 1
che cominciano con 1; in particolare, 1 sar scritto 1, 2 sar scrit-
to 10 - in quanto il 10  l'immediato successore di 1 tra i numeri
scritti usando solo le cifre 0 e 1- 3 sar scritto 11, 4 sar scritto ad-
dirittura 100 - dato che tutti i numeri da 12 a 99 utilizzano anche
almeno una ciJia di~ersa da 0 e da 1, 5 sar scritto 101, ecc.).
 Il diagramma sintattico che illustra il funzionamento di G2 ri-
vela l'analogia di tale grammatica con la grammatica G1:





.

 Infine,  vero che il diagramma sintattico della grammatica G1
descrive la macchina per produrre frasi del linguaggio di Paride;
ma, guardando - come  giusto - le cose anche dal punto di vista
di Gilda, lo stesso grafo rappresenta anche il suo comportamen-
to in quanto automa riconoscitore del linguaggio di Paride. Si trat-
ta di un discorso abbastanza impegnativo, tanto da meritare che
un intero paragrafo (il prossimo) gli sia consacrato.

 Per il momento procediamo ad una rapida ricapitolazione:

 a. Le grammatiche generative sono l'anello di congiunzione tra
matematica, informatica e linguistica.
 b. Il tipo pi semplice di grammatica generativa  la grammati-
ca a stati finiti, che pu essere rappresentata attraverso un dia-
gramma sintattico, cio un grafo orientato con un inizio e una
fine che indica un percorso (o meglio vari possibili percorsi).
 c. Il linguaggio generato da una grammatica a stati finiti  l'in-
sieme di tutte e sole le frasi che si ottengono leggendo le parole
che si incontrano percorrendo il diagramma dall'inizio alla fine
lungo un qualsiasi percorso.
 d. Una grammatica a stati finiti genera un linguaggio infinito se
e solo se contiene al suo interno un ciclo (cio un sotto-percorso
che torna al suo punto d'awio dopo un giro pi o meno tortuo-

so).


3.4. Semplici automi per riconoscere linguaggi

 Avevamo promesso di guardare le cose anche dal punto di vista
di Gilda, ossessionata dalla passione di Paride e dalla forrna poco
elaborata e creativa in cui tale passione si esprime; da qualche
tempo Gilda si comporta n pi n meno come un automa ri-
conoscitore del linguaggio di Paride. Vediamo di chiarire questa
affermazione, apparentemente stravagante.
 A parte il caso di un linguaggio finito, descrivibile semplice-
mente attraverso l'elenco delle frasi che appartengono ad esso,
la conoscenza di un linguaggio si identifica - per quanto detto fi-
nora - con la conoscenza della grammatica che lo genera, owero
con il fatto di disporre di un meccanismo che produce tutte e sole
le frasi che appartengono al linguaggio. Un cittadino cinese co-
nosce la sua lingua in quanto  in grado di esibire a ripetizione
frasi grammaticalmente corrette appartenenti ad essa. Ma non 
questo il solo senso in cui si pu dire di conoscere un linguaggio.
Possiamo dire di conoscere l'arabo anche se, data una successio-
ne di suoni o di simboli, siamo in grado di individuare se essa 
72

una frase di quella lingua o non lo . Insomma, un punto di vista
riconoscitivo invece che generativo. E evidente che questa ottica
nuova e diversa pu essere applicata sia nel caso di un linguaggio
naturale che nel caso di un linguaggio artificiale; ed  chiaro an-
che che il riconoscimento deve awenire in modo certo, inesora-
bile, automatico e non pi o meno e ad occhio. Il nostro pro-
blema  dunque quello di descrivere un procedimento automatico
di riconoscimento di un linguaggio; ebbene, a tal fine ci affidia-
mo ad un automa riconoscitore: chi e cosa pi di un automa pu
garantire certezza e inesorabilit? Ovviamente, quando usiamo
la parola automa non ci riferiamo necessariamente ad una mac-
china concreta, ferraglia o plastica, ingranaggi o circuiti pi o
meno integrati; ma piuttosto ad un comportamento che obbedi-
sce a regole predeterminate e rigide, non lasciando margini ad
ambiguit, dubbi, incertezze, perplessit, esitazioni e titubanze! Tan-
t' che il primo esempio di automa riconoscitore che vogliamo pre-
sentare  costituito dal comportamento di un essere umano, la
nostra malcapitata Gilda, che si regola, relativamente al linguag-
gio di Paride, proprio come un automa;  possibile rendersene
conto individuando esattamente quali sono le sue reazioni da-
vanti ad un messaggio (registrato, ad esempio, dalla sua segrete-
ria telefonica).
 Gilda, dunque, si trova inizialmente in uno stato di placida quie-
te che possiamo denominare s0. Ecco, per, che ascolta la telefo-
nata registrata dalla sua segreteria; se la prima parola  una qual-
siasi parola diversa da Gilda, la nostra amica si tranquillizza com-
pletamente, transitando in uno stato di benessere che chiame-
remo s1; ma se la prima parola del messaggio  proprio Gilda,
nella sua testa si insinua il sospetto - ancora vago, in verit - che
l'autore della telefonata possa essere Paride, e dunque Gilda pas-
sa in uno stato di moderata agitazione s2. La situazione pu esse-
re descritta attraverso il seguente grafo, in cui le frecce sono eti-
chettate con parole:





lda (~)

 Ora,  chiaro che se Gilda si  messa tranquilla (owero si tro-
va nello stato di grazia s1) qualsiasi sia la seconda parola del
messaggio, ella permarr in s1, e dunque tale seconda parola
risulter ininfluente; mentre, se si trova nello stato di moderata
agitazione s2, lo sviluppo del suo stato d'animo dipender dalla
seconda parola: se essa  una qualsiasi parola diversa da , ec-
cola transitare nello stato di benessere s1 (pericolo scampa-
to: non si tratta di Paride); se invece  proprio , Gilda piomba
in uno stato di profonda preoccupazione e di massimo allarme
s3.
 Il grafo seguente d conto dell'evoluzione dello stato d'animo
di Gilda dopo aver ascoltato le prime due parole del messag-
gio:





                         (~) GJ~da > e >(~)




 Terza parola del messaggio: se Gilda si trova in s1, non teme
nulla, e ogni parola produrr l'effetto di lasciarla nello stato sl;
se si trova nello stato di allarmata (ma non rassegnata, giacch, si
sa, la speranza  l'ultima a morire!) preoccupazione s3, allora
la terza parola del messaggio sar ascoltata con estrema atten-
zione: se  diversa da cara e da molto, la tensione svanisce e
Gilda transita in s1; me se - Dio non voglia! - la terza parola 
cara, allora non c' scampo, si tratta proprio di un messaggio
di Paride, e dunque Gilda precipita in uno stato d'animo di to-
tale sconforto, che possiamo indicare con s4; se, infine, la ter-
za parola  molto, ebbene, Gilda rimane nello stato di profon-
da preoccupazione e di massimo allarme s3 (permangono ri-
schio elevato e pallida speranza).
 Ancora una volta, un opportuno grafo illustra efficacemente l'e-
volversi dello stato d'animo di Gilda conseguente all'ascolto di
tre parole del messaggio:
                 molto


                     (~) Gilda ( (~) c ra (~)


 A questo punto il comportamento automatico di Gilda sembra
compiutamente descritto. Volendo proprio essere pignoli occor-
rerebbe, per, specificare che se il messaggio continua quando
Gilda  nello stato di totale desolazione s4, allora evidentemente
c  stato un equivoco -  impossibile che l'autore della regi-
strazione sia Paride, notoriamente incapace di simili levate d'in-
gegno - e quindi ella transiter con evidente sollievo nello stato
di grazia s1. Dunque - se vogliamo considerare tutte le situazioni
che si possono presentare - il grafo che descrive il comportamen-
to di Gilda deve essere completato in modo che in ogni nodo (an-
che in s4) ci siano indicazioni (ci siano frecce in uscita) in corri-
spondenza di ciascun possibile stimolo. Questa  una buona re-
gola per ogni grafo relativo a un automa, insieme all'altra, del
tutto owia, che stabilisce che non ci devono essere ambiguit, e
che quindi una stessa etichetta non pu contrassegnare due frecce
uscenti da uno stesso nodo (altrimenti l'automa non avrebbe indi-
cazioni univoche su come comportarsi in determinati frangenti)
 Ecco allora il grafo che descrive in modo dawero completo ed
esauriente il comportamento di Gilda (o, se vogliamo, il compor-
tamento di un automa A1 che funzioni da riconoscitore del lin-
guaggio L1):





                    (aUl- > (~


(Ad ogni nodo, la lettera X va letta come una qualsiasi parola diversa da quelle presen-
h nelle etic11ette delle frecce uscenti da esso).

 Volendo essere ancora pi pignoli, ci si potrebbe chiedere cosa
succeda se, mentre Gilda si trova in uno stato di agitazione (s2 o
s3), il messaggio ha termine (sancendo cos che non si tratta di
Paride).
 Ma questo caso  assorbito da quello che stiamo per dire: noi
consideriamo awenuto il riconoscimento del messaggio come
appartenente al linguaggio L1 se e solo se Gilda (owero l'auto-
ma riconoscitore A1) si trova, al termine dell'ascolto della regi-
strazione, nello stato finale s4, evidenziato nel grafo come finale
attraverso il doppio circolo; in qualsiasi altro stato si trovi Gilda
dopo la scansione dell'intero messaggio, diremo che il riconosci-
mento non  awenuto.
 Quelle appena viste sono caratteristiche generali degli automi
riconoscitori (o meglio - per essere plU precisi - di quella classe
di automi che si dicono automi riconoscitori a stati finiti, di cui
Gilda costituisce un grazioso esempio).
 Infatti un automa riconoscitore a stati finiti A  definito da:

 - uno stato iniziale
 (che si indica, in generale, con s0)
 - un insieme di stati interrnedi
 (nel caso di Gilda, s1, s2, s3)
 - uno o pi statifinali
 (nel caso di Gilda, il solo s4)
 - una legge di transizione
 (che specifica il modo in cui l'automa risponde ad un nuovo
 stimolo - nel caso di Gilda, una nuova parola - transitan-
 do in un nuovo stato)

 L'automa A riconosce una sequenza di simboli (nel caso di Gilda,
una sequenza di parole) come appartenente ad un dato linguaggio
L (nel caso di Gilda, il linguaggio L1 a cui si riduce la capacit di
produrre frasi di Paride) se al termine della scansione della se-
quenza si trova in uno stato finale (nel caso di Gilda, lo stato s4).
 Il lettore avr notato che la descrizione dell'automa riconosci-
tore A1 relativo al linguaggio L1 coincide, nella sostanza, con la
descrizione della grammatica G1 che genera L1.
 Questo non  motivo di stupore, sorpresa e meraviglia, essendo
 stato gi segnalato in precedenza che grammatiche a stati finiti e
 automi riconoscitori a stati finiti costituiscono due modalit- di-
 stinte ma sostanzialmente equivalenti - per definire un semplice
 linguaggio, rispettivamente attraverso la sua generazione o il suo
riconoscimento.
 Vediamo ora un altro esempio di automa riconoscitore, descrit-
to direttamente attraverso il grafo ad esso associato:
o'~t-~o





n simbolo iniziale  s0; esiste un solo simbolo finale, ed  s2.

Non si capisce niente?
Calma e sangue freddo.
 Intanto, una prima osservazione sorge spontanea: l'automa A2
appare pi direttamente collegato alla matematica tradizionale.
Infatti l'insieme delle etichette che compaiono sulle sue frecce
(costituito dai simboli 0 e 1)  del tutto familiare anche a coloro
le cui conoscenze matematiche sono del tutto elementari.. Poi:
anche in questo grafo, come nel grafo dell'automa Gilda, esiste
una specie di pozzo, cio uno stato (s1 in entrambi i casi) che
non  uno stato finale e dal quale  impossibile tirarsi fuori, giac-
ch tutte le frecce in uscita riconducono ad esso. Dunque, perch
il riconoscimento abbia successo (owero perch la scansione
della sequenza porti ad uno stato finale) bisogna evitare di cade-
re nel pozzo ! E quindi le sequenze buone da una parte devo-
no cominciare con il simbolo 1 (per evitare di farci cadere imme-
diatamente nel pozzo!), e, dall'altra, non devono avere, dal se-
condo posto in poi, il simbolo 1 (per evitare di farci precipitare,
plU tardi ma altrettanto rovinosamente, nel pozzo).
 La conclusione si presenta, a questo punto, in tutta evidenza
davanti ai nostri occhi: l'automa A2 riconosce le sequenze (tutte
e sole le sequenze) che cominciano con il simbolo 1 e che prose-
guono con tanti 0 quanti ne vogliamo, e cio le sequenze

1,10,100,1000, 10000, ecc.

 Possiamo essere soddisfatti: comprendendo il funzionamen-
to dell'automa, abbiamo anche individuato il linguaggio da esso
riconosciuto: si tratta del linguaggio costituito da tutte quelle che
i matematici chiamano le potenze di 10 (owero 10 = 1,101 = 10,
102 = 100,103 = 1000, ecc.). Il grafo (accompagnato dalla precisa-
zione su quale sia lo stato iniziale e quali siano gli stati finali) costi-
tuisce una rappresentazione al tempo stesso espressiva e com-
pleta dell'automa.

E il momento di ricapitolare:

 a. Un'altra modalit di conoscenza di un linguaggio - oltre alla
definizione di una grammatica generativa che produce tutte e
sole le sue frasi -  la capacit di riconoscere se una certa sequen-
za di parole appartiene o no alle frasi del linguaggio.
 b. Il tipo pi semplice di meccanismo automatico di riconosci-
mento delle frasi di un linguaggio  l'automa riconoscitore a stati
finiti.
 c. Un automa riconoscitore a stati finiti  costituito da uno stato
iniziale, da alcuni stati intermedi, da uno o pi stati finali e da
una legge di transizione. Se sottoponiamo all'automa una frase,
(o, pi in generale, una qualsiasi sequenza di simboli), esso -
scandendo la frase o sequenza da sinistra verso destra - per ogni
parola o simbolo che incontra transita da uno stato ad un altro
a norma della legge di transizione definita una volta per tutte. Se
al termine della scansione della frase o sequenza l'automa si tro-
va in uno degli stati finali, allora il riconoscimento  awenuto e la
frase o sequenza appartiene al linguaggio relativo a quell'auto-
ma; altrimenti la frase o sequenza non appartiene al linguaggio
relativo a quell'automa.
 d. Anche l'automa riconoscitore a stati finiti pu essere rappre-
sentato attraverso un opportuno grafo in cui nei nodi ci sono gh
stati e le frecce che connettono i nodi sono etichettate con le pa-
role (o con i simboli) che l'automa pu incontrare nel corso della
scansione.


 3 .5. Simboli terminali e simboli non lerminali

 Tra i linguaggi fin qui presentati, lo spazio maggiore  stato ri-
servato ad L1, il linguaggio di Paride innamorato; in relazione aa
L1 abbiamo considerato la grammatica a stati finiti G1 che lo ge
nera e l'automa a stati finiti A1 che lo riconosce.
 L1 comprende una quantit infinita di frasi, ma esse risultano
piuttosto monotone e ripetitive, costituendo una porzione mar-
ginale e insignificante della moltitudine di frasi che appartengon
 alla lingua italiana.
 Considerazioni analoghe si potrebbero fare a proposito degli al-
tri linguaggi introdotti: evidenti sono i limiti del linguaggio costi-
tuito dalle sole (seppure infinite) potenze di 10; e persino il pi
ampio linguaggio costituito da tutti i numeri in base 2 - cio scrit
ti usando solo le cifre 0 e 1- appare piuttosto circoscritto, non sola
perch i numeri sono rappresentati facendo uso di solo due cifre
78 MATEMATICASENZANUMERI                    GRAMMATlcHEFliNGuAGcil

invece delle dieci abituli, ma anche perch i numeri - comun-
que essi siano scritti - sono solo un caso particolare di espressioni
numeriche (nelle espressioni ricorrono - oltre ai numeri - sim-
boli di operazioni, parentesi, ecc.).
 Dunque i linguaggi presentati, generati da grammatiche a stati
finiti e/o riconosciuti da automi a stati finiti, appaiono piuttosto
limitati.
 Dal che sembra potersi dedurre che le grammatiche a stati fi-
niti hanno degli intrinseci limiti nella loro capacit generativa
(analogamente, sembra potersi dedurre che gli automi a stati
finiti hanno degli intrinseci limiti nella loro capacit riconosci-
tiva).
 Vero o falso?
 La risposta  s,  vero, tali limiti sussistono e sono - lo vedremo
ne~l prossimo paragrafo - piuttosto angusti.
 E per anche vero che non abbiamo ancora ottenuto tutto quel-
lo che si poteva ottenere dalle grammatiche (e dagli automi) a
stati finiti; owero,  possibile generare attraverso grammati-
che a stati finiti dei linguaggi pi ricchi e articolati di quelli fin
qui considerati (analogamente,  possibile ottenere da automi
a stati finiti il riconoscimento di linguaggi pi ricchi e articola-
ti)-
 Quindi, prima di abbandonare le grammatiche (e gli automi) a
stati finiti per dedicarci ad altre grammatiche (e ad altri auto-
mi) pi elaborate, ci sembra giusto soffermarci ancora un mo-
mento su di esse: chiss che non ne venga fuori qualcosa che ci
torner utile quando la nostra navigazione punter risolutamente
verso altri lidi.
 Concentriamo dunque ancora la nostra attenzione sulle gram-
matiche a stati finiti (osservazioni analoghe potrebbero essere
compiute a proposito degli automi a stati finiti, ma - stante il for-
te legame, gi pi volte sottolineato tra grammatiche e automi -
non vale la pena di fare il discorso due volte rischiando di annoiare
in lettore).
 Partiamo nuovamente dal linguaggio L1 e proviamo ad esten-
derlo in modo da tener conto della possibilit che Paride diriga
in futuro le sue pressanti attenzioni su una qualsiasi delle sue col-
leghe d'ufficio (bisogna sapere che, oltre a Gilda, ci sono anche
Anna, Carla e Maria).
 Il diagramma sintattico della grammatica G' 1 che genera que-
sto linguaggio L'1 dovr prevedere una serie di alternative nel
primo tratto di percorso, restando per il resto inalterato rispetto
al diagramma di G1:
Diagl~lllllll~l ('.

 Gr~mr..

   I==
   }




 Non si tratta di un'estensione in s particolarmente significati-
va; per ci suggerisce un'idea che - lo vedremo nel prossimo pa-
ragrafo - si riveler proficua nel seguito. L'idea  quella di intro-
durre una sorta di super-nodo, owero un nodo di livello diver-
so dagli altri, all'interno del diagramma; tale super-nodo non
conterr una parola (o, in generale, un simbolo) del linguaggio
ma un indicatore generico di un 'intera categoria di parole (o simbo-
li) del linguaggio:





 Diagramma B.

 Owiamente, perch il diagramma sia leggibile, occorre che sia
accompagnato da un ulteriore diagramma che specifichi le paro-
le (i simboli) del linguaggio che si possono sostituire al posto del
generico indicatore NOME:

NOME
 L'insieme dei due diagrammi sintattici B e C definisce compiu-
tamente la nuova grammatica G' 1, e quindi essi possono sostitui-
re il diagramma A.


      Gr--mmaUcG'l (5econda rappresen~azlone)

       D IAG RAM M A   
        PRINCIPALE   r--~





 Vogliamo sottolineare l'interessante novit costituita dalla pre-
senza, nella rappresentazione della grammatica attraverso i dia-
grammi sintattici, di parole che non appartengono al linguaggio
generato dalla grammatica. Tali parole si dicono parole (o, pi in
generale, simboli) non terminali e sono destinate ad essere sosti-
tuite in corso d'opera secondo modalit descritte - a loro volta -
attraverso un diagramma sintattico; i simboli non terminali non
compaiono nel prodotto finale dell'attivit generativa, che  una
frase del linguaggio. In contrapposizione ai simboli non terminali, si
dicono parole (o simboli) terminali le parole appartenenti al lin-
guaggio che compaiono nei diagrammi sintattici. Per evitare che
sorgano confusioni si usa racchiudere i simboli non terminali in
cornici rettangolari e i simboli terminali in cornici di forma circo-
lare o (all'incirca) ellittiche; questa accortezza  stata da noi gi usa-
ta nel presentare i diagrammi sintattici relativi alla grammatica G' 1.
Nei diagrammi relativi alla grammatica G' 1 c' dunque un solo sim-
bolo non terminale (NOME) che non comparir nelle frasi del lin-
guaggio L'1 generato da G'1, e svariati simboli terminali (Gilda,
Anna, Carla, Maria, , molto, cara) appartenenti ad L' 1.
 Per acquistare dimestichezza con questa faccenda dei simboli ter-
minali e non terminali, niente di meglio che considerare un secondo
esempio.
 Proponiamoci quindi di estendere il linguaggio costituito dai nu-
meri scritti in base 2, definendo la grammatica G'2 che genera
tutti i numeri interi maggiori di zero scritti normalmente. La
grammatica G' 2  descritta dai seguenti diagrammi sintattici, dove
compaiono due simboli non terminali, CIFRA e CIFRA-NON-NULLA:



       DIAGRAMMA
        PRINCIPALE




      CIFRA-NON-NULLA





 Le rappresentazioni di grammatiche in cui utilizziamo simboli
non terminali sono molto semplici, sintetiche ed efficaci. A pen-
sarci bene, ci dipende dal fatto di disporre di simboli (appunto
i non terminali) che giocano un ruolo analogo a quello che gioca-
no i nomi delle forme grammaticali (sostantivo, awerbio, agget-
tivo, ecc.) nella descrizione delle frasi delle lingue parlate: come
le forme grammaticali permettono di descrivere in termini gene-
rali la struttura delle frasi della lingue parlate, cos i simboli non
terminali facilitano la costruzione dei diagrammi sintattici di una
grammatica poich ci consentono di concentrare l'attenzione
sulla struttura delle sequenze di simboli (nel nostro esempio tale
struttura  cifra non nulla + eventuali ulteriori cifre) della specifica
grammatica considerata, lasciando ad un livello successivo la scel-
ta delle determinazioni (ad esempio 7 al posto della cifra non
nulla, e 4 seguito da 0 e poi da 8 al posto delle ulteriori cifre) che
fanno passare dalla struttura generale della sequenza ad una
particolare sequenza (nel nostro caso la sequenza 7408).
 Detto tutto questo a favore dei non terminali,  giusto ribadire
che, nella sostanza,per l 'uso che ne abbiamo fatto finora, la novit
da essi rappresentata  molto relativa, riducendosi, nella sostan-
za, ad un'abbreviazione, certo utile ed elegante, ma inessenziale:
in ogni momento  possibile passare dalla rappresentazione at-
traverso terminali e non terminali ad una rappresentazione in
cui compaiano solo terminali. La grammatica G'2, ad esempio,
pu essere rappresentata - senza far uso di non terminali - nel
seguente modo:





       ;`-





       }


 E infine giunto il momento della consueta breve ricapitolazione
di fine paragrafo:

 a. I linguaggi generati da grammatiche a stati finiti (e analoga-
mente quelli riconosciuti da automi a stati finiti) sono plUttOStO
limitati.
 b. Un tentativo di forzare questi limiti  costituito dall'intro-
duzione nei diagrammi sintattici di parole o simboli non apparte-
nenti al linguaggio (vengono detti non terminali), che fungono
da generici indicatori di un insieme (finito) di parole o simboli
del linguaggio.
 c. Per convenzione, i simboli non terminali sono racchiusi in
cornici rettangolari e i simboli terminali (cos vengono chiamati
simboli appartenenti al linguaggio che compaiono nei diagram-
mi sintattici) in cornici circolari o (all'incirca) ellittiche; quando
in un diagramma compare un non terminale, occorre allegare
al diagramma principale un ulteriore diagramma che illustri il
funzionamento di tale non terminale.
 d. La distinzione tra non terminali e terminali consente di rap-
presentare le grammatiche in modo pi elegante e sintetico. Tale
distinzione permette quindi di prendere in considerazione gram-
matiche pi complesse; ma, finch i non terminali vengono uti-
lizzati solo per identificare un insieme finito di simboli terminali,
la loro presenza non accresce in modo sostanziale la potenza dei
linguaggi generati.


3.6. Grammatiche di complessit superiore

 Abbiamo preannunciato l'arrivo di linguaggi pi complessi, ri-
spetto ai quali le grammatiche a stati finiti, nonostante i successi
registrati nella parte finale del paragrafo precedente, risultano
inadeguate. Ebbene, non ci resta che presentare uno di tali lin-
guaggi; ma il lettore non immagini chiss quale livello di com-
plessit: il linguaggio che abbiamo scelto per mostrare i limiti delle
grammatiche a stati finiti  quello che ha elaborato Paride, in vena
di innovazioni, e comprende le seguenti frasi:

dolce tesoro
dolce dolce tesoro tesoro
dolce dolce dolce tesoro tesoro tesoro

e, in generale, tutte le frasi costituite dalla parola dolce ripetuta
un numero qualsiasi n di volte, seguita dalla parola tesoro ripetu-
ta esattamente lo stesso numero n di volte. Ebbene, questo lin-
guaggio che chiameremo L3, pur essendo anch'esso estremamente
povero e ripetitivo, non  generabile da una grammatica a stati fi-
niti (e non  riconoscibile da un automa a stati finiti).
           84                      MATEMATICA SENZA NUMERI

 Per convincersi di questa impossibilit  sufficiente ragionare sul
fatto che un'ipotesi di grammatica adeguata a generare il lin-
guaggio L3 dovrebbe prevedere un diagramma sintattico di que-
sto tipo:


                 | Ipotesl dl gr mm~Uc che generl L3 |





 Ma questa grammatica, che avrebbe la pretesa di generare L3,
non essendo in grado di conteggiare n il numero di passaggi per
i1 nodo contrassegnato dal simbolo terminale dolce, n il numero
di passaggi per il nodo eontrassegnato dal simbolo terminale te-
soro, produee un linguaggio pi ampio di L3, e eio il linguaggio
contenente - oltre alle frasi di L3 - anche le frasi dolce dolce teso-
ro, dolce tesoro tesoro tesoro, eee. Il problema che sembra insupe-
rabile, dunque,  che una grammatica adatta a generare L3 do-
vrebbe avere la capacit di .ricordare quante volte si  passati per
un deterrninato nodo, eapaeit ehe appare del tutto estranea al
repertorio di abilit delle grammatiehe a stati finiti
 N  possibile eonsolarsi con l'argomento - pur non infondato -
della particolarit e artificiosit del linguaggio L3. Esso rientra
nella pi generale classe dei linguaggi costituiti dalle sequenze
ab, aabb, aaabbb, aaaabbbb, ecc., che si indicano sinteticamente
con la serittura anbn. Ora, se si riflette sul fatto ehe uno dei requi-
siti fondamentali delle espressioni numeriehe  quello di avere
tante parentesi aperte quante parentesi chiuse, appare evidente che
una grammatica che pretenda di generare tutte le espressioni
numeriche deve avere una sotto-grammatica che genera tutte le
espressioni con n parentesi aperte consecutive seguite da n pa-
rentesi chiuse, cio una sotto-grammatica che genera un linguag-
gio formato da tutte le sequenze (n )n - n parentesi aperte seguite
da n parentesi chiuse - (che  un linguaggio del tipo anbn). Dun-
que le grammatiche a stati finiti non riescono a generare un lin-
guaggio che  al tempo stesso molto semplice e imprescindibile
per le applicazioni matematiche e informatiche della teoria delle
grammatiche generative (altrettanto si potrebbe dire - scam-
biando la parola generare con la parola riconoscere - a proposito
degli automi a stati finiti).
 Per fortuna il lavoro compiuto sulle grammatiche a stati finiti,
come fu preannunciato a suo tempo, ci torna utile nella fase in

          GRAMMATICHF E l INGUAGGI                       85

cui le circostanze ci costringono ad andare oltre i confini al cui in-
terno finora ci siamo tenuti. In particolare, si rivela preziosa l'in-
troduzione dei simboli non terminali, eome mostra la seguente
grammatica (di nuovo tipo) che genera tutte e sole le frasi del lin-
guaggio L3:



       DIAGRAMMA
       PRI~JCIPALE





 Per chiarire le modalit di funzionamento di questa grammati-
ca, la cosa migliore  procedere all'effettiva generazione di qual-
che sequenza. Supponiamo, ad esempio, di voler generare la se-
quenza dolce dolce tesoro tesoro. Il cammino lungo il diagramma
principale ci fa incontrare subito la parola dolce; dopodich
incontriamo il non terminale C e dunque - lasciando in sospeso
il cammino su questo diagramma - ci spostiamo sul diagramma
che descrive C, scegliamo il percorso in alto e troviamo ancora la
parola dolce dopodich incontriamo di nuovo il non terminale C
e dunque - iasciando in sospeso il cammino sul diagramma C -
ricominciamo a percorrere C dall'inizio; per questa volta sce-
gliamo la freccia in basso e quindi non generiamo nulla; dobbia-
mo allora riprendere il cammino dall'ultimo percorso lasciato m
sospeso - ci trovavamo sul diagramma C - e adesso ci troviamo
ad aver scavalcato senza conseguenze il simbolo non terminale
C, incontriamo dunque la parola tesoro, e con ci abblamo per-
corso completamente il diagramma C; non ci resta che tornare al
percorso sul diagramma principale, che avevamo lasciato in so-
speso, ora ci troviamo al di l di C, e quindi incontriamo la parola
tesoro; dopodich abbiamo finito, e dunque la frase generata 
dolce dolce tesoro tesoro.
 C' motivo di lamentarsi: il fatto di lasciare in sospeso l'esplo-
razione di un diagramma rende difficoltosa e pesante la descri-
zione del percorso seguito nella generazione della frase. Ecco per-
ch - nella definizione di una grammatica - si fa spesso uso di una
tecnica diversa, che consente una descrizione pi sintetica del
processo di generazione.
          86                      MATEMATICA SENZA NUMERI

 In effetti, la grammatica prima considerata  evidentemente
equivalente a questo insieme di regole di produzione (intenden-
do le regole di produzione come regole che ci dicono cosa sosti-
tuire a cosa e tenendo conto del fatto che la generazione di una
frase  compiuta solo nel momento in cui non compaiono pi
simboli non terminali):

                     Inizio dolce C tesoro
            C    I dolce C tesoro

dove il simbolo I sta ad indicare che il simbolo non terminale C
pu produrre due sequenze diverse, e il simbolo (che  il sim-
bolo dell insieme vuoto, cio di un insieme privo di elementi) sta
ad indicare che una di queste due produzioni pu essere sterile.
 Ecco come si presentano ora le varie tar,ne .l
della frase dolce dolce tesoro tesoro:

---rrb

Inizio
dolce C tesoro (come suggerito dalla prima regola di produzio-

 dolce dolce C tesoro tesoro (come suggerito dalla seconda alter-
nativa della seconda regola di produzione)
dolce dolce tesoro tesoro (come suggerito dalla prima alternativa
della seconda regola di produzione).

 Vediamo, come secondo esempio, la generazione della frase
dolce dolce dolce dolce tesoro tesoro tesoro tesoro:

Inizio
dolce C tesoro
dolce dolce C tesoro tesoro
dolce dolce dolce C tesoro tesoro tesoro
dolce dolce dolce dolce C tesoro tesoro tesoro tesoro
dolce dolce dolce dolce tesoro tesoro tesoro tesoro.

 A questo punto dovrebbe risultare chiaro che tutte le frasi del
tipO dolcen tesoron sono generate dalla nostra grammatica; per,
per essere dawero tranquilli che essa sia adeguata alla genera-
zione del linguaggio L3, occorre una sorta di controprova, e cio
occorre mostrare che - attraverso di essa - non  possibile gene-
rare frasi con un numero diverso di dolce e di tesoro. Ma, in effet-
ti, questa impossibilit  del tutto evidente guardando con atten-
zione i diagrammi sintattici della nostra grammatica non c'
percorso che permetta di incontrare una di queste due parole
senza incontrare anche l'altra; e - come del resto deve essere -

          GRAMMATICHE E LINGUAGGI                      87

non  possibile incontrare la parola tesoro prima di aver smesso
di incontrare la parola dolce. E, d'altra parte, la faccenda risulta
ancora pi evidente considerando la definizione della grammati-
ca attraverso le sue regole di produzione; tanto evidente che non
abbiamo intenzione di spendere su questo neanche un'altra pa-
rola
 Piuttosto, ora che ci siamo convinti dell'adeguatezza della gram-
matica presentata, rispetto all'obiettivo di generare L3,  oppor-
tuno fare qualche riflessione che ci permetta di cogliere in cosa
questa grammatica differisca (in particolare in relazione all'uso
dei non terminali al suo interno) rispetto alle grammatiche a sta-
ti finiti.
 Una prima differenza  legata al fatto che nella grammatica ge-
neratrice di L3 i simboli non terminali non si limitano a sin-
tetizzare un insieme finito di simboli terminali; qui i simboli non
terminali corrispondono a veri e propri diagrammi complessi al
cui interno possono comparire simboli terminali e simboli non
terminali.
 Ma la caratteristica dawero nuova  un'altra: pu comparire,
all'interno del diagramma sintattico che descrive un non termi-
nale (owero all'interno della regola di produzione che indica
con cosa occorre sostituire il non terminale che compare a sini-
stra della freccia), anche lo stesso non terminale che d il nome al
diagramma (alla regola di produzione). Si tratta di una sorta di
circolarit; ma in questo caso il circolo  assolutamente virtuo-

so...
 Le grammatiche del tipo appena visto, che si dicono libere dal
contesto, sono dunque pi potenti, in modo sostanziale, rispetto
alle grammatiche a stati finiti, giacch generano linguaggi che le
altre non riescono a generare. E bene sapere che ad esse corri-
spondono automi riconoscitori pi potenti di quelli a stati finiti
(tali automi si dicono automi riconoscitori a pila), di cui, per,
non parleremo. Ci sembra pi utile, adesso, fermare la nozio-
ne di grammatica libera dal contesto, fornendo un secondo esem-
pio, che, oltretutto, risulta un pochino pi vicino alle problema-
tiche della matematica di quanto lo sia l'ennesimo delirio di Pa-
ride.
 Vediamo dunque una grammatica che generi tutte le espressioni
(con tanto di addizioni, sottrazioni, moltiplicazioni, divisioni, pa-
rentesi, ecc.) in cui sono coinvolti numeri scritti in base 2 (cio
scritti usando solo le cifre 0 e 1); il passaggio alle espressioni con
i numeri normali  del tutto owio e viene lasciato all'intuizione
del lettore.
 Ecco allora la nostra grammatica G3:
Cr~mm~lcG3

DIAGRAMM
PRI~CIPALE

Inizio~
NOPN
(NOPN)OPN

((N OPN)OPN)OPN
((N OPN)OPN)OP(N OPN)~
((lCOPN)OPN.)OP(NOPN)~

(( 1 0-O'P N )'OP N ) OP ( N OP N )
((lOOPlC)OPN)OP(NOPN)~
((lOOP10C)OPN)OP(NOPN)~
((lOOP101)OPN)OP(NOPN)~
((10+ 101)0PN)OP(NOPN)~
((10+ 101)0P1C)OP(NOPN)~
((10+ 101)0P10)OP(NOPN)~
((10+ 101) 10)OP(NOPN)~
((10+ 101) 10)OP(1COPN)~
((10+ 101)-10)OP(lOOPN)~
((10+ 101)-10)OP(lOOP1)~
((10+101) 10)OP(10-1)~
((10+ 101) 10):(10-1)

         }





         --L



 Ed ecco la sua versione in termini di regole di produzione (dove
i simboli N, C, OP sono non terminali, e la numerazione delle
regole facilita la descrizione della generazione di una sequen-

 Inizio N OP N
 N(NOPN) I 1 I lC
 CO I 1 I OC I lC

 P+1-1 1:

R1
R2
R3
R4

 Vediamo come la grammatica G3 genera l'espressione:

         ((10+101) 10):(10-1)

attraverso R1
attraverso R2-a
attraverso R2-a
attraverso R2-a
attraverso R2-c
attraverso R3-a
attraverso R2-c
attraverso R3-c
attraverso R3-b
attraverso R4-a
attraverso R2-c
attraverso R3-a
attraverso R4-c
attraverso R2-c
attraverso R3-a
attraverso R2-b
attraverso R4-b
attraverso R4-d


 Bene, con questa piccola esibizione riteniamo conclusa la pre-
sentazione delle grammatiche libere dal contesto; possiamo dun-
que procedere alla ricapitolazione (che, questa volta, sar per for-
za di cose alquanto meno rapida e breve!):

 a. Un esempio dei limiti della capacit generativa delle gramma-
tiche a stati finiti (owero, il che  lo stesso, della capacit ricono-
scitiva degli automi a stati finiti)  costituito dall'impossibilit di
generare attraverso una grammatica a stati finiti (di riconoscere
attraverso un automa a stati finiti) il pur semplice linguaggio
 nbn, costituito dalle sequenze che presentano un certo numero
di volte il simbolo a seguito da altrettante volte il simbolo b.
 b. Un sostanziale potenziamento della capacit generativa del-
le grammatiche si ha dando un ruolo diverso ai simboli non ter-
minali: essi non si limitano ad indicare sinteticamente un insieme
finito di terminali tra cui scegliere di volta in volta quello che si
vuole utilizzare nella generazione di una frase o sequenza; ora i
non terminali corrispondono a veri e propri diagrammi comples-
si al cui interno possono comparire simboli terminali e simboli
non terminali, tra cui lo stesso non terminale a cui si riferisce il
diagramma.
 c. Le grammatiche in cui  ammessa la presenza di almeno un
 non terminale che compare anche nel diagramma che lo descrive
 si dicono grammatiche libere dal contesto. Il linguaggio costi-
           90                      MATEMATICA SENZA NUMERI

tuito dalle sequenze del tipo anbn  generato da una grammatica
libera dal contesto
 d. Esistono degli automi che riconoscono i linguaggi generati
dalle grammatiche libere dal contesto; tali automi si dicono au-
tomi a pila.
 e. C' un altro modo (oltre ai diagrammi sintattici) per descri-
vere le grammatiche (e, in particolare, le grammatiche libere dal
contesto). Esso consiste in un elenco di regole di produzione che
specificano cosa  possibile sostituire ad un simbolo non termi-
nale nel corso della generazione di una frase o sequenza.


3.7. Linguaggi, grammatiche, automi, calcolatori...

 Il nostro cammino attraverso i linguaggi artificiali - e, pi in ge-
nerale, la nostraescursione nella matematica senza numeri - si
awia al termine. E giunto il momento di mettere un po' d'ordine
nelle scoperte che abbiamo fatto e di trarre qualche conclusione
Il primo punto che emerge con rilievo dai nostri ragionamenti 
che c  un forte intreccio tra linguaggi, grammatiche e automi
Se, in particolare, soffermiamo la nostra attenzione sui linguaggi
artificiali (quelli pi significativi per i matematici e gli informati-
ci), dove l'elemento prevalente  quello formale-sintattico, la
stessa definizione del linguaggio passa necessariamente per la
definizione di una grammatica che lo genera o di un'automa che
lo riconosce: nel primo caso ci troveremo davanti ad una co-
noscenza del linguaggio basata sulla capacit di costruire frasi
che al linguaggio appartengono; nel secondo caso la conoscenza
del linguaggo sar testimoniata dalla capacit di riconoscere
con sicurezza se una determinata frase ne fa parte o no.
 Un'ulteriore importante tappa del nostro viaggio attraverso i
linguaggi  stata portata a termine indicando per quale via - an-
che se tale procedimento non  stato esplicitato - sia possibile
stabilire una gerarchia tra linguaggi. All'inizio procedevamo a
occhio: i1 tal linguaggio sembra particolarmente povero (viene
subito in mente il Paride innamorato del primo periodo: parla
sempre e solo di Gilda, e utilizzando sempre lo stesso schema di
frase Gilda  molto... molto cara, seppure con la variante del nu-
mero di volte in cui ripete l'awerbio molto); il tal altro linguaggio
sembra pi ricco e articolato. Da un certo punto in poi abbiamo
di fatto adottato un criterio pi scientifico e rigoroso, quello pro-
posto da Chomsly (ancora lui!) e accettato dai matematici e da-
gli informatici: tale criterio stabilisce il livello di complessit di
un linguaggio sulla base del livello di complessit della gramma-

           GRAMMATICHE E LINGUAGGI                      91

tica che lo genera (dell'automa che lo riconosce). Le grammati-
che pi semplici - che abbiamo chiamato grammatiche a stati fi-
niti - sono quelle completamente descritte da diagrammi sintat-
tici in cui i non terminali non giocano nessun ruolo significativo;
ad esse corrispondono gli automi di tipo pi elementare, gli au-
tomi a stati finiti, rappresentabili attraverso grafi etichettati
(tutte le frecce hanno un'etichetta). Ebbene, i linguaggi generati
da queste grammatiche (owero, riconosciuti da questi automi),
sono quelli che collochiamo al gradino pi basso della gerarchia
dei linguaggi; essi, pur potendo risultare infiniti, appaiono in ef-
fetti piuttosto monotoni e ripetitivi. Un secondo livello di gram-
matiche  costituito dalle grammatiche libere dal contesto, ca-
ratterizzate dalla presenza - nei diagrammi che le definiscono -
di non terminali auto-referenziali: questi non terminali sono
presenti nel diagramma che li definisce. Le grammatiche libere
dal contesto vengono spesso rappresentate attraverso un insie-
me finito di regole di produzione che dettano le norme per la so-
stituzione di un simbolo non terminale con altri simboli, termi-
nali e non terminali (tra essi pu comparire lo stesso simbolo che
viene rimpiazzato); gli automi corrispondenti a tali grammatiche
sono detti automi a pila. Abbiamo cos individuato un secondo
gradino nella gerarchia dei linguaggi, dove troviamo i linguaggi
generati dalle grammatiche libere dal contesto (e riconosciuti
dagli automi a pila); essi appaiono pi ricchi e articolati (un esem-
pio significativo gi citato di linguaggio appartenente a questa
classe  quello delle espressioni aritmetiche).
 La domanda che viene naturale, a questo punto,  se e ragione-
vole proporsi di definire grammatiche di livello ancora superiore,
in grado di generare linguaggi ancora pi complessi e sofisticati.
La risposta  positiva; lo si poteva intuire a partire dalla sen-
sazione, del tutto fondata, che una grammatica adeguata a genera-
re una lingua naturale richieda una capacit generativa pi am-
pia di quella finora messa in campo. E c' anche un motivo stretta-
mente logico-matematico che milita a favore della considerazione
di grammatiche di livello superiore rispetto alle stesse gramma-
tiche libere dal contesto: occorre necessariamente uscire fuori
dall'ambito delle grammatiche libere dal contesto per incontrare
una grammatica che sia in grado di generare tutto ciO che e cal-
colabile. In realt, il discorso sulle grammatiche gerarchicamen-
te superiori alle grammatiche libere dal contesto sarebbe lungo e
complesso; non intendiamo affrontarlo in questa sede se non per
 giustificare la qualifica di libere dal contesto che abbiamo at-
 tribuito alle grammatiche di secondo livello:  infatti possibile
 definire grammatiche in cui le regole di produzione specifichino
in quali contesti si opera una certa sostituzione di simboli e in
quali altri si opera una differente sostituzione (si tratta solo di un
esempio di come si possa procedere a ulteriori arricchimenti del-
le modalit di definizione di una grammatica - e, quindi, di come
si possano raggiungere livelli gerarchici superiori).
 Il motivo per cui non abbiamo intenzione di andare oltre le
grammatiche libere dal contesto non risiede esclusivamente nel
crescente livello di difficolt che comporta l'esame di grammati-
che dalla struttura sempre pi articolata e complessa, ma anche
nel fatto che le grammatiche libere dal contesto sono sufficienti
per generare i principali linguaggi di programmazione (i linguag-
gi di programmazione - ricordiamo - sono quelli in cui sono scritte
le liste di istruzioni che i calcolatori memorizzano e poi mettono
in esecuzione per fornire prestazioni e risolvere problemi). Se
consideriamo che tutto il nostro discorso sui linguaggi  partito
dall'esigenza di comunicare con i computer, possiamo ritenerci
soddisfatti, avendo percorso fino in fondo il cammino necessario
per raggiungere l'obiettivo!

 Siamo giunti all'ultima breve ricapitolazione:

 a. C' un forte intreccio tra linguaggi, grammatiche e automi-
per definire un linguaggio artificiale occorre definire una gram-
matica che lo genera o un automa che lo riconosce
 b. E possibile stabilire una gerarchia tra linguaggi stabilendo il
livello di complessit di un linguaggio sulla base del livello di com-
plessit della grammatica che lo genera (o dell'automa che lo ri-
conosce).
 c. Le grammatiche pi semplici (grammatiche a stati finiti) e gli
automi corrispondenti (automi a stati finiti) definiscono i lin-
guaggi pi poveri. Le grammatiche di livello immediatamente su-
periore (le grammatiche libere dal contesto) e gli automi corri-
spondenti (automi a pile) definiscono i linguaggi di livello imme-
diatamente superiore.
 d. Si potrebbe andare avanti nella gerarchia delle grammatiche
e degli automi (e nella corrispondente gerarchia dei linguaggi)
ma le grammatiche libere dal contesto sono gi sufficientemente
potenti da generare i pi usati linguaggi di programmazione.

Conclusoni





 La matematica senza numeri non finisce certo qui. Molte altre
cose si potrebbero dire, molte acquisizioni interessanti Sl pO-
trebbero ricordare, molte linee di ricerca si potrebbero indicare.
Ma ci sembra che non occorrano ulteriori esemplificazioni per
concludere che esistono territori della matematica (o, quanto
meno, alle frontiere della matematica) dove ci si addentra solo
facendo ricorso a sensibilit e attenzioni che non hanno nulla a
che fare con l'idea della matematica che ci portiamo dentro. Que-
sti territori si rivelano, anche ad una rapida e sommaria perlu-
strazione, vasti, fertili e persino divertenti, al di l di ogni previ-
sione.
 Pensiamo di poter chiedere al lettore - se ha avuto la pazlenza
di giungere fino a questo punto - di lasciarsi attraversare da un
dubbio: forse anche la matematica classica pu essere guarda-
ta con spirito libero, creativo e critico, con il gusto della co-
struzione e della scoperta, invece che presumendo di confrontar-
si con una verit assoluta, indiscutibile, data una volta per tutte.
Se questo dubbio - almeno il dubbio! - si  insinuato tra le pigre
certezze intellettuali con cui noi tutti conviviamo abitualmente,
allora la nostra piccola escursione nei territori della mate-
matica senza numeri ha assolto il suo compito.
fine.
