Vai al contenuto
Topos Uranos
Italiano

Semantica della logica proposizionale

Riepilogo

Finora le formule sono state stringhe di cerchi e dischi, e le deduzioni, manipolazioni di stringhe: nulla si è detto della loro verità. Questa lezione dà loro un significato. Un’assegnazione attribuisce a ogni variabile uno dei due valori di verità, 11 (vero) e 00 (falso), e si estende a tutte le formule in un unico modo, per ricorsione sulla loro complessità, con una sola clausola: (φ↓ψ)(\varphi \downarrow \psi) vale 11 esattamente quando φ\varphi e ψ\psi valgono 00. Da questa clausola e dalle abbreviazioni ufficiali si calcolano, senza stipulare nient’altro, i valori della negazione, della disgiunzione, della congiunzione, dell’implicazione, della doppia implicazione e della disgiunzione esclusiva. Il lemma di coincidenza, dimostrato per induzione sulla complessità, assicura che il valore di una formula dipende solo dai valori delle sue variabili; ne segue che la tavola di verità, con 2n2^n righe per nn variabili, contiene tutto ciò che le infinite assegnazioni possono dire della formula. Con ciò si definiscono la soddisfazione, la validità, la soddisfacibilità, la contraddizione e la contingenza, si fissano le formule ⊤\top e ⊥\bot, e si pone il problema di decidere la validità, che le tavole risolvono a un costo che cresce esponenzialmente con il numero di variabili.

Obiettivi di apprendimento

  1. Calcolare il valore di verità di una formula sotto un’assegnazione mediante la sua estensione ricorsiva, e dedurre dalle abbreviazioni ufficiali il valore di ogni connettivo derivato.
  2. Dimostrare per induzione sulla complessità il lemma di coincidenza, e spiegare con esso perché una tavola di verità di 2n2^n righe basta per studiare una formula con nn variabili.
  3. Costruire tavole di verità colonna per colonna e classificare formule come valide, contingenti o contraddizioni, e insiemi di formule come soddisfacibili o insoddisfacibili, senza confondere ⊭φ\not\models \varphi con la contraddizione.
  4. Decidere la validità di una formula cercando un’assegnazione che la falsifichi, e stimare il costo del metodo delle tavole in funzione del numero di variabili.

Il significato delle formule

L’unità sul linguaggio ha costruito, nella lezione sul linguaggio della logica proposizionale, un insieme di stringhe di due simboli, e l’unità sulla deduzione ha insegnato a ottenere alcune stringhe da altre con assiomi e regole. Nessuna delle due ha parlato di verità: il sistema deduttivo trasforma simboli secondo la loro forma, come una macchina che non capisce ciò che scrive. Ora, il linguaggio è stato costruito per rappresentare enunciati, e la lezione sulla formalizzazione del linguaggio naturale ha attribuito loro letture informali: (φ↓ψ)(\varphi \downarrow \psi) è vera quando φ\varphi e ψ\psi sono entrambe false, e le letture degli altri connettivi sono state dedotte da questa. La semantica trasforma quelle letture in definizioni matematiche.

Due decisioni la fondano. La prima è la bivalenza: ci sono esattamente due valori di verità, che si scrivono 11 (vero) e 00 (falso), e ogni formula, in ogni situazione, ha uno di essi. La seconda è la vero-funzionalità: il valore di una formula composta dipende solo dai valori dei suoi componenti, non dal suo argomento, così che la verità delle variabili decide quella di tutte le formule. La lezione sulla formalizzazione ha mostrato il prezzo di questa seconda decisione (la causalità, la modalità e il tempo restano fuori); la sua ricompensa è che la semantica di tutto il linguaggio si ottiene da una sola clausola, quella del connettivo primitivo.

Conviene avvertire, inoltre, che questa unità lavora interamente nel metalinguaggio. Le affermazioni «φ\varphi è vera sotto tale assegnazione» o «φ\varphi è una tautologia» non sono formule, ma enunciati matematici sulle formule, e si dimostrano con il ragionamento ordinario, spesso per induzione sulla complessità; non sono deduzioni nel sistema del corso. La relazione tra i due mondi, cioè che tutto ciò che è deducibile è vero e che tutto ciò che è vero nel senso preciso di questa unità è deducibile, è l’oggetto dell’unità sulla metateoria.