07_2

Simplificación de Funciones

Las funciones booleanas pueden ser simplificadas mediante procedimientos algebraicos empleando las leyes del álgebra lógica y los métodos expuestos anteriormente o mediante técnicas gráficas denominadas mapas de Karnaugh o mapas K.

Un mapa K es un diagrama rectangular dividido en 2ⁿ casillas o compartimentos

Donde n es el número de variables lógicas de la función a simplificar; a cada casilla se le asocia una fila de la tabla de verdad de la función.

Para n = 2 variables x, y, el mapa K es un cuadrado que se divide en 2ⁿ=2²=4 casillas a cada una de las cuales se le asocia una fila de la tabla de verdad, si la tabla de verdad de una función f de dos variables es:

donde cada a_i puede ser 0 ó 1, el mapa k es:

A la casilla donde está a₀ se le asocia la primera fila de la tabla, (0, 0) son las coordenadas binarias que identifican esta casilla; la casilla a₁ está asociada con la segunda fila, (0,1) son las coordenadas binarias que la identifican; (1, 0) identifica la casilla a₂ y (1, 1) a la casilla a₃. De esta manera mientras la tabla de verdad es una lista de todas las combinaciones, el mapa K es un cuadro de doble entrada.

En el mapa se distinguen cuatro regiones:

Región de x (la segunda columna),
Región de x’ (la primera columna),
Región de y’ (la primera fila), y
Región de y (la segunda fila).

Dependiendo de la forma elegida para la función a simplificar: normal disyuntiva o normal conjuntiva, las casillas se llenan sólo con los unos o sólo con los ceros respectivamente, tomados de la columna de f. En lo sucesivo se adoptará la primera forma.

Mapa de Karnaugh para dos Variables

En el apartado anterior se explicó cómo se construye el mapa en este caso. Para simplificar una función a partir del mapa se tienen en cuenta las adyacencias.

Si dos casillas contiguas situadas en la misma fila o en la misma columna, contienen unos, se dice que forman una adyacencia.

Estas adyacencias permiten eliminar variables como se muestra a continuación. No se consideran como adyacencias los unos ubicados en diagonal.

Ejemplo

Simplificar las funciones booleanas especificadas en la tabla:

Los mapas k correspondientes son:

Observaciones:

Sólo los mapas K de f1, f3 y f5 presentan adyacencias.

En f1 la adyacencia de dos unos, situados en la región x’, permiten eliminar la variable y; la función simplificada es f1 = x’. Con el método algebraico en algún paso del proceso debe aparecer el factor y + y’ que de acuerdo con la ley del complemento es equivalente a 1; en efecto, al escribir la forma normal disyuntiva queda:

f₁ = x’y’ + x’y = x’(y’ + y) = x’ . (1) = x’.

Esta función es la F₁₂ de la siguiente tabla.

La función f₂ no es susceptible de simplificación, se escribe directamente f₂ = xy’ + x’y que corresponde a XOR, la función F₆ de la tabla anterior.
En f₃ la adyacencia de dos unos, situados en la segunda fila, o región y, elimina la variable x; la función simplificada queda f₃= y. En el procedimiento algebraico de simplificación aparece el factor x + x’ ; al factorizar f₃ = x’y + xy queda f₃ = (x’+x)y, que se reduce a f₃ = y. Esta función corresponde a F₅.
En el mapa de f₄ no hay adyacencias, la función reducida es f₄= x’y’ + xy que corresponde a XNOR, la función F₉ de la tabla anterior.
El mapa de f₅ tiene dos adyacencias, una en la segunda fila y la otra en la primera columna; la función reducida consta de dos términos: f₅ = x’ + y. La función sin simplificar f₅ = x’y’ + x’y + xy se reduce al aplicar las leyes distributivas y del complemento así:
- al factorizar x’ queda f₅ = x’(y’ + y) + xy = x’ + xy
- al factorizar de nuevo f₅ = (x’ + x)(x’ + y) = x’ + y
- que corresponde a la función F₁₃ de la tabla anterior.
En cualquiera de los casos anteriores (y en los demás casos, al llenar las casillas de unos como se quiera, e inclusive sin ningún uno), la función reducida siempre coincidirá con alguna de las funciones F_i; i = 0, 1, ..., 15; de la tabla anterior.
Con el método de los mapas de Karnaugh se prescinde de los procedimientos algebraicos; su utilidad radica en que a partir de estos se escribe directamente la función reducida.

A continuación se presentan los mapas K de las funciones básicas (reducidas) que se pueden generar con dos variables; de una manera esquemática, y que permiten visualizar con facilidad las regiones de adyacencias.

Los mapas de las funciones i y 15 – i son:

a) Complementarios, es decir: F_i +F_15-i = 1
b) Disyuntos, es decir: F_i . F_15-i = 0

Ejemplo

Se requiere diseñar una alarma que suene cuando una puerta de un automóvil esté abierta mientras el motor está en marcha.

Si se designa x : puerta, tal que x = 1 si la puerta está abierta;
y : motor, tal que y = 1 si el motor esta encendido;

entonces la función booleana alarma A (x, y) se escribirá:

A (x,y) = xy

Mapa de Karnaugh para tres Variables

Para tres variables x, y, z, el mapa k tiene 2³ = 8 casillas dispuestas en dos filas y cuatro columnas, como se muestra a continuación:

Mapa K para 3 variables

donde a_i, para i = 0, ..., 7 puede ser 0 ó 1.

La casilla donde está a_i corresponde a la fila i, (en binario) de la tabla de verdad.

Por conveniencia, se han intercambiado las dos últimas columnas, a fin de que la numeración binaria que encabeza la segunda y tercera columnas pase de 01 a 11, con lo cual cambia una sóla variable (de x’y a xy cambia sólo la x, de complementada a no complementada); de esta manera quedan bien definidas seis regiones:

Región de x (tercera y cuarta columnas),
Región de x’ (primera y segunda columnas),
Región de y (segunda y tercera columnas),
Región de y’ (primera y cuarta columnas),
Región de z (segunda fila), y
Región de z’ (primera fila).

En este mapa se pueden presentar adyacencias de dos, cuatro, y ocho unos; también se consideran adyacencias entre la primera y la cuarta columnas (como si el mapa fuera dibujado sobre un cilindro).

Ejemplo

Simplificar la función booleana si el mapa k es:

En la adyacencia de cuatro unos cambian las variables y y z, de y’ a y, y , de z’ a z; esta adyacencia elimina dos variables; y y z.

Observese además que los cuatro unos están en la región x’. Por otra parte la adyacencia de dos unos (situados en la primera fila y en la segunda y tercera columnas) elimina una variable, la variable x que cambia de x’ a x; estos unos están en las regiones y y z’. La función simplificada es f(x,y,z) = x’ + y z’.

Mediante las leyes del álgebra lógica se justifica esta simplificación como sigue:

Con los unos del mapa se escribe inicialmente la forma normal disyuntiva:

f(x, y, z) = x’y’z’ + x’y’z + x’yz’ + x’yz + xyz’

Al agrupar los términos primero con tercero y segundo con cuarto, y factorizar x’z’ y x’z, respectivamente, queda:

f(x,y,z)	=	x’z’(y’ + y) + x’z(y’ + y) + xyz’
	=	x’z’ + x’z + xyz’
	=	x’(z’ + z) + x.yz’
	=	x’ + x.yz’
	=	(x’ + x)(x’ + yz’)
f(x,y,z)	=	x’ + yz’

Debido a la adyacencia de cuatro unos en la segunda fila (región de z) la función reducida es f(x,y,z) = z
La función simplificada consta de dos términos:
- Por la adyacencia marcada en la primera fila se escribe z’,
- Por la adyacencia en la segunda columna se escribe x’y;
La función reducida es f(x,y,z) = x’y + z’.
La adyacencia de dos unos en la primera fila (entre las columnas primera y cuarta) elimina la variable x (notar que cambia de x a x’), queda el término y’z’; por otro lado los unos en la segunda fila (región de z) permiten eliminar también x, y debe escribirse yz: la función reducida es: f(x,y,z) = y’z’ + yz; observar que:

x’y’z’ + xy’z’ = y’z’
x’yz + xyz = yz
f(x,yz) = y’z’ + yz
La adyacencia de cuatro unos en las columnas primera y cuarta (región de y’) elimina dos variables x y z; la función reducida es f(x,y,z) = y’.