algebra boleana

ALGEBRA BOOLEANA “Boole interpreto su sistema a la manera aristotélica, como un álgebra de clases y de sus propiedades, y al hacerlo amplio la antigua lógica de clases y la liberó de los límites del silogismo”.

Martin Gardner.

INTRODUCCIÓN.
El álgebra booleana fue desarrollada por George Boole y en su libro An investigation of the laws of Thought, publicado en 1854, muestra las herramientas para que las proposiciones lógicas sean manipuladas en forma algebraica. Debido al carácter abstracto de sus principios no tuvo una aplicación directa sino hasta 1938 en que la compañía de teléfonos Bell de Estados Unidos la utilizo para realizar análisis de los circuitos de su red telefónica. En ese mismo año Claude E. Shannon, entonces estudiante de postgrado del Instituto Tecnológico de Massachussets, a partir del álgebra de Boole creó la llamada álgebra de conmutación para representar las propiedades de conmutación eléctrica biestables, demostrando con esto que el álgebra booleana se adapta perfectamente al diseño y representación de circuitos lógicos de control basados en relés e interruptores.
Los circuitos lógicos de control tienen una gran importancia ya que las computadoras, los sistemas telefónicos, los robots y cualquier operación automatizada en una empresa, son algunos de los ejemplos de la aplicación de estos y del álgebra booleana.
Una señal es la representación de información, y puede aparecer en forma de valor o de una cadena de valores de una magnitud física. Existen principalmente dos clases de señales: analógicas y digitales.
La señal analógica tiene como característica principal el continuo cambio de magnitud, de la misma manera que una corriente eléctrica y una presión de gas.
En la señal digital los posibles valores de tensión están divididos en un número infinito de intervalos, a cada uno de los cuales está asignado un valor o una cadena de valores como información. Una señal digital puede obtenerse de una manera analógica asignando ciertos umbrales de sensibilidad.
La señal binaria es una señal digital con solo dos valores posibles: conectado-desconectado, verdadero-falso, 1-0.
EXPRESIONES BOOLEANAS.
El álgebra booleana trabaja con señales binarias. Al mismo tiempo una gran cantidad de sistemas de control, también conocidos como digitales, usan señales binarias y estas son un falso o un verdadero que provienen de sensores que mandan la información al circuito de control, mismo que lleva a cabo la evaluación para obtener un valor que indicará si se lleva a cabo o no una determinada actividad, como encender un foco, arrancar un equipo de ventilación en un cine o ejecutar una operación matemática en una computadora.
Los sensores pueden ser “ópticos”, como los que se usan en las tiendas departamentales (de proximidad); “magnéticos”, como los que permiten detectar armas en aeropuertos; de “temperatura”, como los que utiliza un sistema de calefacción, los refrigeradores o bien el mismo termostato que controla el sistema de enfriamiento del motor de un vehículo; de “nivel”, ya que un flotador como el que tiene un tinaco o una cisterna para controlar la cantidad de agua, es un sensor que puede mandar información a un circuito de control.
En cada uno de estos grupos de sensores existen tipos, tamaños y modelos, de acuerdo con el uso y funcionamiento, de forma que existen infrarrojos, laser, fotoeléctricos y de ultrasonido, entre otros.
Para resolver un problema práctico en el cual se desea automatizar un proceso, es necesario realizar un análisis detallado de lo que se quiere lograr así como de los tipos de sensores necesarios para obtener las señales. Una vez que se conoce esto se plantea el funcionamiento del circuito lógico en una expresión matemática, la cual recibe el nombre de función booleana, y cada una de la variables de que está integrada esta función representa un sensor que provee al circuito de una señal de entrada.
Se puede decir que en general una expresión booleana es un sistema de símbolos que incluyen 1,0, algunas variables y las operaciones lógicas.


 
PROPIEDADES DE LAS EXPRESIONES BOOLEANAS.
Las expresiones booleanas poseen las siguientes propiedades:
Están compuestas de literales (A, B, C, …) y cada una de ellas representa la señal de un sensor. Un ejemplo es F=A^' BD+AB'CD.
El valor de las señales o de la función sólo puede ser 0 o 1, falso o verdadero.
Además de literales, en la expresión booleana se puede tener el valor de 0 o 1. Por ejemplo: F=A^' BD1+AB^' CD+0.
Las literales de las expresiones booleanas pueden estar conectadas por medio de los operadores lógicos And (∧), Or (∨) y Not ('). El operador And es una multiplicación lógica que se indica por medio de un paréntesis, un punto o simplemente poniendo juntas las variables que se multiplican, por ejemplo el producto de A y B se expresa como (A)(B)=A⋅B=AB; el Or es una suma lógica que se indica con el signo +; y el operador Not es el complemento o negación de una señal que se indica por un apostrofe ('). En la siguiente expresión se muestra la forma en que se representan los operadores:
F=A^' BD1+AB^' CD+0
=A'∧B∧D∧1∨A∧B'∧C∧D∨0
Es posible obtener el valor de una expresión booleana sustituyendo en cada una de las literales el valor de 0 o 1, teniendo en cuenta el comportamiento de los operadores lógicos. En las siguientes tablas se muestra la manera en la que se aplica esta propiedad:
And Or Not
A B A∧B=AB A B (A∨B)=A+B A A'
1 1 1 1 1 1 1 0
1 0 0 1 0 1 0 1
0 1 0 0 1 1
0 0 0 0 0 0

Hay que tener un presente que en el algebra booleana:
1+1=1
1+1+1=1
0+1=1
0+0=0
Ya que el valor máximo es 1.
Además de las operaciones básicas, también es posible aplicar la ley de De Morgan de forma semejante a como se aplica en teoría de conjuntos. El siguiente ejemplo muestra la aplicación de esta propiedad:
(ABCD)^'=A^'+B^'+C^'+D'
(A+B+C+D)^'=A'B'C'D'

OPTIMIZACION DE EXPRESIONES BOOLEANAS.
Cuando uno se plantea, en general la expresión booleana obtenida no necesariamente es la óptima, esto es, la más fácil, clara y sencilla de implementar es utilizando compuertas lógicas. La expresión que resulta del planteamiento del problema puede ser simplificada empleando para ello teoremas y postulados del álgebra booleana o bien mapas de Karnaugh.

Simplificación de expresiones booleanas mediante teoremas del álgebra de boole.
Los teoremas que se van a utilizar se derivan de los postulados del álgebra booleana, y permiten simplificar las expresiones lógicas o transformarlas en otras que son equivalentes. Una expresión simplificada se puede implementar con menos equipo y su circuito es más claro que el que corresponda a la expresión no simplificada.
A continuación se presenta una lista de teoremas, cada uno su “dual”.
Número Teorema Dual
1ª 0A=0 1+A=1
2ª 1A=A 0+A=A
3ª AA=A A+A=A
4ª AA^'=0 A+A^'=1
5ª AB=BA A+B=B+A
6ª ABC=A(BC) A+B+C=A+(B+C)
7ª (AB…Z)^'=A^'+B^'+⋯+Z' (A+B+⋯+C)^'=A^' B^'…Z'
8ª AB+AC=A(B+C) (A+B)(A+C)=A+BC
9ª AB+AB^'=A (A+B)(A+B')=A
10ª A+AB=A A(A+B)=A
11ª A+A^' B=A+B A(A^'+B)=AB
12ª CA+CA^' B=CA+CB (C+A)(C+A^'+B)=(C+A)(C+B)
13ª AB+A^' C+BC=AB+A'C (A+B)(A^'+C)(B+C)=(A+B)(A^'+C)

En esta tabla A representa no solo una variable, sino también un término o factor, o bien una expresión.
Para obtener el “dual” de un teorema se convierte cada 0 (cero) en 1 (uno) y cada 1 (uno) en 0 (cero), los signos más (+) se convierten en paréntesis, puntos o simplemente no se ponen, y los puntos en signos más (+). Además de esto, las variables no se complementan ya que al hacerlo se obtendría el complemento en lugar del dual.
Por otro lado, los teoremas 1 al 4 se aplican en cualquier otro caso los teoremas del 5 al 9 son propiedades que tiene el álgebra booleana, semejantes a las reglas de conjuntos correspondientes a las propiedades conmutativa, asociativa y de De Morgan. Por lo general los teoremas 11 al 13 se aplican en combinación, dependiendo de la expresión booleana.
La aplicación de los teoremas es muy sencilla: simplemente se comparan partes de la expresión con los teoremas que permitan hacer más simple la expresión, y esto se realiza hasta que ya no sea posible simplificar.

En general luego de un proceso de simplificación el resultado no siempre es 1, en cambio lo que se espera es obtener una expresión más simple conformada por menos variables.

En los ejemplos anteriores se utilizo un teorema a la vez, y esto se hizo para que no haya confusión en la aplicación de los mismos. Obviamente que cuando ya se tiene suficiente práctica, se pueden aplicar varios teoremas a la vez. Tampoco es necesario indicar qué teorema se usa, sin embargo aquí se hace para ilustrar la simplificación.
Comprensiblemente las expresiones booleanas a simplificar son el resultado del planteamiento de un problema que se busca resolver, tal y como se ilustro al inicio del capítulo con la función booleana
F=A^' B^' C^' D+A^' B^' CD+AB^' C^' D+AB^' CD+AB'CD'
Comúnmente este tipo de expresiones booleanas son factibles de ser simplificadas, como se muestra a continuación:
F=A^' B^' C^' D+A^' B^' CD+AB^' C^' D+AB^' CD+AB'CD'
F=A^' B^' D(C^'+C)+AB^' D(C^'+C)+AB'CD'
F=A^' B^' D+AB^' D+AB'CD'
F=B^' D(A^'+A)+AB'CD'
F=B^' D+AB'CD'
F=B'(D+D'AC)
F=B'(D+AC)
F=B^' D+AB'C

Es conveniente mencionar que con las funciones booleanas se pueden elaborar circuitos equivalentes tanto con la función booleana simplificada como con la que se obtuvo inicialmente, sin embargo el circuito lógico de la función booleana sin simplificar será más grande, complejo y usara mas equipo electrónico en su implementación.

Simplificación de expresiones booleanas usando mapas de Karnaugh
El método del mapa de Karnaugh es un procedimiento simple y directo para minimizar las expresiones booleanas, y fue por supuesto por Edward W. Veitch y modificado ligeramente por Maurice Karnaugh.
El mapa representa un diagrama visual de todas las formas posibles que se puede plantear una expresión booleana en forma normalizada. Al reconocer varios patrones se pueden obtener expresiones algebraicas alternas para la misma expresión, y de éstas se puede escoger la más simple, la cual e general es la que tiene el menor número de variables además de que esta expresión posiblemente no sea única.
Las tablas o mapas se dividen en cierto número de casillas, dependiendo de la cantidad de variables que intervengan en la expresión. El número de casillas se puede calcular con la formula
numero de casillas=2^n
En donde n es el número de variables. Así a una expresión de 2 variables le corresponderá un mapa de 4 casillas, a una de 3 variables un mapa de 8 casillas y así sucesivamente.
Un minitérmino es aquel que forma parte de la expresión y que se puede escribir de la manera más simple formando lo que se conoce en álgebra elemental como un monomio.
Por ejemplo, la expresión
F=X^' Y+XY
Consta de dos minitérminos, X'Y y XY, y como se muestra a continuación en las casillas respectivas de la tabla correspondiente se pone un 1 si el minitérmino se encuentra en la expresión o un 0 si no está:
Y
X 0 1
0 0

1 0 1
Para simplificar la expresión, en la tabla se agrupan los 1 de casillas adyacentes en bloques cuadrados o rectangulares de 2,4,8,16,…,2^n y se descartan las variables cuyo valor, 1 o 0, cambia de una casilla a otra. La regla es agrupar la información con el menor número posible de bloques ya que de cada uno de estos se obtiene cuando menos una literal, y los bloques deben estar conformados por el mayor número de casillas porque entre más grande sea el número de casillas agrupadas por bloque, más simple será la expresión booleana resultante.
En el mapa anterior la variable X no se conserva su valor ya que en la primera línea vale 0 y en la segunda 1, por lo tanto se elimina. Sin embargo, Y mantiene el valor de 1 en ambas casillas, ya que en este caso el bloque que agrupa la información se encuentra solamente en la columna de la derecha. De esta forma se obtiene que la expresión simplificada del mapa de Karnaugh es F=Y.
Como se ve, la simplificación anterior consiste en la aplicación de los postulados del álgebra booleana, pero de manera gráfica.
Para simplificar una expresión que incluye tres variables se tiene que el mapa consta de 8 casillas. Hay que observar que la secuencia en que se coloca la expresión en la tabla no es la binaria ascendente, sino una de forma que solamente existe un cambio de 0 a 1 o de 1 a 0 a la vez, esto es, una en la que no debe cambiar más que un bit en cada paso. A esta forma de arreglar los bits se le llama código reflejado.

En general se tiene que cuando el número de variables que integran la expresión booleana es impar, el número de filas del mapa es menor que el número de columnas. También es conveniente ordenar las variables alfabéticamente colocando las primeras variables como filas y las restantes como columnas.

En el ejemplo anterior se formaron dos bloques, y en el mayor se eliminaron las variables X, Y debido a que de una casilla a otra cambian de valor. Además se observa que entre más grande sea el bloque, la expresión resultante es menor.
Si en un mapa de Karnaugh se unen los dos extremos, ya sea horizontal o verticalmente, entonces las celdas de las esquinas del mismo quedaran juntas y por lo tanto se consideran como celdas adyacentes. Esto permite realizar una mejor simplificación.
A medida que crece el número de variables de la expresión booleana, se hace más complicado el mapa de Karnaugh ya que el número de celdas esta dado por 2^n. Un mapa de 5 variables es equivalente a dos mapas de 4, como se muestra a continuación.


CDE
AB 000 001 011 010 110 111 101 100
00 4
01
11 1
10 X 3 5

Cuanto crece el mapa, también se ve incrementada la cantidad de celdas adyacentes para agrupar la información, Por ejemplo, en un mapa de 4 variables una celda es adyacente a 4 celdas, mientras que en un mapa de 5 variables cada celda tiene 5 celdas adyacentes y así sucesivamente. En el mapa anterior la celda con sombreado oscuro es adyacente a las 5 celdas con sombreado más claro, la celda con la letra X es adyacente a las celdas numeradas con 1, 2, 3, 4, 5, de tal manera que cada celda se puede agrupar para formar un bloque de dos casillas, con cinco celdas de más.
CDE
AB 000 001 011 010 110 111 101 100
00
01
11
10

En el mapa anterior el par de celdas con sombreado oscuro se pueden agrupar con las celdas de sombreado claro para formar un bloque de 4 casillas. Obsérvese como la frontera entre los dos mapas de 4 actúa como espejo.

En algunos mapas de Karnaugh la solución no es única, ya que a veces la información se puede agrupar de manera diferente. Lo que importa al simplificar es obtener la expresión booleana simplificada óptima, independientemente de qué variables son eliminadas. Esto mismo puede suceder con los teoremas del algebra booleana.

COMPUERTAS LÓGICAS
Un bloque lógico es una representación simbólica gráfica de una o más variables de entrada a un operador lógico, para obtener una señal determinada o resultado. Los símbolos varían de acuerdo con la rama donde se utilizan, o bien del fabricante. Cada bloque lógico representa un dispositivo que permite manipular la señal según el campo de acción: en mecánica se les llama válvulas (paso del aire o aceite); en electricidad apagadores, contactos (paso de corriente eléctrica); y en electrónica puertas o compuertas (paso de impulsos eléctricos).
Compuertas básicas:
Compuerta Símbolo
O (Or)

Y (And)

No (Not)

Or-exclusivo


Las compuertas pueden recibir una o más señales de entrada. En la tabla anterior, A y B son señales que entran a la compuerta y pueden tener un valor de 1 o 0 dependiendo de si existe o no la señal, la cual procede de un sensor o bien de la salida de una compuerta anterior. Esos valores de entrada generan una sola salida, que a su vez también es 0 o 1 dependiendo de la compuerta de que se trate y de los valores de las señales de entrada.
Para representar expresiones booleanas mediante compuertas lógicas es conveniente tener en cuenta las tablas de verdad de las compuertas básicas (operadores lógicos) Or, And y Not.
También existen compuertas lógicas compuestas como Nand y Nor, que son una combinación de los operadores Not y And para la primera y Not y Or para la segunda. A continuación se muestran los símbolos correspondientes:
Compuerta Símbolo
Nor

Nand

Xnor


Generalmente los circuitos digitales se construyen con compuertas Nand y Nor, ya que son más fáciles de encontrar en el mercado, son más comunes desde el punto de vista del hardware y están disponibles en la forma de circuitos integrados. Debido a la preferencia de uso de estas compuertas en el diseño de los circuitos, es importante reconocer la relación que existe entre los circuitos construidos con compuertas And, Or y Not y su diagrama equivalente Nand y Nor.
Cuando se simplifica una función el resultado se puede presentar en “sumas de productos” o en “productos de sumas”, y en forma natural la presentación en suma de productos permite una implementación usando compuertas Nand mientras que el producto de sumas se puede representar más fácilmente con compuertas Nor, sin embargo es posible implementar cualquier expresión booleana sólo con compuertas Nand o sólo con compuertas Nor.

APLICACIONES DEL ÁLGEBRA BOOLEANA.
Al álgebra booleana es una extensión de la lógica matemática, ya que utiliza los mismos principios y operadores lógicos (and, or, not, xor, nand, nor) así como los mismos valores, y gracias a esto John Von Neuman crear la computadora de la primera generación.
Los dispositivos con los que se implementan las funciones booleanas se llaman “compuertas”, y al combinarse han permitido inicialmente la creación del “bulbo”, posteriormente la de “transistor” y actualmente la del “chip”, elementos con los cuales se construye todo tipo de aparatos electrónicos digitales.
La electrónica digital es una parte de la electrónica que maneja información codificada en dos únicos estados: “falso” y “verdadero”, o más comúnmente 0 y 1. Electrónicamente se asigna a cada uno un voltaje o rango de voltaje determinado. Esta particularidad permite que, usando el álgebra booleana y con un sistema de numeración binario, se pueden realizar complejas operaciones lógicas o aritméticas sobre señales de entrada. La electrónica digital ha alcanzado una gran importancia debido a que se utiliza en el diseño de sistemas de automatización, robótica, etc., además de que constituye la piedra angular de las computadoras.
Las computadoras llevan a cabo su trabajo por medio de un microprocesador, el cual es un circuito de alta escala de integración (LSI) compuesto por muchos circuitos simples como flip-flops, contadores, decodificadores, comparadores, etc., todos en una misma pastilla de silicio en donde utilizan compuertas del álgebra booleana para llevar a cabo las operaciones lógicas.
Los microoperaciones que lleva a cabo el microprocesador se realizan en lenguaje binario a nivel bit. Por ejemplo, si A=110010, B=011011 entonces el resultado de llevar a cabo las siguientes operaciones en donde intervienen los operadores lógicos (∧,∨,⊕,') es:
A∧B=110010∧011011=010010
A∨B=110010∨011011=111011
A⊕B=110010⊕011011=101001
A^'=(110010)^'=001101
Basada en el álgebra booleana, la unidad lógica aritmética (ALU: Arithmetic Logic Unit) es la parte del microprocesador que realiza las operaciones aritméticas y lógicas en los datos.
Se sabe que en toda computadora está integrada por las memorias ROM (Read Only Memory: Memoria de sólo lectura) y RAM (Random Access Memory: Memoria de acceso aleatorio). Cuando arranca una computadora, ésta debe saber qué hacer, lo cual implica que pueda correr un pequeño programa que le indique lo que debe realizar, qué programas debe ejecutar y en qué lugar debe comenzar. Esta información se guarda en un pequeño programa de solo lectura que recibe el nombre de ROM, el cual está en lenguaje binario y utiliza operadores lógicos del álgebra booleana para la manipulación de la información. La información en este caso se graba electrónicamente y se borra también de la misma manera. Este tipo de memoria se llama Memoria ROM programable electrónicamente (EEPROM). En las computadoras ésta se encuentra en lo que se llama BIOS, la cual es una memoria donde se guarda información de la “tarjeta madre” de los conectores y dispositivos de la PC.