Teorema di deduzione

Il teorema di deduzione è un metodo logico-matematico per dimostrare un teorema seguendo il metodo deduttivo ( deduzione logica ). Nella logica matematica una formula A è deducibile da un'altra formula B se l'implicazione A ⇒ B è vera e dimostrabile. Possiamo scrivere il teorema della deduzione nel seguente modo:

Date due formule A e B, la formula A è conseguenza logica della formula B se la formula ( A ⇒ B ) è valida. La validità logica è una condizione necessaria per la deduzione logica poiché si può affermare che A segue logicamente B se e soltanto se in ogni modello in cui la formula A è vera anche la formula B è vera ( A ⇒ B ). Una formula è logicamente valida soltanto se è vera in tutti i modelli ( validità logica ). Nell'esempio che segue viene dimostrata una delle leggi di De Morgan.

Essendo vera la formula ( A ⇒ B ) in ogni modello, la formula ( A ⇒ B ) è valida e possiamo affermare che A segue logicamente B ( conseguenza logica ). Questo è uno dei principali criteri di funzionamento degli algoritmi basati sull'inferenza logica.