Á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\)

Leyes de Morgan

Sean \(a, b \in B:\) \((a + b)' = a' \cdot b', \; (a \cdot 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 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\).

Observando el mapa, sumando los elementos que contienen \(1\)‘s, se obtiene: \(f(x, y, z) = x'y + xy'\)

Dependiendo el caso, podemos marcar una celda con una \(X\) si su valor es indiferente.

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.