La logica Scienza del ragionamento corretto A cura del Prof. Fabio Santagata 1 CENNO STORICO 384-322 a.c. Aristotele 1815-1864 George Boole 2 Logica proposizionale Lo scopo della logica, fin dai tempi di Aristotele, è quello di descrivere il ragionamento La logica proposizionale è un modello matematico che ci consente di ragionare sulla verità e sulla falsità di espressioni logiche 3 Differenza tra linguaggio naturale (LN) e linguaggio logico (LL) Linguaggio Naturale • • • Ricco di connettivi, scopo rendere la proposizione più espressiva , problema dubbia interpretazione Si considerano solo proposizioni che presentano un nesso tra le componenti A volte due negazioni negano: «Non c’è nessuno!»…"Non c'è alcuno" suona proprio male, oltretutto! Linguaggio Logico • Numero di connettivi limitati • Nesso non necessario (es: Paolo è svenuto e corre) • Due negazioni affermano sempre 4 Definizione di Proposizione Linguaggio naturale Una frase contenente un verbo Es: State zitti! Esci stasera? Domani pioverà Alessia è simpatica 4 è un numero pari Linguaggio logico Si chiama proposizione (o enunciato) ogni affermazione della quale si possa dire, oggettivamente e con certezza, che è vera o falsa 5 Esempi Sono proposizioni: ◦ Roma è la capitale d’Italia ◦ Bari è una città dell’Inghilterra Non sono proposizioni ◦ I dipinti di Picasso sono belli ◦ Forse oggi verrò a farti visita 6 Prova tu….individua le proposizioni logiche Il triangolo ha 4 lati Questo libro è interessante Vai al mare domenica? Omero è autore dell’Iliade Attento: il semaforo è rosso! I Longobardi ebbero come re Alboino Il triplo di 5 è 16 7 Proposizioni atomiche (semplici) e proposizioni composte Le proposizioni semplici possono essere composte tra loro tramite connettivi logici in modo da formare delle espressioni più complesse, dette proposizioni composte, il cui valore di verità può essere univocamente determinato a partire da quelli delle proposizioni che le compongono 8 Tipi di proposizioni logiche PROPOSIZIONI SEMPLICI - Oggi c’è il sole - vado a scuola in bici • PROPOSIZIONI COMPOSTE - oggi c’è il sole e vado a scuola in bici 9 Connettivi logici «e», «o», «non», «se…..allora», «se e solo se» sono connettivi logici: Se studi allora sarai promosso Roma è la capitale d’Italia e Bari è una città italiana Una figura è un quadrilatero se e solo se ha quattro lati 10 Connettivi logici Connettivi logici simboli non NOT e AND (et) Λ o or (vel) V XOR (aut) o esclusivo se …… allora se e solo se ¯ opp. IF THEN IF AND ONLY IF 11 Variabili proposizionali Per affrontare lo studio dei connettivi più in generale, possiamo sostituire le proposizioni con delle variabili proposizionali, che corrispondono a qualunque proposizione abbia un valore di verità. Esse acquistano, di volta in volta, il valore di verità dell’oggetto al quale esse sono associate. Allo stesso modo, invece di utilizzare «Vero» e «Falso» come valori di verità, utilizzeremo «1» e «0» 12 Variabili proposizionali PROPOSIZIONI SEMPLICI p: Oggi c’è il sole q: vado a scuola in bici • PROPOSIZIONI COMPOSTE p Λ q:oggi c’è il sole e vado a scuola in bici «p Λ q =1»significa che è vero che oggi c’è il sole ed è vero che vado a scuola in bici 13 Connettivi logici Congiunzione «Λ»(and/et) p: 9 è un numero dispari q :9 è multiplo di tre r=pΛq: 9 è un numero dispari e 9 è multiplo di 3 LA CONGIUNZIONE di due proposizioni è vera se e solo se sono entrambe vere R è vera perché è vero sia che 9 è dispari e sia che 9 è un multiplo di 3 14 Connettivi logici Congiunzione «Λ»(and/et) p: Roma è la capitale d’Italia q: Bari è una città dell’Inghilterra r=pΛq: Roma è la capitale d’Italia e Bari è una città dell’Inghilterra R è palesemente falsa, in quanto una sola delle due proposizioni semplice è vera 15 Tabelle di verità Per verificare, al variare dei valori di verità delle proposizioni semplici, come varia il valore di verità delle proposizioni composte, si usano la tabella di verità: - le prime colonne hanno come intestazione le proposizioni atomiche e come valori tutte le possibili combinazioni dei valori di verità. - l’ultima colonna ha come intestazione la proposizione composta e contiene i valori di verità che derivano dalle differenti combinazioni 16 Esempio con Tabelle di verità Esempio: p: il libro è giallo q: il quaderno è rosso r=pΛq: il libro è giallo e il quaderno è rosso Il libro è giallo Il quaderno è rosso Il libro è giallo e il quaderno è rosso Vero Vero Vero Vero Falso Falso Falso Vero Falso Falso Falso Falso 17 …. e con variabili proposizionali Esempio: p: il libro è giallo q: il quaderno è rosso r=pΛq: il libro è giallo e il quaderno è rosso p q pΛq 1 1 1 1 0 0 0 1 0 0 0 0 18 Connettivi logici Negazione p: La Sicilia è un’isola p :La Sicilia non è un’isola cambia il valore di verità della proposizione p p V F F V 19 Prova tu… Date le seguenti proposizioni, utilizzando la congiunzione e la negazione…. • a: 11 è un numero pari b: il quadrato ha 4 lati ….traduci in simboli: «11 non è un numero pari e il quadrato ha quattro lati» 20 Disgiunzione a: Mangio il dolce o la frutta • b: Paolo va a scuola o a piedi o in bici • Qual è la differenza nei dei due precedenti esempi nell’uso del connettivo o? Riflettiamo…. • Se mangio solo il dolce, la proposizione a è vera, anche se mangio solo la frutta la proposizione è vera, ma anche se mangio entrambi la proposizione è vera….invece….Paolo non può andare contemporaneamente a scuola sia a piedi che in bici! 21 Connettivi logici Disgiunzione inclusiva (OR/vel) Disgiunzione esclusiva (XOR/aut) In italiano «o» è un connettivo ambiguo: infatti vi sono frasi come «Questo modello di maglietta è in commercio in tinta blu o in tinta rossa» ovviamente se compro una maglietta di quel modello o è di colore blu o è di colore rosso! 22 Connettivi logici Disgiunzione inclusiva (OR/vel) Disgiunzione esclusiva (XOR/aut) Invece la frase: «portami delle pere o delle mele» è soddisfatta in 3 casi: sia quando vengono portate delle mele, sia quando vengono portate delle pere ed anche quando vengono portate entrambe. La parola «o» può avere quindi due distinti significati! 23 Connettivi logici Disgiunzione inclusiva (OR/vel) Disgiunzione esclusiva (XOR/aut) Or inclusivo (“OR” , il latino “vel”): una proposizione non esclude l’altra Or esclusivo (“XOR” da “exclusive OR”, in latino “aut”) 24 Tabella di verità: Disgiunzioni. p q p V q p q 1 1 1 0 1 0 1 1 0 1 1 1 0 0 0 0 25 Prova tu…. riscrivi in linguaggio simbolico utilizzando i connettivi più appropriati Un numero è pari o dispari Il cane corre o abbaia Questa sera leggo o dormo Mangio il dolce o la frutta Mangio o il dolce o la frutta 26 Lewiss Carrol e il gioco delle torte Uno dei crucci più grandi di Lewis Carroll era quello di raccontare nel modo più semplice possibile la logica ai suoi giovani lettori. L'interesse verso i paradossi della logica era sempre ampio e sfociò nella pubblicazione del tomo Logica Simbolica e nella proposizione de Il gioco della logica, una sorta di gioco da tavolo su uno schema quadrato sviluppato a partire dal sistema proposto nel 1761 dal grande Leonhard Euler. Nelle intenzioni di Carroll, il gioco doveva essere fruibile dai bambini della scuola materna, ma nei fatti risultò molto più complesso e all'epoca (e forse anche oggi) poco utile per la diffusione della logica tra i giovani. L'idea era quella di utilizzare, attraverso alcune regole di base, uno schema nel quale realizzare la tavola della verità di una data affermazione. 27 Lewiss Carrol e il gioco delle torte «il gioco delle torte logiche» è un gioco estremamente più semplice dove il tavolo di gioco è dato da un quadrato diviso in quattro settori (la sola dispensa più piccola del gioco di Carroll), vi è un solo tipo di gettone e si considera come insieme universo solo quello delle torte. Inoltre esprimiamo solo proposizioni atomiche o composte da due o tre proposizioni atomiche. Il gioco prevede due giocatori che si alternano in due ruoli: il primo propone una proposizione rappresentabile nella tavola di gioco, il secondo deve rappresentarla nella tavola. Frasi rappresentabili sono, ad esempio, “le torte fresche sono salate” (basta porre un gettone nel settore superiore a destra) e “le torte stagionate sono salate o dolci” (basta porre un gettone nella parte inferiore sulla linea che divide il settore destro da quello sinistro). I materiali previsti per questo gioco sono: le tavole, i gettoni e dei manualetti d'istruzione. 28 Lewiss Carrol e il gioco delle torte Rappresenta le proposizioni: Le torte fresche sono salate Le torte stagionate sono salate o dolci Le torte sono dolci e fresche Le torte sono stagionate o dolci Le torte sono stagionate e non dolci Le torte non sono né dolci e né salate Le torte o sono stagionate e dolci oppure non sono non dolci e sono non fresche (che caratteristiche hanno le proposizioni contenute?) 29 Concetto di enunciato aperto ad una variabile: i predicati Si dice «enunciato aperto p ad una variabile x» o «predicato» un’espressione logica in cui occorre una variabile x, il cui valore appartiene ad un insieme U detto universo. Si indica con p(x) Ad esempio: il predicato p(x) = «x è un multiplo di 4» è una proposizione che potrà assumere valori di vero o falso a seconda del valore che assume x. L’universo U è rappresentato dai numeri naturali U=N 30 Concetto di enunciato aperto ad una variabile: i predicati ESEMPIO: p(x): x è in Italia U = {Napoli, Roma, Londra, Parigi} ◦ ◦ ◦ ◦ Se Se Se Se x= Napoli x= Roma x=Londra x=Parigi p(x) è vera p(x) è vera p(x) è falsa p(x) è falsa 31 Connettivi logici Implicazione p: x è un multiplo di 4 q: x è divisibile per 2 U: insieme dei numeri naturali (N) p q: se x è un multiplo di 4 allora x è divisibile per 2 p q p q 1 1 1 1 0 0 0 1 1 0 0 1 32 Prova tu …. Il professore promette a Paolo “ se studi tutte le materie allora sarai promosso” p q p q V V V V F F F V V F F V 1) il prof ha detto il vero 2) il prof non ha detto il vero 3) Non è in contrasto con la promessa, Paolo è stato promosso pur non avendo studiato tutte le materie 4) Il prof ha detto il vero, Paolo non ha studiato e non è quindi stato promosso 33 Connettivi logici Doppia implicazione p: la Sicilia è un’isola q : la Sicilia è circondata dal mare p q: la Sicilia è un’isola se e solo se è circondata dal mare p q p q V V V V F F F V F F F V 34 Connettivi logici Doppia implicazione Vero o falso? «1+1 = 3 se e solo se Alessandro Manzoni ha scritto la Divina Commedia» p q p q V V V V F F F V F F F V 35 Connettivi logici Doppia implicazione Vero o falso? «1+1 = 3 se e solo se Alessandro Manzoni ha scritto la Divina Commedia» p q p q V V V V F F F V F F F V 36 Connettivi logici Doppia implicazione Vero o falso? «La figura è un rombo se e solo se ha quattro lati» «Un numero è divisibile per 10 se e solo se termina per 0» 37 Tautologie e Contraddizioni Tautologie Contraddizioni E’ una proposizione composta che è sempre vera, per qualunque valore delle proposizioni componenti E’ una proposizione composta che è sempre falsa per qualunque valore delle proposizioni componenti Es: Un numero naturale è pari Es: Dormo e sono sveglio o dispari La circonferenza è una linea Una linea è una retta oppure retta e curva non lo è 2 è un numero pari o non lo è A pallavolo si vince o si perde 38 Tautologie e Contraddizioni Tautologie Contraddizioni p v p è sempre vera “Questa scuola o è un liceo o non è un liceo” p Λ p è sempre falsa “Questa scuola è un liceo e non è un liceo” Esempio con i predicati: Esempio con i predicati: I quadrilateri con un I quadrilateri con un angolo di x gradi angolo di x gradi hanno quattro lati! hanno tre lati! L’universo sono i L’universo sono i numeri da 0 a 360 numeri da 0 a 360 39 Applichiamo quanto studiato! Aiutiamo il commissario Marmaduke Il commissario Marmaduke rilesse ancora una volta la lettera che aveva ricevuto dagli amici: “Caro amico Marmaduke, abbiamo assolutamente bisogno del suo aiuto. Ci raggiunga presto in Transilvania al castello del conte Dracula. Firmato: Lord Black e sir Peabody”. La carrozza si fermò in vista del castello. La luna cominciava a nascondersi dietro una delle torri, e anche controluce, la malformata fortezza appariva diabolica. I cavalli erano nervosi e manifestarono il loro malcontento all'improvvisa fermata. Fu all'ululare dei lupi che Marmaduke ricordò le storie che i contadini gli avevano raccontato sul castello di Dracula. L'uomo a cassetta lo fece scendere e prima di prendere commiato disse con fare misterioso: “se deve proprio andare, Signore, ricordi bene quanto le dico. - O sir Peabody o Lord Black, ma non entrambi, sono vampiri. - Se Dracula è vivo allora sir Peabody è un vampiro. - Dracula è vivo o Lord Black è un vampiro. - Se Lord Black è un vampiro allora Dracula è vivo. Ricordi bene, Signore”. 40 Applichiamo quanto studiato! Aiutiamo il commissario Marmaduke Poi parti come se avesse avuto il diavolo dietro. In un attimo era sparito. Marmaduke pensò che le parole avevano un preciso significato. S'incamminò. Sembrava che nessuno si fosse preso cura del castello per anni. Aprì la porta. C'erano pipistrelli in giro ! Era troppo meravigliato per aver paura... per il momento. Nella tremula luce di una candela, trattenne il fiato quando vide avanzare l'amico ed udì una voce familiare. Per un attimo temette di aver di fronte a sé il conte o sir Peabody; fu ben felice di riconoscere la voce di Lord Black. Ripensando alle parole del cocchiere aveva fatto un semplice calcolo e sapeva con certezza che: Dracula era vivo, sir Peabody era un vampiro mentre Lord Black non lo era. Con gioia riabbraccio l'amico e ... come finisce la storia ? Aveva ragione Marmaduke a non aver paura di Lord Black ? 41 Applichiamo quanto studiato! Aiutiamo il commissario Marmaduke P = Peabody è un vampiro B = Lord Black è un vampiro D = Dracula è vivo Sappiamo con certezza che le affermazioni del cocchiere sono tutte vere. Dobbiamo quindi escludere tutte le combinazioni dove le proposizioni composte hanno valore 0. 42 Applichiamo quanto studiato! Aiutiamo il commissario Marmaduke P = Peabody è un vampiro B = Lord Black è un vampiro D = Dracula è vivo Le combinazioni possibili sono contornate di rosso. Se B fosse vero(1), allora D sarebbe vero(4), ma se D è vero allora anche P è vera(2). Ma è impossibile che siano entrambi vampiri (1)! Dunque B è falso. Se P fosse vera(1), allora B sarebbe falsa (1), ma se B è falsa allora D deve necessariamente essere vera (3) 43 Peabody è un vampiro e Dracula è vivo! Proviamo ancora? Sir Holmes e l’assassino! A Londra il famoso investigatore Sir Holmes è alle prese con un crimine efferato: un uomo è stato ucciso nella sua camera da letto! Holmes dopo un attento esame della salma e della stanza espone le sue deduzioni al fedele Watson: - L’assassino è Moriarty o Jack lo Squartatore ma non possono aver commesso il delitto insieme - se la finestra della camera è aperta allora vi è stato un furto - se è stato effettuato un furto allora Moriarty è l’assassino - se Jack è l’assassino allora la finestra della camera è aperta. Soddisfa le seguenti richieste: 1. Traduci in linguaggio simbolico ogni singola deduzione di Holmes 2. Holmes ha già capito chi è il colpevole. Mostra di non essere da meno! 44 Comporre proposizioni ben fatte (FBF) Un proposizione composta, per avere un significato, deve essere composta correttamente, cioè secondo alcune regole. In questo caso si parla di FBF «formule ben formate». “->p Λ V p q VV -> Λ p” non è una FBF!!! 45 Comporre proposizioni ben fatte (FBF) Le proposizioni: 1. possono essere delle lettere. Es: p,q,r, etc…. 2. possono essere tautologie e contraddizioni: V o F 3. possono essere delle espressioni aperte: p(x), q(x) 4. possono essere oggetti indicati nei punti 1,2,3 e congiunti dai connettivi logici. ES: (p V q) 5. possono essere oggetti indicati nei punti 1,2,3 e negati: ES: p 6. possono essere oggetti descritti in tutti i precedenti punti a cui applico le regole 5 e 6 ES: ((q Λ p)V p) Λ r(x) x∈ 𝑼 46 Equivalenza tra formule logiche Due formule logiche sono equivalenti quando hanno lo stesso valore di verità per la stessa combinazione di valori di verità per le proposizioni atomiche che le compongono. Ad esempio le seguenti formule sono equivalenti: (q Λ p) e (q V p) Proviamolo costruendo la tabella di verità! 47 Leggi e proprietà Per le espressioni logiche valgono alcune proprietà: 1. Proprietà commutativa dell’and «Λ» pΛq=qΛp 2. Proprietà commutativa dell’or «V» pVq=qVp 3. Proprietà associativa dell’and «Λ» (p Λ q) Λ r = p Λ (q Λ r) 4. Proprietà associativa dell’or «V» (p V q) V r = p V (q V r) 5. Proprietà distributiva tra and «Λ» e or «V» p V (q Λ r) = (p V q) Λ (p V r) * p Λ (q V r) = (p Λ q) V (p Λ r) 48 Leggi e proprietà 6. Leggi di idempotenza pVp=p * pΛp=p * 7. Leggi di assorbimento p V (p Λ q) = p * p Λ (p V q) = p * 8. Doppia negazione p =p 9. Leggi di De Morgan (p V q) = p Λ q (p Λ q) = p V q 10. Tautologia e contraddizione pVp=V pΛp=F 49 Esperienza di laboratorio: La logica applicata al Web, i motori di ricerca. Sapete cos’è un motore di ricerca? È un sito attraverso il quale trovare altri siti, semplicemente digitando delle «keyword» cioè delle parole chiave attinenti all’oggetto della vostra ricerca. Quali motori di ricerca conoscete? Sicuramente google! Ma ne esistono tanti altri come altavista, bing, yahoo!, virgilio etc… Riuscite sempre a trovare ciò che cercate? Avete mai pensato a come poter scrivere in modo più preciso i termini di ricerca? Spesso la ricerca standard di google non basta! 50 Esperienza di laboratorio: La logica applicata al Web, i motori di ricerca. Considerate l’homepage di google. Cliccate su ricerca avanzata 51 Esperienza di laboratorio: La logica applicata al Web, i motori di ricerca. Vedrete questa pagina: Cosa significano quelle istruzioni? ◦ Trova risultati….che contengano tutte le seguenti parole: Scrivere parole in quel form equivale alla proposizione logica: Parola1 Λ parola2 Λ parola3 (parola1 and parola2 and parola3) che come sapete è vera se e solo se sono vere tutte le proposizioni contenute cioè tutte le parole. Google vi mostrerà SOLO i risultati che contengono TUTTE le parole che avete scritto! 52 Esperienza di laboratorio: La logica applicata al Web, i motori di ricerca. Vedrete questa pagina: Cosa significano quelle istruzioni? ◦ Trova risultati….che contengano una qualunque delle seguenti parole: Scrivere parole in quel form equivale alla proposizione logica: Parola1 V parola2 V parola3 (parola1 or parola2 or parola3) , che come sapete è vera se e solo se è vera almeno una delle proposizioni contenute. Google vi mostrerà TUTTI i risultati che contengono almeno una parola che avete scritto! 53 Esperienza di laboratorio: La logica applicata al Web, i motori di ricerca. Vedrete questa pagina: Cosa significano quelle istruzioni? ◦ Trova risultati….che NON contengano le seguenti parole: Scrivere parole in quel form equivale alla proposizione logica: Parola1 Λ parola2 Λ parola3 (not parola1 and not parola2 and not parola3) , che, come sapete, è vera se e solo se sono false tutte le proposizioni contenute. Google vi mostrerà TUTTI i risultati che NON contengono nessuna delle parole che avete scritto! 54 Esperienza di laboratorio: La logica applicata al Web, i motori di ricerca. Potete anche combinare i campi di ricerca per creare ricerca più complesse. Ad esempio: …vi farà trovare siti che parlano di «telefoni cellulari», della «apple» O della «samsung», che NON sono né «motorola» e né «lg». Difatti i primi due risultati sono i siti ufficiali di Apple e Samsung mobile! SAPETE TRADURRE QUESTA RICERCA IN ESPRESSIONE LOGICA? 55 56 Il ragionamento corretto “se cè la nebbia, allora la partita è sospesa. La partita è sospesa , quindi c’è la nebbia” ?????????? p: c’è la nebbia q : la partita è sospesa Premessa: p q, q Conseguenza: p Un ragionamento è corretto se da premesse p q p q vere seguono V V V conseguenze V F F vere F V V F F V 57 Prova tu …. Considera i seguenti ragionamenti, costruisci il loro schema simbolico e, attraverso le tavole di verità, stabilisci se sono corretti Se guardo la tv, allora mi viene sonno. Mi viene sonno, quindi guardo la tv. • Se ripasso la lezione, allora sono tranquillo. Non ripasso la lezione, quindi non sono tranquillo. • 58 Forme di ragionamento valide: Modus Ponens (G. Boole) Se è vera un’implicazione ed è vero il suo antecedente, risulta vero anche il suo conseguente p: Alice è colpevole q : Bruno è colpevole Se Alice è colpevole, lo è anche Bruno. Alice è colpevole, quindi Bruno è colpevole. Premessa: p q, p Conseguenza: q p q p q V V V V F F F V V F F V 59 Forme di ragionamento valide: Modus Tollens (G. Boole) Se è vera un’implicazione ed è falso il suo conseguente, risulta falso anche il suo antecedente p: Domani c’è il sole q : vado al mare Se domani c’è il sole allora vado al mare. Non vado al mare, quindi non c’è il sole. Premessa: p q, q Conseguenza: p Prova a verificarlo con una tavola di verità…… 60 Il teorema Si chiama teorema un procedimento logico che dalle premesse porta alle conseguenze Dimostrazione Ipotesi L’insieme delle premesse Tesi Procedimento di deduzione logica L’insieme delle conseguenze Enunciato La proposizione costituita dall’ipotesi e dalla tesi 61 Fonti bibliografiche W. Maraschini – Multiformat –Paravia Abati/Binda/Quartieri- Matematica con metodo – Palumbo Editore Bergamini/Trifone/Barozzi - Algebra e geometria analitica – Zanichelli Internet – siti vari 62