Una raccolta progressiva di 20 esercizi svolti sulla logica proposizionale, pensata per imparare a riconoscere proposizioni, formalizzare enunciati, costruire tavole di verità e usare correttamente i principali connettivi logici.
Ogni esercizio è svolto passo dopo passo, con attenzione al significato delle formule e non soltanto al risultato finale. L'obiettivo è imparare a ragionare in modo rigoroso sul valore di verità degli enunciati e sulle relazioni logiche tra proposizioni.
Ricordiamo che una proposizione è un enunciato dichiarativo al quale è possibile attribuire, in modo non ambiguo, uno e un solo valore di verità:
\[ V \quad \text{oppure} \quad F \]
I connettivi principali della logica proposizionale sono:
\[ \neg,\quad \land,\quad \lor,\quad \rightarrow,\quad \leftrightarrow \]
Essi permettono di costruire proposizioni composte a partire da proposizioni più semplici.
Esercizio 1 — livello ★☆☆☆☆
Stabilisci quali tra i seguenti enunciati sono proposizioni:
\[ \text{a) } 7>3 \]
\[ \text{b) } \text{Chiudi la porta.} \]
\[ \text{c) } 5+2=10 \]
\[ \text{d) } x+1=4 \]
Soluzione
Gli enunciati a) e c) sono proposizioni. Gli enunciati b) e d) non sono proposizioni.
Svolgimento
Per stabilire se un enunciato è una proposizione dobbiamo chiederci se esso possiede un valore di verità ben determinato, cioè se è vero oppure falso.
Consideriamo il primo enunciato:
\[ 7>3 \]
Questo enunciato è dichiarativo e possiamo stabilire chiaramente che è vero. Dunque è una proposizione.
Consideriamo ora:
\[ \text{Chiudi la porta.} \]
Questo non è un enunciato dichiarativo, ma un comando. Non ha senso dire che sia vero o falso. Quindi non è una proposizione.
Il terzo enunciato è:
\[ 5+2=10 \]
Si tratta di un enunciato dichiarativo. Possiamo stabilire che è falso, perché:
\[ 5+2=7 \]
Anche un enunciato falso può essere una proposizione: ciò che conta è che abbia un valore di verità determinato.
Infine consideriamo:
\[ x+1=4 \]
Questo enunciato contiene una variabile libera, \(x\). Senza specificare il valore di \(x\), non possiamo stabilire se sia vero o falso.
Per esempio, se \(x=3\), l'enunciato è vero; se \(x=0\), l'enunciato è falso.
Quindi, così com'è scritto, non è una proposizione.
Riassumendo:
\[ \text{a) proposizione vera} \]
\[ \text{b) non proposizione} \]
\[ \text{c) proposizione falsa} \]
\[ \text{d) non proposizione} \]
Esercizio 2 — livello ★☆☆☆☆
Stabilisci se le seguenti proposizioni sono atomiche oppure composte:
\[ \text{a) } 4 \text{ è pari} \]
\[ \text{b) } 4 \text{ è pari e } 5 \text{ è dispari} \]
\[ \text{c) } \text{Non piove} \]
\[ \text{d) } \text{Se studio, allora supero l'esame} \]
Soluzione
a) atomica; b) composta; c) composta; d) composta.
Svolgimento
Una proposizione è atomica quando non contiene connettivi logici e non è ottenuta combinando proposizioni più semplici.
Una proposizione è invece composta quando contiene almeno un connettivo logico, esplicito o implicito.
Consideriamo:
\[ 4 \text{ è pari} \]
Questa proposizione non è costruita combinando altre proposizioni. È quindi atomica.
Consideriamo ora:
\[ 4 \text{ è pari e } 5 \text{ è dispari} \]
Qui compaiono due proposizioni:
\[ 4 \text{ è pari} \]
e:
\[ 5 \text{ è dispari} \]
unite dalla parola “e”, che corrisponde al connettivo logico di congiunzione:
\[ \land \]
Quindi la proposizione è composta.
La proposizione:
\[ \text{Non piove} \]
contiene una negazione. Se indichiamo con \(p\) la proposizione “piove”, allora “non piove” si scrive:
\[ \neg p \]
Dunque è composta.
Infine:
\[ \text{Se studio, allora supero l'esame} \]
contiene un'implicazione logica. Se poniamo:
\[ p = \text{studio} \]
e:
\[ q = \text{supero l'esame} \]
allora la proposizione si rappresenta come:
\[ p \rightarrow q \]
Quindi è composta.
Esercizio 3 — livello ★☆☆☆☆
Traduci in simboli logici la seguente proposizione:
“Marco studia e Laura legge.”
Usa:
\[ p = \text{Marco studia} \]
\[ q = \text{Laura legge} \]
Soluzione
\[ p \land q \]
Svolgimento
La proposizione contiene due enunciati semplici.
Il primo è:
\[ \text{Marco studia} \]
che viene indicato con:
\[ p \]
Il secondo è:
\[ \text{Laura legge} \]
che viene indicato con:
\[ q \]
La parola “e” indica che le due proposizioni devono essere vere contemporaneamente.
In logica proposizionale questo corrisponde alla congiunzione:
\[ \land \]
Pertanto la proposizione:
“Marco studia e Laura legge”
si traduce in:
\[ p \land q \]
Esercizio 4 — livello ★☆☆☆☆
Traduci in simboli logici la seguente proposizione:
“Se piove, allora resto a casa.”
Usa:
\[ p = \text{piove} \]
\[ q = \text{resto a casa} \]
Soluzione
\[ p \rightarrow q \]
Svolgimento
La frase contiene una struttura condizionale:
“Se ..., allora ...”
In logica proposizionale questa struttura viene rappresentata mediante l'implicazione:
\[ \rightarrow \]
L'antecedente è la proposizione che segue la parola “se”:
\[ p = \text{piove} \]
Il conseguente è la proposizione che segue “allora”:
\[ q = \text{resto a casa} \]
Quindi la proposizione:
“Se piove, allora resto a casa”
si traduce in:
\[ p \rightarrow q \]
È importante notare che \(p\rightarrow q\) non significa che \(p\) e \(q\) siano entrambi veri, ma che la verità di \(p\) obbliga alla verità di \(q\).
Esercizio 5 — livello ★★☆☆☆
Traduci in linguaggio naturale la formula:
\[ \neg p \lor q \]
sapendo che:
\[ p = \text{studio} \]
\[ q = \text{supero l'esame} \]
Soluzione
“Non studio oppure supero l'esame.”
Svolgimento
La formula è:
\[ \neg p \lor q \]
Analizziamo i simboli uno alla volta.
La proposizione \(p\) significa:
\[ \text{studio} \]
Quindi:
\[ \neg p \]
significa:
\[ \text{non studio} \]
La proposizione \(q\) significa:
\[ \text{supero l'esame} \]
Il connettivo:
\[ \lor \]
rappresenta la disgiunzione inclusiva, cioè “oppure”.
Perciò:
\[ \neg p \lor q \]
si legge:
“Non studio oppure supero l'esame.”
In logica, questa disgiunzione è vera anche nel caso in cui entrambe le proposizioni siano vere, cioè nel caso in cui sia vero che non studio e sia vero che supero l'esame.
Esercizio 6 — livello ★★☆☆☆
Costruisci la tavola di verità della formula:
\[ p \land q \]
Soluzione
| \(p\) | \(q\) | \(p \land q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
Svolgimento
La formula contiene due variabili proposizionali:
\[ p \qquad \text{e} \qquad q \]
Una tavola di verità con due variabili deve contenere:
\[ 2^2=4 \]
possibili interpretazioni.
Il connettivo:
\[ \land \]
rappresenta la congiunzione logica.
La congiunzione è vera soltanto quando entrambe le proposizioni sono vere contemporaneamente.
Analizziamo le quattro righe.
Nella prima riga:
\[ p=V \qquad q=V \]
entrambe le proposizioni sono vere, quindi:
\[ p\land q = V \]
Nella seconda riga:
\[ p=V \qquad q=F \]
una delle due proposizioni è falsa. Di conseguenza la congiunzione è falsa:
\[ p\land q = F \]
Lo stesso accade nella terza riga:
\[ p=F \qquad q=V \]
perché non entrambe le proposizioni sono vere.
Infine, nell'ultima riga:
\[ p=F \qquad q=F \]
entrambe sono false, quindi anche la congiunzione è falsa.
Concludiamo dunque che:
\[ p\land q \]
è vera esclusivamente nel caso:
\[ p=V \qquad q=V \]
Esercizio 7 — livello ★★☆☆☆
Costruisci la tavola di verità della formula:
\[ p \lor q \]
Soluzione
| \(p\) | \(q\) | \(p \lor q\) |
|---|---|---|
| V | V | V |
| V | F | V |
| F | V | V |
| F | F | F |
Svolgimento
Il simbolo:
\[ \lor \]
rappresenta la disgiunzione logica inclusiva.
La disgiunzione è vera quando almeno una delle due proposizioni è vera.
Anche in questo caso, poiché le variabili sono due, dobbiamo considerare:
\[ 2^2=4 \]
possibili interpretazioni.
Nella prima riga:
\[ p=V \qquad q=V \]
entrambe le proposizioni sono vere. Quindi:
\[ p\lor q = V \]
Nella seconda riga:
\[ p=V \qquad q=F \]
almeno una delle due proposizioni è vera, dunque:
\[ p\lor q = V \]
Nella terza riga:
\[ p=F \qquad q=V \]
anche qui almeno una delle due proposizioni è vera. Pertanto:
\[ p\lor q = V \]
Solo nell'ultima riga:
\[ p=F \qquad q=F \]
entrambe le proposizioni risultano false.
Di conseguenza:
\[ p\lor q = F \]
Concludiamo quindi che la disgiunzione inclusiva è falsa soltanto quando entrambe le proposizioni sono false.
Esercizio 8 — livello ★★☆☆☆
Costruisci la tavola di verità della formula:
\[ p \rightarrow q \]
Soluzione
| \(p\) | \(q\) | \(p \rightarrow q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
Svolgimento
L'implicazione:
\[ p\rightarrow q \]
si legge:
“se \(p\), allora \(q\)”.
Questo connettivo è spesso il più delicato da interpretare correttamente.
L'implicazione è falsa esclusivamente nel caso in cui:
\[ p=V \]
e contemporaneamente:
\[ q=F \]
Infatti, in questo caso l'antecedente è vero ma il conseguente risulta falso, quindi la promessa logica contenuta nell'implicazione viene violata.
Analizziamo le quattro possibilità.
Prima riga:
\[ p=V \qquad q=V \]
L'implicazione è vera.
Seconda riga:
\[ p=V \qquad q=F \]
Questo è l'unico caso in cui l'implicazione è falsa:
\[ p\rightarrow q = F \]
Terza riga:
\[ p=F \qquad q=V \]
L'implicazione è considerata vera.
Infatti, quando l'antecedente è falso, l'implicazione non viene violata.
Quarta riga:
\[ p=F \qquad q=F \]
Anche qui l'implicazione è vera, sempre perché l'antecedente è falso.
Concludiamo dunque che:
\[ p\rightarrow q \]
è falsa soltanto quando:
\[ p=V \qquad \text{e} \qquad q=F \]
Esercizio 9 — livello ★★★☆☆
Determina il valore di verità della formula:
\[ (p\land q)\rightarrow r \]
nell'interpretazione:
\[ p=V,\qquad q=F,\qquad r=F \]
Soluzione
La formula è vera.
Svolgimento
Consideriamo la formula:
\[ (p\land q)\rightarrow r \]
Per valutare correttamente la formula dobbiamo procedere dall'interno verso l'esterno.
La sottoformula più interna è:
\[ p\land q \]
Sostituiamo i valori assegnati:
\[ p=V,\qquad q=F \]
Otteniamo:
\[ V\land F \]
Una congiunzione è vera soltanto se entrambe le proposizioni sono vere.
Poiché una delle due è falsa, segue:
\[ p\land q = F \]
La formula iniziale diventa quindi:
\[ F\rightarrow F \]
Ricordiamo che un'implicazione è falsa soltanto quando l'antecedente è vero e il conseguente è falso.
Qui invece l'antecedente è falso.
Pertanto:
\[ F\rightarrow F = V \]
Concludiamo quindi che la formula è vera.
Esercizio 10 — livello ★★★☆☆
Verifica mediante tavola di verità che:
\[ \neg(p\land q)\equiv \neg p \lor \neg q \]
Soluzione
Le due formule hanno gli stessi valori di verità in ogni interpretazione, quindi sono logicamente equivalenti.
Svolgimento
Per dimostrare che due formule sono logicamente equivalenti dobbiamo verificare che assumano sempre lo stesso valore di verità.
Costruiamo quindi una tavola di verità completa.
| \(p\) | \(q\) | \(p\land q\) | \(\neg(p\land q)\) | \(\neg p\) | \(\neg q\) | \(\neg p\lor \neg q\) |
|---|---|---|---|---|---|---|
| V | V | V | F | F | F | F |
| V | F | F | V | F | V | V |
| F | V | F | V | V | F | V |
| F | F | F | V | V | V | V |
Osserviamo ora le ultime due colonne:
\[ \neg(p\land q) \]
e:
\[ \neg p\lor\neg q \]
Esse coincidono in tutte le righe della tavola.
Di conseguenza:
\[ \neg(p\land q)\equiv \neg p\lor\neg q \]
Questa equivalenza prende il nome di prima legge di De Morgan.
Esercizio 11 — livello ★★★☆☆
Verifica mediante tavola di verità che:
\[ p\rightarrow q \equiv \neg p \lor q \]
Soluzione
Le due formule hanno gli stessi valori di verità in ogni interpretazione, quindi sono logicamente equivalenti.
Svolgimento
Vogliamo confrontare le due formule:
\[ p\rightarrow q \]
e:
\[ \neg p \lor q \]
Due formule sono logicamente equivalenti se assumono lo stesso valore di verità in tutte le possibili interpretazioni.
Poiché compaiono due variabili proposizionali, \(p\) e \(q\), dobbiamo considerare:
\[ 2^2=4 \]
interpretazioni.
| \(p\) | \(q\) | \(p\rightarrow q\) | \(\neg p\) | \(\neg p\lor q\) |
|---|---|---|---|---|
| V | V | V | F | V |
| V | F | F | F | F |
| F | V | V | V | V |
| F | F | V | V | V |
Confrontiamo ora la colonna di \(p\rightarrow q\) con la colonna di \(\neg p\lor q\).
I valori sono gli stessi in ogni riga:
\[ V,\ F,\ V,\ V \]
Quindi le due formule sono logicamente equivalenti:
\[ p\rightarrow q \equiv \neg p \lor q \]
Questa equivalenza è molto importante perché permette di eliminare l'implicazione e riscriverla usando soltanto negazione e disgiunzione.
Esercizio 12 — livello ★★★☆☆
Stabilisci se la formula:
\[ p\lor\neg p \]
è una tautologia, una contraddizione oppure una formula contingente.
Soluzione
La formula è una tautologia.
Svolgimento
Una formula è una tautologia se è vera in ogni interpretazione.
Una formula è una contraddizione se è falsa in ogni interpretazione.
Una formula è contingente se è vera in alcune interpretazioni e falsa in altre.
Consideriamo:
\[ p\lor\neg p \]
La formula contiene una sola variabile proposizionale, quindi dobbiamo considerare:
\[ 2^1=2 \]
interpretazioni.
| \(p\) | \(\neg p\) | \(p\lor\neg p\) |
|---|---|---|
| V | F | V |
| F | V | V |
Nella prima riga \(p\) è vera e quindi la disgiunzione è vera.
Nella seconda riga \(p\) è falsa, ma \(\neg p\) è vera; quindi anche in questo caso la disgiunzione è vera.
La formula risulta vera in tutte le interpretazioni.
Pertanto:
\[ p\lor\neg p \]
è una tautologia.
Questa tautologia prende il nome di principio del terzo escluso.
Esercizio 13 — livello ★★★☆☆
Stabilisci se la formula:
\[ p\land\neg p \]
è una tautologia, una contraddizione oppure una formula contingente.
Soluzione
La formula è una contraddizione.
Svolgimento
Consideriamo la formula:
\[ p\land\neg p \]
Essa afferma contemporaneamente \(p\) e la sua negazione.
Costruiamo la tavola di verità.
| \(p\) | \(\neg p\) | \(p\land\neg p\) |
|---|---|---|
| V | F | F |
| F | V | F |
Nella prima riga \(p\) è vera, ma \(\neg p\) è falsa. La congiunzione è quindi falsa.
Nella seconda riga \(p\) è falsa, mentre \(\neg p\) è vera. Anche in questo caso la congiunzione è falsa.
La formula risulta falsa in ogni interpretazione.
Pertanto:
\[ p\land\neg p \]
è una contraddizione.
Questa legge prende il nome di principio di non contraddizione.
Esercizio 14 — livello ★★★★☆
Stabilisci se la formula:
\[ p\rightarrow(p\lor q) \]
è una tautologia, una contraddizione oppure una formula contingente.
Soluzione
La formula è una tautologia.
Svolgimento
Per classificare la formula dobbiamo costruire la sua tavola di verità completa.
La formula è:
\[ p\rightarrow(p\lor q) \]
La sottoformula interna da calcolare è:
\[ p\lor q \]
Costruiamo la tavola:
| \(p\) | \(q\) | \(p\lor q\) | \(p\rightarrow(p\lor q)\) |
|---|---|---|---|
| V | V | V | V |
| V | F | V | V |
| F | V | V | V |
| F | F | F | V |
Analizziamo la colonna finale.
Essa contiene soltanto valori veri:
\[ V,\ V,\ V,\ V \]
Quindi la formula è vera in ogni interpretazione.
Pertanto:
\[ p\rightarrow(p\lor q) \]
è una tautologia.
Dal punto di vista intuitivo, se \(p\) è vera, allora è certamente vera anche la disgiunzione \(p\lor q\), perché una disgiunzione inclusiva è vera quando almeno una delle sue componenti è vera.
Esercizio 15 — livello ★★★★☆
Stabilisci se la formula:
\[ (p\land q)\rightarrow p \]
è una tautologia, una contraddizione oppure una formula contingente.
Soluzione
La formula è una tautologia.
Svolgimento
La formula da analizzare è:
\[ (p\land q)\rightarrow p \]
Essa contiene una congiunzione nel primo membro dell'implicazione. Prima di valutare l'implicazione, dobbiamo quindi calcolare:
\[ p\land q \]
Costruiamo la tavola di verità completa:
| \(p\) | \(q\) | \(p\land q\) | \((p\land q)\rightarrow p\) |
|---|---|---|---|
| V | V | V | V |
| V | F | F | V |
| F | V | F | V |
| F | F | F | V |
Osserviamo la colonna finale:
\[ V,\ V,\ V,\ V \]
La formula è vera in tutte le interpretazioni.
Quindi:
\[ (p\land q)\rightarrow p \]
è una tautologia.
Il significato logico è semplice: se sono vere contemporaneamente \(p\) e \(q\), allora in particolare è vera \(p\).
Esercizio 16 — livello ★★★★☆
Verifica se:
\[ p\land q \models p \]
Soluzione
Sì, \(p\) è conseguenza logica di \(p\land q\).
Svolgimento
Scrivere:
\[ p\land q \models p \]
significa affermare che ogni interpretazione che rende vera la premessa \(p\land q\) rende vera anche la conclusione \(p\).
Dobbiamo quindi considerare le interpretazioni in cui:
\[ p\land q \]
è vera.
Una congiunzione è vera soltanto quando entrambi i suoi membri sono veri. Dunque:
\[ p\land q = V \quad \Longleftrightarrow \quad p=V \ \text{e}\ q=V \]
In ogni interpretazione in cui \(p\land q\) è vera, risulta necessariamente:
\[ p=V \]
Quindi non esiste alcuna interpretazione in cui la premessa sia vera e la conclusione sia falsa.
Pertanto:
\[ p\land q \models p \]
Esercizio 17 — livello ★★★★☆
Verifica se:
\[ p \models p\lor q \]
Soluzione
Sì, \(p\lor q\) è conseguenza logica di \(p\).
Svolgimento
La scrittura:
\[ p \models p\lor q \]
significa che ogni interpretazione che rende vera la premessa \(p\) deve rendere vera anche la conclusione \(p\lor q\).
Supponiamo quindi che la premessa sia vera:
\[ p=V \]
La conclusione è:
\[ p\lor q \]
Una disgiunzione inclusiva è vera quando almeno una delle due proposizioni è vera.
Poiché \(p\) è già vera, la disgiunzione:
\[ p\lor q \]
è necessariamente vera, indipendentemente dal valore di \(q\).
Infatti:
\[ V\lor V=V \]
e:
\[ V\lor F=V \]
Quindi ogni modello di \(p\) è anche un modello di \(p\lor q\).
Pertanto:
\[ p \models p\lor q \]
Esercizio 18 — livello ★★★★★
Verifica se:
\[ p\rightarrow q,\ p \models q \]
Soluzione
Sì, \(q\) è conseguenza logica delle premesse \(p\rightarrow q\) e \(p\).
Svolgimento
La scrittura:
\[ p\rightarrow q,\ p \models q \]
significa che ogni interpretazione che rende vere entrambe le premesse deve rendere vera anche la conclusione.
Le premesse sono:
\[ p\rightarrow q \]
e:
\[ p \]
Supponiamo dunque che entrambe siano vere.
Dalla seconda premessa sappiamo che:
\[ p=V \]
Inoltre, la prima premessa afferma che:
\[ p\rightarrow q=V \]
Ricordiamo che un'implicazione con antecedente vero è vera soltanto se anche il conseguente è vero.
Poiché l'antecedente \(p\) è vero, per mantenere vera l'implicazione deve necessariamente essere:
\[ q=V \]
Quindi ogni interpretazione che rende vere le premesse rende vera anche la conclusione.
Pertanto:
\[ p\rightarrow q,\ p \models q \]
Questa è la forma semantica del modus ponens.
Esercizio 19 — livello ★★★★★
Riduci la formula seguente usando le equivalenze logiche:
\[ \neg(p\rightarrow q) \]
Soluzione
\[ \neg(p\rightarrow q)\equiv p\land\neg q \]
Svolgimento
Partiamo dalla formula:
\[ \neg(p\rightarrow q) \]
Per semplificarla, eliminiamo innanzitutto l'implicazione.
Ricordiamo l'equivalenza fondamentale:
\[ p\rightarrow q \equiv \neg p\lor q \]
Sostituendo otteniamo:
\[ \neg(p\rightarrow q)\equiv \neg(\neg p\lor q) \]
Ora applichiamo la legge di De Morgan:
\[ \neg(A\lor B)\equiv \neg A\land\neg B \]
Nel nostro caso:
\[ A=\neg p \qquad \text{e} \qquad B=q \]
Quindi:
\[ \neg(\neg p\lor q)\equiv \neg\neg p\land\neg q \]
Infine usiamo la doppia negazione:
\[ \neg\neg p\equiv p \]
Otteniamo:
\[ \neg(p\rightarrow q)\equiv p\land\neg q \]
Il risultato è coerente anche con il significato dell'implicazione: \(p\rightarrow q\) è falsa soltanto quando \(p\) è vera e \(q\) è falsa.
Esercizio 20 — livello ★★★★★
Trasforma la formula:
\[ p\rightarrow(q\lor r) \]
in una formula equivalente senza il connettivo \(\rightarrow\).
Soluzione
\[ p\rightarrow(q\lor r)\equiv \neg p\lor q\lor r \]
Svolgimento
La formula di partenza è:
\[ p\rightarrow(q\lor r) \]
Vogliamo eliminare il connettivo di implicazione.
Usiamo l'equivalenza:
\[ A\rightarrow B\equiv \neg A\lor B \]
Nel nostro caso:
\[ A=p \]
e:
\[ B=q\lor r \]
Applicando l'equivalenza otteniamo:
\[ p\rightarrow(q\lor r)\equiv \neg p\lor(q\lor r) \]
Per associatività della disgiunzione, possiamo omettere le parentesi:
\[ \neg p\lor(q\lor r)\equiv \neg p\lor q\lor r \]
Quindi la formula equivalente senza implicazione è:
\[ \neg p\lor q\lor r \]
Questa formula è una clausola disgiuntiva, cioè una disgiunzione di letterali, e può essere vista anche come una forma normale congiuntiva composta da una sola clausola.