Álgebra de BOOLE

Tema 4 1. 2. 3. 4. 5. 6. 7. 8. 9.

Definición formal del álgebra de Boole. Leyes y reglas del álgebra de Boole. Operaciones y expresiones booleanas. Formas canónicas de las expresiones booleanas. Expresiones booleanas, tablas de verdad y formas estándar. Teoremas de DeMorgan. Minimización lógica algebraica. Minimización lógica mediante mapas de Karnaugh. Mapa de Karnaugh de cinco variables

Definición del Álgebra de BOOLE

Dr. Oscar Ruano - 2011-2012

2

Definición del Álgebra de BOOLE

Dr. Oscar Ruano - 2011-2012

3

Definición formal de operaciones básicas

Dr. Oscar Ruano - 2011-2012

4

Leyes y Reglas del Algebra de BOOLE

Dr. Oscar Ruano - 2011-2012

5

Teoremas de DeMORGAN


Primer teorema: el complemento de un producto de variables es igual a la suma de los complementos de las variables.




Segundo teorema: el complemento de una suma de variables es igual al producto de los complementos de las variables.



NOTA: Cada variable puede representar una combinación de variables (e.g. X puede ser = AB+C)

Dr. Oscar Ruano - 2011-2012

6

Principio de dualidad I


A toda relación o ley lógica le corresponderá su dual, formada mediante el intercambio de los operadores suma con los de producto, y de los 1s con los 0s.

Dr. Oscar Ruano - 2011-2012

7

Principio de dualidad II

(a)

X Y

type 2

Z

(b)

X Y

Z =X+Y

type 2

(c)

X Y

type 2

Z =X•Y

X

Y

Z

X

Y

Z

X

Y

Z

LOW

LOW

LOW

LOW

HIGH

HIGH

HIGH

LOW

HIGH

HIGH

HIGH

0 1 0 1

0 1 1 1

1 1 0 0

1 0 1 0

1 0 0

HIGH

0 0 1 1

Dr. Oscar Ruano - 2011-2012

0

8

Principio de dualidad III X1 X2 X3

type 1

type 2

type 2 type 1

X4 type 2

X5

type 1

type 1

type 1

type 2 Copyright © 2000 by Prentice Hall, Inc. Digital Design Principles and Practices, 3/e

Xn

X1′ X2′ X3′

type 1

F(X1, X2, ... , Xn)

type 2

type 2 type 1

X4′ X5′

type 2 type 1

Xn′

type 1

type 1

FD(X1′, X2′, ... , Xn′)

type 2 Copyright © 2000 by Prentice Hall, Inc. Digital Design Principles and Practices, 3/e

Dr. Oscar Ruano - 2011-2012

9

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.

Dr. Oscar Ruano - 2011-2012

10

Operaciones y expresiones booleanas II

Dr. Oscar Ruano - 2011-2012

11

Operaciones y expresiones booleanas III Ejemplo: Construcción de la Tabla de Verdad a partir de la expresión booleana



Un circuito lógico puede describirse mediante una tabla de verdad. Evaluar la expresión booleana para todas las posibles combinaciones de valores de las variables de entrada

X Y

Y′

X + Y′ (X + Y′ ) • Z

Z F = ((X + Y′) • Z) + (X′ • Y • Z′)

X′ X′ • Y • Z′ Z′

Dr. Oscar Ruano - 2011-2012

12

Operaciones y expresiones booleanas III

Dr. Oscar Ruano - 2011-2012

13

Formas normalizadas de las expresiones booleanas


Existen dos formas de representar expresiones booleanas:



Suma de Productos AND-OR



Producto de Sumas OR-AND

Dr. Oscar Ruano - 2011-2012

14

Expresiones booleanas, tablas de verdad y formas canónicas


Cualquier función Booleana se puede expresar como suma de miniterminos (minterms) o como producto de maxiterminos (maxterms) y a estas formas se les dice que están en forma estándar o canónica (el conjunto completo de variables del dominio está representado en cada término ).

F=ΣA,B,C (1, 4, 7) = A’B’C + AB’C’ + ABC

F= Π A,B,C (0, 2, 3, 5, 6) = (A+B+C)(A+B’+C)(A+B’+C’)(A’+B+C’)(A’+B’+C)

Dr. Oscar Ruano - 2011-2012

15

Operaciones y expresiones booleanas II

Dr. Oscar Ruano - 2011-2012

16

Propiedad universal de las puertas NAND


Las puerta NAND es una puerta universal porque puede emplearse para generar cualquier función lógica 

inversor



AND



OR

Dr. Oscar Ruano - 2011-2012

17

Propiedad universal de las puertas NOR


Las puerta NOR es una puerta universal porque puede emplearse para generar cualquier función lógica 

INVERSOR



AND



OR

Dr. Oscar Ruano - 2011-2012

18

Ejecución con puertas NAND y NOR

Dr. Oscar Ruano - 2011-2012

19

Ejemplo de ejecución con puertas NAND y NOR

Dr. Oscar Ruano - 2011-2012

20

Ejemplo de ejecución con puertas NAND y NOR

Dr. Oscar Ruano - 2011-2012

21

Ejemplo de propiedad universal de las puertas NAND

Dr. Oscar Ruano - 2011-2012

22

Ejemplo de propiedad universal de las puertas NOR

Dr. Oscar Ruano - 2011-2012

23

Simplificación mediante el álgebra de BOOLE


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 Mapas de Karnaugh

Simplificación Algebraica 



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

Dr. Oscar Ruano - 2011-2012

24

Forma canónica y normalizada


Se llama término canónico de una función lógica a todo producto o suma de literales en los cuales aparecen todas la variables en su forma directa o complementada.




Los términos canónicos producto reciben el nombre de “minitérminos”




Los términos canónicos suma reciben el nombre de “maxitérminos”




Una función de BOOLE está en forma canónica cuando se expresa como suma de minitérminos o producto de maxotérminos.




Dos funciones lógicas son equivalentes si, y solo si, sus formas canónicas son idénticas.




La expresión algebraica en suma de productos o productos de sumas en la que no todos los términos son canónicos recibe el nombre de normalizada

Dr. Oscar Ruano - 2011-2012

25

Forma canónica de la suma de productos


La metodología empleada en la transformación de una suma de productos a su forma canónica se basa en la regla 6, que establece que una variable sumada con su complemento es siempre igual a 1; A + A' = 1. Los pasos son los siguientes: 






Los términos producto que no contengan la(s) variable(s) del dominio, multiplicarlos por un término formado por dicha variable más el complemento de la misma (regla 6). Repetir el paso 1 para todos los términos de la expresión que no contengan todas las variables (o sus complementos) del dominio. Resolver los términos intervenidos.

Ejemplo 

Convertir la expresión booleana ABC' + BC + A' a su forma canónica.




Término BC




El dominio de la expresión es el conjunto de variables A, B y C. Se observa la falta de formato estándar para el segundo y tercer término producto. Sobre ellos se aplicará el procedimiento, para luego volver a agrupar toda la expresión: BC = BC ·(A+A') = ABC + A'BC

Término A’


A' = A'(C+C') = A'C+A'C' ; la expresión aún no tiene el formato canónico, entonces multiplicamos cada término por (B+B') A'C(B+B') +A'C'(B+B') = A'BC + A'B'C + A'BC' + A'B'C'

ABC' + BC + A' = ABC + A'BC + A'BC + A'B'C + A'BC' + A'B'C‘

Dr. Oscar Ruano - 2011-2012

26

Forma canónica del producto de sumas


La metodología empleada en la transformación de un producto de sumas a su forma canónica se basa en la regla 8, que establece que una variable multiplicada por su complemento es siempre igual a 0; AA' = 0. Los pasos son los siguientes: 

 

  

Los términos suma que no contengan la(s) variable(s) del dominio, sumarlos un término formado por dicha variable y su complemento según regla 8. Aplicar la regla 12: A + BC = (A+B)(A+C) Repetir el paso 1 para todos los términos de la expresión que no contengan todas las variables (o sus complementos) del dominio. Ejemplo Convertir la expresión booleana (A+B’+C)(B’+C+D’)(A+B’+C+D’) a su forma canónica. Término A+B’+C




A+B’+C = A+B’+C+DD’ = (A+B’+C+D)(A+B’+C+D’)

Término B’+C+D’


B’+C+D’ = B’+C+D’+AA’ =(A+ B’+C+D’)(A’+ B’+C+D’)

(A+B’+C)(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’)

Dr. Oscar Ruano - 2011-2012

27

Conversión entre formas canónicas Ejemplo: A’B’C’ +A’BC’+A’BC+AB’C+ABC Solución: (A+B+C’)(A’+B+C)(A’+B’+C)

Dr. Oscar Ruano - 2011-2012

28

Mapas de Karnaugh


Proporciona un método sistemático de simplificación de sentencias booleanas generando expresiones mínimas (‘receta de simplificación’) CARACTERÍSTICAS  Útiles para expresiones de dos, tres, cuatro y cinco variables  Es una matriz de 2n celdas en la que cada una representa un valor binario de las variables de entrada.  El orden de los valores en filas y columnas es tal que celdas adyacentes difieren únicamente en una varible  La simplificación de una determinada expresión consiste en agrupar adecuadamente las celdas  Un número mayor de variables exige el uso de un método llamado Quine-McClusky PASOS A SEGUIR  



Obtener la función lógica en suma de productos canónica Representar en el mapa de Karnaugh la función algebraica o tabla de verdad que se desee representar Agrupar unos (maximizar el tamaño de los grupos minimizando el número es estos):







Un grupo tiene que contener 1, 2, 4, 8 o 16 celdas Cada celda del grupo tiene que ser adyacente a una o mas celdas del grupo sin necesidad de que todas las celdas del grupo sean adyacentes entre sí. Incluir siempre en cada grupo el mayor número posible de 1s Cada 1 del mapa tiene que estar incluido en al menos un grupo. Los 1s que ya pertenezcan a un grupo pueden estar incluidos en otro, siempre que los grupos que se solapen contengan 1s no comunes.

Simplificar:


Eliminar variables que aparecen complementadas y sin complementar dentro del mismo grupo

Dr. Oscar Ruano - 2011-2012

29

Ejemplos agrupación & simplificación

Dr. Oscar Ruano - 2011-2012

30

Ejemplos de agrupamientos NO permitidos

Dr. Oscar Ruano - 2011-2012

31

Agrupamientos alternativos

Dr. Oscar Ruano - 2011-2012

32

Simplificación de 2 variables

Dr. Oscar Ruano - 2011-2012

33

Simplificación 3 variables

Dr. Oscar Ruano - 2011-2012

34

Simplificación 3 variables

Dr. Oscar Ruano - 2011-2012

35

Simplificación 3 variables

Dr. Oscar Ruano - 2011-2012

36

Simplificación 4 variables

Dr. Oscar Ruano - 2011-2012

37

Simplificación 4 variables

Dr. Oscar Ruano - 2011-2012

38

Simplificación 4 variables

Dr. Oscar Ruano - 2011-2012

39

Simplificación 5 variables

Mapa con A=0 colocarlo encima del mapa A=1. Cada celda del mapa A=0 es adyacente con la celda que está justo debajo en el mapa A=1

Dr. Oscar Ruano - 2011-2012

40

Condiciones indiferentes

Dr. Oscar Ruano - 2011-2012

41

Condiciones indiferentes

Dr. Oscar Ruano - 2011-2012

42