Posterior: Ejercicios Arriba: Semántica Anterior: Mapas de Karnaugh

Algoritmo de Quine-McCluskey

El algoritmo de QUINE-MCCLUSKEY considera un subconjunto $S\subset \mbox{\rm Dos}^n$ y lo expresa como la unión, no necesariamente ajena, de los cubos maximales incluídos en él. Si $S$ fuese el soporte de una proposición $\phi$, entonces la expresión encontrada para $S$ da, sin más, la forma disyuntiva, consistente de frases minimales, equivalente a $\phi$. Si $S$, en cambio, fuese el conjunto nulo de una proposición $\psi$, $\psi=\neg \phi$, entonces la expresión encontrada para $S$ da, sin más, la forma disyuntiva, consistente de frases minimales, equivalente a $\psi$, la cual, utilizando las Leyes de De Morgan, nos da la forma conjuntiva equivalente a $\phi$.

Ejemplo 1.8   Calcular las formas normales disyuntiva y conjuntiva de la proposición

$$p(x_1,x_2,x_3,x_4)= \left(x_1 \leftrightarrow \overline{x_2}\right) \land \left(x_3 \leftrightarrow \overline{x_4}\right)$$

Explicación. Gráficamente, en el mapa de Karnaugh siguiente, vemos los valores de $p$:

$$\begin{array}{r\vert\vert c\vert c\vert c\vert c\vert} x_1x_... ... & 0 & 0 \\ \hline 10 & 0 & 1 & 0 & 1 \\ \hline \end{array}$$

El soporte de $p$ consta de los vértices marcados con 1 y los demás forman su conjunto nulo, es decir:

$$\begin{eqnarray*} S_p &=& \{0101,0110,1001,1010\} \\ N_p &=& \mbox{\rm Dos}^4-S_p %%\\ \end{eqnarray*}$$

Por tanto, la forma disyuntiva de $p$ es la disyunción de las frases correspondientes a los puntos del soporte:

$$\begin{eqnarray*} \mbox{\it FD}(p) &=& \left(\overline{x_1} \land x_2 \land ... ...x_1 \land \overline{x_2} \land x_3 \land \overline{x_4}\right) \end{eqnarray*}$$

Ahora bien, si consideramos al conjunto nulo, éste puede expresarse como unión de las caras $C$, $D$, $E$, $F$ marcadas como sigue:

$$\begin{array}{r\vert\vert l\vert l\vert l\vert l\vert} x_1x_... ...& GE & E \\ \hline 10 & D & 1 & G & 1 \\ \hline \end{array}$$

por tanto la forma disyuntiva mínima de la negación $\neg p$ de $p$ es

$$\mbox{\it FD}\left(\neg p(x_1,x_2,x_3,x_4)\right)= \left(\ove... ...\lor \left(x_1 \land x_2\right) \lor \left(x_3 \land x_4\right)$$

y, utilizando las leyes de De Morgan, se obtiene la forma conjuntiva mínima de $p$:

$$\mbox{\it FC}\left(p(x_1,x_2,x_3,x_4)\right)= \left(x_1 \lo... ...ght) \land \left(\overline{x_3} \lor \overline{x_4}\right)$$

$\quad\Box$ Así pues es de suma importancia expresar a un subconjunto de $\mbox{\rm Dos}^n$ como la unión de los cubos maximales contenidos en él.


Primera etapa del procedimiento de Quine-McCluskey

Entrada.

Un subconjunto $S\subset \mbox{\rm Dos}^n$.

Salida.

Una colección de cubos $C_1, \ldots, C_k$ tal que $S=\bigcup_{j=1}^k C_j$ (la unión no necesariamente es ajena).

Algoritmo.

1. Para cada $i\in [\![0, n]\!]$, sea $S_i=\{\mbox{\boldmath$\epsilon$}\in S\vert \mbox{\rm card}(\mbox{\boldmath$\epsilon$}^{-1}[1])=i\}$ la colección de vectores en $S$ con exactamente $i$ entradas con valor 1.
2. Para cada $i<n$ se compara cada $\mbox{\boldmath$\epsilon$}_1\in S_i$ con cada $\mbox{\boldmath$\epsilon$}_2\in S_{i+1}$:
   1. Toda vez que $\mbox{\boldmath$\epsilon$}_1$ y $\mbox{\boldmath$\epsilon$}_2$ coincidan en todas sus entradas excepto en una sola, digamos $\ell$,
      $$\begin{eqnarray*} \mbox{\boldmath$\epsilon$}_1 &=& (\epsilon_1,\ldots,\epsilon_... ...\ell-1},\overline{x},\epsilon_{\ell-1},\ldots,\epsilon_{n}) \\ \end{eqnarray*}$$
      
      
      
      
      
      entonces se marca como ``cubiertos'' a $\mbox{\boldmath$\epsilon$}_1$ en $S_i$, a $\mbox{\boldmath$\epsilon$}_2$ en $S_{i+1}$ y se añade el vector $(\epsilon_1,\ldots,\epsilon_{\ell-1},a,\epsilon_{\ell-1},\ldots,\epsilon_{n})$ a $S_i$.
   2. Se suprime a todos los vectores cubiertos.
3. Se repite desde el paso 2. en tanto haya habido vectores marcados.
4. Al concluir, la lista de vectores dará subcubos maximales. Aunque ningún cubo maximal está incluido en ningún otro, bien puede ocurrir en este punto que un cubo maximal esté incluido en la unión de algunos otros cubos maximales.

Para ilustrar este procedimiento identificaremos a $\mbox{\rm Dos}^n$ con el intervalo de enteros $[\![0,2^n-1]\!]$: al escribir cada uno de tales enteros en base 2, tendremos un vector de dimensión $n$.

Ejemplo 1.9   Sea $S=\{1,3,5,7,11,15\}$ visto como un subconjunto del hipercubo $\mbox{\rm Dos}^4$. Expresarlo como una unión de cubos maximales.

Explicación. Al clasificar a los elementos de $S$ según el número de 1's que contengan, obtenemos:

$$\begin{array}{\vert\vert r\vert c\vert\vert} \hline \hline ... ... 11 & 1011 \\ \hline 15 & 1111 \\ \hline \hline \end{array}$$

Al realizar las comparaciones en el paso 2. y reiterarlo consecutivamente, obtenemos las tablas siguientes:

$$\begin{array}{c@{\hspace{3em}}c} \begin{array}[t]{\vert\ver... ...e 3,11, 7,15 & aa11 \\ \hline \hline \end{array} \end{array}$$

Así pues $S=\mbox{\rm Cubo}(0aa1)\cup\mbox{\rm Cubo}(aa11)$. Observamos que $\mbox{\rm Cubo}(0aa1)$ aparece por dos vía y, en consecuencia, está repetido en esta etapa del procedimiento de Quine-McCluskey. $\quad\Box$

Ejemplo 1.10   Sea

$$S=\{2,3,4,5,6,7,12,13,16,17,18,19,24,25,26,27,28,29\}$$

visto como un subconjunto del hipercubo $\mbox{\rm Dos}^5$. Expresarlo como una unión de cubos maximales.

Explicación. Al clasificar a los elementos de $S$ según el número de 1's que contengan, obtenemos la lista mostrada en la tabla 2.5.

Table 2.5: Arreglo inicial del conjunto de entrada en el ejemplo 2.1.10

Al realizar las comparaciones en el paso 2. y reiterarlo consecutivamente, obtenemos, en una primera iteración las aristas enlistadas en la tabla 2.6,

Table 2.6: Aristas en la primera iteración en el ejemplo 2.1.10

en una segunda iteración las caras enlistadas en la tabla 2.7,

Table 2.7: Caras en la segunda iteración en el ejemplo 2.1.10

en una tercera iteración los cubos enlistados en la tabla 2.8,

Table 2.8: Cubos en la segunda (y última) iteración en el ejemplo 2.1.10

Así pues, tomando la unión de los cubos que no hayan sido marcados, se obtiene

$$\begin{eqnarray*} S & =& \mbox{\rm Cubo}(11a01) \cup \mbox{\rm Cubo}(1101a) \cu... ...p \mbox{\rm Cubo}(a110a) \cup \\ &\ & \mbox{\rm Cubo}(1a0aa) \end{eqnarray*}$$

(en la ecuación anterior, escribimos en la primera línea los cubos de dimensión 1, en la segunda y la tercera los de dimensión 2 y en la última el de dimensión 3). Ahora bien, podemos observar que

• $\mbox{\rm Cubo}(1101a) \subset \mbox{\rm Cubo}(1a0aa)$ (las 5 coordenadas del primero empatan con las 5 del segundo),
• $\mbox{\rm Cubo}(a001a) \subset \mbox{\rm Cubo}(00a1a) \cup \mbox{\rm Cubo}(1a0aa)$ y
• $\mbox{\rm Cubo}(0a10a) \subset \mbox{\rm Cubo}(001aa) \cup \mbox{\rm Cubo}(1a0aa)$.

Así pues, al suprimir los cubos cubiertos por los demás, se obtiene la expresión mínima,

$$\begin{eqnarray*} S & =& \mbox{\rm Cubo}(11a01) \cup \\ &\ & \mbox{\rm Cubo}... ...p \mbox{\rm Cubo}(a110a) \cup \\ &\ & \mbox{\rm Cubo}(1a0aa) \end{eqnarray*}$$

$\quad\Box$ La última simplificación hecha en el ejemplo anterior, ilustra lo que hace, más sistemáticamente, la segunda etapa del algoritmo de Quine-McCluskey, la cual selecciona un recubrimiento mínimo de un conjunto en el hipercubo, partiendo de un recubrimiento dado. Veamos los detalles de esta etapa: Sea $S\subset \mbox{\rm Dos}^n$ un conjunto en el hipercubo y sea ${\cal S}=\{S_1,\ldots,S_k\}$ un recubrimiento de $S$, es decir, $S=\bigcup_{i=1}^k S_i$. La TABLA DE ELECCIÓN de $S$ respecto al recubrimiento ${\cal S}$ es un arreglo planar con columnas indicadas por los elementos del conjunto $S$ y con renglones por los elementos del recubrimiento ${\cal S}$. Toda vez que $\mbox{\boldmath$\epsilon$}_j\in S_i$, en la entrada correspondiente $ij$ se coloca una marca $\times$ y se dice que el punto $\mbox{\boldmath$\epsilon$}_j$ QUEDA CUBIERTO por el conjunto $S_i$. Por ejemplo, siguiendo el ejemplo 2.1.10, para

$$S=\{2,3,4,5,6,7,12,13,16,17,18,19,24,25,26,27,28,29\}$$

y el recubrimiento ahí calculado

$$\begin{eqnarray*} S & =& \mbox{\rm Cubo}(11a01) \cup \mbox{\rm Cubo}(1101a) \cu... ...p \mbox{\rm Cubo}(a110a) \cup \\ &\ & \mbox{\rm Cubo}(1a0aa) \end{eqnarray*}$$

la correspondiente tabla de elección se muestra en la tabla 2.9.

Table 2.9: Tabla de elección del ejemplo 2.1.10.

	2	3	4	5	6	7	12	13	16
Cubo(11a01)
Cubo(1101a)
Cubo(00a1a)	$\times$	$\times$			$\times$	$\times$
Cubo(a001a)	$\times$	$\times$
Cubo(001aa)			$\times$	$\times$	$\times$	$\times$
Cubo(0a10a)			$\times$	$\times$			$\times$	$\times$
Cubo(a110a)							$\times$	$\times$
Cubo(1a0aa)									$\times$

	17	18	19	24	25	26	27	28	29
Cubo(11a01)					$\times$				$\times$
Cubo(1101a)						$\times$	$\times$
Cubo(00a1a)
Cubo(a001a)		$\times$	$\times$
Cubo(001aa)
Cubo(0a10a)
Cubo(a110a)								$\times$	$\times$
Cubo(1a0aa)	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$

Diremos que un conjunto $S_j\in{\cal S}$ es ESENCIAL si existe un punto $\mbox{\boldmath$\epsilon$}\in S$ que sólo es cubierto por él. Todo conjunto esencial ha de ser incluído en todo recubrimiento mínimo. En la tabla de elección, los conjuntos esenciales son los renglones de las marcas que corresponden a columnas que tienen una sola marca. En cada renglón hay tantas marcas como número de elementos tenga el conjunto correspondiente. En cada columna, digamos correspondiente a un punto $\mbox{\boldmath$\epsilon$}\in S$, el número de marcas $p(\mbox{\boldmath$\epsilon$})$ indica cuántos conjuntos cubren a ese punto. $p(\mbox{\boldmath$\epsilon$})$ es el peso del punto en el recubrimiento. Un conjunto entonces es esencial si cubre a puntos de peso 1.


Segunda etapa del procedimiento de Quine-McCluskey

Entrada.

Un conjunto $S\subset \mbox{\rm Dos}^n$ y una colección de cubos $C_1, \ldots, C_k$ tal que $S=\bigcup_{i=1}^k C_i$ (la unión no necesariamente es ajena).

Salida.

Una subcolección mínima de $\{C_1, \ldots, C_k\}$ que siga siendo un recubrimiento de $S$.

Algoritmo.

1. Fórmese la tabla de elección $T$ correspondiente.
2. Denotemos por ${\cal SM}$ al recubrimiento mínimo a construirse.
3. Colóquese en ${\cal SM}$ a todos los conjuntos esenciales y márquese a los puntos cubiertos por esos conjuntos.
4. En tanto queden puntos sin haber sido marcados:
   1. elíjase al punto $\mbox{\boldmath$\epsilon$}\in S$ que no haya sido marcado y que esté cubierto por un conjunto $S_j$ que abarque al mayor número de puntos no-marcados,
   2. incorpórese $S_j$ a ${\cal SM}$ y
   3. márquese a los puntos cubiertos por $S_j$.
5. Dése a ${\cal SM}$ como resultado.

Por ejemplo, examinemos la tabla de elección 2.9 del ejemplo 2.1.10. Es claro que $\mbox{\rm Cubo}(1a0aa)$ es un cubo esencial. Al incorporarlo en el recubrimiento mínimo, quedan marcados los puntos 16, 17, 18, 19, 24, 25, 26, 27. El cubo $\mbox{\rm Cubo}(1a0aa)$ es esencial pues sólo él cubre a 28. Al incorporarlo quedan marcados 12, 13, 28 y 29. Elijamos ahora el punto no-marcado 2 el cual está cubierto por $\mbox{\rm Cubo}(00a1a)$ y cubre a otros 3 no-marcados. Al incorporarlo quedan marcados 2, 3, 6 y 7. Hasta aquí llevamos 16 marcados. Al incorporar $\mbox{\rm Cubo}(001aa)$ cubrimos a los dos restantes 4 y 5. El recubrimiento mínimo es pues:

$$\mbox{\rm Cubo}(1a0aa) \cup \mbox{\rm Cubo}(1a0aa) \cup \mbox{\rm Cubo}(00a1a) \cup \mbox{\rm Cubo}(001aa).$$

Posterior: Ejercicios Arriba: Semántica Anterior: Mapas de Karnaugh