Valore di verità delle formule

Se abbiamo alcune proposizioni atomiche che componiamo in una formula, possiamo provare a decidere se la formula intera è vera o falsa.

Valore di verità di una proposizione

Come prima cosa precisiamo che cos’è il valore di verità di una proposizione. Data una proposizione p, dovremmo essere in grado di decidere se è vera o falsa. Una proposizione vera avrà valore di verità 1 e una falsa 0.

Un’assegnazione di valori di verità è quindi una regola e che a una proposizione data assegna 0 oppure 1. Se scriviamo e(p), vogliamo sapere se la proposizione p è vera. Se p è la proposizione «due per due fa quattro», allora e(p) = 1, perché si tratta di una proposizione vera. Se q è la proposizione «Parigi è la capitale d’Italia», allora e(q) = 0, perché la capitale d’Italia è Roma. Quindi e è una funzione che ci restituisce se la proposizione è vera.

Qui bisogna rendersi conto che e non è una funzione magica che sa tutto del mondo. Si comporta come le diciamo noi. Non sa qual è la capitale d’Italia. All’inizio del calcolo dovremmo dichiarare come deve comportarsi la funzione di assegnazione. Se le diciamo che Parigi è la capitale d’Italia, ci restituirà e(q) = 1.

Valore di verità dei connettivi logici

Per poter stabilire la verità di una formula, dobbiamo sapere come valutare la verità dei connettivi logici. Cioè, se conosciamo le assegnazioni e(p) e e(q), quale sarà il valore di verità delle formule p ∧ q, p ⇒ q e così via.

Ogni connettivo logico si comporta in modo diverso e si usa per scopi diversi, quindi vedremo ciascun connettivo separatamente.

Valore di verità della congiunzione

La congiunzione si indica con p ∧ q e si legge «p e allo stesso tempo q». Per esempio, prendiamo la formula «L’Italia si trova nell’Europa meridionale e allo stesso tempo la sua capitale è Roma». Quando sarà vera tutta questa frase?

Per stabilire la verità ci aiuta già il connettivo stesso, «e allo stesso tempo». Ci dice espressamente che vuole che entrambe le proposizioni, a sinistra e a destra, siano vere. Se quindi le proposizioni p e q sono entrambe vere, cioè e(p) = 1 e e(q) = 1, allora è vera anche tutta la congiunzione. Nel caso opposto, cioè quando una delle proposizioni è falsa oppure lo sono entrambe, la formula intera è falsa.

Un esempio di congiunzione che non è vera può essere: «Il Po è un fiume e allo stesso tempo il Po scorre attraverso la Russia». È vero che il Po è un fiume, ma non è vero che scorre in Russia, quindi la congiunzione non è vera.

La tabella seguente lo riassume in modo chiaro:

$$\begin{array}{ccc}p& q& p\wedge q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}$$

Nelle prime due colonne ci sono i valori di verità delle proposizioni p e q e nella terza c’è il valore di verità della formula p ∧ q.

Valore di verità della disgiunzione

La disgiunzione si indica con p ∨ q e si legge «p oppure q». Esempio: «La Turchia si trova in Europa o in Asia.» Quando sarà vera tutta la frase?

Nella disgiunzione ci basta che sia vera almeno una delle possibilità. Il connettivo «o» ci dà una scelta: basta che sia vera la sua parte sinistra o la sua parte destra. L’unica piccola differenza rispetto al linguaggio comune è che la «o» logica è vera anche quando sono soddisfatte entrambe le proposizioni insieme. Questo di solito non è scontato: nel linguaggio comune usiamo spesso la «o» in modo esclusivo, cioè «o… o…»

Su questo c’è una barzelletta classica: una famiglia sceglie un’auto nuova in una concessionaria di usato. Il papà dice al venditore: «abbiamo deciso che prendiamo l’auto blu o quella rossa». Il venditore ha venduto loro entrambe le auto. Questa è un’illustrazione della differenza tra la «o» logica e quella parlata: il papà intendeva probabilmente che avrebbero scelto una sola delle auto, mentre il venditore ha considerato valida la possibilità di venderle tutte e due.

La frase precedente sulla Turchia è vera, perché sono vere entrambe le proposizioni. La frase «il numero 7 è divisibile per 3 oppure il numero 7 è primo» è vera, perché sette è un numero primo. Non è divisibile per tre, è vero, ma questo ormai non ci interessa. Tavola dei valori di verità:

$$\begin{array}{ccc}p& q& p\vee q\\ 1& 1& 1\\ 1& 0& 1\\ 0& 1& 1\\ 0& 0& 0\end{array}$$

Valore di verità dell’implicazione

L’implicazione si indica con p ⇒ q e si legge «se p, allora q». Un esempio di implicazione può essere la frase «se beviamo molto rum, allora vomiteremo». Quando sarà vera la frase?

L’implicazione logica è il più insidioso di tutti i connettivi e anche nel linguaggio comune spesso non è capita bene e viene confusa con l’equivalenza. Proviamo a rispondere alla domanda se valga anche l’implicazione inversa: q ⇒ p.

Sappiamo che se beviamo molto rum, allora vomiteremo. Vale anche che se vomitiamo, allora abbiamo bevuto molto rum? Sicuramente no: potevamo aver bevuto un altro alcolico e stare male comunque, oppure possiamo stare male per tutt’altro motivo. L’implicazione inversa quindi non vale automaticamente. Se vale p ⇒ q e allo stesso tempo vale q ⇒ p, si tratta di un’equivalenza, come vedremo più avanti.

Un altro esempio: «se domani pioverà, allora Marco porterà con sé l’ombrello». E ora ti dico che Marco ha portato con sé l’ombrello. La domanda è: quel giorno ha piovuto? Molti tendono a rispondere di sì, certo, visto che Marco l’ombrello lo prende quando deve piovere. Ma la frase originale non è costruita così!

In realtà Marco può aver preso l’ombrello per qualcos’altro, di cui non abbiamo idea. Magari Marco porta con sé l’ombrello ogni volta che va a trovare la suocera, per poterle cavare un occhio. Oppure ha deciso di comprarsi un ombrello nuovo e vuole buttare via quello vecchio. Sono tutti motivi legittimi per cui Marco può aver preso l’ombrello anche se non è detto che abbia piovuto.

Ora possiamo rispondere alla domanda su quando l’implicazione sarà vera. Quando entrambe le proposizioni sono vere, l’implicazione è sicuramente vera: «se 42 è un numero naturale, allora è positivo». Entrambe le proposizioni sono vere, quindi l’intera implicazione è vera. Un altro esempio può essere l’implicazione «se 42 è un numero naturale, allora è negativo». Questa implicazione non è vera, perché da una cosa vera cerchiamo di dedurne una che non lo è.

Infine restano i casi in cui la prima proposizione è falsa. In tal caso la verità della seconda non ci interessa più. Se partiamo da una falsità, possiamo poi dire ciò che vogliamo. Sono frasi come «se 1 è un numero negativo, allora i maiali volano» oppure «se Roma è una famosa impresa edile, allora il sole è azzurro». In questi casi l’implicazione è automaticamente vera, semplicemente perché parte da una falsità. Tavola:

$$\begin{array}{ccc}p& q& p\Rightarrow q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 0& 1\end{array}$$

Valore di verità dell’equivalenza

L’equivalenza si scrive p ⇔ q e si legge «p se e solo se q». Un esempio di equivalenza può essere «il numero x è divisibile per due se e solo se è pari». Quando sarà vera tutta la frase?

Nell’equivalenza ci aspettiamo che le due proposizioni siano in una tale simbiosi che o valgono entrambe o non vale nessuna. Quindi o il numero x è pari e allo stesso tempo divisibile per due, oppure non è né l’uno né l’altro. Non può verificarsi il caso in cui x sia pari ma non sia divisibile per due.

Esempio: «Luca legge un libro se e solo se è seduto sul water.» Perché l’equivalenza sia soddisfatta, ogni volta che Luca è seduto sul water deve leggere un libro. E allo stesso tempo, ogni volta che legge un libro, deve essere seduto sul water. Non può succedere che legga il libro, per esempio, a letto.

L’equivalenza si può esprimere mediante due implicazioni. Quindi p ⇔ q potremmo riscriverla come p ⇒ q e allo stesso tempo q ⇒ p. Tavola:

$$\begin{array}{ccc}p& q& p\iff q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}$$

Negazione

La negazione è un’operazione unaria; la scriviamo con un apice, p', oppure con questo simbolo: ¬p. La negazione nega l’affermazione originale. Se abbiamo la proposizione «Sofia è una cantante», la sua negazione è la proposizione «Non è vero che Sofia è una cantante» o, in breve, «Sofia non è una cantante». Quasi sempre possiamo formare la negazione mettendo davanti alla proposizione «Non è vero che…»

La negazione inverte il valore di verità, cioè da 0 fa 1 e da 1 fa 0. Possiamo quindi scrivere ¬0 = 1 e ¬1 = 0.

Attenzione ad alcune trappole. Prendiamo l’affermazione «la calce è bianca». Qual è la sua negazione? Qualcuno potrebbe pensare che sia «la calce è nera», ma non è vero! Se usiamo la regola precedente, la negazione sarà la proposizione «non è vero che la calce è bianca». Significa necessariamente che deve essere nera? No, può essere, per esempio, rosa pallido.

Tavola di tutti i connettivi

$$\begin{array}{cccccc}p& q& p\wedge q& p\vee q& p\Rightarrow q& p\iff q\\ 1& 1& 1& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\end{array}$$

Valore di verità di una formula completa

Ormai sappiamo valutare il valore di verità di due proposizioni unite da un connettivo logico. La formula intera la valutiamo in modo del tutto analogo. Se abbiamo la formula (p ⇒ q) ∧ r, nel momento in cui valutiamo la formula (p ⇒ q), per esempio, come 1, otteniamo la classica congiunzione 1 ∧ r, che sappiamo già risolvere.

Applicando via via i connettivi più semplici arriviamo al valore di verità finale dell’intera formula. Spesso a questo scopo si usa la cosiddetta tavola di verità, descritta più avanti.

Tavola di verità

La tavola di verità si usa per valutare formule più complesse. Nelle prime n colonne scriviamo le n variabili proposizionali con cui lavora la formula e nelle colonne successive collochiamo via via le sottoformule che la formula contiene. Con un esempio sarà più chiaro:

Prendiamo la formula (p ∨ q) ∧ (q ⇒ p). All’inizio scriviamo nella tabella tutte le variabili proposizionali, cioè p e q, e tutte le combinazioni delle loro assegnazioni:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Poi aggiungiamo le colonne per le singole sottoformule p ∨ q e q ⇒ p.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Ora valutiamo queste formule e completiamo le colonne con zeri o uni. Nella tabella abbiamo tutte le informazioni necessarie. Procediamo così: quando valutiamo p ∨ q nella prima riga, al posto di p sostituiamo 1 e al posto di q pure 1. Otteniamo così l’espressione 1 ∨ 1. Il risultato di questa espressione è di nuovo 1, quindi nella tabella scriviamo un uno:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

In questo modo completiamo via via tutta la tabella:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}$$

Ora resta da valutare l’intera formula. Chiamiamola, per esempio, φ = (p ∨ q) ∧ (q ⇒ p). Aggiungiamo alla tabella una colonna con φ e la valutiamo, usando ormai per questo le due colonne precedenti.

$$\begin{array}{ccccc}p& q& p\vee q& q\Rightarrow p& \phi \\ 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}$$

La tabella è ormai completa e ci dà il valore di verità della formula in tutte le assegnazioni possibili. Per esempio, se e(p) = 1 e allo stesso tempo e(q) = 1, la formula è vera. Nel caso in cui e(p) = 0 e e(q) = 1, la formula non è vera.

Osserva che non possiamo dire che «la formula è vera». Questa frase non ha senso, perché per poter dire che la formula è vera, dovremmo dire in quale assegnazione la formula è vera. Possiamo quindi dire che «la formula φ è vera nell’assegnazione e₁ e non è vera nell’assegnazione e₂».

L’unico caso in cui potremmo dire che una formula è vera è se è vera in tutte le assegnazioni possibili. Per esempio la formula p ∨ ¬p è vera in tutte le assegnazioni, quindi possiamo dire che la formula è vera. Allo stesso modo nel caso in cui una formula sia falsa in tutte le assegnazioni.

Tali formule hanno poi una denominazione speciale. Una formula che è vera in tutte le assegnazioni si chiama tautologia. Una formula che non è soddisfatta in nessuna assegnazione si chiama contraddizione.