Appunti del corso di Logica, turni A e BVersione beta, 14 ottobre 2011

Alessandro Andrettaalessandro.andretta@unito.it

Felice Cardonefelice@di.unito.it

1 Tecniche di dimostrazione

Le conoscenze alle quali pervengono le scienze esatte si esprimono generalmente informa di proposizioni, frasi dichiarative con il verbo all’indicativo; per esempio:

(i) l’equazione x2 = 2 non ha soluzioni razionali.

Analogamente, in informatica possiamo esprimere la correttezza di un algoritmoa di ordinamento di vettori mediante la proposizione:

(ii) Per ogni vettore v, l’algoritmo a produce una permutazione degli elementidi v ordinata in ordine crescente.

La logica analizza queste proposizioni scomponendole in elementi che apparten-gono ad un numero ristretto di categorie grammaticali, mettendone in evidenzala struttura mediante una traduzione in formule di un opportuno linguaggioformale.

Una caratteristica delle proposizioni come (i) e (ii) e che la loro verita non puoessere stabilita mediante esperimenti. Nessun esperimento potra mai escluderel’esistenza di una soluzione razionale dell’equazione x2 = 2, ne un numero finitodi esperimenti sara mai sufficiente per stabilire la correttezza di un algoritmo. Perquesto la nozione di dimostrazione assume un’importanza centrale: e per mezzodi dimostrazioni che si stabilisce la verita di proposizioni come quelle degli esempi(i) e (ii).

Una dimostrazione ha l’aspetto di una serie di proposizioni concatenate inmodo tale che la conclusione (la proposizione da dimostrare) sia fatta dipendereda altre proposizioni mediante inferenze. La logica analizza la struttura delledimostrazioni formalizzandole come derivazioni, strutture di formule costruite inaccordo con le regole di inferenza opportunamente riformulate in modo da operaresu quei particolari oggetti simbolici che sono le formule.

Prima di studiare formalmente le derivazioni, consideriamo in modo ancorainformale alcuni esempi di schemi di dimostrazione.

Esempio 1.1 (Dimostrazione diretta). In questo esempio dimostriamo un enunciatodella forma

(1) A → B.

Una strategia generica che si puo applicare in questo caso consiste nel dimostrare Bavendo assunto A. Da un punto di vista operativo, assumere A significa poter usareA nella dimostrazione di B. Da un punto di vista semantico, assumere A significasupporre che A sia vera. Questo tipo di dimostrazione di A → B viene chiamataanche dimostrazione diretta. Graficamente, una dimostrazione diretta puoessere rappresentata cosı:

1

A (assunzione)...B

A → B (conclusione)

In questa rappresentazione di una dimostrazione, trascriviamo i passaggi che lacompongono uno per riga; le barre verticali servono a delimitare il campo di azionedi una assunzione. In questo caso, l’assunzione A si estende per tutte le righe delladimostrazione tranne l’ultima riga, in cui l’assunzione viene scaricata: mentrel’enunciato B dipende ancora da A, l’enunciato A → B non ne dipende piu,quindi si trova all’esterno della barra orizzontale, che evidentemente rappresentala struttura d’innestamento dei campi di azione delle assunzioni.

Spesso si vuole dimostrare una proposizione A per tutti i valori di una varia-bile x scelti in un certo insieme. Una strategia che puo essere adottata in questicasi consiste nel dimostrare la proposizione A per un valore generico di x: poicheniente distingue il valore generico scelto per x da tutti gli altri, la proposizione valeallora per tutti i valori di x. Non sempre questa strategia e sufficiente: vedremoche per dimostrare una proprieta per tutti i numeri naturali e spesso necessarioricorrere al principio di induzione.

Si ricordi che un numero intero n e pari se n = 2k per qualche intero k. Analoga-mente, n e dispari se n = 2`+1 per qualche `. Vediamo una dimostrazione direttadell’enunciato seguente:

Per tutti i numeri interi n ed m, se n e dispari e m e pari︸ ︷︷ ︸A

allora n + m e dispari︸ ︷︷ ︸B

Per la dimostrazione: siano n ed m interi qualsiasi, ed assumiamo

n e dispari e m e pari.

Bisogna dimostrare che n + m e dispari. Per definizione n = 2` + 1 per qualcheintero `, mentre m = 2k per qualche intero k. Percio

n + m = (2` + 1) + 2k

= (2` + 2k) + 1

= 2(` + k) + 1

che dimostra che n + m e dispari perche ha la forma 2j + 1 (basta prenderej = ` + k).

Esercizio 1.2. Si dia una dimostrazione diretta del fatto che, se n e pari, alloran2 e divisibile per 4.

2

Esercizio 1.3. Dimostrare i seguenti enunciati utilizzando la tecnica appropriata:

1. Per tutti i numeri interi n, m, se n ed m sono pari allora n + m e pari.

2. Per tutti i numeri interi n, m, se n ed m sono dispari allora n + m e pari.

3. Per tutti i numeri interi n, m, se n ed m sono pari allora nm e pari.

4. Per tutti i numeri interi n, m, se n ed m sono dispari allora nm e dispari.

5. Per tutti i numeri interi n, m, se n e pari ed m e dispari, allora nm e pari.

Esercizio 1.4. Siano a e b due numeri reali. Si definisce il minimo min(a, b) traa e b nel modo seguente:

min(a, b) =

{a if a ≤ b;

b if a > b.

Si dia una dimostrazione diretta dell’enunciato:

Se x ≤ min(a, b), allora x ≤ a e x ≤ b.

Esempio 1.5 (Dimostrazione per assurdo). Una dimostrazione per assurdo euna dimostrazione di una proposizione A che assume che A sia falsa e da questaassunzione deriva una contraddizione, una proposizione della forma C ∧ ¬C(dove C e una proposizione qualsiasi). In particolare, una dimostrazione per as-surdo di una proposizione della forma (1) assume che A sia vera e che B sia falsa,e da queste assunzioni deriva una contraddizione. Una dimostrazione con questastruttura viene anche chiamata una dimostrazione indiretta.

Vediamo una dimostrazione per assurdo dell’enunciato:

Per tutti i numeri reali x, y, se x + y ≥ 2︸ ︷︷ ︸A

allora x ≥ 1 oppure y ≥ 1︸ ︷︷ ︸B

.

Si osservi che assumere che ‘x ≥ 1 oppure y ≥ 1’ sia falsa e equivalente ad assumereche x < 1 e y < 1. Siano x e y numeri reali qualsiasi, e supponiamo che:

x + y ≥ 2

x < 1

y < 1

Allora x + y < 1 + 1 = 2, quindi x + y < 2, ma questo contraddice la nostra primaassunzione, e questo dimostra (per assurdo) che se x + y ≥ 2 allora x ≥ 1 oppurey ≥ 1.

3

Esercizio 1.6. Dimostrare che, se 100 palline vengono distribuite in 9 scatole,almeno una scatola contiene non meno di 12 palline.

Esercizio 1.7. Dimostrare che, se 40 monete vengono distribuite in 9 borse inmodo tale che nessuna borsa sia vuota, almeno due borse contengono lo stessonumero di monete.

Dimostriamo ora l’enunciato:

Per ogni numero intero n, se n2 e pari︸ ︷︷ ︸A

allora n e pari︸ ︷︷ ︸B

.

Usiamo una dimostrazione diretta, assumendo che n2 sia pari. Vorremmo conclu-dere che n e pari. Per arrivare a questa conclusione usiamo una dimostrazione perassurdo, cioe assumiamo che n sia dispari e facciamo vedere che questa assunzioneporta ad una contraddizione. Sia n dispari: allora n = 2m + 1 per qualche interom. Allora possiamo calcolare:

n2 = (2m + 1)2(2)

= 4m2 + 4m + 1

= 2(2m2 + 2m) + 1

che dimostra che n2 e dispari, che contraddice la prima ipotesi. Allora abbiamodimostrato (per assurdo) che n e pari, quindi abbiamo dimostrato (in modo diretto)che se n2 e pari, allora n e pari, per ogni intero n.

Graficamente, la struttura di questa dimostrazione potrebbe essere rappresentatain questo modo:

n2 pari (assunzione della dimostrazione diretta)n dispari (assunzione della dimostrazione per assurdo)...¬(n2 pari) (per (2))n2 pari (per ipotesi della dimostrazione diretta)

n pari (conclusione della dimostrazione per assurdo)n2 pari → n pari (conclusione della dimostrazione diretta)

Il prossimo esempio introduce una tecnica che puo essere utilizzata per semplificarela dimostrazione che abbiamo appena visto.

Esempio 1.8 (Dimostrazione per contrapposizione). Per dimostrare un enunciatodella forma (1), si puo anche dimostrare (in modo diretto) l’enunciato equivalente:

(3) ¬B → ¬A.

Per esempio, si dimostra per contrapposizione l’enunciato:

4

Per ogni numero intero n, se n2 e pari︸ ︷︷ ︸A

allora n e pari︸ ︷︷ ︸B

.

dimostrando (in modo diretto) l’enunciato:

per ogni numero intero n, se n e dispari︸ ︷︷ ︸¬B

allora n2 e dispari︸ ︷︷ ︸¬A

Sia n un intero qualsiasi, e si assuma che n sia dispari; bisogna dimostrare allorache anche n2 e dispari. Se n = 2k + 1 per qualche intero k, abbiamo

n2 = (2k + 1)2

= (4k2 + 4k + 1)

= 2(2k2 + 2k) + 1

quindi n2 e pari, percio l’enunciato e dimostrato.

Esempio 1.9 (Dimostrazione per casi). Quando si deve dimostrare un enuncia-to della forma (1) dove A ha la forma A1 ∨ A2 ∨ . . . ∨ An, si puo cercareequivalentemente di dimostrare tutte le implicazioni

(A1 → B) ∧ . . . ∧ (An → B).

Per esempio, si puo usare una dimostrazione per casi del seguente enunciato:

Per ogni numero reale x, x ≤ |x|.

Distinguiamo due casi:

• x < 0: in questo caso, si ricordi che |x| = −x, quindi |x| > 0 > x percio|x| ≥ x;

• x ≥ 0: |x| = x ≥ 0 anche in questo caso.

Si puo allora concludere che x ≤ |x| per ogni reale x.

Esercizio 1.10. Si dimostri che per tutti i numeri reali x, y, min(x, y)+max(x, y) =x + y.

5

2 Dal linguaggio naturale alla logica

Questa sezione e l’adattamento di un capitolo delle dispense del corsodi Logica Matematica tenuto dal Prof. Gabriele Lolli per il Corso diLaurea in Informatica fino all’anno 2008. Il segno

�

a margine (“curva pericolosa”) segnala un passaggio particolarmentedelicato, sul quale vale la pena soffermarsi.

La prima competenza che bisogna acquisire e quella della formalizzazione, ovverodella traduzione di frasi della lingua naturale o del gergo matematico — che eun misto di formule e di parole — in espressioni di un linguaggio semplificato,schematico e dalla sintassi precisa.

Le frasi che si prendono in considerazione formano un sottoinsieme della to-talita delle frasi. Non si considerano espressioni di interrogazione, esclamazione ocomando, ma solo frasi dichiarative. Ci si riduce, come primo livello di sempli-ficazione, a frasi elementari che esprimono fatti, e a loro combinazioni medianteparticelle logiche.

Non si considerano inoltre frasi con indicatori di tempo e luogo (tempi deiverbi, avverbi di tempo, luogo e modo).

La semplificazione e guidata dalla volonta di restringersi ad espressioni mate-matiche.

Si devono evitare ambiguita e ridondanze, con l’obiettivo di capire e far emer-gere la struttura logica. Una frase come

La vecchia porta la sbarra

e ambigua perche non e chiara la sua struttura sintattica: se “vecchia” sia unaggettivo sostantivato o un aggettivo, se “porta” e “sbarra” siano sostantivi (nomi)o forme verbali.

Una frase come

Giovanni vede Mario che e malato e piange

e ambigua per ragioni di scansione, occorrono delimitatori come le virgole.

2.1 Predicati e relazioni

Noi saremo interessati a linguaggi simbolici in cui formiamo proposizioni a partireda nomi o da altre proposizioni mediante operazioni che corrispondono a modi dicostruzione delle proposizioni che si trovano nei linguaggi naturali (in particolare,

6

l’italiano). Nella logica simbolica, tuttavia, resta ben poco della struttura alta-mente complessa di un linguaggio naturale. Per esempio, vengono dimenticati gliavverbi, i tempi, le persone ed i modi dei verbi, i verbi e gli aggettivi vengonoin molti casi identificati. C’e una motivazione storica per questo impoverimentodi struttura: nel ragionamento matematico, che e stata la motivazione principaleper lo sviluppo della logica matematica (o formale, o simbolica), risulta superfluoconsiderare modo, tempo e persona dei verbi, e parti del discorso come avverbi.Possiamo dare quasi una definizione:

con proposizione si intendera sempre una frase dichiarativa, per laquale abbia senso chiedersi se e vera o falsa (in un contesto determina-to).

E piu difficile spiegare esattamente che cosa si intendera con nome: in gene-rale verra sottintesa una competenza linguistica preesistente, basata sulla nostraesperienza di parlanti di un linguaggio naturale, che ci permette di riconoscereintuitivamente quando un sintagma si comporta come un nome.

In logica, per definizione, ci occupiamo della struttura logica delle proposizioni.Questa struttura e il risultato di un’analisi che risente di presupposti filosofici eche, proprio per questo, e cambiata attraverso i secoli.

Tanto per introdurre il nostro argomento e per apprezzare meglio il contributodella logica formale, vediamo brevemente un’analisi delle proposizioni come e statapraticata per quasi due millenni, a partire da Aristotele (384 a. C. – 322 a. C.).Secondo Aristotele, una proposizione come

Socrate e mortale

puo essere vista come un esempio di uno schema

(4) S e P

dove S e il soggetto e P e il predicato, mentre il verbo essere che esprimel’attribuzione del predicato al soggetto e detto copula. Nella teoria aristotelicadel sillogismo, che e la teoria della dimostrazione sviluppata da Aristotele, ogniproposizione che compare all’interno di un sillogismo ha la forma (4). Oltre a nomidi individui, al posto della variabile S possiamo avere anche i seguenti terminigenerali:

(A) Ogni X,

(I) Qualche X,

(E) Nessun X, e

7

(O) Non ogni X.

Gia analizzando le proposizioni secondo lo schema (4) si puo progredire note-volmente verso una classificazione delle proposizioni da un punto di vista logico,cioe verso un utilizzo delle proposizioni all’interno di dimostrazioni corrette. Peresempio, alla base della logica aristotelica si trova il seguente quadrato delleopposizioni:

(A) contrarie

contraddittorieIII

I

IIII

(E)

uuuuuuuuu

(I) subcontrarie (O)

In questo quadrato le lettere indicano i corrispondenti tipi di soggetto di ciascunaproposizione:

Proposizioni contraddittorie non possono essere entrambe vere enon possono essere entrambe false (es.: “Tutti gli X sono P” e “QualcheX non e P”; “Qualche X e P” e “Nessun X e P );

Proposizioni contrarie non possono essere entrambe vere, ma pos-sono essere entrambe false (es.: “Tutti gli X sono P” e “Nessun X eP”);

Proposizioni subcontrarie possono essere entrambe vere (es.: “Qual-che X e P” e “Qualche X non e P”).

Il passaggio dalla logica tradizionale, aristotelica, alla logica moderna avvienecon i lavori del logico Gottlob Frege (1848 – 1925) verso la fine del 1800. La pro-posta di Frege e semplice: invece di analizzare le proposizioni come nello schema(4), cioe secondo una struttura soggetto/predicato, queste vengono analizzate se-condo una struttura funzione/argomento. Vedremo in che senso questo e possibile,e quali sono i vantaggi di questo cambiamento di prospettiva per l’espressivita delformalismo logico. Diventera evidente, per esempio, che l’analisi aristotelica delleproposizioni in termini di soggetto e predicato, anche usando i termini generali,non si puo estendere in modo da riuscire a distinguere le due possibili letture dellaproposizione:

Ogni uomo ha ballato con qualche donna,

vale a dire:

(i) Per ogni uomo c’e una donna con la quale ha ballato.

(ii) C’e una donna con la quale ogni uomo ha ballato.

8

Le frasi elementari nel linguaggio naturale sono di diverso tipo, ma in tutte sipuo individuare un soggetto, un verbo e un complemento (eventualmente piu sog-getti e piu complementi, o nessuno). I verbi possono essere intransitivi o transitivi,ed esprimere stati o azioni.

Nella terminologia logica si introducono “predicati” (o “proprieta”) e “relazio-ni”; i primi corrispondono ai verbi intransitivi e alla copula “essere”, le seconde aiverbi transitivi.

Si dice che una proprieta e goduta da un soggetto, o che un soggetto ha unadeterminata proprieta o che soddisfa un predicato. Si dice anche che una proprietae predicata di un soggetto, espressione dalla quale si vede il collegamento tra i duetermini.

Con “la rosa e profumata” o “la rosa profuma” si esprime il fatto che la rosa hauna proprieta, quella di essere profumata. Lo stesso se si dice “la rosa ha profumo”.Il verbo “avere” in generale indica possesso, ma non in questo caso. In “Giovanniama Maria” invece1 il verbo “amare” ha un soggetto e un complemento oggetto;in logica si dice che sussiste una relazione tra Giovanni e Maria, o che Giovanni eMaria stanno nell’ordine in una relazione, che e la relazione (non simmetrica) diamore.

Tutti i verbi si potrebbero standardizzare nella forma della attribuzione diuno stato a uno o piu termini, e questo corrisponderebbe ad avere un solo verbo,la copula “essere”, nelle due versioni “essere qualcosa” per i verbi intransitivie “essere nella relazione . . . con” per i verbi transitivi. Questo e il motivo percui nella trattazione formale si usera la dizione unica “predicati” per proprieta erelazioni, distinguendo quelli a un argomento (proprieta) da quelli a piu argomenti(relazioni). Il “numero di argomenti” e il numero di entita a cui si applica ilpredicato. Ma informalmente si preferisce distinguere tra predicati in senso stretto(a un solo argomento, o predicati monadici), e relazioni (a piu argomenti).

La frase “Giovanni dorme” puo diventare “Giovanni ha la proprieta di staredormendo” (o “Giovanni e addormentato”, “Giovanni sta dormendo”, “Giovannie nello stato di sonno”).

“Giovanni possiede un Piaggio 50” diventa “la relazione di possesso sussistetra Giovanni e un Piaggio 50”, o meglio come vedremo “la relazione di possessosussiste tra Giovanni e una cosa, e questa cosa e un Piaggio 50”.

Le frasi matematiche elementari, uguaglianze e disuguaglianze, “e uguale a”, “eminore di”, rientrano in questa tipologia. Cosı quelle insiemistiche con “appartienea”, cioe “e un elemento di”.

Alcune frasi possono essere rese sia mediante relazioni che mediante predicati;dipende da come si definiscono le relazioni e i predicati. In “Giovanni e amico

1O “Maria e amata da Giovanni”, la distinzione tra forma attiva e passiva e inessenziale, salvoche dal punto di vista psicologico.

9

di Mario” si puo considerare la proprieta “essere amico di Mario” e attribuirlaa Giovanni, oppure la relazione “essere amico di” e affermare che sussiste traGiovanni e Mario.

Non si puo dire che una sia giusta e l’altra no; dipende dal contesto; se do-po la prima osservazione si vuole aggiungere che Giovanni piange perche Mario emalato, e bisogna quindi citare di nuovo Mario, si deve usare il nome “Mario” eallora e meglio la versione relazionale, perche in quella con il predicato in nome“Mario” scompare, nella versione formalizzata, assorbito dal simbolo per il predi-cato: “essere amico di Mario” in quanto predicato, nell’analisi logica, e una unitalinguistica non scomponibile, anche se espressa in italiano da una successione diparole tra le quali compare “Mario”.

Le relazioni a due argomenti, come quelle viste negli esempi, si chiamano bina-rie. Le relazioni non sono solo binarie: “il punto C giace tra A e B” e un esempiodi una relazione ternaria, o tra tre termini.

2.2 Termini

I soggetti o gli oggetti, piu in generale i termini tra cui sussiste una relazione,sono indicati da vari costrutti linguistici. Il piu semplice e il nome proprio, come“Giovanni” e “Maria”. Gli altri sono le descrizioni e i nomi comuni.

In “Maria ama il padre di Giovanni”, “padre di Giovanni” e una descrizione,ben precisa, di una persona. Analogamente “il quadrato di 2” e una descrizionedi un numero; entrambe le descrizioni sono ottenute applicando una funzione2, nelprimo caso “padre di” nel secondo “il quadrato di”, a descrizioni piu semplici, chein questi esempi sono nomi. Si possono dare descrizioni piu complesse, come “lamadre del padre di Giovanni” o “meno il quadrato di 2”.

I nomi comuni richiedono una trattazione indiretta. Nella frase “Giovannipossiede un Piaggio 50”, il Piaggio 50 di Giovanni e uno di una categoria di cosesimili; “Piaggio 50” non e un nome proprio, ma un nome comune; e in effetti unpredicato, ragione della versione sopra proposta per la frase, che Giovanni possiedeuna cosa che ha la proprieta di essere un Piaggio 50. Questa frase non e piu tuttaviaelementare, e in effetti la congiunzione di due frasi: “Giovanni possiede una cosa”e “questa cosa e un Piaggio 50”.

Da questo esempio si vede la necessita di chiarire ancora almeno tre aspetti:come rendere “cosa”, come rendere la congiunzione delle due frasi, e come rendere“questa cosa”, che nella seconda frase stabilisce un collegamento con la prima.

2Preciseremo in seguito cosa sono le funzioni dal punto di vista matematico.

10

2.3 Connettivi

Le particelle logiche della lingua italiana sono parole come “e”, “oppure”, “se” ealtre, che collegano frasi di senso compiuto. Nella lingua italiana queste parole dauna parte sono polivalenti e ambigue, hanno diversi sensi — in generale discriminatidal contesto — e dall’altra si presentano in tante versioni equivalenti.

La congiunzione “e” puo ad esempio essere resa da una virgola, da “e anche”,da “ma” e ancora altre espressioni. Il senso avversativo di “ma” e uno degliaspetti che vengono lasciati cadere nel passaggio ad un linguaggio formalizzato,in quanto esprime un’aspettativa soggettiva. La congiunzione e resa anche dacostrutti piu complicati, come “sia . . . sia”: “parto sia che piova sia che faccia beltempo” significa “se fa bel tempo parto, e se piove parto”, magari con l’aggiuntadi un “ugualmente” che di nuovo esprime una determinazione soggettiva.

La stessa congiunzione talvolta esprime qualcosa di piu o di diverso dalla sem-plice affermazione di entrambe le proposizioni congiunte; talvolta puo significare“e poi”, come in “si sposarono e vissero felici”; talvolta significa “e quindi”, comein “si immerge una cartina di tornasole, e diventa rossa” (se questa frase e intesanon come una descrizione di avvenimenti, nel qual caso “e” significa “e dopo”, macome come una caratterizzazione di particolari sostanze).

La disgiunzione, “o” o “oppure”, talvolta ha un senso debole (“uno o l’altroo tutt’e due”), talvolta un senso esclusivo (“uno o l’altro ma non tutt’e due”).L’affermazione “piove o c’e il sole” e compatibile con la situazione in cui pioveda una nuvola anche se c’e il sole. Il latino aveva due parole diverse vel e aut,ma la distinzione non e rimasta nelle lingue moderne. Sara invece ripristinata neilinguaggi formali. La differenza qualche volta e espressa dalla semplice ripetizionedi “o” (“o piove o c’e il sole”) ma piu spesso dall’enfasi della pronuncia; il tono eil contesto devono essere tenuti presenti per capire il significato inteso. C’e volutodel tempo per tornare a riconoscere due particelle diverse, e anche per accettarevel come disgiunzione:

Alcuni dicono che per la verita di una disgiunzione si richiede sempreche uno dei disgiunti sia falso, perche se entrambi fossero veri nonsarebbe una vera disgiunzione, come dice Boezio. Questo pero non mipiace. In realta io dico che se entrambe le parti di una disgiunzionesono vere, l’intera disgiunzione e vera (Walter Burleigh, De Puritate,XCI, 3-19, XIV sec .)

La disgiunzione in italiano talvolta e resa con “ovvero”, ma questa parolasignifica anche “cioe”, “vale a dire”, cioe una precisazione, non un’alternativa.

La “o” si esprime anche con “altrimenti” come in “Lasciate un messaggio,altrimenti non sarete richiamati”, solo apparentemente piu ingiuntiva della versionecon la “o”.

11

Qualche volta la stessa frase puo essere espressa sia con la “e” che con la “o”. Sipuo dire equivalentemente sia “Tutti, bianchi o neri, hanno un’anima”, sia “Tutti,bianchi e neri, hanno un’anima”. L’affermazione “mele e pere sono frutti” vuoleanche dire che “una cosa che sia una mela o una pera e un frutto”.

La negazione di una frase si realizza in diversi modi, di solito con la particella“non”, inserita pero (o soppressa) in vari modi nella frase da negare, con diversicostrutti che coinvolgono altre parole, in particolare i verbi. Da “piove” a “nonpiove”, o “non e vero che piove”; da “qualche volta piove” a “non piove mai”;da “piove sempre” a “qualche volta non piove”; da “non ama nessuno” a “amaqualcuno”, da “e bello” a “e brutto”, e cosı via. Per negare “non piove” non sidice “non non piove” ma “piove” o “non e vero che non piove”.

Per mettere in evidenza proprieta delle particelle logiche, che non dipendonodal significato delle frasi che connettono, negli esempi proposti useremo d’ora inavanti le lettere A, B, . . . per indicare frasi imprecisate, e scriveremo: “A e B”,“A oppure B” e simili.

La parola “se” e un’altra particella dai molteplici sensi, e dalle molteplici rese,ad esempio con “B, se A”, “A solo se B”, “se A allora B”, “A implica B”, “A, �

quindi B” — ma “quindi” ha anche un significato temporale, come “poi”.Quando si afferma “se A allora B”, A e detta condizione sufficiente per B, e B

condizione necessaria per A. “A e condizione sufficiente per B” e “B condizionenecessaria per A” sono altri modi di esprimere “se A allora B”.

Al “se . . . allora” sara dedicata una discussione speciale per la sua importanzarispetto all’inferenza logica.

Spesso “se . . . allora” non e presente in frasi che tuttavia esprimono quel tipo dicollegamento: “un numero primo maggiore di 2 e dispari” significa “se un numeroe primo e maggiore di 2 allora e dispari”. Torneremo sull’argomento.

In considerazione delle ambiguita e molteplicita di espressione messe in luce, unprimo passo e quello di introdurre una sola versione fissa delle particelle logiche, siacome simboli che come significati; fatto questo tuttavia, la competenza piu impor-tante consiste poi nel saper tradurre le frasi della lingua naturale, disambiguandolequando necessario e possibile, e trovando la versione formale corrispondente.

La precedente discussione non esaurisce certo la complessita della lingua, ma estata proposta a titolo esemplificativo. Solo una costante (auto)analisi delle varieforme espressive (leggi: tanti esercizi) aiuta a riconoscere le varie insidie.

La standardizzazione e necessaria per poter comunicare con le macchine; maprima di parlare alle macchine occorre parlare ad altre persone e a se stessi percostruire gli algoritmi. Nell’apprendere a formalizzare si deve anche raffinare lapropria logica naturale.

Tuttavia non esiste un elenco completo di quelle che nei linguaggi naturali siriconoscono come particelle logiche. Non abbiamo menzionato ad esempio “ne

12

. . . ne”, o “a meno che”.3 Qualche volta, parole che non sembrano particelle logi-che possono essere usate in questo modo, e lo si riconosce nella formalizzazione:“quando” e di solito una determinazione temporale, ma “quando piove, prendol’ombrello” viene resa quasi necessariamente da “se piove, prendo l’ombrello”.

Nell’ottica della formalizzazione, chiedere cosa significa “quando piove, prendol’ombrello” non e altro che la richiesta di tradurre la frase in un’altra in cui compaiauna delle particelle logiche riconosciute tali e scompaia “quando”, se non e traquelle; cosı si vede a quale delle particelle note la parola e equivalente; ma nonsempre e evidente una possibile riduzione di una frase ad un’altra, ne sempre unasola.

Esistono peraltro parole anche di difficile catalogazione, che sembrano particellelogiche in quanto legano due frasi, ma hanno sfumature importanti che si perdononella formalizzazione: ad esempio “siccome piove, prendo l’ombrello”, o “prendol’ombrello perche piove” potrebbero essere espresse dall’asserzione unica “la pioggiae la causa del mio prendere l’ombrello”, che coinvolge peraltro la delicata parola“causa”; le frasi contengono tuttavia una determinazione temporale implicita (“stapiovendo”), o anche una qualitativa (un riferimento forse a un particolare tipo dipioggia — a dirotto) che non le rende del tutto equivalenti a “quando piove, prendol’ombrello” o a “la pioggia e la causa del mio prendere l’ombrello”.

Esistono parimenti frasi che ne assommano diverse; la stessa “siccome piove,prendo l’ombrello” invece che una frase puo essere considerata un argomento, poi-che in essa si afferma un fatto, che piove, oltre a un legame condizionale. Potrebbecorrispondere ad un esempio di modus ponens (si vedra a suo tempo): “Se piove,prendo l’ombrello. Piove. Quindi prendo l’ombrello”.

Useremo simboli speciali per rappresentare alcune particelle logiche che sembra-no di uso piu comune, almeno nei discorsi meno sofisticati. Per queste si potrebberousare parole della lingua italiana — o comunque di una lingua naturale — fissandoper convenzione in modo rigido il loro significato, come si fa ad esempio quandoper la congiunzione si usa and, in informatica. Quando si usano and e simili, sivuole che il linguaggio sia friendly perche ci si deve concentrare su altro; noi invecevogliamo concentrarci proprio su quelle parole, per cui sono meglio simboli nuovi,insoliti, che sorprendano.

Useremo per le particelle logiche i simboli:

¬ per la negazione∧ per la congiunzione

3Si noti l’uso della “o” nella nostra frase, di nuovo scambiabile con “e”: si voleva dire che nonabbiamo menzionato “ne . . . ne” e non abbiamo menzionato “a meno che”; avremmo potuto direche non abbiamo menzionato ne “ne . . . ne” ne “a meno che”, usando proprio “ne . . . ne”; l’uso di“o” suggerisce un’altra versione equivalente: “una particella che sia “ne . . . ne” o “a meno che”non e stata menzionata”.

13

∨ per la disgiunzione inclusiva⊕ per la disgiunzione esclusiva→ per il condizionale “se . . . allora”↔ per il bicondizionale “se e solo se”

senza escluderne a priori altri, e li chiameremo connettivi proposizionali. La ne-gazione e un connettivo unario (cioe agisce su una proposizione), gli altri indicatisono connettivi binari (cioe connettono due proposizioni).

Fissare i simboli e come decidere che in italiano la congiunzione si esprimesempre con“e” e non in altri modi. Per evitare invece la molteplicita di sensooccorrera in seguito dare regole opportune.

La scelta di simboli artificiali e piu vantaggiosa anche perche, procedendo, que-sti simboli non saranno soltanto abbreviazioni, ma insieme ad altri diventerannouna struttura che e essa stessa, se si vuole, oggetto di una teoria matematica, consuoi problemi specifici.

Ad esempio una prima questione, comprensibile anche solo sulla base di quan-to detto finora, e se le particelle sopra scelte sono anche fondamentali, e in chesenso, o se sono sufficienti, o quante ce ne potrebbero essere. Un’altra riguardal’equivalenza, affermata per alcuni esempi precedenti, tra frasi diverse espresse conparticelle diverse.

2.4 Variabili

Torniamo a quanto lasciato in sospeso, a come rappresentare “una cosa” e “questacosa”. Nella grammatica, un ruolo fondamentale e svolto dai pronomi, che sipresentano in grande varieta, come “uno”, “chiunque”, “ogni”, “qualche” e simili.

I pronomi servono a formare nuove frasi collegandone alcune che hanno unriferimento in comune; nella frase “se uno ha un amico, e fortunato” si individuanodue proposizioni componenti “uno ha un amico” e “e fortunato”. La seconda frasenon presenta il soggetto, ma s’intende che e lo stesso della prima; si puo ripetere(“uno e fortunato”) oppure piu spesso, in altri casi, si deve precisare, con unindicatore che faccia capire esplicitamente che il soggetto e lo stesso (ad esempio“egli”, “costui” e simili).

Nella seconda di due frasi collegate, il soggetto della prima puo essere presentecome oggetto, ad esempio in “se uno e generoso, tutti ne dicono bene”, dove “ne”significa “di lui”.

Anche per questo tipo di parti del discorso, si hanno molte versioni equivalenti,ciascuna con i suoi vantaggi e la sua convenienza, ad esempio “chiunque abbiaun amico e fortunato”, “coloro che hanno un amico sono fortunati”; talvolta ad-

14

dirittura basta un’unica frase indecomponibile, come “i generosi sono lodati” per“coloro che sono generosi sono lodati”4.

E necessario comunque mettere in rilievo il fatto che entrambe le frasi hanno unriferimento comune; se si formalizza la frase “se uno ha un amico, uno e fortunato”introducendo una lettera A per la prima e una lettera B per la seconda, si ottieneA → B che non mostra la struttura fine della frase, e non permette quindi diindagare se sia vera o no.

Il simbolismo deve essere arricchito. L’uso dei pronomi e standardizzato permezzo di simboli che si chiamano variabili: x, y, . . .. Il simbolo x sta per “unacosa”, “uno”, “una persona” se il discorso si riferisce a esseri umani, “un numero”se il discorso si riferisce ai numeri e cosı via.

La variabile e creduta un elemento alieno del linguaggio, che compare solo neisimbolismi matematici, ma non e cosı. “Se uno ha un amico, e fortunato” equivalenella semiformalizzazione a: “se x ha un amico, x e fortunato”.

Avendo introdotto questi simboli speciali, come peraltro abbiamo gia fattocon i connettivi, tanto vale utilizzare anche altre schematizzazioni e completare ildistacco del lessico naturale.

Introduciamo percio simboli per designare predicati, e altri per costruire ter-mini, che corrispondono alle descrizioni.

Useremo preferibilmente

le lettere P , Q, R, . . . per predicati e relazionile lettere f , g, . . . per funzionile lettere a, b, c, . . . per costanti (nomi propri)le lettere x, y, . . . con o senza indici, per variabili.

La struttura di una frase del tipo “Giovanni dorme” e rappresentata da “dor-me(Giovanni)”, o

P (a).

“Giovanni ama Maria” da “ama(Giovanni, Maria)”, o

R(a, b).

Questa notazione5 e volutamente analoga a quella delle funzioni, in quanto si pensache un predicato o una relazione si applichino ai soggetti interessati; si potrebberoanche pensare come funzioni, aventi come valori “vero” e “falso”.

4La possibilita di questa espressione e all’origine di una diversa analisi del linguaggio, che haportato alla prima logica formale della storia, nell’opera di Aristotele, come vedremo trattandoi sillogismi.

5La preciseremo in seguito.

15

Piu in generale, i termini a cui si applica la relazione non sono necessariamentecostanti, o nomi, ma anche descrizioni, come “Il padre di Giovanni ama Maria”,che diventa

R(f(a), b),

o descrizioni incomplete, cioe contenenti variabili, come

“Uno dorme”: P (x).

Tuttavia la rappresentazione grafica scelta per i simboli non e essenziale, percomodita di traduzione si possono anche usare altre lettere, come le iniziali delleparole italiane (A per “essere amici”), o addirittura complessi di lettere o paroleintere, magari in caratteri particolari, come amici(x, y).

Anche la particolare forma R(a, b) non e rigida, talvolta puo essere sostituitada a R b. Questo succede in particolare con i simboli per tradizionali relazionimatematiche che hanno adottato tale notazione: x < y, x = y.

Volgiamoci ora alla formalizzazione della frase “Giovanni possiede un Piaggio50”, gia trasformata sopra in “Giovanni possiede una cosa, e questa cosa e unPiaggio 50”: con una costante g per “Giovanni”, un simbolo di relazione R per“possedere”, un simbolo di predicato P per “Piaggio 50”, si puo provare a scrivere

R(g, x) ∧ P (x),

ma non e sufficiente.

2.5 Quantificatori

L’uso delle variabili o della loro versione con pronomi presenta aspetti delicati pertrattare i quali il formalismo finora introdotto non e abbastanza discriminante.

Se si dice “A Giovanni piace il Piaggio 50” si intende che a Giovanni piaccionotutti i Piaggio 50, anche se probabilmente desidera averne solo uno (comunque nontutti); se si usa R(y, x) per la relazione “a y piace x” la frase diventerebbe ugualealla precedente, pur avendo un altro senso (in particolare puo essere vere o falseindipendentemente l’una dall’altra).

Nella frase “se uno ha un amico, e fortunato” ci sono due tipi di “uno”, ilprimo “uno” e il soggetto, presente tacitamente anche come soggetto di “e fortu-nato”, e il secondo e l’“un” di “ha un amico”6. Il primo “uno” significa “chi”, nelsenso di “chiunque”, il secondo significa “qualche”. La stessa parola “uno”, e lecorrispondenti variabili x e y possono cioe avere sia un senso universale che unoparticolare.

6Non c’e differenza tra “uno” e “un”; si potrebbe dire in entrambi i casi “una persona”,ristabilendo l’uniformita.

16

Anche se il senso della frase e ovvio, per chiarezza e meglio dire “chiunqueabbia qualche amico e fortunato”. Cosı si potrebbe dire “A Giovanni piace unqualunque Piaggio 50” o “A Giovanni piacciono tutti i Piaggio 50” o “A Giovannipiacciono i Piaggio 50”. La varieta di costrutti linguistici disponibili nelle linguenaturali ha la funzione di evitare possibili ambiguita in altre frasi di non immediatadecifrazione.

Un esempio di frase ambigua, se presa isolatamente, e “uno che segue il corsodi Logica si addormenta”. Il professore spera che voglia solo dire che si conosceuno studente che tende ad addormentarsi, ma magari gli studenti intendono chetutti si addormentano sempre.

L’uso delle variabili da sole non risolve le ambiguita, anzi le potrebbe accrescere,se vengono a mancare le differenze di significato dei pronomi specifici; in “se x ha ycome amico, x e fortunato”, se y fosse presa in senso universale, come la x, allorala frase significherebbe che chi e amico di tutti e fortunato, il che e discutibile,piuttosto e un santo.

Un altro esempio e il seguente: nelle due frasi di argomento aritmetico

un numero moltiplicato per se stesso da 1

e

un numero sommato al suo opposto da 0

“un numero” e da intendersi in modo diverso; nel primo caso l’unico numero conquella proprieta e 1, e la frase potrebbe essere una sua descrizione estrapolata dalcontesto, o un indovinello: “quale e . . . ?”; nel secondo caso “un numero” significa“qualunque numero”.

La differenza non si coglie neanche se si formalizza, la prima frase con x ·x = 1e la seconda con x + (−x) = 0; per capire la differenza si deve pensare a qualispecifici numeri soddisfano le formule, −1 e 1 in un caso, tutti i numeri nell’altro.Nella terminologia usuale, la prima e un’equazione, la seconda un’identita.

Le variabili da sole non rendono la duttilita delle parole che indicano se si parladi uno, qualcuno o tutti.

Si introducono allora due simboli che si chiamano quantificatori,

∀ quantificatore universale

e∃ quantificatore esistenziale

e questi segni si premettono alle formule con variabili per segnalare che, nel lororaggio d’azione determinato dalle parentesi, le variabili stesse devono essere intesenel senso di “tutti” ovvero nel senso di “qualcuno”.

17

La frase “uno che ha un amico e fortunato” diventa, schematizzata,

∀x(∃y(A(x, y)) → F (x)).

L’uso delle parentesi sara codificato quando si studiera il formalismo, addirit-tura in modo pignolo. Per ora basti osservare che quando un quantificatore siriferisce a una variabile fissando il senso delle sue occorrenze, universale o parti-colare, in una frase, tutta la frase che contiene quelle occorrenze della variabile varacchiusa tra parentesi (nell’esempio, tutta la frase ∃y(A(x, y)) → F (x) per quelche riguarda x, e A(x, y) per quel che riguarda la y — cosa che e gia stata fatta7).

Quando si leggono frasi gia formalizzate, i quantificatori ∀x e ∃x si leggonousualmente sempre nello stesso modo: “per tutti gli x” (o “per ogni x”) e “esisteun x tale che” (o “esistono x tali che”), anche quando non e la lettura piu elegante.Invece in italiano ci sono diversi modi di esprimersi.

Alcune espressioni della lingua naturale hanno tuttavia significati colloquialiche non hanno interesse logico e che comunque non sono esprimibili nel formalismo.Anzi bisogna fare attenzione a non lasciarsi influenzare. Ad esempio “qualche”viene spesso usato per dire “pochi”, per indicare un certo numero ma non grande,e spesso maggiore di uno, che se e uno si dice “uno”. Invece ∃x vuol sempre dire �

“esiste almeno un . . . ”, e possono essere uno, dieci o centomila, o anche tutti.Quando si usa “qualche”, talvolta in italiano si sottintende “non tutti”8; in-

vece ∃x . . . e compatibile col fatto che tutti soddisfino la condizione; e solo un’af-fermazione piu debole: se si sa che tutti i gamberi sono rossi, si puo affermare∃x(gambero(x)∧ rosso(x)) come vero; naturalmente cosı non si afferma che tutti igamberi sono rossi (che sarebbe reso da ∀x(gambero(x) → rosso(x))) ma che esisteun gambero rosso.

Le variabili svolgono il ruolo di “uno”, “una cosa”, “un numero” e simili; diquale esattamente dipende dall’universo di discorso. Questo va precisato, in varimodi. Spesso la scelta dei predicati e delle relazioni suggerisce implicitamente dicosa si parla: se si usa una relazione A per “essere amico di . . . ” e implicito chesi parla di persone o animali. Allora ∀x(∃yA(x, y) → F (x)) si legge “ogni personao animale che abbia . . . ”.

Tuttavia e difficile che il discorso entro il quale si inserisce ∀x(∃yA(x, y) →F (x)) si limiti a persone o animali; nel prosieguo possono essere menzionate anchecose o idee. Al di fuori della matematica, dove e di solito ben precisato,9 l’universo

7In realta dopo A(x, y) la y non occorre piu e non c’e bisogno delle parentesi per una letteracorretta, come sara spiegato in seguito: scriveremo anche ∀x(∃yA(x, y) → F (x)).

8Da un compito in classe: “Se qualche triangolo isocele e equilatero, di conseguenza qualchetriangolo isocele non lo e”. La conclusione e vera, ma “di conseguenza” no, e l’unico modo perimmaginare come sia stata concepita e l’interpretazione di “qualche” come “non tutti”.

9Non sempre: s e si discute una equazione e non si precisa quale e il dominio numerico, lerisposte possono essere bene diverse.

18

di discorso e ricco e variegato. ∀x . . . si legge dunque “per ogni x . . . ” dove x apriori puo stare per gli elementi piu disparati.

In molte frasi tuttavia i quantificatori chiaramente non si riferiscono a tuttigli elementi dell’universo di discorso ma a parti piu ristrette; le frasi aritmeticheper esempio raramente iniziano con “tutti i numeri”, piuttosto con “tutti i numeripositivi”, o “tutti i numeri primi”; e raramente si parla di tutti gli esseri viventi,ma piuttosto di tutti gli uomini, o di tutte le donne, o di tutti gli italiani e cosıvia restringendo.

Nel formalismo logico la restrizione dei quantificatori avviene nel seguentemodo. La frase “tutti i tedeschi sono biondi” si rappresenta con due predicati, �

“tedesco” e “biondo”, e la forma

∀x(T (x) → B(x)),

dove il quantificatore ∀x e letto “per tutte le persone”, cioe con la x che varia sututto l’universo del discorso (la specie umana): “per ogni x, se x e tedesco allorax e biondo.

Questa forma e corretta grazie alle proprieta del condizionale, che vedremomeglio in seguito. Se T (x) → B(x) e vero per tutte le persone, allora ogni tedescorende vero il condizionale, l’antecedente e quindi vero il conseguente, ed e vero chetutti i tedeschi sono biondi; se viceversa e vero che tutti i tedeschi sono biondi,anche l’enunciato di sopra che si riferisce con ∀x non ai tedeschi ma a tutte lepersone e vero: se uno e tedesco, allora e biondo e il condizionale e vero; seGiovanni e biondo ma non e tedesco, lo si vorra considerare un controesempio chefalsifica l’affermazione? Non sembra ragionevole; si assume che T (Giovanni) →B(Giovanni) sia vero, e cosı T (x) → B(x) e vera per tutte le persone.

In pratica, gli aggettivi sono resi da predicati con l’ausilio del condizionale: in“tutte le persone tedesche sono bionde” l’aggettivo “tedesco” diventa il predicato“essere tedesco” e la frase “tutte le persone, se sono tedesche, sono bionde”.

“Tutti i P sono . . . ” e “qualche P e . . . ”, dove P delimita il campo di varia-bilita del riferimento, si realizzano dunque introducendo un predicato unario P escrivendo rispettivamente ∀x(P (x) → . . .) e ∃x(P (x)∧ . . .). Si noti ovviamente ladifferenza nel caso del quantificatore esistenziale, dove la restrizione e realizzata �

con la congiunzione, che viene dalla traduzione di “esiste uno che e P e che . . . ”.In particolare e da sottolineare che si usa un solo tipo di variabili; nella pratica

matematica talvolta se ne usa piu di uno, ad esempio in geometria lettere maiuscoleA, B, . . . per punti e minuscole r, s, . . . per rette. Ma ci si riconduce a un solo tipodi variabili usando gli opportuni predicati, ad e sempio “essere un punto” e “essereuna retta”.

19

2.6 Esempi:

2.6.1 dal linguaggio naturale. . .

Esempio 2.1. “Maria ama il padre di Giovanni” e formalizzata da

A(m, f(g)),

dove m e g sono costanti, m per “Maria” e g per “Giovanni”, ed f un simbolofunzionale per “il padre di . . . ”.

Esempio 2.2. Per formalizzare “Maria ama il figlio di Giovanni” non si puo usareun simbolo f per “il figlio di”, perche “figlio di” non e una funzione univoca: auna persona possono corrispondere diversi figli, o nessuno. Allora “Maria ama ilfiglio di Giovanni” si formalizza come sotto “Maria ama un figlio di Giovanni” e aparte si afferma che Giovanni ha un solo figlio (vedremo come).

Esempio 2.3. “Maria ama un figlio di Giovanni” e formalizzata da

∃x(A(m, x) ∧ F (x, g)),

letta

esiste un x tale che Maria ama x e x e figlio di Giovanni,

dove F e un simbolo relazionale a due posti, e F (x, y) sta per “x e figlio di y”.Si potrebbe anche dire “Maria ama uno, che e figlio di Giovanni” o “Maria ama

un tizio che e figlio di Giovanni”.In questo caso “figlio di Giovanni” ha la funzione di nome comune, come “Piag-

gio 50” in “Giovanni possiede un Piaggio 50”, e infatti si formalizza nello stessomodo.

Esempio 2.4. “Maria ama i figli di Giovanni”, che significa che Maria ama tutti ifigli di Giovanni, si formalizza con

∀x(F (x, g) → A(m,x))

e non con ∀x(A(m, x) ∧ F (x, g)); questa significa che tutti sono figli di Giovanni,e che Maria li ama tutti.

Per la formalizzazione corretta, puo essere utile vedere nella frase un caso diquantificatore ristretto, ai figli di Giovanni, leggendola “Tutti i figli di Giovanni,Maria li ama” o al passivo: “Tutti i figli di Giovanni sono amati da Maria”.

Esempio 2.5. “Non tutte le ciambelle riescono col buco”.Si scelga un predicato C per “essere una ciambella” e una relazione B(x, y) per

“x e un buco di y”. Quindi si trasforma la frase eliminando “non tutte” a favore

20

di “qualche ciambella non riesce col buco”. “Riuscire con buco” o “avere il buco”possono essere trattate come equivalenti: la prima versione allude al processo difabbricazione che finisce male, la seconda al risultato. Allora

∃y(C(y) ∧ ¬∃xB(x, y)).

Esempio 2.6. “Ogni rosa ha le sue spine”.Sia R il predicato “essere una rosa” e S(x, y) la relazione “x e una spina di y”.

∀x(R(x) → ∃yS(y, x)).

Si noti che se S(x, y) e la relazione “x e una spina di y”, S(y, x) si legge “y euna spina di x”. C’e grande liberta nell’uso delle variabili: ∃yS(y, x) si potrebbescrivere anche ∃zS(z, x); in italiano hanno la stessa traduzione “x ha qualchespina”. Quello che importa e non usare la stessa variabile quando devono esseredistinte: se si scrive ∃xS(x, x) si dice che c’e una rosa che e una spina.

Esempio 2.7. “Ogni rosa ha qualche spina”.La frase e la stessa di prima, perche se una rosa ha delle spine queste sono sue.

Entrambe possono comunque essere formalizzate anche in un altro modo, con unpredicato per “essere una spina” e una relazione binaria H di possesso:

∀x(R(x) → ∃y(S(y) ∧H(x, y))).

Esempio 2.8. “Chi rompe paga e i cocci sono suoi”.“Rompere” e verbo transitivo, salvo che in usi metaforici, quindi bisogna pen-

sare che si dica “chi rompe qualcosa, una qualunque cosa”; sia R(x, y) la relazione“x rompe y”; sia quindi C(x, y) la relazione che intercorre tra due pezzi di materiase il primo e un coccio dell’altro, cioe un pezzo che risulta dalla sua rottura; sce-gliamo la relazione S(x, y) a indicare che x paga il valore di y, e sia infine H(x, y)la relazione “x assume il possesso di y”. Allora

∀x∀y(R(x, y) → S(x, y) ∧ ∀z(C(z, y) → H(x, z))).

Il complesso ∀x∀y . . . si legge “per ogni x e per ogni y . . . ”. E anche lecitoabbreviare con ∀x, y . . ., cosı come ∃x∃y . . . con ∃x, y . . .. �

“Chiunque rompa qualunque cosa . . . ” o “Qualunque cosa uno rompa . . . ”sono equivalenti: in base a questa lettura e evidente che risultera che ∀x∀y . . . eequivalente a ∀y∀x . . . e che ∃x∃y . . . e equivalente a ∃y∃x . . ..

La precedente formula e tuttavia ambigua, e deve essere corretta in

∀x∀y(R(x, y) → (S(x, y) ∧ ∀z(C(z, y) → H(x, z))))

in modo che entrambe le conseguenze (pagare e tenere i cocci) dipendano daR(x, y). Altrimenti se si pensasse a (R(x, y) → S(x, y))∧ . . . la frase ∀z(C(z, y) →H(x, z)) significherebbe che x si prende i cocci di ogni cosa, che l’abbia rotta lui ono.

21

Esempio 2.9. “Un regalo conquista un amico”.Cominciamo a riformulare la frase spogliandola di significati metaforici (un

regalo e una cosa e non conquista nulla). Si intende ovviamente dire che chifa un regalo acquista un amico, e piu dettagliatamente che se una persona fa unregalo a un’altra persona, questa diventa suo amico. Usiamo una relazione ternariaR(x, y, z) per “x regala y a z” e una relazione binaria per A(x, y) “x diventa amicodi y”.

∀x∀y(∃zR(x, z, y) → A(y, x)).

Esempio 2.10. “A Natale si fanno regali agli amici”.Si intende che a Natale ognuno fa un regalo a ciascuno dei suoi amici. Non e

il caso di mettere in evidenza “Natale”, che non e rilevante per la struttura logicadella frase. Usiamo una relazione ternaria R(x, y, z) per “x a Natale regala y a z”e una relazione binaria A(x, y) per “y e un amico di x”.

∀x∀y(A(x, y) → ∃zR(x, z, y)).

Esempio 2.11. “Chi non risica non rosica”.“Risicare” e verbo intransitivo (anche se qualche volta si dice “ha rischiato

qualcosa”, ma si intende “ha rischiato un po’ ”). “Rosicare” e transitivo, anche senella frase non compare il complemento oggetto, ma si intende “non rosica nulla”.Usiamo un predicato R per “risicare” e una relazione S(x, y) per “x rosica y”.

∀x(¬R(x) → ¬∃yS(x, y)).

Esempio 2.12. “Sono eligibili tutti e soli gli studenti in corso”.Non interessa a cosa siano eligibili; serve un predicato per “essere eligibile”,

uno per “essere studente” e uno per “essere in corso”.

∀x(E(x) ↔ S(x) ∧ C(x)).

La dizione “tutti e soli” e strettamente legata a “se e solo se”. “Tutti gli studenti �

in corso sono eligibili” e formalizzata da

∀x(S(x) ∧ C(x) → E(x)),

mentre “solo gli studenti in corso sono eligibili” da

∀x(E(x) → S(x) ∧ C(x)).

La congiunzione di queste due ultime frasi e equivalente, come vedremo, alla prima.

22

2.6.2 . . . dalla matematica

Esempio 2.13. La frase “dati due numeri, uno minore dell’altro, esiste un terzonumero compreso tra i due”, vera nel campo dei razionali e in quello dei reali,falsa negli interi, puo essere resa da

∀x∀y(x < y → ∃z(x < z ∧ z < y)).

La congiunzione x < z ∧ z < y si puo abbreviare, secondo l’uso matematico, conx < z < y.

Non esiste un quantificatore che quantifichi sulle coppie; ci si comporta comese la frase fosse “dato un primo numero e dato un secondo numero . . . ”. Ma “unprimo” e “un secondo” servono solo a facilitare l’espressione, si sarebbe potuto direanche “dato un numero e dato un numero . . . ”, con qualche difficolta nel seguitoper i riferimenti appropriati.

Si faccia attenzione che neanche la presenza di “due” vuol dire che i numeridevono essere considerati diversi; tale forma comune di espressione distingue ilmodo, il momento in cui i numeri sono presentati, o pensati, ma non e escluso ingenerale che si presenti lo stesso numero due volte.

Nell’esempio 2.10 precedente, a Natale uno fa anche regali a se stesso, se sivuole bene.

“Dati due numeri” significa “fatta due volte la scelta di un numero”, e le sceltepossono cadere sullo stesso numero. In termini probabilistici, si tratta di sceltecon reimmissione; oppure si deve considerare che la scelta di un numero non lotoglie certo dall’insieme. “Dati due numeri, esiste la loro somma” si puo scrivere

∀x∀y∃z(z = x + y)

ma esiste anche la somma di ogni numero con se stesso; x e y possono prenderetutti i valori in tutte le combinazioni possibili, quindi anche valori uguali.

Quando tuttavia si mette come sopra la condizione “uno minore dell’altro” —come nella frase proposta — allora si esclude che possano essere uguali perche larelazione “minore di” non e riflessiva. Tuttavia lo si esclude solo attraverso unadeduzione, non con la semplice scrittura: se x e y denotano lo stesso numero,e bisogna considerare anche questo caso per verificare se la frase e vera, in x <y → ∃z(x < z ∧ z < y) l’antecedente x < y risulta falso (come nell’esempio deitedeschi).

Con “un terzo” di nuovo si vuol dire semplicemente “un numero”, e che siadiverso dai primi due segue automaticamente se “compreso” significa “strettamentecompreso”; altrimenti, se la relazione d’ordine fosse intesa come ≤ allora potrebbeanche essere uguale a uno dei due; non e questo il senso della frase, che vuoleesprimere la densita dell’ordine dei numeri reali — e anche dei razionali.

23

Se nella stessa formula il segno di relazione e interpretato su di una relazioneriflessiva, come

∀x∀y(x ≤ y → ∃z(x ≤ z ∧ z ≤ y)),

o piu in generale “se R e riflessiva allora . . . ”, ovvero

∀xR(x, x) → ∀x∀y(R(x, y) → ∃z(R(x, z) ∧R(z, y))),

allora la formula e banalmente vera per ogni relazione10.

Esempio 2.14. “La relazione R e riflessiva”, che significa che ogni elemento stanella relazione R con se stesso, si scrive

∀xR(x, x),

come abbiamo fatto sopra.

Esempio 2.15. “La relazione R e simmetrica”, che significa che se la relazione Rsussiste tra uno primo e un secondo elemento allora sussiste anche tra il secondoe il primo, si scrive

∀x∀y(R(x, y) → R(y, x)).

Esempio 2.16. “La relazione R e transitiva”, che significa che se R sussiste tra unprimo elemento e un secondo, e tra questo e un terzo, allora sussiste anche tra ilprimo e il terzo, si scrive,

∀x∀y∀z(R(x, y) ∧R(y, z) → R(x, z)).

Esempio 2.17. Come non esiste un quantificatore sulle coppie, cosı non esiste unquantificatore che esprima “esiste esattamente un . . . ”, o “esiste un solo . . . ”. Talelocuzione si realizza mediante l’uguaglianza come nel seguente esempio.

La frase “dati due numeri, esiste un solo numero che e la loro somma” siformalizza come

∀x∀y∃z(z = x + y ∧ ∀u(u = x + y → u = z)).

In generale “Esiste un solo x tale che P (x)” si formalizza come

∃x(P (x) ∧ ∀y(P (y) → x = y)).

Esempio 2.18. In modo analogo si puo esprimere la locuzione “esistono esattamentedue elementi tali che . . . ” (esercizio).

Suggerimento. Si scriva prima “esistono almeno due elementi tali che . . . ”,ricordando quanto detto nell’esempio 2.13 a proposito delle coppie di quantificatori.

10Con “banalmente” s’intende che dati x e y come z si puo prendere o x o y, e la formula nonci da veramente informazioni.

24

Esempio 2.19. Non si riesce invece con nessun giro di formule del formalismo chestiamo usando ad esprimere “la maggior parte degli elementi . . . ” o “quasi tutti. . . ”. Analogamente non si riesce ad esprimere “tanti”.

Esempio 2.20. La frase “dati due numeri diversi tra loro, esiste un numero che epropriamente compreso tra i due numeri dati” si rappresenta con

∀x∀y(x 6= y → ∃z(x < z < y ∨ y < z < x)).

dove x 6= y e un’abbreviazione per ¬(x = y).

Esempio 2.21. La frase “ogni numero positivo ha una radice quadrata”, vera neireali, falsa nei razionali, si rappresenta come

∀x(0 < x → ∃y(x = y2)),

dove con y2 si indica la funzione potenza di esponente 2.

Esempio 2.22. “Un numero e divisibile per un altro numero se e solo se esiste unterzo numero che moltiplicato per il secondo da il primo”.

Scriviamo x|y per “y e divisibile per x” o “x divide y” e usiamo il solito segnodi moltiplicazione:

∀x∀y(x|y ↔ ∃z(y = x · z)),

ma di nuovo si noti che x, y, z non devono necessariamente indicare numeri tuttidiversi tra loro.

Esempio 2.23. “Esistono due numeri primi consecutivi”.Per questa frase complicata procediamo in due passi; usiamo un’abbreviazione

pr(x) per “x e primo ” e scriviamo

∃x∃y(x = y + 1 ∧ pr(x) ∧ pr(y))

riservandoci di sostituire pr(x) con la sua scrittura corretta data nel prossimoesercizio.

Che i numeri siano due non risulta dallo scrivere ∃x∃y ma da x = y + 1che implica x 6= y (lo si deduce facilmente dagli assiomi dei numeri naturali); sipotrebbe anche scrivere:

∃x(pr(x) ∧ pr(x + 1)),

dando per scontato, come sopra, che x 6= x + 1.

Esempio 2.24. “Un numero e primo se e solo se e maggiore di 1 ed e divisibile soloper 1 e per se stesso”.

Per esprimere questa che e la definizione di un nuovo predicato usiamo unnuovo simbolo pr(x) e scriviamo

∀x(pr(x) ↔ x > 1 ∧ ∀z(z|x → z = 1 ∨ z = x))

25

Esempio 2.25. “2 e l’unico numero primo pari”.“Numero pari” significa “divisibile per 2”. La frase si puo trasformare in “2 e

primo e pari e se un numero e primo e pari allora e uguale a 2”. Quindi

pr(2) ∧ 2|2 ∧ ∀x(pr(x) ∧ 2|x → x = 2).

Esempio 2.26. “3 e dispari”Il predicato “dispari” si puo definire come “non pari” e quindi

¬2|3,

o meglio ¬(2|3) perche ¬ non si confonda con un segno aritmetico11, oppure dicendoche un numero dispari e della forma 2 · y +1, e in aritmetica si dimostra che le duedefinizioni sono equivalenti, quindi

∃y(3 = 2 · y + 1).

Esempio 2.27. “Ogni primo maggiore di 2 e dispari”e un caso di quantificatore ristretto, ma lo si puo restringere in due modi: ai

numeri primi oppure ai numeri primi maggiori di 2. Il predicato “essere primomaggiore di 2” si puo definire con (pr(x)∧x > 2) e si ha allora, se si scrive disp(x)per “x e dispari ”,

∀x((pr(x) ∧ x > 2) → disp(x)).

Oppure se si restringe solo ai primi si deve scrivere

∀x(pr(x) → (x > 2 → disp(x))).

In questo caso le parentesi interne servono a evidenziare la composizione correttadella frase mediante le due occorrenze del condizionale.

Esempio 2.28. “Esistono numeri pari arbitrariamente grandi”.La locuzione “arbitrariamente grandi” o “grandi quanto si vuole” significa che

comunque si dia un numero, ne esiste uno piu grande con la proprieta in oggetto— non che un numero e grande quanto si vuole, un numero e quello che e. Quindi

∀x∃y(x < y ∧ 2|y).

Esempio 2.29. “Ci sono almeno due quadrati minori di 10”.Consideriamo 10 una costante (in realta e un termine complesso). “x e un

quadrato” significa che x e il quadrato di qualche numero, e si formalizza come∃u(x = u2). Quindi

∃x∃y(x 6= y ∧ x < 10 ∧ y < 10 ∧ ∃u(x = u2) ∧ ∃u(y = u2)).

11Che non si legga ¬2 come “diverso da 2”.

26

Si noti che da ∃u(x = u2)∧∃u(y = u2)) non segue che la u sia la stessa, e quindi xe y uguali; le due frasi sono indipendenti; e come se si dicesse: “esiste un numeroil cui quadrato e x ed esiste un numero il cui quadrato e y”; non vuol dire che sialo stesso numero. Ma si sarebbe potuto anche scrivere ∃u(x = u2) ∧ ∃v(y = v2)).

Esempio 2.30. “Per due punti passa una e una sola retta”.Primo modo. Usiamo variabili diverse per punti e rette e una relazione binaria

Q per “un punto giace su una retta”.

∀A∀B∃r(Q(A, r) ∧Q(B, r) ∧ ∀s(Q(A, s) ∧Q(B, s) → r = s))

Secondo modo. Usiamo un solo tipo di variabili e due predicati P per “essere unpunto” e R per “essere una retta”.

∀x∀y(P (x) ∧ P (y) → ∃z(R(z) ∧Q(x, z) ∧Q(y, z)∧∀u(R(u) ∧Q(x, u) ∧Q(y, u) → z = u)).

Le due soluzioni sono equivalenti; nella prima si usa un linguaggio a due sortadi variabili, che ha le stesse proprieta logiche di quello con una sola sorta.

Esempio 2.31. “La funzione y = x3 e iniettiva e suriettiva” si formalizza

∀x1∀x2(x1 6= x2 → x31 6= x3

2) ∧ ∀y∃x(y = x3),

in un linguaggio che abbia il simbolo = e un simbolo funzionale indicato con x3.

Esempio 2.32. L’affermazione che la relazione “y = 2·x” e una relazione funzionalee iniettiva e formalizzata da:

∀x∃y(y = 2 · x ∧ ∀z(z = 2 · x → z = y)) ∧ ∀x1∀x2(x1 6= x2 → 2 · x1 6= 2 · x2).

Dagli esempi si traggono diverse regole euristiche: riformulare la frase in un �

italiano semplice, con soggetto, verbo e complementi; trasformare i pronomi quan-titativi come “ognuno”, “alcuni”, “nessuno”, “uno” . . . usando sempre solo “pertutti . . . ” ed “esiste un . . . ”, anche se la frase diventa barocca; guardare i verbi,se sono intransitivi o transitivi, e sostituire le frasi elementari con le dizioni “ha laproprieta . . . ” e “sussiste la relazione . . . ”; non prendere relazioni troppo inglo-banti che nascondano la sintassi informale, immaginando possibili proseguimentidella frase che richiedono di riprendere certi elementi; invece lasciare cadere parti-colari empirici; nelle frasi matematiche, risalire sempre alle definizioni dei terminicoinvolti.

27

2.7 Esercizi

Esercizio 2.33. Formalizzare “A Giovanni piacciono i Piaggio 50”; trasformarlaprima in italiano in modo da far comparire un quantificatore ristretto.

Esercizio 2.34. Formalizzare “I professori premiano gli studenti meritevoli”.

Esercizio 2.35. In un’assemblea di politici, questi si dividono in onesti e disonesti,e si sa che

1. esiste almeno un politico onesto;

2. presi due politici a caso, uno almeno e disonesto.

Si formalizzino le condizioni sui politici.Se nell’assemblea ci sono cento politici, si puo decidere (dedurre) quanti sono

gli onesti e quanti i disonesti? Formalizzare anche la risposta.

Esercizio 2.36. Usando un predicato S per “x e uno studente”, una relazione Cper “x e un computer”, un predicato F per “x e funzionante” e una relazione Uper “x utilizza y”, formalizzare le seguenti frasi:

1. Un computer non e utilizzato da nessun studente.

2. Ogni computer funzionante e utilizzato da almeno uno studente.

3. Non tutti i computer sono funzionanti.

Quale dei seguenti enunciati e una traduzione corretta di (1)?

∃x(C(x) ∧ ∀y(¬S(y) ∧ ¬U(y, x)))

∃x(C(x) → ∀y(S(y) → ¬U(y, x)))

∃x(C(x) ∧ ∀y(S(y) → ¬U(y, x)))

Qual’e il significato delle altre formule? Tradurre (2) e (3) in opportuni enun-ciati del linguaggio formale introdotto.

Esercizio 2.37. Una base di dati relazionale e una tabella come la seguente:

Codice genitori Nome figliCodice 1 PaolaCodice 1 FrancescoCodice 2 PaolaCodice 3 AnnaCodice 3 LeaCodice 4 Giovanni

28

Le interrogazioni sono del tipo:“(insieme dei) codici dei genitori che non hannofigli di nome Paola”. Se si usa una relazione R(x, y) per “x e il codice di genitori chehanno figli di nome y”, rappresentata dalla tabella, l’interrogazione si formalizzacome ¬∃y(R(x, y) ∧ y = “Paola”), che definisce l’insieme {x : ¬∃y(R(x, y) ∧ y =“Paola”)}.

Formalizzare la interrogazione “codici dei genitori che hanno figli di nomediverso da Paola”.

29

3 Insiemi

3.1 Elementi ed insiemi

In matematica e uso comune considerare delle collezioni di oggetti e queste colle-zioni si dicono insiemi. Useremo anche le espressioni classe e famiglia comesinonimo di insieme, ma non il termine gruppo che in matematica ha un significatodifferente. Un oggetto o elemento puo appartenere o meno ad un insieme. Perdire che l’oggetto x appartiene all’insieme A scriveremo

x ∈ A

Un insieme e completamente determinato dai suoi elementi. Questo discende dalseguente:

Principio di estensionalita. Due insiemi coincidono se e solo se hanno gli stessielementi.

L’insieme formato dagli elementi x1, . . . , xn lo si indica con

{x1, . . . , xn}.

Per esempio l’insieme delle soluzioni dell’equazione x3 − 4x2 + x + 6 e l’insieme

(5) {−1, 2, 3},

che per il principio di estensionalita e lo stesso insieme che {2,−1, 3} oppure{3, 2, 3,−1}. In altre parole: l’ordine in cui vengno elencati gli elementi di uninsieme e irrilevante, e le eventuali ripetizioni non contano. L’insieme di tutti glix che godono della proprieta P e indicato con

{x | P (x)}

o anche con

{x : P (x)} .

A volte ci basta considerare tutti gli x appartenenti ad un insieme A e tali chesoddisfano la proprieta P , cioe {x | x ∈ A e P (x)}. In questo caso scriveremo

{x ∈ A | P (x)} .

Un insieme si dice vuoto se non contiene elementi. Per il principio di estensio-nalita due insiemi vuoti coincidono, per cui parleremo dell’insieme vuoto, che siindica con ∅.

Un insieme A e contenuto in un insieme B ovvero A e un sottoinsiemedi B, in simboli A ⊆ B, se ogni elemento di A e anche un elemento di B. Dalprincipio di estensionalita si ottiene subito il

30

Principio di doppia inclusione. Dati due insiemi A e B coincidono se e solo se

A ⊆ B e B ⊆ A.

Osserviamo che A ⊆ A. Quando A ⊆ B ma A 6= B diremo che A e contenutopropriamente in B e scriveremo A ⊂ B. Per verificare che A non e contenuto inB, in simboli A * B e sufficiente trovare un elemento di A che non appartiene aB. Poiche ∅ non ha elementi ne consegue che ∅ ⊆ B per ogni insieme B.

Osservazione 3.1. Non bisogna confondere la nozione di appartenenza ∈ con quelladi inclusione ⊆: la prima collega elementi ad insiemi, la seconda confronta insiemi.

3.2 Esempi

L’insieme dei numeri naturali

N = {0, 1, 2, . . .}

e contenuto propriamente nell’insieme dei numeri interi

Z = {. . . ,−2,−1, 0, 1, 2, . . .}

L’insieme Q dei numeri razionali e l’insieme di tutti i numeri della forma n/mcon n,m ∈ Z e, naturalmente, m 6= 0. Ogni intero k puo essere scritto comek/1 quindi Z ⊆ Q e poiche ci sono razionali che non sono interi, l’inclusione epropria, cioe Z ⊂ Q. Un razionale ha un’espansione decimale finita (per esempio12

= 0,5) oppure un’espansione periodica (per esempio 13

= 0,33333 . . .). I numerila cui espansione decimale e arbitraria (cioe finita, periodica o aperiodica) si dicononumeri reali e l’insieme dei numeri reali si denota con R. Chiaramente Q ⊆ Re poiche ci sono numeri reali che non sono razionali (per esempio

√2), l’inclusione

e propria.

3.3 Operazioni su insiemi

Dati due insiemi A e B possiamo costruire altri insiemi:

• L’intersezione di A e B, in simboli A ∩B, e l’insieme di tutti gli enti chestanno tanto in A quanto in B.

• L’unione di A e B, in simboli A∪B, e l’insieme di tutti gli enti che stannoin A o in B (o in entrambi gli insiemi),

• La differenza tra A e B, in simboli A \B, e l’insieme di tutti gli enti chestanno in A ma non in B.

31

• La differenza simmetrica tra A e B, in simboli A4B, e l’insieme ditutti gli enti che stanno in uno dei due insiemi ma non nell’altro.

L’insieme delle parti di un insieme A e l’insieme di tutti i sottoinsiemi diA

P(A) = {B | B ⊆ A} .

Osserviamo che l’insieme delle parti e un insieme i cui elementi sono a loro voltainsiemi.

Le operazioni di unione e di intersezione possono essere generalizzate a famigliearbitrarie di insiemi. Una famiglia arbitraria di insiemi e denotata da {Ai | i ∈ I}— ad ogni indice i ∈ I corrisponde un insieme Ai. L’unione degli Ai e l’insieme⋃

i∈I

Ai = {x | x ∈ Ai, per qualche i ∈ I}

mentre l’intersezione degli Ai e l’insieme⋂i∈I

Ai = {x | x ∈ Ai, per ogni i ∈ I} .

Chiaramente ogni⋃

i∈I Ai contiene ogni Aj mentre⋂

i∈I Ai e contenuta in ogni Aj.Per esempio, se consideriamo la famiglia {An | n ∈ N} di intervalli di R dove

An = [−1; 1− 2n], allora⋃n∈N

An = [−1; 1) e⋂n∈N

An = [−1; 0].

Se invece An = [−1; 1 + 2n], allora⋃n∈N

An = [−1; 2) e⋂n∈N

An = [−1; 1].

3.4 Relazioni e funzioni

Il prodotto cartesiano di A e B, in simboli A × B, e l’insieme di tutte lecoppie ordinale (x, y) dove x ∈ A e y ∈ B, cioe

A×B = {(x, y) | x ∈ A e y ∈ B} .

Osserviamo che, a differenza degli insiemi, nelle coppie ordinate l’ordine e fonda-mentale, cioe (x, y) e un oggetto diverso da (y, x), a meno che x non sia y. QuindiA × B e distinto da B × A, a meno che A = B nel qual caso scriveremo A2. Peresempio R2 e l’insieme delle coppie ordinate di numeri reali e questo insieme viene

32

usualmente identificato con il piano mediante un sistema di assi cartesiani. Ingenerale se n ≥ 2

(x1, x2, . . . , xn)

indica la n-upla ordinata costituita degli elementi x1, x2, . . . , xn e

An = A× · · · × A︸ ︷︷ ︸n

e il prodotto cartesiano di n-copie dell’insieme A.Una relazione n-aria, con n ≥ 1 e un sottoinsieme di A1 × · · · × An, per

qualche insieme A1, . . . , An e se questi insiemi sono tutti lo stesso insieme A parle-remo di relazione n-aria su A. Se n = 1 parleremo di relazione unaria o predicato,se n = 2 parleremo di relazione binaria, se n = 3 parleremo di relazione ternaria,etc. Spesso le relazioni binarie si dicono semplicemente relazioni e si scrive a R binvece di (a, b) ∈ R.

Definizione 3.2. Diremo che una relazione (binaria) R su un insieme A e

riflessiva se a R a per ogni a ∈ A,

simmetrica se ogni qual volta a R b ne segue che b R a,

antisimmetrica se ogni qual volta a R b e b R a ne segue che a = b,

transitiva se da a R b e b R c segue che a R c.

Definizione 3.3. Una relazione di equivalenza su A e una relazione rifles-siva, simmetrica e transitiva su A.

La diagonale o identita dell’insieme A e

I(A) =def {(a, a) | a ∈ A} .

I(A) e A × A sono relazioni di equivalenza su A. Inoltre se E e una relazione diequivalenza su A, allora I(A) ⊆ E ⊆ A× A.

La classe di equivalenza di un elemento a ∈ A relativamente ad unarelazione di equivalenza E su A e

[a]E =def {x ∈ A | x E a}

l’insieme di tutti gli elementi E-equivalenti ad a. Spesso si usa il simbolo a/Einvece di [a]E. L’insieme quoziente e

A/E =def {[a]E | a ∈ A}

l’insieme di tutte le classi di equivalenza. Osserviamo che l’insieme quoziente euna famiglia di sottoinsiemi di A, cioe

A/E ⊆ P(A).

33

Proposizione 3.4. Data una relazione di equivalenza E su un insieme A, dueclassi di equivalenza sono disgiunte o coincidono.

Dimostrazione. Fissiamo due classi di equivalenza [a]E e [b]E, dove a, b ∈ A.

Caso 1: a E b. Sia c ∈ [a]E: allora c E a e per la proprieta transitiva c E b equindi c ∈ [b]E. Quindi [a]E ⊆ [b]E.

Sia c ∈ [b]E: allora c E b, per la proprieta simmetrica b E a e per la proprietatransitiva c E a e quindi c ∈ [a]E. Quindi [b]E ⊆ [a]E.

Per il principio della doppia inclusione abbiamo quindi [a]E = [b]E.

Caso 2: a 6E b. Verifichiamo che in questo caso [a]E ∩ [b]E = ∅. Supponiamo,per assurdo, che ci sia un c ∈ [a]E ∩ [b]E. Allora c E b e quindi b E cper simmetria, e dato che c E a si ha b E a per transitivita. Ma questocontraddice la nostra assunzione.

Quindi il risultato e dimostrato.

Definizione 3.5. Una partizione di un insieme A 6= ∅ e una famiglia C disottoinsiemi non vuoti di A, a due a due disgiunti, che ricoprono A, cioe

(1) se X ∈ C allora ∅ 6= X ⊆ A,

(2) se X,Y ∈ C e X 6= Y allora X ∩ Y = ∅,

(3) ogni elemento di A appartiene a qualche X ∈ C.

Se E e una relazione di equivalenza su A, allora A/E e una partizione di A.Viceversa, data una partizione C di A, la relazione E ⊆ A2 definita da

a E b se e solo se a e b appartengono al medesimo X ∈ C

e una relazione di equivalenza su A.

Definizione 3.6. Una relazione d’ordine su A — o piu semplicemente: unordine o ordinamento su A — e una relazione riflessiva, antisimmetrica etransitiva su A.

L’esempio canonico di ordinamento e la relazione ≤ su N, cioe l’insieme{(n,m) ∈ N2 | n ≤ m

}.

Analogamente ≤ e un ordinamento sugli insiemi Z, Q e R. L’ordinamento ≤ suquesti insiemi e un ordine lineare, dove

34

Definizione 3.7. Un ordine R su un insieme A e lineare o totale se a R b ob R a per ogni scelta di a, b ∈ A.

L’inclusione e un ordinamento su P(A), ma se A ha almeno due elementi,diciamo a e b, questo ordine non e lineare, dato che {a} e {b} non sono sottoinsiemil’uno dell’altro.

Definizione 3.8. Sia � un ordinamento su A. Un elemento a ∈ A si dice

• massimo se b � a per ogni b ∈ A

• minimo se a � b per ogni b ∈ A.

Esempi 3.9. • L’ordinamento ≤ su N ha minimo (il numero 0), ma non hamassimo.

• L’ordinamento ≤ su Z non ha ne minimo, ne massimo.

• L’ordinamento ≤ sull’intervallo (0; 1] =def {x ∈ R | 0 < x ≤ 1} ha massimo(il numero 1) ma non ha minimo.

• L’ordinamento ⊆ su P(A) ha minimo (l’insieme ∅) e massimo (l’insieme A).

Esercizio 3.10. Definiamo � su N come

n � m se e solo se m = nk, per qualche k ∈ N.

Dimostrare che � e un ordine non totale su N che ha minimo e massimo.

La relazione < non e un ordine su N, Z, Q o R dato che non vale la proprietariflessiva. Per questo motivo introduciamo la seguente

Definizione 3.11. Un ordine stretto su A e una relazione R su A tale che

R ∪ I(A)

e un ordine su A.

Definizione 3.12. Una relazione F ⊆ A×B e una funzione da A in B se

(1) per ogni a ∈ A c’e un b ∈ B tale che (a, b) ∈ F .

(2) ogni qual volta (a, b1) ∈ F e (a, b2) ∈ F succede che b1 = b2.

In questo caso scriveremo F : A → B e l’unico b ∈ B tale che (a, b) ∈ F lo si indicacon F (a).

35

Definizione 3.13. Una funzione F : A → B e

iniettiva se da a1 6= a2 segue che F (a1) 6= F (a2), o, equivalentemente, se daF (a1) = F (a2) segue che a1 = a2;

suriettiva se ogni b ∈ B e della forma F (a) per qualche a ∈ A;

biettiva se e iniettiva e suriettiva.

Definizione 3.14. Una operazione n-aria su A e una F : An → A.

36

4 Il principio di induzione

In matematica (ed in informatica) e spesso necessario dimostrare che una certaproprieta e vera per tutti i numeri naturali. Per esempio:

• Per ogni n ∈ N,n∑

i=0

i =n(n + 1)

2.

• Consideriamo un frammento di codice della forma:

while (b)

S;

Se P e una proposizione che esprime una relazione tra i valori delle variabiliche compaiono nell’istruzione S, allora si puo definire un’altra proprieta

Q(n) ⇔ P e vera dopo n iterazioni del ciclo while.

Proprieta di questo tipo sono utilizzate per stabilire che P e una proprietainvariante del ciclo in questione.

• Se E(n) e un’espressione aritmetica che contiene la variabile n, l’equazione

f(n) = E(n)

stabilisce che la funzione f per l’argomento n ha lo stesso valore dell’espres-sione E(n). Se immaginiamo che la funzione f sia definita ricorsivamente, sipuo dimostrare per induzione che f(n) = E(n) per ogni valore naturale di n,stabilendo cosı la correttezza della definizione ricorsiva della funzione il cuivalore per n e dato da E(n).

La formulazione piu generalmente nota del principio di induzione e la seguente.

principio di dimostrazione per induzione: Data una proprietaP dei numeri naturali, se P (0) e P (n) ⇒ P (n+1), allora ∀x ∈ N.P (x).

Qui una proprieta dei numeri naturali e una proprieta per la quale abbia sensochiedersi se e vera o falsa per un numero naturale. La base dell’induzione e ladimostrazione di P (0), mentre il passo induttivo e la dimostrazione dell’im-plicazione P (n) ⇒ P (n + 1), che normalmente si articola nel modo seguente: siassume che P (n) sia vera (questa e detta l’ipotesi induttiva), e si dimostra cheP (n + 1). Un’altra formulazione, del tutto equivalente alla prima, del principio diinduzione, usa l’estensione della proprieta P , cioe l’insieme dei numeri naturaliper i quali la proprieta e vera:

Se A ⊆ N e tale che 0 ∈ A e, per ogni n ∈ N, n ∈ A ⇒ n + 1 ∈ A,allora A = N.

37

Aritmetica Vediamo subito il primo esempio di utilizzo del principio di indu-zione:

Proposizione 4.1. Per ogni n ∈ N,

n∑i=0

i =n(n + 1)

2.

Dimostrazione. Qui la proprieta P (k) e

k∑i=0

i =k(k + 1)

2.

La base consiste nel verificare che entrambi i lati dell’induzione hanno valore 0.Per dimostrare il passo induttivo, assumiamo che

n∑i=0

i =n(n + 1)

2

e dimostriamo chen+1∑i=0

i =(n + 1)(n + 2)

2.

Ora,

n+1∑i=0

i =

(n∑

i=0

i

)+ (n + 1)

=n(n + 1)

2+ (n + 1) per l’ipotesi induttiva

=n(n + 1)

2+

2(n + 1)

2

=(n + 1)(n + 2)

2

e mediante un’applicazione del principio di induzione si ottiene la conclusione.

Correttezza di programmi Consideriamo il problema di calcolare il quozienteq ed il resto r della divisione di due numeri interi X ≥ 0 e D > 0. L’algoritmousuale consiste nel sottrarre ripetutamente D a X, aumentando ogni volta di 1 ilvalore di q che inizialmente ha valore 0. Schematicamente, l’algoritmo e il seguente:

1. fino a quando X ≥ D esegui le seguenti azioni: sottrai D a X; aumenta q di1

38

2. quando X < D, poni r = X.

Un programma Java che realizza questo algoritmo e il seguente:

class divisione {

public static void main (String[] args) {

int X, D, q, r;

X = 14;

D = 3;

q = 0;

r = X;

while (r >= D) {

r = r - D;

q = q + 1;

}

System.out.println ("Il quoziente e: " + q);

System.out.println ("Il resto e: " + r);

}

}

Come si puo dimostrare che il programma precedente e corretto? Prima di tutto,serve una specifica precisa del problema da risolvere: La condizione di ingresso delprogramma, cioe la proprieta che i dati in ingresso X e D devono soddisfare, e cheX ≥ 0 e D > 0 (la seconda proprieta serve ad evitare casi di divisione per 0). Lacondizione di uscita del programma, cioe la proprieta che i dati in uscita q ed rdevono soddisfare, e che X = q ∗D + r, con r < D. Questa proprieta dice proprioche q ed r sono, rispettivamente, il quoziente ed il resto della divisione intera di Xper D. La correttezza del programma (qualche volta si parla di questa condizionecome di correttezza parziale) asserisce che:

per ogni dato in ingresso che soddisfa la condizione di ingresso, se ilprogramma termina, allora i dati in uscita soddisfano la condizione diuscita.

Una condizione piu esigente di correttezza e quella che si chiama correttezzatotale:

per ogni dato in ingresso che soddisfa la condizione di ingresso, ilprogramma termina e i dati in uscita soddisfano la condizione di uscita.

Per stabilire che un programma soddisfa la specifica vi sono vari modi, ma latecnica piu conveniente consiste nel trovare quello che si chiama un invariante(di ciclo):

39

invariante (di un ciclo) e una proprieta che lega (tutte o alcune del)levariabili coinvolte nel ciclo, e che e vera dopo un numero arbitrariodi iterazioni del ciclo. In particolare, e vera all’ingresso nel ciclo (cioedopo 0 iterazioni).

Ci sono molte proprieta invarianti del ciclo

while (r >= D) {

r = r - D;

q = q + 1;

}

nel programma precedente, per esempio la proprieta q ≥ 0. Tra tutte le possibiliproprieta ce ne sono alcune che sono piu interessanti di altre. Consideriamo ora laproprieta:

(6) X = q ∗D + r

che e molto simile alla condizione di uscita del programma. Che si tratti veramentedi un invariante e qualcosa che deve ancora essere dimostrato, ma per il momentoassumiamo che lo sia. Quando il ciclo termina (e prima o poi deve terminare,perche ad ogni iterazione a r viene sottratto il valore D che, per la condizione diingresso, e un numero > 0, quindi prima o poi deve accadere che r < D) abbiamoche X = q ∗ D + r perche abbiamo assunto che questa proprieta sia invariante,ed inoltre si esce dal ciclo perche r < D. Ma allora e vera la proprieta X =q ∗D + r, con r < D, che e proprio la condizione di uscita del programma. L’usodell’invariante ci permette quindi di dimostrare che il programma e (parzialmente)corretto. In questo caso abbiamo gia implicitamente dimostrato che il programmae anche totalmente corretto, perche abbiamo gia visto che il ciclo deve terminare.Resta da dimostrare che la proprieta (6) e proprio invariante. Questo si puo fareper induzione sul numero di iterazioni del ciclo. Supponiamo che questo numerosia 0 (base dell’induzione) (ovviamente, la dimostrazione che (6) e invariante valein generale, non solo per gli specifici valori di X e D che abbiamo scelto). Alloraq = 0(perche q non viene incrementato) e r = X. Allora X = q ∗ D + r perchequesto si riduce a dire che X = 0∗D+X, che e ovviamente vero. Supponiamo cheil ciclo sia stato eseguito n volte, e che la proprieta (6) sia vera (ipotesi induttiva);vogliamo dimostrare ora che resta vera anche dopo la (n + 1)-esima iterazione.Durante questa iterazione vengono modificati i valori di q e di r, ottenendo valori

q′ = q + 1

r′ = r −D

dove q′ ed r′ sono i valori delle variabili q ed r dopo l’esecuzione delle istruzioni

40

r = r - D;

q = q + 1;

Allora calcoliamo:

q′ ∗D + r′ = (q + 1) ∗D + (r −D)

= q ∗D + D + r −D

= q ∗D + r = X

dove l’ultimo passaggio sfrutta l’ipotesi induttiva. Per induzione si conclude allorache la proprieta (6) e vera per qualsiasi numero di iterazioni del ciclo, quindi (6)e invariante.

Esempio 4.2. (Quadrato di un numero naturale) Vediamo un altro esempio dellatecnica appena usata per dimostrare la correttezza del programma per la divisioneintera, utilizzandola questa volta per sintetizzare un programma per calcolare ilquadrato di un numero naturale N . La condizione di ingresso sara dunque N ≥ 0,mentre la condizione di uscita sara Y = X ∗X e X = N dove Y e il dato in uscitaed X una variabile ausiliaria utilizzata come contatore. L’invariante appropriatoin questo caso e la formula

(7) Y = X ∗X.

Inizialmente avremo dunque X = 0 e Y = 0: l’invariante e ovviamente veroin questo caso, e questo stabilisce la base della dimostrazione induttiva che laproprieta (7) e invariante.

class quadrato {

public static void main (String[] args) {

int N, X, Y;

N = ? ; // inizializzazione

X = 0;

Y = 0;

while (X < N) {

Y = Y + 2 * X + 1;

X = X + 1;

}

System.out.println ("Quadrato = " + Y);

}

}

Per quanto riguarda il passo induttivo, l’ipotesi induttiva e

41

Y = X ∗X dopo l’n-esima iterazione;

bisogna dimostrare che (7) resta vera dopo la (n + 1)-esima iterazione. Se Y ′ e ilvalore di Y dopo l’esecuzione dell’istruzione Y = Y + 2 ∗ X + 1, mentre X ′ e ilvalore di X dopo l’esecuzione dell’istruzione X = X + 1, possiamo calcolare

Y ′ = Y + 2 ∗X + 1

= (X ∗X) + 2 ∗X + 1 (per ipotesi induttiva)

= (X + 1) ∗ (X + 1)

= X ′ ∗X ′

da cui si conclude che (7) e proprio invariante. Poiche il valore di N −X decrescestrettamente ad ogni iterazione, il ciclo deve terminare (Perche non ci puo essereuna sequenza infinita di numeri naturali k0 > k1 > k2 > . . .) all’uscita dal cicloavremo X = N (perche la condizione del while e diventata falsa e sappiamo,per come e fatto il programma, che X ≤ N) quindi, per l’invariante, Y = N ∗N .Questo mostra che la condizione di uscita e soddisfatta dal dato in uscita Y , percioil programma e corretto.

Definizioni ricorsive di funzioni Immaginiamo di volere definire una funzionef : N → A, dove N e l’insieme dei numeri naturali ed A un insieme qualsiasi. Sipuo allora utilizzare il seguente schema di ricorsione:

f(0) = a

f(n + 1) = E(f(n))

dove a e un elemento di A e con la notazione E(f(n)) si indica che l’espressioneE( ) puo utilizzare il valore f(n). Una giustificazione intuitiva di questo schema sipuo ottenere considerando la struttura dei numeri naturali: la funzione f e definitaper 0 perche la prima clausola dello schema ne fornisce il valore a; supponiamoinvece che k sia un numero positivo, e che quindi k = n + 1 per qualche numeronaturale n. Si puo immaginare di avere gia calcolato il valore di f(n)(la funzione fviene calcolata “dal basso”, partendo dall’argomento 0), e si puo quindi calcolareE(f(n)) che da il valore di f(n+1). (Una giustificazione rigorosa di questo metododi definizione di funzioni verra data piu tardi, nel Teorema 4.13.)

Vediamo solo un esempio di applicazione di questo schema, riprendendo unesempio gia visto trattato mediante un programma iterativo dimostrato correttomediante invarianti:

Esempio 4.3. (La funzione quadrato) Si puo definire ricorsivamente il quadrato diun numero naturale mediante le clausole:

q(0) = 0

q(n + 1) = q(n) + 2 ∗ n + 1

42

Vediamo che le clausole precedenti definiscono effettivamente la funzione desidera-ta, dimostrando per induzione che la proprieta q(n) = n ∗ n e vera per ogni valoredi n:(Base dell’induzione)

q(0) = 0 (per definizione)

= 0 ∗ 0

(Passo indutttivo)

q(n + 1) = q(n) + 2 ∗ n + 1 (per definizione)

= n ∗ n + 2 ∗ n + 1 (per ipotesi induttiva)

= (n + 1) ∗ (n + 1) (per proprieta algebriche)

Osservazione Le clausole della definizione ricorsiva della funzione q(n) consentonoanche di calcolare il valore di questa funzione per un valore arbitrario dell’argo-mento. Per esempio:

q(5) = q(4 + 1)

= q(4) + 2 ∗ 4 + 1

= q(3 + 1) + 2 ∗ 4 + 1

= q(3) + 2 ∗ 3 + 1 + 2 ∗ 4 + 1

= q(2 + 1) + 2 ∗ 3 + 1 + 2 ∗ 4 + 1

= q(2) + 2 ∗ 2 + 1 + 2 ∗ 3 + 1 + 2 ∗ 4 + 1

= q(1 + 1) + 2 ∗ 2 + 1 + 2 ∗ 3 + 1 + 2 ∗ 4 + 1

= q(1) + 2 ∗ 1 + 1 + 2 ∗ 2 + 1 + 2 ∗ 3 + 1 + 2 ∗ 4 + 1

= q(0 + 1) + 2 ∗ 1 + 1 + 2 ∗ 2 + 1 + 2 ∗ 3 + 1 + 2 ∗ 4 + 1

= q(0) + 2 ∗ 0 + 1 + 2 ∗ 1 + 1 + 2 ∗ 2 + 1 + 2 ∗ 3 + 1 + 2 ∗ 4 + 1

= 0 + 2 ∗ 0 + 1 + 2 ∗ 1 + 1 + 2 ∗ 2 + 1 + 2 ∗ 3 + 1 + 2 ∗ 4 + 1

= 1 + 2 + 1 + 4 + 1 + 6 + 1 + 8 + 1

= 25

Esercizio 4.4. Dimostrare per induzione che la funzione definita dalle clausole:{f(0, y, z) = z × y

f(x + 1, y, z) = z + f(x, y, z)

e tale che, per ogni x, y, z ∈ N:

f(x, y, z) = (x + y)× z

43

Esercizio 4.5. Dimostrare per induzione che la funzione definita dalle clausole:{f(0) = 1

f(n + 1) = f(n) + f(n)

e tale che, per ogni n ∈ N:f(n) = 2n.

Esercizio 4.6. Dimostrare per induzione che la funzione definita dalle clausole:{f(0) = 0

f(n + 1) = (n + 1) + f(n)

e tale che, per ogni n ∈ N:

f(n) =n∑

i=0

i

4.1 Generalizzazioni del principio di induzione

C’e un altro principio fondamentale per ragionare sui numeri naturali:

Principio del minimo: Se la proprieta P e vera per qualche numeronaturale, allora c’e un minimo numero naturale n tale che P (n).

Dire che n e il minimo per il quale la proprieta P vale implica, in particolare,che ∀k < n.¬P (k). Una conseguenza fondamentale del principio del minimo e laseguente proprieta, che si esprime dicendo che la relazione d’ordine stretta < suinumeri naturali e ben fondata:

In N non esiste alcuna successione discendente infinita della forma

(8) n0 > n1 > n2 > . . .

Infatti, se esistesse una successione della forma (8), l’insieme {n0, n1, n2, . . .} nonavrebbe un minimo elemento. L’importanza di questa proprieta dei numeri natu-rali, che verra generalizzata nella sezione 4.1.2, risiede tra l’altro nell’utilizzo chese ne puo fare per dimostrare la terminazione di programmi. Si ricordi che implici-tamente questa proprieta era gia stata utilizzata, per esempio, nella dimostrazionedella correttezza totale del programma per la divisione intera. La terminazione delciclo che calcola sul quale quel programma si basa viene dimostrata assegnando aciascuna configurazione di valori c = (X, D, q, r) assunti dalle corrispondenti va-riabili del programma un numero naturale T (c) (nel caso specifico r). Si utilizza

44

poi l’osservazione che, se il programma permette di passare da una configurazionec = (X, D, q, r) ad una configurazione c′ = (X ′, D′, q′, r′), allora T (c) > T (c′).Questo e sufficiente a stabilire la terminazione: se il programma non terminassedovrebbe esistere una successione di configurazioni c0, c1, c2, . . . tale che il program-ma passa dalla configurazione ci alla configurazione ci+1 , per ogni i = 0, 1, 2, . . ..Ma allora dovrebbe anche esistere una successione discendente di numeri naturaliT (c0) > T (c1) > T (c2) > . . ., contro la buona fondazione di < su N.

Dimostriamo ora che il principio di induzione implica il principio del minimo. Ilviceversa, cioe che il principio del minimo implica il principio di induzione, e unbell’esercizio per voi.

Teorema 4.7. Se P e vera per qualche numero naturale, allora c’e un numero ntale che P (n) ed inoltre ∀k < n.¬P (k).

Dimostrazione. Per assurdo, cioe cerchiamo di derivare una contraddizione dallanegazione di quello che vogliamo dimostrare, che e equivalente alla congiunzionedelle proposizioni seguenti:

(9) ∃m ∈ N.P (m) ∀n ∈ N.P (n) ⇒ ∃q < n.P (q).

Detto in italiano, assumiamo che ci sia un numero naturale che soddisfa P ma nonci sia un minimo numero che soddisfa P e cerchiamo di ottenere una contraddizione.Per induzione, dimostriamo che ∀i ∈ N.Q(i), dove Q(i) e vera se e solo se ∀j <i.¬P (j).Base: Q(0) e vera perche non c’e nessun numero naturale minore di 0 che la rendafalsa.Passo induttivo: Assumiamo l’ipotesi induttiva Q(i), cioe che

(10) ∀j < i.¬P (j),

e dimostriamo che Q(i + 1), cioe che ∀j ≤ i.¬P (j). Sappiamo gia, per (10),che ¬P (0), . . . ,¬P (i − 1), ci resta da dimostrare che ¬P (i), e facciamo questoancora per assurdo. In effetti, se P (i), mentre ∀j < i.¬P (j) per (10), allorai e il minimo numero naturale che soddisfa P , ma questo contraddice l’ipotesi(9). Quindi ¬P (i) e percio ∀j ≤ i.¬P (j), cioe ∀j < i + 1.¬P (j), che significaQ(i + 1). Un’applicazione del principio di induzione ci permette di concludere che∀i ∈ N.Q(i). Ma allora non ci puo essere un numero naturale che soddisfa P :infatti se ci fosse un n siffatto, poiche vale Q(n + 1) per quanto abbiamo appenaconcluso, si dovrebbe avere ¬P (n) per la definizione di Q e per il fatto che Q evera per ogni numero naturale, contro l’ipotesi (9). Abbiamo quindi raggiunto unacontraddizione con la nostra prima ipotesi, e questo dimostra che il principio delminimo e vero.

45

Vediamo un’applicazione del principio del minimo:

Proposizione 4.8. Ogni numero naturale ≥ 2 ha una scomposizione in fattoriprimi.

Dimostrazione. Per assurdo, sia n ≥ 2 tale da non avere una scomposizione infattori primi. Supponiamo anche che n sia il minimo numero con questa proprieta.Ci sono due casi:

1. n e primo: allora n ha una scomposizione in fattori primi, assurdo.

2. n e composto: sia n = pq, dove p, q ≥ 2. I numeri p e q devono avere unascomposizione in fattori primi, perche n e il minimo che non ce l’ha, quindianche n deve averla, componendo in modo opportuno le scomposizioni di pe q, assurdo.

In entrambi i casi abbiamo contraddetto l’ipotesi che ci sia un numero naturale chenon ha scomposizione in fattori primi, quindi abbiamo dimostrato la proposizione.

Esercizio 4.9. Sia s1, . . . , sn, dove n ≥ 2, una sequenza di interi dove s1 e positivo,sn e negativo e per ogni i, se 1 ≤ i < n, si+1 = si − 1 o si+1 = si + 1. Si dimostriche esiste i, con 1 < i < n, tale che si = 0.

4.1.1 Il principio di induzione forte

Si puo anche dare la seguente formulazione del principio di induzione, che risulteraessere equivalente alla prima. Diciamo che una proprieta P dei numeri naturali eprogressiva se

(∀y < x.P (y)) → P (x),

e scriviamo Prog(P ) per indicare che P e una proprieta progressiva.

principio di dimostrazione per induzione forte: Se Prog(P ),allora ∀n ∈ N.P (n).

Vediamo di dimostrare che il principio di induzione implica il principio di induzioneforte. A questo scopo, assumiamo che Prog(P ). L’idea naturale sarebbe quelladi dimostrare per induzione che P (n) per ogni n ∈ N. In effetti si dimostra cheP (0) perche ∀y < 0.P (y) e non c’e alcun elemento di N minore di 0, quindi perl’assunzione che Prog(P ) abbiamo P (0). Per dimostrare il passo induttivo tuttavia,dovremmo riuscire a dimostrare che P (n+1) assumendo che P (n), ma questo nonbasta per applicare l’ipotesi Prog(P ).

46

Allora seguiamo un’altra strategia: dimostriamo per induzione che ∀n ∈ N.P ](n),dove la nuova proprieta P ] e definita nel modo seguente, per x ∈ N:

P ](x) se e solo se ∀y < x.P (y).

Possiamo concludere per lo stesso ragionamento di prima che P ](0). Supponiamoora (ipotesi induttiva) che P ](n) per un generico n ∈ N, e vediamo di dimostrareche e anche vero che P ](n + 1). Se P ](n), allora per la definizione di P ] abbiamo∀y < n.P (y). Poiche Prog(P ), P (n) e vera e quindi ∀y < n + 1.P (y), ma questoequivale alla verita di P ](n + 1). Per induzione concludiamo allora che ∀n ∈N.P ](n). Sia ora k un generico numero naturale: allora P ](k + 1), quindi ∀y <k + 1.P (y) e percio P (k), quindi possiamo asserire che ∀n ∈ N.P (n), che e laconclusione desiderata.

Un modo piu semplice per dimostrare che il principio di induzione implica ilprincipio di induzione forte sfrutta l’equivalenza del principio di induzione con ilprincipio del minimo. Supponiamo che Prog(P ), e che esista (per assurdo) unn ∈ N tale che non P (n). Allora c’e un minimo m ∈ N tale che non P (m). Quindi∀y < n.P (y) e dalla progressivita di P segue che P (n), assurdo.

Esercizio 4.10. Dimostrare che il principio di induzione forte implica il principiodi induzione. [Suggerimento: supponiamo che P (0) e che P (n) → P (n + 1) perun generico n ∈ N, e assumiamo per assurdo che P non sia progressiva; allora perqualche k ∈ N abbiamo che ∀y < k.P (y) ma non P (k). Ci sono due casi: k = 0 ek 6= 0, che portano entrambi ad una contraddizione.]

Il principio di induzione forte ammette una generalizzazione interessante ainsiemi per i cui elementi e definita una nozione di altezza.

Corollario 4.11 (Principio di induzione strutturale). Sia A un insieme con unafunzione h : A → N. Data una proprieta P , assumiamo che per ogni n ∈ N:

(?) se P (a) per ogni a con h(a) < n, allora P (a) per ogni a con h(a) = n.

Allora P (a), per ogni a ∈ A.

Dimostrazione. Definiamo, per un generico n ∈ N:

P (n) se e solo se ∀a ∈ A (h(a) = n ⇒ P (a)).

Abbiamo Prog(P ), perche P (k) per ogni k < n implica che P (n), per l’ipotesi (?)su P . Quindi, per induzione forte, P (n) per ogni n ∈ N. Sia a ∈ A qualsiasi: ab-biamo allora P (h(a)), percio P (a), da cui la conclusione del principio di induzionestrutturale.

47

Naturalmente, questa formulazione del principio di induzione strutturale e signifi-cativa soltanto nel caso in cui la funzione h non sia a sua volta definita induttiva-mente sulla costruzione di A. Purtroppo, questo e quello che accade nella maggiorparte delle applicazioni: e cosı necessario in generale trovare un’altra giustifica-zione di questo principio, che tuttavia richiede l’approfondimento di tecniche cheescono dall’ambito di questo corso.

4.1.2 Induzione noetheriana

Il principio di induzione forte sfrutta una proprieta essenziale dell’ordine strettodei numeri naturali: non ci sono catene discendenti infinite della forma

. . . x2 < x1 < x0

che si esprime dicendo che la relazione < su N e ben fondata. In generale, unarelazione binaria R su un insieme non vuoto A e ben fondata se non esistonocatene discendenti infinite della forma

. . . x2Rx1Rx0

e possimo pensare di generalizzare il principio di induzione forte a tali relazionidefinendo, per una proprieta P di elementi di A

Prog(P ) ⇔ (∀yRx.P (y)) → P (x).

In effetti abbiamo il seguente:

Principio di induzione noetheriana: Se la relazione binaria R eben fondata su A, per ogni proprieta P di elementi di A:

Prog(P ) → ∀x ∈ A.P (x).

4.2 La caratterizzazione dei numeri naturali

Verso la fine del secolo scorso, Richard Dedekind ha trovato un modo puramenteformale di caratterizzare l’insieme dei numeri naturali

N = {0, 1, 2 . . .}

e di conseguenza di dare un significato preciso ai tre puntini ‘. . . ’ che sottointen-dono un modo unico di continuare la successione.

La descrizione seguente del lavoro di Dedekind e di alcuni sviluppi successivi etratta quasi testualmente da un articolo di Leon Henkin.

Se ammettiamo che non sia problematica l’esistenza di insiemi infiniti, tra cuiisolare l’insieme dei numeri naturali, allora e legittimo introdurre una classe distrutture del tipo di similarita adatto:

48

Definizione 4.12. Un modello di Peano e una struttura

〈N, 0, S〉che verifica le condizioni:

1. ∀x ∈ N.Sx 6= 0;

2. ∀xy ∈ N.x 6= y → Sx 6= Sy;

3. Principio di induzione:

∀G ⊆ N.(0 ∈ G ∧ ∀x ∈ N.x ∈ G → Sx ∈ G) → G = N.

Per ogni modello di Peano, si puo dimostrare il teorema di definizione perricorsione, che assume la forma seguente:

Teorema 4.13 (Definizione per ricorsione). Sia

N = 〈N, 0, S〉un modello di Peano, e sia A = 〈A, a ∈ A, f : A → A〉 una struttura dello stessotipo di similarita. Esiste un unico omomorfismo

h : N → A,

cioe una funzione N → A per cui valgano le condizioni:

h(0) = a

h(Sy) = f(hy).

Non consideriamo la dimostrazione di questo teorema, ma vediamo soltanto doverisiede la difficolta. Un argomento che potrebbe venire in mente per dimostrare ilteorema e il seguente, basato sul solo principio di induzione (3) della Definizione4.12:

I h e definita per 0, perche h(0) = a;

I sia h definita per y, allora h e anche definita per Sy, perche h(Sy) = f(hy);

I quindi, h e definita per ogni elemento di A.

Ma che cosa e h in questo argomento? Ovviamente, la funzione che si trattadi costruire, e questo argomento comporta pertanto una circolarita che non eaccettabile.

Dalle considerazioni precedenti si ottiene anche una giustificazione dell’uso del sim-bolo ‘. . . ’ per indicare il proseguimento della serie 0, 1, 2, . . .: essa puo continuareessenzialmente in un solo modo.

Corollario 4.14. I modelli di Peano sono a due a due isomorfi.

49

5 Sistemi formali

Vediamo ora una nozione che, oltre a essere fondamentale per la logica formale,offre un modo alternativo per precisare la nozione di insieme induttivamente ge-nerato: quella di sistema formale. Un sistema formale serve, essenzialmente, agenerare induttivamente un insieme, i cui elementi si chiameranno teoremi. Tan-to per avere presente un esempio, consideriamo un sistema formale i cui teoremisono (in corrispondenza biunivoca con) i numeri naturali.

Esempio 5.1. Abbiamo una costante 0 ed un operatore ad un argomento s. C’eun predicato unario num che e descritto (induttivamente) dall’assioma:

` num(0)

e dalla regola di inferenza:

` num (x)

` num(s(x))

Una regola di inferenza della forma:

t1, . . . , tnt

permette di passare da proposizioni t1, . . . , tn dette le premesse ad una proposi-zione t detta la conclusione. (Si intende che, nell’applicazione delle regole, ognivariabile deve essere rimpiazzata da un oggetto del sistema formale di categoria N .Un assioma, quando contiene variabili, si intende come uno schema che abbreviatutte le proposizioni (che di solito sono infinite di numero) che si possono ottenererimpiazzando le variabili con oggetti di categoria N .)

Possiamo usare il sistema formale appena descritto per produrre i teoremi

` num(0), ` num(s(0)), ` num(s(s(0))), . . .

mediante dimostrazioni che consistono di applicazioni della regola di inferenza apartire dall’assioma. Per esempio, abbiamo la dimostrazione:

` num(0)

` num(s(0)).

In generale, un sistema formale consiste dei seguenti elementi:

1. Operatori, includendo tra questi anche le costanti come operatori connessun argomento.

2. Predicati, e

50

3. Regole di inferenza, includendo tra questi anche gli assiomi, che sonoregole di inferenza con nessuna premessa.

E fondamentale il concetto di dimostrazione in un sistema formale. Vediamonela definizione:

Definizione 5.2 (Dimostrazione). (i) Un assioma ` t e una dimostrazione di sestesso.(ii) Se Π1, . . . , Πn sono dimostrazioni rispettivamente di t1, . . . , tn, e se

` t1, . . . ,` tn` t

e una regola, alloraΠ1, . . . , Πn

` t

e una dimostrazione di ` t.

Si puo associare ad ogni dimostrazione un numero naturale, detto la sua al-tezza, nel modo seguente:

• Una dimostrazione che consiste di un’unica occorrenza di un assioma haaltezza 0;

• Una dimostrazione della forma

Π1 . . . Πn

` t,

dove Π1, . . . , Πn sono dimostrazioni di altezze rispettive k1, . . . , kn, ha altezzamax{k1, . . . , kn}+ 1.

Vediamo ora alcuni esempi di sistemi formali:

Esempio 5.3. Uguaglianza di numeri naturali.Operatori: come nell’esempio 5.1.Predicati: oltre a quelli dell’esempio 5.1, una relazione = di categoria (N, N)F .Regole di inferenza: oltre a quelle dell’esempio , un assioma ` 0 = 0, e la regoladi inferenza

` x = y

` s(x) = s(y).

Esempio 5.4. Addizione di numeri naturali.Operatori: oltre a quelli dell’esempio 5.1, un operatore + di categoria (N, N)N .Predicati: come nell’esempio 5.3.

51

Regole di inferenza: oltre a quelle dell’esempio 5.3, l’assioma ` x + 0 = x e laregola di inferenza

` x + y = z

` x + s(y) = s(z).

Si possono introdurre variazioni a questo esempio. Una possibilita e quella disostituire la relazione = e l’operatore + con una singola relazione A di categoria(N, N, N)F con l’interpretazione: ‘la somma di e e ’, con l’assioma `A(x, 0, x) e la regola di inferenza

` A(x, y, z)

` A(s, s(y), s(z)).

Esempio 5.5. Prodotto di numeri naturali.Operatori: oltre a quelli dell’esempio 5.4, un operatore · di categoria (N, N)N .Predicati: come nell’esempio 5.4.Regole di inferenza: un assioma ` x · 0 = 0 e la regola di inferenza

x · y = z x + z = u

` x · s(y) = u.

Esempio 5.6. Numeri non primi.Operatori: come nell’esempio 5.5.Predicati: oltre a quelli dell’esempio 5.5, un predicato P di categoria (N)F .Regole di inferenza: oltre a quelle dell’esempio 5.5, la regola di inferenza

` s(s(x)) · s(s(y)) = z

` P (z).

Esercizio 5.7. Scrivere esplicitamente una dimostrazione che stabilisce che

` P (s(s(s(s(s(s(0)))))))

e un teorema del sistema formale dell’esempio 5.6.

Esercizio 5.8. (a) Costruire un sistema formale che abbia, tra gli altri, predicatiP e D di categoria (N)F tali che:

1. ` P (x) se e solo se x e un numero naturale pari, e

2. ` D(x) se e solo se x e un numero naturale dispari.

(b) Dimostrare che la equivalenze 1 e 2 sono vere, per induzione (Suggerimento:per ciascuna delle due equivalenze, l’implicazione da sinistra a destra deve esseredimostrata per induzione sull’altezza delle derivazioni, mentre l’implicazione dadestra a sinistra deve essere dimostrata per induzione sui numeri naturali).

52

Esercizio 5.9. (a) Costruire un sistema formale che abbia, tra gli altri, un predi-cato M di categoria (N)F tale che:

1. ` M(x) se e solo se x rappresenta un numero naturale multiplo di 3.

(b) Dimostrare che l’equivalenza 1 e vera.

Esercizio 5.10. Si consideri il sistema formale con a, b : N , un operatore dicategoria (N, N)N che forma il termine xy a partire da termini x, y : N ed ilpredicato unario S : (N)F , l’unico assioma ` S(ab) e le regole

` S(x)

` S(axb)

` S(x) ` S(y)

` S(xy)

Dimostrare che se ` S(x) in questo sistema formale, allora x contiene lo stessonumero di simboli a e b.

Vediamo ora una distinzione importante tra le regole di un sistema formale, pren-dendo come esempio un sistema formale che ha operatori o di categoria N , σ dicategoria (N)N e 2 di categoria (N, N)N . I predicati sono O di categoria (N)F ,W di categoria (N)F e T di categoria (N)F . Abbiamo due assiomi: ` O(o) e` T (o 2 o) e le seguenti regole di inferenza:

` O(x)

` O(σ(x))

` O(x) ` O(y)

` W (x 2 y)

` T (x 2 y)

` T (σ(x) 2 σ(y))

Consideriamo prima la regola:

` T (x 2 y)

` T (σ(σ(x)) 2 σ(σ(y)))).

Si vede che questa regola si puo ottenere componendo le regole di inferenza delsistema. Abbiamo qui un esempio di regola derivata. Invece, le seguentiregole:

` O(x)

` T (x 2 x)

` T (x 2 y)

` W (x 2 y)

non si possono ottenere componendo le regole di inferenza del sistema, e tuttavia,se usate, non permettono di ottenere nuovi teoremi rispetto a quelli che gia sipotevano dimostrare usando soltanto le regole di inferenza del sistema. Questeregole sono esempi di regole ammissibili.

Proposizione 5.11. La regola

` O(x)

` T (x 2 x)

e ammissibile.

53

Dimostrazione. Per induzione sull’altezza della dimostrazione della premessa dellaregola.Base: quando la premessa ha una dimostrazione di altezza 0, l’unica possibilita eche questa sia un assioma, precisamente l’assioma ` O(o). In questo caso allora laconclusione e semplicemente l’assioma ` T (o 2 o).Passo induttivo: se la premessa ha una dimostrazione di altezza > 0, allora deveavere la forma

...

O(y)

O(σ(y))

dove x = σ(y). Per ipotesi induttiva abbiamo che ` T (y 2 y), quindi T (σ(y) 2 σ(y))usando la regola di inferenza, e questo significa appunto ` T (x 2 x).

Esercizio 5.12. Dimostrare che la regola

` T (x 2 y)

` W (x 2 y)

e ammissibile.

Esercizio 5.13. Per il sistema formale dell’esercizio precedente:(1) si interpreti a come ‘(’ e b come ‘)’. Si dimostri che, se ` S(x), allora l’inter-pretazione di x e una sequenza ben formata di parentesi.(2) Dimostrare che la regola:

` S(aaxbb)

` S(axb)

non e ammissibile in questo sistema formale.

54