domingo, 7 de noviembre de 2010

Lenguajes Logicos.


En clase se estudiaron ya varios tipos de lenguajes, que entran en la categoría de paradigma imperativo y paradigma funcional, en esta ocasión estudiaremos el paradigma lógico.
Sabemos que las aplicaciones que hemos desarrollado casi siempre siguen un mismo esquema, por ejemplo casi siempre nuestros programas involucran operaciones aritméticas, secuencias de instrucciones, etc. Muchas veces es difícil (inclusive para un programador experimentado) tratar de modelar cierto problema con la programación tradicional.
Hoy en día estos lenguajes que pertenecen a la categoría del paradigma imperativo, han evolucionado bastante que ya no es tan complicado como en varios años.
Para poder resolver problemas de este tipo tenemos a la programación lógica, que es una manera más sencilla, para el intelecto humano, de expresar problemas complejos y así poder resolverlos mediante la aplicación de reglas, hipótesis y teoremas.
De ahí surgen los lenguajes del paradigma lógico, en donde es más factible resolver ciertos problemas en donde la programación tradicional sería un fracaso.
Para tratar de demostrar esto, nuestra tarea consiste en elegir un problema lógico y modelar su solución, aplicando varias reglas de lógica, algunos teoremas del álgebra booleana, etc..
El problema que elegí está un poco largo pero no es nada del otro mundo que no podamos comprender ya que aplicaremos conceptos ya vistos en matemáticas discretas y en sistemas digitales. Está un poco encaminado al área de la electrónica digital pero sigue los mismos principios de la lógica computacional.
Mi problema es el siguiente:
Granja de Ovejas
Un granjero requiere de una alarma para detectar cuando hay peligro para sus ovejas ya que cercas del rancho, hay una manada de lobos y pueden ser devorados por ellos. El rancho cuenta con una puerta grande que solo puede ser cerrada o abierta por varios trabajadores.
Entonces hay que diseñar un sistema que
1-active la alarma cuando las ovejas estén fuera del corral y la puerta este abierta
2-active la alarma cuando los lobos estén cercas y las ovejas fuera del corral.
Todo esto aplicando reglas de lógica, y algunos teoremas.
Para ello tomaremos como variables de entrada: las ovejas, los lobos y la puerta.
La salida resultante sería la función de la alarma que implementaremos.
Entonces lo siguiente que realizaremos será una tabla de verdad en donde veremos todas las posibles condiciones.
Tomaremos los siguientes valores para trabajar.
Si la puerta está cerrada tomaremos como un 0
Si la puerta está abierta tomaremos como un 1

Si las ovejas están fuera del corral tomaremos como un 1
Si las ovejas están dentro del corral tomaremos como un 0

Si los lobos están cerca tomaremos como un 1
Si los lobos están lejos tomaremos como un 0 



Este comportamiento lo vemos representado en la tabla de verdad con todas las condiciones posibles, cuando se activara la alarma. 


Para que se comprenda mucho mejor los conceptos y tener un mejor control sobre las variables, utilizaremos las variables A para representar las ovejas, B para representar la puerta y C para representar los lobos.
Luego de esto obtendremos la función que representa el comportamiento anterior que estaría dada por la siguiente:
F=A¬ B C+A B C¬+A B C
donde solo tomaremos los resultados verdaderos para construir dicha función. Para aclaración el símbolo “¬” indica que el termino es negado.
Posteriormente de la tabla de verdad obtenida, haremos uso de algunos teoremas para reducir esta expresión algebraica booleana, estos teoremas son ampliamente utilizados en el diseño secuencial.

Haremos uso del mapa de Karnaugh. ¿Pero que son entonces los mapas de karnaugh?
Los Mapas de Karnaugh son una herramienta muy utilizada para la simplificación de circuitos lógicos. Cuando se tiene una función lógica con su tabla de verdad y se desea implementar esa función de la manera más económica posible se utiliza este método.
Para armar nuestro mapa se utiliza la formula 2^ n donde n es el numero de variables que utilizamos, en nuestro caso 3 variables, sustituyendo quedaría 2^3 que sería igual a 8. Ese será el número de casillas de nuestro mapa de Karnaugh.
Luego vamos llenando nuestro mapa con los resultados de la tabla de verdad, asignándolos en la posición correspondiente de acuerdo con nuestro mapa, por ejemplo en nuestra tabla de verdad en la posición 001 tenemos una salida que es igual a 0, posteriormente buscamos esa posición en nuestro mapa de Karnaugh y el resultado lo representaremos ahí. Haremos lo mismo con todos los valores de la tabla de verdad hasta llenar nuestro mapa de Karnaugh. 











Para que se comprenda mejor el llenado de la tabla, haremos las siguientes aclaraciones: Las dos primeras filas indican los valores que puede tomar la variable “Lobos” o la variable “C” en este caso primera fila donde C = 0 y segunda fila donde C = 1; La primera columna donde se puede observar los dos ceros agrupados, esta columna representa los valores de A y B es decir de las ovejas y de la puerta en donde toman los valores de cero AB=00(A=0 y B=0); La segunda columna al igual que la anterior representa los dos estados posibles de las variables donde AB=01(A=0 y B=1); Lo mismo para la tercera y cuarta columna AB=11(A=1 y B=1) y AB=10(A=1 y B= 0) respectivamente.
Posteriormente que llenamos nuestro mapa, hay que crear nodos agrupando en potencias de 2, los “unos” 1 que tengamos adyacentes de manera horizontal y vertical. 










 Ahora en cada grupo de unos se le asigna la unión (producto lógico) de las variables que se mantienen constante (ya sea uno o cero) ignorando aquellas que cambian.
Por ejemplo en nuestro mapa de karnaugh , nos vamos a la posición 0 1 1 que es donde tenemos nuestro primer 1 y nuestro nodo, entonces comparamos las variables A,B y C con cada uno de los nodos y solo las que permanezcan constantes, las tomaremos para formar la nueva función. 

Entonces quedaría así: 

Primera unión en la posición 0 1 1, con las variables C, A y B respectivamente.
Primera unión en la posición 1 1 1, con las variables C, A y B respectivamente.
Observamos que la variable C cambio cuando comparamos ambas posiciones y las variables A y B permanecieron constantes, entonces A y B las tomaremos para la nueva función.

Hacemos lo mismo en la segunda unión.
Segunda unión en la posición 1 1 1, con las variables C, A y B respectivamente.
Segunda unión en la posición 1 1 0, con las variables C, A y B respectivamente.
En esta segunda unión observamos que solo la variable B fue la que cambio, y las variables C y A permanecieron constantes, entonces son las que tomaremos para nuestra función.
La tabla siguiente muestra de manera mas clara el procedimiento anterior:












  






Como ya se dijo anteriormente solo se tomaron los valores que permanecieron constantes.

Nuestra nueva función ya reducida quedaría de la siguiente forma:
F= (A+B)(A+C) Agrupamos terminemos semejantes
F = A (B+C) y esta seria nuestra expresión ya reducida.
Ahora si queremos representar dicha función en un circuito o en algún lenguaje de programación, recordemos algunas de las puertas lógicas que vimos anteriormente en matemáticas discretas.
Si recordamos la puerta lógica AND indica una multiplicación y sus condiciones son: para que sus salida sea verdadera, por lo menos dos de sus entradas tendrán que ser verdaderas. Su representación es el siguiente:
 
La puerta lógica OR indica una suma y sus condiciones son: para que su salida sea verdadera, por lo menos una de sus entradas tendrá que ser verdadera. Su representación es la siguiente:


Nuestro circuito quedaria de la siguiente forma: 





 









Y de ahí solo quedaría a nuestro criterio si queremos implementarlo en un circuito electrónico o representar dicha función en un lenguaje de programación, en este caso, mas adelante lo representaremos en un lenguaje logico como lo es Prolog.

Referencias.


Publicado por en

1 comentario:

  1. Elisa8 de noviembre de 2010, 8:18

    Bueno, el problema que elegiste te empuja más a lo que es la electrónica digital que en la programación en sí, pero reportas bien. Te pongo un total de cuatro puntos: dos por la explicación y dos por el programa propuesto.

    ResponderEliminar

Suscribirse a: Enviar comentarios (Atom)