Prueba por contradicción

En este laboratorio, aprenderás que algunos problemas no se pueden resolver en absoluto.

En esta página, resolverá acertijos lógicos encontrando una contradicción, es decir, mostrando que una posibilidad tiene que ser verdadera porque la otra no tiene sentido.

  1. Imagina una isla en algún lugar con dos familias numerosas. Una familia (a diferencia de las personas normales) solo puede decir la verdad, incluso cuando prefiere mentir. Esta familia portavoz de la verdad no puede hacer declaraciones falsas, ni siquiera por error. La otra familia, la familia portavoz de la mentira, es igual de confiable, pero de la manera opuesta: nunca pueden hacer declaraciones verdaderas.

    Estás visitando la isla y conoces a dos de sus habitantes, Diego y Zoey. Diego dice: "Zoey y yo somos de la misma familia."

    Habla con tu compañero
    1. ¿Puedes decir con seguridad de qué familia es Zoey? Si es así, ¿qué familia?
    2. ¿Puedes decir con seguridad de qué familia es Diego? Si es así, ¿qué familia?
Jasmine, Omar y Morgan están conversando sobre el problema anterior.
Jasmine: Estoy bastante segura de que Zoey es portavoz de la verdad, pero no sé cómo demostrarlo.
: Prueba por contradicción

Una prueba por contradicción (proof by contradition) es una prueba de dos pasos para saber si algo es falso que se realiza:

  1. asumiendo que es verdad
  2. mostrando cómo eso es imposible (que crea una contradicción)

Omar: A veces es más fácil demostrar que algo es falso que demostrar que algo es verdadero. Entonces, asumamos lo contrario de lo que quieres probar, y veamos a dónde nos lleva. Supongamos que Zoey es portavoz de la mentira.
Jasmine: Bueno. Entonces, si Diego es portavoz de la verdad, entonces lo que dijo es cierto, y son de la misma familia, los que dicen la verdad. Pero supusimos que Zoey es portavoz de la mentira, por lo que en realidad son de diferentes familias, por lo que Diego no puede ser portavoz de la verdad.
Morgan: Entonces, Diego tiene que ser portavoz de la mentira.
Omar: ¡Pero eso tampoco funcionará! Si Diego es portavoz de la mentira, entonces lo que dijo es falso, y son de diferentes familias. Pero ambos son portavoces de la mentira, por lo que en realidad están en la misma familia, por lo que Diego tampoco puede ser portavoz de la mentira.
Jasmine: No importa de qué familia sea Diego, nuestra suposición de que Zoey es portavoz de la mentira nos llevó a una contradicción. Zoey no puede ser portavoz de la mentira, por lo que tiene que ser portavoz de la verdad. Lo probamos.
  1. Imagina que conoces a alguien llamado Derek en la isla y le preguntas si es de la familia de los portavoces de la verdad. ¿Qué contesta él?
  2. ¿Qué pasa si le preguntas a Derek si es de la familia portavoz de la mentira?
Jasmine y Omar están explorando sus propias declaraciones lógicas.
Jasmine: La declaración que estoy haciendo en este momento es falsa.
Omar: (Piensa por un momento) ¡Espera! ¿¡Qué!?
  1. Jasmine afirma que su declaración es falsa. ¿Qué piensas tú? Explica tu pensamiento claramente.
Omar: Eso es muy inteligente, Jasmine. Tu declaración no puede ser verdadera, y no puede ser falsa. Entonces, ni portavoz de la verdad ni portavoz de la mentira podrían decir eso.
Hay cuatro tipos de afirmaciones verdadero/falso:
: Declaración indecidible vs. declaración autocontradictoria

Una declaración indecidible (undecidable) puede ser verdadera o falsa; no sabemos cuál.

Una declaración autocontradictoria (self-contradictory) no puede ser verdadera ni falsa.

  1. ¿Qué preguntas puedes hacer para determinar si una persona es portavoz de la verdad o portavoz de la mentira? Habla con tu compañero Al hablar con otros, encuentra al menos cuatro preguntas que funcionen de manera confiable.
    Si Diego fuera portavoz de la verdad, ¿cómo respondería a tus preguntas? Verifica para asegurarte de que si Diego fuera portavoz de la mentira, respondería de manera diferente.

Teorema: Todos los números enteros positivos son interesantes.

Prueba:

  1. En esa isla de portavoz de la verdad y portavoz de la mentira, te encuentras con Max y Min. Max dice "¡Min y yo somos mentirosos!" ¿Qué tipo de declaración es esta? ¿Es contradictorio? ¿Es indecidible (podría ser cualquiera, pero no hay forma de saberlo)? ¿O es definitivamente resoluble? Si se puede resolver, ¿quién está en qué familia?