Logica Matematica Corso ACorso di Laurea in InformaticaAnno 2002-03

Indice

Indice 1 2 Introduzione Dal linguaggio naturale alla logica 2.1 Esercizi Logica proposizionale 3.1 Connettivi 3.2 Sintassi 3.2.1 Il linguaggio proposizionale 3.2.2 Analisi sintattica 3.2.3 Esercizi 3.3 Semantica 3.3.1 Tavole di verit` a 3.3.2 Esercizi 3.3.3 Validit` e conseguenza a 3.3.4 Esercizi 3.4 Sull implicazione Insiemi e algebre di Boole 4.1 Variabili 4.2 Algebra degli insiemi 4.3 Algebre di Boole 4.3.1 Esercizi 4.4 Algebra delle proposizioni 4.5 Rapporti tra proposizioni e insiemi

i 1 3 7 10 10 10 11 13 20 22 23 26 26 31 33 36 36 37 47 49 50 56

3

4

i

5

Relazioni 5.1 Prodotto cartesiano 5.2 Relazioni 5.2.1 Esercizi 5.3 Relazioni d ordine 5.4 Relazioni di equivalenza 5.5 Funzioni Forme normali 6.1 Denibilit` dei connettivi a 6.1.1 Esercizi 6.2 Forme normali disgiuntive 6.3 Forme normali congiuntive 6.4 Esercizi Dimostrazioni 7.1 Dimostrazioni dirette 7.2 Distinzione di casi 7.3 Sillogismo disgiuntivo 7.4 Contrapposizione e M odus tollens 7.5 Dimostrazioni per assurdo 7.6 Dimostrazioni in avanti e all indietro Alberi di refutazione 8.1 Il metodo 8.2 Correttezza e completezza 8.3 Forme normali 8.4 Esercizi Variabili e quanticatori Linguaggi predicativi 10.1 Alfabeto 10.2 Termini e formule 10.3 Variabili libere e vincolate 10.4 Interpretazioni 10.5 Sui quanticatori ristretti 10.6 Esercizi ii

60 60 61 64 65 69 71 75 75 77 77 79 83 86 86 90 93 95 96 102 104 104 110 114 115 117 122 122 123 131 134 137 138

6

7

8

9 10

11

Leggi logiche 11.1 Esercizi Quanticatori e dimostrazioni Sillogismi 13.1 Sillogismi categorici 13.2 Diagrammi di Venn Alberi di refutazione 14.1 Regole per i quanticatori 14.1.1 Esercizi 14.3 Applicazione ai sillogismi Il principio di induzione 15.1 I numeri naturali 15.2 Il principio di induzione 15.3 L induzione empirica 15.4 Il ragionamento induttivo 15.5 Esercizi 15.6 Denizioni ricorsive 15.6.1 Esercizi 15.7 Il principio del minimo 15.8 Varianti dell induzione 15.9 Errori e paradossi 15.10 Denizioni induttive 15.10.1 Esercizi

140 147 148 157 158 167 172 172 178 178 183 183 186 192 195 198 201 207 209 216 221 222 230

12 13

14

15

iii

1

Introduzione

Lo scopo di questo corso ` quello di rendere familiari con le forme di rae gionamento tipiche degli argomenti matematici; in informatica in particolare interessano soprattutto quelli che mirano a trovare la soluzione di un problema, a dimostrare che ` una soluzione e a presentarla come un algoritmo. e Un algoritmo ` un insieme articolato e connesso di istruzioni per risolvere e un problema; gli algoritmi non sono scritti in un linguaggio di programmazione, ma inizialmente nel linguaggio matematico o addirittura in quello naturale, e in questo devono essere formulati e riconosciuti tali, prima che la loro descrizione guidi alla traduzione nei relativi programmi. La maggior parte degli algoritmi che sostengono le prestazioni dei calcoltori non sono numerici ma riguardano manipolazioni di simboli (ad esempio lordinamento di una lista, o la fusione di due liste in una), quindi la prima consapevolezza - e competenza - da acquisire ` che il linguaggio e matematico non ` solo quello dei numeri, ma abbraccia qualsiasi argomento e che si possa riferire ad elementi strutturati. I ragionamenti relativi devono avere ed hanno lo stesso rigore di quelli numerici, e si svolgono con lausilio di un simbolismo appropriato, che ` e quello della logica matematica (= logica formale moderna). In vista della precisione richiesta, che non ammette licenze n eccezioni, e ` bene realizzare che ogni ragionamento si pu` rappresentare in forme stane o dardizzate di passaggi, e imparare a farlo, usando regole logiche e la propriet` a fondamentale dei numeri naturali che ` il principio di induzione. e Il corso ` lequivalente di quelli che nelle universit` americane si chiamano e a di Introduction to Proofs, che contengono in genere anche elementi di matematica discreta (strutture nite, combinatoria). Tali corsi sono concepiti come ponte tra la scuola secondaria e il college, rivolti a studenti che hanno appreso la matematica come un insieme di ricette e di calcoli, senza aver mai imparato a seguire e tanto meno a fare una dimostrazione. Nella scuola italiana qualche esperienza con le dimostrazioni si acquisisce con la geometria, ma limitatamente alle sue costruzioni e senza approfondire le ragioni di tale forma di ragionamento tipicamente matematica. N tale problema sar` indagato in questo corso introduttivo: lo studio delle e a dimostrazioni e lobiettivo della familiarit` con esse sono perseguiti non in a vista di spiegare il senso dellimpostazione deduttiva delle teorie, ma solo per abituare a vedere le connessioni tra i vari risultati, la loro mutua dipendenza e derivabilit`, il che aiuta anche a ricordarli meglio. a 1

Scrivere dimostrazioni presuppone comunque la comprensione degli argomenti trattati, e costituisce quindi unoccasione di ripasso di nozioni elementari di aritmetica che sono alla base del pensiero informatico. Nel testo, il segno !!! a margine segnala che si deve prestare particolare attenzione. !!! I riferimenti in nota del tipo Horstmann, p. 186 rimandano al testo del corso di Programmazione C. S. Horstmann, Java 2 . Le parti scritte in corpo minore sono letture con informazioni integrative. Il segno 2 ` usato per indicare la ne di una dimostrazione, al posto del e tradizionale QED.

2

2

Dal linguaggio naturale alla logica

La prima competenza che bisogna acquisire ` quella della formalizzazione, e ovvero della traduzione di frasi della lingua naturale, o del gergo matematico - misto di formule e di parole - in espressioni di un linguaggio semplicato e dalla sintassi precisa. La semplicazione ` guidata dalla volont` di restringersi ad espressioni e a matematiche o comunque di carattere logico. Non si considerano quindi frasi con indicatori di tempo e luogo (tempi dei verbi, avverbi di tempo, luogo e modo). Non si considerano espressioni di comando o di interrogazione, ma solo frasi dichiarative. Ci si riduce, come primo livello di semplicazione, a frasi elementari che esprimono fatti, e a loro combinazioni mediante particelle logiche. Le particelle logiche della lingua italiana sono parole come e, oppure, se e altre, che collegano frasi di senso compiuto. Nella lingua italiana queste parole da una parte sono polivalenti e ambigue, hanno diversi sensi - in generale discriminati dal contesto - e dallaltra si presentano in tante versioni equivalenti. La congiunzione e pu` ad esempio essere resa da una virgola, da e o anche, da ma e altre espressioni. Il senso avversativo di ma ` uno degli e aspetti che vengono lasciati cadere nel passaggio ad un linguaggio formalizzato, in quanto esprime unaspettativa soggettiva. La congiunzione ` resa e anche da costrutti pi` complicati, come sia . . . sia: vado sia che piova sia u che faccia bel tempo signica se fa bel tempo vado, e se piove vado, magari con laggiunta di un ugualmente che di nuovo esprime una determinazione soggettiva. La stessa congiunzione talvolta esprime qualcosa di pi` o di diverso dalla u semplice aermazione di entrambe le proposizioni congiunte; talvolta pu` o signicare e poi, come in si sposarono e vissero felici; talvolta signica e quindi, come in si immerge una cartina di tornasole, e diventa rossa (se questa frase ` intesa non come una descrizione di avvenimenti, nel qual caso e e signica e dopo, ma come come una caratterizzazione di particolari sostanze). La disgiunzione, o o oppure, talvolta ha un senso debole (A o B o tutte due), talvolta un senso esclusivo (A o B ma non tutte due). Laermazione piove o c` il sole ` compatibile con la situazione in cui e e piove da una nuvola anche se c` il sole. Il latino aveva due parole diverse e vel e aut, ma la distinzione non ` rimasta nelle lingue moderne. La e 3

dierenza non sempre ` espressa dalla semplice ripetizione di o (o A o e B) ma pi` spesso dallenfasi della pronuncia; il tono e il contesto devono u essere tenuti presenti per capire il signicato inteso. C` voluto del tempo e per tornare a riconoscere due particelle diverse: Alcuni dicono che per la verit` di una disgiunzione si richiede a sempre che uno dei disgiunti sia falso, perch se entrambi fossero e veri non sarebbe una vera disgiunzione, come dice Boezio. Questo per` non mi piace. In realt` io dico che se entrambe le parti di o a una disgiunzione sono vere, lintera disgiunzione ` vera (Walter e Burleigh, De Puritate, XCI, 3-19, XIV sec .) La disgiunzione in italiano talvolta ` resa con ovvero, ma questa parola e signica anche cio`, vale a dire. e Qualche volta la stessa frase pu` essere espressa sia con la e che con o la o. Si pu` dire equivalentemente sia Tutti, bianchi o neri, hanno o unanima, sia Tutti, bianchi e neri hanno unanaima. Laermazione mele e pere sono frutti vuole anche dire che se si prende una mela o una pera, si ha un frutto. La negazione di una frase si realizza in diversi modi, di solito con la particella non, inserita per` (o soppressa) in vari modi nella frase da negare, o con diversi costrutti che coinvolgono altre parole, in particolare i verbi. Da piove a non piove, o non ` vero che piove; da qualche volta piove a e non piove mai; da piove sempre a qualche volta non piove; da non ama nessuno a ama qualcuno, da ` bello a ` brutto, e cos` via. Per e e negare non piove non si dice non non piove ma piove o non ` vero e che non piove. La parola se ` unaltra particella dai molteplici sensi, e dalle molteplici e 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 signicato temporale, come poi. Quando si aerma se A allora B, A ` detta condizione suciente per e B, e B condizione necessaria per A. A ` condizione suciente per B ` un e e altro modo di esprimere se A allora B. Al se . . . allora sar` dedicata una discussione speciale per la sua ima portanza rispetto allinferenza logica. In considerazione di queste ambiguit` e molteplicit` di espressione, un a a primo passo ` quello di introdurre una sola versione ssa delle particelle e 4

logiche, sia come simboli che come signicati; fatto questo tuttavia, la competenza pi` importante consiste poi nel saper tradurre le frasi della lingua u naturale, disambiguandole quando necessario e possibile, e trovando la versione formale corrispondente. Tale standardizzazione ` necessaria per poter comunicare con le macchine; e ma prima di parlare alle macchine occorre parlare ad altre persone e a se stessi per costruire gli algoritmi. Nellapprendere a formalizzare si deve anche ranare la propria logica naturale. Tuttavia non esiste un elenco completo di quelle che nei linguaggi naturali si riconoscono come particelle logiche. Non abbiamo menzionato ad esempio n . . . n, o a meno che1 . Qualche volta, parole che non seme e brano particelle logiche possono essere usate in questo modo, e lo si riconosce nella formalizzazione: quando ` di solito una determinazione temporale, e ma quando piove, prendo lombrello pu` essere reso da se piove, prendo o lombrello. Nellottica della formalizzazione, chiedere cosa signica quando piove, prendo lombrello non ` altro che la richiesta di tradurre la frase in unaltra e in cui compaia una particella logica (una di quelle riconosciute tali) e scompaia quando; cos` si vede subito a quale delle particelle note la parola ` e equivalente; ma non sempre ` evidente una possibile riduzione di una frase e ad unaltra, n sempre una sola. e Esistono peraltro parole di dicile catalogazione, che sembrano particelle logiche in quanto legano due frasi, ma hanno sfumature che si perdono nella formalizzazione: ad esempio siccome piove, prendo lombrello, o prendo lombrello perch piove potrebbe essere espressa dallasserzione unica la e pioggia ` la causa del mio prendere lombrello, che coinvolge per` la delie o cata parola causa; la frase contiene tuttavia una determinazione temporale (siccome sta piovendo), o anche una qualitativa (con un implicito riferimento forse a un particolare tipo di pioggia - a dirotto) che non la rende del tutto equivalente a quando piove, prendo lombrello. Esistono parimenti frasi di dicile interpretazione; la stessa siccome piove, prendo lombrello, o poich piove, prendo lombrello invece che e una frase pu` essere considerata un argomento, poich in essa si aerma o e un fatto, che piove, oltre a un legame condizionale. Potrebbe corrispondereSi noti luso della o nella nostra frase, di nuovo scambiabile con e: si voleva dire che non abbiamo menzionato n . . . n e non abbiamo menzionato a meno che; luso e e di o suggerisce unaltra versione equivalente: una particella che sia n . . . n o a e e meno che non labbiamo menzionata.1

5

ad un esempio di modus ponens (si vedr` a suo tempo): Se piove, prendo a lombrello. Piove. Quindi prendo lombrello. Useremo simboli speciali per rappresentare alcune particelle logiche che sembrano di uso pi` comune, almeno nei discorsi meno sosticati. Per queste u si potrebbero usare parole della lingua italiana - o comunque di una lingua naturale - ssando per convenzione in modo rigido il loro signicato, come si fa ad esempio quando per la congiunzione si usa and, in informatica. Quando si usano and, e simili, si vuole che il linguaggio sia friendly perch e ci si deve concetrare su altro; noi invece vogliamo concentrarci proprio su quelle parole, per cui sono meglio simboli nuovi, insoliti, che sorprendano; la scelta di simboli articiali ` pi` vantaggiosa anche perch, procedendo, questi e u e simboli non saranno soltanto abbreviazioni, ma insieme ad altri diventeranno una struttura che ` essa stessa, se si vuole, oggetto di una teoria matematica, e con suoi problemi specici. Ad esempio una prima questione comprensibile anche solo sulla base di quanto detto nora ` se le particelle scelte sono anche fondamentali, e in e che senso, o se sono sucienti, o quante ce ne potrebbero essere. Unaltra riguarda lequivalenza, aermata per alcuni esempi precedenti, tra frasi diverse espresse con particelle diverse. Queste strutture forniranno un ricco campo di scrittura di algoritmi non numerici ma simbolici, applicati a liste o alberi o altre strutture di dati, Il signicato delle particelle logiche ` lo stesso a prescindere dal lessico, e e per studiarlo occorre non ssarsi su un linguaggio particolare; la trattazione deve valere per tutti, quindi useremo lo stesso articio matematico di usare lettere (come p, q e altre) per indicare entit` non precisate, che nelle a applicazioni dovranno essere asserzioni sensate. Oggetto di studio saranno dunque congurazioni simboliche astratte del tipo p e non q2 che non rientrano apparentemente nellesperienza comune; si consideri tuttavia che le persone sono in grado di pronunciare tutte le frasi del tipo c` una tavolo e non c` una sedia, c` una quadrato e non c` e e e e un tavolo, . . . e cos` via per tutte le circa diecimila parole del lessico di una persona (colta). Il numero di queste e di tutte le altre frasi (come se c` e un tavolo non c` una sedia) supera il numero dei neuroni del cervello, per e cui, anche ammettendo - che non ` - che ogni frase richieda un neurone o e una combinazione di neuroni per la memorizzazione, non si pu` pensare che o tutte le frasi della competenza linguistica siano immagazzinate in memoria;2

Al posto di e e non ci saranno i simboli speciali corrispondenti.

6

questo signica che, insieme al lessico, sono immagazzinati invece schemi che possiamo immaginare di rappresentare (esternamente) come p e non q, e che questi fanno parte dellinconscio cognitivo3 . Si tratta solo di diventarne consapevoli. Loggetto di studio della logica sono tali schemi di frasi, non le frasi, e per questo si parla di logica formale. La formalizzazione del linguaggio naturale non ` qualcosa di meccanico e e di compiuto per lintera gamma delle potenzialit` espressive. Esistono a argomenti controversi e ancora oggetto di discussioni e di proposte per una formalizzazione soddisfacente - che rientrano in studi pi` avanzati. u La restrizione alle frasi dichiarative ` uno di questi, dal momento che i e comandi ad esempio hanno un ruolo apparentemente importante nella programmazione. Abbiamo visto qualche dicolt` con siccome. Allo stesso modo ` disa e cutibile se ` necessario che . . . sia da considerare una particella logica: ` e e necessario che al giorno segua la notte, o al giorno segue necessariamente la notte, non sembra equivalente a al giorno segue la notte, e neanche a al giorno segue sempre la notte, che ` equivalente alla precedente se segue, e privo di determinazioni temporali, assorbe il sempre; anche necessariamente 2 + 2 = 4 forse dice di pi` di 2 + 2 = 4, ma non ` del tutto chiaro u e che cosa. Ancora, ` possibile sostenere che il costrutto ` vero che . . . ` pleonase e e tico, in quanto ` vero che piove ` equivalente a piove, ma ` altrettanto e e e possibile sostenere che non ` possibile farne a meno. e

2.1

Esercizi

1. Esaminare i seguenti discorsi (e altri tratti a scelta da fonti letterarie o giornalistiche) ed individuare le particelle logiche e le frasi elementari (racchiudendole tra parentesi e se necessario riformulando in modo equivalente i discorsi e le loro frasi). Se non ` possibile prevedere tutte le azioni delle persone ale lora o luniverso non ` deterministico o le persone non sono e perfettamente razionali. Chi sostiene il determinismo deveNon freudiano. Signica che nel cervello ` memorizzato (hardwired ) uno schema del e genere; non sappiamo come, ma di esso diventiamo coscienti attraverso luso delle variabili.3

7

dunque sostenere che se le azioni delle persone sono prevedibili allora le persone sono perfettamente razionali. Se non ` possibile prevedere tutte le azioni delle persone ale lora o luniverso non ` deterministico o le persone non sono e perfettamente razionali. Chi sostiene il determinismo deve dunque sostenere che se le azioni delle persone non sono prevedibili allora le persone non sono perfettamente razionali. Suggerimento. Introdurre abbreviazioni per le frasi che si ripetono, in modo da arrivare, nel caso del primo brano, a Se non Prev allora o non Det o non Raz. Chi sostiene Det allora deve sostenere che se Prev allora Raz e ancora, togliendo il chi sostiene, a Se non Prev allora o non Det o non Raz. Se Det allora (se Prev allora Raz). Le abbreviazioni aprono la strada alluso delle lettere per indicare proposizioni; quando si saranno anche introdotti simboli per le particelle logiche e se ne saranno viste alcune leggi, sar` anche facile esa primere un giudizio sulla corettezza o meno dellargomento. Altri esempi: Se le persone sono interamente razionali, allora o tutte le azioni di una persona possono essere previste in anticipo o luniverso ` essenzialmente deterministico. Non tutte le e azioni di una persona possono essere previste in anticipo. Dunque, se luniverso non ` essenzialmente deterministico, e allora le persone non sono interamente razionali. Il numero di queste e di tutte le altre frasi supera il numero dei neuroni del cervello, per cui, anche ammettendo - che non ` - che ogni frase richieda un neurone o una combinazione di e 8

neuroni per la memorizzazione, non si pu` pensare che tutte o le frasi della competenza linguistica siano immagazzinate in memoria. 2. Con il costrutto se . . . allora e le frasi dico x e x ` una verit` e a esprimere: dico tutta la verit` e solo la verit`. a a 3. Scrivere con le giuste particelle logiche: a) non c` fumo senza arrosto e b) fumo vuol dire fuoco. 4. Trovare altre particelle logiche della lingua italiana, oltre a quelle menzionate nel testo. 5. Discutere se cio` ` una particella logica o no, e a quali altre ` evene e e tualmente equivalente, in diversi contesti. 6. Cosa signica per voi necessariamente 2 + 2 = 4?

9

33.1

Logica proposizionaleConnettivi per per per per per per la negazione la congiunzione la disgiunzione inclusiva la disgiunzione esclusiva il condizionale se . . . allora il bicondizionale se e solo se

Useremo per le particelle logiche i simboli:

senza escluderne a priori altri, e li chiameremo connettivi proposizionali. La negazione ` un connettivo unario (cio` agisce su una proposizione), gli altri e e indicati sono connettivi binari (cio` connettono due proposizioni). e Introdotti i simboli per i connettivi, occorre dare le loro precise regole duso, sia dal punto di vista sintattico (dove scriviamo ad esempio per formare la negazione di unasserzione?), sia dal punto di vista semantico (come interpretiamo il signicato delle frasi composte, in funzione delle frasi componenti?).

3.2

Sintassi

La necessit` di fornire regole rigide per la formazione delle frasi ` data dalla a e volont` di evitare le ambiguit` possibili nelle lingue naturali: a a la vecchia porta la sbarra ` un esempio di frase essenzialmente ambigua, se non sono indicati quali sono e soggetto e verbo. Si tratta di unambiguit` che ` risolvibile nel contesto della a e storia raccontata, e nel parlato soprattutto con le pause. Altre ambiguit` si riferiscono proprio alla distribuzione dei connettivi; a supponiamo ad esempio di leggere un problema: x2 + 4x + 3 < 0 e x < 3 o x > 2. Lo studente tende a rispondere risolvo lequazione, poi interseco con x < 3 e unisco con x > 2, ma ` lordine di queste operazioni che conta, che non e sempre ` quello del rst come, rst served nella scrittura del problema. e Si pu` intendere che si chieda quali siano i valori per cui o si ha che o 10

x2 + 4x + 3 < 0 e x < 3 o si ha che x > 2; si pu` anche intendere che si chieda quali siano i valori per cui si ha o x2 + 4x + 3 < 0 ma ristretti ad essere x < 3 o x > 2. Nel primo caso la risposta ` (2, +), nel secondo caso ` (2, 1). e e Naturalmente lambiguit`, che nel parlato si risolve con le pause, nella a scrittura matematica si risolve con le parentesi, il primo caso essendo (x2 + 4x + 3 < 0 e x < 3) o x > 2 e il secondo caso x2 + 4x + 3 < 0 e (x < 3 o x > 2). La stessa soluzione delle parentesi1 adotteremo per le formule logiche. 3.2.1 Il linguaggio proposizionale

Le frasi di ogni linguaggio sono stringhe2 di simboli dellalfabeto. Lalfabeto del linguaggio proposizionale contiene, oltre ai connettivi, le parentesi sinistra ( e destra ), e un insieme L di lettere proposizionali. Tali lettere non le chiamiamo variabili, come talvolta si usa, perch il loro e dominio di variabilit` (le frasi) ` troppo indenito. a e Le parole accettabili di questo alfabeto si chiameranno proposizioni , un termine tecnico per distinguerle dalle asserzioni dei linguaggi dotati di senso. Quello che importa delle proposizioni ` solo la loro struttura formale, che poi e si dovr` riconoscere nelle frasi dei linguaggi naturali o matematici, quando aLe parentesi sono state anche aggiunte al linguaggio naturale, ma solo nella scrittura - almeno la saggistica, meno la letteratura - non nel parlato. 2 Con stringa sintende o lista o successione nita. Non ` necessario entrare nei partie colari del tipo di rappresentazione dei dati che si sceglie, nch non si deve implementare. e1

11

il linguaggio proposizionale sar` interpretato sostituendo alle lettere frasi a relative ad un precisato argomento. Non tutte le stringhe di simboli dellalfabeto sono ammesse come proposizioni. Una generica stringa, anche illecita, ` chiamata parola. e La denizione dellinsieme P delle proposizioni stipula innanzi tutto che: Per ogni lettera p L, (p) ` una proposizione atomica e (cio` non ulteriormente analizzata e scomposta nel contesto della trattazione). e Per il resto della denizione, occorre parlare di proposizioni qualunque e della loro composizione; ` quindi necessario avere delle variabili che variano e sullinsieme delle proposizioni, e che si chiamano metavariabili 3 ; useremo le lettere A, B, . . . Si danno quindi le seguenti clausole: 1 Se A ` una proposizione, anche (A) lo `. e e 2 Se ` un connettivo binario, e se A e B sono proposizioni, anche (A B) e lo `. e Le clausole della denizione sono anche regole di costruzione. Sintende che ogni proposizione si ottiene applicando un numero nito di volte le clausole della denizione. Esempi 1. (p q) non ` una proposizione perch non ` un elemento dellalfabeto4 . e e e 2. p q non ` una proposizione, perch: e e Ogni proposizione contiene almeno una parentesi5 .La ragione di questo termine, non usato altrove in matematica, ` che queste variabili e indicano elementi di una struttura che ` anchessa un linguaggio, e che contiene a sua e volta variabili (le lettere) che devono essere interpretate su frasi; meta signica sopra, oltre, e deriva dal greco, dove signicava piuttosto dopo; ma dopo che sono stati chiamati metasica i libri di Aristotele che seguivano quelli di sca, ` venuta questa e variante di signicato. 4 Per i linguaggi formali si chiede sempre che lalfabeto e le sue diverse categorie di simboli siano insiemi decidibili, cio` tali che lappartenenza o meno ad essi di un simbolo e possa essere decisa da un algoritmo. 5 Tutte queste propriet` diventeranno esercizi sul principio di induzione nel paragrafo a 15.3

12

3. )p( non ` una proposizione, come non lo sono p o )p), perch: e e Ogni proposizione inizia con una parentesi ( e termina con una parentesi ). 4. ((p) (q)) ` una proposizione perch ottenuta dalle proposizioni atome e iche (p) e (q) con una applicazione della clausola induttiva relativa a . 5. (((p) (q))) ` una proposizione perch ottenuta dalle proposizioni e e atomiche (p) e (q) con una prima applicazione della clausola induttiva relativa a e una seconda applicazione della clausola relativa a . 6. ((p) non ` una proposizione perch: e e In ogni proposizione il numero di parentesi sinistre ` uguale al numero e di parentesi destre. 7. (pq) non ` una proposizione perch non ` atomica e non contiene nessun e e e connettivo. Se una proposizione ` della forma (A) o della forma (A B), e sono e rispettivamente il suo connettivo principale, e A e B le sottoproposizioni immediate. Si dice che (A) ` una negazione, citando il suo connettivo principale, la e negazione di A - e si legge non A; si dice che (A B) ` una congiunzione, e la congiunzione di A e B - e si legge A e B; A e B sono le proposizioni congiunte in (AB); analogamente per la disgiunzione6 (AB) - che si legge A o B; (A B) si pu` leggere o A o B; (A B) si dice un condizionale o - e si legge se A allora B; A si chiama antecedente, e B conseguente; (A B) si dice bicondizionale - e si legge A se e solo se B. 3.2.2 Analisi sintattica

Una proposizione ` una lista di simboli, ma ` anche passibile di una rappe e resentazione con una diversa struttura. A ogni proposizione ` associato un e 7 albero di costruzione, o di analisi sintattica , che ` un albero etichettato nito e binario.6 7

Chiameremo semplicemente disgiunzione, e disgiunzione esclusiva o forte. In inglese parsing.

13

Un albero binario8 ` un insieme parzialmente ordinato9 X con una ree lazione con le seguenti propriet`. a ` una relazione riessiva, transitiva e e antisimmetrica10 . Gli elementi dellalbero si chiamano nodi . Se x y, si dice che y ` un successore, o un discendente di x. Esiste un nodo minimo e r tale che r x per ogni nodo di X, e si chiama radice. I nodi a tali che non esiste b = a per cui a b si chiamano foglie11 . Ogni nodo che non sia una foglia ha uno o al massimo due successori immediati12 , dove si dice che b ` un successore immediato di a se a b, a = b e non esiste un c tale che e a c b, con c = a e c = b. La rappresentazione usuale di un albero binario ` di questo tipo: e

dove con la freccia si indica il successore immediato, la radice ` in alto e e lalbero cresce verso il basso. Un ramo ` un insieme totalmente ordinato13 di nodi che va dalla radice e a una foglia. La sua lunghezza ` il numero di nodi che vi appartengono. e Laltezza dellalbero ` la massima lunghezza dei suoi nodi. e Un albero si dice etichettato se ad ogni nodo ` associato un elemento di e qualche insieme pressato, che si chiama etichetta.Esistono denizioni leggermente diverse, pi` o meno generali, ad esempio con una o u pi` radici; diamo quella che serve ai nostri scopi. u 9 Presenteremo in seguito la denizione di relazione dordine e della terminologia connessa; per ora ` suciente la rappresentazione data sotto. e 10 Questo signica che x x, che se x y ey z allora x z e che x y ey x implicano x = y. 11 Esistono sempre se lalbero, ovvero linsieme dei nodi X, ` nito. e 12 Unaltra terminologia ` gli. Se ci sono due gli, sintende che sono esplicitamente e distinti il primo e il secondo - sulla pagina, a sinistra e a destra. 13 Per ora basti intendere che ogni nodo del ramo salvo lultimo ha esattamente un successore immediato.8

14

Lalbero sintattico di una proposizione ` denito in questo modo: e la radice ` etichettata con la proposizione data e ogni nodo ha nessuno, uno o due successori immediati a seconda che la proposizione etichetta del nodo sia atomica, o della forma (A), o della forma (A B). Nel secondo caso il successore ` etichettato con e A, nel terzo caso i due successori sono etichettati rispettivamente con A e con B. Si chiama altezza della proposizione laltezza del suo albero di costruzione. Esempio Lalbero per (((p) ((q))) ((p))) ` il seguente: e (((p) ((q))) ((p))) ((p) ((q))) (p) ((q)) (q) ((p)) (p)

La sua altezza ` quattro. e Le etichette dei nodi dellalbero di costruzione di una proposizione sono le sue sottoproposizioni . Le lettere che compaiono nelle (proposizioni atomiche nelle) foglie sono le lettere che occorrono nella proposizione; si dice che un simbolo occorre in una proposizione se ` un elemento della lista (che ` la e e proposizione); le occorrenze di un simbolo in una proposizione sono i vari posti della lista in cui il simbolo si presenta. Se p, . . . , q sono le lettere che occorrono nella proposizione A, si scrive anche A[p, . . . , q]. Qualche volta si usa questa notazione anche se p, . . . , q sono solo alcune delle lettere che occorrono in A, o viceversa se le lettere che occorrono in A sono incluse tra le p, . . . , q; invece di introdurre notazioni apposite, la dierenza sar` chiara a dal contesto o da esplicite precisazioni. Le parentesi sono essenziali per individuare il connettivo principale di una proposizione, e quindi per costruire il suo albero sintattico. Per individuare il connettivo principale, si usa un contatore di parentesi14 .14

Horstmann, p. 76.

15

Il contatore scansisce la lista da sinistra verso destra, e scatta di +1 quando incontra una parentesi sinistra, di 1 quando incontra una parentesi destra. Condizione necessaria anch una parola sia una proposizione ` che e e il contatore, inizializzato a 0, torni a 0 solo alla ne della parola. Perch poi !!! e la parola sia una proposizione bisogna che gli altri simboli siano distribuiti in mezzo alle parentesi in modo corretto. Ad esempio per (((p) ((q))) ((p))) il contatore assume i valori: 0 1 2 3 2 3 4 3 2 1 2 3 2 1 0. Per individuare il suo possibile connettivo principale, si elimina la prima parentesi, e si mette di nuovo in funzione il contatore su ((p) ((q))) ((p))) notando che esso assume questa volta i valori 0 1 2 1 2 3 2 1 0 quando arriva alla ne di ((p) ((q))). Questa parola ` candidata ad essere una sottoproposizione; nel prossimo e posto a destra compare un connettivo , candidato a essere il connettivo principale, e se anche ((p)) ` una parola si sar` trovato che la parola data ` una disgiunzione di ((p) e a e ((q)) e di ((p)). Poich questultima si vede facilmente che ` una proposizione, proseguiamo e e lanalisi di ((p) ((q))). Il contatore applicato a questa assume i valori 0 1 2 1 2 3 2 1 0 16

e applicato a (p) ((q))) i valori 0 1 0 alla ne di (p), individuando a destra il connettivo , che lega (p) e ((q)). In questo modo si arriva a costruire lalbero sintattico. Alcune parentesi sono sovrabbondanti, ma solo quelle della coppia pi` esu terna e quelle nelle proposizioni atomiche, dove sono usate sia per uniformit` a sia per sottolineare la dierenza tra una lettera come elemento dellalfabeto e la lettera come proposizione15 . Ma ora per comodit` di scrittura e leta tura ` meglio ridurre il numero di parentesi con le seguenti convenzioni: e non si scrivono le parentesi intorno alle lettere nelle proposizioni atomiche, non si scrivono le parentesi pi` esterne, e si eliminano alcune coppie di paru entesi intorno ad alcune sottoproposizioni, con un criterio suciente a farle ripristinare in modo corretto formulato nel seguente modo. Si ordinano per priorit` i connettivi secondo le seguente graduatoria: a Data quindi una parola le cui parentesi non rispettano le condizioni per essere una proposizione (s` per` la parit`, il fatto che il numero di parentesi o a sinistre sia uguale a quello delle parentesi destre, il fatto che in ogni punto che non sia lultimo il numero di sinistre ` maggiore o uguale di quello delle e destre, e tutte le propriet` che si mantengono quando si eliminano alcune a coppie di parentesi corrispondenti16 ), le parentesi si rimettono secondo questo procedimento: prima si rimettono le parentesi a sinistra e a destra delleTra alfabeto e parole c` una dierenza di tipo logico. Nei linguaggi naturali si presene tano alcune eccezioni, come le vocali e e o usate come parole, ma ` raro che si parli e dellalfabeto; quando lo si fa, si scrive appunto e e non e. 16 In questo caso, in seguito, la chiameremo ancora proposizione.15

17

lettere17 ; quindi si prende in esame la negazione, se occorre nella parola; si esamina unoccorrenza della negazione che non abbia immediatamente alla sua destra unaltra negazione18 . Alla sua destra c` una parentesi sinistra e - altrimenti si pu` dire che quella parola non proviene dalla eliminazione o di coppie di parentesi da una genuina proposizione (brevemente, che non ` una proposizione). Sia la parola alla sua destra che termina con la e parentesi destra che chiude la parentesi sinistra. Per trovare la parentesi destra che chiude la parentesi sinistra si usa di nuovo il contatore in modo !!! ovvio. Allora si rimette una parentesi sinistra alla sinistra della negazione, se non c` gi`, e una parentesi destra a destra di , se non c` gi`, ottenendo e a e a (); si ripete per ogni occorrenza di , quindi si passa ai connettivi binari e per ciascuno di essi , nellordine di priorit`, si considerano le pi` corte a u sottoparole e a sinistra e a destra di che sono chiuse tra due parentesi sinistre e destre, e si introduce una parentesi ( a sinistra di e ) a destra di , se non ci sono gi`, ottenendo ( ), e cos` via. a Per occorrenze dello stesso connettivo si conviene lassociazione a destra, cio` ad esempio con A B C si intende A (B C). e Esempi Data p q p, la reintroduzione delle parentesi avviene attraverso questa successione di passi: 1 2 3 4 (p) (q) (p) (p) ((q)) ((p)) ((p) ((q))) ((p)) (((p) ((q))) ((p))). Data p (q r) 1 217

(p) ((q) (r)) (p) ((q) ((r)))

Questo praticamente si pu` fare anche alla ne, per non appesantire la scrittura, se o lo si fa del tutto. 18 A parte questa condizione, lordine in cui si lavora sulle eventuali diverse occorrenze della negazione non ` rilevante; lo si pu` anche fare in simultanea. Lo stesso vale per gli e o altri connettivi.

18

3 4 5

(p) ((q) (((r)))) (p) (((q) (((r))))) ((p) (((q) (((r))))))

oppure, per rendere pi` chiara la lettura u 1 2 3 4 p (q (r)) p (q ((r))) p ((q ((r)))) (p ((q ((r)))))

rimettendo inne le parentesi intorno alle lettere. Si noti che se fosse stata data p q r la reintroduzione delle parentesi avrebbe portato a una diversa proposizione: ((p) (((q)) (((r))))) (esercizio, e si confrontino i due alberi sintattici), per cui le due parentesi lasciate in p (q r) sono essenziali, se si vuole parlare della !!! proposizione ((p) (((q) (((r))))) . Non ` comunque necessario n obbligatorio togliere tutte le parentesi; e e per agevolare la lettura, o allinizio quando non si ` ancora fatta esperienza, e pu` essere conveniente lasciarne alcune, che pure grazie alle convenzioni si o potrebbero eliminare. Cos` ad esempio si potr` scrivere p (q r) invece a di p q r oppure (p q) r invece di p q r. Le parentesi si rimettono solo se si ha necessit` di capire quale ` il cona e nettivo principale, per svolgere lanalisi sintattica. Le parentesi esterne possono tranquillamente essere tralasciate, nch la proposizione non deve essere e combinata con altre mediante qualche connettivo. Lalbero sintattico si pu` costruire direttamente anche per le espressioni o prive di tutte le parentesi, se si tiene presente la priorit` dei connettivi. Il a connettivo principale ` sempre quello di priorit` pi` bassa. e a u !!! Esempio Lalbero per p q p ` il seguente, essendo il connettivo e principale:

19

p q p p q p q q. p p

Le etichette sono diverse, ma lalbero ` lo stesso della proposizione analizzata e in precedenza. Dal prossimo paragrafo, chiameremo proposizioni anche le parole ottenute da proposizioni per eliminazione di parentesi. 3.2.3 Esercizi (p (q) (p)) q) ((p) q) ((p) ((q))) ((p) ) p ((p)). 2. Vericare quali delle seguenti parole sono proposizioni e quali no, costruendo lalbero sintattico e spiegando dove eventualmente la costruzione fallisce e per quale ragione: ((p)) ((p) ((q) ((r)))) (((p) (q))) ((((p) (q)) (p)) (q)) (((p)) (q)) (r)) ((((p)) (q)) (r)).

1. Discutere se le seguenti parole sono proposizioni:

20

3. Dare ragioni per le seguenti propriet` (e si vedano poi gli esercizi in a 15.10.1): Ogni proposizione ha lunghezza maggiore o uguale a 3. In ogni proposizione non atomica occorre un connettivo. In nessuna proposizione occorrono due connettivi consecutivi. In nessuna proposizione occorre la sottosequenza (), n )p. e In ogni proposizione la sua lunghezza (come lista) ` maggiore della sua e altezza. 4. Una misura di complessit` delle proposizioni ` una funzione dalle propoa e sizioni nei numeri naturali che soddisfa la condizione che la misura di una proposizione ` maggiore delle misure delle proposizioni compoe nenti, e le atomiche hanno tutte la stessa misura minima. Il numero (di occorrenze) dei connettivi ` una misura di complessit`, come lo sono e a la lunghezza (della stringa) e laltezza (dellalbero sintattico). Trovare la relazione tra il numero di occorrenze di connettivi e laltezza. Dimostrare con un controesempio che il numero di connettivi diversi non ` una misura di complessit`. e a 5. Eliminare le parentesi, applicando le convenzioni sulla priorit` dei cona nettivi, dalle seguenti proposizioni: ((p) (((q)) ((p)))) (((((p)))) ((p) (q))) ((((p)) ((q))) (((p)) (q))) (((p) ((q))) ((p) ((q)))). 6. Reintrodurre le parentesi nelle seguenti parole in modo da ottenere, se possibile, proposizioni, o se no spiegare il perch: e p p q r p q r (p q) p q pqpq 21

p q r p p q r r p ( r q) p q p q p q r.

3.3

Semantica

La semantica ha a che fare con le interpretazioni, grazie alle quali le proposizioni vengono ad assumere un senso (che a noi non interessa, lo bypassiamo) e diventano vere o false. Tale attribuzione nale di valori di verit` ` per noi ae loperazione di interpretazione, che viene studiata in astratto per vedere se abbia propriet` generali, indipendenti dalle interpretazioni concrete. a I valori di verit` saranno rappresentati dallinsieme19 {0, 1}. Ci si colloca a con tale scelta nellottica della logica classica a due valori. Nellinsieme {0, 1} ` necessario introdurre un minimo di struttura20 : la e pi` per semple consiste in convenire che 0 < 1 e usare la sottrazione come se u 0 e 1 fossero numeri interi, con | x | a indicare il valore assoluto. Uninterpretazione ` una funzione21 i : L {0, 1}; una valutazione ` e e una funzione v : P {0, 1} che soddisfa le seguenti condizioni22 : v((A)) v((A B)) v((A B)) v((A B)) v((A B)) v((A B))19 20

= = = = = =

1 v(A) min{v(A), v(B)} max{v(A), v(B)} | v(A) v(B) | max{1 v(A), v(B)} 1 | v(A) v(B) | .

Altre notazioni per i valori di verit` sono {V, F }, {T, F }, { , }, True, False. a Vedremo in seguito che si pu` considerare unalgebra di Boole. o 21 La notazione con la freccia sar` spiegata in seguito; per ora si intenda che a ogni a lettera corrisponde un valore di verit`, e per v sotto che a ogni proposizione corrisponde a o 0 o 1. 22 Si noti che in v((A)) e in altre espressioni analoghe ci sono due tipi di parentesi, che andrebbero tipogracamente distinte; quelle interne sono le parentesi della proposizione, quelle esterne servono per la notazione funzionale v(x).

22

In alternativa, si considerano 0 e 1 come interi modulo23 2, {0, 1} = Z2 con le solite operazioni aritmetiche e si scrivono le condizioni: v((A)) v((A B)) v((A B)) v((A B)) v((A B)) v((A B)) = = = = = = 1 v(A) v(A) v(B) (v(A) + v(B)) v(A) v(B) v(A) + v(B) 1 v(A) (1 v(B)) 1 (v(A) + v(B)).

Ogni interpretazione i si estende a una valutazione i ponendo i ((p)) = i(p) e denendo i sulle proposizioni composte in modo da soddisfare le condizioni della denizione di valutazione. Per ogni valutazione v il valore di verit` di una proposizione A si ottiene a applicando ai valori delle sottoproposizioni immediate di A una funzione, che dipende dal connettivo principale di A. 3.3.1 Tavole di verit` a

Ad ogni connettivo ` associata una funzione di verit` , cio` una funzione da e a e {0, 1}n in {0, 1}, dove n ` il numero di argomenti del connettivo ({0, 1}n ` e e linsieme delle n-uple di 0 e 1). Per il loro carattere nito queste funzioni sono rappresentate da tabelle, che sono dette tavole di verit` . a La tavola di verit` della negazione `: a e A A 0 1 1 0 la tavola di verit` della congiunzione: a23

Per chi non sa cosa signica, sar` spiegato in seguito. a

23

A 0 0 1 1

B 0 1 0 1

AB 0 0 0 1

la tavola di verit` della disgiunzione: a A 0 0 1 1 B 0 1 0 1 AB 0 1 1 1

la tavola di verit` della disgiunzione esclusiva: a A 0 0 1 1 B 0 1 0 1 AB 0 1 1 0

la tavola di verit` del condizionale: a A 0 0 1 1 B 0 1 0 1 AB 1 1 0 1

e la tavola di verit` del bicondizionale: a A 0 0 1 1 B 0 1 0 1 AB 1 0 0 1 24

Quando si deve trovare il valore di verit` di una proposizione, o di un nua mero nito di esse, sotto uninterpretazione, ` suciente considerare i valori e assunti dalle lettere che vi compaiono, quindi le interpretazioni diventano assegnazioni di valori 0 o 1 ad un numero nito di lettere, e per ogni proposizione ce ne ` un numero nito. Data una proposizione, il calcolo dei suoi e valori di verit` per ogni possibile interpretazione si pu` organizzare in una a o tabella con i valori progressivi attribuiti alle sottoproposizioni (individuate dallanalisi sintattica), come nei seguenti esempi: Se A ` p p q: e p 0 0 1 1 q p p p 0 1 0 1 1 0 0 0 0 1 0 0 p p q 1 1 1 1

Se A ` p r p (q r): e p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r p q r p (q r) p r 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 A 1 1 1 1 0 0 0 0

Tali tabelle si chiamano tavole di verit` delle proposizioni. a Come si vede dagli esempi, ci sono proposizioni che per ogni interpretazione hanno il valore 1, altre che per alcune interpretazioni hanno il valore 0 e per altre interpretazioni il valore 1. Si possono dare esempi di proposizioni che per ogni interpretazione assumono il valore 0 (esercizio). Si ricordi che una proposizione, in quanto schema, non ` n vera n falsa; !!! e e e solo la sua tavola di verit` completa spiega tutti i possibili modi in cui lo a schema pu` realizzarsi nelle diverse interpretazioni. o 25

3.3.2

Esercizi (p p) p p (p p) pq pq p (q r) (p r) s p (q p).

1. Costruire la tavola di verit` delle proposizioni: a

2. Dire quale ` la disgiunzione usata nella programmazione, considerando e che ivi si adotta la valutazione pigra: quando viene valutata una disgiunzione, e la prima condizione ` vera, la seconda condizione non viene e esaminata24 . 3. Trovare le tavole di verit` corrispondenti a a meno che, anche se. a 4. Scrivere la tavola di verit` per le particelle logiche n . . . n e non a e e (` vero che) sia . . . sia . . . . e 5. Costruire la tavola di verit` per if . . . then . . . else. a Suggerimento. Si faccia attenzione che il costrutto if . . . then nei linguaggi di programmazione ` usato piuttosto come ; se lo statement e ` falso listruzione non viene eseguita: ad esempio se si esegue25 e if importo saldo then saldo = saldo - importo, lenunciato dellassegnazione verr` eseguito sole se limporto da prela evare ` minore o uguale al saldo. e Nellesercizio, si consideri invece se . . . allora . . . , altrimenti . . . . 3.3.3 Validit` e conseguenza a

Se i (A) = 1, si dice che A ` vera nellinterpretazione i, o che i soddisfa A, e o che i ` un modello di A, e si scrive anche e !!! i |= A.24 25

Horstmann, p. 212. Horstmann, p. 186.

26

Se esiste almeno una i tale che i |= A, si dice che A ` soddisfacibile, o e (semanticamente) consistente. Se non esiste alcun modello di A, si dice che A ` insoddisfacibile, o (semanticamente) inconsistente, o contraddittoria, o e una contraddizione. Se per ogni i si ha i |= A, si dice che A ` logicamente e valida, o logicamente vera, o una tautologia, e si scrive |= A. Si dice che B ` conseguenza logica di A, o che A implica B, e si scrive e A |= B se per ogni i, se i |= A allora i |= B. Si noti che, grazie alla tavola di verit` a del condizionale, Osservazione 3.3.1 Per ogni A e B, A |= B se e solo se |= A B. Se A ` A1 . . . An , A1 . . . An |= B si scrive A1 , . . . , An |= B. Se e T = {A1 , . . . , An }, allora si dice che i soddisfa T se e solo se i |= A1 . . .An . Se A |= B e B |= A, si dice che A e B sono logicamente equivalenti , o anche solo equivalenti, e si scrive A B. Per ogni A e B, A B se e solo se |= A B. Si noti che |= e sono segni metalinguistici. Le tautologie, in particolare quelle che sono nella forma di equivalenze, sono dette anche leggi logiche. Un elenco di leggi logiche notevoli ` presentato nella pagina successiva. e

27

Leggi logiche notevoli 1 AA legge dell identit` a A A legge della doppia negazione AB BA commutativit` di a (A B) C A (B C) associativit` di a AB BA commutativit` di a (A B) C A (B C) associativit` di a AAA idempotenza di AAA idempotenza di AB A eliminazione di AAB introduzione di A (B C) (A B) (A C) distributivit` a A (B C) (A B) (A C) distributivit` a A (A B) A legge di assorbimento A (A B) A legge di assorbimento (A B) (A B) legge di De M organ (A B) (A B) legge di De M organ A A legge del terzo escluso (A A) legge di non contraddizione A B B A legge di contrapposizione A A B Lewis, o ex falso quodlibet A (B A) af ermazione del conseguente f A (A B) negazione dell antecedente (A B B) A legge di riduzione all assurdo (A A) A riduzione all assurdo debole (A A) A consequentia mirabilis ((A B) A) A legge di P eirce (A B) (B A) legge di Dummett A ((A B) B) modus ponens A (B C) B (A C) scambio antecedenti (A C) (B C) A B C distinzione di casi (A B) (A B) B distinzione di casi (A (B C)) ((A B) (A C)) distributivit` di a (A B) (B C) (A C) transitivit` di a A (B C) (A B) C importazione/esportazione delle premesse

28

Per vericare queste leggi, dove A, B, . . . sono qualunque, si devono prima vericare le stesse nel caso particolare che A, B, . . . siano atomiche (ad esempio p p per la legge dellidentit`), e poi sfruttare il fatto che se A[p] ` a e una tautologia e B ` qualunque, allora anche il risultato della sostituzione di e B a p in A ` una tautologia (vedi esercizi). e Per le leggi che sono scritte come condizionali e non bicondizionali, si vedr` in seguito che limplicazione inversa in generale non sussiste (salvo a alcuni casi, ad esempio per linverso della riduzione allassurdo debole A (A A), che rientra nellaermazione del conseguente). Lassociativit` della congiunzione giustica che si possa scrivere senza a ambiguit`, indipendentemente dalle convenzioni sulle parentesi, A B C a per (indierentemente) A (B C) o (A B) C, o in generale A1 . . . An (e lo stesso per la disgiunzione). A (B C) e (A B) C sono diverse (si disegni il loro albero sintattico) ma si dice che sono uguali a meno di equivalenza logica. Anche le seguenti sono leggi logiche: A B A B (A B) (A B) (B A) A B (A B) (B A) A B (A B) (A B). Si noti che le due leggi per forniscono un esempio di come una particella logica possa essere espressa con diversi giri di frase equivalenti; queste equivalenze in genere mostrano cosa signica che frasi diverse vogliono dire la stessa cosa. Per mezzo di esse, dalle leggi elencate sopra se ne derivano altre; ad esempio dal modus ponens e dallesportazione, con la prima, si ricava A (A B) B sillogismo disgiuntivo.

Ma queste leggi soprattutto permettono di vedere che i connettivi , , sono denibili in termini di , e . Alcune leggi sono spesso presentate in forma di regole di inferenza; ad esempio il modus ponens da

29

A, A B , B il sillogismo disgiuntivo da

A, A B B o da

A, A B , B leliminazione della congiunzione da

AB AB e A B e lintroduzione della disgiunzione da

A B e . AB AB Le leggi corrispondenti permettono di asserire che se sono vere le proposizioni sopra la riga, o premesse della regola, allora ` vera anche la propoe sizione sotto la riga, o conclusione. Regole dinferenza di questo genere si dicono corrette se le premesse implicano logicamente la conclusione - quindi le regole sopra elencate sono corrette. Per mezzo delle regole di inferenza si deduce una proposizione da unaltra, o da altre date, che si chiamano assunzioni; si dice che una proposizione B si deduce da unaltra A se A |= B e se questo fatto ` riconosciuto e certicato da una spiegazione. Un modo e per riconoscere la sussistenza di A |= B ` quello di inserire tra A e B altre e proposizioni legate tra loro dalla relazione di premesse-conclusione di regole corrette. Ad esempio per stabilire 30

(r p q) r p |= q si pu` eseguire la seguente deduzione: o (r p q) r p r pq r p pq q usando leliminazione della congiunzione, il modus ponens e il sillogismo disgiuntivo. La relazione di conseguenza logica ` evidentemente transitiva: se A |= C e e C |= B allora A |= B (esercizio). 3.3.4 Esercizi

1. Vericare con le tavole di verit` le precedenti leggi logiche. a 2. Spiegare perch e Se |= A allora B |= A per ogni B. Se |= A allora |= A B per ogni B. Se |= A e |= A B allora |= B. 3. Spiegare perch se A[p] ` una tautologia, anche la proposizione che si e e ottiene sostituendo p con una B qualunque ` una tautologia. e 4. Vericare la seguente generalizzazione delle leggi di assorbimento, che A A C se C |= A, e che A A C se A |= C. !!! 5. Vericare che A T A se T ` una tautologia e che A F A se F e ` una contraddizione, e dedurlo dal risultato del precedente esercizio. e 6. Vericare che A B (A B) (sia con le tavole, sia in base alla denizione di interpretazione). 7. Vericare che A B ` equivalente a (A B), in base alla denizione e di interpretazione. 31

8. Vericare che |= A B A B ma non viceversa. 9. Spiegare perch A A B non ` logicamente vera. e e 10. Vericare che p q ` equivalente a p (q p) ed a p (q p). e 11. Notare (A B) A B e A A A A (provare a trovare frasi in italiano che si possono dire bene in entrambi i modi). 12. Vericare che la regola del sillogismo disgiuntivo ` corretta anche con e al posto di . 13. Vericare se A (B C) (A B) C. 14. In base al precedente esercizio, discutere quando A1 . . . An ` vera. e 15. Vericare che A A e che A A. Generalizzare. 16. Si consideri il problema del merging di due liste List1 e List2 in una terza lista List3 (ad esempio nomi, in ordine alfabetico). Una prima formulazione dellalgoritmo ` la seguente: nello scorrere le e due liste, se List1 non ` esaurita e List2 ` esaurita oppure lelemento e e in considerazione di List1 precede il primo non ancora inserito di List2, allora lelemento di List1 ` inserito in List3. e Unaltra formulazione potrebbe essere la seguente: il prossimo elemento in List3 ` preso da List1 quando List1 non ` esaurita e List2 s` oppure e e , quando List1 non ` esaurita e lelemento in considerazione di List1 e precede il primo non ancora inserito di List2. Usando lettere p, q, r per rappresentare rispettivamente List1 non ` e esaurita, List2 ` esaurita e lelemento di List1 precede quello di e List2, scrivere le proposizioni corrispondenti alle due versioni delle condizioni (che portano entrambe a mettere in List3 lelemento in esame di List1), e discutere se siano o no equivalenti, in base a quali leggi. 17. Si distribuiscono carte da gioco, e si sa che un giocatore ha in mano un Asso o un Re. Si considerino le seguenti due proposizioni: A: se c` in mano un Asso, c` un 2 e e B: se c` in mano un Re, c` un 2. e e

32

Che cosa si pu` dedurre se esattamente una tra le proposizioni A e B o ` vera? e Che cosa si pu` dedurre se entrambe le proposizioni A e B sono vere? o 18. Per conquistare la principessa, Aladino deve scegliere di aprire una di due scatole A e B; sa che in una c` un anello di danzamento, nellaltra e un serpente velenoso. Sulla scatola A ` scritto: Almeno una di queste e scatole contiene un anello; sulla scatola B ` scritto: Nella scatola e A c` un serprente velenoso che uccide allistante. Ad Aladino viene e detto che o entrambe le scritte sono vere, o entrambe false. Quale scatola apre? 19. Se io ho ragione, tu hai torto; se tu hai ragione, io ho torto; quindi uno di noi ha ragione. Corretto o no? Perch? e 20. La storia insegna che non si impara niente dalla storia. Vero o falso? Perch? e Suggerimento. Riduzione allassurdo debole.

3.4

Sullimplicazione

Abbiamo distinto il condizionale, che ` un connettivo, o il nome di una propoe sizione della forma A B, dallimplicazione, che ` una relazione tra propoe sizioni, e non si scrive A B ma |= A B. A implica B signica il condizionale A B ` una tautologia. e La terminologia ` qualche volta ambigua perch per leggere ad esempio e e una regola come il sillogismo disgiuntivo si trova anche detto se A e A B allora B, in alternativa a A e A B implicano B. Se si ` in un contesto e deduttivo si capisce forse che si sta parlando dellimplicazione e non leggendo semplicemente la forma di una proposizione. Limportante ad ogni modo non ` la terminologia quanto capire la dierenza. e Il soggetto di A implica B non ` A ma A B. Qualche volta - non e qui - si trova introdotto un simbolo speciale per limplicazione (in analogia al caso dellequivalenza), ad esempio A B. Si dice ad esempio il condizionale p p q ha cinque simboli, non limplicazione p p q ha cinque simboli, perch limplicazione ` un e e fatto che sussiste o no, e un fatto non ` formato da simboli. Al massimo ` e e un predicato, sotto cui cadono alcuni condizionali, come in il condizionale 33

p p q ` unimplicazione. Oppure si pu` dire che vale limplicazione e o p p q, ma non si parler` ad esempio dellimplicazione p q r, che non a ` una tautologia. e Siccome purtroppo la terminologia non ` uniforme, e si possono trovare e usate entrambe le parole, bisogna fare attenzione al contesto.Nella tradizione logica, il condizionale era anche chiamato implicazione materiale, per distinguere la relazione di conseguenza da altre forme di implicazione, o da altri sensi del costrutto se . . . allora. In eetti, il signicato di se . . . allora ` polimorfo: e signicato logico (o inferenziale): Se tutti gli uomini sono mortali e Socrate ` un uomo, allora Socrate ` more e tale. signicato denitorio: Se ` scapolo, allora non ` sposato. e e signicato causale: Se si immerge una cartina di tornasole e diventa rossa, allora il liquido ` un e acido. signicato materiale: Se la Terra vola, allora la Terra ` piatta. e ` E dicile trovare qualcosa di positivo in comune tra queste diverse accezioni del se . . . allora. In particolare il caso che ha sollevato maggiori discussioni ` lultimo, come considerare il condizionale se antecedente e conseguente sono e entrambe false. Una cosa in comune ce lhanno, ed ` che in tutte le accezioni lunico modo e per dichiarare il condizionale falso ` quello di riscontrare antecedente vera e cone seguente falsa, anche per il signicato materiale: se la Terra ` rotonda, allora il e Sole ` freddo si considera falso. e Allora il signicato parziale comune si pu` esprimere riempiendo la tavola di o verit` con i valori che sono di fatto quelli di (A B): a !!! Un condizionale ` corretto [secondo Crisippo] se la negazione della e sua conclusione ` incompatibile con la sua premessa (Sesto Empirico, e Schizzi pirroniani, II, 110-2). Si ottiene cos` quella che gli antichi chiamavano implicazione materiale:

34

Secondo lui [Filone di Megara] ci sono tre modi in cui un condizionale pu` essere vero, e uno in cui pu` essere falso. Perch un condizionale o o e ` vero quando inizia con una verit` e termina con una verit`, come e a a se ` giorno, ` chiaro. Ed ` vero anche quando inizia con una fale e e sit` e termina con una falsit`, come se la terra vola, la terra ha a a ali. Analogamente, ` vero un condizionale che inizia con una falsit` e a e termina con una verit`, come se la terra vola, la terra esiste. Un a condizionale ` falso soltanto quando inizia con una verit` e termina e a con una falsit`, come se ` giorno, ` notte (Sesto Empirico, Contro i a e e matematici , VIII, 113). Con questa scelta per la tavola di si giustica la regola del modus ponens, che ` quello che interessa, per luso che se ne fa nei discorsi con se . . . allora. e

Il motivo per cui il condizionale ` dicile e controverso ` che non gli si e e pu` associare una rappresentazione mentale immediata di quello che descrive. o Quando si ascolta A B, le rappresentazioni nella mente del fatto descritto da A e di quello descritto da B vengono fuse in ununica rappresentazione, del fatto descritto da A B, aancandole o integrandole; anche con A B le due rappresentazioni possono essere compresenti, con lattenzione che si sposta dalluna allaltra e viceversa, come se si guardassero alternativamente due quadri vicini. Con il condizionale non ` possibile avere una rappresentazione e del fatto descritto da A B, combinando quelle relative ad A e B. Non esiste una rappresentazione unica della falsit` di A. Vengono meno perci` a o gli ausili dellimmaginazione e della sensibilit`; lunico modo per dominare il a condizionale ` quello di imparare bene no a interiorizzarle le sue condizioni e duso, sia il calcolo dei valori di verit` sia le leggi e le regole che lo concernono. a La denizione del condizionale tuttavia non ` solo adeguata per svolgere e le dimostrazioni, grazie alla giusticazione del modus ponens, ma ` anche e comoda (nella scelta di dare il valore vero quando lantecedente ` falsa) per e la costruzione generale dei linguaggi formali, e la trattazione delle variabili, come vedremo oltre.

35

44.1

Insiemi e algebre di BooleVariabili

Esempi di proposizioni a cui si applicano utilmente le nozioni e le tecniche logiche sono le formule matematiche; in esse tuttavia compaiono le variabili x, y, . . . 1 Le variabili che occorrono in una formula, ad esempio 1 < x < 3, si chiamano anche variabili individuali, perch` prendono come valori gli elementi e delluniverso del discorso. In generale, unasserzione in cui compare la variabile x sar` indicata con p(x). Possiamo considerare una formula del genere a come una proposizione, che aerma qualcosa a proposito di x; x denota un elemento non precisato delluniverso. Quanto visto nora sulla logica proposizionale ` gi` utile per alcune analisi e a logiche anche delle formule con variabili. Consideriamo di nuovo la formula aritmetica 1 < x < 3; immaginiamo che si stia parlando di numeri naturali (che cio` il dominio o universo di discorso sia costituito dai numeri naturali, e e < rappresenti la relazione dordine). Di una tale formula non si pu` dire se o ` vera o falsa, dipende. Si pu` dire che ` soddisfatta da certi (valori di) x; ` e o e e come se fosse presente un numero incappucciato, che dice io sono compreso tra 1 e 3. Se si toglie il cappuccio ed appare 2 ha detto il vero, se appare 0, o 3 o 5 o qualsiasi altro numero, ha detto il falso. Se il numero incappucciato continua dicendo quindi io sono il numero 2, bisogna ammettere che la deduzione ` corretta, anche senza sapere chi ` il e e numero incappucciato. La formula 1 < x < 3 ` soddisfatta dal solo elemento e 2, e possiamo aermare 1 < x < 3 x = 2. Se invece luniverso di discorso, che dalla formula in s non si evince, ` !!! e e quello dei numeri reali, la formula ` soddisfatta anche da 1,1, da 1,9, da 2,5 e e da tutti gli inniti elementi dellintervallo (1, 3). La formula 1 < x < 3 daltra parte ` unabbreviazione per 1 < x x < 3; e perch un valore di x la soddis, questo valore deve soddisfare sia 1 < x sia e x < 3. Abbiamo dunque formule che assomigliano a quelle le linguaggio proposizionale, in quanto sono composizione mediante connettivi di formule atomAllargomento delle variabili sar` dedicato ampio spazio in seguito, per la loro impora tanza, non solo matematica ma logica in generale; esse permettono di completare lanalisi linguistica in modo molto pi` approfondito di quello che si realizza limitandosi a considu erare i connettivi.1

36

iche, solo che queste ultime invece di lettere sono espresisoni che contengono anche x. Si potrebbe dire che si tratta di un linguaggio proposizionale applicato. Ogni volta che si d` a x un valore, nelluniverso ssato, ` come a e assegnare il valore vero o falso alle componenti atomiche. Parleremo per semplicit` anche in questo caso per ora di proposizioni, per non complicare a la terminologia, quando applicheremo risultati della logica proposizionale, oppure le chiameremo formule, in analogia alle formule matematiche.

4.2

Algebra degli insiemi

Se le proposizioni si riferiscono a un dominio di discorso costituito da un insieme U , U per universo, ad ognuna di queste proposizioni p(x) ` e associato un insieme, che si pu` chiamare insieme di verit` di p(x): o a Vp(x) = {x U | p(x) ` vero in U }. e Nel linguaggio insiemistico, x X signica che x ` un elemento di X, o e che x appartiene a X; x X signica che x non appartiene a X. Con la notazione {x U | p(x) ` vero in U }, si indica linsieme degli e elementi di U che soddisfano la condizione p(x) in U . Talvolta si scrive anche {x U | p(x)} o addirittura {x | p(x)} se ` chiaro linsieme ambiente e U. Con la notazione {x1 , . . . , xn } si indica linsieme i cui elementi sono x1 , . . . , xn . Linsieme {x, y} si chiama coppia (non ordinata) di x e y, che sono gli unici elementi di {x, y}: x {x, y} e y {x, y}2 , e inoltre z {x, y} z = x z = y. La coppia {x, y} ha due elementi se x = y; altrimenti se x = y ne ha uno solo, si indica {x} e si chiama anche insieme unitario, o singoletto di x. Linsieme di verit` di p(x) ` anche linsieme denito da p(x) in U . Ad a e esempio, se U = {a, b, c, d} e p(x) x = a x = b, linsieme denito da p(x) in U ` {a, b}. e Se U ` linsieme dei numeri naturali e p(x) ` la condizione x ` divisibile e e e per 2, linsieme di verit` di p(x) ` linsieme dei numeri pari, e tale insieme a e ` denito dalla condizione x ` divisibile per 2. e e2

Talvolta si scrive x, y X per x X e y X.

37

Un insieme di verit` ` un sottoinsieme di U ; si dice che X ` un sottoinae e 3 sieme di Y , o che ` contenuto in Y , in simboli X Y , se ogni elemento di e X ` anche elemento di Y : per ogni x, se x X allora x Y . e Qualche volta, raramente, si scrive Y X per X Y . Si dice che X ` un sottoinsieme proprio di Y , e si scrive X Y , se X Y e ma X = Y . Se X Y e Y X allora X e Y hanno gli stessi elementi; questo per denizione signica che X = Y . Quello che caratterizza gli insiemi non sono le loro eventuali denizioni ma i loro elementi; ad esempio linsieme dei triangoli con due lati uguali e linsieme dei triangoli con due angoli uguali sono lo stesso insieme. Cos` {x, y} = {y, x}, da cui la dizione non ordinata. Le operazioni insiemistiche principali, sui sottoinsiemi di un insieme U , sono le seguenti: Complemento. Il complemento di X (rispetto a U ) ` linsieme degli elementi e di U che non appartengono a X: X = {x U | x X}. Dierenza. La dierenza di X meno Y ` linsieme degli elementi di U che e appartengono a X e non a Y : X \ Y = {x U | x X x Y }. Dierenza simmetrica. La dierenza simmetrica di X e Y ` linsieme degli e elementi di U che appartengono a X e non a Y o a Y e non a X: X Y = {x U | x X x Y }. Intersezione. Lintersezione di X e Y ` linsieme degli elementi di U che e appartengono sia a X sia a Y : X Y = {x U | x X x Y }.Si distingue tra essere contenuto, che si riferisce a sottoinsiemi, ed appartenere, che si riferisce ad elementi.3

38

X Y si legge: X intersezione Y o X intersecato con Y o lintersezione di X e Y . Unione. Lunione di X e Y ` linsieme degli elementi di U che appartengono e ad almeno uno dei due insiemi X e Y : X Y = {x U | x X x Y } X Y si legge: X unione Y o X unito a Y o lunione di X e Y . Lintersezione di X e Y ` il pi` grande insieme che ` contenuto sia in X e u e sia in Y , nel senso che X Y X4 X Y Y e se Z X e Z Y allora Z X Y mentre lunione di X e Y ` il pi` piccolo insieme che contiene sia X sia Y , e u nel senso che X X Y Y X Y e se Y X e Z X allora Y Z X. Per dimostrare X Y X ad esempio, si osservi che se x X Y allora x X x Y , ma x X x Y x X, quindi x X. Inoltre x X x Y x Y , quindi X Y Y . In modo analogo per le altre. Nella propriet` di minimalit` dellunione troviamo la spiegazione dello a a scambio di e ed o osservato in precedenza in certe frasi. Se si indica con Y linsieme delle mele, con Z linsieme delle pere, e con X linsieme dei frutti, allora la frase mele e pere sono frutti, intesa come le mele sonoSi noti che non occorrono parentesi perch non ` possibile interpretare questa formula e e come X (Y X) in quanto si avrebbe unoperazione tra un insieme e una proposizione - un errore di tipo, si dice in logica. Qualche volta le parentesi di mettono per agevolare la lettura.4

39

frutti e le pere sono frutti signica che Y X Z X, ma questa implica Y Z X, cio` che mele o pere sono frutti. e Viceversa, se Y Z X, allora siccome Y Y Z si ha, per la transitivit` a di - vedi oltre - che Y X e analogamente Z X, cio` mele o pere sono e frutti implica a sua volta le mele sono frutti e le pere sono frutti. Le operazioni insiemistiche corrispondono ai connettivi: lappartenenza al complemento ` denita mediante la negazione, lappartenenza allintersezione e mediante la congiunzione, e cos` via. In analogia, si possono usare le stesse convenzioni sullordine di priorit` dei simboli di operazione (, , ) per !!! a ridurre il numero di parentesi. Viceversa, ai connettivi proposizionali corrispondono le operazioni insiemistiche sugli insiemi di verit` delle proposizioni componenti. a Vp(x) = Vp(x)q(x) = Vp(x)q(x) = Vp(x) Vp(x) Vq(x) Vp(x) Vq(x) .

In particolare si ha VxX = X. Si pu` osservare allora che le operazioni non sono tutte indipendenti, ad o esempio: X \ Y = X ( Y ). Infatti X \Y = {x | x X x Y } = {x | x X x Y } = {x | x X ( Y )} = X ( Y ).

Ma le mutue relazioni delle operazioni le vedremo meglio pi` avanti. u Linsieme vuoto ` linsieme che non ha alcun elemento, ed ` un sottoine e sieme di qualsiasi U , denito da una condizione contraddittoria qualunque: = {x U |p(x) p(x)}, o 40

= {x U |x = x}. Se si denotasse questo insieme U e si denisse V = {x V | x = x} si avrebbe U = V perch i due insiemi hanno gli stessi elementi, nessuno per e entrambi. Caratteristica dellinsieme vuoto ` che per ogni x, in qualunque U , x . e Due insiemi X e Y la cui intersezione sia vuota, X Y = , cio` non e abbiano alcun elemento in comune, si dicono disgiunti . Le relazioni tra le operazioni insiemistiche sono espresse da un gruppo di leggi.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

X X =X idempotenza dell intersezione X X =X idempotenza dell unione X Y =Y X commutativit` dell intersezione a X Y =Y X commutativit` dell unione a X (Y Z) = (X Y ) Z associativit` dell intersezione a X (Y Z) = (X Y ) Z associativit` dell unione a X (Y Z) = (X Y ) (X Z) distributivit` di rispetto a a X (Y Z) = (X Y ) (X Z) distributivit` di rispetto a a X (X Y ) = X assorbimento X (X Y ) = X assorbimento ( X) = X doppio complemento (X Y ) = ( X) ( Y ) legge di De M organ (X Y ) = ( X) ( Y ) legge di De M organ =U U = X ( X) = legge dell inverso per X ( X) = U legge dell inverso per X U =X legge dell elemento neutro per X U =U X = X =X legge dell elemento neutro per .

Esistono altre leggi che riguardano la relazione (alcune gi` menzionate), a come 41

22 23 24 25 26 e propriet` come a

XX X XU X X Y X Y X

27 28 29 30 31 32 33

se X Y e Y Z allora X Z X Y se e solo se X Y = X X Y se e solo se X Y = Y X Y se e solo se X ( Y ) = X Y se e solo se X Y = U se X Y e X Z allora X (Y Z) se Y X e Z X allora (Y Z) X.

Ma non tutte sono indipendenti. La loro dimostrazione pu` consistere nel o mostrare direttamente che i due insiemi implicati hanno gli stessi elementi. Esempi 3 X Y = Y X. Dimostrazione Se x X Y , allora x X x Y ; ma per la commutativit` della congiunzione si ha allora x Y x X, quindi a x Y X. Il viceversa, partendo da x Y X, ` analogo. e 4 X Y = Y X. Dimostrazione Se x X Y allora x X x Y . La conclusione segue come sopra per la commutativit` della disgiunzione. Oppure a usiamo la distinzione di casi: se x X, allora x Y x X per la tautologia A B A. Se x Y allora per la tautologia A A B si ha x Y x X. Quindi x X x Y x Y x X e X Y Y X. Il viceversa ` analogo. e 42

5

X (Y Z) = (X Y ) (X Z). Dimostrazione Mostriamo prima che X (Y Z) (X Y ) (X Z). Se x X (Y Z) allora x X e x Y Z. Ci sono due casi: o x Y o x Z. Nel primo caso, x X e x Y , quindi x X Y , e quindi x (X Y ) (X Z) per la 25, che supponiamo dimostrata5 . Nel secondo caso, x X e x Z, quindi x X Z e quindi x appartiene a (X Y ) (X Z), per la 25 e la 4. Si mostri ora nello stesso modo (esercizio) che (X Y ) (X Z) X (Y Z), e luguaglianza ` provata. e

21

X = X. Dimostrazione Se x X , allora x X x , ma x quindi per il sillogismo disgiuntivo x X. Il viceversa segue dalla 25.

24

X U. Dimostrazione x U (x X x U ) - quale legge logica interviene?

23

X. Dimostrazione Per ogni x, x x X ` vera, qualunque sia X, e perch lantecedente ` falso. e e

17

X ( X) = U . Dimostrazione Per ogni x, x X (x X) ` vera per la legge del e terzo escluso. Cos` si dimostra , il viceversa ` 24. e

30

X Y se e solo se X ( Y ) = . Dimostrazione Se x X allora x Y ; se ora esistesse un x X ( Y ) si avrebbe una contraddizione x Y e x Y .

Come si vede dagli esempi, alcune propriet` delle operazioni sono dia retta conseguenza delle omonime propriet` dei connettivi corrispondenti; dal a terzo esempio relativo alla 5 si vede anche che in dimostrazioni di questo tipo fa comodo, per saltare qualche passaggio, fare appello ad altre delle leggi elencate - pi` semplici, o intuitive o gi` dimostrate. Pi` in generale, u a u5

La dimostrazione ` implicita nella precedente dimostrazione di 4. e

43

una volta dimostrate alcune delle suddette leggi in modo diretto, ` possibile e derivare le altre in stile algebrico, usando quelle gi` dimostrate e le leggi a delluguaglianza. Con leggi delluguaglianza si intendono le propriet` riessiva, simmetrica a e transitiva di =, rappresentate dalle formule x=x x=yy=x x = y y = z x = z, e le propriet` di sostituzione, che sono di due tipi: a t = s f (t) = f (s), dove t ed s sono termini del linguaggio in uso, e f (x) un altro termine contenente la x, e t = s (p(t) p(s)), dove p(x) sta per una proposizione qualunque contenente x. Queste leggi sono tacitamente usate nei passaggi di trasformazione di formule algebriche, o di proposizioni di qualunque linguaggio che contenga luguaglianza. I passaggi da unuguaglianza ad unaltra presuppongono il modus ponens: da t = s a f (t) = f (s) grazie a t = s f (t) = f (s). Nel caso delle leggi insiemistiche in esame le variabili sono X, Y, . . . invece che x, y . . . , perch non si riferiscono agli elementi ma ai sottoinsiemi. e Esempi 1. La 15 segue dalla 14 e dalla 11 con i passaggi =U ( ) = U = U U = . 2. La 17 segue dalla 16 e dalle 12, 14, 11, 4, nellordine, con i seguenti passaggi

44

X ( X) = (X ( X)) = ( X) ( ( X)) = U ( X) X = U X ( X) = U . 3. La 18 segue da 17, 7, 1, 16 e 21 con i seguenti passaggi X ( X) = U U = X ( X) X U = X (X ( X)) X U = (X X) (X ( X)) X U =X X U = X. 4. La 31: X Y se e solo se X Y = U , segue dalla 30 e da De Morgan con 11 e 14. Grazie alla validit` delle leggi associative per unione e intersezione, queste a operazioni possono essere generalizzate a pi` di due insiemi. u Se A1 , . . . , An sono n sottoinsiemi di U , la loro unione ` linsieme i cui e elementi sono gli elementi di U che appartengono a qualche Ai , in simboli:

n

Ai = {x U | per qualche i, 1 i n, x Ai }i=1

o anchen i=1

Ai , o semplicemente

Ai .

Lintersezione generalizzata degli n insiemi ` linsieme degli elementi che e appartengono a tutti gli Ai , in simboli:

45

n

Ai = {x U | per ogni i, 1 i n, x Ai }i=1

o anchen i=1

Ai , o semplicemente

Ai .

Per queste operazioni generalizzate valgono molte delle leggi dellunione e intersezione, opportunamente riformulate, ad esempio le propriet` commua tativa, associativa e di assorbimento; valgono le leggi di De Morgan: ( e (n i=1 n i=1

Ai ) = Ai ) =

n i=1 (

Ai ) Ai ).

n i=1 (

Valgono le leggi distributive di una operazione generalizzata rispetto a una normale (non con entrambe generalizzate):n n

(i=1

Ai ) B =

(Ai B)i=1

en n

(i=1

Ai ) B =

(Ai B).i=1

Pi` in generale ancora, si denisce lunione uiI

Ai o

{Ai | i I}

per una famiglia di insiemi indiciata6 da I ponendo che xiI

Ai se e solo se esiste un i I per cui x Ai ,

e analogamente per lintersezione. La denizione come si vede ` la stessa, e con i I al posto di 1 i n.Si chiama cos` e si indica anche con {Ai }iI un insieme i cui elementi corrispondono ciascuno a un elemento di un insieme I. Si veda alla ne del paragrafo 5.6

46

4.3

Algebre di Boole

Indagando la reciproca derivabilit` delle varie leggi, ci si accorge che tutte a (sia quelle elencate che altre, quelle che sono valide per ogni famiglia di sottoinsiemi di un insieme) sono derivabili dalle seguenti:

3 4 5 6 7 8 9 10 16 17 18 21

X Y =Y X X Y =Y X X (Y Z) = (X X (Y Z) = (X X (Y Z) = (X X (Y Z) = (X X (X Y ) = X X (X Y ) = X X X = X X = U X U =X X =X

Y)Z Y)Z Y ) (X Y ) (X

commutativit` dell intersezione a commutativit` dell unione a associativit` dell intersezione a associativit` dell unione a Z) distributivit` di rispetto a a Z) distributivit` di rispetto a a assorbimento assorbimento legge dell inverso per legge dell inverso per legge dell elemento neutro per legge dell elemento neutro per .

Queste leggi si chiamano assiomi delle algebre di Boole. La scelta degli assiomi non ` arbitraria (ci sono ragioni di analogia con altri sistemi di ase siomi per altre strutture) ma non ` univoca. Abbiamo visto ad esempio che e se ci fosse la 1, la 18 sarebbe superua. Limportante ` la mutua e varia ine terderivabilit` delle leggi tra loro, e che tutte le leggi valide per i sottoinsiemi a di un insieme non vuoto U siano derivabili da quelle scelte come assiomi. La raccolta di queste negli assiomi ` solo, inizialmente, una comodit` mnemone a ica. Linsieme dei sottoinsiemi di un insieme non vuoto U , con le operazioni , , e gli elementi speciali e U ` una particolare algebra di Boole, che e si chiama algebra di insiemi . Vediamo come si derivano dagli assiomi alcune delle altre leggi prima elencate. 1 X =X X

47

X X X X X 2 20 X =X X X =

=X U = X (X X) = (X X) (X X) = (X X) =X X (esercizio)

per la 18 per la 17 per la 7 per la 16 per la 21

X = (X ) X = ( X) X = 19 X U =U (esercizio).

per la 21 per la 3 e la 4 per la 9

Prima di considerare altre leggi, occorre dimostrare lunicit` degli elea menti neutri e del complemento. Per quello dellintersezione, questo signica: 34 Se X Y = Y per ogni Y , allora X = U . Dimostrazione Sostituendo U a Y si ha X U = U ma X U = X per la 18, quindi X = U . Per lelemento neutro dellunione, lunicit` signica: a 35 Se X Y = Y per ogni Y , allora X = (esercizio). Lunicit` del complemento, o dellinverso, ` la propriet` che: a e a 36 Se X Y = e X Y = U allora X = Y . Dimostrazione X =X U = X (Y Y ) = (X Y ) (X Y ) = (X Y ) = (Y Y ) (X Y ) = (Y X) Y = U Y = Y per la 18 per la 17 per la 7 per l ipotesi per la 16 per la 7 per l ipotesi per la 18.

48

11

X = X Dimostrazione Siccome X X = e X X = U , per la 36 ora vista con X al posto di Y si ha X = X.

13

(X Y ) = X Y Dimostrazione Per applicare la 36, facciamo vedere che ( X Y ) (X Y ) = U e ( X Y ) (X Y ) = . La prima segue da questi passaggi (abbreviati, esplicitarli tutti per esercizio, serve anche la 19 di sopra): ( X Y ) (X Y ) = ( X X Y ) ( Y X Y ) =U U =U e la seconda (utilizzando 20) da: ( X Y ) (X Y ) = ( X Y X) ( X Y Y ) = = .

4.3.1

Esercizi A (B (C \ A)) = A B A B (A B) = A B A (C (A B)) = A (C B) (A \ B) (B A) = A (A (B C)) ( B A) = (A B) (A C).

1. Dimostrare

49

2. Dimostrare le propriet` 22 - 33 della relazione , a partire dagli assiomi, a usando 28 come denizione di 7 . 3. Lo stesso, usando una volta 29, una volta 30 e una volta 31 come denizione di 4. Dimostrare, a partire dagli assiomi delle algebre di Boole, tutte le altre leggi sopra elencate per le operazioni di unalgebra di insiemi.

4.4

Algebra delle proposizioni

Due altre notevoli algebre di Boole sono importanti, lalgebra 2 e lalgebra delle proposizioni. Quando si dice che gli assiomi sopra elencati sono gli assiomi delle algebre di Boole, non si intende che i simboli di operazioni usati nella formulazione degli assiomi denotino le operazioni insiemistiche di unione, intersezione e complemento; altrimenti le uniche algebre di Boole sarebbero le algebre di insiemi. Sintende solo che siano operazioni rispettivamente binarie (le prime due) e unaria (la terza), e che soddisno le propriet` espresse dagli assiomi. a Pu` essere utile addirittura riscrivere gli assiomi con altri simboli8 : o

x y =yx commutativit` a x+y =y+x commutativit` a x (y z) = (x y) z associativit` a x + (y + z) = (x + y) + z associativit` a x (y + z) = (x y) + (x z) distributivit` a x + (y z) = (x + y) (x + z) distributivit` a x (x + y) = x assorbimento x + (x y) = x assorbimento x (x) = 0 inverso x + (x) = 1 inverso x 1=x elemento neutro x+0=x elemento neutroLa 22 e la 27, insieme a X = Y se e solo se X Y e Y X stabiliscono che ` e una relazione di ordine parziale, secondo la denizione che sar` data nel paragrafo 5. a 8 Con lordine di priorit` , , +. a7

50

e indicare la relazione denita da x y = x con . Si ha 0 x 1 per ogni x (esercizio). La relazione ` un ordine parziale e per lesercizio 1 di 4.3.1. Lalgebra 2 ` lalgebra il cui universo ` {0, 1} con 0 < 1, rappresentata e e dal diagramma 1 0 dove ` < e x + y = max{x, y} e x y = min{x, y}. e Lalgebra 2 ` lalgebra dei valori di verit`. Le sue tre operazioni sono e a quelle che intervengono nel calcolo dei valori di verit` di negazioni, disgiuna zioni e congiunzioni. Esistono altre algebre di Boole nite, come ad esempio lalgebra 4 1 a 0 dove a e b sono inconfrontabili rispetto a ; ` proprio parziale. e Esercizio: denire le operazioni in modo che questa struttura diventi unalgebra di Boole. Esercizio. Dimostrare che ` lalgebra dei sottoinsiemi di un universo con e due elementi. Lalgebra delle proposizioni si ottiene nel seguente modo; gi` si sono dia mostrate (considerando anche gli esercizi) quasi tutte le leggi logiche che hanno lo stesso nome degli assiomi delle algebre di Boole: b

AB BA commutativit` a AB BA commutativit` a A (B C) (A B) C associativit` a A (B C) (A B) C associativit` a A (B C) (A B) (A C) distributivit` a A (B C) (A B) (A C) distributivit` a A (A B) A assorbimento A (A B) A assorbimento. 51

Le equivalenze non sono uguaglianze ma si possono trasformare in vere uguaglianze tra (nuovi) oggetti con la seguente costruzione. La relazione ` una relazione di equivalenza, vale a dire soddisfa le e propriet`: a AA se A B allora B A se A B e B C allora A C rif lessiva simmetrica transitiva.

Si denisce allora per ogni A la classe di equivalenza di A come [A] = {B | A B} e si ha che [A] = [B] se e solo se A B (esercizio). Date due proposizioni A e B, esse o sono logicamente equivalenti o no. Nel primo caso, [A] = [B]. Nel secondo caso le due classi [A] e [B] sono disgiunte: se infatti ci fosse un elemento C in comune, vorrebbe dire che A C e che B C, ma allora per la transitivit` si avrebbe A B e a [A] = [B]. A si dice un rappresentante della classe [A]; ogni classe ha pi` rappresenu tanti, anzi inniti. Se B [A] allora B A quindi [A] = [B] e B ` un altro e rappresentante di [A]. In particolare ad esempio [A] = [AA] = [AAA] . . . Si possono denire tra queste classi le seguenti operazioni: [A] = [A] [A] [B] = [A B] [A] + [B] = [A B]. Le denizioni sono ben poste, in questo senso. Si tratta di operazioni sulle classi, ma la loro denizione fa riferimento ad un particolare rappresentante delle classi. Ad esempio [A] ` denita con A e non ad esempio con A. e Se si cambia il rappresentante di una classe, si vuole che il risultato, che ` e una classe, sia lo stesso. 52

In eetti ` cos` per le operazioni sopra denite. Ad esempio se A1 A e e B1 B, siccome A1 B1 A B (esercizio - si veda anche paragrafo 6.1) si ha [A1 ] [B1 ] = [A B], cos` come [A] [B] = [A B], quindi [A1 ] [B1 ] = [A] [B]. Si giustica in questo modo la dizione a meno di equivalenza con cui una proposizione ` considerata uguale ad ogni altra ad essa logicamente equivae lente, o almeno indistinguibile da quelle, ai ni della trattazione semantica. Date queste denizioni, le precedenti equivalenze danno allora origine alle uguaglianze: [A] [B] = [B] [A] commutativit` di a [A] + [B] = [B] + [A] commutativit` di + a [A] ([B] [C]) = ([A] [B]) [C] associativit` di a [A] + ([B] + [C]) = ([A] + [B]) + [C] associativit` di + a [A] ([B] + [C]) = ([A] [B]) + ([A] [C]) distributivit` a [A] + ([B] [C]) = ([A] + [B]) ([A] + [C]) distributivit` a [A] ([A] + [B]) = [A] assorbimento [A] + ([A] [B]) = [A] assorbimento. Tutte le tautologie sono tra loro equivalenti, e non equivalenti a nessuna proposizione non logicamente valida; lo stesso per le contraddizioni; denotiamo con 1 la classe delle tautologie, e con 0 la classe delle contraddizioni. Allora [A] ([A]) = [A A] = 0 e [A] + ([A]) = [A A] = 1 e possiamo quindi aggiungere: [A] ([A]) = 0 [A] + ([A]) = 1 [A] 1 = [A] [A] + 0 = [A] inverso inverso elemento neutro elemento neutro

completando la lista degli assiomi delle algebre di Boole. Le ultime due leggi seguono dal fatto (o lo esprimono in altra forma) che se T ` una tautologia AT A e se F ` una contraddizione allora AF A. e e La relazione [A] [B] ` denita da [A][B] = [A], oppure dallequivalente9 e [A] [B] = 0.9

O anche da [A]+[B] = [B] - a seconda dei casi converr` usare luna o laltra denizione. a

53

Inseriamo qui una dimostrazione dellequivalenza tra due denizioni di , dove si noter` lanalogia formale con quella fatta in 4.3.1 per la denizione a di (la 28 e la 30 dellalgebra degli insiemi). Se xy =x allora 1 = x + (x) 1 = (x y) + (x) 1 = (x + (x)) (y + (x)) 1 = (y + (x) 0 = x (y). Viceversa se x (y) = 0 allora x=x1 x = x (y + (y)) x = (x y) + (x (y)) x = x y. Esercizio. Dimostrare lequivalenza con la (versione corrispondente della) 29. Dallequivalenza booleana delle due denizioni di si deriva la seguente propriet` logica, che a A A B se e solo se |= A B. Una dimostrazione logica di questo fatto ricalca la dimostrazione algebrica di sopra. Si noti che [A] = 0 signica che A ` una contraddizione. e Allora la seguente ` una deduzione del fatto che |= A B segue da e A A B: A A (A B) A (A A) (B A B A A B. 54

Ogni proposizione o ` una tautologia o segue logicamente dalle precedenti e e da A A B, quindi lultima ` una tautologia. e Viceversa, se A B ` una contraddizione e A A (B B) A (A B) (A B) A A B. Esercizio. Dimostrare in modo analogo che A A B se e solo se |= B A. La corrispondenza tra le deduzioni algebriche e quelle logiche ` fondata e sulla corrispondenza tra [A] [B] e |= A B. Il fatto che per ogni A, 0 [A] 1 corrisponde al fatto che una contraddizione implica qualsiasi proposizione, e una tautologia ` implicata da e qualsiasi proposizione. La relazione booleana ha le seguenti propriet`, che se a b allora a b a e per ogni c, c a c b e c + a c + b (esercizio). Queste propriet` corrispondono per limplicazione al fatto che se |= A a B allora |= B A e per ogni C, |= C A C B e |= C A C B (esercizio). La propriet` transitiva di corrisponde alla transitivit` del condizionale, a a mentre la propriet` di sostituzione t = s f (t) = f (s) corrisponde ad a unanaloga propriet` logica: se in una proposizione si sostituisce una sottoa proposizione con una equivalente, il risultato ` una proposizione equivalente e a quella iniziale. Conviene indicare loperazione di rimpiazzamento di una sottoproposizione B con C in una proposizione A, con la notazione: A[B/ /C]. Si ha allora che se B C allora A A[B/ /C]. Nellesempio di sopra A A (A B) A poich A A B. e Nella dimostrazione, per trattare i vari casi, si fa uso dei seguenti fatti Per ogni A e B, se A B, allora se A1 A2 e B1 B2 , allora A B A1 B1 A2 B2

che si dimostrano facilmente con le tavole di verit` per i vari connettivi. a

55

4.5

Rapporti tra proposizioni e insiemi

I rapporti tra algebra degli insiemi con operazioni insiemistiche, logica proposizionale con connettivi e algebra boleana sono molteplici e bidirezionali. Sostanzialmente largomento ` sempre lo stesso, con varianti formali, e a sece onda delle preferenze si pu` adottare luno o laltro dei tipi di simbolismo o coinvolti; la familiarit` con luno aiuta anche nello svolgimento dellaltro, ma a il ragionamento ` identico. e Abbiamo visto come, per dimostrare le leggi dellalgebra degli insiemi (cio` identit` valide per tutti i sottinsiemi di un qualunque insieme non vuoto e a U ), procedendo direttamente in base alla denizione di uguaglianza tra insiemi (X = Y se e solo se X Y e Y X) ci si riconduca ad applicare leggi logiche a proposizioni costruite su atomiche della forma x X, x Y, . . . Si possono anche al contrario derivare le leggi logiche dalle leggi dellalgebra degli insiemi. In generale due proposizioni (con o senza la x) logicamente equivalenti10 hanno lo stesso insieme di verit` in ogni U . a Supponiamo infatti che p(x) sia equivalente a q(x). Allora siccome p(x) q(x) e q(x) p(x) sono sempre vere, Vp(x)q(x) e Vq(x)p(x) sono entrambi uguali a U ; ma siccome Vp(x)q(x) = ( Vp(x) ) Vq(x) , se questo ` uguale a U e allora Vp(x) Vq(x) e viceversa, quindi Vp(x) = Vq(x) . Vale anche il viceversa; diciamo che una proposizione p(x) ` valida in U e se Vp(x) = U ; allora se Vp(x) = Vq(x) in U si ha che p(x) q(x) ` valida in U . e Basta ripercorrere allindietro i precedenti passaggi. Supponiamo allora di voler dimostrare |= (p q) p q. Pensiamo ad un insieme qualunque U (che non c` bisogno di precisare, e in accordo col fatto che usiamo leggi valide per insiemi qualunque). Consideriamo i sottoinsiemi Vp = {x U | p } e Vq = {x U | q }. Non importa che p e q contengano o no la x; basta che valga, per denizione, che x Vp p, cio` che Vp sia denito ponendo che x Vp ` vero se e solo se p ` vero. Se e e e p non contiene x, p o ` vera o ` falsa, indipendentemente da x. In tal caso e e Vp = {x U | p } o ` o ` U . e e Dalla denizione di insieme di verit` e dalla legge insiemistica a (Vp Vq ) = ( Vp ) ( Vq ),10 Nel senso che p(x) e q(x) hanno sempre lo stesso valore di verit` calcolato a partire a dalla attribuzione di 0 e 1 alle loro componenti atomiche, anche se contengono x.

56

cio` e x (Vp Vq ) se e solo se x ( Vp ) ( Vq ), segue, siccome x (Vp Vq ) se e solo se (p q), e analogamente per x ( Vp ) ( Vq ), che (p q) p q ` vero qualsiasi siano p e q, la cui verit` o falsit` non gioca alcun ruolo nella e a a dimostrazione1