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

Elementos y operadores lógicosEditar

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 postuladosEditar

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

TeoremasEditar

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

 

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ógicasEditar

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
     
    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
     

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

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:

 

De las combinaciones para las cuales la función F toma el valor 0 se obtiene el producto de MAXTERMS:

 

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 complementariaEditar

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:

 

Producto de MAXTERMS:

 

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.