Material Bool

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

Unidad 2 Álgebra de Boole y expresiones lógicas [email protected] [email protected]

⋅1⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

CONTENIDO Unidad 2. Álgebra de Boole y expresiones lógicas. 1. 2. 3. 4.

Fundamentos del álgebra de Boole. Operaciones y expresiones booleanas. Formas estándar de las expresiones booleanas. Expresiones booleanas, tablas de verdad y formas estándar. 5. Leyes y reglas del álgebra de Boole. 6. Teoremas de DeMorgan. 7. Minimización lógica algebraica. 8. Minimización lógica mediante mapas de Karnaugh. 9. Riesgos de temporización (estáticos y dinámicos). 10. Aplicación a los sistemas digitales.

OBJETIVOS ESPECÍFICOS ! ! ! ! ! ! ! ! ! ! !

Aplicar las leyes y reglas básicas del Álgebra de Boole. Aplicar los teoremas de DeMorgan a las expresiones booleanas. Describir los diagramas lógicos mediante expresiones booleanas. Evaluar las expresiones booleanas. Simplificar expresiones booleanas mediante las leyes y reglas del Álgebra de Boole. Convertir cualquier expresión booleana en una suma de productos y en un producto de sumas. Utilizar los mapas de Karnough para simplificar expresiones booleanas. Utilizar los mapas de karnough para simplificar tablas de verdad. Utilizar condiciones indiferentes para simplificar funciones lógicas. Identificar riesgos de temporización (estáticos y dinámicos). Aplicar el Álgebra de Boole y los mapas digitales a los sistemas digitales.

⋅2⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

1. FUNDAMENTOS DEL ÁLGEBRA DE BOOLE George Boole, lo desarrolló en 1854 para “poder expresar las leyes fundamentales del razonamiento en el lenguaje simbólico del Cálculo”. Fue Shannon, en 1838, quien lo adaptó para describir y analizar el comportamiento de los circuitos. El Álgebra Booleana parte de un conjunto de axiomas o postulados ( conjunto mínimo de definiciones que consideramos verdaderas) a partir de los cuales se construye el sistema matemático.

Abstracción digital (A1) X=0 si X≠1

(A1’) X=1 si X≠0

OJO!!! Se cumple el principio de dualidad

Función inversora (A2) Si X=0 entonces X’=1

(A2’) Si X=1 entonces X’=0

OJO!!! Se cumple el principio de dualidad

Definición formal de las operaciones básicas AND y OR (A3) 0.0 = 0 (A4) 1.1 = 1 (A5) 0.1 = 1.0 = 0

(A3’) 1+1 = 1 (A4’) 0+0 = 0 (A5’) 1+0 = 0+1 = 1

A continuación habrían que desarrollarse todos los teoremas, y comprobar que el sistema matemático constituye un “Álgebra”. Todos los teoremas se demuestran utilizando estos axiomas como punto de partida, mediante “inducción perfecta”. Nosotros vamos a estudiar el álgebra desde un punto de vista no tan formal. ⋅3⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

2. OPERACIONES Y EXPRESIONES BOOLEANAS (I) Mediante el Álgebra Booleana buscamos un método sistemático y versátil para la implementación de circuitos combinacionales. El Álgebra Booleana utiliza variables y operadores para obtener expresiones lógicas que representan un circuito combinacional. Luego describe una serie de teoremas que utilizaremos para manipular las expresiones lógicas.

Estados posibles 0: Estado Falso 1: Estado Verdadero

Variables Booleanas ! Se corresponden con señales de entrada, de salida o intermedias. ! Se representan mediante caracteres alfabéticos “A”, “B”, “X”... ! Pueden tomar dos valores (0 ó 1). ! Se denomina literal a una variable o a su complemento A, A’

Operadores Booleanos

⋅4⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

2. OPERACIONES Y EXPRESIONES BOOLEANAS (II) Ejemplo: Extracción de la expresión booleana de un sistema a partir de su diagrama lógico A partir del siguiente circuito lógico se nos pide que obtengamos su expresión booleana equivalente.

Ejemplo: Extracción de la expresión booleana de un sistema a partir de su tabla de verdad A partir de la siguiente tabla de verdad se nos pide que obtengamos su expresión booleana equivalente.

C = ( A.B) + (A .B) = A.B+ A .B

D = A.B.C + A.B.C + A.B.C

⋅5⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

2. OPERACIONES Y EXPRESIONES BOOLEANAS (III) Una vez que tenemos una expresión Booleana a partir de cualquiera de los métodos que hemos visto, veremos más adelante que será susceptible de simplificación utilizando los teoremas Boleanos. En esta caso, puede ser interesante saber generar un diagrama lógico a partir de su expresión Booleana.

Ejemplo: Extracción de un diagrama lógico de un sistema a partir de su expresión Booleana A partir de la siguiente expresión Booleana se nos pide que obtengamos su diagrama lógico equivalente.

C = A.B + A.B + ( A + B)

⋅6⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

3. FORMAS ESTÁNDAR DE LAS EXPRESIONES BOOLEANAS Existen dos formas estándar de representar expresiones booleanas:

• Suma de productos.

• Producto de sumas.

⋅7⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

4. EXPRESIONES BOOLEANAS, TABLAS DE VERDAD Y FORMAS ESTÁNDAR Como ya se ha visto, a partir de la tabla de verdad se puede obtener una expresión algebraica que la represente. Para ello se puede utilizar un operador OR que combine todas las expresiones que representan cada una de las filas de la tabla para los que la función vale 1.

A cada una de esas expresiones algebraicas se les denomina “minterms” o “ miniterminos” Maxiterms A + B+ C A + B’+ C A +B’+ C’ A’+ B + C’ A’+ B’ + C

Representar una tabla de verdad mediante productos de l os “maxterms” o “maxiterminos” es la forma dual. Cualquier función Booleana se puede expresar como suma me miniterminos (minterms) o como producto de maxiterminos (maxterms) y a estas formas se dice que está en forma canónica. ⋅8⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

5. LEYES Y REGLAS DEL ÁLGEBRA DE BOOLE Al igual que en otras áreas de las matemáticas, en el Álgebra de Boole existen una serie de reglas y leyes que tienen que seguirse para aplicarlo correctamente.

Leyes del Álgebra de Boole (son teoremas)

A+B = B+A (Conmutativa) A.B = B.A A+(B+C) = (A+B)+C (Asociativa) A.(B.C) = (A.B).C A.(B+C) = A.B + A.C (Distributiva) Reglas del Álgebra de Boole (son teoremas)

⋅9⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

6. TEOREMAS DE DeMORGAN (I) Primer teorema de DeMorgan

(X.Y)’ = X’+Y’

Segundo teorema de DeMorgan

(X+Y)’ = X’.Y’

Hemos visto el modo de obtener expresiones Booleanas a partir las tablas de verdad, pero no sabemos nada sobre si esas expresiones son las más simples posibles. Lo cual es importante ya que implica implementaciones sencillas, es decir reducir el número de componentes y por tanto reducir el coste de la aplicación final. Las leyes, reglas y teoremas Boléanos se pueden utilizar, entre otras razones, con este fin: simplificar las expresiones Booleanas ⇒ simplificar el diseño ⇒ reducir costes en la implementación del diseño

⋅10⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

6. TEOREMAS DE DeMORGAN (II) Como se verá más adelante en ocasiones resulta muy útil generar un circuito combinacional con un único tipo de compuerta. Para algunas familias lógicas las puertas NAND son las más sencillas.

Ejemplo: Obtención de un diagrama lógico de un sistema a partir de su expresión Booleana utilizando puertas NAND A partir de la siguiente expresión Booleana se nos pide que obtengamos su diagrama lógico equivalente utilizando exclusivamente puertas NAND. D = A.B.C + A.B.C + A.B.C

El Teorema de Morgan nos dice que:

A + B + C = A.B.C

Luego el circuito quedará del siguiente modo:

⋅11⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

6. TEOREMAS DE DeMORGAN (III) Para otras familias lógicas las puertas NOR son las más sencillas.

Ejemplo: Obtención de un diagrama lógico de un sistema a partir de su expresión Booleana utilizando puertas NOR A partir de la siguiente expresión Booleana se nos pide que obtengamos su diagrama lógico equivalente utilizando exclusivamente puertas NOR.

El teorema de Morgan nos dice que:

A.B.C = A + B + C

Luego finalmente el circuito quedará del siguiente modo:

⋅12⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

7. MINIMIZACIÓN LÓGICA ALGEBRAICA (I) El propósito de la minimización lógica es tomar una expresión algebraica y reducirla a una forma que sea más fácil de realizar:

! Simplificación algebraica (miniterminos)) ! Mapas de Karnaugh.

(i.e.:

suma

de

productos

Simplificación algebraica A partir de una expresión Booleana e su forma de suma de productos se combinan los términos, reduciendo la complejidad, mediante las reglas, leyes y teoremas del álgebra de Boole.

⋅13⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

7. MINIMIZACIÓN LÓGICA ALGEBRAICA (II) Ejemplo: Simplificar el número de puertas de un circuito Se pide simplificar el siguiente circuito mediante simplificación algebraica.

1º Se obtiene la función Booleana. D = A.B.C + B.C + A.B.C + A.B.C

2º Se simplifica utilizando las reglas. D = A.B.C + B.C + A.B.C + A.B.C = = A.B.C + B.C + B.C( A + A) = = A.B.C + B.C + B.C = = A.B.C + B.(C + C) = = A.B.C + B = = A.C + B

⋅14⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

8. MINIMIZACIÓN LÓGICA MEDIANTE MAPAS DE KARNAUGH (I) El mapa de Karnaugh es un método gráfico de representación de la información que se encuentra en una tabla de verdad.

"

"

Los cuadros adyacentes, tanto en forma horizontal como vertical, difieren en el estado de una variable (i.e. X-Y, X-Z). Esta propiedad no se aplica a los cuadros que se encuentran en una diagonal (i.e. Y-Z)

⋅15⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

8. MINIMIZACIÓN LÓGICA MEDIANTE MAPAS DE KARNAUGH (II) Utilización de los mapas de Karnaugh Los mapas de Karnaugh se van a utilizar para simplificar expresiones algebraicas. Para ello se hará lo siguiente: 1º) Representar en un mapa de Karnough la función algebraica o tabla de verdad que se deseé simplificar. 2º) Se agruparan los “1” siguiendo las reglas que a continuación se citan: a) Los grupos de celdas más grandes posibles deberán construirse primero; cada uno deberá contener 2n elementos. b) Deberán agregarse grupos cada vez más pequeños, hasta que cada celda que contenga un “1” se haya incluido por lo menos una vez. c) Deberán eliminarse los grupos redundantes (aun cuando se trate de grupos grandes) para evitar la duplicación.

⋅16⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

8. MINIMIZACIÓN LÓGICA MEDIANTE MAPAS DE KARNAUGH (III) Ejemplos de agrupamientos permitidos

⋅17⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

8. MINIMIZACIÓN LÓGICA MEDIANTE MAPAS DE KARNAUGH (IV) Ejemplos de agrupamientos no permitidos

Ejemplos de agrupamientos alternativos

⋅18⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

8. MINIMIZACIÓN LÓGICA MEDIANTE MAPAS DE KARNAUGH (V) Ejemplo: Simplificación de una expresión lógica Se pide simplificar la siguiente expresión: D = A.B.C + A.B.C + A.B.C + A.B.C + A.B.C + A.B.C

Quedando la siguiente expresión: D = B + A.C + A.C

Ejemplo: Simplificación de una expresión lógica Se pide simplificar la siguiente expresión:

D = A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D

En este caso para evitar redundancias hemos eliminado el grupo interior grande.

⋅19⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

8. MINIMIZACIÓN LÓGICA MEDIANTE MAPAS DE KARNAUGH (VI) Ejemplo: Simplificación de una expresión lógica Se pide simplificar la siguiente expresión: D = A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D

En este caso para evitar redundancias hemos eliminado el grupo interior grande.

Ejemplo: Simplificación de una expresión de cinco variables E = A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D

⋅20⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

8. MINIMIZACIÓN LÓGICA MEDIANTE MAPAS DE KARNAUGH (VII) Condiciones indiferentes

⋅21⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

9. RIESGOS DE TEMPORIZACIÓN (I) Un riesgo de 1 estático es un par de combinaciones de entrada que: 1) Difieren solamente en una variable de entrada. 2) Ambas proporcionan una salida 1. 3) Es posible que ocurra una salida 0 momentánea (glitch) durante una transición en la variable de entrada que difieren.

X=Y=1, e inicialmente Z=1 Un riesgo de 0 estático es un par de combinaciones de entrada que: 4) Difieren solamente en una variable de entrada. 5) Ambas proporcionan una salida 0. 6) Es posible que ocurra una salida 1 momentánea (glitch) durante una transición en la variable de entrada que difieren.

⋅22⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

9. RIESGOS DE TEMPORIZACIÓN (II) Hallando riesgos estáticos mediante el uso de mapas

Eliminación de riesgos estáticos mediante el uso de redundancias

⋅23⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

9. RIESGOS DE TEMPORIZACIÓN (III) Riesgos dinámicos Un riesgo dinámico es la posibilidad de un cambio en la salida más de una vez como resultado de una transición de entrada simple.

En las estructuras AND-OR u OR-AND no hay riesgo dinámico, si ninguna variable y su complemento no están conectadas a la misma compuerta de primer nivel.

⋅24⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

9. RIESGOS DE TEMPORIZACIÓN (IV) Diseño de circuitos libres de riesgo

• Los circuitos libres de riesgo se requieren normalmente en circuitos secuenciales de retroalimentación. • Las técnicas para analizar riegos en circuitos arbitrarios son difíciles de utilizar → utilizar estructuras sencillas de analizar. • Un circuito AND-OR de dos niveles no tiene riesgos dinámicos, ni de 0 estático. • En un circuito AND-OR los riesgos de 1 estático pueden ser eliminados con el método descrito. • De manera dual , un circuito OR-AND de dos niveles libres de riesgo puede diseñarse para cualquier función lógica utilizando mapas. • Lo dicho para AND-OR es aplicable a NAND-NAND. (A+B)’’=(A’.B’)’

• Lo dicho para OR-AND es aplicable a NOR-NOR. (A.B)’’=(A’+B’)’

⋅25⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

10. APLICACIONES A LOS SISTEMAS DIGITALES (I) Ejemplo: Diseñar un circuito para convertir números binarios de 3 bits a código Gray

El circuito combinacional que se busca debe cumplir con la siguiente tabla de verdad:

Aplicando Karnaugh tenemos lo siguiente:

Luego el circuito combinacional que buscamos podrá ser el siguiente:

⋅26⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

10. APLICACIONES A LOS SISTEMAS DIGITALES (II) Ejemplo: Diseñar un circuito que tome un número de 4 bits ABCD y produzca una sola salida Y que esté activa si la entrada representa un número primo

El circuito combinacional que se busca debe cumplir con la siguiente tabla de verdad, obteniéndose el correspondiente diagrama de Karnaugh:

⋅27⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

10. APLICACIONES A LOS SISTEMAS DIGITALES (III) Ejemplo: Diseñar un circuito que tome un número BCD y produzca una sola salida Y que esté activa si la entrada es: 1, 2, 5, 6 ó 9.

El circuito combinacional que se busca debe cumplir con la siguiente tabla de verdad, obteniéndose el correspondiente diagrama de Karnaugh:

⋅28⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

10. APLICACIONES A LOS SISTEMAS DIGITALES (IV) Ejemplo: Diseñar un decodificador BCD a siete segmentos (I).

⋅29⋅

Electrónica Industrial-ED5

Unidad 2. Álgebra de Boole y expresiones lógicas

10. APLICACIONES A LOS SISTEMAS DIGITALES (V) Ejemplo: Diseñar un decodificador BCD a siete segmentos (II).

⋅30⋅