Algebra de boole y simplificacion logica

Algebra de boole y simplificacion logica

1. Circuitos Digitales
Unidad 4
Algebra de Boole y Simplificacion Lógica
Ing. Roberto Espitia Steer
E-mail:[email protected]
Universidad Autónoma del Caribe -2012

2. Operadores y Expresiones
Booleanas

3. Operaciones y Expresiones Booleanas
•Addition
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
•Multiplication
0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1

4. Leyes y Reglas del Algebra de
Boole

5. Leyes del algebra de Boole
•Ley Conmutativa
•Ley Asociativa
•Ley Distributiva

6. Leyes del Algebra de Boole
•Ley Conmutativa de la Suma:
A + B = B + A

7. Leyes del Algebra de Boole
•Ley Conmutativa de la Multiplicacion:
A * B = B * A

8. Leyes del Algebra de Boole
•Ley Asociativa de la Suma:
A + (B + C) = (A + B) + C

9. Leyes del Algebra de Boole
•Ley Asociativa de la Multiplicacion:
A * (B * C) = (A * B) * C

10. Leyes del Algebra de Boole
•Ley Distributiva:
A(B + C) = AB + AC

11. Reglas del Algebra Booleana

12. Reglas del Algebra Booleana
•Regla 1
OR Truth Table

13. Reglas del Algebra Booleana
•Regla 2
OR Truth Table

14. Reglas del Algebra Booleana
•Regla 3
AND Truth Table

15. Reglas del Algebra Booleana
•Regla 4
AND Truth Table

16. Reglas del Algebra Booleana
•Regla 5
OR Truth Table

17. Reglas del Algebra Booleana
•Regla 6
OR Truth Table

18. Reglas del Algebra Booleana
•Regla 7
AND Truth Table

19. Reglas del Algebra Booleana
•Regla 8
AND Truth Table

20. Reglas del Algebra Booleana
•Regla 9

21. Reglas del Algebra Booleana
•Regla 10: A + AB = A
AND Truth TableOR Truth Table

22. Reglas del Algebra Booleana
•Regla 11:BABAA 
AND Truth TableOR Truth Table

23. Reglas del Algebra Booleana
•Regla 12: (A + B)(A + C) = A + BC
AND Truth TableOR Truth Table

24. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 24
Simplificación Mediante algebra de Boole
•Muchasveces,alahoradeaplicarelálgebrabooleana,hayquereducirunaexpresiónasu
formamássimpleocambiarlaaunaformamásconvenienteparaconseguirunaimplementación
máseficiente.
•Estemétododesimplificaciónutilizalasreglas,leyesyteoremasdelÁlgebradeBoolepara
manipularysimplificarunaexpresión.
•Unaexpresiónbooleanasimplificadaempleaelmenornumeroposibledecompuertasenla
implementacióndeunadeterminadaexpresión.
Ejemplo:MediantelastécnicasdelalgebradeBoole,simplificarlasiguienteexpresión.

25. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 25
Circuito Lógico Original Y Simplificado.
A partir de lasimplificación se obtienen dos redes de puertas equivalentes:
•Se pasa de cinco a dos puertas necesarias para implementarla expresión.
•Para cualquier combinación de valores de entrada A, B y C, se obtiene siempre la
misma salida.

26. Teorema de DeMorgan’s

27. Teorema de DeMorgan’sYXXY 
•Teorema 1
•Teorema 2YXYX 
Recuerda:
“Romper la Barra,
Cambia el Signo”

28. Formas Estandar de Expresiones
Booleanas

29. Formas Estandar de Expresiones Booleanas
•Forma de suma de productos (SDP)
Ejemplo: X = AB + CD + EF
•Forma de productos de suma (PDS)
Ejemplo: X = (A + B)(C + D)(E + F)

30. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 30
Aplicaciones de los teorema de Demorgan

31. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 31
Ejemplos De Aplicación De Los Teoremas de
Demorgan

32. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 32
Ejercicios Partiendo de Compuertas Lógicas

33. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 33
Análisis Booleano de los Circuitos Lógicos
•ElÁlgebradeBooleproporcionaunamaneraconcisadeexpresarelfuncionamiento
deuncircuitológicoformadoporunacombinacióndepuertaslógicas,detalforma
quelasalidapuededeterminarseporlacombinacióndelosvaloresdeentrada.Para
obtenerlaexpresiónbooleanadeundeterminadocircuitológico,lamanerade
procederconsisteen:
A.Comenzarconlasentradassituadasmásalaizquierda.
B.Iravanzandohastalaslíneasdesalida,escribiendolaexpresiónparacada
compuerta.

34. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 34
Formato estándar de las expresiones booleanas
Funciónlógicaesunaexpresiónbooleanaquerelacionavariableslógicasdirectaso
complementadaspormediodeoperacionesANDyOR.
Todaslasexpresionesbooleanas,independientementedesuforma,pueden
convertirseencualquieradelasdosformasestándar:
–SumadeproductosoSumadeMinTerminos
–ProductodesumasoProductodeMaxTerminos.
Estoposibilitaquelaevaluación,simplificacióneimplementacióndelas
expresionesbooleanaseamuchomássistemáticaysencilla

35. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 35
Suma de productos o suma de Minterminos.
o•Es la suma de dos o másproductos mediante la adición booleana.
o AB + ABC
o A + ABC + AC
o•Una barra no puede extenderse sobre más de una variable:
o
oEl dominio de una expresión booleana es el conjunto de variables (o sus
complementos) contenido en una expresión:
oEl dominio de AB + ABC esel conjunto de variables A, B, C
o•La implementación de una suma de productos simplemente requiere aplicar la
operación OR a las salidas de dos o más puertas AND:

36. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 36
Producto de Sumas o Producto de Maxterms
•Eslamultiplicacióndedosomástérminossuma.
•Unabarranopuedeextendersesobremásdeunavariable:
Implementación de un Producto de Sumas.
Laimplementacióndeunproductodesumasrequieresimplementelaaplicacióndela
operaciónANDalassalidasdedosomáspuertasOR.

37. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 37
Los Mapas de Karnaugh

38. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 38
Mapas de Karnaugh
•UnmapadeKarnaughproporcionaunmétodosistemáticodesimplificacióndeexpresionesbooleanas.
•Aplicadoadecuadamentegeneralasexpresionessumadeproductosyproductodesumasmássimples
posibles.
•UnmapadeKarnaughessimilaraunatabladeverdad,yaquemuestratodoslosposiblesvaloresdelas
variablesdeentradaylasalidaresultanteparacadavalor.
ElmapadeKarnaughesunasecuenciadeceldasenlaquecadaceldarepresentaunvalorbinariodelas
variablesdeentrada.
•Lasceldassedisponendetalmaneraquelasimplificacióndeunadeterminadaexpresiónconsisteen
agruparadecuadamentelasceldas.
•LosmapasdeKarnaughpuedenutilizarseparaexpresionesdedos,tres,cuatroycincovariables.
•ElmétododeQuine-McCluskypuedeusarseparaunnúmerodevariablesmayor.
•Aligualqueocurríaconelnúmerodefilasdeunatabladeverdad,elnúmerodeceldasdeunmapade
Karnaughesigualalnúmerototaldecombinacionesdelasvariablesdeentrada.
•Paratresvariables,elnúmerodeceldasnecesariases2^3=8.Paracuatrovariables,elnúmerodeceldas
es2^4=16celdas.

39. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 39
Mapas de Karnaugh de Tres Variables
Es un conjunto de 8 celdas.
• Se utilizan A, B y C para denominar las variables, aunque se podrían usar otras letras.
• Los valores binarios de A y B se encuentran en la parte izquierda y los valores de C en la parte
superior.
• El valor de una determinada celda es:
–el valor binario de A y B, en la parte izquierda de la misma fila
–combinado con el valor de C en la parte superior de la misma columna.
Representación de un mapa de Karnaugh de tres variables vacío (matriz de 8 celdas) y con los
términos producto estándar representados para cada celda:

40. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 40
Mapas de Karnaugh de Cuatro Variables
• Es un conjunto de 16 celdas.
• Se utilizan A, B, C y D para denominar las variables, aunque se podrían usar otras letras.
• Los valores binarios de A y B se encuentran en la parte izquierda y los valores de C y D en la parte
superior.
• El valor de una determinada celda es:
–el valor binario de A y B, en la parte izquierda de la misma fila
–combinado con el valor de C y D en la parte superior de la misma
Columna.
Representación de un mapa de Karnaugh de cuatro variables vacío (matriz de 16 celdas) y con los
términos producto estándar representados para cada celda:

41. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 41
Adyacencia de Celdas
•LasceldasdeunmapadeKarnaughsedisponendemaneraquesólocambiaunaúnicavariable
entreceldasadyacentes.
•Lasceldasquedifierenenunaúnicavariablesonadyacentes.
•Enelmapade3variables,lacelda010esadyacentealacelda000,ala011yala110.
•Lasceldascuyosvaloresdifierenenmásdeunavariablenosonadyacentes.
•Enelmapade3variables,lacelda010NOesadyacentealacelda001,ala111,ala100niala
101.
•Físicamente,cadaceldaesadyacentealasceldasqueestánsituadasinmediatasaellapor
cualesquieradesuscuatrolados.
•UnaceldaNOesadyacenteaaquellasquetocandiagonalmentealgunadesusesquinas.
•Además,lasceldasdelafilasuperiorsonadyacentesalasdelafilainferiorylasceldas
delacolumnaizquierdasonadyacentesalasceldassituadasenlacolumnaderecha.
•AdyacenciadeceldasenunmapadeKarnaughdecuatrovariables.
•Lasflechasapuntanalasceldasadyacentes.

42. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 42
Simplificación de una Suma de Productos Mediante
el Mapa de Karnaugh
• El proceso que genera una expresión que contiene el menor número posible de términos con el mínimo
número de variables se denomina minimización.
• Después de haber obtenido el mapa de Karnaugh de una suma de productos, se deben seguir tres pasos
para obtener la expresión suma de productos mínima:
–Agrupar los 1s.
–Determinar el término producto correspondiente a cada grupo.
–Sumar los términos productos obtenidos.
Agrupación de 1s
• La finalidad es maximizar el tamaño de los grupos y minimizar el número de estos grupos. Reglas:
1. Un grupo tiene que contener 1, 2, 4, 8 ó 16 celdas.
2. Cada celda de un grupo tiene que ser adyacente a una o más celdas del mismo grupo, pero no todas las
celdas del grupo tienen que ser adyacentes entre sí.
3. Incluir siempre en cada grupo el mayor número posible de 1s de acuerdo con la regla 1.
4. 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.

43. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 43
Agrupación de 1`s

44. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 44
Determinar el Término Producto
Correspondiente a Cada Grupo
1. Cada grupo de celdas que contiene 1s da lugar a un término producto compuesto por todas
las variables que aparecen en el grupo en sólo una forma (no complementada o complementada). Las
variables que aparecen complementadas y sin complementar dentro del mismo grupo se eliminan. A éstas se
las denomina variables contradictorias.
2. Determinar la operación producto mínima para cada grupo.
Determinar la operación producto mínima para un mapa de 3 variables.
I.Ungrupoformadoporunaúnicaceldadalugarauntérminoproductodetresvariables.
II.Ungrupoformadopor2celdasdalugarauntérminoproductodedosvariables.
III.Ungrupoformadopor4celdasdalugarauntérminodeunavariable.
IV.Ungrupoformadopor8celdasindicaquelaexpresiónvale1.
Determinarlaoperaciónproductomínimaparaunmapade4variables.
I.Ungrupoformadoporunaúnicaceldadalugarauntérminoproductodecuatrovariables.
II.Ungrupoformadopor2celdasdalugarauntérminoproductodetresvariables.
III.Ungrupoformadopor4celdasdalugarauntérminoproductodedosvariables.
IV.Ungrupoformadopor8celdasdalugarauntérminodeunavariable.
V.Ungrupoformadopor16celdasindicaquelaexpresiónvale1.

45. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 45
Sumar los términos de productos obtenidos
Cuando se han obtenido todos los términos mínimos, se suman para obtener la expresión suma de
productos mínima.
Ejemplo: Determinar los productos para cada uno de los mapas de Karnaugh y escribir las
correspondientes expresiones suma de productos mínima resultante.
Solución. La expresión suma de productos mínima para cada uno de los mapas de Karnaugh es:

46. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 46
Sumar los términos de productos obtenidos -EJ
Ejemplo: Mediante un mapa de Karnaugh minimizar la expresión suma
de productos siguiente:
Se indica el término producto para cada grupo y la expresión suma de productos mínima resultante
es:
Nota: esta expresión mínima es equivalente a la expresión estándar original.

47. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 47
Obtención Directa del Mapa de Karnaugh
a Partir de la Tabla de Verdad
Los1sdelacolumnadesalidadelatabladeverdadsetrasladandirectamentealmapade
Karnaugh,alasceldascorrespondientesalosvaloresasociadosdelascombinacionesde
variablesdeentrada.

48. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 48
Minimización de un Producto de Sumas
Mediante el Mapa de Karnaugh
•Estemétodoessimilaraldelaminimizacióndeunaexpresiónsumadeproductosmediantelos
mapasdeKarnaugh.
•Enestaocasión,los0srepresentanlasoperacionesdesumaestándarysecolocanen
elmapadeKarnaughenlugardelos1s.
MapadeKarnaughdeunproductodesumasestándar.
•Porcadatérminosumadelaexpresiónproductodesumassecolocaun0enelmapadeKarnaugh
enlaceldacorrespondientealvalordelasuma.
•Lasceldasquenotienen0sonaquellasparalasquelaexpresiónes1.

49. Floyd
Digital Fundamentals, 9/e
Copyright ©2006 by Pearson Education, Inc.
Upper Saddle River, New Jersey 07458
All rights reserved.
Slide 49
Simplificación Mediante el Mapa de Karnaugh
de Expresiones Producto de Sumas
• El proceso de minimización de un producto de sumas es básicamente el mismo que para una
expresión suma de productos, excepto que ahora hay que agrupar los 0s para generar el
mínimo número de términos suma.
• Las reglas para agrupar los 0s son las mismas que para agrupar los 1s.