2.4: Prueba por contradicción

¿Cuántas veces te he dicho que cuando has eliminado lo imposible,
lo que quede, por improbable que sea, debe ser la verdad?

Sherlock Holmes, detective británico ficticio
en El signo de los cuatro

La forma habitual de probar que una afirmación es falsa es demostrar que no puede ser verdad. Esto lo hacemos considerando qué pasaría si efectivamente fuera cierto. Es decir, suponemos, en aras de la argumentación, que la aseveración es cierta. Si, mediante el uso de la lógica, podemos demostrar que esta suposición conduce a una contradicción, entonces podemos concluir que la hipótesis estaba equivocada: la afirmación que nos interesa debe ser falsa. Esto se conoce como prueba por contradicción.

Las pruebas por contradicción se utilizan con bastante frecuencia en la vida cotidiana. Aquí hay un ejemplo artificial:

Ejemplo\(\PageIndex{1}\)

Supongamos que alguien ha robado un brazalete del salón de la señora Haslot. ¿Podría haberlo hecho el mayordomo? El inspector Thinkright podría decir: “Supongamos que Jeeves, el mayordomo, se llevó el brazalete. Sabemos que estuvo en la cocina hasta las 8 de la tarde, por lo que el robo debió haber ocurrido en un momento posterior. No obstante, Jeeves es altamente alérgico a Fifi, y ese perro estuvo en el salón desde las 7:30pm hasta que se descubrió el robo a medianoche, por lo que Jeeves debió haber estornudado continuamente mientras estaba en el salón. Pero el guardia de seguridad refuta absolutamente esto: afirma inequívocamente que precisamente hubo 2 tos, y ningún estornudo en absoluto, viniendo del salón anoche. Así, Jeeves no podría haberse llevado el brazalete; lo eliminamos como sospechoso”.

También surgen en matemáticas:

Ejemplo\(\PageIndex{2}\)

Aquí hay un argumento en inglés que muestra que no hay un número natural mayor (es decir, el más grande):

Supongamos que hay algún mayor número natural. Llámalo\(n\).

Entonces también\(n + 1\) es un número natural. Y, obviamente,\(n+1 > n\).

Entonces hay un número natural (es decir,\(n + 1\)) que es mayor que\(n\).

Esto contradice el hecho de que\(n\) es el mayor número natural.

Entonces nuestra hipótesis lleva a consecuencias que son imposibles.

Conclusión: Nuestra hipótesis no puede ser cierta: no hay mayor número natural.

La regla de “Prueba por Contradicción” nos permite convertir una explicación de este tipo en una prueba oficial. Si asumimos que una afirmación particular es cierta y demostramos que esto lleva a algo imposible (es decir, una contradicción), entonces hemos probado que nuestra suposición es errónea; la suposición debe ser falsa, por lo que su negación debe ser verdadera:

R: Alberta es grande.

B: BC es grande.

#	Aserción	Justificación	Versión en Inglés de Assertion
m	A	suposición (por contradicción)	Supongamos que Alberta es grande.
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
n	B &\(\lnot\) B	Cualquiera que sea la razón	Entonces BC es grande y BC no es grande.
	\(\lnot\)A	prueba por contradicción (líneas m-n)	Alberta no debe ser grande.

Para que esta regla se aplique, la última línea del subprueba debe ser una contradicción explícita de la forma\(B \& \lnot B\): alguna aserción y su negación. Escribimos “(conducirá a una contradicción)” o “(por contradicción)” como nota para nosotros mismos y para el lector. Es una explicación de por qué iniciamos la subprueba, y no forma parte formalmente de la prueba.

Otra Terminología

Prueba por Contradicción nos permite poner\(\lnot\) en una aserción, por lo que algunos lógicos la llaman\(\neg\) - introducción, pero utilizamos la terminología de los matemáticos, que siempre se refieren a ella como “Prueba por Contradicción”. (Y la\(\neg\) - regla de eliminación es el hecho que\(\lnot\lnot A\) es lógicamente equivalente a\(A\), que es una de las reglas de negación en.)

Ejercicio\(\PageIndex{3}\)

Proporcionar una justificación (números de regla y línea) para cada línea de estas pruebas.

1. #	Aserción	Justificación
   1	\(\lnot\)C\(\Rightarrow\) B\(\lor\) C
   2	A y\(\lnot\) B
   3	\(\lnot\)C
   4	B\(\lor\) C
   5	B
   6	\(\lnot\)B
   7	B &\(\lnot\) B
   8	\(\lnot\lnot\)C
   9	C
   10	(A y\(\lnot\) B)\(\Rightarrow\) C

2. #	Aserción	Justificación
   1	(A\(\lor\) B)\(\Rightarrow \lnot\) B
   2	B
   3	A\(\lor\) B
   4	\(\lnot\)B
   5	B &\(\lnot\) B
   6	\(\lnot\)B

3. #	Aserción	Justificación
   1	P\(\Rightarrow\) Q
   2	Q\(\Rightarrow\) R
   3	R\(\Rightarrow \lnot\) P
   4	P
   5	Q
   6	R
   7	\(\lnot\)P
   8	P &\(\lnot\) P
   9	\(\lnot\)P

4. #	Aserción	Justificación
   1	(P\(\lor \lnot\) Q)\(\Rightarrow \lnot\) R
   2	Q\(\Rightarrow\) R
   3	R
   4	Q
   5	P
   6	P\(\lor \lnot\) Q
   7	\(\lnot\)R
   8	R &\(\lnot\) R
   9	\(\lnot\)Q
   10	P\(\lor \lnot \) Q
   11	\(\lnot\)R
   12	R &\(\lnot\) R
   13	\(\lnot\)R

5. #	Aserción	Justificación
   1	Z\(\Rightarrow\) (C y\(\lnot\) N)
   2	\(\lnot\)Z\(\Rightarrow\) (N y\(\lnot\) C)
   3	\(\lnot\)(N\(\lor\) C)
   4	N
   5	N\(\lor\) C
   6	(N\(\lor\) C) y\(\lnot\) (N\(\lor\) C)
   7	\(\lnot\)N
   8	C
   9	N\(\lor\) C
   10	(N\(\lor\) C) y\(\lnot\) (N\(\lor\) C)
   11	\(\lnot\)C
   12	Z
   13	C &\(\lnot\) N
   14	C
   15	C &\(\lnot\) C
   16	\(\lnot\)Z
   17	N &\(\lnot\) C
   18	N
   19	N &\(\lnot\) N
   20	\(\lnot\lnot\)(N\(\lor\) C)
   21	N\(\lor\) C

Ejercicio\(\PageIndex{4}\)

Dar un comprobante de dos columnas de cada una de estas deducciones.

1. \(Q\Rightarrow(Q\&\lnot Q)\),\(\therefore \lnot Q\)
2. \(J\Rightarrow\lnot J\),\(\therefore \lnot J\)
3. \(U \Rightarrow X\),\(V \Rightarrow \lnot X\),\(\therefore \lnot (U \& V)\)
4. \((M \lor N) \Rightarrow \lnot T\),\(\lnot T \Rightarrow \lnot M\),\(\therefore \lnot M\)
5. Hipótesis:

Si Alice está aquí, entonces Bob está aquí.
Si Bob está aquí, entonces Carol está aquí.
Si Carol está aquí, entonces Bob no está aquí.

Conclusión: Alice no está aquí.