simplificacion de funciones booleanas

simplificacion de funciones booleanas

(Parte 1 de 9)

Simplificación de funciones booleanas. Circuitos lógicos mínimos.

Sistemas electrónicos digitalesMaterial de apoyo didactico

Los procedimientos de simplificación de funciones booleanas se desarollan con el propósito de obtener una expresión booleana mínima que permita construir un circuito con el menor número posible de puertas lógicas.

El criterio que vamos a utilizar es el de obtener un circuito mínimo en dos niveles. Esto se consigue a partir de una expresión booleana normalizada, bien como suma de productos, bien como producto de sumas, que sea mínima en cuanto al número de términos utilizados, (producto o suma) y mínima en cuanto al nº de literales de los mismos.

Este criterio no es único y, a veces, conduce a circuitos que presentan problemas de implementación práctica, (riesgos) que tienen solución introduciendo cierta redundancia en la expresión mínima. Además, objetivos de diseño como son fiabilidad y testabilidad, de especial importancia en el diseño de circuitos integrados, implican modificar el

Los métodos que vamos a estudiar son:

- Reducción Algebraica: Usa los teoremas y axiomas del álgebra de Boole para reducir una expresión dada.

- Mapas de Karnaugh: Método gráfico. Útil para simplificar manualmente funciones de hasta 6 variables.

- Método tabular de Quine-McCluskey. Algoritmo para la simplificación de cualquier función booleana, apropiado para ser programado. Especialmente útil para funciones de muchas variables y simplificación simultánea de varias funciones booleanas.

Simplificación de funciones booleanas criterio anterior. De todas formas, un circuito en dos niveles es un punto de partida adecuado para el diseño de sistemas digitales.

Simplificación de funciones booleanas. Metodo algebraico.

Sistemas electrónicos digitalesMaterial de apoyo didáctico

Método Agebraico Se basa en el siguiente teorema del Álgebra de Boole:

a) La suma de dos términos producto adyacentes es igual a un término producto que posee un literal menos, aquel en el que se diferencian.

Los términos producto de la expresión a) se dice que son adyacentes por coincidir en todos sus literales menos en uno, x1 .

El teorema puede leerse así:

b) El producto de dos términos suma adyacentes es igual a un término suma que posee un literal menos, aquel en el que se diferencean.

Para aplicar este método de simplificación:

1º. Se obtiene una expresión canónica, bien suma de productos, bien producto de sumas.

2º. Se buscan términos adyacentes y se sustituyen por términos más simples.

3º. El paso 2º se repite hasta encontrar una expresión irreducible.

Ej:

adyacencias de 2º orden

Los términos suma de la expresión b) se dice que son adyacentes por coincidir en todos sus literales menos en uno, x1.

Simplificación de funciones booleanas. Metodo algebraico.

Sistemas electrónicos digitalesMaterial de apoyo didáctico

Definiciones: Sean F(x1,...xn) y G(x1,...xn) dos funciones booleanas.

Si F cubre a G, se dice que G implica a F, o que G es implicante de F.

Se dice que F cubre a G si siempre que G toma el valor 1, Ftambien lo toma. F GÊ( )

Ej:

Un producto de literales p se dice que es implicante primo de una función booleana F, sii implica a F y además, cualquier subproducto (producto con menos literales) obtenido de p, no es implicante de F.

Vamos a llamar PF al conjunto de los implicantes primos de F.

Ej:

a) No son implicantes primos porque existe el subproducto wx que es b) Si es implicante primo porque implica a F y ni y,ni z son implicantes a) b) implicante de F. wx si es implicante primo porque implica a F y ni w , ni x son implicantes de F.

PF = {wx , yz } de F.

Simplificación de funciones booleanas. Metodo algebraico.

Sistemas electrónicos digitalesMaterial de apoyo didáctico

Tabla 1: Procedimiento sistemático para la obtención de una expresión mínima en forma de suma de productos de una función booleana.

1º Obtener el conjunto de implicantes primos.

2º Seleccionar, de entre éstos, los implicantes primos esenciales, y formar una expresión mínima.

3ºEliminar del conjunto de implicantes primos aquellos que cubran minitérminos que ya estén cubietos por los implicantes primos esenciales.

4ºVerificar que todos los minitérminos que hacen uno a la función dada están cubiertos por la expresión mínima obtenida, y si no es así, añadir a ésta los implicantes primos necesarios para conseguirlo.

Teorema:

Cualquier expresión irreducible en forma suma de productos de una función booleana F resulta de la unión de implicantes primos de F.

Definición:

Un implicante primo de una función F se dice que es esencial si cubre al menos a un minitérmino de la función que no puede ser cubierto por ningún otro implicante primo de la misma.

Ej:

PF = { yt , zt , yz } yt yz zt cubre a los minitérminos {0,2,8,10} cubre a los minitérminos {2,6,10,14} cubre a los minitérminos {6,7,14,15} yt yz son implicantes primos esenciales,

Simplificación de funciones booleanas. Metodo algebraico.

Sistemas electrónicos digitalesMaterial de apoyo didáctico

(Parte 1 de 9)

Comentários