Limitiamo la risposta alla sola logica delle proposizioni; la difficoltà appare già in questo contesto semplificato. Per questo tipo di calcolo logico può essere fornito un sistema assiomatico dal quale, mediante le regole di trasformazione, è possibile dedurre i teoremi della logica: per maggiori dettagli si può vedere anche la risposta http://www.vialattea.net/esperti/php/risposta.php?num=14422. Allo scopo quindi di capire quali teoremi un sistema assiomatico è in grado di dimostrare (risolvere cioè il problema della completezza) si cerca una proprietà delle proposizioni che è soddisfatta se e solo se questa proposizione è un teorema della teoria: questa proprietà è la proprietà di essere una tautologia. Classicamente, una tautologia viene definita in termini di vero e falso, ovvero una tautologia è una proposizione che è sempre vera qualunque valore di verità si assegni alle variabili proposizionali in gioco: ad esempio, come l'autore afferma, la proposizione "p v non(p)" è una tautologia, e si dimostra applicando le usuali tavole di verità dei connettivi logici. La verità però è un concetto semantico, mentre a livello di logica proposizionale e deduzione logica dobbiamo restare ad un puro livello sintattico. Dobbiamo quindi individuare un modo alternativo per identificare le tautologie senza appellarci a vero e falso: questo è possibile e anche molto semplice. È sufficiente infatti dividere in due classe disgiunte ed esaustive le formule della logica: diciamo C1 e C2; la classe C1 sarà la classe delle tautologie. Fissiamo ora le seguenti convenzioni:
- Una formula del tipo "p v q" appartiene a C2 se p e q sono entrambi in C2, in caso contrario appartiene alla classe C1;
- Una formula del tipo "p ⇒ q" appartiene a C2 se p appartiene a C1 e q appartiene a C2, in caso contrario appartiene alla classe C1;
- Una formula del tipo "p ∧ q" appartiene a C1 se p e q sono entrambi in C1, in caso contrario appartiene alla classe C2;
- Una formula del tipo "non p" appartiene a C2 se p appartiene a C1, in caso contrario appartiene alla classe C1.
Un rapido esame semantico delle convenzioni effettuate ci convince della bontà della definizione "sintattica" di tautologia. Infatti, ad esempio la proposizione "p v q" risulta sempre vera se non capita mai che sia p sia q sono false, che è proprio il caso in cui sia p sia q stanno in C2. Oppure ancora, la proposizione "p ⇒ q" è una tautologia se non capita mai il caso p vero e q falso, che di nuovo è proprio il caso escluso dalla convenzione 2. In modo analogo si vedono i significati delle convenzioni 3 e 4. Una volta stabilito che la classe C1 rappresenta la classe delle tautologie si passa a verificare che gli assiomi scelti per assiomatizzare la logica sono tutti elementi di C1, e dunque si procede dimostrando che il sistema assiomatico (non uno qualunque ben inteso, va scelto in modo opportuno) dimostra tutte e sole le proposizioni di C1, che sono quindi tutte e sole le tautologie semantiche. Risulta quindi dimostrata la completezza della logica delle proposizioni, risultato ottenuto da Gödel nel 1929. L'approccio semantico alla questione è più intuitivo ma coinvolge la nozione di verità che non è definibile a livello sintattico, ma è del tutto equivalente all'approccio sintattico sopra esposto, per cui le due strade permettono di ottenere le stesse verità logiche.