El ejercicio 9 del práctico 1 tiene algunos desafíos interesantes, entre ellos el de estructurar razonablemente la demostración. La letra, dice lo siguiente:

Considere el alfabeto \( \Sigma = \{a, b\} \), y los lenguajes \( \Delta \) y \( \Gamma \) definidos inductivamente con las siguientes reglas. Demuestre que \( \Gamma = \Delta \).

  1. \( \epsilon \in \Gamma \)
  2. Si \( \omega \in \Gamma \), entonces \( a\omega\in \Gamma \)
  3. Si \( \omega \in \Gamma \), entonces \( b\omega\in \Gamma \)
  1. \( \epsilon \in \Delta \)
  2. Si \( \omega\in \Delta \), entonces \( \omega a \in \Delta \)
  3. Si \( \omega \in \Delta \), entonces \( \omega b \in \Delta \)

Cómo demostrar esto? El punto clave en la demostración de cualquier teorema es, en mi opinión, definir la estrategia pensando primero en la estructura y luego en los detalles.

La estructura

Tenemos que hacer una demostración, por lo que tenemos que saber desde donde salimos y hacia dónde tenemos que ir.
Esto es plantear la estructura del problema como un teorema, identificando:
  • Hipótesis: Desde donde se parte. Las hipótesis se asumen como ciertas.
  • Tesis: Qué queremos demostrar. Esto no será cierto hasta que lo demostremos.
  • Demostración: Esto es un encadenamiento de razonamientos que deben ser evidentemente válidos para constituir una prueba.

Cuando se dice evidentemente válido significa que hay que justificar de una forma aceptable para el que lee nuestra demostración, que ese paso de razonamiento es correcto. Puede haber muchos motivos porque un paso puede no ser correcto En el siguiente link, hay una muestra de algunos teoremas mal demostrados: pruebas erróneas.

Un elemento que muchas veces puede llevar a una demostración errónea es el perder de vista qué se quiere demostrar y de donde se parte. Y para esto, es fundamental tener identificadas las hipótesis y tesis. Además, cuando no están debidamente identificadas pueden hacer perder al lector fácilmente. Por lo tanto:
  • Identificar hipótesis y tesis de nuestro problema.
  • Identificar claramente dónde comienza y dónde termina la demostración que se está haciendo.
Describir la Estrategia
Al comenzar cada demostración, conviene describir la estrategia de demostración que se va a seguir.

Para la mayoría de los problemas, no es difícil identificar una estrategia general de la demostración. Algunas veces alcanza con una frase del estilo:
"Demostraremos la propiedad por Inducción sobre el conjunto \( \Gamma \)".
Otras veces, es necesario más detalles:
"Dado que la propiedad a demostrar incluye varios elementos del conjunto \( \Delta \), la demostración se estructurará como una inducción sobre \( \alpha \)"
En la primera sólo se indica el conjunto, y por lo tanto es una indicación de qué PIP se usará, pero en la segunda, se indica el conjunto e incluso el objeto  sobre la que se va a trabajar.
Un ejemplo de estructura: Ej. 9 Práctico 1.

Las hipótesis de nuestro problema siempre existen. Algunas veces se omiten porque estamos en contexto muy determinado (como es este caso) y está muy claro desde donde se sale para lo que se pide demostrar. En este caso, serían las definiciones de los conjuntos \( \Gamma \) y \( \Delta \).

La tesis es claramente: \( \Gamma = \Delta \)

Para continuar, debemos identificar y declarar la estrategia que vamos a utilizar. Esto nos puede llevar a generar nuevas demostraciones que deberemos estructurar de la misma forma. En este caso particular, dado que tenemos una igualdad de conjuntos, elegimos una estrategia determinada de las varias que podrían usarse para esto: la doble inclusión. De esta forma aparecen dos nuevos teoremas en en nuestra demostración.

Una forma de escribirlo sería la siguiente:

H) Definiciones de \( \Gamma \) y \( \Delta \). (* En este caso particular se podría omitir la hipótesis. *)

T) \( \Gamma = \Delta \)

Dem.)

Dado que la tesis es una igualdad de conjuntos, entonces se demuestra la doble inclusión. Esto hace que haya que demostrar los siguientes teoremas.

  1. T) \( \Gamma \subseteq \Delta \)
  2. T) \( \Delta \subseteq \Gamma \)
Una vez demostrados esos dos teoremas, de acuerdo a la definición de igualda de conjuntos se concluye que \( \Gamma = \Delta \).
\( \blacksquare \)
A continuación siguen las demostraciones de los teoremas (o Lemas) a y b

Lema a

H) Definiciones de \( \Gamma \) y \( \Delta \). (* En este caso particular se podría omitir la hipótesis. *)

T) \( \Gamma \subseteq \Delta \)

Dem.)

Por la definición de inclusión, demostrar esta tesis es lo mismo que demostrar:

\[ \bar{\forall x} \in \Gamma. x \in \Delta \]

Esta demostración se realizará usando una inducción (* o aplicando el PIP *) sobre \( \Gamma \) y como propiedad se utilizará \( x \in \Delta \).

Para aplicar el PIP sobre \( \Gamma \) se deben hacer las siguientes demostraciones:

  1. T) \( \epsilon \in \Delta \)

  2. H) \( \omega \in \Delta \)
    T) \( a\omega \in \Delta \)

  3. H) \( \omega \in \Delta \)
    T) \( b\omega \in \Delta \)

a.a

T) \( \epsilon \in \Delta \)

Dem.)

Por la regla i. de la definición de \( \Delta \) , se cumple que \( \epsilon \in \Delta \)

\( \blacksquare \)
a.b
H) \( \omega \in \Delta \)
T) \( a\omega \in \Delta \)
Dem.)

Nuestro teorema puede reformularse como la siguiente propiedad: \( \bar\forall x ( x \in \Delta \Rightarrow ax \in \Delta ) \) o lo que es lo mismo \( \bar\forall x \in \Delta \Rightarrow ax \in \Delta \) .

Esta propiedad, ahora es una propiedad general sobre \( \Delta \) por lo que se puede demostrar por inducción, obtiendo así otro teorema a demostrar.

(* Queda para que lo terminen *)
\( \blacksquare \)

a.c
H) \( \omega \in \Delta \)
T) \( b\omega \in \Delta \)
Dem.)
(* Similar a a.b)
\( \blacksquare \)

Las demostraciones anteriores prueban que la propiedad \( x \in \Delta \) cumple con las hipótesis del PIP de \( \Gamma \) por lo que queda demostrado que la propiedad se cumple para cualquier elemento \( x \) de \( \Gamma \)
\( \blacksquare \)
Lema b.

H) Definiciones de \( \Gamma \) y \( \Delta \). (* En este caso particular se podría omitir la hipótesis. *)

T) \( \Delta \subseteq \Gamma \)

Dem.)

(* Similar a lema a*)
 \( \blacksquare \)




Última modificación: jueves, 16 de marzo de 2017, 10:13