Álgebra De Boole

Álgebra de Boole

El álgebra de boole es un sistema matemático constituido por:

-Dos operaciones binarias, la suma y el producto

-Un conjunto B con al menos dos elementos

-Una operación unitaria, la complementación

Definidas para todos los elementos x, y, z de B; tal que se cumplen los axiomas:

A1: La suma y el producto lógico son operaciones conmutativas

x + y=y + x; xy = xy Leyes conmutativas

A2: Cada operación es distributiva respecto a la otra

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

x (y + z) = xy +xz

A3: El conjunto B tiene dos elementos 0 y 1, tal que:

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

A4: Para todo x € B existe un x’ € B, llamado el complemento o la negación de x, tal que:

x + x’= 1; x.x’ = 0 Leyes de complemento

Observaciones:

Las leyes anteriores pueden ser reformuladas si se sustituyen las variables lógicas por conjuntos o por proposiciones. Cuando sustituimos los signos + y . por los símbolos de unión e intersección se obtienen las correspondientes leyes de conjuntos. Por ejemplo cambiando x, y por A, B el axioma A1 se escribirá:

A B = B A; A B = B A

que es la ley conmutativa para conjuntos. Cuando sustituimos + y . por los simbolos de disyunción ˅ y conjunción ˄ se obtienen las leyes correspondientes en lógica proporcional. Por ejemplo. El cambiar x, y, z por p,q,r. el axioma A2 se escribirá:

p˅(q˄r) ↔ (p˅q) ˄ (p˅r)

p˄(q˅r) ↔ (p˄q) ˅ (p˄r)

Los números 0 y 1 se cambian por los conjuntos vacio ∅ y universal U; para obtener las correspondientes leyes de la teoría de conjuntos y de la lógica matemática; esto significa que el álgebra de conjuntos y el álgebra de proposiciones de la lógica matemática son sistemas axiomáticos análogos al sistema del álgebra lógica.

En la definición de álgebra booleana no se incluye la ley de asociatividad de la suma y del producto lógico, debido a que dicha ley se puede deducir a partir de los axiomas mencionados (la ley asociativa de la suma y el producto no es independiente de tales axiomas), es decir, la ley asociativa es un teorema, no un axioma.

Las propiedades algebraicas de los operadores lógicos (+, ., ,) (AND, OR, NOT) se denominan también leyes; las leyes que se refieren a este conjunto de operadores vienen expresadas por pares; cada una de ellas es la ley “dual” de la otra. Esta propiedad se expresa mediante el siguiente teorema de dualidad: sean x y y variables booleanas expresadas con el conjunto de operaciones {AND, OR, NOT}. La expresión dual Ad es una expresión booleana obtenida de A por el intercambio de la conectiva AND por la OR y viceversa.

Nótese que (Ad)d=A. El teorema establece que:

A- Si es verdadero, ~ (Ad) es verdadero

B- Si → B es verdadero, entonces Bd → Ad es verdadero

C- Si ↔ B es verdadero, entonces Ad ↔ Bd es verdadero

Por ejemplo: la expresión dual de la ley modulativa

x + 0= x es x.1 = x

Tipos de funciones booleanas

Las funciones lógicas constituyen la base para el diseño de los circuitos lógicos,

Teoremas del algebra de boole

Para la demostración de teoremas y la simplificación de expresiones booleanas se utilizan las siguientes propiedades o leyes del álgebra boolena:

Leyes de asociatividad:

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

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

Leyes de idempotencia:

x + x = x; xx = x

Leyes de acotación:

x + 1 = 1; x.0 = 0

Leyes de absorción:

x + x y = x; x(x + y) = x

Leyes de involución:

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

Leyes de D’Morgan:

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

Para facilitar la comprensión de las leyes anteriores se puede recurrir a la teoría de conjuntos. Por ejemplo, la ley de absorción x + xy = x se traduce a A (A B) = A, donde es obvio que al unir el conjunto A con el conjunto A B que está incluido en (o absorbido por) el conjunto A, el resultado es el mismo conjunto A.

Funciones booleanas de dos variables

El número total de funciones lógicas básicas que se pueden escribir con n variables es 22. Para n = 2 variables x y y se pueden escribir =24 = 16 funciones lógicas básicas, cada una de las cuales se denota FI con i = 0, 1,…, 15. En la tabla se presentan funciones ordenadas desde F0 hasta hasta F15 y enseguida de cada FI aparece escrito el numero binario 4bits equivalente a cada decimal i; o sea la tabla de verdad correspondiente a cada función. Notar que FI ⌐F’j si i+j ⌐15, es decir que, las funciones se pueden agrupar por pares mutuamente complementarios, así F0 = F’15 y F15 = F’0; las funciones constantes F0 = 0 y F15 = 1 son las funciones falsa y verdadera, respectivamente; F1 = x

Tabla de verdad de la función f(x,y) = xy’ + x’y’

Funciones lógicas de dos variables. Expresiones equivalentes y compuertas

y, y F14 = (x y)’ son AND y NAND; F2 = x y’ , y F13 = x’ + y son las negación de la implicación diresta y la misma implicación directa; F3 = x y F12 = x’ son la variable x, y su negación contraria y la misma implicación contraria; F5 = y, y F10 = y’ la variable y, y su negación; F6 =x’y + xy’ , y F9 =x’y’ + xy son XOR y XNOR;

F7 = x + y, y F8 = (x + y)’ son OR y NOR.

...