Karnaugh y Quine–McCluskey: dos formas de quitarle lo estorboso a una regla

Cuando describes un concepto en términos de sí y no —¿tiene alas? ¿tiene pico? ¿vuela?— acabas con una función booleana: una combinación de condiciones que da verdadero o falso.

Y esas funciones crecen. Agregas casos, agregas excepciones, agregas condiciones para cubrir las excepciones de las excepciones, y terminas con algo enorme que ya no puedes usar aunque sea correcto.

Simplificar una función booleana es el mismo problema que simplificar una fracción, sólo que con más pasos. Y, como con las fracciones, sí existe metodología. Hay dos clásicas.

El método de Karnaugh: verlo

Es una forma gráfica. Acomodas todas las combinaciones posibles de tus condiciones en una tabla especialmente ordenada, marcas las que dan verdadero, y entonces lo que buscas se vuelve visible: grupos de casillas contiguas.

Cada grupo que encuentras significa lo mismo: dentro de ese grupo, alguna de las condiciones dejó de importar. Si el resultado es verdadero tanto si la condición se cumple como si no, esa condición se puede borrar de esa parte de la regla.

Al final juntas los grupos y tienes una versión mucho más corta que dice exactamente lo mismo: te quedaste con lo que sí tiene valor para describir el concepto, y tiraste lo que sólo estaba ocupando lugar.

La ventaja es que se entiende de un vistazo. La desventaja es que sólo funciona con pocas variables; con más de cinco o seis, la tabla deja de poderse leer y el método pierde su gracia.

Quine–McCluskey: calcularlo

Es la versión mecánica del mismo objetivo. Es un algoritmo tal cual: una serie de pasos que se pueden seguir sin criterio ni intuición, y por lo tanto se pueden programar.

Compara sistemáticamente todas las combinaciones que dan verdadero, va detectando pares que difieren en una sola condición —que es justo el caso en que esa condición no importa— y las va fusionando. Repite hasta que no queda nada más que fusionar. Después elige, del conjunto resultante, el subconjunto más pequeño que cubre todos los casos.

No es bonito de hacer a mano y no importa: no está hecho para hacerse a mano. Está hecho para que lo haga una computadora cuando el problema tiene demasiadas variables para dibujarlo.

Lo que tienen en común

Los dos parten de lo mismo: si el resultado no cambia cuando cambias una condición, esa condición sobra.

Es una idea que sirve mucho más allá de la lógica booleana. La mayoría de las reglas que arrastramos —en un programa, en un proceso de trabajo, en una decisión— tienen condiciones que ya no cambian nada, que se agregaron para un caso que ocurrió una vez y que nadie ha vuelto a revisar.

Quitarlas no requiere un método formal. Requiere hacerse la misma pregunta que se hacen estos dos: si esto fuera falso, ¿cambiaría el resultado?

Este texto sale del episodio 004 del Podcast Algoritmos, sobre simplificar.