Logica proposizionale e dimostrazioni: esercizi con soluzioni passo passo
Detto anche: logica proposizionale · tavole di verità
Esercizi gratuiti su Logica proposizionale e dimostrazioni con schemi, suggerimenti e soluzioni svolte complete. Valori nuovi ogni volta, su tre livelli: tabelle di verità, equivalenze e metodi di dimostrazione, quantificatori e argomenti.
Esercizio gratuitoFacile
Completa la tabella di verità (1 = vero, 0 = falso). In quante righe N è vera (p → r) ↔ (r ∨ q)?
(p → r) ↔ (r ∨ q)
Risposta esatta: un numero intero, senza arrotondamenti.
Impara Logica proposizionale e dimostrazioni da zero
1Enunciati e connettivi
Una proposizione è un enunciato che è vero o falso, come “7 è primo”. Si indica con una lettera, p o q, e il suo valore di verità con 1 (vero) o 0 (falso).
I connettivi costruiscono formule più grandi a partire da formule più piccole:
¬p (non p) inverte il valore.
p ∧ q (e) vale 1 solo quando entrambi valgono 1.
p ∨ q (o) vale 0 solo quando entrambi valgono 0. È l’o inclusivo: possono essere veri entrambi.
p → q (se p allora q) vale 0 solo quando p = 1 e q = 0.
p ↔ q (se e solo se) vale 1 quando p e q hanno lo stesso valore.
L’implicazione sorprende molti studenti: quando p è falsa, p → q è vera qualunque sia q. Una promessa “se piove, prendo l’ombrello” si infrange solo in un giorno di pioggia senza ombrello.
Autoverifica p = 0 e q = 1. Quanto vale p → q?
0
1
Dipende dal contesto
Non definito
Risposta: 1. Un’implicazione è falsa solo quando la condizione è vera e la conclusione fallisce (p = 1, q = 0). Con p = 0 è vera, qualunque sia q.
2Tabelle di verità
Una tabella di verità elenca ogni combinazione dei valori di verità delle variabili. Con n variabili distinte ci sono 2ⁿ righe: 4 per due variabili, 8 per tre, 16 per quattro. Una variabile che compare due volte conta comunque una sola volta.
Procedi dall’interno verso l’esterno. Dai a ogni sottoformula una colonna propria, così ogni nuova colonna richiede un solo connettivo applicato a colonne che hai già.
Elenca le variabili e scrivi tutte le 2ⁿ combinazioni, partendo da tutti 1.
Aggiungi una colonna per ogni sottoformula, partendo dalla più interna.
Compila ogni colonna con la regola del suo connettivo principale.
Leggi la risposta nell’ultima colonna: conta gli 1 o trova la riga richiesta.
Autoverifica Quante righe ha la tabella di verità di (p ∧ q) → (r ∨ p)?
16
4
6
8
Risposta: 8. La formula ha tre variabili distinte, p, q e r, quindi 2³ = 8 righe. p compare due volte ma è una sola variabile; 16 sarebbe 2⁴ per quattro occorrenze.
3Un esempio svolto
Segui ogni passaggio. Prova a prevedere il successivo prima di aprirlo.
Esempio svolto
In quante righe della sua tabella di verità (p → q) ∧ ¬q è vera?
1
Variabili e righe
Due variabili, p e q, quindi 4 righe: (1, 1), (1, 0), (0, 1), (0, 0).
2
Colonna p → q
Vale 0 solo nella riga p = 1, q = 0:
p → q: 1, 0, 1, 1
3
Colonna ¬q
¬q: 0, 1, 0, 1
4
La congiunzione
Entrambe le colonne devono valere 1. Succede solo nell’ultima riga, p = 0 e q = 0.
(p → q) ∧ ¬q: 0, 0, 0, 1
Risposta
La formula è vera in 1 riga, quella con p = 0, q = 0. Per questo p → q e ¬q insieme danno ¬p (modus tollens).
4Equivalenze e metodi di dimostrazione
Due formule sono equivalenti (≡) quando le loro colonne nella tabella di verità sono identiche. Una tautologia vale 1 in ogni riga, una contraddizione vale 0 in ogni riga, e una contingenza non è né l’una né l’altra.
Le leggi che userai più spesso:
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Queste leggi sono la base dei metodi di dimostrazione. Una dimostrazione per contrapposizione di p → q dimostra invece ¬q → ¬p, che è equivalente. Una dimostrazione per assurdo assume p ∧ ¬q, l’unico modo in cui l’implicazione può fallire, e ne deriva qualcosa di impossibile.
Attenzione: l’inversa q → p e la contraria ¬p → ¬q non sono equivalenti a p → q.
Autoverifica Quale formula è equivalente a ¬(p ∧ q)?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Risposta: ¬p ∨ ¬q. Per De Morgan l’∧ diventa ∨ e le due parti vengono negate. ¬p ∧ ¬q è la negazione di p ∨ q, un enunciato diverso: è falsa quando esattamente una tra p e q è vera, mentre ¬(p ∧ q) è vera.
5Quantificatori e argomenti validi
Con variabili su un dominio, ∀x P(x) dice “P vale per ogni x” e ∃x P(x) dice “P vale per almeno un x”. Una negazione scambia il quantificatore:
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Sposta la negazione verso l’interno un passo alla volta; all’interno usa le leggi proposizionali. Per esempio ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): “non ogni P è un Q” significa “qualche P non è un Q”.
Un argomento è valido quando la conclusione vale 1 in ogni riga in cui tutte le premesse valgono 1. Le forme valide classiche sono il modus ponens (p → q, p, quindi q), il modus tollens (p → q, ¬q, quindi ¬p) e il sillogismo ipotetico (p → q, q → r, quindi p → r).
Una riga con tutte le premesse a 1 e la conclusione a 0 è un controesempio. Affermare il conseguente (p → q, q, quindi p) non è valido: la riga p = 0, q = 1 è un controesempio.
Autoverifica Qual è la negazione di “tutti gli studenti sono stati promossi”, ∀x P(x)?
¬P(x) per un solo studente x fissato
∀x ¬P(x): nessuno studente è stato promosso
∃x P(x): qualche studente è stato promosso
∃x ¬P(x): qualche studente non è stato promosso
Risposta: ∃x ¬P(x): qualche studente non è stato promosso. Basta uno studente bocciato per rendere falso “tutti gli studenti sono stati promossi”. “Nessuno studente è stato promosso” è molto più forte della negazione.
6Errori comuni
Considerare p → q falsa quando p è falsa. È falsa solo quando p = 1 e q = 0.
Contare due volte una variabile ripetuta quando si calcola il numero di righe.
Confondere la contronominale ¬q → ¬p con l’inversa q → p o con la contraria ¬p → ¬q.
Negare ∀x P(x) come ∀x ¬P(x): il quantificatore deve cambiare in ∃.
Scrivere ¬(p ∧ q) come ¬p ∧ ¬q: De Morgan scambia anche il connettivo.
Autoverifica Quale enunciato è la contronominale di “se n² è pari, allora n è pari”?
Se n è dispari, allora n² è dispari
Se n è pari, allora n² è pari
Se n² è dispari, allora n è dispari
n² è pari e n è dispari
Risposta: Se n è dispari, allora n² è dispari. Scambia le due parti e negale entrambe: non (n pari) → non (n² pari). “Se n è pari, allora n² è pari” è l’inversa; l’ultima opzione è ciò che assume una dimostrazione per assurdo.
7Come sono fatte le domande d’esame
Facile: tabelle di verità. Trovi il numero di righe, conti le righe in cui una formula è vera o clicchi l’unica riga che rende vera o falsa una formula.
Medio: equivalenze e metodi di dimostrazione. Decidi se una formula è una tautologia, una contraddizione o una contingenza, scegli la formula equivalente o l’enunciato da dimostrare in una dimostrazione per contrapposizione o per assurdo.
Difficile: quantificatori e argomenti. Neghi enunciati quantificati, scegli la conclusione che segue dalle premesse, clicchi la riga del controesempio di un argomento non valido o conti le righe vere in una tabella a quattro variabili.
Esattamente una riga della tabella di verità rende falsa ¬(p ∨ q) → q. Clicca quella riga.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
Mostra i suggerimenti
a → b vale 0 solo quando a = 1 e b = 0. ¬a inverte il valore. a ∨ b vale 0 solo quando entrambi valgono 0.
Ricava prima il connettivo principale: come devono essere i suoi due lati perché l’intera formula sia 0?
Dai a ogni parte una colonna propria: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Mostra la risposta e la spiegazione
Tabelle di verità: una formula con n variabili distinte ha 2ⁿ righe, una per ogni combinazione di valori di verità (1 = vero, 0 = falso). Procedi dall’interno verso l’esterno e dai a ogni sottoformula una colonna propria. ¬a inverte il valore; a ∧ b vale 1 solo quando entrambi valgono 1; a ∨ b vale 0 solo quando entrambi valgono 0; a → b vale 0 solo quando a = 1 e b = 0; a ↔ b vale 1 quando i due lati sono uguali.
Quale formula è logicamente equivalente a (b ∧ c) → a? Clicca su di essa.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
Mostra i suggerimenti
Le formule equivalenti coincidono in ogni riga della tabella di verità. Una riga in cui differiscono esclude un’opzione.
Prova una riga in cui (b ∧ c) → a vale 0 e controlla quali opzioni valgono 0 anche lì.
Esportazione: (a ∧ b) → c ≡ a → (b → c). Entrambe valgono 0 solo quando a = 1, b = 1 e c = 0.
Mostra la risposta e la spiegazione
Equivalenza logica: due formule sono equivalenti (≡) quando hanno lo stesso valore in ogni riga della tabella di verità. Una tautologia vale 1 in ogni riga, una contraddizione vale 0 in ogni riga, e una contingenza non è né l’una né l’altra. Leggi utili: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b e ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contronominale); ¬(a → b) ≡ a ∧ ¬b; e le leggi distributive, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
La legge
Esportazione: (a ∧ b) → c ≡ a → (b → c). Entrambe valgono 0 solo quando a = 1, b = 1 e c = 0.
(b ∧ c) → a ≡ b → (c → a)
Verifica con la tabella di verità
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Risposta
b → (c → a)
Le colonne dopo la barra sono le opzioni nell’ordine mostrato.
Esempio 3Difficile
Sono date le premesse (q ∧ p) → r; q; ¬r. Quale conclusione ne segue? Clicca su di essa.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
Mostra i suggerimenti
Una conclusione segue quando vale 1 in ogni riga in cui tutte le premesse valgono 1.
Trova le righe in cui tutte le premesse valgono 1, poi verifica ogni opzione in quelle righe.
Questa è una regola standard: modus tollens con una congiunzione.
Mostra la risposta e la spiegazione
Quantificatori e argomenti: ¬∀x P(x) ≡ ∃x ¬P(x) e ¬∃x P(x) ≡ ∀x ¬P(x). Sposta una negazione verso l’interno, scambia ogni quantificatore che attraversa e nega la formula interna con le leggi proposizionali, come ¬(a → b) ≡ a ∧ ¬b. Un argomento è valido quando la conclusione vale 1 in ogni riga in cui tutte le premesse valgono 1. Una sola riga con premesse vere e conclusione falsa è un controesempio e mostra che l’argomento non è valido.
Righe con tutte le premesse vere
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Conclusione
¬p (modus tollens con una congiunzione)
Risposta
¬p
Domande e risposte
Logica proposizionale e dimostrazioni: di cosa si tratta?
Una proposizione è un enunciato che è vero o falso, come “7 è primo”. Si indica con una lettera, p o q, e il suo valore di verità con 1 (vero) o 0 (falso).
I connettivi costruiscono formule più grandi a partire da formule più piccole:
Logica proposizionale e dimostrazioni: come si risolvono gli esercizi passo per passo?
Conta le variabili distinte: la tabella di verità ha 2ⁿ righe, e la prima ha tutti i valori a 1.
Assegna a ogni sottoformula una colonna propria e compila le colonne dall’interno verso l’esterno.
Applica la regola di ogni connettivo: → vale 0 solo per 1 → 0, ↔ vale 1 quando i due lati coincidono.
Per le equivalenze, confronta riga per riga le colonne finali; per un argomento, guarda solo le righe in cui ogni premessa vale 1.
Per negare un enunciato quantificato, sposta ¬ verso l’interno, scambia ∀ e ∃ e nega la formula interna.
Logica proposizionale e dimostrazioni: quali sono gli errori più comuni?
Considerare p → q falsa quando p è falsa.
Contare due volte una variabile ripetuta quando si calcola il numero di righe.
Confondere la contronominale ¬q → ¬p con l’inversa q → p.
Negare ∀x P(x) come ∀x ¬P(x) invece che come ∃x ¬P(x).
Applicare De Morgan senza scambiare ∧ e ∨.
Logica proposizionale e dimostrazioni: che cosa si esercita?
Facile: tabelle di verità
Media: equivalenze e metodi di dimostrazione
Difficile: quantificatori e argomenti
Ogni esercizio ha valori nuovi, così impari il metodo invece di una risposta. Bloccato? Apri prima un piccolo suggerimento e la spiegazione completa solo quando ti serve.
Come funziona l’esercitazione
Ogni esercizio ha valori nuovi, così impari il metodo invece di una risposta.
Bloccato? Apri prima un piccolo suggerimento e la spiegazione completa solo quando ti serve.
I tuoi progressi, i tuoi errori e gli esercizi salvati restano memorizzati, così puoi ripassare prima dell’esame.