completezza logica

completezza logica

completezza logica il termine completezza viene utilizzato in logica con due diversi significati; si parla infatti di completezza semantica o di completezza sintattica di un sistema di assiomi.

Completezza semantica

Un sistema formale è semanticamente completo se in esso è possibile dimostrare formalmente tutte le formule valide, cioè vere rispetto a una qualsiasi interpretazione. Per esempio il calcolo degli enunciati è semanticamente completo perché in esso è possibile derivare tutte le tautologie; il calcolo dei predicati è semanticamente completo perché in esso è possibile derivare tutte le formule valide. La completezza semantica del calcolo dei predicati, formalizzato come teoria del primo ordine, è espressa dal teorema di completezza che può essere formulato nel modo seguente: nel linguaggio dei predicati del primo ordine i teoremi sono esattamente le formule ben formate logicamente valide. Questo teorema è stato dimostrato da Gödel che ne diede una formulazione differente: «Se α è una formula del calcolo dei predicati del primo ordine, allora o α o ￢α è soddisfacibile in un modello costruito a partire dai numeri naturali». Si può dimostrare che le due formulazioni del teorema di completezza sono equivalenti.

Completezza sintattica

Un sistema formale è sintatticamente completo se per ogni formula α è possibile dimostrare formalmente α oppure la sua negazione ￢α. Si può esprimere ciò dicendo che ogni formula è decidibile, cioè è possibile stabilire in un numero finito di passi se la formula è dimostrabile oppure no. Il calcolo degli enunciati è sintatticamente incompleto; infatti, se A è una formula atomica, allora né A né ￢A sono tautologie, quindi nessuna delle due formule è dimostrabile per la completezza semantica. Anche l’aritmetica formalizzata dagli assiomi di Peano è sintatticamente incompleta: ciò segue dal primo teorema di Gödel. In base a questo teorema è possibile, infatti, costruire una formula aritmetica la cui verità o falsità non è dimostrabile nell’ambito dell’aritmetica stessa.