Videos: Simplificacion de Funciones Booleanas

SIMPLIFICACIÓN DE FUNCIONES BOOLEANAS

Ejercicios 

SIMPLIFICACIÓN DE FUNCIONES BOOLEANAS - Ejercicio #1

SIMPLIFICACIÓN DE FUNCIONES BOOLEANAS - Ejercicio #2

SIMPLIFICACIÓN DE FUNCIONES BOOLEANAS - Ejercicio #3

Videos: Teoremas del Álgebra de Boole

TEOREMAS DEL ÁLGEBRA DE BOOLE (1er TEOREMA DE DEMORGAN)

TEOREMAS DEL ÁLGEBRA DE BOOLE (2do TEOREMA DE DEMORGAN)

Videos: Leyes del Algebra de Boole

LEYES DEL ÁLGEBRA DE BOOLE (Leyes conmutativas)

LEYES DEL ÁLGEBRA DE BOOLE (Leyes asociativas)

LEYES DEL ÁLGEBRA DE BOOLE (Ley distributiva)

Videos: Compuertas Lógicas

COMPUERTA LÓGICA NOT (Inversor lógico)

COMPUERTA LÓGICA AND (Multiplicación lógica)

COMPUERTA LÓGICA OR (Suma lógica)

COMPUERTA LÓGICA NAND (AND negada)

COMPUERTA LÓGICA NOR (OR negada)

COMPUERTA XOR (OR Exclusiva)

Puertas Lógicas XNOR (NOR Exclusiva)

Ejercicios de Álgebra de Boole

Ejercicio 1

        Hacer circuito con pulsadores, tabla de verdad, circuito con compuertas lógicas, expresión booleana sintetizada y mapa k.

Respuesta

Ejercicio 2

            Dada la tabla de verdad, encontrar la función algebraica, el circuito con llave y la

compuerta lógica.

Respuesta Ejercicio 3             Resolver minimizando:  Respuestas

Tema #10 Minimización 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 Álgebra 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.

 

 

 

Tema 9# Compuertas Lógicas

            Las Compuertas Lógicas son circuitos electrónicos conformados internamente por transistores que se encuentran con arreglos especiales con los que otorgan señales de voltaje como resultado o una salida de forma booleana, están obtenidos por operaciones lógicas binarias (suma, multiplicación). También niegan, afirman, incluyen o excluyen según sus propiedades lógicas. 

            Existen diferentes tipos de compuertas y algunas de estas son más complejas, con la posibilidad de ser simuladas por compuertas más sencillas. Todas estas tienen tablas de verdad que explican los comportamientos en los resultados que otorga, dependiendo del valor booleano que tenga en cada una de sus entradas.

            Ademas de las que antes hemos estudiado: AND, OR y NOT, tendremos las siguientes:

Compuerta NAND

        También denominada como AND negada, esta compuerta trabaja al contrario de una AND ya que al no tener entradas en 1 o solamente alguna de ellas, esta concede un 1 en su salida, pero si esta tiene todas sus entradas en 1 la salida se presenta con un 0.

Compuerta NOR

         Así como vimos anteriormente, la compuerta OR también tiene su versión inversa. Esta compuerta cuando tiene sus entradas en estado 0 su salida estará en 1, pero si alguna de sus entradas pasa a un estado 1 sin importar en qué posición, su salida será un estado 0.

Compuerta XOR

        También llamada OR exclusiva, esta actúa como una suma binaria de un dígito cada uno y el resultado de la suma seria la salida. Otra manera de verlo es que con valores de entrada igual el estado de salida es 0 y con valores de entrada diferente, la salida será 1.

Compuerta XNOR

        Esta es todo lo contrario a la compuerta XOR, ya que cuando las entradas sean iguales se presentara una salida en estado 1 y si son diferentes la salida será un estado 0.

Compuerta IF

        Esta compuerta no es una muy utilizada o reconocida ya que su funcionamiento en estados lógicos es parecido a si solo hubiera un cable conectado porque exactamente lo que se le coloque en la entrada, se encontrara en la salida. Pero también es conocido como un buffer, en la práctica se utiliza como amplificador de corriente o como seguidor de tensión para adaptar impedancias.

Tema 8# Expresiones de conmutación

        Un símbolo x es una variable booleana si representa a cualquier elemento de un conjunto B sobre el que se ha definido un Algebra de Boole. Una función booleana o de conmutación es una expresión algebraica de variables booleanas con las operaciones +, * y complemento

Literal: 

        Es toda ocurrencia de una variable, ya sea complementada o sin complementar, en una expresión de conmutación.

Por ejemplo: En la expresión de conmutación:

A · B + C · A + D + B · 1

A, B, C y D son Variables.

A, B, C, A, D y B son Literales.

1 es una Constante.

Dual:

        Esta expresión se obtiene, intercambiando las operaciones AND por OR (y viceversa), e intercambiando las constantes 0 por 1 y 1 por 0 en la expresión de conmutación.

Por ejemplo: Para la expresión de conmutación:

(A · B) + (C · D) + 0

La Expresión Dual es:

(A + B) · (C + D) · 1

Tema 7# Teoremas y postulados del Álgebra Boole

Postulados       

  

            Un álgebra de Boole es toda clase o conjunto de elementos que pueden tomar dos valores perfectamente diferenciados, que designaremos por 0 y 1 y que están relacionados por dos operaciones binarias denominadas suma (+) y producto (.) (la operación producto se indica en general simplemente mediante la ausencia de símbolo entre dos variables) lógicos que cumplen los siguientes postulados:

 

a) Ambas operaciones son conmutativas, es decir, si a y b son elementos del álgebra, se verifica:

 

a + b = b + a                    a . b = b . a

 

b) Dentro del álgebra existen dos elementos neutros, el 0 y el 1, que cumplen la propiedad de identidad con respecto a cada una de dichas operaciones:

 

0 + a = a                         1 . a = a

 

c) Cada operación es distributiva con respecto a la otra:

 

a . (b + c) = a . b + a . c                       a + (b . c) = (a + b) . (a + c)

 

d) Para cada elemento, a, del álgebra existe un elemento denominado, ā  , tal que:

 

a + ā = 1                          a . ā = 0

 

    Este postulado define realmente una nueva operación fundamental que es la inversión o complementación de una variable. La variable ā se encuentra siempre en un estado binario contrario al de a.

 

    La primera ecuación expresa la imposibilidad de que a y ā tomen el valor lógico cero al mismo tiempo y la segunda ecuación indica que nunca pueden tener el valor lógico uno al mismo tiempo.

 

    De lo explicado anteriormente se deduce que el álgebra de Boole es un ente matemático. En realidad, son físicamente varios los conjuntos que poseen dos operaciones binarias que cumplen los postulados desarrollados. Ejemplos de estos conjuntos son el álgebra de las proposiciones formales y el álgebra de la conmutación formad también por elementos que pueden tomar dos estados perfectamente diferenciados.

 

    Los primeros circuitos de conmutación o lógicos utilizados han sido los contactos, y aunque poco a poco han sido desplazados por los circuitos electrónicos, pueden ser empleados para memorizar más fácilmente las leyes del álgebra de Boole antes expresadas y los teoremas que desarrollaremos seguidamente.

 

    La operación suma se asimila a la conexión en paralelo de contactos y la operación producto a la conexión en serie. El inverso de un contacto es otro cuyo estado es siempre opuesto del primero, es decir está cerrado cuando aquel está abierto y viceversa. El elemento 0 es un contacto que está siempre abierto y el elemento 1 un contacto que está siempre cerrado. Además se considera una función de transmisión entre los dos terminales de un circuito de contactos, que toma el valor 1, cuando existe un camino para la circulación de corriente entre ellos (cortocircuito) y el valor 0 al no existir dicho camino (Circuito abierto).

Teoremas

 

        Basándose en los postulados anteriores se deducen los teoremas que expondremos seguidamente. Su demostración se puede realizar algebraicamente mediante la llamada tabla de verdad. La tabla de verdad de una expresión algebraica binaria representa los valores que dicha expresión puede tomar para cada combinación, de estados de las variables que forman parte de la misma. Dos expresiones algebraicas que tienen la misma tabla de verdad son equivalentes.

Teorema 1: 

        Cada identidad deducida de los anteriores postulados del álgebra de Boole permanece válida si la operación + y . y los elementos 0 y 1 se intercambian entre si.

        Este principio, llamado de dualidad, se deduce inmediatamente de la simetría de los cuatro postulados con respecto a ambas operaciones y ambos elementos neutros.

Teorema 2: 

        Para cada elemento a de un álgebra de Boole se verifica:

                             a + 1 = 1                          a . 0 = 0

Teorema 3:

        Para cada elemento a de un álgebra de Boole se verifica:

                            a + a = a                          a . a = a

Teorema 4: 

        Para cada par de elementos de un álgebra de Boole a y b, se verifica:

 

                           a +ab = a                         a . (a + b) = a

        Esta ley se llama de absorción.

Teorema 5: 

        En álgebra de Boole, las operaciones suma y producto son asociativas:

 

                           a + (b + c) = (a + b) + c = a + b + c

                          a . (b . c) = ( a . b) . c = a . b . c 

Teorema 6: 

        Para todo elemento ā de un álgebra de Boole se verifica:

                                                 ā = a

       Estas igualdades se llaman leyes de De Morgan

Tema 6# Reglas del Álgebra de Boole

1- A + 0 = A

2- A + 1 = 1

3- A x 0 = 0

4- A x 1 = A

5- A + A = A

6- A + ̄ A = 1

7- A x A = A

8- A x ̄ A = 0

9- ̄ ̄ A = A

10- A + AB = A

A + AB = AA + AB = A (1 + B) Sacar factor común A

(ley distributiva)

= A ·1 Regla 2: (1 + B) = 1

= A Regla 4: A ·1 = A

11- A + ̄ AB = A + B

A+ ̄ AB = (A + AB)+ ̄ AB Regla 10: A = A + AB

= A + (A + ̄ A) B Sacar factor común

= A + 1 ·B Regla 6: A + ̄ A= 1

= A + B Regla 4: A ·1 = A

12- (A + B) (A + C) = A + BC

(A + B)(A + C) = AA + AC + AB + BC   Ley distributiva

= A + AC + AB + BC          Regla 7: AA = A

= A + BC                Regla 10: A + AB = A (x2 veces)

Tema #5 Simplificación de funciones Booleanas

         Al usar los teoremas y leyes booleanas, podemos simplificar las expresiones booleanas, mediante las cuales podemos reducir el número requerido de compuertas lógicas a implementar. Podemos simplificar la función Boolean utilizando dos métodos:

• El Método de Mapa Karnaugh. 

        Un mapa de Karnaugh (también conocido como tabla de Karnaugh o diagrama de Veitch, abreviado como Mapa-K o Mapa-KV) es un diagrama utilizado para la simplificación de funciones algebraicas Booleanas. El mapa de Karnaugh fue inventado en 1953 por Maurice Karnaugh, un físico y matemático de los laboratorios Bell.

    Los mapas de Karnaugh reducen la necesidad de hacer cálculos extensos para la simplificación de expresiones booleanas, aprovechando la capacidad del cerebro humano para el reconocimiento de patrones y otras formas de expresión analítica, permitiendo así identificar y eliminar condiciones muy inmensas.

        El mapa de Karnaugh consiste en una representación bidimensional de la tabla de verdad de la función a simplificar. Puesto que la tabla de verdad de una función de N variables posee 2N filas, el mapa K correspondiente debe poseer también 2N cuadrados. Las variables de la expresión son ordenadas en función de su peso y siguiendo el código Gray, de manera que sólo una de las variables varía entre celdas adyacentes. La transferencia de los términos de la tabla de verdad al mapa de Karnaugh se realiza de forma directa, albergando un 0 ó un 1, dependiendo del valor que toma la función en cada fila. Las tablas de Karnaugh se pueden fácilmente realizar a mano con funciones de hasta 6 variables, para funciones de mayor cantidad de variables es más eficiente el uso de software especializado.

           Al calcular el numero de renglones y columnas debemos tomar en cuenta:

        Normalmente suele representarse como un mapa cuadrado (número de renglones = número de columnas) cuando el número de variables es par (2, 4, 6, 8... etc) y cuando el número de variables es impar el número de renglones igual a la mitad del número de columnas; siguiendo la siguientes fórmulas:

          Cuando el número de variables es par:

                                 

          Cuando el número de variables es impar:

                                                  

                                                   

Ejemplo:

          Dada la siguiente función algebraica booleana representada como el sumatorio de sus minitérminos, y con las variables Booleanas A, B, C, D, la función se puede representar con dos notaciones distintas:

                               

Tabla de Verdad

        Las variables de entrada pueden combinarse de 16 formas diferentes, por lo que el mapa de Karnaugh tendrá 16 celdas, distribuidas en una cuadrícula de 4 × 4. La razón por la cual en las tablas de 4 variables (por ejemplo) hay una transición de una columna rotulada como "01" a otra "11" (en vez de "10" que sería el próximo valor binario) se debe a que es un requisito en la construcción del mapa que en cada nueva columna (de izquierda a derecha) sólo varíe una variable a la vez. Entonces, al "01" le sigue el "11", de tal forma que sólo varía el primer bit, cosa que no ocurriría si se pasará del "01" al "10" (porque cambiarían ambos bits a la vez).

• El Método Algebraico. 

      Para la simplificación por este método no sólo bastará con conocer todas las propiedades y teoremas del álgebra de Boole, además se debe desarrollar una cierta habilidad lógico-matemática que se adquiere fundamentalmente con la experiencia.

            Como ejemplo se simplificará la siguiente función:

                    F = A’C’ + ABC + BC’ + A’B’C + A’BC

            Observando cada uno de los sumando podemos ver que hay factores comunes en los sumandos 2º con 5º y 4º con 5º que conllevan simplificación:

                   F = A’C’ + BC’ + BC(A + A’) + A’C(B + B’)

            Note que el término 5º se ha tomado dos veces, de acuerdo con la propiedad que dice que A + A = A. Aplicando las propiedades del álgebra de Boole (A + A' = 1 y A . 1 = A), queda

                   F = A’C’ + BC’ + BC + A’C

               Repitiendo nuevamente el proceso,

                    F = A’( C’ + C) + B( C’ + C) = A’ + B

            No siempre las funciones son tan fáciles de simplificar como la anterior. El método algebraico, por lo general, no resulta cómodo para los no expertos, a los cuales, una vez simplificada una ecuación le pueden quedar serias dudas de haber conseguido la máxima simplificación.

• Numérico de Quine-McCluskey

        El algoritmo Quine-McCluskey permite la simplificación de funciones lógicas de cualquier número de variables y es el que se utiliza para diseñar aplicaciones informáticas en las que se necesite obtener funciones simplificadas.

              A continuación se indican los pasos a seguir en este método a partir de un ejemplo.

            Se expresa la función a simplificar en su forma canónica de suma de productos.

            Sea la siguiente función a simplificar:

               

            Se forma una tabla con el valor decimal de la combinación, el estado de las variables y el índice (número de unos que contiene el estado de las variables).

        Se agrupan las combinaciones cuyos estados difieren en una sola variable, sustituyéndola por un guion bajo (_). Las combinaciones utilizadas se marcan con un aspa (X). Hay que fijarse en las combinaciones cuya diferencia entre sus respectivos índices es la unidad.

            Se repite el proceso anterior las veces que sean necesarias y se van eliminando estados idénticos.

           

           Se forma una tabla con las combinaciones finales y las no agrupadas. Se toman como filas las combinaciones finales y las no agrupadas y como columnas los valores decimales de dichas combinaciones. Cada celda que contenga el valor decimal de una combinación se marca con un aspa. A continuación nos fijamos en aquellas columnas con una sola aspa; sus combinaciones serán esenciales. Finalmente se toman aquellas combinaciones de los valores decimales no seleccionados, teniendo precaución de no tomar aquellas combinaciones cuyos valores decimales hayan sido ya tomados en otras combinaciones. La función simplificada final viene dada por las combinaciones esenciales y estas últimas.