Álgebra de Boole y mapas de Karnaugh: leyes y simplificación

Álgebra de Boole: sus leyes, las de De Morgan y cómo simplificar una función con el mapa de Karnaugh, con un mapa para practicar.

El álgebra de Boole es el álgebra de los circuitos digitales: trabaja solo con dos valores, 0 y 1, y con tres operaciones, la suma lógica (OR), el producto lógico (AND) y la negación (NOT). Sus leyes sirven para simplificar una función lógica, y el mapa de Karnaugh hace lo mismo sin cuentas, agrupando unos en una cuadrícula. Una función más corta es un circuito con menos puertas.

⏱ 11 min · Por Jaime Aniorte, profesor de Tecnología

➜ Qué es · Las leyes · De Morgan · Simplificar · El mapa de Karnaugh · Ejemplos · Preguntas frecuentes

Qué es el álgebra de Boole

En 1854, el matemático inglés George Boole publicó un libro para escribir la lógica, las frases que son verdaderas o falsas, con símbolos y reglas, como si fueran números. Casi un siglo después, en 1937, Claude Shannon se dio cuenta de que esas mismas reglas describían los circuitos de interruptores. Desde entonces, el álgebra de Boole es la herramienta con la que se diseña todo lo digital.

Sus variables solo valen 0 o 1, los dos dígitos del sistema binario, y tiene tres operaciones:

• La suma lógica, A + B, es la puerta OR: vale 1 si vale 1 al menos una. Por eso, en esta álgebra, 1 + 1 = 1.
• El producto lógico, A · B, es la puerta AND: vale 1 solo si valen 1 las dos.
• La negación, A (A con una barra encima, «no A»), es la puerta NOT: le da la vuelta al valor.

Si todavía no conoces las puertas, empieza por puertas lógicas: allí están las siete, con su tabla de verdad y sus símbolos.

Las leyes del álgebra de Boole

Casi todas van por parejas: la misma ley con la suma y con el producto. Basta cambiar + por ·, y 0 por 1, para pasar de una columna a la otra.

Y una más, muy útil para simplificar, que sale de la distributiva y del complemento: A + A · B = A + B. Se lee así: si A ya vale 1, da igual lo demás; y si no, basta con B.

Dos de ellas sorprenden porque en los números de siempre no se cumplen: A + A = A (la idempotencia) y la distributiva de la suma, A + B · C = (A + B) · (A + C). En el álgebra normal, 2 + 3 · 4 no es lo mismo que (2 + 3) · (2 + 4).

Cómo se comprueba una ley: con su tabla de verdad

En el álgebra de Boole cada variable solo puede valer 0 o 1, así que una ley se demuestra probando todas las combinaciones. Si las dos columnas salen iguales en todas las filas, la ley es cierta. Esta es la tabla de la distributiva que sorprende:

Las columnas en verde, A + B · C y (A + B) · (A + C), coinciden en las ocho filas: la ley se cumple. Con 3 variables hay 2³ = 8 combinaciones; con 4, 16.

Las leyes de De Morgan

Son las dos leyes que más se usan, porque dicen cómo se niega una suma o un producto entero. La regla para recordarlas: para romper la barra, se niega cada letra y la operación cambia (el · pasa a +, y el + a ·).

A · B = A + B   y   A + B = A · B

Con puertas se ve mejor. La primera ley dice que una NAND hace lo mismo que una OR con las dos entradas negadas; la segunda, que una NOR hace lo mismo que una AND con las entradas negadas.

Por eso la NAND y la NOR se llaman puertas universales: con una sola de ellas se monta cualquier circuito. Con De Morgan también se quitan barras largas. Por ejemplo, A · B = A + B = A + B.

Simplificar una función con las leyes: un ejemplo resuelto

La alarma de una casa debe sonar si se abre la puerta (A) o la ventana (B), pero solo si está conectada (C). Su tabla de verdad tiene un 1 en las filas 3, 5 y 7, y la función que sale de la tabla, sumando un producto por cada 1 (la función canónica), es:

S = A · B · C + A · B · C + A · B · C

De tres productos de tres letras a una OR y una AND: dos puertas. Y la función final es justo la frase del enunciado: «la puerta o la ventana, y conectada». El problema de este método es que hay que ver qué ley aplicar en cada paso, y con 4 variables es fácil perderse. Para eso está el mapa de Karnaugh.

El mapa de Karnaugh: simplificar sin cuentas

El mapa de Karnaugh es la tabla de verdad colocada en una cuadrícula, con una casilla por fila de la tabla. Con 2 variables es de 2 × 2; con 3, de 2 × 4 (A en las filas y BC en las columnas); con 4, de 4 × 4 (AB en las filas y CD en las columnas).

El truco está en el orden de las filas y las columnas: no van contando en binario (00, 01, 10, 11) sino en el orden de Gray, 00, 01, 11, 10, en el que de una a la siguiente solo cambia una letra. Así, dos casillas que se tocan solo se diferencian en una variable, y esa variable desaparece al juntarlas. Las reglas:

1. Se agrupan los unos, nunca los ceros.
2. Cada grupo es un rectángulo de 1, 2, 4, 8 o 16 casillas: nunca de 3 ni de 6, y nunca en diagonal.
3. Los bordes se tocan: la columna de la izquierda es vecina de la de la derecha, y la fila de arriba, de la de abajo. Las cuatro esquinas forman un grupo.
4. Los grupos pueden solaparse: un 1 puede estar en dos grupos si así cada grupo es más grande.
5. Hay que usar los menos grupos posibles y que cada uno sea lo más grande posible.
6. Cada grupo da un producto con las letras que no cambian dentro de él: negada si vale 0 y sin negar si vale 1. La función es la suma de esos productos.

Dos ejemplos resueltos con el mapa

En Bachillerato aparecen las casillas «indiferentes» (una X): combinaciones que nunca se dan, y que se pueden tratar como 1 si eso hace un grupo más grande.

Con las leyes o con el mapa: comparación

Pruébalo en el simulador

El modo «Karnaugh» del simulador de puertas lógicas es un mapa para practicar con tus propias tablas. Lo que puedes hacer:

• Rellenar la tabla de 2, 3 o 4 variables tocando cada casilla, o coger la de un circuito que hayas montado.
• Agrupar los unos en el mapa y comprobarlo: si un grupo no vale, podría ser mayor o te sobra alguno, te lo dice.
• Ver un agrupamiento mínimo con su función y montar el circuito simplificado con un toque.

En «Del problema al circuito» tienes ocho problemas que acaban en un mapa, y el nivel 3 de «Practica» propone mapas al azar.

En mis clases, el fallo que más se repite en Karnaugh no es agrupar mal, sino olvidar que los bordes se tocan: por eso el ejemplo de la figura tiene un grupo en las esquinas y otro que da la vuelta de arriba abajo.

Errores típicos (y cómo no caer en ellos)

• Pensar que 1 + 1 = 2. En el álgebra de Boole, 1 + 1 = 1: la suma es una OR.
• Romper la barra de De Morgan sin cambiar la operación. A · B no es A · B, sino A + B.
• Ordenar el mapa contando en binario. Las filas y las columnas van 00, 01, 11, 10.
• Hacer grupos de 3, de 6 o en diagonal. Solo rectángulos de 1, 2, 4, 8 o 16.
• Olvidar que los bordes se tocan. Las esquinas, la primera y la última fila, y la primera y la última columna son vecinas.
• Quedarse con grupos pequeños. Cuanto mayor es el grupo, menos letras tiene su producto.
• Dejar algún 1 sin agrupar. Todos los unos tienen que estar en algún grupo, aunque sea solo.

Preguntas frecuentes

¿Qué es el álgebra de Boole?

Es un álgebra en la que las variables solo valen 0 o 1 y las operaciones son la suma lógica (OR), el producto lógico (AND) y la negación (NOT). La creó George Boole en 1854 y es la base de los circuitos digitales.

¿Cuáles son las leyes del álgebra de Boole?

Las principales son el elemento neutro, el elemento nulo, la idempotencia, el complemento, la doble negación, la conmutativa, la asociativa, la distributiva, la absorción y las leyes de De Morgan. Casi todas van por parejas: una con la suma y otra con el producto.

¿Qué dicen las leyes de De Morgan?

Que la negación de un producto es la suma de las negaciones, A · B = A + B, y que la negación de una suma es el producto de las negaciones, A + B = A · B. Con puertas: una NAND equivale a una OR con las entradas negadas.

¿Para qué sirve el álgebra de Boole en tecnología?

Para escribir con letras lo que hace un circuito de puertas lógicas y para simplificarlo: una función más corta es un circuito con menos puertas, más barato y con menos cables. Con ella se diseñan desde una alarma hasta un procesador.

¿Qué es un mapa de Karnaugh?

Es la tabla de verdad de una función colocada en una cuadrícula ordenada en código Gray. Agrupando los unos vecinos en rectángulos de 1, 2, 4, 8 o 16 casillas se obtiene la función simplificada sin hacer cuentas de álgebra.

¿Por qué el mapa de Karnaugh va en el orden 00, 01, 11, 10?

Porque es el orden de Gray: de una fila o columna a la siguiente solo cambia una letra. Así, dos casillas vecinas solo se diferencian en una variable, y esa variable desaparece cuando se agrupan.

¿Cómo se hacen los grupos en un mapa de Karnaugh?

Se rodean los unos con rectángulos de 1, 2, 4, 8 o 16 casillas, nunca en diagonal, teniendo en cuenta que los bordes se tocan. Hay que usar los menos grupos posibles y hacerlos lo más grandes que se pueda, aunque se solapen.

¿Qué es mejor, simplificar con las leyes o con el mapa de Karnaugh?

Para funciones de 2 a 4 variables que vienen de una tabla, el mapa de Karnaugh: es más rápido y te asegura la expresión más simple. Las leyes van mejor para expresiones cortas, para demostrar una igualdad y para aplicar De Morgan.

Para seguir: las siete puertas, con sus tablas y sus chips, en puertas lógicas. Los ceros y unos, en el sistema binario. Y para practicar todo esto, el simulador de puertas lógicas.