El álgebra booleana es un sistema matemático deductivo centrado en los valores cero y uno

Algebra Booleana

El álgebra booleana es un sistema matemático deductivo centrado en los valores cero y uno (falso y verdadero). Un operador binario " º " definido en éste juego de valores acepta un par de entradas y produce un solo valor booleano, por ejemplo, el operador booleano AND acepta dos entradas booleanas y produce una sola salida booleana.

Para cualquier sistema algebraico existen una serie de postulados iniciales, el álgebra booleana a menudo emplea los siguientes postulados:

• Cerrado. El sistema booleano se considera cerrado con respecto a un operador binario si para cada par de valores booleanos se produce un solo resultado booleano.

• Conmutativo. Se dice que un operador binario " º " es conmutativo si A º B = B º A para todos los posibles valores de A y B.
  
• Asociativo. Se dice que un operador binario " º " es asociativo si (A º B) º C = A º (B º C) para todos los valores booleanos A, B, y C.
  
• Distributivo. Dos operadores binarios " º " y " % " son distributivos si A º (B % C) = (A º B) % (A º C) para todos los valores booleanos A, B, y C.
  
• Identidad. Un valor booleano I se dice que es un elemento de identidad con respecto a un operador binario " º " si A º I = A.
  
• Inverso. Un valor booleano I es un elemento inverso con respecto a un operador booleano " º " si A º I = B, y B es diferente de A, es decir, B es el valor opuesto de A.

- Los dos posibles valores en el sistema booleano son cero y uno.

- El símbolo · representa la operación lógica AND.

- El símbolo "+" representa la operación lógica OR.

- El complemento lógico, negación o NOT es un operador unitario, utilizaremos el símbolo " ' " para denotar la negación lógica.

Teoremas:

Teorema 1: A + A = A

Teorema 2: A · A = A

Teorema 3: A + 0 = A

Teorema 4: A · 1 = A

Teorema 5: A · 0 = 0

Teorema 6: A + 1 = 1

Teorema 7: (A + B)' = A' · B'

Teorema 8: (A · B)' = A' + B'

Teorema 9: A + A · B = A

Teorema 10: A · (A + B) = A

Teorema 11: A + A'B = A + B

Teorema 12: A' · (A + B') = A'B'

Teorema 13: AB + AB' = A

Teorema 14: (A' + B') · (A' + B) = A'

Teorema 15: A + A' = 1

Teorema 16: A · A' = 0

Para cada función booleana es posible diseñar un circuito electrónico y viceversa, como las funciones booleanas solo requieren de los operadores AND, OR y NOT podemos construir nuestros circuitos utilizando exclusivamente éstos operadores utilizando las compuertas lógicas homónimas.

Un hecho interesante es que es posible implementar cualquier circuito electrónico utilizando una sola compuerta, ésta es la compuerta NAND
Para probar que podemos construir cualquier función booleana utilizando sólo compuertas NAND, necesitamos demostrar cómo construir un inversor (NOT), una compuerta AND y una compuerta OR a partir de una compuerta NAND, ya que como se dijo, es posible implementar cualquier función booleana utilizando sólo los operadores booleanos AND, OR y NOT. Para construir un inversor simplemente conectamos juntas las dos entradas de una compuerta NAND. Una vez que tenemos un inversor, construir una compuerta AND es fácil, sólo invertimos la salida de una compuerta NAND, después de todo, NOT (NOT (A AND B)) es equivalente a A AND B. Por supuesto, se requieren dos compuertas NAND para construir una sola compuerta AND, nadie ha dicho que los circuitos implementados sólo utilizando compuertas NAND sean lo óptimo, solo se ha dicho que es posible hacerlo. La otra compuerta que necesitamos sintetizar es la compuerta lógica OR, esto es sencillo si utilizamos los teoremas de DeMorgan, que en síntesis se logra en tres pasos, primero se reemplazan todos los "·" por "+" después se invierte cada literal y por último se niega la totalidad de la expresión:

Teoremas de Morgan

...