Quine

Juan Medina Molina

Universidad Polit´cnica de Cartagena e

´ METODO DE QUINE-McCLUSKEY
Sea K un ´lgebra de Boole y f una funci´n booleana de orden n sobre K. Denotamos a o por B = {0, 1}.Para obtener una expresi´n simplificada de f realizamos los siguientes o pasos: 1. Calculamos su tabla de verdad. 2. Ordenamos los valores cuya imagen es 1 en una columna de arriba a abajo en n´mero u decreciente de unos. Separamos ´stos en bloques de forma que los elementos de cada e bloque tengan el mismo n´mero de unos. u 3. Comparamos cada elemento de cada bloque con cada uno de loselementos del bloque inferior de forma que si dos de estos elementos difieren en un unico valor, les antepon´ dremos un + y escribiremos en una nueva columna, el elemento que se obtiene al sustituir oınea cuando dicho valor por un gui´n. Separaremos los elementos resultantes por una l´ acabemos de comparar dos bloques. 4. Repetimos el proceso anterior con la nueva columna obtenida y as´sucesivamente ı hasta que s´lo tengamos una unica columna con un unico bloque o bien, cuando de los o ´ ´ bloques que se tengan, no existan elementos que difieran s´lo en un valor de otro elemento o delbloque siguiente. 5. Rellenamos una tabla donde escribimos en la primera fila las secuencias de unos y ceros correspondientes a los ´tomos de f , en la primera columna las secuencias con guionesque a no llevan + obtenidas anteriormente, y en cada recuadro interior correspondiente a un a ´tomo y uno con gui´n, escribiremos un asterisco si todos los valores de ambos, sin contar o loselementos con guiones coinciden. 6. Finalmente, de cada columna elegimos un asterisco de forma que el n´ mero de filas u donde hayan sido elegidos asteriscos sea el menor posible. La suma de loselementos de la primera columna que contienen asteriscos elegidos junto u con los elementos de la primera fila en cuya columna no hay ning´ n asterisco es una expresi´n booleana simplificada de f. o