Deducción: introducción

Resumen

Esta clase abre la segunda unidad del curso, dedicada a la deducción. Presenta sus cinco clases y el hilo que las une, desde la definición de un sistema deductivo formal hasta las leyes de De Morgan y de distribución; sitúa la unidad en el camino del curso, entre el lenguaje, ya construido, y la semántica y la metateoría, que vendrán, y adelanta lo que estas dirán de ella; justifica la elección de un sistema axiomático, que se construye en dos etapas (el sistema de Łukasiewicz, con tres esquemas de axiomas y el modus ponens, y el sistema del curso, que le añade la regla del reemplazo de la doble negación), y explica por qué hace falta esa segunda regla y por qué se postula en lugar de demostrarse; muestra con una deducción breve cuánto trabajo esconde un razonamiento elemental; precisa lo que se toma de la unidad anterior, que es la lectura única, la inducción fuerte y el despliegue de las abreviaturas, y da consejos para estudiarla.

Objetivos de aprendizaje

Describir la secuencia de las cinco clases de la unidad y explicar qué resultados de cada una usa la siguiente.
Situar la deducción en el recorrido del curso, distinguir la deducibilidad $\Gamma \vdash \varphi$ de la consecuencia semántica $\Gamma \models \varphi$ y explicar qué afirmarán la corrección y la completitud.
Explicar por qué el sistema del curso añade al de Łukasiewicz una segunda regla primitiva, el reemplazo de la doble negación, a partir de lo que los tres esquemas pueden y no pueden ver en una negación conjunta.
Leer una deducción breve por líneas numeradas, distinguir la deducción de fórmulas de la deducción sobre deducciones, reconocer lo que la unidad toma de la anterior y organizar su estudio a partir de la evaluación de entrada.

Evaluación de entrada

Antes de recorrer la unidad conviene medir el punto de partida. Esta evaluación es una autoevaluación: no se califica, y su único propósito es orientar el estudio. Sus trece preguntas son de dos clases. Las tres primeras tocan lo que la unidad da por sabido de la anterior: la lectura única, la inducción fuerte y el despliegue de las abreviaturas; quien falle alguna debe repasar, antes de seguir, la clase que la pregunta nombra. Las diez restantes tocan, en orden, las cinco clases de esta unidad: tres la primera, tres la segunda, dos la tercera, una la cuarta y una la quinta. Quien nunca haya estudiado un sistema deductivo no debe esperar acertarlas, y no importa: cada respuesta, acertada o no, explica el punto y nombra la clase que lo trata. Las mismas destrezas se vuelven a medir al final, en la clase de síntesis.

Evaluación de entrada

Antes de comenzar la unidad, mide tu punto de partida. Es una autoevaluación breve: no se califica y su resultado se guarda solo en tu navegador.

Pregunta 1De unidades anterioresLa cadena $\sigI\sigI\sigO\sigI\sigO\sigO\sigI\sigO\sigI$ es una fórmula compuesta, de la forma $\sigI\varphi\psi$ . ¿Cuáles son sus componentes $\varphi$ y $\psi$ ?
$\varphi = \sigI\sigO\sigI\sigO\sigO\sigI$ y $\psi = \sigO\sigI$ .
$\varphi = \sigI\sigO\sigI$ y $\psi = \sigO\sigO\sigI\sigO\sigI$ .
Admite dos descomposiciones, según dónde se corte la cadena tras el disco inicial.
$\varphi$ es toda la cadena que sigue al disco inicial, y $\psi$ es la cadena vacía.
Pregunta 2De unidades anterioresEn una demostración por inducción fuerte de que todo natural $n$ cumple una propiedad $P(n)$ , ¿qué puede suponerse al demostrar $P(n)$ ?
Que $P(m)$ se cumple para todo natural $m$ menor que $n$ .
Solo que se cumple $P(n - 1)$ .
Que $P(m)$ se cumple para todo natural $m$ menor o igual que $n$ .
Nada, hasta haber demostrado por separado $P(1)$ y $P(2)$ .
Pregunta 3De unidades anterioresCon las abreviaturas oficiales del curso, ¿qué fórmula designa $(\varphi \rightarrow \psi)$ , escrita con la negación conjunta y la negación?
$\neg(\neg\varphi \downarrow \psi)$ .
$(\neg\varphi \downarrow \psi)$ .
$\neg(\varphi \downarrow \neg\psi)$ .
Ninguna en particular: depende de cómo se decida leerla.
Pregunta 4El esquema A1 es $(\varphi \rightarrow (\psi \rightarrow \varphi))$ . ¿Es la fórmula $(v_{1} \rightarrow (v_{2} \rightarrow v_{3}))$ una instancia de A1?
No: la primera y la última aparición de $\varphi$ tendrían que reemplazarse por la misma fórmula, y aquí son $v_{1}$ y $v_{3}$ .
Sí, con $\varphi := v_{1}$ y $\psi := v_{2}$ .
Sí, porque toda implicación cuyo consecuente es otra implicación es instancia de A1.
No, porque las instancias de un esquema no pueden contener variables.
Pregunta 5En una deducción figuran ya las líneas $\psi$ y $(\varphi \rightarrow \psi)$ , donde $\varphi$ y $\psi$ son fórmulas distintas. ¿Qué fórmula permite escribir el modus ponens aplicado a esas dos líneas?
Ninguna: el modus ponens exige el antecedente $\varphi$ , y lo que se tiene es el consecuente.
$\varphi$ .
$(\psi \rightarrow \varphi)$ .
$\neg\varphi$ .
Pregunta 6Se sabe que $\{\varphi\} \vdash \psi$ , es decir, que hay una deducción de $\psi$ cuya única premisa es $\varphi$ . ¿Qué afirma entonces el teorema de deducción?
Que $\vdash (\varphi \rightarrow \psi)$ : la implicación es un teorema.
Que $\vdash \psi$ : la premisa puede suprimirse sin más.
Que $\vdash (\psi \rightarrow \varphi)$ .
Que $\{\psi\} \vdash \varphi$ .
Pregunta 7¿Qué se deduce, sin más premisas, del conjunto $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\}$ ?
$(\varphi \rightarrow \chi)$ .
$\chi$ , aplicando dos veces el modus ponens.
$(\chi \rightarrow \varphi)$ .
$(\varphi \wedge \chi)$ .
Pregunta 8La regla del reemplazo de la doble negación (RDN) cambia, en una línea, una sola aparición de una subfórmula, y actúa sobre la cadena de la lengua base. ¿Cuántas apariciones de la subfórmula $\neg v_{1}$ contiene la cadena que designa $(v_{1} \rightarrow v_{2})$ ?
Dos.
Una, la que corresponde al antecedente.
Ninguna: la fórmula no contiene negaciones.
Cuatro.
Pregunta 9¿Qué fórmula se obtiene de $(\neg\varphi \rightarrow \psi)$ por contraposición, sin añadir dobles negaciones?
$(\neg\psi \rightarrow \varphi)$ .
$(\psi \rightarrow \neg\varphi)$ .
$(\varphi \rightarrow \neg\psi)$ .
$(\neg\psi \rightarrow \neg\varphi)$ .
Pregunta 10¿Designan $(\varphi \vee \psi)$ y $(\neg\varphi \rightarrow \psi)$ la misma fórmula?
No: la primera es $\neg(\varphi \downarrow \psi)$ y la segunda, $\neg(\neg\neg\varphi \downarrow \psi)$ ; son fórmulas distintas, equivalentes por deducción.
Sí, por la definición de la implicación.
Sí, porque ambas se leen « $\varphi$ o $\psi$ ».
No, y tampoco se deduce una de la otra.
Pregunta 11Se sabe que $\varphi \dashv\vdash \varphi'$ , es decir, que cada una se deduce de la otra. ¿Qué justifica que también $\neg\varphi \dashv\vdash \neg\varphi'$ ?
Un teorema, el reemplazo de equivalentes, que se demuestra con el teorema de deducción y la contraposición.
Ninguna justificación especial: basta «negar ambos lados» de la equivalencia.
La definición de la negación, porque $\neg\varphi$ es $(\varphi \downarrow \varphi)$ .
Nada, porque no es cierto: la negación puede separar fórmulas equivalentes.
Pregunta 12Desde el conjunto de premisas $\Gamma \cup \{\neg\varphi\}$ se deducen una fórmula $\chi$ y su negación $\neg\chi$ . ¿Qué puede concluirse?
Que $\Gamma \vdash \varphi$ .
Que $\Gamma \vdash \neg\varphi$ .
Que de $\Gamma$ se deduce cualquier fórmula.
Nada: una deducción que llega a una contradicción no prueba nada.
Pregunta 13¿A qué fórmula es equivalente la negación de una implicación, $\neg(\varphi \rightarrow \psi)$ ?
A $(\varphi \wedge \neg\psi)$ .
A $(\neg\varphi \rightarrow \neg\psi)$ .
A $(\varphi \rightarrow \neg\psi)$ .
A $(\neg\varphi \wedge \psi)$ .