En álgebra booleana , cualquier función booleana se puede expresar en la forma normal disyuntiva canónica ( CDNF ) [1] o forma canónica minterm , y su dual, la forma normal conjuntiva canónica ( CCNF ) o forma canónica maxterm . Otras formas canónicas incluyen la suma completa de implicantes primos o forma canónica de Blake (y su dual) y la forma normal algebraica (también llamada Zhegalkin o Reed-Muller).
Los términos mínimos se llaman productos porque son el Y lógico de un conjunto de variables, y los términos máximos se llaman sumas porque son el O lógico de un conjunto de variables. Estos conceptos son duales debido a su relación de simetría complementaria expresada por las leyes de De Morgan .
Dos formas canónicas duales de cualquier función booleana son una "suma de mintérminos" y un "producto de máxtérminos". El término " Suma de Productos " ( SoP o SOP ) se usa ampliamente para la forma canónica que es una disyunción (OR) de mintérminos. Su dual de De Morgan es un " Producto de sumas " ( PoS o POS ) para la forma canónica que es una conjunción (Y) de maxterms. Estas formas pueden resultar útiles para la simplificación de estas funciones, lo cual es de gran importancia en la optimización de fórmulas booleanas en general y de circuitos digitales en particular.
Para una función booleana de variables , un término producto en el que cada una de las variables aparece una vez (ya sea en su forma complementada o no complementada) se llama minterm . Por tanto, un minterm es una expresión lógica de n variables que emplea sólo el operador de complemento y el operador de conjunción .
Por ejemplo, y son 3 ejemplos de los 8 términos mínimos para una función booleana de las tres variables , y . La lectura habitual del último de ellos es a AND b AND NOT-c .
Hay 2 n mintérminos de n variables, ya que una variable en la expresión de mintérmino puede estar en su forma directa o complementada: dos opciones por variable.
Los minitérminos suelen estar numerados mediante una codificación binaria del patrón de complementación de las variables, donde las variables se escriben en un orden estándar, generalmente alfabético. Esta convención asigna el valor 1 a la forma directa ( ) y 0 a la forma complementada ( ); el mintérmino es entonces . Por ejemplo, minterm se numera 110 2 = 6 10 y se denota .
Un minterm dado n da un valor verdadero (es decir, 1) para sólo una combinación de las variables de entrada. Por ejemplo, el minitérmino 5, a b ' c , es verdadero solo cuando a y c son verdaderos y b es falso: la disposición de entrada donde a = 1, b = 0, c = 1 da como resultado 1.
Dada la tabla de verdad de una función lógica, es posible escribir la función como una "suma de productos". Esta es una forma especial de forma normal disyuntiva . Por ejemplo, si se le da la tabla de verdad para la suma aritmética del bit u de la lógica de la posición de un bit de un circuito sumador, en función de x e y de los sumandos y el acarreo, ci :
Observando que las filas que tienen una salida de 1 son la 2.ª, 3.ª, 5.ª y 8.ª, podemos escribir u como una suma de mintérminos y . Si deseamos verificar esto: evaluado para las 8 combinaciones de las tres variables coincidirá con la tabla.
Para una función booleana de n variables , un término de suma en el que cada una de las n variables aparece una vez (ya sea en su forma complementada o no complementada) se llama maxterm . Por tanto, un término máximo es una expresión lógica de n variables que emplea sólo el operador de complemento y el operador de disyunción . Los maxterms son un dual de la idea de minterm (es decir, exhiben una simetría complementaria en todos los aspectos). En lugar de utilizar AND y complementos, utilizamos OR y complementos y procedemos de manera similar.
Por ejemplo, los siguientes son dos de los ocho términos máximos de tres variables:
Nuevamente hay 2 n maxterms de n variables, ya que una variable en la expresión maxterm también puede estar en su forma directa o complementada: dos opciones por variable.
A cada maxterm se le asigna un índice basado en la codificación binaria convencional opuesta utilizada para los minterms. La convención maxterm asigna el valor 0 a la forma directa y 1 a la forma complementada . Por ejemplo, asignamos el índice 6 al término máximo (110) y denotamos ese término máximo como M 6 . De manera similar, M 0 de estas tres variables es (000) y M 7 es (111).
Es evidente que maxterm n da un valor falso (es decir, 0) sólo para una combinación de las variables de entrada. Por ejemplo, el término máximo 5, a ′ + b + c ′, es falso solo cuando a y c son verdaderos y b es falso; la disposición de entrada donde a = 1, b = 0, c = 1 da como resultado 0.
Si se le da una tabla de verdad de una función lógica, es posible escribir la función como un "producto de sumas". Esta es una forma especial de forma normal conjuntiva . Por ejemplo, si se le da la tabla de verdad para el bit de acarreo co de la lógica de posición de un bit de un circuito sumador, en función de x e y de los sumandos y el acarreo, ci :
Observando que las filas que tienen una salida de 0 son la 1.ª, 2.ª, 3.ª y 5.ª, podemos escribir co como producto de maxterms y . Si queremos verificar esto:
evaluados para las 8 combinaciones de las tres variables coincidirán con la tabla.
El complemento de un minterm es el maxterm respectivo. Esto se puede verificar fácilmente utilizando la ley de Morgan . Por ejemplo:
A menudo ocurre que la forma canónica del minterm se puede simplificar a una forma SoP equivalente. Esta forma simplificada seguiría constituyéndose en una suma de términos de producto. Sin embargo, en la forma simplificada, es posible tener menos términos de producto y/o términos de producto que contengan menos variables. Por ejemplo, la siguiente función de 3 variables:
tiene la representación canónica de minterm: , pero tiene una forma simplificada equivalente: . En este ejemplo trivial, es obvio que , pero la forma simplificada tiene menos términos de producto y el término tiene menos variables.
La representación SoP más simplificada de una función se denomina forma SoP mínima .
De manera similar, una forma canónica de maxterm puede tener una forma de PoS simplificada.
Si bien este ejemplo se simplificó aplicando métodos algebraicos normales [ ], en casos menos obvios, un método conveniente para encontrar la forma mínima PoS/SoP de una función con hasta cuatro variables es usar un mapa de Karnaugh .
Las formas mínimas de PoS y SoP son importantes para encontrar implementaciones óptimas de funciones booleanas y minimizar circuitos lógicos.
Las tablas de verdad de muestra para minterms y maxterms anteriores son suficientes para establecer la forma canónica para una posición de un solo bit en la suma de números binarios, pero no son suficientes para diseñar la lógica digital a menos que su inventario de puertas incluya AND y OR. Cuando el rendimiento es un problema (como en el Apollo Guidance Computer), es más probable que las piezas disponibles sean NAND y NOR debido a la acción complementaria inherente a la lógica del transistor. Los valores se definen como estados de voltaje, uno cerca de tierra y otro cerca del voltaje de suministro de CC Vcc , por ejemplo, +5 VCC. Si el voltaje más alto se define como el valor 1 "verdadero", una puerta NOR es el elemento lógico útil más simple posible.
Específicamente, una puerta NOR de 3 entradas puede consistir en 3 transistores de unión bipolar con sus emisores todos conectados a tierra, sus colectores unidos y conectados a V cc a través de una impedancia de carga. Cada base está conectada a una señal de entrada y el punto colector común presenta la señal de salida. Cualquier entrada que sea un 1 (alto voltaje) en su base pone en cortocircuito el emisor de su transistor en su colector, lo que hace que la corriente fluya a través de la impedancia de carga, lo que acerca el voltaje del colector (la salida) a tierra. Ese resultado es independiente de las otras entradas. Solo cuando las 3 señales de entrada son 0 (bajo voltaje), las impedancias del emisor-colector de los 3 transistores permanecen muy altas. Entonces fluye muy poca corriente y el efecto divisor de voltaje con la impedancia de carga impone en el punto colector un voltaje alto muy cercano a Vcc .
La propiedad complementaria de estos circuitos de puerta puede parecer un inconveniente cuando se intenta implementar una función en forma canónica, pero hay una ventaja compensatoria: una puerta de este tipo con una sola entrada implementa la función complementaria, que se requiere con frecuencia en lógica digital.
Este ejemplo supone el inventario de piezas de Apollo: puertas NOR de 3 entradas solamente, pero la discusión se simplifica suponiendo que las puertas NOR de 4 entradas también están disponibles (en Apollo, éstas estaban compuestas por pares de NOR de 3 entradas).
Un conjunto de 8 puertas NOR, si sus entradas son todas combinaciones de las formas directa y complementaria de las 3 variables de entrada ci, x e y , siempre producen mintérminos, nunca maxtérminos, es decir, de las 8 compuertas necesarias para procesar todas las combinaciones. de 3 variables de entrada, solo una tiene el valor de salida 1. Esto se debe a que una puerta NOR, a pesar de su nombre, podría verse mejor (usando la ley de De Morgan) como el AND de los complementos de sus señales de entrada.
La razón por la que esto no es un problema es la dualidad de minterms y maxterms, es decir, cada maxterm es el complemento del minterm indexado del mismo modo, y viceversa.
En el ejemplo de término mínimo anterior, escribimos, pero para realizar esto con una puerta NOR de 4 entradas necesitamos reformularlo como un producto de sumas (PoS), donde las sumas son los términos máximos opuestos. Eso es,
En el ejemplo anterior de maxterm, escribimos pero para realizar esto con una puerta NOR de 4 entradas debemos notar la igualdad con NOR de los mismos minterms. Eso es,
Se podría suponer que el trabajo de diseñar una etapa sumadora ya está completo, pero no hemos abordado el hecho de que las 3 variables de entrada deben aparecer tanto en su forma directa como en su forma complementaria. No hay ninguna dificultad con los sumandos x e y a este respecto, porque son estáticos durante toda la suma y, por lo tanto, normalmente se mantienen en circuitos de retención que habitualmente tienen salidas tanto directas como complementarias. (El circuito de pestillo más simple hecho de puertas NOR es un par de puertas acopladas cruzadas para formar un flip-flop: la salida de cada una está conectada como una de las entradas de la otra). Tampoco es necesario crear la forma complementaria. de la suma u . Sin embargo, el acarreo de una posición de bit debe pasarse como acarreo a la siguiente posición de bit tanto en forma directa como en complemento. La forma más sencilla de hacer esto es pasar co a través de una puerta NOR de 1 entrada y etiquetar la salida co ′, pero eso agregaría un retraso de puerta en el peor lugar posible, ralentizando la fluctuación de los acarreos de derecha a izquierda. Una puerta NOR adicional de 4 entradas que construye la forma canónica de co ′ (a partir de los minitérminos opuestos como co ) resuelve este problema.
La contrapartida de mantener la velocidad máxima de esta manera incluye un costo inesperado (además de tener que usar una puerta más grande). Si hubiéramos usado esa puerta de 1 entrada para complementar co , el minterm no habría servido de nada y la puerta que lo generó podría haberse eliminado. Sin embargo, sigue siendo un buen negocio.
Ahora podríamos haber implementado esas funciones exactamente de acuerdo con sus formas canónicas SoP y PoS, convirtiendo las puertas NOR en las funciones especificadas. Una puerta NOR se convierte en una puerta OR pasando su salida a través de una puerta NOR de 1 entrada; y se convierte en una puerta AND pasando cada una de sus entradas a través de una puerta NOR de 1 entrada. Sin embargo, este enfoque no solo aumenta la cantidad de puertas utilizadas, sino que también duplica la cantidad de retrasos de puerta que procesan las señales, reduciendo la velocidad de procesamiento a la mitad. En consecuencia, siempre que el rendimiento sea vital, vale la pena ir más allá de las formas canónicas y aplicar el álgebra booleana para que las puertas NOR sin mejorar funcionen.
Ahora hemos visto cómo se pueden utilizar las herramientas minterm/maxterm para diseñar una etapa sumadora en forma canónica con la adición de algo de álgebra booleana, lo que cuesta solo 2 retrasos de puerta para cada una de las salidas. Esa es la forma "de arriba hacia abajo" de diseñar el circuito digital para esta función, pero ¿es la mejor manera? La discusión se ha centrado en identificar "más rápido" como "mejor", y la forma canónica aumentada cumple perfectamente con ese criterio, pero a veces predominan otros factores. El diseñador puede tener como objetivo principal minimizar el número de puertas y/o minimizar la distribución de señales hacia otras puertas, ya que las grandes distribuciones reducen la resiliencia a un suministro de energía degradado u otros factores ambientales. En tal caso, un diseñador puede desarrollar el diseño de forma canónica como base, luego intentar un desarrollo ascendente y finalmente comparar los resultados.
El desarrollo ascendente implica notar que u = ci XOR ( x XOR y ), donde XOR significa OR exclusivo [verdadero cuando cualquiera de las entradas es verdadera pero no cuando ambas son verdaderas], y que co = ci x + xy + y ci . Uno de estos desarrollos requiere doce puertas NOR en total: seis puertas de 2 entradas y dos puertas de 1 entrada para producir u en retardos de 5 puertas, más tres puertas de 2 entradas y una puerta de 3 entradas para producir co ′ en retardos de 2 puertas. La línea de base canónica tomó ocho puertas NOR de 3 entradas más tres puertas NOR de 4 entradas para producir u, co y co ′ en retardos de 2 puertas. Si el inventario del circuito realmente incluye puertas NOR de 4 entradas, el diseño canónico de arriba hacia abajo parece un ganador tanto en número de puertas como en velocidad. Pero si (contrariamente a nuestra cómoda suposición) los circuitos son en realidad puertas NOR de 3 entradas, de las cuales se requieren dos para cada función NOR de 4 entradas, entonces el diseño canónico requiere 14 puertas en comparación con las 12 del enfoque ascendente, pero todavía produce el dígito suma u considerablemente más rápido. La comparación fanout se tabula como:
La descripción del desarrollo ascendente menciona co ′ como producto pero no co . ¿Ese diseño simplemente nunca necesita la forma directa de llevar a cabo? Bueno, sí y no. En cada etapa, el cálculo de co ′ depende solo de ci ′, x ′ e y ′, lo que significa que la propagación del acarreo se propaga a lo largo de las posiciones de los bits tan rápido como en el diseño canónico sin desarrollar nunca co . El cálculo de u , que requiere que ci se haga a partir de ci ′ mediante una NOR de 1 entrada, es más lento, pero para cualquier longitud de palabra el diseño solo paga esa penalización una vez (cuando se desarrolla el dígito de suma más a la izquierda). Esto se debe a que esos cálculos se superponen, cada uno en lo que equivale a su propia pequeña tubería sin afectar cuándo se puede calcular el bit suma de la siguiente posición del bit. Y, sin duda, el co ′ fuera de la posición del bit más a la izquierda probablemente tendrá que complementarse como parte de la lógica que determina si la suma se desbordó. Pero al usar puertas NOR de 3 entradas, el diseño ascendente es casi tan rápido para realizar sumas paralelas en una longitud de palabra no trivial, reduce el recuento de puertas y utiliza distribuciones más bajas... por lo que gana si el recuento de puertas y/o fanout son primordiales!
Dejaremos el circuito exacto del diseño ascendente del cual todas estas afirmaciones son verdaderas como ejercicio para el lector interesado, asistido por una fórmula algebraica más: u = ci ( x XOR y ) + ci ′( x XOR y )′]′. Desacoplar la propagación del acarreo de la formación de la suma de esta manera es lo que eleva el rendimiento de un sumador de acarreo anticipado sobre el de un sumador de acarreo ondulado .
Una aplicación del álgebra de Boole es el diseño de circuitos digitales, con un objetivo de minimizar el número de puertas y otro de minimizar el tiempo de establecimiento.
Hay dieciséis funciones posibles de dos variables, pero en el hardware de lógica digital, los circuitos de compuerta más simples implementan solo cuatro de ellas: conjunción (AND), disyunción (OR inclusive) y los respectivos complementos de aquellas (NAND y NOR).
La mayoría de los circuitos de compuerta aceptan más de 2 variables de entrada; por ejemplo, la Computadora de Orientación Apolo , que fue pionera en la aplicación de circuitos integrados en la década de 1960, fue construida con un solo tipo de puerta, una NOR de 3 entradas, cuya salida es verdadera sólo cuando las 3 entradas son falsas. [2] [ página necesaria ] [3]
Para ver cómo se usó la lógica de puerta NOR en la ALU de la computadora de guía Apollo, seleccione cualquiera de las entradas del MÓDULO DE 4 BITS en el índice de dibujos y expanda las imágenes como desee.
Los autores demuestran una prueba de que cualquier función booleana (lógica) se puede expresar en forma normal disyuntiva o conjuntiva (véanse las páginas 5 y 6); la prueba simplemente continúa creando las 2 N filas de N variables booleanas y demuestra que cada fila ("minterm" o "maxterm") tiene una expresión booleana única. Cualquier función booleana de las N variables se puede derivar de una combinación de filas cuyos minterm o maxterm son 1 lógicos ("verdaderos")
Las expresiones canónicas están definidas y descritas.
Designación de funciones minterm y maxterm
