Tema 4: Álgebra de Boole
Álgebra de Boole
Conjunto algebráico formado por un conjunto \(B = { 0, 1 }\) finito. Las variables pueden tomar el valor de verdadero o falso. Se pueden realizar las operaciones: \(\thicksim, +, \cdot\).
Operación NOT \(\thicksim\) ATTACH
| x | \(\thicksim x\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
Operación OR (+) ATTACH
| x | y | x + y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Operación AND (⋅) ATTACH
| x | y | x ⋅ y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Postulados
- Propiedad Clausura:
- \(x + y \in B\)
- \(x \cdot y \in B\)
- Los resultados son 0 ó 1
- Propiedad Conmutativa:
- \(x + y = y + x\)
- \(x \cdot y = y \cdot x\)
- Propiedad Distributiva:
- \(x + (y \cdot z) = (x \cdot y) + (x \cdot z)\)
- Elemento Identidad:
- \(x + 0 = x\)
- \(x \cdot 0 = x\)
- Elemento Complementado:
- \(x \cdot \overline{x} = 0\)
- \(x + \overline{x} = 1\)
Teorema Booleano por Inducción Perfecta
Si se comprueba la veracidad para cada caso particular, se cumple en el caso general. Por ejemplo: \(x \cdot (y + z) = (x + y) \cdot (x + z)\)
Principio de Dualidad
Los postulados presentan dos versiones intercambiando \(1 \leftrightarrow 0\) y \(+ \leftrightarrow \cdot\):
- \(x + 1 = 1\)
- \(x \cdot 0 = 0\)
Teoremas
- Doble Complementación: \(\overline{\overline{x}} = x\)
- Idempotencia: \(x + x = x | x \cdot x = x\)
- Identidad: \(x + 1 = 0 | x \cdot 0 = 0\)
- Absorción: \(x + x \cdot y = x | x \cdot (x + y) = x\)
- Asociativa: \(x + (y + z) = (x + y) + z\)
- Morgan: \(\overline{x + y} = \overline{x} \cdot \overline{y} | \overline{x \cdot y} = \overline{x} + \overline{y}\)
- Adyacencia: \(x \cdot y + x \cdot \overline{y} = x | (x + y) \cdot (x + \overline{y}) = x\)
- Consenso: \(x \cdot y + \overline{x} \cdot z + y \cdot z = x \cdot y + \overline{x} \cdot z | (x + y) \cdot (\overline{x} + z) \cdot (y + z) = (x + y) \cdot (\overline{x} + z)\)
- Simplificación: \(x + \overline{x} \cdot y = x + y | x \cdot (\overline{x} + y) = x \cdot y\)
Problema Lógico
Enunciado que se puede re-escribir o interpretarmediante relaciones entre variables de verdadero o falso.
Representación de Circuitos Digitales
Una función lógica es una expresión matemática que evalúa cuando una variable lógica toma el valor “verdadero” en función de los valores (“verdadero” o “falso”) de otras variables lógicas operados mediante las operaciones AND, OR y NOT.
Normalmente para escribir las funciones lógicas se usan los valores (0, 1). Mientras que la prioridad de los operadores de mayor a menor es:
- Not \(\thicksim\)
- AND \(\cdot\)
- OR \(+\)
Las funciones lógicas habitualmente se reescriben empleando expresiones equivalentes.
\(F_1 = C \cdot D(A + B) = A \cdot C \cdot D + B \cdot C \cdot D\)
Para una representación de circuitos lógicos se emplean las expresiones de las funciones lógicas. Y estos circuitos lógicos se implementan interconectando puertas lógicas:
Puerta Buffer (1 Entrada) ATTACH
| X | Z |
|---|---|
| 0 | 0 |
| 1 | 1 |
Puerta NOT o Inversor (1 Entrada) ATTACH
| X | Z |
|---|---|
| 0 | 1 |
| 1 | 0 |
Puerta NAND (2 o más entradas) ATTACH
| X | Y | Z |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Puerta AND (2 o más entradas) ATTACH
| X | Y | Z |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Puerta NOR (2 o más entradas) ATTACH
| X | Y | Z |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Puerta OR (2 o más entradas) ATTACH
| X | Y | Z |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Puerta EXNOR (2 o más entradas) ATTACH
| X | Y | Z |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Puerta EXOR (2 o más entradas) ATTACH
| X | Y | Z |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Cuando tenemos las mismas entradas (i.e. 2 ceros o 2 unos) nos devuelve cero, pero si son diferentes nos devuelve uno.
Minimización de Funciones Lógicas
Una misma especificación lógica puede expresarse con diferentes funciones lógicas si se sustituyen los términos de la función empleando los teoremas y postulados del álgebra de Boole. Todas estas ecuaciones que se obtengan a partir de los diferentes teoremas y postulados se consideran equivalentes.
Mientras que las funciones lógicas distintas dan lugar a circuitos lógicos distintos. Aunque, normalmente, al diseñador lo que le interesa es que un circuito sea lo más pequeño posible, es decir, emplear una función lógica con el menor número de térmnos y operaciones.
Simplificaciones
- \(\overline{\overline{X}} = X\)
- \(X + 1 = 1\) ó \(X \cdot 0 = 0\)
- \(X + 0 = X\) ó \(X \cdot 1 = X\)
- \(X + \overline{X} = 1\) ó \(X \cdot \overline{X} = 0\)
- \(X + X \cdot Y = X\) \(X \cdot (X + Y) = X\)
- \(X + \overline{X} \cdot Y = X + Y\) ó \(X \cdot (\overline{X} + Y) = X \cdot Y\)
- \(X \cdot Y + X \cdot \overline{Y} = X\) ó \((X + Y) \cdot (X + \overline{Y}) = X\)
- \(X \cdot Y + \overline{X} \cdot Z + Y \cdot Z = X \cdot Y + \overline{X} \cdot Z\) ó \((X + Y) \cdot (\overline{X} + Z) \cdot (Y + Z) = (X + Y) \cdot (\overline{X} + Z)\)
-
Ejemplos ATTACH
\((AB + C + D) (\overline{C} + D) (\overline{C} + D + E) = ?\)
- Aplicando el Teorema de Absorción \(X \cdot (X + Y) = X\), donde \(X = \overline{C} + D\) e \(Y = E\), la expresión podría reescribirse como:
\(= (AB + C + D)(\overline{C} + D) =\)
-
Aplicando la propiedad distributiva \((X + Y) \cdot (X + Z) = X + Y \cdot Z\), donde \(X = D\), \(Y = AB + C\) y \(Z = \overline{C}\), la ecuación queda:
\(= D + \overline{C} (C + AB) =\)
-
Por último, aplicando el Teorema de Simplificación \(X \cdot (\overline{X} + Y) = X \cdot Y\), donde \(X = \overline{C}\), \(\overline{X} = \overline{\overline{C}} = C\) e \(Y = A \cdot B\), la expresión queda simplificada como:
\(= D + AB\overline{C}\)
-
Minimización de Funciones Lógicas
También es posible obtener una función lógica a partir de una tabla de verdad con las formas canónicas de las funciones.
Para conseguirlo, son posibles dos razonamientos:
- Forma SOP: Suma de productos.
- Forma POS: Producto de sumas.
-
Razonamiento SOP ATTACH
La función es 1 si los valores de las entradas coinciden con los de una u otra (puerta OR) de las filas de la tabla de verdad que producen 1.
Coincidir con una fila significa que todas las entradas (puerta AND) tienen el valor de la entrada en la fila, donde 1 es la entrada y 0 la entrada complementada.
Ejemplo: \(F = (P, C, M) = P \cdot \overline{C} + M \cdot \overline{P}\)
Para obtener las expresiones canónicas se parte de la tabla de verdad calculada para esta ecuación. Y, a partir d las soluciones que han quedado con 1 en la tabla, se obtienen los minterms:
Con los minterms obtenidos, se escribe la función de la tabla (conocida como forma canónica SOP):
\(F(P, C, M) = \overline{PC} M + \overline{P} C M + P \overline{CM} + P \overline{C} M\)
Nota: Si el valor en la tabla de verdad de alguno de los términos es 0, pasa negado, y si es 1 pasa normal.
Sin embargo, esta ecuación no está simplificada. Para hacerlo, se aplica el Teorema de Adyacencia. A esta nueva función simplificada se le conoce con el nombre de forma estándar SOP:
\(F(P, C, M) = \overline{P}M + P\overline{C}\)
-
Razonamiento POS ATTACH
La función es 1 si los valores de las entradas no coinciden con ninguna (puerta AND) de las filas de la tabla de verdad que producen cero.
No coincidir con una fila significa que el valor de una u otra (puerta OR) de las entradas es distinto del valor en la fila, para lo que 1 es la entrada complementada y 0 sin complementar.
Ejemplo: \(F(P, C, M) = P \cdot \overline{C} + M \cdot \overline{P}\)
A partir de las soluciones que han quedado con 0, se obtienen los Maxterms:
Aquí se suman en función de la tabla:
\(F(P,C,M) = (P + C + M) (P + \overline{C} + M) (\overline{P} + \overline{C} + M) (\overline{P} + \overline{C} + \overline{M})\)
Nota: Cuando en la tabla tienen un valor de 1, pasa a la función negado.
Con esta función obtenemos la forma canónica POS, que no está simplificada. Para hacerlo, se aplica el Teorema de Adyacencia. A esta nueva función se le conoce como forma estándar POS:
\(F(P,C,M) = (P + M)(\overline{P} + \overline{C})\)
-
Notación Decimal ATTACH
Nosotros le podemos asignar un valor decimal a cada columna de la tabla:
A partir de la tabla, se puede escribir la expresión usando la notación decimal como:
\(F(P, C, M) = \sum(1, 3, 4, 5) = \prod (0, 2, 6, 7)\)
Escribimos los valores de 1 como sumatoria, y los valores 0 como producto.
-
Mapas de Karnaugh ATTACH
Otra forma de simplificar funciones algebráicas son los Mapas de Karnaugh. Estos mapas consisten en una representación bidimensional de la función que se pretende simplificar.
Los pasos a seguir praa simplificar una función a partir d esta estrategia son:
- Convertir la función que se pretende simplificar a una suma de productos
- Agrupar todos los 1 del mapa mediante rectángulos o cuadrados de 2^n elementos, donde N es el número de variables.
- Obtener la MSP (Suma de productos mínimos)
Ejemplo:
Ahora se realiza un Mapa de Karnaugh de 3 variables (AB en el eje horizontal y C en el veritcal) y se colocan los 1 que aparecen en la salida de la tabla:
Nótese que el término 11 se adelanta al término 10
A continuación, se usa la tabla para agrupar los 1 formando rectángulos del mayor tamaño posible:
Por último, buscan las variables que tienen en común los elementos que forman los rectángulos. La solución del problema es:
\(BC + AB + AC\)
-
Funciones Incompletamente Especificadas
Por último, es importante señalar que hay problemas lógicos en los que no están definidas todas las combinaciones de sus entradas. Este es el caso de las funciones incompletamente especificadas, que son aquellas en las que no importa el estado de la salida para ciertas combinaciones de entrada.
Estas se representan con el símbolo ∅.
