La logica proposizionale (o logica degli enunciati) costituisce il livello fondamentale della logica matematica e fornisce l'apparato formale per l'analisi rigorosa del ragionamento deduttivo. Essa studia le proposizioni, ossia gli enunciati dichiarativi cui può essere associato in modo univoco un valore di verità, e le loro combinazioni mediante connettivi logici.
In questa trattazione presentiamo un'esposizione sistematica e completa: linguaggio formale, sintassi, semantica vero-funzionale, equivalenze e leggi fondamentali, tautologie e conseguenza logica, forme normali, sistemi deduttivi e i teoremi metalogici di correttezza e completezza.
Indice
- Proposizioni e Linguaggio Formale
- Sintassi delle Formule Ben Formate
- Semantica e Interpretazioni
- Connettivi Logici e Completezza Funzionale
- Tavole di Verità
- Equivalenze Logiche
- Leggi Fondamentali
- Tautologie, Soddisfacibilità e Conseguenza Logica
- Forme Normali (CNF e DNF)
- Sistemi Deduttivi
- Correttezza e Completezza
- Esempi Avanzati
Proposizioni e Linguaggio Formale
Una proposizione (o enunciato) è una frase dichiarativa di senso compiuto che, in base al principio di bivalenza, assume in modo univoco uno e uno solo dei due valori di verità: vero (\(V\) o \(1\)) o falso (\(F\) o \(0\)).
Una proposizione si dice atomica (o enunciato semplice) se non contiene al suo interno altre proposizioni connesse mediante operatori logici. Le proposizioni che si ottengono combinando proposizioni atomiche tramite connettivi logici si dicono composte (o molecolari).
Si fissa un insieme numerabile di variabili proposizionali, indicate generalmente con lettere latine minuscole:
\[ \mathcal{P} = \{p_1, p_2, p_3, \dots\} = \{p, q, r, \dots\} \]
Il linguaggio della logica proposizionale \(\mathcal{L}\) è composto dai seguenti simboli:
- le variabili proposizionali di \(\mathcal{P}\);
- i connettivi logici: \(\neg,\ \land,\ \lor,\ \rightarrow,\ \leftrightarrow\);
- i simboli ausiliari: parentesi tonde \((,\ )\).
Sintassi delle Formule Ben Formate
L'insieme \(\mathcal{F}\) delle formule ben formate (fbf) è il più piccolo insieme di stringhe sull'alfabeto di \(\mathcal{L}\) definito induttivamente dalle seguenti clausole:
- Clausola base: ogni variabile proposizionale \(p \in \mathcal{P}\) è una fbf;
- Clausole induttive:
- se \(A \in \mathcal{F}\), allora \((\neg A) \in \mathcal{F}\);
- se \(A, B \in \mathcal{F}\), allora \((A \land B),\ (A \lor B),\ (A \rightarrow B),\ (A \leftrightarrow B) \in \mathcal{F}\);
- Clausola di chiusura: nessun'altra stringa è una fbf.
In notazione BNF la grammatica del linguaggio si scrive:
\[ A ::= p \mid (\neg A) \mid (A \land A) \mid (A \lor A) \mid (A \rightarrow A) \mid (A \leftrightarrow A) \]
Per convenzione di precedenza, ai connettivi si attribuisce il seguente ordine decrescente di legame, che permette di omettere parentesi senza ambiguità:
\[ \neg \;>\; \land \;>\; \lor \;>\; \rightarrow \;>\; \leftrightarrow \]
Avvertenza. Mentre la precedenza di \(\neg\) su tutti gli altri connettivi e quella di \(\rightarrow,\ \leftrightarrow\) come meno leganti sono universalmente accettate, l'ordine relativo tra \(\land\) e \(\lor\) non è uniforme nella letteratura: alcuni autori (per analogia con \(\cdot\) e \(+\) nell'algebra di Boole) attribuiscono a \(\land\) priorità superiore rispetto a \(\lor\), mentre altri (per esempio Mendelson) li considerano allo stesso livello e richiedono parentesi esplicite. È perciò buona prassi, in caso di possibile ambiguità, esplicitare le parentesi tra \(\land\) e \(\lor\): si scriva, ad esempio, \( (A \land B) \lor C \) anziché \( A \land B \lor C \).
Il principio di induzione strutturale sulle fbf afferma che, per dimostrare una proprietà \(P\) per ogni \(A \in \mathcal{F}\), è sufficiente verificare:
- (base) \(P\) vale per ogni proposizione atomica;
- (passo) \(P\) si conserva mediante l'applicazione di ciascun connettivo.
Semantica e Interpretazioni
La semantica della logica proposizionale è vero-funzionale: il valore di verità di una formula composta è univocamente determinato dai valori di verità delle sue sottoformule.
Un'interpretazione (o valutazione, o assegnamento) è una funzione:
\[ v : \mathcal{P} \to \{V, F\} \]
che si estende in modo unico a una funzione \(\hat{v} : \mathcal{F} \to \{V, F\}\) mediante le seguenti clausole ricorsive:
- \( \hat{v}(\neg A) = V \iff \hat{v}(A) = F \);
- \( \hat{v}(A \land B) = V \iff \hat{v}(A) = V \text{ e } \hat{v}(B) = V \);
- \( \hat{v}(A \lor B) = V \iff \hat{v}(A) = V \text{ oppure } \hat{v}(B) = V \) (eventualmente entrambi);
- \( \hat{v}(A \rightarrow B) = F \iff \hat{v}(A) = V \text{ e } \hat{v}(B) = F \);
- \( \hat{v}(A \leftrightarrow B) = V \iff \hat{v}(A) = \hat{v}(B) \).
Se una formula contiene \(n\) variabili proposizionali distinte, le interpretazioni possibili (ristrette a tali variabili) sono \(2^n\).
Osservazione importante. Il connettivo \(\lor\) rappresenta la disgiunzione inclusiva (corrispondente al vel latino): \(A \lor B\) è vera quando è vera almeno una delle due proposizioni, incluso il caso in cui siano entrambe vere. Va distinta dalla disgiunzione esclusiva (corrispondente all'aut latino, denotata \(\oplus\) o XOR), in cui \(A \oplus B\) è vera se e solo se \(A\) e \(B\) hanno valori di verità diversi. In simboli:
\[ A \oplus B \;\equiv\; (A \lor B) \land \neg(A \land B) \;\equiv\; \neg(A \leftrightarrow B) \]
Nel linguaggio naturale italiano la congiunzione "o" è ambigua tra i due significati; la logica formale rimuove tale ambiguità adottando per default la lettura inclusiva.
Connettivi Logici e Completezza Funzionale
I connettivi logici sono operatori vero-funzionali, ossia funzioni \(\{V,F\}^n \to \{V,F\}\):
- la negazione \(\neg\) è un operatore unario;
- la congiunzione \(\land\), la disgiunzione \(\lor\), l'implicazione \(\rightarrow\) e la doppia implicazione (o bicondizionale) \(\leftrightarrow\) sono operatori binari.
Un insieme di connettivi si dice funzionalmente completo se ogni funzione di verità \(\{V,F\}^n \to \{V,F\}\) può essere espressa mediante combinazioni di tali connettivi. Sono insiemi funzionalmente completi:
\[ \{\neg, \land, \lor\}, \quad \{\neg, \land\}, \quad \{\neg, \lor\}, \quad \{\neg, \rightarrow\} \]
Inoltre, esistono singoli connettivi binari sufficienti da soli per esprimere ogni funzione di verità: la NAND di Sheffer, denotata \(\uparrow\), e la NOR di Peirce, denotata \(\downarrow\).
Le definizioni semantiche giustificano le seguenti riduzioni, che mostrano come \(\rightarrow\) e \(\leftrightarrow\) siano definibili a partire da \(\{\neg, \land, \lor\}\):
\[ A \rightarrow B \equiv \neg A \lor B \]
\[ A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A) \equiv (A \land B) \lor (\neg A \land \neg B) \]
Tavole di Verità
Una tavola di verità è la rappresentazione tabellare della funzione vero-funzionale associata a una formula. Per una formula contenente \(n\) variabili distinte, la tavola ha \(2^n\) righe, una per ciascuna interpretazione possibile.
Le tavole di verità dei connettivi fondamentali sono:
| \(A\) | \(B\) | \(\neg A\) | \(A \land B\) | \(A \lor B\) | \(A \rightarrow B\) | \(A \leftrightarrow B\) |
|---|---|---|---|---|---|---|
| V | V | F | V | V | V | V |
| V | F | F | F | V | F | F |
| F | V | V | F | V | V | F |
| F | F | V | F | F | V | V |
Si osservi che l'implicazione \(A \rightarrow B\) è falsa esclusivamente nel caso in cui l'antecedente \(A\) sia vero e il conseguente \(B\) sia falso: questa è la sola riga in cui essa assume valore \(F\).
Equivalenze Logiche
Due formule \(A\) e \(B\) si dicono logicamente equivalenti, e si scrive \(A \equiv B\), se assumono lo stesso valore di verità in ogni interpretazione:
\[ A \equiv B \iff \forall v,\ \hat{v}(A) = \hat{v}(B) \]
L'equivalenza \(\equiv\) è una relazione di equivalenza sull'insieme \(\mathcal{F}\) (riflessiva, simmetrica, transitiva) ed è una congruenza: vale il teorema di sostituzione, secondo cui se \(A \equiv B\) e \(C[A]\) è una formula contenente \(A\) come sottoformula, allora \(C[A] \equiv C[B]\), dove \(C[B]\) è la formula ottenuta sostituendo (un'occorrenza di) \(A\) con \(B\) in \(C\).
È fondamentale distinguere \(\equiv\) (relazione metalinguistica fra formule) e \(\leftrightarrow\) (connettivo del linguaggio): vale infatti
\[ A \equiv B \iff \models A \leftrightarrow B \]
cioè \(A\) e \(B\) sono logicamente equivalenti se e solo se la formula \(A \leftrightarrow B\) è una tautologia.
Leggi Fondamentali
Le seguenti equivalenze, dimostrabili tramite tavole di verità, costituiscono le leggi fondamentali del calcolo proposizionale (con \(\top\) si indica una tautologia, con \(\bot\) una contraddizione):
- Idempotenza: \(A \land A \equiv A\), \(\quad A \lor A \equiv A\)
- Commutatività: \(A \land B \equiv B \land A\), \(\quad A \lor B \equiv B \lor A\)
- Associatività: \((A \land B) \land C \equiv A \land (B \land C)\), e analogamente per \(\lor\)
- Distributività: \(A \land (B \lor C) \equiv (A \land B) \lor (A \land C)\), \(\quad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\)
- Doppia negazione: \(\neg \neg A \equiv A\)
- Leggi di De Morgan: \(\neg(A \land B) \equiv \neg A \lor \neg B\), \(\quad \neg(A \lor B) \equiv \neg A \land \neg B\)
- Assorbimento: \(A \land (A \lor B) \equiv A\), \(\quad A \lor (A \land B) \equiv A\)
- Identità: \(A \land \top \equiv A\), \(\quad A \lor \bot \equiv A\)
- Dominazione: \(A \lor \top \equiv \top\), \(\quad A \land \bot \equiv \bot\)
- Terzo escluso: \(A \lor \neg A \equiv \top\)
- Non contraddizione: \(A \land \neg A \equiv \bot\)
- Contrapposizione: \(A \rightarrow B \equiv \neg B \rightarrow \neg A\)
- Esportazione: \((A \land B) \rightarrow C \equiv A \rightarrow (B \rightarrow C)\)
Tautologie, Soddisfacibilità e Conseguenza Logica
Sia \(A \in \mathcal{F}\). Si dice che:
- \(A\) è una tautologia (o formula logicamente valida), e si scrive \(\models A\), se \(\hat{v}(A) = V\) per ogni interpretazione \(v\);
- \(A\) è una contraddizione (o formula insoddisfacibile) se \(\hat{v}(A) = F\) per ogni \(v\);
- \(A\) è soddisfacibile se esiste almeno un'interpretazione \(v\) tale che \(\hat{v}(A) = V\);
- \(A\) è contingente se è soddisfacibile ma non è una tautologia.
Le quattro categorie sono legate da:
\[ A \text{ è tautologia} \iff \neg A \text{ è contraddizione} \]
Sia \(\Gamma \subseteq \mathcal{F}\) un insieme di formule (eventualmente infinito) e \(B \in \mathcal{F}\). Si dice che \(B\) è conseguenza logica (semantica) di \(\Gamma\), e si scrive
\[ \Gamma \models B \]
se per ogni interpretazione \(v\) tale che \(\hat{v}(A) = V\) per ogni \(A \in \Gamma\), si ha \(\hat{v}(B) = V\). In altri termini: ogni modello di \(\Gamma\) è anche un modello di \(B\).
Teorema di deduzione semantica:
\[ \Gamma \cup \{A\} \models B \iff \Gamma \models A \rightarrow B \]
In particolare, ponendo \(\Gamma = \emptyset\), si ha \(A \models B\) se e solo se \(\models A \rightarrow B\).
Forme Normali (CNF e DNF)
Si chiama letterale una variabile proposizionale o la sua negazione: \(p\) o \(\neg p\). Conseguentemente:
- una clausola disgiuntiva è una disgiunzione di letterali: \(\ell_1 \lor \ell_2 \lor \dots \lor \ell_k\);
- una clausola congiuntiva è una congiunzione di letterali: \(\ell_1 \land \ell_2 \land \dots \land \ell_k\).
Una formula è in:
- Forma Normale Congiuntiva (CNF) se è una congiunzione di clausole disgiuntive;
- Forma Normale Disgiuntiva (DNF) se è una disgiunzione di clausole congiuntive.
Teorema (esistenza delle forme normali): ogni formula \(A \in \mathcal{F}\) è logicamente equivalente a una formula in CNF e a una formula in DNF.
Procedura di riduzione:
- eliminare il bicondizionale: \(A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A)\);
- eliminare l'implicazione: \(A \rightarrow B \equiv \neg A \lor B\);
- portare le negazioni davanti alle sole variabili (leggi di De Morgan e doppia negazione), ottenendo la forma normale negativa (NNF);
- applicare la distributività per ottenere la forma desiderata: \(\lor\) su \(\land\) per la DNF, \(\land\) su \(\lor\) per la CNF.
Esempio:
\[ A \rightarrow (B \lor C) \;\equiv\; \neg A \lor (B \lor C) \;\equiv\; \neg A \lor B \lor C \]
che risulta simultaneamente in CNF (un'unica clausola disgiuntiva) e in DNF (disgiunzione di clausole congiuntive ridotte a singoli letterali).
Sistemi Deduttivi
Un sistema deduttivo (o calcolo logico) è un apparato puramente sintattico costituito da assiomi e regole di inferenza, che permette di derivare formule a partire da premesse senza fare riferimento alla semantica. La nozione fondamentale è quella di derivabilità: si scrive
\[ \Gamma \vdash A \]
per indicare che esiste una derivazione della formula \(A\) a partire dalle premesse \(\Gamma\) nel sistema considerato.
I sistemi deduttivi più diffusi per la logica proposizionale sono:
- Sistemi assiomatici (alla Hilbert-Frege): pochi schemi assiomatici e una sola regola (modus ponens);
- Deduzione naturale (Gentzen, Prawitz): regole di introduzione ed eliminazione per ciascun connettivo;
- Calcolo dei sequenti (Gentzen): regole su sequenti della forma \(\Gamma \Rightarrow \Delta\);
- Tableaux semantici (Beth, Smullyan): metodo di refutazione mediante alberi.
Le regole di inferenza più importanti sono:
Modus Ponens (eliminazione di \(\rightarrow\)):
\[ \dfrac{A \qquad A \rightarrow B}{B} \]
Modus Tollens (contropositiva):
\[ \dfrac{A \rightarrow B \qquad \neg B}{\neg A} \]
Sillogismo ipotetico (transitività dell'implicazione):
\[ \dfrac{A \rightarrow B \qquad B \rightarrow C}{A \rightarrow C} \]
Sillogismo disgiuntivo:
\[ \dfrac{A \lor B \qquad \neg A}{B} \]
Introduzione ed eliminazione della congiunzione:
\[ \dfrac{A \qquad B}{A \land B} \qquad\qquad \dfrac{A \land B}{A} \qquad\qquad \dfrac{A \land B}{B} \]
Reductio ad absurdum (dimostrazione per assurdo):
\[ \dfrac{\Gamma, \neg A \vdash \bot}{\Gamma \vdash A} \]
Correttezza e Completezza
La relazione fra deducibilità sintattica \(\vdash\) e conseguenza semantica \(\models\) è espressa dai due teoremi metalogici fondamentali della logica proposizionale.
Teorema di correttezza (soundness): per ogni \(\Gamma \subseteq \mathcal{F}\) e ogni \(A \in \mathcal{F}\):
\[ \Gamma \vdash A \;\Longrightarrow\; \Gamma \models A \]
Tutto ciò che è derivabile sintatticamente è effettivamente conseguenza semantica delle premesse.
Teorema di completezza (Post, 1921): per ogni \(\Gamma \subseteq \mathcal{F}\) e ogni \(A \in \mathcal{F}\):
\[ \Gamma \models A \;\Longrightarrow\; \Gamma \vdash A \]
Ogni conseguenza semantica può essere effettivamente derivata nel calcolo.
Combinando i due risultati si ottiene l'equivalenza fra sintassi e semantica:
\[ \Gamma \vdash A \iff \Gamma \models A \]
A questi si affiancano altri due risultati metalogici di rilievo:
- Teorema di compattezza: \(\Gamma\) è soddisfacibile se e solo se ogni suo sottoinsieme finito lo è;
- Decidibilità: esiste un algoritmo (per esempio, il metodo delle tavole di verità) che, in tempo finito, stabilisce se una data formula sia o meno una tautologia.
Esempi Avanzati
Esempio 1 — Riduzione in forma normale
Si riduca \( (A \rightarrow B) \land \neg B \) in CNF e DNF.
Risultato
CNF: \( (\neg A \lor B) \land \neg B \) — DNF: \( \neg A \land \neg B \)
Svolgimento
Eliminiamo l'implicazione mediante \( A \rightarrow B \equiv \neg A \lor B \):
\[ (A \rightarrow B) \land \neg B \;\equiv\; (\neg A \lor B) \land \neg B \]
che è già in CNF (congiunzione di due clausole disgiuntive). Per ottenere la DNF applichiamo la distributività di \(\land\) rispetto a \(\lor\):
\[ (\neg A \lor B) \land \neg B \;\equiv\; (\neg A \land \neg B) \lor (B \land \neg B) \;\equiv\; \neg A \land \neg B \]
poiché \( B \land \neg B \equiv \bot \) per la legge di non contraddizione. Il risultato \( \neg A \land \neg B \) è una DNF degenere: si tratta infatti di un'unica clausola congiuntiva, interpretabile come disgiunzione di un solo addendo. Per convenzione, una singola clausola congiuntiva è considerata in DNF (così come una singola clausola disgiuntiva è in CNF), pur non comparendo esplicitamente alcun \(\lor\).
Esempio 2 — Verifica di tautologia (sillogismo ipotetico)
Si dimostri che \( ((A \rightarrow B) \land (B \rightarrow C)) \rightarrow (A \rightarrow C) \) è una tautologia.
Svolgimento
Procediamo per assurdo: supponiamo esista un'interpretazione \(v\) che renda falsa la formula. Affinché un'implicazione sia falsa, l'antecedente deve essere vero e il conseguente falso, da cui:
- \( \hat{v}((A \rightarrow B) \land (B \rightarrow C)) = V \), quindi \( \hat{v}(A \rightarrow B) = V \) e \( \hat{v}(B \rightarrow C) = V \);
- \( \hat{v}(A \rightarrow C) = F \), da cui \( \hat{v}(A) = V \) e \( \hat{v}(C) = F \).
Da \( \hat{v}(A) = V \) e \( \hat{v}(A \rightarrow B) = V \) segue \( \hat{v}(B) = V \) (poiché altrimenti l'implicazione sarebbe falsa). Da \( \hat{v}(B) = V \) e \( \hat{v}(B \rightarrow C) = V \) segue \( \hat{v}(C) = V \), in contraddizione con \( \hat{v}(C) = F \). Pertanto la formula è una tautologia.
Esempio 3 — Conseguenza logica e regola di risoluzione
Si verifichi che \( \{A \lor B,\ \neg A \lor C\} \models B \lor C \).
Svolgimento
Sia \(v\) un'interpretazione che soddisfa entrambe le premesse. Distinguiamo due casi sul valore di \( \hat{v}(A) \):
- se \( \hat{v}(A) = V \), allora da \( \hat{v}(\neg A \lor C) = V \) segue necessariamente \( \hat{v}(C) = V \), e dunque \( \hat{v}(B \lor C) = V \);
- se \( \hat{v}(A) = F \), allora da \( \hat{v}(A \lor B) = V \) segue \( \hat{v}(B) = V \), e dunque \( \hat{v}(B \lor C) = V \).
In entrambi i casi \( \hat{v}(B \lor C) = V \), il che prova la conseguenza logica. Questo principio costituisce la regola di risoluzione, alla base dei metodi automatici di dimostrazione: dalle clausole \( A \lor B \) e \( \neg A \lor C \) si deduce il risolvente \( B \lor C \).
La logica proposizionale rappresenta il primo livello di formalizzazione del ragionamento matematico. Pur con la sua limitata espressività — incapace di descrivere la struttura interna delle proposizioni — essa fornisce gli strumenti concettuali fondamentali per affrontare la logica del primo ordine, le teorie assiomatiche, la metalogica e le strutture algebriche associate (algebre di Boole, reticoli). La sua padronanza è prerequisito imprescindibile per ogni studio rigoroso della matematica e dell'informatica teorica.