Posterior: Algoritmo de Quine-McCluskey Arriba: Optimización de formas conjuntivas Anterior: Optimización de formas conjuntivas

Mapas de Karnaugh

Los MAPAS DE KARNAUGH son esquemas de representación del hipercubo $\mbox{\rm Dos}^n$. En la figura 2.1 presentamos los mapas correspondientes a $n\leq 5$.

Figure 2.1: Mapas de Karnaugh correspondientes a $n\leq 5$.

La manera de leerlos se ajusta a varias convenciones y conveniencias:

• Cada entrada en un mapa representa un vértice en el hipercubo. En esa entrada se puede colocar un valor 0 o 1 asignado al correspondiente vértice por una función $\mbox{\rm Dos}^n\to\mbox{\rm Dos}$. Así pues cada mapa representa a una función booleana.
• Dos entradas vecinas por una arista forman una arista en el hipercubo. Por ejemplo, para $n=3$ las entradas marcadas en el mapa
  
  $$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert} x\bac... ...\times & \times & \\ \hline 1 & & & & \\ \hline \end{array}$$
  
  
  corresponden a la arista tal que $x=0$ & $z=1$:
  
  $$\{(x,y,z)=(0,\epsilon_2,1)\vert\epsilon_2=0,1\}.$$
  
  

• Cuatro entradas en una misma columna, en un mismo renglón o con un vértice común forman una ``cara'', es decir un cubo cuya dimensión es 2. Por ejemplo, para $n=3$ las entradas marcadas en el mapa
  
  $$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert} xy\ba... ...times & \times & \\ \hline 10 & & & & \\ \hline \end{array}$$
  
  
  corresponden a la cara tal que $y=1$ & $w=1$:
  
  $$\{(x,y,z,w)=(\epsilon_1,1,\epsilon_3,1)\vert\epsilon_1,\epsilon_3=0,1\}.$$
  
  

• Las líneas ``fronterizas'' en un mapa han de identificarse (tal como si los mapas estuvieran dibujados en un toro). Por ejemplo, para $n=4$ en el mapa
  
  $$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert} xy\ba... ...11 & & & & \\ \hline 10 & c & a & & c \\ \hline \end{array}$$
  
  
  las entradas marcadas con $a$ forman la arista $y=0$ & $z=0$ & $w=1$:
  
  $$\{(x,y,z,w)=(\epsilon_1,0,0,1)\vert\epsilon_1=0,1\}$$
  
  
  y las entradas marcadas con $c$, con las esquinas como vértice común, forman la cara $y=0$ & $w=0$:
  
  $$\{(x,y,z,w)=(\epsilon_1,0,\epsilon_3,0)\vert\epsilon_1,\epsilon_3=0,1\}.$$
  
  
  En el mapa de $n=5$, casillas correspondientes en ambos mapas de dimensión 4 son vecinas.
• Ocho casillas que contengan $n-3$ coordenadas constantes, es decir tres coordenadas variables, forman un cubo de dimensión 3.
• De manera sucesiva, un mapa de dimensión $n+1$ puede verse como dos mapas de dimensión $n+1$ superpuestos.

Ejemplo 1.6   Se quiere construir un circuito que reciba un dígito decimal y lo incremente en 3.

Explicación. Ya que $3< \log_2(10)<4$ hemos de necesitar 4 bits para representar a los dígitos decimales. Si expresamos a un dígito como $d=e_4e_3e_2e_1$, donde $e_i\in\mbox{\rm Dos}$, $i=1,2,3,4$, entonces se ha de calcular $d+3=F(d) = f_4f_3f_2f_1$. En la tabla 2.1 presentamos los valores de cada $f_j$ en términos de $d$.

Table 2.1:

$\begin{array}{cccc} \multicolumn{4}{c}{d} \\ e_4 & e_3 & e_2 & e_1 \\ \hline... ...& 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 %%\\ \end{array}$

$\begin{array}{cccc} \multicolumn{4}{c}{F(d)} \\ f_4 & f_3 & f_2 & f_1 \\ \hl... ...& 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 %%\\ \end{array}$

En la tabla 2.3 presentamos los correspondientes mapas de Karnaugh:

Table 2.2: Mapas de Karnaugh del incrementador en tres de dígitos decimales.

$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert} e_1e_2\backslash e_3e_4... ...ine 11 & 0 & a & a & 0 \\ \hline 10 & 0 & 0 & a & 0 \\ \hline \end{array}$	$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert} e_1e_2\backslash e_3e_4... ...ine 11 & 1 & a & a & 1 \\ \hline 10 & 0 & 0 & a & 0 \\ \hline \end{array}$
(a) $f_1$	(b) $f_2$
$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert} e_1e_2\backslash e_3e_4... ...ine 11 & 1 & a & a & 0 \\ \hline 10 & 1 & 1 & a & 0 \\ \hline \end{array}$	$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert} e_1e_2\backslash e_3e_4... ...ine 11 & 0 & a & a & 1 \\ \hline 10 & 0 & 1 & a & 1 \\ \hline \end{array}$
(a) $f_3$	(b) $f_4$

En los mapas el valor $a$ significa un valor irrelevante (recuérdese que sólo nos interesan los 10 dígitos decimales. En la tabla 2.2 presentamos, en cada mapa, al conjunto de vértices con valores 1 o $a$ como una unión de cubos maximales. A los valores $a$ que quedan fuera de los cubos marcados se les ha hecho tomar el valor 0. Cada cubo se nombra consecutivamente con una letra mayúscula a partir de $C$. Así, las entradas marcadas con varias letras pertenecen a varios cubos. Debajo de cada mapa ponemos a las correspondientes formas disyuntivas utilizando las frases correspondientes a los cuos maximales localizados. Estas expresiones son mínimas en cuanto a la longitud de las frases.

Table 2.3: Cubos maximales en el incrementador en tres de dígitos decimales.

$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert} e_1e_2\backslash e_3e_4... ...ine 11 & 0 & 0 & 0 & 0 \\ \hline 10 & 0 & 0 & 0 & 0 \\ \hline \end{array}$	$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert} e_1e_2\backslash e_3e_4... ...ine 11 & D & D & D & D \\ \hline 10 & 0 & 0 & 0 & 0 \\ \hline \end{array}$
(a) $f_1\equiv\overline{e_1}$	(b) $f_2\equiv(\overline{e_1}\land \overline{e_2})\lor(e_1\land e_2)$
$\begin{array}{c\vert\vert l\vert l\vert l\vert l\vert} e_1e_2\backslash e_3e_4... ...11 & DE & DE & 0 & 0 \\ \hline 10 & \ E & \ E & 0 & 0 \\ \hline \end{array}$	$\begin{array}{c\vert\vert c\vert c\vert l\vert l\vert} e_1e_2\backslash e_3e_4... ... 11 & 0 & C & CDE & DE \\ \hline 10 & 0 & C & CE & E \\ \hline \end{array}$
(a) $f_3\equiv \begin{array}[t]{l} (\overline{e_1}\land \overline{e_2}\land e_3)\lor \\ (e_2\land \overline{e_3})\lor (e_1\land \overline{e_3}) \end{array}$	(b) $f_4 \equiv e_4\lor(e_2\land e_3) \lor(e_1\land e_3)$

$\quad\Box$ Para finalizar esta presentación introductoria de los mapas de Karnaugh, mencionaremos que la enumeración de las columnas y renglones en un tal mapa sigue el esquema de un CÓDIGO DE GRAY. Un tal código es una enumeración de los vértices del hipercubo tal que cualesquiera dos vértices consecutivos difieren en a lo sumo un bit. De hecho, un código de Gray es un recorrido hamiltoniano de la gráfica de adyacencias del hipercubo. Una manera de construir un código de Gray se obtiene fácilmente por recursión. En efecto, denotemos por $E_n$ a la enumeración del hipercubo de dimensión $n$ que corresponda al código de Gray a construir. Entonces:

Caso base.

Sea $E_1:0\mapsto 0$, $1\mapsto 1$.

Caso recursivo.

Escribamos $\mbox{\rm Dos}^{n+1} = 0*\mbox{\rm Dos}^{n} \cup 1*\mbox{\rm Dos}^{n}$. La lista $E_{n+1}$ la obtenemos de anteponerle 0 a los elementos de la lista $E_{n}$ y de anteponerle 1 a los elementos de la lista $E_{n}^{\mbox{\scriptsize rev}}$: $E_{n+1} = 0*E_{n} \otimes 1*E_{n}^{\mbox{\scriptsize rev}}$.

En la tabla 2.4 presentamos el listado del código de Gray $E_5$ siguiendo el algoritmo descrito.

Table 2.4: Código de Gray para $n=5$.

Hemos visto que para dos proposiciones $p,q\in \mbox{\it Pbf}_B(X)$ se tiene $p\models q$ si y sólo si $p \rightarrow q$ es una tautología. Si $f$ es una frase, es decir, una conjunción de literales, siempre que $f\models q$, para una proposición $q\in \mbox{\it Pbf}_B(X)$, entonces se dice que la frase $f$ es un IMPLICANTE de $q$. La frase $f$ se dice ser un IMPLICANTE PRIMO de $q$ si es un implicante y además ninguna subfrase de $F$ es un implicante. Es decir, los implicantes primos son las frases de longitudes minimales, las cuales a su vez corresponden a subcubos de dimensiones maximales incluídos en el soporte de $q$. Ya que el soporte de la disyunción de dos proposiciones es la unión de los soportes de esas proposiciones, tenemos que al expresar al soporte de una proposición como una unión de subcubos maximales estamos, en realidad, expresando a esa proposición como la disyunción de sus implicantes primos, es decir, la expresamos en su forma disyuntiva mínima. El procedimiento de optimización con mapas de Karnaugh es puramente visual y consiste en localizar los cubos de dimensión maximal que cubran a los puntos marcados en un mapa.

Ejemplo 1.7   Sea $\phi=\phi(x_1,x_2,x_3) = \left(x_3\rightarrow \left(x_1\lor x_2\right)\right) \land \left(\left(x_1\land x_2\right)\rightarrow x_3\right)$. La forma disyuntiva mínima de $\phi$, $\mbox{\it FD}_{\phi}$, consiste de 6 implicantes primos de 2 literales cada uno.

Explicación. Los valores de verdad de $\phi$ se muestran en el siguiente mapa de Karnaugh:

$$\begin{array}{c\vert\vert c\vert c\vert c\vert c\vert} x_1\b... ...0 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 & 0 \\ \hline \end{array}$$

y ahí vemos que su soporte es la unión de 6 aristas:

$$\begin{array}{cc} \begin{array}{rcl} C &=& \{000,100\} \\... ...1,010\} \\ H &=& \{010,000\} %%\\ \end{array} \end{array}$$

o, vistas en el mapa:

$$\begin{array}{c\vert\vert l\vert l\vert l\vert l\vert} x_1\b... ...F & GH \\ \hline 1 & DC & DE & EF & 0 \\ \hline \end{array}$$

por tanto $\mbox{\it FD}_{\phi}=\mbox{\it fr}(a00)\lor \mbox{\it fr}(10a)\lor \mbox{\it fr}(1a0)\lor \mbox{\it fr}(a11)\lor \mbox{\it fr}(01a)\lor \mbox{\it fr}(0a0)$. Se tiene que $\mbox{\it fr}(10a)=x_1\land\overline{x_2}$ es un implicante primo, pero $x_1\land\overline{x_2}\land\overline{x_2}$ es un implicante no-primo. $\quad\Box$ El procedimiento de optimización con mapas de Karnaugh no es nada formalizable y es inútil para valores de $n$ superiores a 5. Lo hemos presentado aquí como una mera curiosidad histórica.
Posterior: Algoritmo de Quine-McCluskey Arriba: Optimización de formas conjuntivas Anterior: Optimización de formas conjuntivas