Representación de Funciones Booleanas

Existen infinitas maneras de representar una función booleana. Así por ejemplo la función G = X + Y Z puede también representarse como G = X + X + YZ.  

Otras veces se suele utilizar  la forma negada o el complemento de la función. Para esto es se niegan los literales y se intercambian los AND y OR.

			_
Por ejemplo, el complemento de:	A	+	B	C
	_				_
es:	A	(	B	+	C	)

El complemento de una función no es la misma función, es la forma negada de la función.

En el álgebra de Boole es fundamental la existencia de una forma algebraica que proporcione explícitamente el valor de una función para todas las combinaciones de los valores de las variables. Es esta la forma canónica de la función.

Veamos antes algunos conceptos.

Definiciones:

Literal: se refiere a una variable o a su complemento (por ej. A, X,  )

Termino producto: es un grupo de literales que se encuentran relacionados entre si por un AND
(por ej. A·B, C·A, ·Y·Z ) 

termino suma:es un grupo de literales que se encuentran relacionados entre si por un OR
(por ej. A+B, C+A, +Y+Z ) 

termino normal: termino producto o termino suma en el que un literal no aparece mas de una vez

termino canónico: termino en el que se encuentra exactamente uno de cada uno de los literales de la función.Si el termino canónico es un producto, se denominará mintermino. Si es una suma se denominará maxtermino,

forma normal de una función: es la que está constituida por términos normales. Puede estar en la forma suma de términos productos o productos de términos sumas.

forma canónica de una función: es aquella constituida exclusivamente por términos canónicos que aparecen una sola vez.

Minimizacion de Funciones Booleanas

¿Que es la minimización? Básicamente es la simplificación de una función, obteniendo una expresión que contenga menos términos o menos variables que la función original. Esto se refleja en la obtención de circuito mas económicos por tener un menor numero de compuertas. La simplificación de estas funciones puede realizarse con el uso de álgebra de Boole pero no es un método sencillo de ejecutar. La manipulación de funciones booleana puede llegar a ser muy compleja y muchas veces es necesario un ingenio considerable y quizás mucha suerte. La minimización con álgebra de Boole presenta dos limitaciones importantes: No existe un algoritmo que nos garantice encontrar la forma mas simple de la expresión. · Dado un determinado resultado intermedio no hay forma de saber si realmente hemos llegado a la forma mínima. Para efecto de este curso cuando nos referimos a una expresión mínima, nos estamos refiriendo a la expresión mas simple de dos niveles. Forma de dos niveles Cualquier función booleana puede ser implantada con dos niveles de compuertas. Como se señaló anteriormente una función puede ser representada utilizando la forma suma de productos como: f = ( )+( )+( ) .......+ ( ) De esta manera los términos ( ) son productos de las variables de entrada (negadas o no ) que se realizan con compuertas AND. Los + se realizan con una compuerta OR de tantas entradas como términos productos haya en la función. Como resultado tendremos que la función puede realizase con dos niveles de compuertas: El nivel 1 representado por las compuertas AND y el nivel 2 representado por la compuerta OR, como se muestra en la figura. (En el nivel 1 se consideran también la variables negadas, que siendo formales se implantan con una compuerta NOT.)  Como señalamos anteriormente, la simplificación de las funciones lógicas es una meta importante por el hecho de que cuanto mas sencilla sea la función, más fácil será construir el circuito equivalente. El objetivo de la simplificación es el de minimizar el costo de implantación de una función mediante componentes electrónicos, donde el costo depende del número y complejidad de los elementos necesarios para construirla. La optimalidad de la simplificación utilizando Algebra de Boole depende de la habilidad del diseñador para aplicar la propiedad más adecuada en cada paso del proceso. Esta tarea se hace cada vez más difícil al crecer la complejidad de la expresión. Por ello, se utilizan algunos métodos que facilitan y automatizan el proceso de simplificación de las funciones lógicas, como lo son los Mapas de Karnaugh, y el método de Quine-McCluskey. (Para este curso solo se cubrirá el método de Mapas de Karnaugh) l En este punto, siendo la minimización el último paso antes de la implantación en el diseño de un sistema digital y antes de pasar a describir el método de minimización utilizando Mapas de Karnaugh, resumamos los diferentes pasos que deben seguirse en un problema de diseño de lógica combinacional. 1. Se toman las proposiciones y se simbolizan. 2. Se construye una tabla de verdad con todas las combinaciones posibles de las variables de entrada y se coloca un 1 para las combinaciones que cumplan con las condiciones de diseño. 3. Se obtiene la forma canónica Suma de productos tomando los minterminos de la tabla de verdad que sean iguales a 1. 4. Se simplifica la función utilizando Mapas de Karnaugh y se obtiene una expresión mínima de dos niveles 5. Se realiza el diagrama circuital y se implanta el circuito.

Algebra de Boole

En 1854 George Boole introdujo una notación simbólica para el tratamiento de variables cuyo valor podría ser verdadero o falso (variables binarias) Así el álgebra de Boole nos permite manipular relaciones proposicionales y cantidades binarias. Aplicada a las técnicas digitales se utiliza para la descripción y diseño de circuitos mas económicos. Las expresiones booleanas serán una representación de la función que realiza un circuito digital. En estas expresiones booleanas se utilizarán las tres operaciones básicas ( AND, OR NOT ) para construir expresiones matemáticas en las cuales estos operadores manejan variables booleanas (lo que quiere decir variables binarias).

Elementos del álgebra de Boole

Los símbolos elementales son:
· 0: representativo de FALSO
· 1: representativo de VERDADERO

Las operaciones fundamentales son:
· Conjunción u operación AND  (se representa con   ·  )
· Disyunción u operación OR (se representa con + )
· Complementación, Negación u operación NOT ( se representa con una barra sobre la variable,  )

Las variables son las proposiciones, que se representan o simbolizan por letras.

Postulados:

Los postulados para las tres operaciones básicas, AND, OR Y NOT, son suficientes para deducir cualquier relación booleana.

OR	AND	NOT
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1	0 · 0 = 0 0 · 1 = 0 1 · 0 = 0 1 · 1 = 1

Teoremas:

1. Regla del cero y la unidad a) X + 0 = X b) X + 1 = 1 c) X · 1 = X d) X · 0 = 0

2. Idempotencia o potencias iguales a) X + X = X b) X · X = X

3. Complementación a) X +  = 1 b) X ·  = 0

4. Involución

5. Conmutatividad a) conmutatividad del + X + Y = Y + X   b) conmutatividad del · X ·  Y = Y  · X

6. Asociatividad a) asociatividad del + X + (Y + Z) = (X + Y) + Z   b) asociatividad del · X ·  (Y  · Z) = (X  · Y)  · Z

7. Distribuitividad a) distribuitividad del + X + (Y · Z) = (X + Y) · (X + Z)   b) distribuitividad del · X · (Y + Z) = (X · Y) + (X · Z)

8. Leyes de absorción a) X · (X + Y)= X b) X · ( + Y)= X·Y c)  · (X + Y)= ·Y d) (X + Y) · (X + )= X e) X +  X·Y = X f) X + ·Y = X + Y g)   +  X·Y =  + Y h) X·Y + X·= X

9. Teoremas de De Morgan a)  b)  c)  d)

10. Teoremas generalizados de De Morgan a)  b)

Dualidad Los postulados y teoremas presentados anteriormente están representados en pares. La razón es que cada teorema posee lo que llamamos un dual. El dual de una expresión se obtiene intercambiando las ocurrencias de OR por AND, 0 por 1 y viceversa.. Si un teorema es valido, también lo será su dual, En efecto siguiendo el dual de la demostración del teorema, se obtiene la demostración del dual del teorema. Por ejemplo dado el postulado  0+0 = 0 se obtiene el dual haciendo 1·1 = 1

Se utilizaran los postulados y teoremas del álgebra de Boole para minimizar funciones booleanas. La simplificación de estas funciones con el uso de álgebra de Boole es un "arte". No existe un algoritmo que uno pueda seguir para garantizar que el resultado llegue a dar la forma más simple de expresión mínima. Como en el juego del ajedrez, con la práctica se va aprendiendo a reconocer patrones que nos guían hacia la solución.

Una pregunta importante que tenemos que hacernos es la de ¿que es simplificación? ¿Una expresión con menos literales? ¿Una expresión con menos operaciones? La respuesta depende de lo que deseamos optimizar, ¿velocidad? ¿Numero de interconexiones entre compuertas? ¿Numero de componentes?