Forma normal canónica

Formas estándar de funciones booleanas

En álgebra de Boole , cualquier función booleana se puede expresar en la forma normal disyuntiva canónica ( CDNF ), ^[1] forma canónica de mintérminos o suma de productos ( SoP o SOP ) como una disyunción (OR) de mintérminos. El dual de De Morgan es la forma normal conjuntiva canónica ( CCNF ), forma canónica de maxtérminos o producto de sumas ( PoS o POS ) que es una conjunción (AND) de maxtérminos. Estas formas pueden ser útiles para la simplificación de funciones booleanas, lo cual es de gran importancia en la optimización de fórmulas booleanas en general y circuitos digitales en particular.

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

Términos mínimos

Para una función booleana de variables , un mintérmino es un término producto en el que cada una de las variables aparece exactamente una vez (ya sea en su forma complementada o no complementada). Por lo tanto, un mintérmino es una expresión lógica de n variables que emplea solo el operador de complemento y el operador de conjunción ( AND lógico ). Un mintérmino da un valor verdadero para solo una combinación de las variables de entrada, la cantidad mínima no trivial. Por ejemplo, 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. ${\displaystyle n}$ ${\displaystyle {x_{1},\dots ,x_{n}}}$ ${\displaystyle n}$

Indexación de minitérminos

Hay 2 ⁿ minterms de n variables, ya que una variable en la expresión de minterm puede estar en su forma directa o complementada (dos opciones por variable). Los minterms 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 minterm es entonces . Por ejemplo, el minterm se numera 110 ₂  = 6 ₁₀ y se denota . ${\displaystyle x_{i}}$ ${\displaystyle x'_{i}}$ ${\displaystyle \sum \limits _{i=1}^{n}2^{i-1}\operatorname {value} (x_{i})}$ ${\displaystyle abc'}$ ${\displaystyle m_{6}}$

Forma canónica de minterm

Dada la tabla de verdad de una función lógica, es posible escribir la función como una "suma de productos" o "suma de mintérminos". Esta es una forma especial de la forma normal disyuntiva . Por ejemplo, si se da la tabla de verdad para la suma aritmética del bit u de la lógica de una posición de bit de un circuito sumador, como una función de x e y a partir 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 suma de minterms y . Si deseamos verificar esto: evaluado para las 8 combinaciones de las tres variables coincidirá con la tabla. ${\displaystyle m_{1},m_{2},m_{4},}$ ${\displaystyle m_{7}}$ ${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)}$

Términos máximos

Para una función booleana de n variables , un maxtérmino es un término suma en el que cada una de las n variables aparece exactamente una vez (ya sea en su forma complementada o no complementada). Por lo tanto, un maxtérmino es una expresión lógica de n variables que emplea solo el operador de complemento y el operador de disyunción ( OR lógico ). Los maxtérminos son un dual de la idea de mintérmino, siguiendo la simetría complementaria de las leyes de De Morgan . En lugar de usar AND y complementos, usamos OR y complementos y procedemos de manera similar. Es evidente que un maxtérmino da un valor falso para solo una combinación de las variables de entrada, es decir, es verdadero en el número máximo de posibilidades. Por ejemplo, el maxtérmino 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. ${\displaystyle {x_{1},\dots ,x_{n}}}$

Indexación de maxterms

Hay nuevamente 2 ⁿ 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). La numeración se elige de modo que el complemento de un minterm sea el respectivo maxterm. Es decir, a cada maxterm se le asigna un índice basado en la codificación binaria convencional opuesta utilizada para 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 maxterm (110) y denotamos ese maxterm como M ₆ . El complemento es el minterm , utilizando la ley de De Morgan . ${\displaystyle (x_{i})}$ ${\displaystyle (x'_{i})}$ ${\displaystyle a'+b'+c}$ ${\displaystyle (a'+b'+c)'}$ ${\displaystyle abc'=m_{6}}$

Forma canónica de Maxterm

Si se da una tabla de verdad de una función lógica, es posible escribir la función como un "producto de sumas" o "producto de términos máximos". Esta es una forma especial de la forma normal conjuntiva . Por ejemplo, si se da la tabla de verdad para el bit de salida co de la lógica de una posición de bit de un circuito sumador, como una función de x e y a partir de los sumandos y el acarreo de entrada, ci :

Observando que las filas que tienen una salida de 0 son la 1.ª, 2.ª, 3.ª y 5.ª, podemos escribir co como un producto de maxterms y . Si queremos comprobarlo: ${\displaystyle M_{0},M_{1},M_{2}}$ ${\displaystyle M_{4}}$

${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}=(ci+x+y)(ci+x+y')(ci+x'+y)(ci'+x+y)}$

evaluado para las 8 combinaciones de las tres variables coincidirá con la tabla.

Formularios mínimos de PoS y SoP

A menudo, la forma de término mínimo canónico es equivalente a una forma SoP más pequeña. Esta forma más pequeña seguiría estando compuesta por una suma de términos de producto, pero tendría menos términos de producto o términos de producto que contienen menos variables. Por ejemplo, la siguiente función de 3 variables:

tiene la representación canónica de mintérmino , pero tiene una forma SoP equivalente . En este ejemplo trivial, es obvio que , y la forma más pequeña tiene menos términos de producto y menos variables dentro de cada término. Las representaciones SoP mínimas de una función según esta noción de "más pequeño" se denominan formas SoP mínimas . En general, puede haber múltiples formas SoP mínimas, ninguna claramente más pequeña o más grande que otra. ^[2] De manera similar, una forma maxtérmino canónica se puede reducir a varias formas PoS mínimas. ${\displaystyle f=a'bc+abc}$ ${\displaystyle f=bc}$ ${\displaystyle bc=a'bc+abc}$

Si bien este ejemplo se simplificó aplicando métodos algebraicos normales [ ], en casos menos obvios un método conveniente para encontrar formas mínimas PoS/SoP de una función con hasta cuatro variables es usar un mapa de Karnaugh . El algoritmo de Quine-McCluskey puede resolver problemas ligeramente más grandes. El campo de la optimización lógica se desarrolló a partir del problema de encontrar implementaciones óptimas de funciones booleanas, como las formas mínimas PoS y SoP. ${\displaystyle f=(a'+a)bc}$

Ejemplo de aplicación

Las tablas de verdad de muestra para minterms y maxterms anteriores son suficientes para establecer la forma canónica para una única posición de 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 la computadora de guía Apollo), es más probable que las partes disponibles sean NAND y NOR debido a la acción complementaria inherente a la lógica de transistores. Los valores se definen como estados de voltaje, uno cerca de tierra y otro cerca del voltaje de suministro de CC V _cc , por ejemplo, +5 VCC. Si el voltaje más alto se define como el valor "verdadero" 1, una puerta NOR es el elemento lógico útil más simple posible.

En concreto, una compuerta NOR de 3 entradas puede constar de 3 transistores de unión bipolar con sus emisores todos conectados a tierra, sus colectores unidos y vinculados 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 con su colector, lo que hace que la corriente fluya a través de la impedancia de carga, lo que lleva el voltaje del colector (la salida) muy cerca de tierra. Ese resultado es independiente de las otras entradas. Solo cuando las 3 señales de entrada son 0 (bajo voltaje) las impedancias de 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 alto voltaje muy cercano a V _cc .

La propiedad complementaria de estos circuitos de compuerta puede parecer una desventaja cuando se intenta implementar una función en forma canónica, pero hay una ventaja compensatoria: una compuerta con una sola entrada implementa la función complementaria, que se requiere con frecuencia en la lógica digital.

Este ejemplo asume el inventario de piezas de Apollo: solo puertas NOR de 3 entradas, pero la discusión se simplifica al suponer que también están disponibles puertas NOR de 4 entradas (en Apollo, estas se componían de pares de NOR de 3 entradas).

Consecuencias canónicas y no canónicas de las puertas NOR

Un conjunto de 8 puertas NOR, si sus entradas son todas combinaciones de las formas directas y complementarias de las 3 variables de entrada ci, x e y , siempre producen minterms, nunca maxterms; es decir, de las 8 puertas necesarias para procesar todas las combinaciones de las 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 mintérminos y maxtérminos, es decir, cada maxtérmino es el complemento del mintérmino de índice similar, y viceversa.

En el ejemplo de minterm 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 maxterms opuestos. Es decir, ${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}}$

${\displaystyle u(ci,x,y)=\mathrm {AND} (M_{0},M_{3},M_{5},M_{6})=\mathrm {NOR} (m_{0},m_{3},m_{5},m_{6}).}$

En el ejemplo de maxterm anterior, escribimos pero para realizar esto con una puerta NOR de 4 entradas, necesitamos notar la igualdad con el NOR de los mismos minterms. Es decir, ${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}}$

${\displaystyle co(ci,x,y)=\mathrm {AND} (M_{0},M_{1},M_{2},M_{4})=\mathrm {NOR} (m_{0},m_{1},m_{2},m_{4}).}$

Se consideran compensaciones de diseño además de las formas canónicas

Uno podría suponer que el trabajo de diseñar una etapa de suma ya está completo, pero no hemos abordado el hecho de que las 3 variables de entrada tienen que aparecer tanto en su forma directa como en su forma complementaria. No hay ninguna dificultad con los sumandos x e y en este sentido, porque son estáticos durante toda la suma y, por lo tanto, normalmente se mantienen en circuitos de retención que rutinariamente tienen salidas tanto directas como complementarias. (El circuito de retención más simple hecho de puertas NOR es un par de puertas acopladas de forma cruzada para formar un flip-flop: la salida de cada una está conectada como una de las entradas a la otra). Tampoco hay necesidad de crear la forma complementaria de la suma u . Sin embargo, el acarreo de salida de una posición de bit debe pasarse como acarreo a la siguiente posición de bit tanto en forma directa como complementaria. La forma más directa 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 ondulación de acarreos de derecha a izquierda. Una puerta NOR adicional de 4 entradas que construye la forma canónica de co ′ (a partir de los mintérminos opuestos como co ) resuelve este problema.

${\displaystyle co'(ci,x,y)=\mathrm {AND} (M_{3},M_{5},M_{6},M_{7})=\mathrm {NOR} (m_{3},m_{5},m_{6},m_{7}).}$

La compensación por mantener la velocidad máxima de esta manera incluye un costo inesperado (además de tener que usar una compuerta más grande). Si solo hubiéramos usado esa compuerta de 1 entrada para complementar co , no habría habido uso para el minterm y la compuerta que lo generó podría haberse eliminado. Sin embargo, sigue siendo un buen intercambio. ${\displaystyle m_{7}}$

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 al pasar su salida a través de una puerta NOR de 1 entrada; y se convierte en una puerta AND al pasar cada una de sus entradas a través de una puerta NOR de 1 entrada. Sin embargo, este enfoque no solo aumenta el número de puertas utilizadas, sino que también duplica el número de retardos de puerta que procesan las señales, lo que reduce 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 hacer el álgebra booleana para hacer que las puertas NOR no mejoradas hagan el trabajo.

Diseño de arriba hacia abajo vs. diseño de abajo hacia arriba

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, con un coste de tan solo 2 retardos de compuerta 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 "lo más rápido" como "lo mejor", y la forma canónica aumentada cumple ese criterio sin problemas, pero a veces predominan otros factores. El diseñador puede tener como objetivo principal minimizar el número de compuertas y/o minimizar los abanicos de salida de señales a otras compuertas, ya que los abanicos de salida grandes reducen la resiliencia a una fuente de alimentación degradada u otros factores ambientales. En tal caso, un diseñador puede desarrollar el diseño en forma canónica como base, luego intentar un desarrollo de abajo hacia arriba y, finalmente, comparar los resultados.

El desarrollo de abajo hacia arriba 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 5 retardos de puerta, más tres puertas de 2 entradas y una puerta de 3 entradas para producir co ′ en 2 retardos de puerta. La línea 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 2 retardos de puerta. Si el inventario de circuitos realmente incluye puertas NOR de 4 entradas, el diseño canónico de arriba hacia abajo parece un ganador tanto en cantidad de puertas como en velocidad. Pero si (contrariamente a nuestra suposición conveniente) 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 aún produce el dígito de suma u considerablemente más rápido. La comparación de abanico de salida se tabula como:

La descripción del desarrollo de abajo hacia arriba menciona co ′ como una salida pero no co . ¿Ese diseño simplemente nunca necesita la forma directa del acarreo? 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 ondula a lo largo de las posiciones de bit 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 un 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 de suma de la siguiente posición de bit. Y, para estar seguros, el co ′ que sale de la posición de bit más a la izquierda probablemente tendrá que complementarse como parte de la lógica que determina si la adición se desbordó. Pero al usar puertas NOR de 3 entradas, el diseño de abajo hacia arriba es casi tan rápido para hacer sumas paralelas en una longitud de palabra no trivial, reduce el conteo de puertas y usa abanicos de salida más bajos... ¡así que gana si el conteo de puertas y/o el abanico de salida son primordiales!

Dejaremos el circuito exacto del diseño ascendente del cual todas estas afirmaciones son verdaderas como un ejercicio para el lector interesado, con la ayuda de 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 con anticipación por sobre el de un sumador de acarreo con ondulación .

Aplicación en el diseño de circuitos digitales

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 estabilización.

Hay dieciséis funciones posibles de dos variables, pero en hardware de lógica digital, los circuitos de compuerta más simples implementan solo cuatro de ellas: conjunción (AND), disyunción (OR inclusivo) 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 guía espacial Apollo , que fue pionera en la aplicación de circuitos integrados en la década de 1960, se construyó con un solo tipo de compuerta, una NOR de 3 entradas, cuya salida es verdadera solo cuando las 3 entradas son falsas. ^{[3] [ página necesaria ] [4]}

Véase también

• Lista de temas de álgebra de Boole

Referencias

1. Peter J. Pahl; Rudolf Damrath (6 de diciembre de 2012). Fundamentos matemáticos de la ingeniería computacional: un manual. Springer Science & Business Media. pp. 15–. ISBN 978-3-642-56893-0.
2. Lala, Parag K. (16 de julio de 2007). Principios del diseño digital moderno. John Wiley & Sons. pág. 78. ISBN 978-0-470-07296-7.
3. Hall, Eldon C. (1996). Viaje a la Luna: la historia de la computadora de guía del Apolo . AIAA. ISBN 1-56347-185-X.
4. "Esquemas de la COMPUTADORA DE ORIENTACIÓN APOLLO (AGC)". klabs.org . Rich Katz . Consultado el 19 de junio de 2021 . Para ver cómo se utilizó la lógica de la compuerta NOR en la ALU de la Computadora de Guía Apolo, seleccione cualquiera de las entradas de MÓDULO DE 4 BITS en el Índice de Dibujos y expanda las imágenes como desee.

Lectura adicional

• Bender, Edward A.; Williamson, S. Gill (2005). Un curso breve de matemáticas discretas . Mineola, NY: Dover Publications, Inc. ISBN 0-486-43946-1Los autores demuestran que cualquier función booleana (lógica) puede expresarse en forma normal disyuntiva o conjuntiva (consulte las páginas 5 y 6); la prueba simplemente procede 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 puede derivarse de una combinación de las filas cuyo minterm o maxterm son 1 lógicos ("verdaderos")
  
• McCluskey, EJ (1965). Introducción a la teoría de circuitos de conmutación . Nueva York: McGraw–Hill Book Company. pág. 78. LCCN  65-17394. Se definen y describen expresiones canónicas .
• Hill, Fredrick J.; Peterson, Gerald R. (1974). Introducción a la teoría de conmutación y al diseño lógico (2.ª ed.). Nueva York: John Wiley & Sons. pág. 101. ISBN 0-471-39882-9Designación de funciones mediante minterm y maxterm

Enlaces externos

• Boole, George (1848). "El cálculo de la lógica". Cambridge and Dublin Mathematical Journal . III . Traducido por Wilkins, David R.: 183–198.