Teorema de la deducción

Teorema de la deducción

El teorema de la deducción es un metateorema de la lógica proposicional, la lógica de primer orden y otros sistemas lógicos, que es bastante utilizado para demostrar otros metateoremas.[1] 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 \Gamma \cup \{A\}, entonces A → B es deducible a partir de Γ solamente.[1] En símbolos:

\Gamma \cup \{A\} \vdash_S B   implica   \Gamma \vdash_S A \to B

O alternativamente, en la notación del cálculo de secuentes:

\Gamma, A \vdash_S B   implica   \Gamma \vdash_S A \to B

En el caso especial donde Γ es el conjunto vacío, el teorema de la deducción dice que:[1]

A \vdash_S B   implica   \vdash_S A \to B

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.[1]

Contenido

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 Γ, entonces B es deducible a partir de \Gamma \cup \{A\}.[1] Simbólicamente:

\Gamma \vdash_S A \to B   implica   \Gamma \cup \{A\} \vdash_S B

Esto, junto con el teorema de la deducción, permite establecer el metateorema:[1]

\Gamma \cup \{A\} \vdash_S B   si y sólo si   \Gamma \vdash_S A \to B

Y cuando Γ es el conjunto vacío:

A \vdash_S B   si y sólo si   \vdash_S A \to B

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:

A demostrar: \phi \to \phi \,
Paso Fórmula Razón
1 \phi \, Supuesto.
2 \phi \or \phi Desde (1) por introducción de la disyunción.
3 (\phi \or \phi) \and \phi Desde (1) y (2) por introducción de la conjunción.
4 \phi \, Desde (3) por eliminación de la conjunción.
5 \phi \vdash \phi Resumen de (1) hasta (4).
6 \vdash \phi \to \phi Desde (5) por introducción del condicional. Q.E.D.

Véase también

Notas y referencias

  1. ↑ a b c d e f Hunter, Geoffrey (1971). «Sección 26». Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press. 

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Teorema (lógica) — Saltar a navegación, búsqueda Un teorema es una afirmación que puede ser demostrada como verdadera dentro de un marco lógico. Demostrar teoremas es el asunto central en la matemática. Un teorema generalmente posee un número de condiciones que… …   Wikipedia Español

  • Deducción del módulo de la suma — Saltar a navegación, búsqueda Este artículo presenta una deducción para la expresión del módulo resultante de dos vectores (véase Vector (física) y Módulo (vector)) Deducción Sean dos vectores y que forman un ángulo θ entre sí: La fórmula para c …   Wikipedia Español

  • Teorema de equipartición — Figura 1. Movimiento térmico de un péptido tipo hélice α. El movimiento vibratorio es aleatorio y complejo, y la energía de un átomo en particular puede fluctuar ampliamente. Sin embargo, el teorema de equipartición permite que se pueda calcular… …   Wikipedia Español

  • Teorema de completitud de Gödel — El teorema de completitud de Gödel es un importante teorema de la lógica matemática, que fue demostrado por primera vez por Kurt Gödel en 1929 y que en su forma más conocida establece lo siguiente: En una lógica de primer orden, toda fórmula que… …   Wikipedia Español

  • Teorema — Para otros usos de este término, véase Teorema (desambiguación). Esta imagen muestra la relación entre las cadenas de caracteres, las fórmulas bien formadas y los teoremas. En algunos sistemas formales, sin embargo, el conjunto de los teoremas… …   Wikipedia Español

  • Teorema de inversión de Lagrange — En el ámbito del análisis matemático, el teorema de inversión de Lagrange, también denominado fórmula de Lagrange Bürmann , permite obtener la expansión en serie de Taylor de la función inversa de una función analítica. Contenido 1 Enunciado del… …   Wikipedia Español

  • Teorema del coseno/apéndice — Artículo principal: Teorema del coseno El objetivo de este apéndice es presentar pruebas de algunas afirmaciones usadas en el artículo Teorema del coseno, pero que por razones didácticas es preferible separar del cuerpo principal, ya que… …   Wikipedia Español

  • teorema — {{＃}}{{LM T37546}}{{〓}} {{［}}teorema{{］}} ‹te·o·re·ma› {{《}}▍ s.m.{{》}} Proposición demostrable a través de la lógica mediante reglas de deducción aceptadas: • el teorema de Pitágoras.{{○}} {{★}}{{＼}}ETIMOLOGÍA:{{／}} Del griego theórema… …   Diccionario de uso del español actual con sinónimos y antónimos

  • Demostración original del teorema de completitud de Gödel — Saltar a navegación, búsqueda En 1930 Gödel demostró la completitud de la lógica cuantificacional de primer orden. Literalmente el Teorema de completitud de Gödel establece: Para toda fórmula A de la lógica cuantificacional de primer orden, si A… …   Wikipedia Español

  • Validez (lógica) — En lógica, la validez es una propiedad que tienen los argumentos cuando las premisas implican la conclusión. Si la conclusión es una consecuencia lógica de las premisas, se dice que el argumento es deductivamente válido. Algunos consideran estas… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”