AUTOMATAS

Actividad 3

Leer la lectura "¿Para qué sirven los autómatas?" del libro de Introducción a la Teoría de Autómatas, Lenguajes y Computación de John E. Hopcroft y con base en lo leído da un ejemplo de situaciones en las que se pueden aplicar las siguientes demostraciones:

• Demostraciones deductivas

Consisten en una secuencia de afirmaciones o proposiciones, cuya validez nos conduce a una conclusión a partir de unas proposiciones iniciales, llamadas hipótesis o postulados.

Ejemplo:

Un teorema que se demuestra cuando es posible llegar desde una hipótesis H, a una conclusión C, es la proposición “si H, entonces C”, por lo cual “C, se deduce a H”.

• Demostración de la conversión contradictoria

La conversión contradictoria de la proposición “si H, entonces C” es “si no C, entonces no H”. Una proposición y su conversión contradictoria son ambas verdaderas o ambas falsas y se pueden demostrar cualquiera de las dos para demostrar también la otra.

Ejemplo:

H y C son ambas verdaderas

H es verdadera y C es falsa

C es verdadera y H es falsa

H y C son ambas falsas

• Demostración por reducción al absurdo

“H y no C implica falsedad”

Se Comienza suponiendo que son ciertas tanto la hipótesis H como la negación de la conclusión C, se completa probando que algo que se sabe que es falso, deriva lógicamente de “H y no de C”

Ejemplo:

El teorema donde se probo la proposición “si entonces” cuya hipótesis era “U, es un conjunto infinito, S es un subconjunto finito de U, y T es el conjunto complementario de S respecto a U”, este teorema se realizo por esta demostración y se supuso “no C”, que T es infinito.

La demostración condujo a obtener falsedad a partir de H y no C, primero se probo que U tenía que ser finito a partir de que S y T eran finitos, en la hipótesis H se establece que U es infinito y un conjunto no puede ser finito e infinito a la vez, se demostró que la proposición lógica es falsa.

• Contraejemplos

Si al hacer la demostración de un teorema no podemos demostrar que es verdadero, existe otra alternativa, demostrar que es falso.

Generalmente es más sencillo demostrar que una proposición no es un teorema, que demostrar que si lo es.

Ejemplo:

Si S es cualquier proposición, entonces la proposición “S, no es un teorema”, es en si misma una proposición sin parámetros y por tanto puede considerarse más una observación que un teorema.

“Todos los números son impares”

Refutación

“El numero entero 2 es primo, pero 2 es impar”

...