2.4: Forma Normal Disyuntiva (DNF)

Forma Normal Disyuntiva (DNF) es una forma estándar de escribir funciones booleanas. Se puede describir como una suma de productos, y un OR y ANDS ³. Para entender DNF, primero se cubrirá el concepto de un minterm.

Un minterm es una fila en la tabla de verdad donde la función de salida para ese término es verdadera. Por ejemplo, en la Tabla 2.3.3, la función f1 (A, B, C) tiene un minterm cuando A=1, B=0 y C=0. Podemos escribir este minterm a AB'C' (A y no-B y no-C), ya que A es cierto, y B y C son ambos falsos. La función f1 (A, B, C) también tiene otros tres minterms, AB'C, ABC' y ABC. Entonces el DNF para la función f1 (A, B, C) se escribiría como:

f1 (A, B, C) = AB'C' + AB'C + ABC' + ABC

Tenga en cuenta que estos minterms son los números 4, 5, 6 y 7 ⁴ en la tabla por lo que una mano corta para escribir el DNF es la siguiente:

f1 (A, B, C) = σ (4,5,6,7)

Así mismo f2 (A, B, C) se puede escribir como:

f2 (A, B, C) = A'B'C + A'BC + AB'C + ABC =σ (1, 3, 5, 7)

Tenga en cuenta que cualquier función booleana se puede escribir en DNF, y DNF requiere solo 3 tipos de operaciones, AND, OR y NOT. Es por ello que Y, O, y NO son universales. La prueba de ello se deja para los ejercicios al final del capítulo.

\(\PageIndex{1}\)Relaciones Booleanas

La siguiente pregunta a hacer es si alguna función booleana se puede escribir en DNF, ¿se debe usar DNF para representar todas las funciones booleanas? La respuesta a esta pregunta viene de la ingeniería del circuito. En algún momento, una computadora tiene que implementar la función booleana como circuito. Ese circuito necesitará 1 puerta para cada operación. Y en la ingeniería del circuito, el objetivo es minimizar el número de compuertas necesarias.

¿Por qué se debería minimizar el número de compuertas? Cuando una puerta está realmente incluida en un circuito, tiene 3 efectos negativos:

• Cada puerta requiere energía para operarla. Cuantas más puertas haya en el circuito significa que se necesitará energía para operar la computadora.
• Dado que las compuertas requieren energía, producen calor como resultado. Más puertas significan más calor de la CPU.
• Siempre hay retrasos en la propagación de la señal a través de las puertas. La velocidad de la luz es muy rápida, pero no es infinita. Cuanto más tiene que ir la electricidad para llegar al final del circuito, más tiempo tarda. Entonces, cuanto más puertas haya en el circuito, más lenta será la CPU. Y en las computadoras modernas, la velocidad de la luz suele ser el factor limitante en qué tan rápido puede ciclar la CPU, y por lo tanto en la velocidad de la CPU.

Así, el objetivo en cualquier diseño de circuito es limitar el número de puertas en el circuito. Para la función f1 (A, B, C) en la Tabla 2.3.3, el número de puertas AND es 8, o puertas es 3, y no puertas es 4, o un total de 15 puertas. La cuestión es si el circuito se puede implementar o no en menos de 15 puertas.

El álgebra booleana es el mecanismo que se utiliza para responder a esta pregunta. El álgebra booleana es igual que el álgebra tradicional en que hay un conjunto de relaciones que se pueden aplicar a una función para transformarla. Y esas operaciones son generalmente algo análogas a las operaciones en álgebra tradicional, haciendo algo más fácil la transición al álgebra booleana. Una lista de estas relaciones se da en la tabla\(\PageIndex{1}\).

Mesa\(\PageIndex{1}\)

Relación	Regla No.	Relación	Regla No.
x+0=x	1	x*0=0	2
x+1 = 1	3	x*1=x	4
x+x =x	5	x*x=x	6
x+x'=1	7	x*x'=0	8
x+y=y+x	9	xy=yx	10
x+ (y+z) = (x+y) +z	11	x (yz) = (xy) z	12
x (y+z) =xy+yz	13	x+yz= (x+y) (x+z)	14
(x+y) '= x'y'	15	(xy) '=x'+y'	16
(x') '= x	17

Todas estas relaciones a excepción de 15 y 16 deben derivarse fácilmente. Las relaciones 15 y 16 se conocen como Leyes de DeMorgan, y simplemente deben ser memorizadas.

Aplicando estas relaciones para f1 (A, B, C), encontramos lo siguiente:

f1 (A, B, C)

= AB'C' + AB'C + ABC' + ABC = AB' (C'+C) + AB (C'+C) (regla 13) = AB' (1) + AB (1) (regla 7) = AB' + AB (regla 4) = A (B'+B) (regla 13) = A (1) (regla 7) = A (regla 4)

Esta expresión es obviamente más simple que la original, y el número de puertas necesarias para este circuito se ha reducido de 15 a 0. Esta reducción obviamente valió la pena el esfuerzo.

Pero, ¿cómo sabíamos seguir reduciendo esta expresión después de “AB' + AB”? Esta fue una reducción significativa en sí misma, de 15 a 4 puertas. Dado que ahora hemos demostrado que DNF no necesariamente (y muchas veces no) da como resultado una expresión mínima, ¿cómo podemos saber si se ha alcanzado una expresión mínima? Ese es el tema de la siguiente sección de este capítulo.

---

³ Otra forma de representar la función es la Forma Normal Conjuntiva (CNF). El CNF puede describirse como un producto de sumas, o un AND o OR. El uso de CNF se deja a los problemas al final del capítulo.
⁴ Tenga en cuenta que el número comienza en 0, no en 1.