Álgebra booleana


Conceptos básicos.

Los conjuntos y las proposiciones satisfacen leyes semejantes. Estas leyes sirven para definir una estructura matemática abstracta denominada álgebra booleana, en honor del matemático George Boole (1815-1864).

Conectivos lógicos.






Una compuerta AND se dibuja como se indica en la figura


Una compuerta OR se dibuja como se indica en la figura.

Una compuerta NOT se dibuja como se indica en la figura.

A continuación aparecen las tablas lógicas para los circuitos AND, OR y NOT básicos

Álgebras booleanas y circuitos combinatorios

Un circuito combinatorio.

La tabla lógica para este circuito combinatorio es la siguiente.

Observe que se listan todas las combinaciones posibles de los valores de las entradas
x1, x2 y x3. Para un conjunto determinado de entradas, el valor de la salida y se calcula rastreando
el flujo a través del circuito. Por ejemplo, la cuarta línea de la tabla da el valor de
la salida y para los valores de entrada.

Si  la salida de la compuerta AND es 0. Como  las estradas a la compuerta OR  son ambas 0.Por lo tanto, la salida de la compuerta OR es 0. Como la entrada a la compuerta NOT es 0, se produce una salida

 

 

 

Los circuitos combinatorios individuales se pueden interconectar. Es posible combinar los circuitos combinatorios como se muestra en la figura.

Ejemplo.

Encuentre el circuito combinatorio correspondiente a la expresión booleana y escriba la tabla lógica para el circuito obtenido.

Se comienza con la expresión en el paréntesis interior. Esta expresión se convierte en un circuito combinatorio como el mostrado en la figura.

 

Se aplica AND a la salida de este circuito y  para producir el circuito dibujado en la figura.

Por último, se aplica OR a la salida de este circuito y  para dar el circuito deseado de la figura.

La tabla lógica es la que sigue.

Un álgebra booleana B consiste en un conjunto S que contiene elementos distintos 0 y 1, operadores binarios + y · en S, y un operador unitario en S que satisface las siguientes leyes.
Como es costumbre, suele abreviarse a · b como ab. También se supone que · se evalúa antes que +. Esto permite eliminar algunos paréntesis. Por ejemplo, (xy) + z se escribe de manera más sencilla como xy + z.
Es adecuado hacer algunos comentarios respecto a la definición 11.3.1. En primer lugar, 0 y 1 son sólo nombres simbólicos y, en general, no tienen relación con los números 0 y 1. Este mismo comentario se aplica a + y ·, que sólo denotan operadores binarios y, en general, no tienen relación con la suma y multiplicación comunes.
En un álgebra booleana, el elemento  recibe el nombre de complemento de x.


Si U es un conjunto, P(U) se puede considerar un álgebra booleana. Por lo tanto, las leyes de Morgan, que para conjuntos se pueden enunciar.

Se cumplen. Estas ecuaciones se verifican de manera directa. las ecuaciones que incluyen elementos de un álgebra booleana vienen en pares. Por ejemplo, las leyes de identidad son.

Se dice que estos pares son duales.
El dual de una afirmación que incluye expresiones booleanas se obtiene sustituyendo 0 por  1, 1 por 0, + por · y · por +.
Cada condición en la definición de álgebra booleana incluye su dual. Por lo tanto, se tiene el siguiente resultado.


Funciones booleanas y simplificación de circuitos

Un circuito permite realizar una tarea específica. Si se quiere construir un circuito combinatorio, el problema puede darse en términos de entradas y salidas. Por ejemplo, suponga que se desea construir un circuito combinatorio para calcular el OR-exclusivo de x1 y x2. Se puede establecer el problema haciendo una lista de las entradas y salidas que define el OR-exclusivo. Esto equivale a elaborar la tabla lógica deseada.
Una tabla lógica, con una salida, es una función. El dominio es el conjunto de entradas y el recorrido o imagen es el conjunto de salidas. Para la función OR-exclusivo dada en la tabla.

Si se pudiera desarrollar una fórmula para la función OR-exclusivo de la forma donde X es un expresión booleana, se podría resolver el problema de la construcción del circuito combinatorio. Se podría simplemente construir el circuito correspondiente a X.
Las funciones que se pueden representar por expresiones booleanas se llaman funciones booleanas.