La logica proposizionale è alla base del ragionamento formale in informatica: condizioni negli if, query, circuiti digitali, verifica di programmi. È semplice, a patto di partire dalle definizioni e non dall'intuizione del linguaggio parlato, che spesso inganna.
Che cos'è una proposizione
Una proposizione è un enunciato che può essere vero o falso, ma non entrambe le cose. «7 è un numero primo» è una proposizione (vera). «Il file è più grande di 2 MB» è una proposizione, una volta fissato il file. «Chiudi la porta» non lo è: è un ordine, non ha valore di verità.
Le proposizioni elementari si indicano con lettere: p, q, r. Combinandole con i connettivi si ottengono proposizioni composte, il cui valore dipende solo dai valori delle componenti.
I connettivi fondamentali
| Connettivo | Simbolo | Si legge | Vero quando |
|---|---|---|---|
| Negazione | ¬p | non p | p è falso |
| Congiunzione | p ∧ q | p e q | entrambi veri |
| Disgiunzione | p ∨ q | p o q | almeno uno vero |
| Implicazione | p → q | se p allora q | tranne quando p è vero e q falso |
| Doppia implicazione | p ↔ q | p se e solo se q | p e q hanno lo stesso valore |
Due punti meritano attenzione.
La «o» logica è inclusiva
Nel linguaggio comune «vuoi tè o caffè?» suggerisce una scelta esclusiva. In logica, p ∨ q è vera anche quando p e q sono entrambe vere. Se serve l'esclusiva si usa un connettivo distinto, lo XOR (p ⊕ q), vero quando esattamente una delle due è vera.
L'implicazione con premessa falsa è vera
p → q è falsa in un solo caso: p vera e q falsa. Se la premessa è falsa, l'implicazione è vera qualunque sia q. Sembra strano, ma pensate a una promessa: «se piove, ti presto l'ombrello». Se non piove, non ho mancato alla promessa, qualunque cosa io faccia. Questa convenzione, chiamata implicazione materiale, è ciò che rende coerente l'intero sistema.
Costruire una tavola di verità
Una tavola di verità elenca tutte le combinazioni di valori delle variabili e, per ciascuna, il valore della formula. Con n variabili le righe sono 2ⁿ: 4 righe con due variabili, 8 con tre, 16 con quattro.
Un metodo ordinato per non dimenticare righe:
- Scrivete le variabili in colonna da sinistra a destra.
- Nella colonna più a destra alternate V e F una riga sì e una no; in quella precedente a coppie; in quella ancora prima a gruppi di quattro, e così via. È lo stesso schema del conteggio in binario.
- Aggiungete una colonna per ogni sottoformula, dalla più interna alla più esterna.
- Calcolate ogni colonna usando solo le colonne già compilate.
Esempio con la formula (p → q) ∧ ¬q:
| p | q | p → q | ¬q | (p → q) ∧ ¬q |
|---|---|---|---|---|
| V | V | V | F | F |
| V | F | F | V | F |
| F | V | V | F | F |
| F | F | V | V | V |
La formula è vera solo quando p e q sono entrambe false. Notate che, ogni volta che la formula è vera, anche ¬p è vera: è la base della regola di inferenza chiamata modus tollens.
Tautologie, contraddizioni, formule soddisfacibili
Guardando l'ultima colonna di una tavola si classifica una formula:
- Tautologia: vera in ogni riga. Esempio: p ∨ ¬p.
- Contraddizione: falsa in ogni riga. Esempio: p ∧ ¬p.
- Soddisfacibile: vera in almeno una riga. La formula dell'esempio precedente è soddisfacibile ma non tautologica.
Due formule sono logicamente equivalenti quando hanno la stessa colonna finale. Per esempio p → q è equivalente a ¬p ∨ q, e questa equivalenza è utilissima per semplificare condizioni nel codice.
Precedenza dei connettivi
Per evitare parentesi ovunque si adotta di solito questa precedenza, dalla più forte alla più debole: ¬, ∧, ∨, →, ↔. Quindi ¬p ∧ q ∨ r si legge ((¬p) ∧ q) ∨ r. L'implicazione, per convenzione, associa a destra: p → q → r significa p → (q → r). Quando scrivo condizioni complesse, nel mio lavoro preferisco comunque mettere le parentesi: costano poco e tolgono ogni dubbio a chi legge.
Dove serve in pratica
- Programmazione: semplificare una condizione con molti
&&e||, verificare che due versioni di un controllo siano equivalenti, scrivere test che coprano tutte le combinazioni. - Database: le clausole WHERE sono formule logiche; capire la negazione evita filtri che escludono righe per errore.
- Circuiti: ogni porta logica realizza un connettivo; una tavola di verità è letteralmente la specifica di un circuito combinatorio.
Il limite della tavola di verità è la crescita esponenziale: con 20 variabili le righe sono più di un milione. Per formule grandi si usano trasformazioni algebriche e SAT solver.
In sintesi
- Una proposizione è un enunciato vero o falso; i connettivi le combinano guardando solo i valori di verità.
- La disgiunzione è inclusiva e l'implicazione con premessa falsa è sempre vera.
- Con n variabili una tavola di verità ha 2ⁿ righe: compilatela con lo schema del conteggio binario.
- Tautologie, contraddizioni ed equivalenze si riconoscono confrontando le colonne finali.
- Le stesse regole governano condizioni nel codice, query e circuiti.
