decisione, problema della

decisione, problema della

decisione, problema della in logica, problema che concerne la possibilità di determinare la validità di un enunciato in un dato sistema logico. Per esempio, nel linguaggio degli enunciati esiste un metodo algoritmico per determinare la verità di ogni formula: ciò avviene grazie alle tavole di verità che consentono di stabilire il valore di verità di ogni proposizione composta a partire dai valori di verità delle proposizioni elementari che la costituiscono. In questo senso il calcolo degli enunciati è decidibile. Ciò non avviene nella logica predicativa (ossia nel linguaggio dei predicati) come dimostrato nel 1936 da A. Church e in generale dal teorema di → Gödel, che afferma l’esistenza, per ogni sistema formale non contraddittorio contenente la teoria dei numeri, di proposizioni che non possono essere né dimostrate né confutate. Ciò non significa, però, che non sia possibile isolare classi di formule per le quali il problema della decisione sia risolubile.