Algoritmo Para la Construcción de Una Máquina de Estado Finito y Para Determinar La Distributividad En Los Reticulados

En esta era de computadores y telecomunicaciones, nos enfrentamos día a día a situaciones de entrada y salida. Por ejemplo, al comprar un refresco en una máquina expendedora, damos como entrada ciertas monedas y después oprimimos un botón para obtener la salida esperada, es decir, el refresco. La primera moneda que damos como entrada pone la máquina en movimiento. Aunque generalmente no nos preocupamos acerca de lo que ocurre dentro de la máquina (a menos que se descomponga y tengamos una pérdida), convendría notar que, de alguna forma, la máquina lleva un registro de las monedas depositadas, hasta que se introduce el importe correcto. Sólo entonces, y no antes, la máquina deja salir el refresco esperado. En consecuencia, para que el vendedor tenga la ganancia esperada por cada refresco, la máquina debe recordar internamente, conforme se va insertando cada moneda, la suma de dinero depositado. A éste tipo de máquinas, le llamamos MAQUINAS DE ESTADO FINITO.

Algoritmo Para la Construcción de Una Máquina de Estado Finito

Paso 1: Describir la máquina en palabras; hay que escribir en detalle todo lo que queremos que realice la máquina sin obviar comandos o decisiones que debe tomar.

Paso 2: Dibujar el diagrama; ayuda a entender las funciones de la máquina, contiene todas las posibles entradas y salidas que la máquina tiene, es decir estados y valores que va a realizar.

Paso 3: Seleccionar números para representar estados y valores; se necesita representar los valores como números binarios para luego poder representarlos en un circuito. Sustituimos en el diagrama los nombres a los valores por los números.

Paso 4: Escribir una tabla de verdad; esto ayuda a determinar si el diagrama está bien constituido.

Paso 5: Encontrar la expresión booleana; para cada circuito que necesitamos diseñar, vamos a escribir una expresión lógica que expresa su salida en función de sus entradas. Derivamos las expresiones de la tabla de verdad hecha en el paso anterior. A esta expresión se le llama expresión booleana

Existen métodos para determinar si un reticulado es distributivo. El primero consiste en satisfacer dos condiciones dadas para todos sus elementos, el cual será explicado en esta primera parte. El segundo es por medio de un criterio gráfico el cual compara gráficamente todos los subreticulados con dos reticulados que no son distributivos.

Algoritmo. Determinar la Distributividad A Través de Satisfacer 2 Condiciones.

Paso 1. Identificar el conjunto.

Paso 2. Identificar el Cardinal del Conjunto.

Paso 3. El Cardinal del Conjunto elevarlo a la 3. Este Paso determina la cantidad de alternativas posibles a combinar.

Paso 4. Asignar valor a x.

Paso 5. Con x fijo, asignarle valor a y.

Paso 6. Con x,y fijos. Asignarle valor a z.

Paso 7. Calcular

J= x ∈ (y ∈ z),

K= (x ∈ y) ∈ (x ∈ z),

H = x ∈ (y ∈ z),

L = (x ∈ y) ∈ (x ∈ z)

Paso 8. Verificar si coincide: J = K, H = L.

Paso 9. El algoritmo se detiene si una de las comparaciones no es verdadera. Si esto sucede, el reticulado no es distributivo.

Paso 10. Si el número de posibilidades del paso 3; son todas verdaderas en el paso 8. El reticulado es distributivo.

Algoritmo. Determinar la Distributividad de un Reticulado de Manera Gráfica

Paso 1. Identificar el conjunto.

Paso 2. Identificar el Cardinal del Conjunto.

Paso 3. Sí el cardinal es menor a 5, el reticulado es distributivo.

Paso 4. Sí el cardinal es mayor o igual a 5, determinar todos los subreticulados que sean isomorfos a alguno de los dos reticulados siguientes:

Paso 5. Comparar cada reticulado con los reticulados F1 y F2.

Paso 6. Sí uno de ellos coincide con F1 ó F2. El reticulado no es distributivo.

Paso 7. Sí todos sus subreticulados isomorfos a F1 y F2 no coinciden, dicho reticulado es distributivo.

 

Si te gustó este contenido, compartelo!