deduzione, catena di
deduzione, catena di
deduzione, catena di rappresentazione formale di un ragionamento consistente in una sequenza di formule ben formate (ƒbƒ), ognuna delle quali è legata alla successiva da determinate regole, le regole di inferenza (o di deduzione). La struttura di una catena di deduzione è la seguente: si parte da una o più formule di base che sono gli assiomi del sistema formale considerato. Da tali formule ben formate si ricava una nuova formula ben formata tramite l’applicazione di una regola di inferenza; questo procedimento si ripete un numero finito di volte fino ad arrivare a una formula finale, il teorema. Un teorema è quindi una formula ottenibile dagli assiomi attraverso una catena deduttiva; tale catena è la dimostrazione del teorema, che può essere riassunta nello schema seguente:
In un calcolo logico si definisce formalmente una deduzione di una formula α da un insieme di formule Γ come una sequenza finita di formule α1, α2, …, αn tali che αn = α e ogni formula αi sia o una delle formule di Γ o un assioma oppure derivi dalle formule precedenti per mezzo dell’applicazione di una regola di inferenza.
Come esempio di catena di deduzione, si riporta la dimostrazione del teorema A ⇒ A del calcolo degli enunciati (si legge «A implica A», il simbolo ⇒ rappresenta il connettivo della implicazione). Per costruire tale deduzione si utilizzano due assiomi del calcolo degli enunciati:
• la formula A ⇒ (B ⇒ A) indicata come assioma 1;
• la formula (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C)) indicata come assioma 2;
e la regola di deduzione detta modus ponens, in base alla quale si può dedurre la formula B dalle due formule A e A ⇒ B (sia negli assiomi sia nella regola di deduzione, i simboli A, B e C rappresentano delle formule ben formate qualsiasi).
Si parte dall’assioma 1 scegliendo come formula B la formula (A ⇒ A):
L’ultima formula a cui si perviene, cioè α5, è proprio il teorema che si voleva dimostrare.