INTRODUZIONE ALLA LOGICA 1 Le proposizioni semplici La logica è lo studio del ragionamento che, partendo da alcune premesse, consente di arrivare a determinate conclusioni. Come la matematica, anche la logica dispone di un proprio per esprimere i concetti e gli argomenti studiati. In matematica si usano i numeri, le variabili, gli operatori aritmetici e le espressioni; nella logica si usano le proposizioni semplici, i connettivi logici e le proposizioni composte. linguaggio Partiamo quindi dalla definizione della proposizione logica più elementare. Una proposizione semplice è una qualunque frase, vera o falsa, nell’universo di riferimento. Questa importante definizione ci fornisce numerose informazioni. Innanzitutto la logica non studia tutte le frasi, ma considera unicamente le    , cioè quelle frasi che sono sempre, sicuramente, o , o . ▶ proposizioni vere false Per esempio, la frase «2 è un numero pari» può essere considerata, perché si tratta di una proposizione logica vera. Quando diciamo che una proposizione logica è vera, oppure è falsa, stiamo dando alla frase un che indicheremo con ( ) oppure ( ). valore di verità vero V falso F Il valore di verità di una frase potrebbe anche cambiare in base alle circostanze, ma una proposizione non può mai essere contemporaneamente sia vera sia falsa.   / proposizione proposition esempio «Oggi nevica» Per conoscere il valore di verità di questa proposizione, basta guardare dalla finestra. Poiché non è possibile che nevichi e non nevichi contemporaneamente, questa frase è una proposizione. Se ci soffermiamo a riflettere sull’esempio precedente ci viene, però, un dubbio, attraverso quale finestra dobbiamo guardare? La risposta è: quella che viene indicata dall’universo al quale facciamo riferimento. Studiando la logica infatti, come sappiamo dalla definizione di proposizione semplice, è importante stabilire un   al quale fare riferimento. universo esempio «Si diventa maggiorenni a 18 anni» La proposizione è vera se consideriamo come universo  , ma fino al 1975 nel nostro paese si diventava maggiorenni a 21 anni; senza contare il fatto che, in altri paesi, la legge stabilisce la maggiore età diversamente. oggi, in Italia Nel momento in cui viene fissato l’universo di riferimento (oggi, in Italia), la frase dell’esempio diventa sicuramente vera e quindi diventa una proposizione. Consideriamo, invece, la frase «1 + 1 = 10», nell’universo decimale è una proposizione falsa ma nell’universo binario è vera. In ogni caso, fissato l’universo di riferimento (sistema decimale oppure binario), la frase considerata è una . proposizione logica E le frasi che non sono proposizioni? Le frasi che non rientrano nella definizione di proposizione non vengono studiate dalla logica. Sicuramente sono proposizioni logiche le frasi né vere né false, come: non «Come stai?» «Torna qui!» «L’informatica è bella» Se una frase è una , un’ oppure esprime un’ , sicuramente non può trattarsi di una proposizione, perché non è possibile stabilire se è vera oppure falsa. domanda affermazione imperativa opinione Al contrario, frasi come le seguenti sono proposizioni logiche, anche se possono sembrare strane: «La Luna è il satellite della Terra» «Le galline hanno quattro zampe» Se prendiamo come universo di riferimento il nostro pianeta, la prima proposizione è vera, mentre la seconda è falsa. Nel linguaggio della logica le proposizioni semplici vengono indicate utilizzando le dell’alfabeto. Per esempio: lettere minuscole «Oggi splende il sole» p: «La luce è spenta» q: prova tu   Una proposizione semplice è: una qualunque frase, vera o falsa. una qualunque frase, vera o falsa, in un universo di riferimento. un universo di riferimento di una qualunque frase, vera o falsa.  >> pagina 113  I connettivi logici In è possibile scrivere «2 + 3 = 5», per esprimere il concetto che se si uniscono il numero 2 e il numero 3 utilizzando il +, allora si ottiene un altro numero, il 5, che rappresenta la loro composizione. matematica Nella esiste un’astrazione analoga, in base alla quale utilizzando i è possibile collegare fra loro le proposizioni semplici, ottenendo proposizioni . I connettivi logici principali sono: logica connettivi logici composte ; ▶ negazione non ; ▶ congiunzione e ; ▶ disgiunzione o inclusiva . ▶ disgiunzione o esclusiva   / negazione negation / congiunzione conjunction / disgiunzione inclusiva disjunction / disgiunzione esclusiva esclusive disjunction  >> pagina 114 La negazione “non” Data la proposizione p , la sua negazione è non p e si indica con ¬ p . Il valore di verità di ¬ dipende dal valore di verità della proposizione di partenza che può essere o vera o falsa. p p esempio Data la proposizione semplice: p : «Oggi piove» la sua negazione è la proposizione composta: ¬   p : «Oggi non piove» Per stabilire il valore di verità di   p   basta guardare fuori dalla finestra e constatare quale tra le seguenti possibilità si è verificata. : «Oggi piove» è  p vero ¬  : «Oggi non piove» è  p falso : «Oggi piove» è  p falso ¬  : «Oggi non piove» è  p vero Possiamo riassumere  tutti i casi  che si possono verificare scrivendo una  tabella di verità . La   è uno strumento che consente di determinare il valore logico di una proposizione a partire dalla proposizione semplice e dal connettivo logico. tabella di verità colonna che contiene tutti i valori di verità che può assumere la proposizione semplice di partenza p p ¬ p colonna che contiene tutti i valori di verità che la negazione , assume in funzione del valore di ¬ p p V F F V La   è un connettivo logico   perché opera su una sola proposizione. negazione unario Gli altri connettivi logici che analizzaremo, operano invece su due proposizioni e per questo motivo vengono detti connettivi logici  . binari La congiunzione “e” Date le proposizioni p e q , la loro congiunzione è p e q e si indica con p q . Il valore di verità di ^ dipende dai valori di verità delle proposizioni e di partenza che possono essere, ciascuna, o vera o falsa. p q p q esempio Date le proposizioni semplici: : «Oggi piove», : «Marco ha l’ombrello» la loro congiunzione è la proposizione composta: p q p ^ q : «Oggi piove e Marco ha l’ombrello» Per stabilire il valore di verità di e di basta guardare fuori dalla finestra e constatare quale tra le seguenti possibilità si è verificata: p q «Oggi piove» e «Marco ha l’ombrello» «Oggi piove» e «Marco non ha l’ombrello» «Oggi non piove» e «Marco ha l’ombrello» «Oggi non piove» e «Marco non ha l’ombrello» Se guardando dalla finestra vediamo che sta piovendo e che Marco ha l’ombrello, allora la proposizione composta ^ : «Oggi piove e Marco ha l’ombrello» è . p q vera Se sta piovendo, ma Marco si sta bagnando perché è senza ombrello, allora la proposizione composta ^ : «Oggi piove e Marco ha l’ombrello» è . p q falsa Se non sta piovendo, sia che Marco abbia l’ombrello, sia che non ce l’abbia, la proposizione composta ^ : «Oggi piove e Marco ha l’ombrello» non afferma il vero perché non piove e quindi è . p q falsa Anche per la congiunzione, possiamo riassumere che si possono verificare scrivendo una . tutti i casi tabella di verità colonne in cui sono indicate tutte le possibili combinazioni di valori di verità che possono essere assunti dalle proposizioni   e  p q p q p q ∧ colonna che contiene tutti i valori di verità che assume   Λ  , in funzione dei valori di   e di  p q p q V V V V F F F V F F F F La   è vera solo quando le proposizioni che la compongono sono entrambe vere. In tutti gli altri casi, è falsa. congiunzione prova tu   Vero o falso La negazione è un connettivo logico binario.     V F Il simbolo della congiunzione è ^.     V F  >> pagina 115  La disgiunzione “o” inclusiva ∨  Date le proposizioni p e q , la loro disgiunzione inclusiva è p o q e si indica con p q . Il valore di verità di dipende dai valori di verità delle proposizioni e di partenza che possono essere, ciascuna, o vera o falsa. p q p q esempio Date le proposizioni semplici dell’esempio precedente la loro disgiunzione inclusiva è la proposizione composta: p ∨  q : «Oggi piove o Marco ha l’ombrello» Come per la congiunzione, per stabilire il valore di verità di e di basta guardare fuori dalla finestra e constatare quale tra le seguenti possibilità si è verificata: p q «Oggi piove» o «Marco ha l’ombrello» «Oggi piove» o «Marco non ha l’ombrello» «Oggi non piove» o «Marco ha l’ombrello» «Oggi non piove» o «Marco non ha l’ombrello» La proposizione composta ∨  : «Oggi piove o Marco ha l’ombrello» è se si verifica almeno una delle due condizioni descritte dalle proposizioni semplici. Quindi, basta che piova e automaticamente la proposizione composta diventa . p q vera vera Analogamente, è sufficiente che Marco abbia l’ombrello perché la proposizione composta sia . vera L’unico caso in cui la proposizione composta ∨  : «Oggi piove o Marco ha l’ombrello» è è quello in cui, guardando dalla finestra, si constata che non sta piovendo e inoltre Marco non ha l’ombrello. p q falsa attenzione   Nella logica anche le frasi apparentemente incoerenti, come quella di questo esempio, hanno un significato logico. Possiamo riassumere che si possono verificare scrivendo la per la disgiunzione inclusiva. tutti i casi tabella di verità colonne in cui sono indicate tutte le possibili combinazioni di valori di verità che possono essere assunti dalle proposizioni   e  p q p q p q ∨ colonna che contiene tutti i valori di verità che assume   ∨ , in funzione dei valori di   e di  p q p q V V V V F V F V V F F F La è falsa solo quando le proposizioni che la compongono sono entrambe false. In tutti gli altri casi, è vera. disgiunzione inclusiva La disgiunzione inclusiva si chiama così perché   include   la possibilità che entrambe le proposizioni semplici   p e q   si possano verificare contemporaneamente. Esistono però casi in cui questa possibilità non può essere contemplata. Lo sapevi che Il termine latino   vel , che significava “o” con senso inclusivo, ha forse prestato l’iniziale al simbolo per rappresentare la disgiunzione inclusiva.  >> pagina 116  La disgiunzione o esclusiva Nel linguaggio comune usiamo il in due modi diversi, spesso senza rendercene conto; infatti, può avere un significato: connettivo o (latino ): quando la possibilità che le ipotesi ( e ) possano essere vere entrambe nello stesso momento; inclusivo vel include p q (latino ): quando la possibilità che le ipotesi ( e ) possano essere vere entrambe nello stesso momento e pertanto il verificarsi delle due ipotesi è strettamente alternativa. esclusivo aut esclude p q esempio Consideriamo le seguenti proposizioni composte. «Marco guarda la televisione o mangia i pop corn» La proposizione composta è se Marco guarda la televisione oppure se mangia i pop corn ed è se non fa nessuna delle due attività. vera falsa Nulla esclude che Marco possa fare le due cose contemporaneamente: se guarda la tv mangiando i pop corn, la proposizione resta vera. «Andrea va a lavorare in treno o in automobile» La proposizione composta è se Andrea va a lavorare in treno o se va a lavorare con l’automobile. La proposizione è se Andrea non usa né il treno, né l’automobile. vera falsa Il verificarsi di uno dei due casi il contemporaneo verificarsi dell’altro! Se Andrea va a lavorare in treno non è possibile che usi contemporaneamente l’automobile, e viceversa. esclude Nella logica i due tipi di vengono considerati separatamente prendendo rispettivamente il nome di    ( ) e    ( ). o ▶ o inclusivo OR ▶ o esclusivo XOR Date le proposizioni p e q , la loro disgiunzione esclusiva è p o q e si indica con p ⩒ q . Il valore di verità di ⩒  dipende dai valori di verità delle proposizioni e di partenza che possono essere, ciascuna, o vera o falsa. p q p q esempio Date le proposizioni semplici: : «Andrea va a lavorare in treno», p : «Andrea va a lavorare in automobile» la loro disgiunzione esclusiva è: q   p ⩒ q : «Andrea va a lavorare in treno o in automobile» Ancora una volta, per stabilire il valore di verità di e di basta guardare p q che cosa sta facendo Andrea e constatare quale tra le seguenti possibilità si è verificata: «Andrea va a lavorare in treno» (e quindi non in automobile) «Andrea va a lavorare in automobile» (e quindi non in treno) «Andrea non va a lavorare né in treno né in automobile» (magari va a piedi!) L’unica ipotesi alla quale verificarsi è «Andrea va a lavorare non è consentito in treno e in automobile» (è impossibile) e pertanto risulta . falsa   / o inclusivo or / o esclusivo exclusive or Possiamo riassumere che si possono verificare scrivendo la della disgiunzione esclusiva. tutti i casi tabella di verità colonne in cui sono indicate tutte le possibili combinazioni di valori di verità che possono essere assunti dalle proposizioni   e  p q p q p q ⩒ colonna che contiene tutti i valori di verità che assume   ⩒ , in funzione dei valori di   e di  p q p q V V F V F V F V V F F F attenzione   La   disgiunzione esclusiva   ha una tabella quasi identica a quella della   disgiunzione inclusiva , differisce solo nel caso in cui   p   e   q   siano entrambe vere.  >> pagina 118 Le proposizioni composte e le tabelle di verità Come abbiamo visto, applicando i connettivi logici alle , si ottengono delle . È possibile applicare i connettivi logici anche alle proposizioni composte ottenendo altre proposizioni composte, via via sempre più articolate. proposizioni semplici proposizioni composte In generale una proposizione composta è una frase formata da più proposizioni, legate fra loro da connettivi logici . esempio Date le proposizioni semplici: : «Roberta ascolta la musica», : «Roberta canta» è possibile ottenere, fra le altre, la proposizione composta: p q ( p  ∨ ¬ p ) ∧ ¬ q che potrebbe essere letta «Roberta ascolta la musica o non la ascolta, e non canta». Fino a questo momento dare un significato alle proposizioni (semplici o composte) è stato utile per comprendere meglio come lavora la logica. Da questo punto in avanti abbandoneremo le frasi e useremo solo la delle proposizioni. notazione letterale Come le proposizioni semplici, anche quelle possiedono un proprio , vero ( ) oppure falso ( ), che dipende dal valore di verità delle proposizioni che le costituiscono. composte valore di verità V F La ricerca del valore di verità delle proposizioni composte è oggetto di studio della logica e prende il nome di calcolo proposizionale . Per stabilire i valori di verità delle proposizioni composte, si ricorre alle . tabelle di verità La costruzione delle tabelle di verità La di una proposizione composta si costruisce per passi successivi, come quando si risolve un’espressione algebrica. tabella di verità : si la proposizione composta e si le proposizioni semplici contenute al suo interno ( ). Ciascuna proposizione, anche se compare più volte, deve essere conteggiata una volta sola. Passo 1 osserva determinano N : si utilizza la formula = 2 per ottenere il ( ) della tabella di verità. Passo 2 R N numero di righe R : di righe inserendo nelle prime colonne le proposizioni semplici. Passo 3 si disegna una tabella R N : nella prima colonna si inseriscono delle V nella prima metà delle righe e delle F nella seconda metà. Le successive colonne riferite alle proposizioni semplici vanno riempite tenendo conto della colonna precedente: vicino alle V (della colonna precedente) si inseriscono metà V e metà F e si fa la stessa cosa per le F. Si continua per tutte le proposizioni semplici presenti nella tabella. Passo 4 : se nella proposizione composta ci sono delle , si completano le colonne corrispondenti determinando i valori di verità a partire dalle proposizioni semplici. Passo 5 proposizioni semplici negate : la proposizione composta di partenza, e tenendo conto delle , si determina quale composta considerare per scrivere la nuova colonna. Passo 6 osservando colonne già ottenute sotto-proposizione : fino a determinare i valori logici della colonna che si riferisce all’intera proposizione composta di partenza. Passo 7 si ripete il passo 6 esempio Determiniamo i valori di verità della proposizione composta: ( p ∨  ¬ p ) ∧   ¬ q : le proposizioni semplici sono 2 ( e ; anche se compare due volte, quindi = 2 Passo 1 p q) p N : = 2 = 2 = 4 Passo 2 R N 2 : la tabella ha = 4 righe e = 2 proposizioni (colonne verdi). Passo 3 R N : inseriamo le V e le F a partire dalla prima colonna, per tutte le proposizioni semplici (colonne verdi), come mostrato in figura. Passo 4 : per determinare ¬ guardiamo la colonna e scriviamo il valore di verità opposto (dove è vera, scriviamo che ¬ è falsa e viceversa). Procediamo allo stesso modo per determinare ¬ . Passo 5 p p p p q : consideriamo la sotto-proposizione contenuta nella parentesi, cioè ( ∨ ¬ ). Questa sotto-proposizione ci dice che il connettivo logico da utilizzare è la o inclusiva e che le colonne da considerare sono quella di e quella di ¬ . Passo 6 p p p p : resta da mettere in relazione con il connettivo logico la colonna di ( ∨ ¬ ) e quella di ¬ . Passo 7 e p p q La tabella di verità elenca tutte le   (nelle colonne in verde), cioè tutti i possibili modi in cui le   possono essere verificate. ipotesi proposizioni semplici Con i  , che permettono di ottenere le colonne intermedie (colonne in bianco), la tabella di verità consente di conoscere, per ciascuna ipotesi, il corrispondente valore di verità della   (colonna in azzurro). calcoli proposizionali proposizione composta Quando la proposizione composta è formata da  , la tabella di verità aumenta il numero delle righe perché aumenta il numero delle possibili combinazioni iniziali. più di due proposizioni semplici attenzione   Il numero di righe   R   della tabella di verità è pari al numero di combinazioni diverse che si riescono a ottenere con   N   proposizioni semplici. Ciascuna proposizione semplice può assumere solo 2 valori:   vero   o   falso . Il 2 è lo stesso che compare nella formula per determinare   R . Una proposizione semplice, infatti, si comporta come se fosse un bit, sappiamo che con   bit si possono ottenere 2N combinazioni differenti. N esempio Determiniamo i valori di verità della proposizione composta: ⩒  p ∧ ( q r ) : le proposizioni semplici sono , e , quindi: Passo 1 p q r = 3 N : = 2 = 2 = 8 Passo 2 R N 3 : la tabella ha = 8 righe e = 3 proposizioni. Passo 3 R N : inseriamo le V e le F a partire dalla prima colonna, per tutte le proposizioni semplici, come mostrato in figura. Passo 4 Nell’ultima colonna (verde) le V e le F risultano sempre alternate. p q r V V V V V F V F V V F F F V V F V F F F V F F F : si salta perché non ci sono proposizioni negate. Passo 5 : la prima sotto-proposizione da considerare è quella fra parentesi, cioè ( ⩒  ). Passo 6 q r : resta da considerare la proposizione composta di partenza. Passo 7 attenzione   La   N -esima colonna (verde) ha sempre una continua alternanza di   V   e   F . Il può essere effettuato compilando le tabelle di verità o individuando direttamente i valori di verità delle proposizioni composte. Basta sostituire i valori di verità delle proposizioni semplici in quella composta. calcolo proposizionale Se consideriamo la tabella di verità dell’esempio precedente essa ci informa che nell’ipotesi di: = F •  = F •  = V la proposizione composta vale . p q r F p q r q ⩒ r p ∧ (q ⩒ r) V V V F F V V F V V V F V V V V F F F F F V V F F F V F V F F F V V F F F F F F Lo stesso risultato può essere ottenuto attraverso la sostituzione diretta nella proposizione composta: p ∧ (  r) =     (   ) = F   (V) = F   V =    q ⩒ F ∧ F ⩒ V ∧ ∧ F prova tu   Costruisci la tabella di verità delle proposizioni. (¬ ∧  ) ∨ (¬ ∧  ) a a b b ( ∧  ∧  ) ∨ (a ∧  ∧ ¬ ) a b c b c (¬ ∧  ∧  ) ⩒ (¬ ∧ ¬ ∧  ) a b c a b c  >> pagina 121 Le proposizioni logicamente equivalenti Due proposizioni sono logicamente equivalenti se partendo dalle stesse ipotesi (colonne in verde) si arriva per entrambe alle stesse conclusioni (colonne in azzurro). Per capire se due proposizioni sono logicamente equivalenti occorre costruire le di entrambe e verificare se sono uguali. tabelle di verità Per poter considerare due di due proposizioni diverse basta che siano identiche solo le colonne delle ipotesi (verdi) e quelle delle conclusioni (azzurre). Il contenuto delle colonne intermedie (bianche) non è rilevante ai fini dell’uguaglianza fra le tabelle. uguali tabelle di verità Per comodità, spesso due tabelle vengono costruite all’interno di un’ : in questo modo le colonne delle ipotesi (verdi) vengono scritte una volta sola e sicuramente coincideranno, mentre l’uguaglianza delle colonne delle conclusioni (azzurre) diventa l’unica da verificare. unica tabella complessiva esempio Vogliamo dimostrare che: p ∧ ( q ∨ r ) = ( p ∧ q ) ∧ ( p ∧ r ) Dobbiamo costruire una tabella complessiva, all’interno della quale sia possibile individuare sia la tabella di verità della prima proposizione (indicata in rosso) sia la tabella di verità della seconda proposizione (indicata in blu). Poiché le colonne delle (verdi) coincidono e le colonne delle (azzurre) sono identiche fra loro, si può affermare che le due tabelle di verità sono uguali e che quindi le proposizioni composte da cui esse derivano siano logicamente equivalenti. ipotesi conclusioni A conclusione di questo argomento, vale la pena di sottolineare che i colori verde, azzurro e bianco utilizzati nella trattazione una universalmente riconosciuta. Le tabelle di verità, infatti, normalmente non hanno colori specifici, nella nostra trattazione abbiamo deciso di inserirli per aiutare la memorizzazione dei concetti. non costituiscono convenzione Le colonne identificate con il colore contenevano tutte le possibili combinazioni di valori di verità delle proposizioni semplici di partenza (ipotesi). verde Le colonne identificate con il colore contenevano tutti i valori di verità assunti dalle proposizioni composte di “arrivo”, in funzione dei valori delle proposizioni semplici di “partenza”. azzurro Le colonne identificate con il colore contenevano gli eventuali passaggi intermedi che non sono sempre identici, ma dipendono dalla strategia adottata per il calcolo proposizionale. bianco  >> pagina 122  ApprofondiMENTO   I CONNETTIVI LOGICI E GLI INSIEMI In matematica, l’ intersezione   fra due insiemi   P   e   Q   viene definita come l’insieme degli elementi che appartengono al primo insieme   e   al secondo insieme. L’  U tra due insiemi   e   viene invece definita come l’insieme degli elementi che appartengono al primo insieme   al secondo insieme. unione P Q o Esiste una   tra i connettivi logici e e le operazioni sugli insiemi e U e i loro simboli ce lo ricordano! corrispondenza SCHEDA CLIL   Necessary conditions vs sufficient conditions When speaking about logic, statements may be true or false and their value may affect the value of other statements. We often refer to such statements as “conditions”. The logical operation that bounds the first statement with the second statement is called “implication”, or “logical consequence”. When statement A implies statement B, we can say that if A is true, then B comes true, too. In this case, we say that statement A is a sufficient condition for statement B. It means that it’s enough to have A true to imply that B is also true. On the other hand: when A is false, and such condition implies that B is false, too, we say that statement A is a necessary condition for B. If B is true, A must be true. But if A is true, B can be any value (true o false). There are statements A that can be both necessary and sufficient for B. When it happens, we say that A is a necessary and sufficient condition for B. The vice versa also happens. We say “if and only if A happens, then B happens, too”. In computer science: “if A then B” states that A is a sufficient condition for B to happen.