Minimización de funciones booleanas – Part 1

Como se discutió en la «Representación de funciones booleanas» , cada función booleana se puede expresar como una suma de minitérminos o un producto de maxtérminos. Dado que el número de literales en dicha expresión suele ser alto, y la complejidad de las puertas lógicas digitales que implementan una función booleana está directamente relacionada con la complejidad de la expresión algebraica a partir de la cual se implementa la función, es preferible tener la mayor cantidad posible. forma simplificada de la expresión algebraica.
El proceso de simplificación de la expresión algebraica de una función booleana se llama minimización . La minimización es importante ya que reduce el costo y la complejidad del circuito asociado.
Por ejemplo, la función $F=x^\prime y^\prime z + x^\prime yz + xy^\prime$ se puede minimizar a $F=x^\prime z + xy^\prime$ . Los circuitos asociados con las expresiones anteriores son:

de la imagen anterior queda claro que la versión minimizada de la expresión requiere menos puertas lógicas y también reduce sustancialmente la complejidad del circuito. Por lo tanto, la minimización es importante para encontrar la representación equivalente más económica de una función booleana.
La minimización se puede realizar mediante la manipulación algebraica o el método K-Map . Cada método tiene sus propios méritos y deméritos.

Minimización usando Manipulación Algebraica –

Este método es el más simple de todos los métodos utilizados para la minimización. Es adecuado para expresiones de tamaño mediano que involucran 4 o 5 variables. La manipulación algebraica es un método manual, por lo que es propenso al error humano.
Leyes comunes utilizadas en la manipulación algebraica:

$\:A + A^\prime = 1$
$\:A + A^\prime B = A + B$
$\:A + AB = A$

Ejemplo 1: minimice la siguiente función booleana usando manipulación algebraica :
$F=ABC^\prime D^\prime + ABC^\prime D + AB^\prime C^\prime D + ABCD + AB^\prime CD + ABCD^\prime \\ + AB^\prime CD^\prime$
Solución: las propiedades se refieren a las tres leyes comunes mencionadas anteriormente.
$\begin{align*} F=\:&ABC^\prime(D^\prime + D) +AB^\prime C^\prime D + ACD(B + B^\prime) &&\\ &\:+ ACD^\prime(B + B^\prime)&&\\ =\:&ABC^\prime +AB^\prime C^\prime D + ACD +ACD^\prime && \text{Using Property-1}\\ =\:&ABC^\prime +AB^\prime C^\prime D + AC(D +D^\prime )&&\\ =\:&ABC^\prime +AB^\prime C^\prime D + AC && \text{Using Property-1}\\ =\:&A(BC^\prime +C)+AB^\prime C^\prime D &&\\ =\:&A(B+C)+AB^\prime C^\prime D&& \text{Using Property-2}\\ =\:&AB +AC+AB^\prime C^\prime D &&\\ =\:&AB + AC+ A C^\prime D && \text{Using Property-2}\\ =\:&AB + AC+ AD && \text{Using Property-2}\\ \end{align*}$

Minimización usando K-Map –

El método de manipulación algebraica es tedioso y engorroso. El método K-Map es más rápido y se puede utilizar para resolver funciones booleanas de hasta 5 variables. Consulte este enlace para obtener más información sobre K-Map.

Ejemplo 2: considere la misma expresión del ejemplo 1 y minimícela usando K-Map.
Solución: el siguiente es un K-Map de 4 variables de la expresión dada.

La figura anterior resalta los principales implicantes en verde, rojo y azul.
El verde abarca toda la tercera fila, lo que nos da – $AB$
El rojo abarca 4 cuadrados, lo que nos da – $AD$
El azul abarca 4 cuadrados, lo que nos da – $AC$
Entonces, la expresión booleana minimizada es- $AB+AC+AD$

Preguntas de GATE CS Corner

Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.

1. GATE CS 2012, Pregunta 30
2. GATE CS 2007, Pregunta 32
3. GATE CS 2014 Conjunto-3, Pregunta 17
4. GATE CS 2005, Pregunta 18
5. GATE CS 2004, Pregunta 17
6. GATE CS 2003, Pregunta 45
7. GATE CS 2002, Pregunta 12

Referencias-

K-Map – Diseño digital de Wikipedia , 5.ª edición por Morris Mano y Michael Ciletti

Este artículo es una contribución de Chirag Manwani . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta