La logica proposizionale tratta enunciati già completi, veri o falsi. Ma molte affermazioni interessanti parlano di «tutti» o di «qualcuno»: tutti i server hanno una patch, qualche utente ha una password debole, per ogni richiesta esiste una risposta. Per esprimerle serve la logica dei predicati, detta anche logica del primo ordine. È lo strumento con cui si scrivono specifiche precise, si ragiona sulle query e si formulano teoremi.
Predicati e dominio
Un predicato è un enunciato con una o più variabili libere, che diventa vero o falso quando le variabili ricevono un valore. P(x) = «x è pari» non è né vero né falso; P(4) è vero, P(7) è falso. Un predicato può avere più argomenti: M(x, y) = «x è maggiore di y».
Ogni variabile spazia su un dominio (o universo del discorso): i numeri interi, gli utenti di un sistema, i file di una cartella. Il dominio va sempre dichiarato, perché lo stesso enunciato può essere vero in un dominio e falso in un altro. «Ogni x ha un predecessore» è vero sugli interi e falso sui naturali, dove 0 non ha predecessore.
I due quantificatori
- Universale ∀x P(x): «per ogni x, P(x)». È vero se P vale per tutti gli elementi del dominio.
- Esistenziale ∃x P(x): «esiste x tale che P(x)». È vero se P vale per almeno un elemento.
Su un dominio finito {a₁, …, aₙ} i quantificatori sono solo abbreviazioni: ∀x P(x) equivale a P(a₁) ∧ … ∧ P(aₙ), mentre ∃x P(x) equivale a P(a₁) ∨ … ∨ P(aₙ). È esattamente ciò che fanno le funzioni all() e any() di Python:
tutti_aggiornati = all(s.patch_applicata for s in server)
qualcuno_debole = any(u.password_debole for u in utenti)
Un dettaglio istruttivo: all([]) restituisce True e any([]) restituisce False. Non è un capriccio del linguaggio: un enunciato universale su un dominio vuoto è vero (non c'è nessun controesempio), uno esistenziale è falso (non c'è nessun testimone).
Negare i quantificatori
Le regole di negazione sono la versione «quantificata» delle leggi di De Morgan:
- ¬∀x P(x) ≡ ∃x ¬P(x)
- ¬∃x P(x) ≡ ∀x ¬P(x)
«Non tutti i backup sono andati a buon fine» significa «esiste almeno un backup fallito», non «tutti i backup sono falliti». «Non esiste un utente senza password» significa «ogni utente ha una password».
Per negare una formula con più quantificatori si scorre da sinistra: ogni ∀ diventa ∃, ogni ∃ diventa ∀, e la negazione arriva fino al predicato. Esempio:
¬∀x ∃y (y > x) ≡ ∃x ∀y ¬(y > x) ≡ ∃x ∀y (y ≤ x)
Cioè: «non è vero che per ogni numero ne esiste uno più grande» equivale a «esiste un numero maggiore o uguale a tutti», ossia un massimo.
L'ordine dei quantificatori conta
Quantificatori dello stesso tipo si possono scambiare: ∀x ∀y equivale a ∀y ∀x. Ma scambiare ∀ ed ∃ cambia il significato. Consideriamo il predicato A(u, c) = «l'utente u conosce la chiave c».
- ∀u ∃c A(u, c): ogni utente conosce almeno una chiave (magari diversa per ciascuno).
- ∃c ∀u A(u, c): esiste una chiave che tutti gli utenti conoscono.
La seconda è molto più forte, e in un contesto di sicurezza descrive una situazione ben diversa: una chiave condivisa da tutti. La seconda implica la prima, ma non viceversa.
Un esempio matematico classico: sugli interi, ∀x ∃y (y > x) è vero (per ogni numero ce n'è uno più grande, basta prendere x + 1), mentre ∃y ∀x (y > x) è falso (non esiste un intero più grande di tutti).
Un trucco per leggere correttamente: in ∀x ∃y, la y può dipendere da x. In ∃y ∀x, la y viene scelta una volta per tutte, prima di conoscere x. Pensatelo come un gioco: chi sceglie per primo e chi risponde.
Quantificatori ristretti
Nella pratica i quantificatori sono quasi sempre ristretti a una parte del dominio. Le forme corrette sono:
- «tutti gli A sono B»: ∀x (A(x) → B(x))
- «qualche A è B»: ∃x (A(x) ∧ B(x))
Lo scambio dei connettivi è un errore frequente. ∀x (A(x) ∧ B(x)) dice che tutto il dominio è sia A sia B, il che è molto diverso. E ∃x (A(x) → B(x)) è quasi sempre vero per ragioni banali: basta un elemento che non sia A, perché l'implicazione con premessa falsa è vera.
Dove si incontra
- SQL:
EXISTSè il quantificatore esistenziale; «tutti» si esprime spesso come «non esiste un controesempio», cioè conNOT EXISTS, applicando proprio la regola di negazione. - Specifiche e test: le proprietà da verificare sono enunciati universali («per ogni input valido, l'output è ordinato»); un test che fallisce è un testimone del quantificatore esistenziale negato.
- Contratti e asserzioni: precondizioni e invarianti si scrivono naturalmente con ∀ ed ∃.
In sintesi
- Un predicato diventa vero o falso solo quando le variabili hanno un valore in un dominio dichiarato.
- ∀ è un AND su tutto il dominio, ∃ un OR; su un dominio vuoto ∀ è vero ed ∃ è falso.
- Negare scambia ∀ con ∃ e porta la negazione fino al predicato.
- Scambiare ∀ ed ∃ cambia il significato: in ∀x ∃y, y può dipendere da x.
- «Tutti gli A sono B» usa →, «qualche A è B» usa ∧.
