Algebra de boole
Matemáticas discretas
Lázaro Alvarado Cano
Instituto Tecnológico Superior de san Luis Potosí Capital ITTSSLPC.
ANTONIO CASTRO ROQUE
[email protected] Algebra de Boole.
El álgebra de Boole es una herramienta diseñada para poder representar
proposiciones lógicas en forma algebraica. Desarrollada originalmente
en 1847 por George Boole.
Actualmente, esta álgebra es utilizada ampliamente en el diseño y
simplificación de sistemas digitales binarios, es decir, sistemas que
basan todo su comportamiento en los valores {0,1}.
El álgebra de Boole ha sido de gran utilidad para poder generar circuitos
lógicos eficientes y simplificados en su mínima expresión, ¿Qué significa
esto?
Un circuito digital está compuesto por un conjunto de entradas con
valores binarios, las combinaciones que se pueden formar por medio de
estas entradas determinarán el comportamiento que se tendrá en la o
las salidas del sistema, es decir, tenemos un conjunto de actuadores de
salida dependientes del comportamiento de las variables de entrada.
Dependiendo del número de variables de entrada, se tiene el número de
combinaciones que se pueden generar por medio de NC=2n, dónde n es
el número de entradas, sin embargo, el número de salidas puede ser
definido sin ninguna restricción.
Las combinaciones mencionadas pueden ser representadas por medio
de funciones lógicas o algebraicas, por ejemplo, la combinación de
entrada 0101 puede ser representada por medio de la función A―BC―D,
donde la barra por encima de una variable indica que tiene un valor
negado o 0. La suma de estas combinaciones genera ecuaciones lógicas
extensas que tienen el mismo comportamiento lógico que una expresión
más pequeña, por ejemplo, la siguiente suma de funciones:
S=A―B―CD+A―BC+C⋯⋯ (1)
Tiene el mismo comportamiento lógico que la función
S=A―C (2) ⋯⋯
Es fácil notar, que la segunda función es mucho más simple que la
primera. Esta simplificación se logra aplicando los axiomas lógicos
booleanos a la primera de las funciones presentadas.
La realización de la simplificación en una función lógica no sólo impacta
en la función matemáticas, sino que impacta en el gasto realizado en
espacio y monetario, ya que entre más elementos tenga una función
lógica, en el momento de construir un circuito lógico, se tendrán más
componentes, utilizando mayor espacio en su construcción, y
obviamente, invirtiendo mayor cantidad monetaria en la adquisición e
instalación de los mismos.
Existen 3 compuertas lógicas básicas, sobre las cuales cae el diseño de
cualquier circuito lógico, la compuerta AND, OR y NOT. Cada operación
que se marca sobre una función booleana, corresponde a una
compuerta; A la compuerta OR, le corresponde la suma; A la compuerta
AND, le corresponde la multiplicación; A la compuerta NOT, le
corresponde la negación. Si contamos el número de sumas,
multiplicaciones y negaciones que contiene una función, se puede saber
la cantidad de compuertas necesarias para implementar tal función. Por
ejemplo, la función (1) requiere 2 compuertas OR, 6 compuertas AND y 4
compuertas NOT (Considerando compuertas lógicas de dos entradas),
mientras que la función (2) requiere solamente una compuerta AND y
una compuerta NOT.
Debido a que, para la realización de las funciones lógicas podemos
utilizar las combinaciones de variables que den como resultado 1, o las
combinaciones que den como resultado 0, las funciones booleanas se
pueden expresar como suma de productos o producto de sumas,
respectivamente. Una suma de productos está definida en la
forma S=A―BC+AB―C―+ABC―, mientras que un producto de sumas
está definido por S=(A―+B+C) (A+B―+C―) (A+B+C―).
Teoremas y postulados del Algebra booleana.
TEOREMA 1: el elemento complemento A’ es único.
TEOREMA 2 (ELEMENTOS NULOS): para cada elemento de B se verifica:
A+1 = 1
A·0 = 0
TEOREMA 3: cada elemento identidad es el complemento del otro.
0’=1
1’=0
TEOREMA 4 (IDEMPOTENCIA): para cada elemento de B, se verifica:
A+A=A
A·A=A
TEOREMA 5 (INVOLUCIÓN): para cada elemento de B, se verifica:
(A’)’ = A
TEOREMA 6 (ABSORCIÓN): para cada par de elementos de B, se verifica:
A+A·B=A
A·(A+B) =A
TEOREMA 7: para cada par de elementos de B, se verifica:
A + A’·B = A + B
A · (A’ + B) = A · B
TEOREMA 8 (ASOCIATIVIDAD): cada uno de los operadores binarios (+) y
(·) cumple la propiedad asociativa:
A+(B+C) = (A+B) +C
A·(B·C) = (A·B) ·C
Postulado 1. El elemento identidad de la suma es el "0". (A + 0 = A)
Postulado 2. El elemento de identidad del producto es el "1". (A · 1 = A)
Postulado 3. La suma es conmutativa A + B = B + A
Postulado 4. El producto es conmutativo: A · B = B · A
Postulado 5. La suma es asociativa: (A + B) + C = A + (B + C)
Postulado 6. El producto es asociativo: (A · B) · C = A · (B · C)
Postulado 7. El producto es distributivo respecto de la suma:
A · (B + C) = (A · B) + (A · C)
Postulado 8. La suma es distributiva respecto del producto:
A + (B · C) = (A + B) · (A + C).
Postulado 9. Para cada valor A existe un valor Ā tal que A· Ā = 0 y A + Ā
= 1. Este valor es el complemento lógico o negado de A.
Postulado 10. El álgebra de Boole es cerrada bajo las operaciones suma,
producto y negación.
Aplicaciones del algebra booleana.
El álgebra de Boole encuentra aplicaciones en una amplia variedad de
áreas:
Diseño de circuitos digitales: procesadores, memorias y dispositivos
lógicos programables.
Programación y algoritmos: el álgebra permite la toma de decisiones y el
control del flujo de ejecución en los programas.
Sistemas de control y automatización: se utiliza en la modelización y
diseño de sistemas de control, como en la industria manufacturera.
Criptografía: los principios del álgebra de Boole se aplican en algoritmos
criptográficos, proporcionando la base matemática para la seguridad de
la información y el cifrado de datos.
Minitérminos y Maxitérminos
Minitérmino: Es un producto booleano en la que cada variable aparece
sólo una vez; es decir, es una expresión lógica que se compone de
variables y los operadores lógicos AND y NOT. P. ejem. ABC y AB’C.
Maxitérmino: Es una expresión lógica que se compone de variables y los
operadores lógicos OR y NOT. P. ejem. A+B’+C y A’+B+C.
Representación de expresiones booleanas con circuitos lógicos
Un circuito lógico es un dispositivo que tienen una o más entradas y
exactamente
una salida. En cada instante cada entrada tiene un valor, 0 o 1; estos
datos son
procesados por el circuito para dar un valor en su salida, 0 o 1.
Los valores 0 y 1 pueden representar ciertas situaciones físicas como,
por
ejemplo, un voltaje nulo y no nulo en un conductor.
Los circuitos lógicos se construyen a partir de ciertos
circuitos elementales denominados compuertas lógicas, entre las cuales
diferenciaremos:
•Compuertas lógicas básicas: OR, AND, NOT.
•Compuertas lógicas derivadas: NOR, NAND.
Compuerta OR
En una compuerta OR con entradas A y B, la
salida Y resulta:
Y= A+ B
donde la suma se define por la siguiente tabla:
A B Y=A+B
000
011
101
111
La compuerta OR se representa del siguiente modo:
La compuerta OR también puede tener más de dos entradas:
donde la salida Y=A+B+C+D puede obtenerse asociando los sumandos:
Y=A+B+C+D = (A+B) +(C+D) = ((A+B) +C) +D
Compuerta AND
En una compuerta AND con entradas A y B, la salida Y resulta:
Y =A*B
donde el producto se define por la siguiente tabla:
A B Y=A*B
000
010
100
111
La compuerta AND se representa del siguiente modo:
La compuerta AND también puede tener más de dos entradas:
donde la salida Y=A*B*C*D puede obtenerse asociando los factores:
Y =A*B*C*D = (A*B) *(C*D) = ((A*B) *C) *D
Compuerta NOT
En una compuerta NOT con entrada A, la salida Y resulta:
Y =A
donde el complemento se define por la siguiente tabla:
AY
10
01
La compuerta NOT se representa del siguiente modo:
Compuertas NOR y NAND
Las compuertas NOR y NAND no son básicas. Una compuerta NOR
equivale a
una compuerta OR seguida de una compuerta NOT. Una compuerta
NAND equivale a una compuerta AND seguida de una compuerta NOT.
Por lo tanto, cuando las entradas son A y B, las salidas de estas
compuertas
resultan:
NOR: Y = A+B
NAND: Y = A*B
Circuitos lógicos
Los circuitos lógicos se forman combinando compuertas lógicas. La
salida de un
circuito lógico se obtiene combinando las tablas correspondientes a sus
compuertas componentes.
