Motivación para la deducción natural

Question

He estado aprendiendo deducción natural recientemente. He visto muchos problemas y estoy empezando a ser capaces de resolver problemas más fácilmente.

Por alguna razón siento la necesidad de preguntar a qué escuela secundaria de matemáticas de los estudiantes siempre pregunte acerca de las matemáticas.

¿Cuál es el punto de deducción natural? Yo enseño un problema de clase en ciencias de la computación módulo y me preocupa que cuando llegamos a estos problemas de un estudiante va a preguntar.

Para la teoría de grafos o la teoría de los números me puede decir algo interesante, pero ¿qué podía decir que, en todo interesante acerca de deducción natural? No hay nada en absoluto?

Answer 1

La razón más probable sería usar deducción natural en una prueba es porque es paralela a la forma de pensar de la gente. Cuando tratando de probar algunos complicado implicación de la cadena como $$(A\to(B\to C))\to((A\to B)\to(A\to C)),$$ la mayoría de las personas encuentran que es más lógico y razonable asumir que una parte de la izquierda y deducir la parte de la derecha, en lugar de trabajar con los axiomas que lidiar con la implicación directa, aunque los enfoques puede ser demostrado ser equivalentes. Por encima de la tautología, es menos esclarecedor para hacer una tabla de verdad y demostrar que es verdadera en virtud de todas las asignaciones que simplemente a la razón en una deductivo manera:

Supongamos que $A\to(B\to C)$, $A\to B$, y $A$ son conocidos. (Quiero mostrar $C$.) Desde $A$ es verdadera y $A$ implica $B$, sabemos $B$ es cierto, y desde $A$ implica $B\to C$, que es cierto. Pero, a continuación, $B$ $B\to C$ son verdaderas, por lo $C$ también es cierto.

Este enfoque escala mucho mejor que una tabla de verdad de enfoque, y es más fácil de seguir, por lo que se ha informado a mí en mi propio trabajo en la creación de un sistema para la simulación de deducción natural de pruebas en Metamath, que se basa en un enfoque axiomático para la manipulación de implicaciones.

Answer 2

Deducción Natural ha jugado un papel en la automatizados de teoremas.

También, la configuración natural deductivo derivaciones y, a continuación, convertir esas derivaciones a axiomático pruebas puede dar una lista de fórmulas que pueden funcionar bien como los resonadores cuando se utiliza un sistema automatizado teorema de armario que pueda ayudarle a encontrar un acortamiento de la axiomática de la prueba. O incluso hacer que sea más fácil encontrar una primera automatizado de prueba. Por ejemplo, hace poco me escribieron a mano natural de la derivación deductiva y la convirtió en un 94 paso axiomática de la prueba, en donde cada paso que indica un uso de condensados desprendimiento de generar un teorema que no es un axioma. A continuación, utilizando los pasos como los resonadores, más cortas pruebas de la misma teorema en el mismo sistema que se encontraron (y alguien tiene la prueba para menos pasos, probablemente con el uso de otras técnicas). O aquellos deducción natural derivaciones, si se convierte a axiomático de las pruebas, puede ayudar a encontrar teoremas decir más débiles de las teorías, tales como Lukasiewicz 3-valores de la lógica o intuitionistic lógica o relevantes de la lógica con Bob Veroff del método de prueba de bocetos (búsqueda de "a prueba de bocetos" en el enlace).

Answer 3

En breve, la deducción natural es una prueba de cálculo de los modelos que la forma natural de la conducta de la gente de su razonamiento deductivo - es un Kalkül des natürlichen Schließens (Gentzen, 1943).

Deducción Natural se opone a los principios de "artificial" tratamiento de la lógica que se encuentra en Frege, Russell Y Whitehead o de Hilbert por medio de la axiomatization del pensamiento lógico. Las pruebas de esos llamados "de Hilbert-estilo" los sistemas pueden ser muy molestos, como ya he puesto en otro lugar:

[Axiomático] pruebas tienden a ser mucho más desconcertante y laborioso, a continuación, Gentzen de estilo. Presumiblemente, una deducción natural experimentado lógico habría problemas para demostrar que el mismo teorema de él demostró en el último sistema utilizando la antigua (Por ejemplo, tenga en cuenta que el menor de prueba conocidos en Mendelson's sistema de $M$ el (trivial?) '$A \wedge B \vdash A$' exige $-$ as far as I know $-$ más de 50 líneas! [§2.3]).

Usted puede tener un cheque no cómo una axiomática de la prueba de $¬A→B⊢¬B→A$ ganancias, y comparar, ofreciendo una deducción natural contraparte prueba de ello.

Answer 4

En el contexto de la informática, la deducción natural tiene un papel muy importante que jugar. La estructura de las pruebas de deducción natural se puede leer como simples programas funcionales con una reducción semántica dada por la forma en que la introducción y eliminación de reglas para un cierto conectivo de encajar.

Por ejemplo, considere una prueba de (A ^ B) => (B ^ A). En deducción natural, esto se puede escribir

--------------x ---------------x A ^ B |- A ^ B A ^ B |- A ^ B -------------- ^E2 ----------------^E1 A ^ B |- B A ^ B |- A -------------------------------^I A ^ B |- B ^ A ---------------^I(x) |- A^B => B^A

De una manera más concisa de escribir esta prueba sería (fun x = <#2 x, #1 x>). En otras palabras, es una función que toma un par de valores y devuelve un par de la segunda componente, seguido por el primer componente.

En esta interpretación de programas como pruebas, las proposiciones comprobado en deducción natural dan un tipo de sistema. Por dar sentido a otros conectivos lógicos en términos de deducción natural, tenemos nuevo tipo de sistemas y, a veces nuevo programa de construcciones en el lenguaje de programación.

Esta idea se refiere con frecuencia como la de Curry-Howard Correspondencia, que constituye la base de una gran cantidad de lenguaje de programación moderno de investigación.