Autómatas

Autómatas

Un autómata es un modelo computacional que consiste en un conjunto de estados bien definidos: un estado inicial un alfabeto de entrada y una función de transición. Esta definición se iguala a la de un autómata finito o máquina de estados.

En un autómata un estado es la representación de su condición en un instante dado. Un autómata comienza en el estado inicial con un conjunto de símbolos; su paso de un estado a otro se efectúa a través de la función de transición, la cual, partiendo de su estado actual y un conjunto de símbolos de entrada, lo lleva al nuevo estado.

Demostraciones deductivas: el método de deductivos basa en ir encadenando estados que se suponen verdaderos de manera tal que se obtienen de nuevos estados; es decir, es aquel que combina principios necesarios y simples (axiomas postulados, teoremas definiciones, etc.) para deducir nuevas estados. Por ejemplo: a) Todo cuadrado es figura geométrica, toda figura geométrica es un plano, todo cuadrado es un plano. B) Toda arquitectura es un estudio, todo el estudio es una profesión, toda arquitectura es una profesión.

Demostraciones inductivas: Se basa en estados iniciales reales y verdaderos que apoyan la función de transición y que nos llevan a otro estado nuevo verdadero. Ejemplo: Demostrar que si n es un número entero positivo, entonces 4n+15n−1 es múltiplo de 9.

Solución: Si n=1 entonces: 4(1)+15(1)−1=18 y como 9 es múltiplo de 18 se tiene que la afirmación es cierta.

Demostraciones de la conversión contradictoria: En una proposición demostrar “si H, entonces C” mediante la demostración de la proposición equivalente “si no C, entonces no H”. Esta última recibe el nombre de conversión contradictoria de la primera. Ejemplo: Si a todos les gusta nadar, entonces todos saben nadar. Conversión contradictoria: Si no sabes nadar, no te gusta la natación.

Demostración por reducción al absurdo: La Reducción al Absurdo es uno de los métodos más usados para hacer demostraciones matemáticas. La idea es suponer que la proposición que queremos demostrar es falsa, y a partir de esta suposición, usando deducciones matemáticas, llegar a una contradicción o algo absurdo, lo cual implica que nuestra proposición es necesariamente cierta. Ejemplo:

Demuestre que si m y n son enteros tales que n + n2 + n3 = m + m2, entonces n es par

Solución. Supongamos que n es impar. A partir de esto debemos conseguir una contradicción. Como n es impar, entonces n2 y n3 son ambos impares, de donde n + n2 + n3 es impar (ya que es la suma de tres impares). Entonces, como m + m2 = n + n2 + n3, se tiene que m + m2 es impar. Sin embargo, m+m2 es siempre par (ya que m+m2 = m (m+1) y necesariamente alguno de los números m ó m+1 es par). Hemos llegado a una contradicción. De allí se tiene que n es par, que es lo que queríamos demostrar.

Contraejemplos: Un contraejemplo es un ejemplo que prueba la falsedad de un enunciado. Ejemplo; "todos los corredores son maratonistas". Como esta proposición dice que una cierta capacidad (todos tiene la condición de correr grandes distancias) es válida para todos los corredores, incluso un solo corredor de pista probará su falsedad. En este caso, un corredor de pista es un contraejemplo a "todos los escritores son maratonistas".

Inducciones estructurales: Consiste en demostrar que una proposición se cumple para todos los elementos mínimos del tipo, y que si la propiedad se cumple para todas las subestructuras de una cierta estructura X, entonces se debe cumplir también para X. Por ejemplo, Todos los nadadores dominan los cuatro estilos de natación, entonces si un nadador participa en el estilo de mariposa, todos participan en este estilo.

...