Esatto: A⇒B non è una tautologia, e quindi non è un teorema di logica. La domanda posta deriva, probabilmente, dal fatto che siamo abituati a pensare che A⇒B sia la tipica forma di un teorema matematico: questo è sicuramente vero, cioé i teoremi della matematica hanno la struttura logica A⇒B, dove A e B sono proposizioni concernenti oggetti matematici. Ma in questa domanda si fa riferimento ad un altro tipo di teorema, ovvero ai teoremi della logica (proposizionale o predicativa): una formula logica è un teorema se essa è valida dal punto di vista puramente sintattico, e la sua validità prescinde dall'interpretazione; un teorema della logica potrebbe essere, ad esempio, p∨(¬p), ovvero affermare che vale una proposizione p oppure vale il suo contrario; od ancora p⇒p, ovvero affermare che se vale p allora vale p. Ma per dimostrare teoremi bisogna partire da assiomi e applicare delle regole di deduzione: anche la logica delle proposizioni o dei predicati, si può assiomatizzare; si possono scegliere quindi dei simboli primitivi e un set di assiomi, unitamente a delle regole di deduzione logica, e si possono poi costruire tutti i teoremi deducibili dagli assiomi assegnati. Dal punto di vista semantico i teoremi della logica sono tautologie, ovvero sono affermazioni sempre vere, per ogni scelta di valore di verità che noi possiamo attribuire alle proposizioni elementari che costituiscono la formula del teorema. I teoremi della logica sono quindi tautologie; ma è vero il viceversa? In altre parole, è vero che tutte e sole le tautologie sono i teoremi che si possono dimostrare a partire da un certo set di assiomi e usando solo le regole di deduzione logica? La risposta a questa domanda è affermativa, e si tratta di un risultato ottenuto da Gödel nel 1929, noto come teorema di completezza: la logica predicativa del primo ordine è finitamente assiomatizzabile e sintatticamente completa. Dunque possiamo rispondere alla domanda posta dall'autore: p⇒q non è una tautologia dal momento che è falsa se p è vera e q è falsa, di conseguenza non è un teorema di logica.
Questa la spiegazione a parole. Per i più curiosi di sapere qualche dettaglio in più vediamo come si formalizza un'assiomatizzazione della logica, per semplicità ci limitiamo a quella proposizionale. In questo tipo di calcolo le variabili (proposizionali) vengono denotate con le lettere p,q,r,…, mentre le costanti, i connettivi proposizionali sono:
- ¬ (che significa “non”)
- ∨ (che significa “oppure”)
- ∧ (che significa “e”),
- ⇒ (che significa “implica”).
Infine, i segni di interpunzione sono le parentesi tonde (,). Per esprimere col minimo indispensabile tutta la logica proposizionale sono in realtà sufficienti meno connettivi: in particolare, scegliamo di usare solo ¬ e ⇒; gli altri connettivi possono essere ricondotti ai due scelti: infatti, basta intendere p∨q come (¬q)⇒p e p∧q come ¬((¬p)∨(¬q)). Non tutte le combinazione di segni ovviamente costituiscono delle formule: ci sono delle regole di formazione. Le regole di formazione sono le seguenti:
- ogni variabile proposizionale è una formula;
- se F è una formula allora ¬F è una formula;
- se F1,F2 sono formule allora F1∨F2 è una formula;
- se F1,F2 sono formule allora F1∧F2 è una formula;
- se F1,F2 sono formule allora F1⇒F2 è una formula.
Ad esempio, quindi, non è una formula l'espressione p⇒q¬ in quanto il connettivo ¬ non figura prima di una variabile proposizionale. Si passa quindi a descrivere quali sono le regole di trasformazione che permettono di passare da una formula ad un’altra formula. Tali regole sono due:
- regola di sostituzione: in una formula è lecito sostituire, in ogni occorrenza dove figuri una variabile proposizionale, una generica formula. Ad esempio, nella formula p⇒(q∨p) possiamo sostituire al posto di p la formula (¬q)∨r ottenendo la formula ((¬q)∨r)⇒(q∨((¬q)∨r))).
- modus ponens (deduzione logica): dalle due formule p e p⇒q è possibile dedurre q.
Per completare il quadro servono ora gli assiomi del calcolo dai quali si possono poi, applicando le regole di trasformazione, dedurre i teoremi del calcolo proposizionale. Una possibile scelta di assiomi (scegliamo quelli proposti dal matematico polacco Łukasiewicz ai primi del Novecento) è dato da:
- p⇒(q⇒p);
- (p⇒(q⇒r))⇒((p⇒q)⇒(p⇒r));
- ((¬p)⇒(¬q))⇒(q⇒p).
I teoremi della logica si ottengono quindi dagli assiomi 1,2,3 applicando le regole di trasformazione. Ad esempio, dimostriamo il seguente teorema:
Teorema: (¬p)∨p.
Dimostrazione: Prima di tutto, per definizione di ∨ dobbiamo mostrare che (¬p)⇒(¬p), ovvero, grazie alla regola di trasformazione, che p⇒p. Usiamo l'assioma 2 con la scelta p,q=p⇒p,r=p; abbiamo (p⇒((p⇒p)⇒p))⇒((p⇒(p⇒p))⇒(p⇒p)). Siccome p⇒((p⇒p)⇒p)) è l'assioma 1 con la scelta q=p⇒p, per modus ponens si ha (p⇒(p⇒p))⇒(p⇒p). Ancora per modus ponens si ha p⇒p, che è la tesi.
Gli assiomi scelti sono delle tautologie, come si controlla facilmente, e dunque la domanda se la logica delle proposizioni sia o no completa rispetto agli assiomi dati può essere posta, ottenendo, come accennato in precedenza, risposta affermativa.