Esercizi sulla logica proposizionale

In questo articolo vediamo alcune formule e le loro possibili assegnazioni di valori di verità, usando il metodo della tavola di verità.

Primo esercizio

Cerchiamo di capire quando questa formula è vera: ϕ = (p ∧ q) ∨ ¬q. Scriviamo nella tavola le variabili proposizionali p e q:

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

Poi aggiungiamo alla tavola la prima parte della formula, (p ∧ q), la negazione ¬q e infine l’intera formula:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Ora calcoliamo i valori della terza colonna, cioè una semplice congiunzione, e anche quelli della negazione: qui basta scrivere i valori opposti a quelli della seconda colonna:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Infine calcoliamo i valori dell’ultima colonna, che corrisponde all’intera formula. Nella nostra tavola si tratta quindi di calcolare la disgiunzione «tra la terza e la quarta colonna». Risultato:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Secondo esercizio

Stessa consegna, formula diversa: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Vediamo che nella formula compaiono le variabili proposizionali p e q e le loro negazioni. Per prima cosa costruiamo quindi una tavola con le due variabili e le loro negazioni:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Poi aggiungiamo le formule p ∧ ¬q e ¬p ⇒ q, che ora sappiamo valutare facilmente, perché nella tavola abbiamo sia i valori delle singole proposizioni sia quelli delle loro negazioni. La tavola si presenta così:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Per ultima ci resta da valutare l’intera formula, che è un’equivalenza tra le ultime due colonne:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Terzo esercizio

Il terzo esercizio è un po’ più complicato: proviamo con tre variabili proposizionali, per cui il calcolo della tavola diventa più laborioso. La formula è la seguente: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Poiché ci sono tre variabili proposizionali, il numero totale delle possibili assegnazioni di valori è otto:

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

Da qui in poi procediamo come nel caso precedente: valutiamo ogni colonna in tutte e otto le righe. L’intera tavola si presenta così:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Quarto esercizio

Questo esercizio non è dato come una semplice formula, ma come un problema espresso a parole. Tre amici vogliono andare a una festa scatenata, ma non vanno molto d’accordo e pongono delle condizioni per andarci. Si chiamano Marco, Giacomo e Pietro. Le regole sono le seguenti:

1. Se va Marco, va anche Giacomo.
2. Alla festa viene Pietro oppure, se viene Marco, non viene Giacomo.
3. Pietro viene se e solo se non viene Marco o non viene Giacomo.

La domanda è: possono andare tutti alla festa? Se no, chi può andarci senza violare nessuna regola?

Per prima cosa dobbiamo riscrivere le affermazioni a parole usando variabili proposizionali e formule. Indichiamo quindi le variabili proposizionali con M, G e P (Marco, Giacomo, Pietro); ognuna indicherà una proposizione del tipo «Marco va alla festa». La prima regola si può scrivere così: M ⇒ G — «se M, allora G», cioè «se Marco va alla festa, allora Giacomo va alla festa».

La seconda regola la scriviamo così. La regola comincia con la frase «Alla festa viene Pietro oppure…», quindi ci servirà evidentemente una disgiunzione. Per ora scriviamo: P ∨ … La parte successiva della frase dice: «se viene Marco, non viene Giacomo». Questa è un’implicazione, in cui a destra dobbiamo usare anche una negazione. «Non viene Giacomo» = ¬G. L’intera implicazione si scrive così: M ⇒ ¬G. La colleghiamo alla disgiunzione precedente: P ∨ (M ⇒ ¬G).

La terza regola la riscriviamo così: partiamo da «Pietro viene se e solo se». Questo indica un’equivalenza: P ⇔ … Poi abbiamo «non viene Marco o non viene Giacomo», che scriviamo così: ¬M ∨ ¬G. Mettendo tutto insieme: (P ⇔ (¬M ∨ ¬G)).

Ora inseriamo tutte le formule nella tavola e calcoliamo i valori:

$$\begin{array}{cccccc}M& G& P& (M\Rightarrow G)& (P\vee (M\Rightarrow \mathrm{\neg }G))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }G))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

La domanda era se tutti e tre i ragazzi possono andare alla festa. La risposta si trova nella prima riga, che corrisponde al caso in cui vanno tutti: lo indicano i tre 1 nelle prime tre colonne. Sono soddisfatte tutte le condizioni? La prima sì (quarta colonna), anche la seconda (quinta colonna), ma l’ultima no (ultima colonna), dove c’è uno zero. Questo significa che, se vanno tutti e tre, la terza condizione non è soddisfatta.

Cerchiamo quindi le righe in cui nelle posizioni che rappresentano le condizioni (cioè nelle ultime tre colonne) ci sono solo 1. Un 1 significa che la condizione è soddisfatta. Vediamo che ciò accade in due casi: quando vanno Giacomo e Pietro ma non Marco, e quando va solo Pietro.

Puoi calcolarlo anche aggiungendo alla tavola la formula ϕ, che sarà la congiunzione delle tre condizioni. Avremo quindi: ϕ = ((M ⇒ G) ∧ (P ∨ (M ⇒ ¬G)) ∧ (P ⇔ (¬M ∨ ¬G))). Questa formula esprime ciò che vogliamo: che tutte le formule (tutte le condizioni) siano soddisfatte. La tavola si presenta quindi così:

$$\begin{array}{ccccccc}M& G& P& (M\Rightarrow G)& (P\vee (M\Rightarrow \mathrm{\neg }G))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }G))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Altri esercizi sul metodo della tavola di verità

Dato che ho scritto un programma che costruisce automaticamente l’intera tavola a partire da una formula, devo sfruttarlo a dovere, e quindi seguono ancora alcune formule svolte:

Formula: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Tavola:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Formula: (a ∨ ¬a) ⇔ (b ∧ ¬b). Tavola:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Formula: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Tavola:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Formula: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Tavola:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Formula: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Tavola:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$