Diferencia entre revisiones de «Teorema de la deducción»

2586 bytes añadidos ,  hace 10 años
Ampliación general del artículo
m (robot Modificado: en:Deduction theorem)
(Ampliación general del artículo)
En [[lógica matemática]], elEl '''teorema de la deducción''' es un [[metateorema]] de la [[lógica proposicional]], la [[lógica de primer orden]] y otros [[Sistema lógico|sistemas lógicos]], que es bastante utilizado para demostrar otros metateoremas.<ref name=Hunter /> Se trata de una formalización de la técnica de [[demostración]] ordinaria según la cual para demostrar que de A se sigue B, basta con suponer A y a partir de ello llegar a la conclusión de que B.
 
Más formalmente, el teorema establece que si una fórmula B es deducible (en un sistema deductivo S) a partir del conjunto de fórmulas <math>\Gamma \cup \{A\}</math>, entonces A → B es deducible a partir de <math>\Gamma</math> solamente.<ref Oname=Hunter>{{cita enlibro |apellido=Hunter |nombre=Geoffrey |título=Metalogic: An Introduction to the Metatheory of Standard First-Order Logic |editorial=University of California Press |año=1971 |capítulo=Sección 26}}</ref> En símbolos:
 
:<math>\Gamma \cup \{A\} \vdashvdash_S B</math> &nbsp; implica &nbsp; <math>\Gamma \vdashvdash_S A \to B</math>
 
O alternativamente, en la notación del [[cálculo de secuentes]]:
En el caso especial donde <math>\Gamma</math> es el [[conjunto vacío]], el teorema de la deducción dice que:
 
:<math>\Gamma, A \vdashvdash_S B</math> &nbsp; implica &nbsp; <math>\vdashGamma \vdash_S A \to B</math>
 
En el caso especial donde <math>\Gamma</math> es el [[conjunto vacío]], el teorema de la deducción dice que:<ref name=Hunter />
 
:<math>A \vdash_S B</math> &nbsp; implica &nbsp; <math>\vdash_S A \to B</math>
 
El teorema de la deducción parece haber sido demostrado por primera vez por [[Alfred Tarski]] en 1921, pero la primera demostración publicada es de [[Jacques Herbrand]] en 1930.<ref name=Hunter />
 
== Converso del teorema de la deducción ==
 
A partir del teorema de la deducción, es fácil demostrar que si A → B es deducible (en un sistema deductivo S) a partir de <math>\Gamma</math>, entonces B es deducible a partir de <math>\Gamma \cup \{A\}</math>.<ref name=Hunter /> Simbólicamente:
 
:<math>\Gamma \vdash_S A \to B</math> &nbsp; implica &nbsp; <math>\Gamma \cup \{A\} \vdash_S B</math>
 
Esto, junto con el teorema de la deducción, permite establecer el metateorema:<ref name=Hunter />
 
:<math>\Gamma \cup \{A\} \vdash_S B</math> &nbsp; si y sólo si &nbsp; <math>\Gamma \vdash_S A \to B</math>
 
Y cuando <math>\Gamma</math> es el conjunto vacío:
 
:<math>A \vdash_S B</math> &nbsp; si y sólo si &nbsp; <math>\vdash_S A \to B</math>
 
== El teorema en los sistemas de deducción natural ==
 
El teorema de la deducción se utiliza en los sistemas de deducción natural como regla de introducción del [[condicional material]]. La regla dice que si suponiendo A se llega a la conclusión de que B, entonces se puede afirmar que A → B, introduciendo así un condicional material. Por ejemplo, una demostración que hace uso de la regla de introducción del condicional material podría ser:
 
{| class="wikitable" style="background:white"
! colspan="3" | A demostrar: <math>\phi \to \phi \,</math>
|-
! align="left" | Paso
! Fórmula
! Razón
|-
| 1 || <math>\phi \,</math> || Supuesto.
|-
| 2 || <math>\phi \or \phi</math> || Desde (1) por introducción de la disyunción.
|-
| 3 || <math>(\phi \or \phi) \and \phi</math> || Desde (1) y (2) por introducción de la conjunción.
|-
| 4 || <math>\phi \,</math> || Desde (3) por eliminación de la conjunción.
|-
| 5 || <math>\phi \vdash \phi</math> || Resumen de (1) hasta (4).
|-
| 6 || <math>\vdash \phi \to \phi</math> || Desde (5) por introducción del condicional. [[Q.E.D.]]
|}
 
== Véase también ==
* [[Metalógica]]
 
== Notas y referencias ==
{{listaref}}
 
[[Categoría:Teoremas de lógica]]
20 580

ediciones