Algebra Booleana

ALGEBRA BOOLEANA

INTRODUCCIÓN

Las aplicaciones de la electrónica digital a los procesos de control y automatismo industriales y a la computación, están fundamentadas teóricamente en el sistema matemático denominado álgebra booleana.

Los círculos digitales o lógicos operan de un modo binario donde cada voltaje (señal) de entrada o de salida es un cero (9) o un uno (1). Las designaciones 0 y 1 representan intervalos predefinidos de voltaje. Esta característica de los circuitos lógicos permite emplear el álgebra booleana en el análisis y diseño de sistemas digitales. En este capítulo se estudiarán las compuertas lógicas, que son los circuitos lógicos fundamentales cuyo funcionamiento puede describirse mediante el uso del álgebra booleana. Las combinaciones de estas compuertas conforman circuitos lógicos cuyas salidas son las respuestas deseadas para propósitos de automatismo y control.

VARIABLES Y CONSTANTES BOOLEANAS

Las variables y constantes del álgebra booleana sólo pueden tener dos valores posibles: cero (0) y uno (1). Una variable booleana, denominada también variable lógica, puede, en diferentes ocasiones, ser igual a 0 ó a 1. las variables booleanas se emplean para representar el nivel de voltaje presente en los terminales de entrada y salida de un circuito. A este nivel de voltaje también se llama El “nivel lógico” de la variable. Cuando este nivel de voltaje es bajo (entre 0 y 0.8 voltios) se emplean los términos: falso, desactivado, no, interruptor abierto (0). Cuando el nivel lógico es alto (por ejemplo, entre 4 y 5 voltios) se usan las palabras: verdadero, activado, si, interruptor cerrado (1).

El álgebra booleana se utiliza para describir los efectos que producen las entradas lógicas sobre los diversos circuitos digitales (circuitos lógicos). También se usa para manipular variables lógicas en la determinación del método de ejecución de una cierta función de un circuito.

Las operaciones del álgebra booleana son:

Adición o suma lógica

También llamada operación OR, o simplemente OR. Corresponde a la disyunción de proposiciones en lógica y a la unión de conjuntos; su símbolo es (+). El dispositivo electrónico que ejecuta esta operación se denomina compuerta OR y su representación es:

Multiplicación o producto lógico.

Llamada también operación AND o simplemente AND. Corresponde a la conjunción de proposiciones en lógica y a la intersección de conjuntos; su símbolo es el punto (.). El dispositivo electrónica que ejecuta esta operación se llama compuerta AND y su representación es:

Complementación o inversión lógica

Denominada también operación NOT, corresponde a la negación de una proposición en lógica o a la operación de complementación en conjuntos. Se simboliza con apóstrofo en la variable complementada. El dispositivo electrónico que ejecuta esta operación es un inversor y su representación es:

Lógica Disyunción Conjunción Negación

p Ú q p Ú q ~ p

Conjuntos Unión Intersección Complemento

A È B A Ç B A’

Algebra Suma Producto Inversor

Booleana x + y xy x’

Compuertas OR AND NOT

lógicas

Tabla 4.1.

La tabla 4.1. muestra las correspondencias mencionadas. Las propiedades o leyes que se cumplen para estas operaciones en lógica y en conjuntos son válidas también para las correspondientes operaciones del álgebra booleana.

DEFINICIÓN DEL ÁLGEBRA BOOLEANA

Una definición del álgebra booleana como un sistema axiomático consistente, completo e independiente fue dada por E.V. Huntington en 1904.

La definición formal es la siguiente:

Un álgebra booleana es un sistema matemático que comprende: un conjunto B, con al menos dos elementos; dos operaciones binarias, la suma y el producto (+ y.), y una operación unitaria, la complementación, definidas para todos los x, y, z elementos de B, tales que se cumplen los siguientes axiomas:

P1: las operaciones suma y producto lógico son conmutativas:

x + y = y + x xy = yx Leyes conmutativas

P2: cada operación es distributiva respecto a la otra:

x + yz = (x + y)(x + z) Leyes distributivas

x(y + z) = xy + xz

P3: existen elementos individuales 0 y 1, tales que:

x + 0 = x x.1 = x Leyes modulativas

P4: para todo x Î B existe el elemento x’ llamado el complemento de x,

o la negación de x, tal que:

x + x’ = 1 x.x’ = 0 Leyes del complemento

Sobre la anterior definición caben las siguientes observaciones:

1. Tanto la lógica matemática como la teoría de conjuntos cumplen con la definición de álgebra booleana por son sistemas axiomáticos similares.

2. La definición de álgebra booleana no hace mención del axioma de asociatividad de las operaciones suma y producto lógico, porque éste no es independiente de los cuatro postulados citados, sino que es deducible de ellos. La ley o propiedad asociativa de las operaciones suma y producto lógico se escribe:

Para todo x, y, z elementos de B se verifica que:

x + (y + z) = (x + y) + z = x + y + z

x(yz) = (xy)z = xyz

3. En cada axioma de la definición aparecen dos expresiones. Cada una puede obtenerse de la otra intercambiando + por . y 0 por 1. por esta razón se denominan expresiones duales. Cada uno de los axiomas y teoremas del álgebra booleana tiene la propiedad de tener su dual.

PROPIEDADES DEL ÁLGEBRA BOOLEANA

Otras propiedades o leyes del álgebra booleana empleadas en los procesos de simplificación de expresiones booleanas o en la demostración de teoremas, son:

Ley de idempotencia:

x + x = x x.x = x

Ley de acotación:

x + 1 = 1 x.0 = 0

Ley de absorción:

x + xy = x x(x + y) = x

Ley de involución:

(x’)’ = x (0’)’ = 0 (1’)’ = 1

Ley de De Morgan:

(x + y)’ = x’.y’ (x.y)’ = x’ + y

La representación de algunos axiomas y teoremas del álgebra booleana se puede realizar con compuertas lógicas como se demuestra en la tabla 4.2:

Nombre Ley Ley dual

Modulativa x + 0 = x x.1 = x

Complemento x + x’ = 1 x.x’ = 0

Ley de idempotencia: x + x = x x.x = x

Ley de acotación: x + 1 = 1 x.0 = 0

Ley de absorción: x + xy = x x(x + y) = x

Ley de involución: (x’)’ = x (0’)’ = 0

Ley de D’Morgan: (x + y)’ x’.y’

Ley de D’Morgan: (x.y)’ = x’ + y’

Tabla 4.2

RELACIÓN DE ORDEN EN UN ÁLGEBRA BOOLEANA

El conjunto B, con al menos dos elementos, debe ser parcialmente ordenado. Esto quiere decir que sus elementos deben cumplir con las propiedades de la relación de orden: reflexiva, antisimétrica y transitiva.

La relación de orden parcial £ (menor o igual) en un conjunto B, por ser parcialmente ordenado, cumple las siguientes propiedades:

Para todo x, y,z elementos de B:

Reflexiva: x £ x

Antisimétrica: x £ y Ù y £ x ® x = y

Transitiva: x £ y Ù y £ z ® x £ z

El conjunto potencia de B o de partes de B es un conjunto parcialmente ordenado que cumple las condiciones de la definición de un álgebra booleana. En este caso el cero (0) es el conjunto vacío Æ y el uno (1) es el mismo conjunto B. La relación de orden es la de inclusión de conjuntos.

Establecida la relación de orden parcial anterior, se puede enunciar:

Definición:

En un álgebra de Boole:

x £ y si y solo si x + y = y

Para indicar que el elemento y es mayor que x, se emplea el diagrama (línea dirigida de x hacia y)

• y

• x

Así 0 £ 1 porque 0 + 1 = 1

En un álgebra de Boole, las siguientes afirmaciones son equivalentes:

Si x £ y, entonces:

1. x + y = y

2. x.y’ = 0

3. x.y = x

4. x’ + y = 1

EXPRESIONES BOOLEANAS

Una expresión booleana (función booleana o función lógica) es un conjunto finito de símbolos, cada uno representa una constante o una variable, combinados mediante las operaciones de suma, producto o complementación. Por ejemplo, la expresión x + x’ = 1 representa la proposición de que esta función de

...