deduzióne (matematica)
Indice
Generalità
La deduzione è sinonimo, di volta in volta, di derivazione, dimostrazione e inferenza. L'uso più frequente è però come sinonimo di derivazione. In questo senso per deduzione di una formula F in un calcolo logico C si intende una successione finita di formule di C, che soddisfa alle seguenti condizioni: innanzitutto ogni formula della deduzione o è un assioma logico, o è un'assunzione, o è il risultato dell'applicazione di una delle regole di C a una o più formule precedenti; in secondo luogo, la formula finale della successione deve essere appunto F. Va osservato che il carattere peculiare della deduzione è dato dal fatto che essa fa riferimento non solo agli assiomi logici di C, ma anche a delle assunzioni (che possono essere infinite) che si fanno in via ipotetica. L'insieme degli assiomi e delle assunzioni di C costituisce le premesse della deduzione e la formula derivata ne è la conclusione.
Teorema di deduzione
Teorema, dovuto separatamente a Herbrand (1928) e a Tarski), che si può formulare in termini sintattici nel modo seguente: se M è un dato insieme di formule e P e Q sono delle formule, allora da M è deducibile (derivabile) che P implica Q se e solo se da M e P è derivabile Q. In termini semantici il teorema suona così: se M è un dato insieme di formule e P e Q sono delle formule, allora “P implica Q” è una conseguenza di M se e solo se Q è una conseguenza di M e P riuniti. Si può dimostrare che queste due formulazioni sono equivalenti. Questo teorema, cioè, ci dice che una certa espressione P di una teoria T è deducibile (derivabile) dagli assiomi A di T se e solo se “A´ implica P” è una tesi logica, dove A´ è la congiunzione di un numero finito di assiomi di A. Utilizzando questo teorema sono stati sviluppati nel 1934 da S. Jaskowski e da G. Gentzen, separatamente, dei calcoli particolari detti di deduzione naturale. Essi sono caratterizzati dal fatto di essere costituiti da sole regole e in particolare da regole per l'introduzione e l'eliminazione di connettivi, dall'assumere come regole primitive il teorema di deduzione e il principio del terzo escluso.