SIMPLIFICACIÓN DE FUNCIONES POR ALGEBRA DE BOOLE. TABLA DE LA VERDAD. FORMAS CANÓNICAS.



Gracias a los postulados y teoremas vistos en el tema anterior podemos “simplificar” cualquier función Booleana. Entiéndase por simplificar a que podemos reducir a la misma a otra función que use menos compuertas o incluso menos variables que la original y aún así obtener los mismos resultados. La utilidad de ésto es evidente ya que a la hora de implementar nuestro diseño digital, haremos uso de menos componentes reduciendo así el tamaño del circuito y facilitando también dicha implementación.

Existen varias formas para reducir una función lógica y algunas de ellas serán vistas en los próximos temas pero en éste en particular, haremos las reducciones basándonos sólo en reglas del álgebra de Boole, o sea, manipulaciones algebraicas. Para este tipo de simplificación, no existen reglas preestablecidas. La mejor forma de simplificar una función de Boole por manipulación algebraica es por medio del tanteo por lo que el mejor amigo en este tipo de procedimiento es la práctica.

Veamos a continuación ejemplos de simplificaciones de funciones de Boole.

A + A'B

Sabemos, por ley distributiva, que ésto es igual a: (A + A')(A + B)

como A + A' = 1, entonces:

A + A'B = A + B

Queda claro que la reducción es importante ya que la primera usa una compuerta OR, una NOT y una AND, mientras que la segunda sólo usa una OR. Excelente. Ahora, haciendo uso de la tabla de la verdad que vimos en el tema anterior, veamos si ambas funciones obtienen el mismo resultado:

A

B

A + A'B

A + B

0

0

0

0

0

1

1

1

1

0

1

1

1

1

1

1

En efecto, amblas tablas de la verdad muestran el mismo resultado. Veamos más ejemplos.

A(A' + B)

Por ley distributiva, ésto es igual a AA' + AB y como por por el postulado 2, AA' = 0, entonces:

A(A' + B) = AB

COMENTARIO: Debido al principio dualidad que manifiesta el álgebra de Boole, esa conclusión era de esperarse. Este ejemplo es, por dualidad, la contraparte del primero.

Veamos las tablas de la verdad:

A

B

A(A' + B)

A B

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

Correcto.

ATENCIÓN: Estos ejemplos son bastante sencillos. Este tipo de reducción no es tan fácil para funciones más complejas. Por eso comenté que la mejor forma de entender este método es "practicando". A continuación, más ejemplos:

Simplificar:

  1. (x + y)(x + y')

  2. xyz + x'y + xyz'

  3. (x + y)'(x' + y')'

  4. B(DC' + DC) + AB

Respuestas:

Para el número 1:

(x + y)(x + y') por distributiva = xx + xy' + yx + yy'

Por conmutativa: yx = xy. Por términos complementarios yy' = 0, por lo tanto:

= xx + xy + xy' = por distributiva x(x + y + y') = por asociativa x(x + (y + y')), pero como y + y' = 1, entonces

= x(x + 1) = x (1) = x

Respuesta: (x + y)(x + y') = x

Este ejemplo es interesante ya que vemos que la función no sólo redujo los componentes (y de hecho los redujo de dos OR, una AND y un NOT a “cero” componentes) sino que también redujo el número de variables requeridas. Aquí se concluye que la variable 'y' no tiene efecto en el resultado lógico de la función. Veamos la tabla de la verdad de la función de Boole original:

X

Y

(X+Y)(X+Y')

0

0

0

0

1

0

1

0

1

1

1

1

Se ve que la función tiene el mismo valor que 'x'.

Para la 2:

xyz + x'y + xyz' por distributiva = xy(z +z') + x'y = xy(1) +x'y = y(x + x') = y

Se observa que se reducen el uso de tres variables, 5 AND, 2 OR y 2 NOT a una línea directa desde una variable (sin compuertas). Veamos la tabla de la verdad de la función y veamos si coincide con la variable y

X

Y

Z

XYZ+X'Y+XYZ'

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

0

1

1

0

1

1

1

1

1

PERFECTO!!!

El tercer caso:

(x + y)'(x' + y')' = (x'y')(xy) = xx'yy' = 0

¿Qué tal? Se usó distributivo, teorema de Morgan, asociativo y ley de los complementos (xx' = 0). Veamos la tabla de la verdad de la función:

X

Y

(x+y)'(x'+y')'

0

0

0

0

1

0

1

0

0

1

1

0

Siempre resulta cero.

El último:

B(DC' + DC) + AB = B(D(C + C')) + AB = BD + AB = B(D+A)

reduciendo 4 variables, 4 AND, 2 OR y una NOT a sólo 3 Variables, una AND y una OR. Veamos la tabla de la verdad:

A

B

C

D

B(DC'+DC)+AB

B(D+A)

0

0

0

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1

1

0

0

0

1

0

0

0

0

0

1

0

1

1

1

0

1

1

0

0

0

0

1

1

1

1

1

1

0

0

0

0

0

1

0

0

1

0

0

1

0

1

0

0

0

1

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

Siga haciendo ejercicios. La simplificación de funciones lógicas o de Boole es una parte importante en el diseño de aplicaciones lógicas.

DEFINICIONES: Un literal no se refiere más que a una variable de la función o a su complemento (A, B , x, y', etc). El ejemplo dos anterior, antes de la simplificación, tiene 8 literales. Un término es una operación que usa sólo una compuerta lógica sin importar el número de literales que ésta tenga. Por ejemplo XYZ' es un término de 3 literales. Sólo usa una compuerta AND para X, Y y Z'. El ejemplo dos anterior tiene 3 términos.



Complemento de una función

Cuando invertimos una función lógica F (eso quiere decir que cambiamos los ceros por uno y viceversa) obtenemos la función invertida F' lo cual se conoce como el complemento de F. Para calcular el complemento de una función Booleana podemos ayudarnos con el teorema de Morgan que vimos en el tema anterior. En aquella oportunidad vimos el teorema con sólo dos literales pero es fácilmente demostrable que también aplica a casos de 3 o más literales (de hecho, háganlo como ejercicio: Demostrar que (A+B+C)' = A'B'C'). El ejemplo más sencillo sería que si tenemos F = A, el complemento de F sería F' = A'. En el caso de funciones más complejas, puede usarse el teorema de Morgan tantas veces como sea necesario. Veamos algunos otros ejemplos:

Siendo F1 = A'BC' + A'B'C y F2 = A(B'C'+BC), halle los complementos de ambas funciones.

Respuestas:

F1' = (A'BC'+A'B'C)' que por Morgan es = (A'BC')'(A'B'C)' Por Morgan en ambos términos negados = (A+B'+C)(A+B+C')

F2' = (A(B'C'+BC))' = A' + (B'C'+BC)' = A' + ((B'C')'(BC)') = A' + (B+C)(B'+C') que a su vez puede simplificarse a = A' + (BB'+BC'+B'C+CC') = A' + BC' + B'C

El complemento de una función también puede ser hallado consiguiendo el dual de la función y luego invirtiendo todos sus literales.


FORMAS CANÓNICAS

Términos mínimos y máximos

Sabemos que podemos expresar el complemento de una variable gracias al uso del “tilde” ( ' ). Para el caso de que una función contenga dos variables A y B, con los que se puede formar los cuatro literales A, B , A' y B', existen sólo cuatro posibilidades de combinar éstas (o sea, 4 términos) a través de una AND y éstas son: AB, AB', A'B y A'B'. A cada una de estas cuatro combinaciones se les conoce como término mínimo (ó minterm) y su designación es mk donde k es un número entre 0 y 2n-1.

Se dice que un término es normal cuando las variables aparecen sólo una vez en dicho término ya sea en su forma directa o invertida (A o A'). Un término producto es aquel en el que los literales que contiene están relacionados sólo por una operación AND, por ejemplo (AB), (AB'C), (AD), etc. Por eso a los términos mínimos también se les conoce como “términos mínimos del producto normalizado”.

Teniendo las mismas variables del caso anterior, existen cuatro términos posibles de expresar a través de compuertas OR y estos son: (A+B), (A'+B), (A+B') y (A'+B'). A cada uno de éstos se les conoce como término máximo (ó maxterm) y su designación es Mk donde k es un número entre 0 y 2n-1.

Un término suma es aquel en el que los literales que contiene están relacionados sólo por una operación OR, por ejemplo (A+B), (A+C), (A+D+E), etc. Por eso a los términos máximos también se les conoce como “términos máximos de la suma normalizada”.

Los casos vistos anteriormente son con dos variables pero existen términos mínimos y máximos para cualquier número de ellas. Teniendo n variables posibles, el números de términos máximos y mínimos será siempre igual a 2n que serán las representaciones de todos los casos entre 0 y 2n – 1. Veamos una tabla que muestra ésto para un caso de 3 variables.

Variables

Términos mínimos

Términos máximos

X

Y

Z

Término

Designación

Término

Designación

0

0

0

x'y'z'

m0

x+y+z

M0

0

0

1

x'y'z

m1

x+y+z'

M1

0

1

0

x'yz'

m2

x+y'+z

M2

0

1

1

x'yz

m3

x+y'+z'

M3

1

0

0

xy'z'

m4

x'+y+z

M4

1

0

1

xy'z

m5

x'+y+z'

M5

1

1

0

xyz'

m6

x'+y'+z

M6

1

1

1

xyz

m7

x'+y'+z'

M7

Véase en la tabla que para cada combinación binaria posible, el término mínimo será aquella que haga 1 el resultado a través de la AND y el término máximo será el que haga 0 el resultado de la OR. Ambas son situaciones únicas. Para cada combinación binaria posible existe uno y sólo un término mínimo y sólo un término máximo. Observe también que son 3 variables, hay 2n = 23 = 8 combinaciones y que para los mk y Mk, k va entre 0 y 2n – 1 que se representa con el número decimal correspondiente a la combinación binaria (Ej: xyz = (101)2 = (5)10, entonces k=5).

Dada cualquier tabla de la verdad, es posible expresar algebraicamente una función lógica a través de sus términos mínimos. Ésto es creando dicha función para que contenga una OR entre todos los términos mínimos que hacen que dicha función sea “1”. Por ejemplo, si la función se hace uno cuando las variables son 010 entonces dicha función contendrá el término mínimo x'yz' que es el término que se hace 1 para esa combinación. Para profundizar un poco más, veamos la siguiente tabla de la verdad:

X

Y

Z

F1

F2

0

0

0

0

1

0

0

1

1

1

0

1

0

1

0

0

1

1

1

0

1

0

0

0

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

Entonces, F1 = 1 para:

F1 = x'y'z + x'yz' + x'yz + xyz (que es una OR entre m1, m2, m3 y m7)

y F2 = 1 para:

F2 = x'y'z' + x'y'z + xy'z + xyz' + xyz (que es una OR entre m0, m1, m5, m6 y m7)

CONCLUSIÓN: Cualquier función lógica puede ser expresada a través de una suma (OR) de términos mínimos.

Se puede formar el complemento de una función a través de términos mínimos haciendo una OR entre todos aquellos que hagan a dicha función 0. Por ejemplo, para la tabla de la verdad anterior:

F1' = x'y'z' + xy'z' + xy'z + xyz'

aplicando Morgan a esta función llegamos a que también es posible expresar algebraicamente una función lógica a través de sus términos máximos y ésto se hace creando una función que contenga una AND entre todos los términos máximos que hacen que la misma sea 0. Según la misma tabla de la verdad anterior:

F1 = (x+y+z)(x'+y+z)(x'+y+z')(x'+y'+z) = M0M4M5M6

De forma análoga:

F2 = M2M3M4

Recuerden ésto: LO QUE SIEMPRE BUSCAMOS EN UNA FUNCIÓN DE BOOLE ES LA COMBINACIÓN QUE HAGA QUE DICHA FUNCIÓN SEA CIERTA O UNO (1). Se ve que si uno de los términos suma es cero entonces la función se hará cero también. Por ellos la función NO puede contener ninguno de los términos máximos si queremos que se haga “cierta” dicha función.

CONCLUSIÓN: Cualquier función lógica puede ser expresada a través de un producto (AND) de términos máximos.

A las funciones de Boole que están expresadas como un producto de términos máximos o una suma de términos mínimos se le conoce como FORMA CANÓNICA de la función.

Algunas veces se hace conveniente expresar una función lógica en su forma canónica, digamos como una suma de términos mínimos. Pero hay veces que la función no contiene a todos los literales posible para el término. En esta caso lo que se hace es aprovechar los postulados de identidad y ley conmutativa para agregar al término los literales faltantes. ¿Cómo? Inspeccionamos toda la función. Si vemos que en alguno de sus términos falta una variable, digamos que A, entonces hacemos una AND del término con (A+A'). Como (A+A')=1 no alteramos el resultado del término. Luego aplicamos propiedad distributiva. Veamos un ejemplo para clarificar este punto:

Sea F = BC + AC' + AB, para hallar la forma canónica de esta función debemos hacer:

= BC(A+A') + AC'(B+B') + AB(C+C') = ABC +A'BC + ABC' + AB'C' + ABC + ABC', que por absorción es:

= ABC + A'BC + ABC' +AB'C' que son m7, m3, m6 y m4

NOTA: Como ejercicio, simplifique la expresión anterior a cuatro literales.

Hay ocasiones en las que expresar una función de Boole a través de su tabla de la verdad o de una de sus formas canónicas se hace tedioso debido a lo largo que se haría el trabajo. Es por ello que existe una forma de mostrar la misma función pero de manera abreviada. Ésto se hace expresando las funciones a través de una sumatoria (matemáticamente expresada por el signo Sigma mayúscula Σ ) o de una productoria (expresada por el signo PI mayúsculo Π usado también en los factoriales). La forma incluirá de un lado el nombre de la función (regularmente F ó Fn) y las variables que contiene entre paréntesis y del otro lado de la igualdad el número del término mínimo a incluir si es una sumatoria o el número de términos máximos si es una productoria con su respectivo signo sigma o pi. Tomemos como base las funciones F1 y F2 con las que hemos estado trabajando. Entonces:

F1(x,y,z) = Σ(1,2,3,7) = Π(0,4,5,6)

y

F2(x,y,z) = Σ(0,1,5,6,7) = Π(2,3,4)

Se conoce como Forma normalizada de una función a una función de Boole ya sea expresada como una suma de productos o un producto de sumas donde en cada término aparece uno de los literales ya sea una, dos o cualquier número de veces. Las formas canónicas son formas normalizadas de la función pero existen otras formas que no contienen todos los literales. Por ejemplo: F = x + x'y + xy'z es una forma normalizada de una función lógica ya que está compuesta por una suma de tres términos productos con uno, dos y tres literales respectivamente. La forma dual de esa función: F = x(x'+y)(x+y'+z) también es una función en su forma normalizada ya que contiene el producto de tres sumas. Son tres términos sumas con uno, dos y tres literales respectivamente. Por otra parte NO es una forma normalizada: F = (xy + wz)(x'y' + w'z'), pero puede convertirse en una si se aplica la propiedad distributiva, siendo entonces la suma de productos obtenida la siguiente: F = xyw'z' + x'y'wz (atención: los otros dos términos resultantes del postulado distributivo son cero y se omitieron)

Lo que queda ahora es hacer ejercicios. En la próxima clase virtual se verán algunos.

Si desea ampliar esta información, le recomiendo este enlace que está excelente. Refiere varios de los puntos vistos hasta ahora. Si quiere otra perspectiva, le recomiendo que vayan.

Para la próxima clase veremos el tema 4: Simplificación de funciones por el método de los mapas de Karnaugh.