enerxia.net - LOGICA - Simplificación de funciones lógicas por Karnaugh

Simplificación de funciones lógicas por el método gráfico de Karnaugh

Fuente original del documento:
http://www.terra.es/personal2/equipos2/karnaugh.htm

Suponiendo que conozcamos la tabla de la verdad de un circuito combinacional, a partir de la cual deseamos diseñar dicho circuito, lo más corriente es tener que buscar una expresión simplificada de la función o funciones a implementar. En este artículo trataré de explicar cómo ello es posible de una forma sencilla gracias al empleo de un método de simplificación gráfico muy extendido (extendido precisamente por esto, por su facilidad de uso). Para ello me ayudaré de una tabla ejemplo mediante la cual iré explicando todo lo referente a este tipo de simplificación de funciones lógicas. Pero antes, un poco de teoría necesaria:

Mapas de Karnaugh para dos, tres, cuatro y cinco variables:

El aspecto de los mapas de Karnaugh es el de la siguiente figura:

----------------------------------------------------------------

De izquierda a derecha y de arriba a abajo aparecen los mapas para dos, tres, cuatro y cinco variables. Note que en cada mapa existe una línea diagonal en la esquina superior izquierda. Por encima y por debajo de dicha línea aparecen los nombres de las variables implicadas (en este caso a, b, c, d y/o e, según el mapa, aunque pudieran ser otros diferentes), de tal forma que para el mapa de cuatro variables, por ejemplo, las combinaciones de ceros y unos de la parte superior del mapa son las combinaciones posibles de las variables a y b, en este orden, y las combinaciones de dígitos binarios del lateral izquierdo son la posibles combinaciones de las variables c y d, también en ese orden.

La adyacencia gráfica y la adyacencia algebraica

Dos casillas son adyacentes gráficamente si están una junto a otra en el mapa de Karnaugh, teniendo en cuenta que nunca deben considerarse las diagonales. Por otro lado, dos casillas de un mapa de Karnaugh son adyacentes algebraicamente si en el conjunto formado por los bits de sus coordenadas x e y sólo hay un dígito diferente, no importando la posición en la que se encuentre dicho dígito. Pues bien, siempre se verifica que dos casillas que sean adyacentes gráficamente también lo son algebraicamente (recuerde que no vale en diagonal). El recíproco no es cierto en general, de tal forma que hay casillas que son adyacentes algebraicas y no lo son gráficamente. La adyacencia algebraica es la que realmente hay que tener en cuenta en el proceso de simplificación gráfica. Podemos decir que la adyacencia algebraica es "más fuerte" que la gráfica. Sin embargo, a efectos de poder realizar la simplificación de forma fácil convendría que los dos tipos de adyacencias coincidiesen para tener una imagen gráfica de las adyacencias algebraicas. Lamentablemente esto no es así, pero con objeto de conseguir una imagen mental y gráfica de las adyacencias algebraicas podemos ayudarnos de las siguientes figuras:

- Para tres variables:

- Para cuatro variables:

- Para cinco variables (¿tiene buena visión espacial?):

Si a usted no se le da bien la visualización espacial siempre puede aplicar la regla comentada en principio para saber si dos casillas de un mapa son o no adyacentes. La práctica en esta cuestión le hará finalmente no tener que ni pensarlo.

Las formas canónicas de las funciones lógicas

Toda función lógica es posible expresarla en cualquiera de las dos formas canonicas que existen. Estas dos formas de representación universales son por un lado la forma de maxitérminos o maxterms y por otro lado la forma de minitérminos o minterms. Cada una de estas formas canónicas está formada por un número de términos variable.

----------------------------------------------------------------

En cada uno de esos términos deben aparecer todas las variables de la función, ya sea en forma negada o en forma directa (sin negar). Además, en las formás canónicas no existen términos repetidos.
Centrémonos primeramente en la forma canonica de minitérminos. En esta forma cada uno de los términos estará formado por productos lógicos de unas variables (negadas una a una o no) con otras (negadas una a una o no), teniendo que aparecer finalmente en cada término todas y cada una de las variables que intervienen en la función (negadas o no una a una). Por último, todos los términos involucrados deberán sumarse lógicamente en una única expresión. Este expresión es la forma canónica de minitérminos. El aspecto de una forma canónica de este tipo tendrá un aspecto similar a los siguientes:

Veamos ahora la forma canónica de maxitérminos. En ella los términos se forman no con el producto lógico, sino con la suma lógica y la expresión completa de maxitérminos se consigue multiplicando lógicamente todos los términos y no sumándolos como pasaba en la otra forma canónica. Así, ejemplos de formas canónicas de maxitérminos podrían ser los siguientes:

La relación existente entre tablas de la verdad y formas canónicas:

Supongamos que tenemos una tabla de la verdad de una función lógica tal como la que sigue (W es la función y a, b y c las variables de dicha función):

a	b	c	W
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

Para expresar W en forma canónica de minitérminos debemos fijarnos en aquellas filas de la tabla en las que W=1. Cada una de estas filas corresponderá a un término de la forma canónica. Dentro de cada término, si una variable tiene valor cero deberá negarse. Por contra, si tiene valor uno deberá aparecer sin negar. Entonces, la forma canónica de minitérminos correspondiente a la función W es la siguiente:

----------------------------------------------------------------

Veamos ahora la forma canónica de maxitérminos. En este caso es necesario fijarse en las filas de la table en las que W=0. Igual que antes, cada una de estas filas corresponderá a un término de la forma canónica de maxitérminos. Ahora bien, dentro de cada término la variable que tenga valor cero debe aparecer sin negar y negada la que tenga valor uno. Así pues, W en forma canónica de maxitérminos sería la siguiente:

¡Basta de teoría! He aquí la tabla de la verdad:

La tabla que usaremos para explicar la simplificación gráfica de Karnaugh es la siguiente:

a	b	c	d	F	G	H
0	0	0	0	1	0	0
0	0	0	1	1	0	0
0	0	1	0	0	0	1
0	0	1	1	1	0	1
0	1	0	0	1	0	0
0	1	0	1	0	1	0
0	1	1	0	1	0	1
0	1	1	1	1	1	1
1	0	0	0	1	0	1
1	0	0	1	0	0	0
1	0	1	0	1	0	1
1	0	1	1	1	1	0
1	1	0	0	1	0	0
1	1	0	1	0	0	0
1	1	1	0	0	0	1
1	1	1	1	1	0	1

En esta tabla se han diferenciado las funciones de salida de las variables de entrada gracias al empleo de mayúsculas (para las funciones) y minúsculas (para las variables). Tenemos pues cuatro variables de entrada y tres funciones de salida. Cada una de estas funciones corresponderá a una salida de nuestro circuito combinacional (es por eso que reciben ese nombre, funciones de salida). Por contra, cada una de las variables de entrada corresponderá a una entrada del circuito. Entonces, la tabla de la verdad indica cómo se comportará el circuito, desde el punto de vista de sus salidas, ante cualquier combinación lógica en sus entradas (vea que en la tabla aparecen todas las combinaciones lógicas posibles de entrada).
Empecemos diciendo que de esta tabla se podrían sacar las formas canónicas (de minitérminos o de maxitérminos) de las funciones F, G y H y, a partir de estas formas canónicas, implementar el circuito lógico correspondiente a cada función. Sin embargo, esta forma de proceder no es la más adecuada por motivos de economía de medios, ya que las formas canónicas no son las expresiones más

----------------------------------------------------------------

simples de una determinada función, y mientras más simple sea una función más simple será el circuito que la implemente. Así pues, se hace necesario simplificar las formas canónicas para obtener otras expresiones más simples. Es aquí donde entran en juego los mapas de Karnaugh.
Como ya se desprende de lo comentado más arriba, la simplificación se puede llevar a cabo de la forma canónica de minitérminos o de la forma canónica de maxitérminos. A nosotros nos toca decidir. ¿Cómo?. Pues el criterio que considero más lógico (salvo demostración en contra) es el de simplificar la forma canónica que ya de por sí sea más simple, o sea, la que tenga menos términos. En el caso de la función F de la tabla estaríamos hablando de forma canónica de maxitérminos. Bien, pues simplifiquemos primeramente F en su forma canónica de maxitérminos. Para ello eligiremos un mapa de Karnaugh de igual número de variables que las que tenga la función a simplificar, en este caso será de cuatro variables. A continuación, colocaremos ceros en las casillas del mapa cuyas coordenadas correspondan con los valores de las variables que producen los ceros de F:

A continuación hay que intentar realizar agrupamientos de los ceros colocados en el mapa. Sólo se permiten agrupamientos de un número de ceros que sea una potencia de dos (2, 4, 8, 16 , etc.) y nunca en diagonal. Además, los agrupamientos que se hagan hay que tratar que sean lo mayor posible. Los agrupamientos que pueden realizarse en el mapa de más arriba son los siguientes:

La simplificación de la función se producirá en los agrupamientos. Así, ninguno de los dos ceros de la línea inferior no se han podido agrupar. Eso hará que cada uno de ellos de lugar a un maxitérmino de la siguiente forma:

O sea, la variable que tenga valor cero aparece en el maxitérmino de forma directa y la que tenga el valor uno aparece de forma negada. Esto respecto a los términos que no se simplifican. Respecto a los que sí se simplifican lo hacen de la siguiente forma:

Como puede verse, se sigue la misma regla que en los términos no simplificados en cuanto a la negación o no de una variable, pero además, cada agrupamiento (y no cada casilla) da lugar a un término en el que la variable que cambia de valor en las casillas del agrupamiento desaparece del término directamente, o sea, no se incluye en él.
La función F simplificada tendrá el siguiente aspecto:

¿Sería posible simplificar aún más la función F? Sí, pero ya aplicando métodos de simplificación algebraica. Por ejemplo, se podría sacar factor común c + d', con lo que quedaría:

Pasemos a simplificar otra función de las de la tabla. Acometamos la simplificación de la función G. Esta función tiene menor número de unos que de ceros. Por tanto, simplificaremos por minitérminos. Además, como G tiene cuatro variables

----------------------------------------------------------------

deberemos usar un mapa de Karnaugh de ese número de variables. Ahora se irán rellenando las casillas igual que en el caso anterior pero con unos en lugar de con ceros (es un convenio que permite que se sepa con un simple vistazo si se está trabajando con base en minitérminos o en maxitérminos):

Agrupando según la regla que ya se ha visto tendremos:

En el agrupamiento cambia (y por tanto desaparece de su término correspondiente) la variable c y en el uno no agrupado no se puede hacer simplificación alguna (y por tanto su término contendrá todas las variables). Así pues:

Como puede verse, el criterio que se ha seguido para negar o no una variable es el contrario que en el caso de los maxitérminos, es decir, en minitérminos una variable se niega si su valor es cero y se deja sin negar si su valor es uno.
Bien, pasemos ya a simplificar la función restante, o sea, la función H. Esta función tiene igual número de ceros que de unos, así que es indiferente que nos basemos en minitérminos o en maxitérminos. Yo personalmente tengo preferencia por los minitérminos. Basémonos en minitérminos pues. El mapa de Karnaugh con los agrupamientos ya hechos será el siguiente: