2.3: Subpruebas para\(\Rightarrow\)-introduction
- Page ID
- 116540
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
Considera esta deducción:
| \(P \Rightarrow R\) | Si el Papa está aquí, entonces el Registrador está aquí. | |
| \(\therefore (P \& Q) \Rightarrow R\) | Si el Papa y la Reina están ambos aquí, entonces el Registrador está aquí. |
La deducción es válida. Intuitivamente, podemos justificarlo señalando que si\(P \& Q\) es cierto, entonces ciertamente\(P\) es cierto, por lo que la hipótesis implica\(R\) es verdadera. Así, lo hemos verificado\((P \& Q) \Rightarrow R\). La regla\(\Rightarrow\) -introducción nos permitirá convertir esta justificación intuitiva en una prueba oficial.
Comenzamos la prueba anotando la hipótesis de la deducción y dibujando una línea horizontal oscura, así:
| # | Aserción | Justificación | Versión en Inglés de Assertion |
|---|---|---|---|
| 1 | P\(\Rightarrow\) R | Hipótesis | Si el Papa está aquí, entonces el Registrador está aquí. |
La conclusión de la deducción es una aseveración sobre lo que sucede cuando\(P \& Q\) es cierto. Es decir, queremos ver qué pasa si asumimos, en aras de la argumentación, que la aseveración\(P \& Q\) es cierta. Para lograrlo, lo que haremos es iniciar una Subprueba, una prueba dentro de la prueba principal, donde asumimos que eso\(P \& Q\) es cierto. Cuando iniciamos una subprueba, iniciamos un nuevo conjunto de columnas dobles, y las sangramos desde el margen izquierdo. Entonces escribimos en una suposición para la subprueba. Esto puede ser lo que queramos. En el caso que nos ocupa, queremos asumir\(P \& Q\). Nuestra prueba ahora se ve así:
| # | Aserción | Justificación | Versión en Inglés de Assertion |
|---|---|---|---|
| 1 | P\(\Rightarrow\) R | Hipótesis | Si el Papa está aquí, entonces el Registrador está aquí. |
| 2 | P & Q | suposición | Supongamos que el Papa y la Reina están ambos aquí. |
Es importante notar que no estamos pretendiendo haber probado\(P \& Q\) (que el Papa y la Reina están aquí). Se puede pensar en la subprueba como planteando la pregunta: ¿Qué podríamos mostrar si\(P \& Q\) fuera verdad? Por una cosa, podemos derivar\(P\). Así que hacemos:
| # | Aserción | Justificación | Versión en Inglés de Assertion |
|---|---|---|---|
| 1 | P\(\Rightarrow\) R | hipótesis | Si el Papa está aquí, entonces el Registrador está aquí. |
| 2 | P & Q | suposición | Supongamos que el Papa y la Reina están ambos aquí. |
| 3 | P | &-elim (línea 2) | El Papa está aquí. |
Y ahora, como el Papa está aquí, podemos derivar\(R\), de la hipótesis de que\(P \Rightarrow R\):
| # | Aserción | Justificación | Versión en Inglés de Assertion |
|---|---|---|---|
| 1 | P\(\Rightarrow\) R | hipótesis | Si el Papa está aquí, entonces el Registrador está aquí. |
| 2 | P & Q | suposición | Supongamos que el Papa y la Reina están ambos aquí. |
| 3 | P | &-elim (línea 2) | El Papa está aquí. |
| 4 | R | \(\Rightarrow\)-elim (líneas 1 y 3) | El Registrador está aquí. |
Esto ha demostrado que si tuviéramos\(P \& Q\) como hipótesis, entonces podríamos probar\(R\). En efecto, hemos probado\((P \& Q) \Rightarrow R\): que si el Papa y la Reina están aquí, entonces el Registrador está aquí. En reconocimiento a esto, la regla de if-introducción (\(\Rightarrow\)-intro) nos permitirá cerrar la subprueba y derivar\((P \& Q) \Rightarrow R\) en la prueba principal. Nuestra prueba final se ve así:
| # | Aserción | Justificación | Versión en Inglés de Assertion |
|---|---|---|---|
| 1 | P\(\Rightarrow\) R | hipótesis | Si el Papa está aquí, entonces el Registrador está aquí. |
| 2 | P & Q | suposición | Supongamos que el Papa y la Reina están ambos aquí. |
| 3 | P | &-elim (línea 2) | El Papa está aquí. |
| 4 | R | \(\Rightarrow\)-elim (líneas 1 y 3) | El Registrador está aquí. |
| 5 | (P & Q)\(\Rightarrow\) R | \(\Rightarrow\)-intro (líneas 2-4) | Si el Papa y la Reina están ambos aquí, entonces el Registrador está aquí. |
Observe que la justificación para aplicar la regla\(\Rightarrow\) -intro es la totalidad de la subprueba. Por lo general, eso va a ser más de sólo tres líneas.
Puede parecer como si la capacidad de asumir algo en absoluto en una subprueba conduciría al caos: ¿te permite probar alguna conclusión a partir de alguna hipótesis? La respuesta es no, no lo hace. Considera esta prueba:
| # | Aserción | Justificación | Versión en Inglés de Assertion |
|---|---|---|---|
| 1 | P | hipótesis | El Papa está aquí. |
| 2 | Q | suposición | Supongamos que la Reina está aquí. |
| 3 | Q | repetir (línea 2) | Como se mencionó anteriormente, la Reina está aquí. |
Puede parecer como si esto es una prueba de que se puede derivar cualquier conclusión\(Q\) (como la conclusión de que la Reina está aquí) de cualquier hipótesis\(P\) (como la hipótesis de que el Papa está aquí). Cuando termina la línea vertical para la subprueba, la subprueba se cierra. Para completar una prueba, debe cerrar todas las subepruebas. Y no se puede cerrar la subprueba y volver a utilizar la regla de repetición en la línea 4 para derivar\(Q\) en la prueba principal. Una vez que cierras una subprueba, no puedes volver a referir a líneas individuales dentro de ella.
\[\text{You CANNOT use a line from a subproof as a hypothesis for a theorem that is being applied in the main proof. Lines in a subproof stay in the subproof.}\]
\[\text{In particular, you CANNOT use the repeat theorem to copy a line from a subproof into the main proof.}\]
Por supuesto, es legítimo hacer esto:
| # | Aserción | Justificación | Versión en Inglés de Assertion |
|---|---|---|---|
| 1 | P | hipótesis | El Papa está aquí. |
| 2 | Q | suposición | Supongamos que la Reina está aquí. |
| 3 | Q | repetir (línea 2) | Como se mencionó anteriormente, la Reina está aquí. |
| 4 | Q\(\Rightarrow\) Q | \(\Rightarrow\)-intro (líneas 2 y 3) | Si la Reina está aquí, entonces la Reina está aquí. |
Esto no debería parecer tan extraño, sin embargo. Dado que\(Q\Rightarrow Q\) es una tautología, se desprende válidamente de cualquier hipótesis.
En una forma general, la regla\(\Rightarrow\) - introducción se ve así:
| # | Aserción | Justificación | Versión en Inglés de Assertion |
|---|---|---|---|
| m | A | suposición (querer B) | Supongamos que Alberta es grande. |
| \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) |
| n | B | Cualquiera que sea la razón | Entonces BC es grande. |
| A\(\Rightarrow\) B | \(\Rightarrow\)-intro (líneas m-n) | Si Alberta es grande, entonces BC es grande. |
Cuando introducimos una subprueba, es útil tomar nota de lo que queremos derivar (y agregarlo a la justificación). Esto es para que a cualquiera que lea la prueba le resulte más fácil entender por qué estamos haciendo lo que estamos haciendo (y también para que no olvidemos por qué iniciamos la subprueba si continúa por cinco o diez líneas). No hay regla de “querer”. Es una nota para nosotros mismos y para el lector; no forma parte formalmente de la prueba.
Si bien es legal abrir una subprueba con cualquier suposición que le plazca, hay alguna estrategia involucrada en elegir una suposición útil. Comenzar una subprueba con una suposición arbitraria y alocada simplemente desperdiciaría líneas de la prueba. Para derivar una declaración if-then mediante el uso de\(\Rightarrow\) -intro, por ejemplo, se debe asumir la hipótesis de la declaración en una subprueba.
Ahora que tenemos tanto la regla de introducción como la regla de eliminación para “implica”, podemos probar que la siguiente deducción es válida:
| \(P \Rightarrow Q\) | Si el Papa está aquí, entonces también lo está la Reina. | ||
| \(Q \Rightarrow R\) | Si la Reina está aquí, entonces también lo está el Registrador. | ||
| \(\therefore P \Rightarrow R\) | Por lo tanto, si el Papa está aquí, entonces también lo está el Registrador. |
Comenzamos la prueba escribiendo las dos hipótesis como suposiciones. Dado que el principal operador lógico en la conclusión es\(\Rightarrow\), podemos esperar usar la regla\(\Rightarrow\) -introduction. Para eso, necesitamos una subprueba, así que escribimos en la hipótesis de la declaración if-then como la suposición de una subprueba:
| # | Aserción | Justificación | Versión en Inglés de Assertion |
|---|---|---|---|
| 1 | P\(\Rightarrow\) Q | hipótesis | Si el Papa está aquí, entonces también lo está la Reina. |
| 2 | Q\(\Rightarrow\) R | hipótesis | Si la Reina está aquí, entonces también lo está el Registrador. |
| 3 | P | suposición (quiero R) | Supongamos que el Papa está aquí. |
Lo pusimos a\(P\) disposición asumiendo en una subprueba, lo que nos permite aplicar\(\Rightarrow\) -elim a la línea 1. Esto nos da\(Q\), lo que nos permite aplicar\(\Rightarrow\) -elim a la línea 2. Habiendo derivado\(R\), cerramos la subprueba. Al asumir\(P\) que pudimos probar\(R\), así\(\Rightarrow\) -elim completa la prueba. Aquí está escrito:
| # | Aserción | Justificación | Versión en Inglés de Assertion |
|---|---|---|---|
| 1 | P\(\Rightarrow\) Q | hipótesis | Si el Papa está aquí, entonces también lo está la Reina. |
| 2 | Q\(\Rightarrow\) R | hipótesis | Si la Reina está aquí, entonces también lo está el Registrador. |
| 3 | P | suposición (quiero R) | Supongamos que el Papa está aquí. |
| 4 | Q | \(\Rightarrow\)-elim (líneas 1 y 3) | La Reina está aquí. |
| 5 | R | \(\Rightarrow\)-elim (líneas 2 y 4) | El Registrador está aquí. |
| 6 | P\(\Rightarrow\) R | \(\Rightarrow\)-intro (líneas 3-5) | Si el Papa está aquí, entonces también lo está el Registrador. |
Proporcionar una justificación (números de regla y línea) para cada línea de estas pruebas.
-
# Aserción Justificación 1 A\(\Rightarrow\) B 2 \(\lnot\)A\(\Rightarrow\) C 3 A\(\lor \lnot\) A 4 A 5 B 6 B\(\lor\) C 7 A\(\Rightarrow\) (B\(\lor\) C) 8 \(\lnot\)A 9 C 10 B\(\lor\) C 11 \(\lnot\)A\(\Rightarrow\) (B\(\lor\) C) 12 B\(\lor\) C -
# Aserción Justificación 1 L\(\Leftrightarrow \lnot\) O 2 L\(\lor \lnot\) O 3 L 4 L 5 L\(\Rightarrow\) L 6 \(\lnot\)O\(\Rightarrow\) L 7 L -
# Aserción Justificación 1 F\(\Rightarrow\)\(\left(\text{(G & H)}\lor \text{I} \right)\) 2 \(\lnot\)I 3 \(\lnot\)G 4 \(\lnot\)G\(\lor \lnot\) H 5 (\(\lnot\)G\(\lor \lnot\) H) e\(\lnot\) I 6 \(\lnot\)(G & H)\(\lor\) I) 7 \(\lnot\)(G & H)\(\lor\) I)\(\Rightarrow \lnot\) F 8 \(\lnot\)F 9 \(\lnot\)G\(\Rightarrow \lnot\) F 10 \(\lnot\lnot\)F\(\Rightarrow\lnot\lnot\) G 11 F\(\Rightarrow\) G -
# Aserción Justificación 1 \(\lnot\)C\(\Rightarrow\) B\(\lor\) C 2 C\(\lor \lnot\) C 3 C 4 B\(\lor\) C 5 C\(\Rightarrow\) (B\(\lor\) C) 6 B\(\lor\) C 7 A y\(\lnot\) B 8 \(\lnot\)B 9 C 10 (A y\(\lnot\) B)\(\Rightarrow\) C -
# Aserción Justificación 1 Z\(\Rightarrow\) (C y\(\lnot\) N) 2 \(\lnot\)Z\(\Rightarrow\) (N y\(\lnot\) C) 3 Z\(\lor \lnot\) Z 4 Z 5 C &\(\lnot\) N 6 C 7 N\(\lor\) C 8 Z\(\Rightarrow\) (N\(\lor\) C) 9 \(\lnot\)Z 10 N &\(\lnot\) C 11 N 12 N\(\lor\) C 13 \(\lnot\)Z\(\Rightarrow\) (N\(\lor\) C) 14 N\(\lor\) C -
# Aserción Justificación 1 A\(\Rightarrow\) E 2 C\(\Rightarrow\) E 3 A\(\lor\) C 4 E 5 (A\(\lor\) C)\(\Rightarrow\) E
Escriba un comprobante de dos columnas de cada una de las siguientes deducciones:
- \(P \Rightarrow (Q \lor R)\),\(Q \Rightarrow S\),\(R \Rightarrow S\),\(\therefore\)\(P \Rightarrow S\)
- \(Q \Rightarrow (Q \Rightarrow P)\),\(\therefore\)\(Q \Rightarrow P\)
- \(M\lor(N\Rightarrow M)\),\(\therefore\)\(\lnot M \Rightarrow \lnot N\)
- \(R \Rightarrow \Bigl(R \Rightarrow \bigl(R \Rightarrow (R \Rightarrow Q) \bigr) \Bigr)\),\(\therefore\)\(R \Rightarrow (Q \lor P)\)
- \(A \lor B\),\(A \Rightarrow C\),\(B \Rightarrow D\),\(C \Rightarrow E\),\(D \Rightarrow E\),\(\therefore E\)
R" label="PQRIfIntro-P<>R">6. Hipótesis:
El Papa está aquí si y sólo si la Reina está aquí.
La Reina está aquí si y sólo si el Registrador está aquí.
Conclusión: El Papa está aquí si y sólo si el Registrador está aquí.
7. R" label="PQRIfIntro-P<>R">Hipótesis:
Si Jim está enfermo, debería quedarse en la cama.
Si Jim no está enfermo, debería salir a jugar afuera.
Conclusión: Jim debería quedarse en la cama o salir a jugar.
8. R" label="PQRIfIntro-P<>R">Hipótesis:
Si el Rey va a cantar, entonces la Reina cantará.
Si tanto el Rey como la Reina cantarán, entonces también cantarán el Príncipe y la Princesa.
Si el Rey y la Reina y el Príncipe y la Princesa cantarán todos, entonces la fiesta será divertida.
Conclusión: Si el Rey va a cantar, entonces la fiesta será divertida.
9. R" label="PQRIfIntro-P<>R">Hipótesis:
Si el Papa está aquí, entonces o la Reina está aquí o el Registrador está aquí.
Si la Reina está aquí, entonces el Espía está aquí.
Si el Registrador está aquí, entonces el Espía está aquí.
Conclusión: Si el Papa está aquí, entonces el Espía está aquí.