Dos expresiones booleanas o dos circuitos son equivalentes cuando producen la misma salida para todas las combinaciones posibles de entrada.
Un mismo comportamiento lógico puede representarse de varias formas. Podemos escribirlo como una expresión booleana, como una tabla de verdad o como un circuito de puertas lógicas.
Cuando dos representaciones producen exactamente las mismas salidas, decimos que son equivalentes.
Dos expresiones booleanas son equivalentes si tienen el mismo valor de verdad en todos los casos posibles.
A ∧ B ≡ B ∧ ALa equivalencia anterior se cumple porque cambiar el orden de las entradas de AND no cambia la salida.
Dos circuitos son equivalentes cuando, para las mismas entradas, siempre producen la misma salida.
No importa si usan distinta cantidad de puertas o si están dibujados de manera diferente. Lo importante es el comportamiento de salida.
La forma más directa de comprobar equivalencia es construir una tabla de verdad para ambas expresiones y comparar sus salidas.
Si las columnas finales coinciden fila por fila, las expresiones son equivalentes.
Comparemos A ∧ B con B ∧ A.
| A | B | A ∧ B | B ∧ A |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Como las dos columnas finales son iguales, las expresiones son equivalentes.
También podemos demostrar equivalencias usando leyes del álgebra booleana.
A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)Esta equivalencia corresponde a la ley distributiva. Permite transformar un circuito en otro con el mismo comportamiento.
Para convertir una expresión en circuito, cada operador se reemplaza por una puerta lógica.
S = (A ∧ B) ∨ CPrimero A y B entran a una puerta AND. Luego la salida de esa AND y la señal C entran a una puerta OR.
Para convertir un circuito en expresión, se lee desde las entradas hacia la salida.
Si A y B entran a una puerta OR, y esa salida entra junto con C a una puerta AND, la expresión es:
S = (A ∨ B) ∧ CUna expresión simplificada debe ser equivalente a la expresión original. Simplificar no significa cambiar el comportamiento, sino representarlo con menos operaciones o con una forma más clara.
(A ∧ B) ∨ (A ∧ ¬B) ≡ ALa expresión de la izquierda puede requerir varias puertas; la de la derecha solo necesita la señal A.
Comparemos (A ∧ B) ∨ (A ∧ ¬B) con A.
| A | B | ¬B | A ∧ B | A ∧ ¬B | Resultado | A |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 1 |
Las dos últimas columnas coinciden, por lo tanto la simplificación es válida.
Las leyes de De Morgan permiten transformar negaciones de operaciones compuestas.
¬(A ∧ B) ≡ ¬A ∨ ¬B
¬(A ∨ B) ≡ ¬A ∧ ¬BEstas equivalencias son muy útiles para reemplazar combinaciones de puertas por circuitos alternativos.
Como NAND y NOR son puertas universales, un circuito puede rediseñarse usando solo una de estas puertas.
El circuito resultante puede verse diferente, pero si conserva la misma tabla de verdad, es equivalente al original.
Cuando dos circuitos son equivalentes, puede convenir elegir el más simple.
Algunos criterios comunes son:
En programación también buscamos condiciones equivalentes pero más claras.
if ((activo && permiso) || (activo && !permiso)) {
ejecutar();
}La condición puede simplificarse a:
if (activo) {
ejecutar();
}Ambas tienen el mismo comportamiento lógico.
Las expresiones booleanas y los circuitos equivalentes muestran que una misma lógica puede representarse de distintas maneras. La clave es verificar que todas produzcan la misma salida para cada combinación de entradas.
En el próximo tema estudiaremos la lógica aplicada a condiciones en programación.