Diseño de circuitos digitales y tecnología de computadores/Álgebra de Boole

Elementos y operadores lógicos

El álgebra de Boole se compone de un conjunto de dos elementos o estados mútuamente excluyentes, que en el caso de los sistemas digitales es {0,1}, aunque en otros campos de aplicación puede ser distinto (por ejemplo, en lógica se utilizan los valores VERDADERO y FALSO). Por lo tanto, en los sistemas digitales, las variables lógicas o booleanas pueden tomar sólo el valor 0 o el 1. Físicamente estos dos estados se implementan mediante dos valores o rango de valores de una variable física, usualmente voltaje, por ejemplo, de 0 a 3 voltios para designar el 0, y de 4 a 5 voltios para designar el 1.

Sobre los elementos y variables lógicas se pueden realizar las siguientes operaciones:

Operación	Notación matemática	Función lógica	Significado
Suma	A+B	OR	A+B vale 1 sólo cuando A o B o ambas valen 1
Producto	A·B	AND	A·B vale 1 sólo cuando A y B valen 1
Complemento	A	NOT	Conmuta (cambia) el estado de la variable

En la práctica el operador del producto lógico (·) se suele omitir, por lo que la expresión A·B se escribe AB.

Propiedades o postulados

Propiedad conmutativa

• de la suma: A+B = B+A
• del producto: AB = BA

Propiedad distributiva

• del producto respecto de la suma: A(B+C) = AB+AC
• de la suma respecto del producto: A+(BC) = (A+B)(A+C)

Elemento neutro

• de la suma: A+0 = A
• del producto: A·1 = A

Elemento simétrico, inverso o complementario

• de la suma: A + A = 1
• del producto: A · A = 0

Teoremas

Se pueden demostrar, bien algebraicamente mediante los postulados, o bien mediante una tabla de verdad.

Principio de dualidad

Si en los postulados se intercambian las operaciones suma y producto lógico, y los valores 0 y 1, los resultados siguen siendo válidos. Ejemplos:

A+0 = A ↔ A·1 = A

A(B+C) = AB+AC ↔ A+BC = (A+B)(A+C)

Debido a este principio, cualquier postulado o teorema tiene dos versiones, duales entre sí.

Elemento idempotente

A+1 = 1

A·0 = 0

Idempotencia

A+A=A

A·A=A

Absorción o redundancia

A + AB = A

A(A+B) = A

Asociación

A+(B+C) = (A+B)+C = A+B+C

A(BC) = (AB)C = ABC

Involución o doble negación

${\overline {\overline {A}}}=A$

Teoremas de DeMorgan

A+B = A · B

A·B = A + B

También se aplica para más de dos elementos:

A+B+C = A · B · C

ABC = A + B + C

Los teoremas de DeMorgan se utilizan cuando se desea que en una expresión algebraica aparezca un único tipo de operación (suma o producto lógico).

Otro teorema

A + A·B = A+B

A · (A + B) = A·B

Funciones lógicas

Una función lógica es una variable binaria que depende de otras variables binarias que se relacionan entre sí mediante las operaciones elementales del álgebra de Boole (suma, producto e inversión). Ejemplo:

F(A,B,C) = A B C + A B C + B C

Término canónico es todo producto o suma en el que aparecen todas las variables de la función, directas o negadas. Hay dos tipos:

• Producto canónico (MINTERM): es un término a través del cual la función toma el estado lógico 1; en él las variables se relacionan por el producto lógico.
• Suma canónica (MAXTERM): es un término a través del cual la función toma el estado lógico 0; en él las variables se relacionan por la suma lógica.

Una función es canónica cuando se expresa con los términos canónicos, en una de las siguientes formas algebraicas:

• Suma de MINTERMS. Ejemplo: F(A,B,C) = A B C + A B C + A B C
• Producto de MAXTERMS. Ejemplo: G(A,B,C) = (A+B+C)(A+B+C)(A+B+C)

La forma numérica de una función canónica consiste en sustituir cada término canónico por un equivalente decimal:

1. Dada una función que depende de tres variables A, B y C, asignamos a éstas pesos correlativos en el sistema de numeración binario a partir del peso menor o LSB (peso = 1). Por ejemplo, A será la variable de menor peso (1), B tendrá peso 2 y B será la variable de mayor peso (4).
2. Cada variable puede tomar el valor 0 o 1 con respecto a un término canónico de acuerdo con el siguiente criterio:
   • MINTERM: x ≡ 1, x ≡ 0
   • MAXTERM: x ≡ 0, x ≡ 1
3. Los números binarios así formados se transforman en decimal, expresando el resultado como sumatorio de MINTERMS o productorio de MAXTERMS:
   
   F(A,B,C) = A B C + A B C + A B C
   C B A ≡ 001 ≡ 1
   C B A ≡ 110 ≡ 6
   C B A ≡ 111 ≡ 7
   $F=\sum _{3}(1,6,7)$
   G(A,B,C) = (A+B+C)(A+B+C)(A+B+C)
   C+B+A ≡ 111 ≡ 7
   C+B+A ≡ 010 ≡ 2
   C+B+A ≡ 101 ≡ 5
   $G=\prod _{3}(2,5,7)$

Conversión de una función lógica a forma canónica

Mediante la tabla de verdad

A B C F(A,B,C) 0 0 0 0 1 1 0 0 1 0 2 0 1 0 0 3 0 1 1 1 4 1 0 0 1 5 1 0 1 1 6 1 1 0 0 7 1 1 1 0

De las combinaciones para las cuales la función F toma el valor 1 se obtiene la suma de MINTERMS: $F={\overline {C}}\cdot {\overline {B}}\cdot {\overline {A}}+{\overline {C}}\cdot B\cdot A+C\cdot {\overline {B}}\cdot {\overline {A}}+C\cdot {\overline {B}}\cdot A=\sum _{3}(0,3,4,5)$ De las combinaciones para las cuales la función F toma el valor 0 se obtiene el producto de MAXTERMS: $F=(C+B+{\overline {A}})(C+{\overline {B}}+A)({\overline {C}}+{\overline {B}}+A)({\overline {C}}+{\overline {B}}+{\overline {A}})=\prod _{3}(1,2,6,7)$

Mediante transformaciones algebraicas

Suma de MINTERMS

1. Expresar la función no canónica en una suma de productos que pueden ser canónicos o no:
   F = A(B+C) = AB + AC
2. Los términos no canónicos se multiplican por la suma de la variable directa y negada que no figura en ese producto. A continuación se aplica el primer paso. Si hubiera algún término repetido se elimina.
   F = AB(C+C) + AC(B+B) = ABC + ABC + ABC + ABC = ABC + ABC + ABC

Producto de MAXTERMS

1. Expresar la función en un producto de sumas canónicas o no (se aplica la propiedad distributiva de la suma respecto del producto).
   F = A+BC = (A+B)(A+C)
2. A cada suma no canónica se le suma el producto de la variable directa y negada que no figura en esa suma. A continuacion se aplica el primer paso. Si hubiera algún término repetido se elimina.
   F = (A+B)(A+C) = [(A+B)+CC] [(A+C)+BB] = (A+B+C)(A+B+C)(A+C+B)(A+C+B) = (A+B+C)(A+B+C)(A+B+C)

Función inversa o complementaria

La inversa de una función lógica se puede obtener a partir de su tabla de verdad, de su forma numérica o de su forma algebraica.

Mediante la tabla de verdad

A	B	C	F	F
0	0	0	1	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	1	0
1	1	0	0	1
1	1	1	0	1

A partir de la forma numérica

Suma de MINTERMS:

$F=\sum _{3}(0,3,4,5)$

Producto de MAXTERMS:

${\overline {F}}=\prod _{3}(0,3,4,5)$

A partir de la forma algebraica

En este caso no se precisa que la función sea canónica. Se aplican los teoremas de DeMorgan.

$F={\overline {C}}\cdot {\overline {B}}\cdot {\overline {A}}+{\overline {C}}\cdot B\cdot A+C\cdot {\overline {B}}\cdot {\overline {A}}+C\cdot {\overline {B}}\cdot A$

${\overline {F}}$	$={\overline {{\overline {C}}\cdot {\overline {B}}\cdot {\overline {A}}+{\overline {C}}\cdot B\cdot A+C\cdot {\overline {B}}\cdot {\overline {A}}+C\cdot {\overline {B}}\cdot A}}$
	$={\overline {{\overline {C}}\cdot {\overline {B}}\cdot {\overline {A}}}}\cdot {\overline {{\overline {C}}\cdot B\cdot A}}\cdot {\overline {C\cdot {\overline {B}}\cdot {\overline {A}}}}\cdot {\overline {C\cdot {\overline {B}}\cdot A}}=(C+B+A)(C+{\overline {B}}+{\overline {A}})({\overline {C}}+B+A)({\overline {C}}+B+{\overline {A}})$