Básicamente es la simplificación de una función, obteniendo una expresión que contenga menos términos o menos variables que la función original.  Esto se refleja en la obtención de circuito más económicos por tener un menor número de compuertas.La simplificación de estas funciones puede realizarse con el uso de álgebra de Boole pero no es un método sencillo de ejecutar. La manipulación de funciones booleana puede llegar a ser muy compleja y muchas veces es necesario un ingenio considerable y quizás mucha suerte.

La minimización con álgebra de Boole  presenta dos limitaciones importantes:

No existe un algoritmo que nos garantice encontrar la forma más simple de la expresión.

Dado un determinado resultado intermedio no hay forma de saber si realmente hemos llegado a la forma mínima.

Para efecto de este curso cuando nos referimos a una expresión mínima, nos estamos refiriendo  a la expresión más simple de dos niveles.

Cualquier función booleana puede ser implantada con dos niveles de compuertas.

Como se señaló anteriormente una función puede ser representada utilizando la forma suma de productos como:

                      f = ( )+( )+( ) .......+ ( )

De esta manera  los términos ( ) son productos de las variables de entrada (negadas o no ) que se realizan con compuertas AND. Los + se realizan con una compuerta OR de tantas entradas como términos productos haya en la función.

Como resultado tendremos que la función puede realizarse con dos niveles de compuertas: El nivel 1 representado por las compuertas AND y el nivel 2 representado por la compuerta OR, como se muestra en la figura. (En el nivel 1 se consideran también la variables negadas, que siendo formales se implantan con una compuerta NOT.)

Como señalamos anteriormente, la simplificación de las funciones lógicas es una meta importante por el hecho de que cuanto mas sencilla sea la función, más fácil será construir el circuito equivalente. El objetivo de la simplificación es el de minimizar el costo de implantación de una función mediante componentes electrónicos, donde el costo depende del número y complejidad de los elementos necesarios para construirla.

La optimalidad de la simplificación utilizando Algebra de Boole depende de la habilidad del diseñador para aplicar la propiedad más adecuada en cada paso del proceso. Esta tarea se hace cada vez más difícil al crecer la complejidad de la expresión. Por ello, se utilizan algunos métodos que facilitan y automatizan el proceso de simplificación de las funciones lógicas, como lo son los Mapas de Karnaugh, y el método de Quine-McCluskey. (Para este curso solo se cubrirá el método de Mapas de Karnaugh) l

En este punto, siendo la minimización el último paso antes de la implantación en el diseño de un sistema digital y antes de pasar a describir el método de minimización utilizando Mapas de Karnaugh, resumamos los diferentes pasos que deben seguirse en un problema de  diseño de lógica combinacional.

• Se toman las proposiciones y se simbolizan.
• Se construye una tabla de verdad con todas las combinaciones posibles de las variables de entrada y se coloca un 1 para las combinaciones que cumplan con las condiciones de diseño.
• Se obtiene la forma canónica Suma de productos tomando los minterminos de la tabla de verdad que sean iguales a 1.
• Se simplifica la función utilizando Mapas de Karnaugh y se obtiene una expresión mínima de dos niveles.
• Se realiza el diagrama circuital y se implanta el circuito.

Es un dispositivo electrónico con una función booleana u otras funciones como sumar o restar, incluyen o excluyen según sus propiedades lógicas. Se pueden aplicar a tecnología electrónica, eléctrica, mecánica, hidráulica y neumática. Son circuitos de conmutación integrados en un chip. 

Experimentada con relés o interruptores electromagnéticos para conseguir las condiciones de cada compuerta lógica, por ejemplo, para la función booleana Y (AND) colocaba interruptores en circuito serie, ya que con uno solo de estos que tuviera la condición «abierto», la salida de la compuerta Y sería = 0, mientras que para la implementación de una compuerta O (OR), la conexión de los interruptores tiene una configuración en circuito paralelo. 

La tecnología microelectrónica actual permite la elevada integración de transistores actuando como conmutadores en redes lógicas dentro de un pequeño circuito integrado. El chip de la CPU es una de las máximas expresiones de este avance tecnológico. En nanotecnología se está desarrollando el uso de una compuerta lógica molecular, que haga posible la miniaturización de circuitos.

Compuertas Lógicas

La Lógica binaria tiene que ver con variables binarias y con operaciones que toman un sentido lógico. La manipulación de información binaria se hace por circuitos lógicos que se denominan Compuertas Lógicas Cada puerta lógica consiste en una red de dispositivos interruptores que cumple las condiciones booleanas para el operador particular. Son esencialmente Circuitos de conmutación integrados en un Chip Las compuertas son bloques del Hardware que producen señales en binario 1 ó 0 cuando se satisfacen los requisitos de entrada lógica. Las diversas compuertas lógicas se encuentran comúnmente en sistemas de computadoras digitales. Cada compuerta tiene un símbolo gráfico diferente y su operación puede describirse por medio de una función algebraica. Las relaciones entrada - salida de las variables binarias para cada compuerta pueden representarse en forma tabular en una Tabla de la verdad.

Compuertas más usadas

Compuerta AND

Cada compuerta tiene dos variables de entrada designadas por A y B y una salida binaria designada por x. La compuerta AND produce la multiplicación lógica AND: esto es: La salida es 1 si la entrada A y la entrada B están ambas en el binario 1: de otra manera, la salida es 0.

Estas condiciones también son especificadas en la tabla de la verdad para la compuerta AND. La tabla muestra que la salida x es 1 solamente cuando ambas entradas A y B están en 1. El símbolo de operación algebraico de la función AND es el mismo que el símbolo de la multiplicación de la aritmética ordinaria (*).

Las compuertas AND pueden tener más de dos entradas y por definición, la salida es 1 si todas las entradas son 1.

Compuerta OR

La compuerta OR produce la función sumadora, esto es: La salida es 1 si la entrada A o la entrada B o ambas entradas son 1; de otra manera, la salida es 0.

El símbolo algebraico de la función OR (+), es igual a la operación de aritmética de suma. Las compuertas OR pueden tener más de dos entradas y por definición la salida es 1 si cualquier entrada es 1.

Compuerta NOT

El circuito NOT es un inversor que invierte el nivel lógico de una señal binaria. Produce el NOT, o función complementaria. El símbolo algebraico utilizado para el complemento es una barra sobra el símbolo de la variable binaria. Si la variable binaria posee un valor 0, la compuerta NOT cambia su estado al valor 1 y viceversa. El círculo pequeño en la salida de un símbolo gráfico de un inversor designa un inversor lógico. Es decir cambia los valores binarios 1 a 0 y viceversa.

Compuerta Separador (yes)

Un símbolo triángulo por sí mismo designa un circuito separador, el cual no produce ninguna función lógica particular puesto que el valor binario de la salida es el mismo de la entrada. Este circuito se utiliza simplemente para amplificación de la señal. Por ejemplo, un separador que utiliza 5 volt para el binario 1, producirá una salida de 5 volt cuando la entrada es 5 volt.

Sin embargo, la corriente producida a la salida es muy superior a la corriente suministrada a la entrada de la misma. De ésta manera, un separador puede excitar muchas otras compuertas que requieren una cantidad mayor de corriente que de otra manera no se encontraría en la pequeña cantidad de corriente aplicada a la entrada del separador.

Compuertas lógicas combinadas

Al agregar una compuerta NOT a cada una de las compuertas anteriores, los resultados de sus respectivas tablas de verdad se invierten, y dan origen a tres nuevas compuertas llamadas NAND, NOR y NOR-EX..

Compuerta NAND

Es el complemento de la función AND, como se indica por el símbolo gráfico, que consiste en una compuerta AND seguida por un pequeño círculo (quiere decir que invierte la señal). La designación NAND se deriva de la abreviación NOT - AND. Una designación más adecuada habría sido AND invertido puesto que es la función AND la que se ha invertido. Las compuertas NAND pueden tener más de dos entradas, y la salida es siempre el complemento de la función AND.

Compuerta NOR

La compuerta NOR es el complemento de la compuerta OR y utiliza el símbolo de la compuerta OR seguido de un círculo pequeño (quiere decir que invierte la señal). Las compuertas NOR pueden tener más de dos entradas, y la salida es siempre el complemento de la función OR.

Compuerta NOR-EX

Es simplemente la inversión de la compuerta OR-EX, los resultados se pueden apreciar en la tabla de verdad, que bien se podría comparar con la anterior y notar la diferencia.

Una aplicación importante del álgebra booleana es el álgebra de circuitos de conmutación. Un conmutador es un dispositivo con dos estados que son cerrado y abierto y que se denotarán respectivamente 1 y 0.mEn esta forma, un álgebra de circuitos de conmutación no es más que un álgebra booleana con dos elementos a saber: 0 y 1. Se designará un conmutador con una sola letra: a, b, c, x, y etcétera.

Si dos conmutadores operan en tal forma que se abren y se cierran simultáneamente, se designarán con la misma letra. Si operan en tal forma que cuando uno está abierto el otro está cerrado, y viceversa entonces se designará uno de ellos con una letra y el otro por su complemento.

Un circuito consistente de los conmutadores x e y conectados en paralelo, se designará por x + y, si los conmutadores están conectados en serie se designarán por xy. Para cada circuito serie paralelo corresponderá una expresión algebraica y viceversa, tales expresiones involucran las operaciones (+ ), (.), (´). Gráficamente ocurre entonces lo siguiente:

Se dice que dos circuitos de conmutadores son equivalentes si para cualquier posición de los conmutadores de cada circuito o pasa la corriente a través de ambos circuitos (circuitos cerrados) o por ninguno pasa (circuitos abiertos). Dos expresiones booleanas serán iguales sí sólo sí representan circuitos equivalentes. Se tendrán en cuenta sólo los factores que determinan si un circuito está abierto o cerrado. Se desecharán problemas referentes a corriente, voltaje, resistencia, etc.

Ejemplo

La ley distributiva de (+ ) respecto a (.) es: x + yz = (x + y) (x + z). El correspondiente circuito de conmutación para cada miembro es:

 

Se puede observar que los dos circuitos están cerrados (la corriente pasa) si:

• x está cerrado.
• y, z están cerrados.

Los dos circuitos están abiertos (la corriente no pasa) si:

• x e y están abiertos.
• x y z están abiertos.

Por tanto los dos circuitos son equivalentes.

Teoremas

Regla del cero y la unidad

Toda operación simple que involucre a un elemento con las variables binarias, queda definida:

• 0 + A = A
• 1 + A = 1
• 0 . A = 0
• 1 . A = A

Potencias iguales o idempotencia

Las operaciones entre variables iguales quedan definidas como:

• A + A = A
• A . A = A

Complementación

Toda operación entre una variable y su complemento queda definida como:

• A + NOT A = 1
• A . NOT A = 0

Involución o doble negación

Toda doble negación sera considerada como la variable natural.

• NOT (NOT A ) = A

Conmutativa

• A + B = B + A ; Conmutatividad de la suma.
• A . B = B . A ; Conmutatividad del producto.

Asociativa

• A + ( B + C ) = ( A + B ) + C = A + B + C ; Asociatividad de la suma.
• A . ( B . C ) = ( A . B ) . C = A . B . C ; Asociatividad del producto.

Distributiva

• A + ( B . C ) = ( A + B ) . ( A + C ) ; Distributividad de la suma con respecto al producto.
• A . ( B + C ) = ( A . B ) + ( A + C ) ; Distributividad del producto con respecto a la suma.

Leyes de absorción

Existen muchas leyes de absorción entre múltiples referencias, algunas de las más conocidas son:

• A . ( A + B ) = A
• A . ( NOT A + B ) = A . B
• NOT A ( A + B ) = NOT A . B
• ( A + B ) . ( A + NOT B ) = A
• A + A . B = A
• A + NOT A . B = A + B
• NOT A + A . B = NOT A + B
• A . B + A . NOT B = A

Teorema de Morgan

Son leyes de transformación, que manejan pares de variables que interactúan entre las operaciones definidas del álgebra booleana ( + . ).

• NOT ( A . B ) = NOT A + NOT B
• NOT ( A +B ) = NOT A . NOT B
• A + B = NOT ( NOT A + NOT B )
• A . B = NOT ( NOT A . NOT B )

Dualidad

Todos los postulados y teoremas poseen la facultad de la dualidad. Esto implica que al intercambiar las variables y operaciones se verifica la proposición resultante. Es decir ,que al intercambiar 0 por 1 y AND por OR o viceversa; se crea una expresión que también será completamente válida. Por ejemplo si se toma el postulado 1 . 0 = 0 Y se le aplica la dualidad 0 + 1 = 1 Se obtiene otro postulado perfectamente válido.

Postulados

Existen teoremas que rigen las leyes lógicas estructurales del álgebra booleana. De igual forma se tienen postulados para conocer los resultados posibles en diferentes combinaciones de variables binarias, según la operación que se realice.

Suma (+)

El operador OR cuyo elemento lógico es la unión (U) queda definido para variables binarias de la siguiente manera:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 1

Producto (.)

El operador AND cuyo elemento lógico es la intersección (∩) queda definido para variables binarias de la siguiente manera:

• 0 . 0 = 0
• 0 . 1 = 0
• 1 . 0 = 0
• 1 . 1 = 1

Opuesto (NOT)

El operador NOT cuyo elemento lógico es el complemento (X)’ queda definido para variables binarias de la siguiente manera:

• NOT 0 = 1
• NOT 1 = 0

Muchos de los postulados difieren de sus equivalentes en el álgebra convencional. Esto es debido al dominio de las variables. Por ejemplo, la adición de elementos universo en álgebra booleana (1 + 1) no puede arrojar el resultado convencional de 2, debido a que no pertenece a los elementos del conjunto binario.