Álgebra Booleana y Compuertas Lógicas

Axiomas y Propiedades de Álgebra Booleana

Sea $B$ un conjunto de elementos: $B = \{a, b, c, \ldots\}$ y el conjunto $\{0, 1\}$
Sea $\Phi$ un conjunto de operaciones binarias: $\Phi = \{+, \cdot, '\}$ (or, and, not)

Estos elementos conforman un álgebra de Boole si se cumplen los axiomas:

• Clausura: $\;a, b \in B \implies a + b, \; a \cdot b \in B$

• Conmutatividad: $\;a + b = b + a, \; a \cdot b = b \cdot a$

• Axioma del $0$: $\; \exists \; 0 \in B \; | \; a + 0 = a, \; a \cdot 0 = 0$

• Axioma del $1$: $\; \exists \; 1 \in B \; | \; a + 1 = 1, \; a \cdot 1 = a$

• Distributividad de $+$ respecto a $\cdot$, $\;a \cdot (b + c) = a \cdot b + a \cdot c$

• Distributividad de $\cdot$ respecto a $+$, $\;a + b \cdot c = (a + b) \cdot (a + c)$

• Inverso: $\;a \in B \implies \exists \; a' \in B \; | \; a + a' = 1, \; a \cdot a' = 0$

• Cardinalidad: $\;|B| \geq 2$

También se encuentran los siguientes teoremas:

• Ley de Morgan: $(a + b)' = a' \cdot b', \; (a \cdot b)' = a' + b'$

• Involución: $(a')' = a$

• Absorción: $a + ab = a, \; a(a+b) = a, \; a + a'b = a + b$

Funciones Booleanas

Una función booleana es una función que toma valores booleanos y devuelve valores booleanos. Se puede representar mediante una tabla de verdad.

Ejemplo: $F_1 = x + y'z$

Compuertas Lógicas

Las compuertas lógicas son circuitos electrónicos que realizan operaciones booleana según los valores de entrada.

Estas son las compuertas con su respectiva ecuación:

Las compuertas NOR y NAND son universales, estas compuertas pueden representar las funciones NOT, AND, OR.

Las funciones booleanas se pueden representar mediante compuertas lógicas. Es posible simplificar las funciones booleanas como suma de minitérminos $m_i$ o producto de maxitérminos $M_i$

Tomemos la tabla de verdad de tres variables binarias:

Una función $f = x'y'z' + xyz\;$ se puede expresar como $f = m_0 + m_7$

Mapas de Karnaugh

Los mapas de Karnaugh son una herramienta para simplificar funciones booleanas. Cada cuadrado representa un minitérmino y se agrupan los cuadrados que contienen $1$‘s.

Un mapa de dos variables se ve así:

Si queremos representar una función de tres variables como $f(x, y, z) = \sum (2, 3, 4, 5)$ (suma correspondiente a minitérminos) en un mapa de Karnaugh, se vería así:

Para mantener ese orden solo un bit cambia por columna. El cuadrado $m_5$, por ejemplo, corresponde a la fila $1$ y a la columna $01$. Concatenados son $101$, es decir, en decimal $5$.

Al igual que con una tabla de verdad, podemos expresar la función como suma de minitérminos o producto de maxitérminos. Para ello agrupamos en forma de cuadrado/rectángulo los $1$‘s’ o $0$‘s, respectivamente.

Una vez agrupados, tenemos una expresión canónica de la función, que se puede simplificar. En este ejemplo si sumamos minitérminos no es necesario reducir.

Dependiendo el caso, podemos marcar una celda con una $X$ si su valor es indiferente. Dependiendo los valores del mapa, puede resultar más sencillo agrupar $0$ o $1$.

Funciones pares e impares

La función par es un detector de paridad entre $0$‘s o $1$‘s, esta se puede simplificar como $f = (A \oplus B \oplus C)'$
La función impar es un detector de imparidad entre $0$‘s p $1$‘s, esta se puede simplificar como $f = A \oplus B \oplus C$

Un generador de paridad par en un mensaje de tres bits podría verse así:

Esto funciona como una detección de bits erróneos en un mensaje, necesitando un verificador de errores de paridad que compare el mensaje con el detector de paridad:

Cuando el verificador es $1$, se sabe que hay un error en el mensaje (activo por alto).