tema3_clase

8/7/2019 TEMA3_clase

1/65

lgebra de Boole y funciones lgicas 1Electrnica Digital I

Universidad

Rey Juan Carlos

Ingeniera de Telecomunicacin

ElectrElectrnicanica Digital IDigital I

Norberto MalpicaSusana Borromeo

lgebralgebra de Boole yde Boole y funcionesfunciones llgicasgicas

Ingeniera deTelecomunicacin


2/65


1. Introduccin2. Definicin de lgebra de Boole3. Teoremas y propiedades del lgebra de Boole

4. Formas cannicas o normales de las funciones lgicas5. Implementacin de funciones lgicas: puertas lgicas6. Simplificacin de funciones lgicas

ContenidoContenido


3/65


George BooleGeorge Boole

Naci en 1815 en Licolnshire, Inglaterra

Profesor de colegio desde la edad de 16

Filsofo y matemtico

Profesor en el Queens Collegeen Cork, Irlanda


4/65


Claude E. ShannonClaude E. Shannon

Naci en Michigan en 1916

Ingeniero Elctrico y Matemtico (Michigan 36)

Estudios de grado en el M.I.T.

En 1937, su Proyecto Fin de Carrera A

Symbolic Analysis of Relay and SwitchingCircuits se convirti en uno de los trabajosms importantes del siglo

Trabaj en los Bell Labs, donde contribuy endiferentes campos.


5/65


El lgebra de Boole fue creada por el matemtico britnico George Boole(An Investigation of the Laws of Thought, 1854)

Constituye un formalismo matemtico sencillo para representar elconocimiento y realizar clculos.

Inicialmente se plante como un formalismo ms para realizar clculos en

Lgica Proposicional.

En 1939, Claude E. Shannon public su tesis de master (A SymbolicAnalysis of Relay and Switching Circuits), en la que estabeci la relacin

existente entre el lgebra de Boole y el estudio de los circuitos electrnicos.

El lgebra de Boole son las matemticas de los circuitos digitales

IntroducciIntroduccinn


6/65


Elementos del lgebra de Boole: Valores: verdadero (V, 1) y falso (F, 0).

Lgica binaria o bivaluada.

Constantes: valores fijos (0,1).

Variables: elementos cuyo valor puede cambiar.

Se designan por letras (a veces con subndice): A, Bi, xj.

Operaciones en el lgebra de Boole Son reglas de combinacin de elementos que permiten hacer clculos.

Se representan mediante operadores.

Operaciones bsicas: Adicin o unin: A+B, AB

Producto o interseccin: AB, AB

Complementacin o inversin: , A, A, AA



7/65


Expresiones en el lgebra de Boole (formas booleanas, expresiones lgicas oexpresiones de conmutacin): son combinaciones de constantes, variables yoperadores, incluyendo quiz parntesis.

Funciones en el lgebra de Boole (funciones lgicas o funciones deconmutacin): son expresiones sin constantes (salvo que la funcin sea siemprecierta o siempre falsa).

Tablas de verdad: representan los valores adoptados por las funciones lgicasde forma extensiva.

Tienen una columna por cada variable, ms una adicional para el valor de lafuncin.

Tienen una fila por cada posible combinacin de valores de las variables.



8/65


Literal: es una variable suelta, afirmada o negada.

Trmino producto: es una expresin booleana compuesta por un nico literal o porun producto de literales.

Minitrmino (minterm): es un trmino producto que contiene todas las variablesde la funcin, algunas de ellas pueden estar afirmadas y otras negadas.

Trmino suma: es una expresin booleana compuesta por un nico literal o por una

suma de literales. Maxitrmino (maxterm): es un trmino suma que contiene todas las variables dela funcin, algunas de ellas pueden estar afirmadas y otras negadas

Suma de productos (SOP, SdP): es una expresin booleana compuesta por unnico trmino producto o por una suma de trminos producto.

Producto de sumas (POS, PdS): es una expresin booleana compuesta por unnico trmino suma o por un producto de trminos suma.



9/65


Un lgebra de Boole bivaluada es un conjunto B que cumple que:

1. a B , a = 0 a = 1.

2. Todo elemento tiene un complementario (funcin NOT).

NOT: negacin lgica o complementacin.

3. La operacin producto lgico ( , AND) que se define como: AND: producto lgico, interseccin o conjuncin.

4. La operacin suma lgica (+, OR) se define como:

OR: suma lgica, unin o disyuncin.

5. La operacin AND tiene precedencia sobre la OR.

111

001

010

000

f(a,b) = abba

111

101

110

000

f(a,b) = a+bba

01

10

a af(a)=

2. Definici2. Definicin deln del lgebra de Boolelgebra de Boole


10/65


Otras operaciones usuales

XOR o EOR (suma lgica exclusiva o diferencia simtrica)

NOR (suma lgica complementada)

NAND (producto lgico complementado)

XNOR (suma lgica exclusiva complementada o equivalencia).

XOR

011

101

110

000

ba bab)f(a, =NOR

011

001

010

100

ba bab)f(a, +=

011

101

110

100

ba bab)f(a, =

111

001

010

100

ba bab)f(a, =NAND XNOR

Operaciones delOperaciones del lgebra de Boolelgebra de Boole


11/65


Un conjunto B dotado de dos operaciones algebraicas + y es un lgebrade Boole si y slo si se verifican los postulados de Huntington:

1. Las operaciones + y son conmutativas: a+b = b+a ; ab=ba, a,b B.

2. 0 y 1 B tal que: a+0 = 0+a= a ; a1 = 1a = a a B.

3. Cada operacin es distributiva respecto de la otra. Es decir, que a,b B secumple que:

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

a(b+c) = ab+ac

4. a B su complementario a B tal que:

a + a = 1; aa = 0.

Otra definiciOtra definicin formal deln formal del lgebra de Boolelgebra de Boole


12/65


Principio de dualidad: dado un teorema del lgebra de Boole, existe otroteorema que se obtiene sustituyendo:

+ por

por + 0 por 1

1 por 0

El nuevo teorema as obtenido se denomina teorema dual.

Ejemplo:

Si se cumple el siguiente teorema (propiedad conmutativa de la suma)

a+b = b+atambin se cumplir su teorema dual (propiedad conmutativa del producto):

ab = ba

3. Teoremas y propiedades del3. Teoremas y propiedades del lgebra de Boolelgebra de Boole


13/65


(a+b)(a+c)= (a+b)(a+c)(b+c)ab+ac= ab+ac+bcTeoremas del consenso

a(b+c) = ab + aca+(bc) = (a+b) (a+c)Propiedad distributiva

ab = baa+b = b+aPropiedad conmutativa

a(bc) = (ab)c = abca+(b+c) = (a+b)+c = a+b+cPropiedad asociativa

(ab) = a+b(a+b) = abLeyes de De Morgan

a(a+b)=aba+ab=a+b

a(a+b) = aa+ab = aTeoremas de absorcin

(a)=aTeorema de involucin

aa=aa+a=aTeoremas de idempotencia

aa=0a+a=1Teoremas de identidad

0a=01+a=1

1a=a0+a=aElemento neutro

Teoremas y propiedades delTeoremas y propiedades del lgebra de Boolelgebra de Boole


14/65


Ley de De Morgan generalizada: la inversa de una funcin se obtienecomplementando todas las variables que aparecen en ella e intercambiandolos operadores de suma y producto lgicos.

IMPORTANTE: es preciso respetar las precedencias de la expresin

booleana original.

Ejemplo:

[ ] [ ][ ] [ ] dc)a()cb(adcac)(ba

dcac)(badcac)(bad)c,b,(a,fdcac)(bad)c,b,f(a,

++=+++=

=+=+++=

+++=



15/65


Teorema de expansin (de descomposicin de funciones):

Ejemplo:

c,...)]b,f(1,ac,...)]b,f(0,ac,...)b,f(a,

c,...)b,f(1,ac,...)b,f(0,ac,...)b,f(a,

++=

+=

[[

dcac)(ba

a)a(dcac)(badacadac)(ba

]dc1c)(b1[a]dc0c)(b0[a

d)c,b,f(1,ad)c,b,f(0,ad)c,b,f(a,

dcac)(bad)c,b,f(a,

+++=

=++++==++++=

=+++++++=

=+=

+++=



16/65


4. Formas can4. Formas cannicasnicas Todas las expresiones booleanas, independientemente de su forma,pueden convertirse en cualquiera de las dos formas cannicas.

Formas cannicas, formas normales o formas estndares de una funcin

booleana son expresiones booleanas de la funcin que verifican: Primera forma cannica, primera forma normal o forma normaldisyuntiva: es una expresin de una funcin booleana compuesta poruna suma de minitrminos.

Segunda forma cannica, segunda forma normal o forma normalconjuntiva: es una expresin de una funcin booleana compuesta por unproducto de maxitrminos.


17/65


Minitrmino (minterm): trmino producto que contiene todas las variables dela funcin, algunas de las cuales pueden estar afirmadas y otras negadas.

Ejemplo: f(a,b,c)

S son minitrminos:

NO son minitrminos:cbacbacbacbacba

cabacacbba

Maxitrmino (maxterm): trmino suma que contiene todas las variables de lafuncin, algunas de las cuales pueden estar afirmadas y otras negadas.

Ejemplo: f(a,b,c)

S son maxitrminos:

NO son maxitrminos:cbacbacbacbacba ++++++++++

cabacacbba +++++

Formas canFormas cannicasnicas


18/65


Los minitrminos se nombran con subndices (mi),donde i es un nmero obtenido tras pasar a base 10el nmero binario formado al sustituirordenadamente las variables afirmadas por 1 y lasnegadas por 0.

Ejemplo: f(a,b,c), minitrmino

Cada minitrmino est asociado a una fila de latabla de verdad de la funcin lgica correspondiente.

Primera forma cannica, primera forma normal

o forma normal disyuntiva: es una expresin deuna funcin booleana compuesta por una suma deminitrminos.

La expresin en 1FC es nica para cada funcin.

Minitrmino

m151111

m140111

m131011

m120011

m111101

m100101

m91001

m80001

m71110

m60110

m51010

m40010

m31100

m20100

m11000

m00000

midcba

5mcba =

dcba

dcba

dcba

dcba

dcba

dcba

dcba

dcba

dcba

dcba

dcba

dcba

dcba

dcba

dcba

dcba

Primera forma canPrimera forma cannica (1FC)nica (1FC)


19/65


La expresin en 1FC de una funcin booleana es la suma de losminitrminos asociados a las filas que valen 1 en la tabla de verdad.

0

1

0

1

0

1

0

1

c

0

0

0

0

1

1

1

0

a(b+c)

0

0

0

0

1

1

1

1

a

1

1

1

0

1

1

1

0

b+c

0

1

0

1

0

0

0

0

ac

0111

1011

0101

1001

1110

1010

1100

0000

f(i)cba

Ejemplo:

Calculando su tabla de verdad se obtiene lo siguiente:

cac)(bac)b,f(a, ++=

Entonces: =++++=3

64321 6)m(1,2,3,4,mmmmmc)b,f(a,

Primera forma canPrimera forma cannica (1FC)nica (1FC)


20/65


Los maxitrminos se nombran con subndices(Mi), donde i es un nmero obtenido tras pasar abase 10 el nmero binario formado al sustituirordenadamente las variables afirmadas por 0 y lasnegadas por 1.

Ejemplo: f(a,b,c), maxitrmino

Cada maxitrmino est asociado a una fila de latabla de verdad de la funcin lgica correspondiente

Segunda forma cannica, segunda forma

normal o forma normal conjuntiva: es unaexpresin de una funcin booleana compuesta poruna producto de maxitrminos

La expresin en 2FC es nica para cada funcin

Maxitrmino

M151111

M140111

M131011

M120011

M111101

M100101

M91001

M80001

M71110

M60110

M51010

M40010

M31100

M20100

M11000

M00000

Midcba

2Mcba =++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

dcba +++

Segunda forma canSegunda forma cannica (2FC)nica (2FC)


21/65


La expresin en 2FC de una funcin booleana es el producto de losmaxitrminos asociados a las filas que valen 0 en la tabla de verdad.

0111

1011

0101

1001

1110

1010

1100

0000

f(i)cba

75076543210

76543210

mmm1m0m1m0m0m0m0m1m

(7)fm(6)fm(5)fm(4)fm(3)fm(2)fm(1)fm(0)fmc)b,(a,f

++=+++++++=

=+++++++=

Ejemplo: cac)(bac)b,f(a, ++=

Tomando las filas que valen 0,tendremos f(a,b,c):

Negando la expresin anterior obtendremos f(a,b,c) :

===++==3

M(0,5,7)c)b,f(a,750750750 MMMmmmmmmc)b,f(a,c)b,(a,f

Segunda forma canSegunda forma cannica (2FC)nica (2FC)


22/65


En algunos sistemas digitales reales, hay ciertascombinaciones de las variables de entrada que por nopueden producirse nunca.

En estos casos, la salida que pudiera producir el sistema

ante dichas combinaciones de entrada es irrelevante, puestoque nunca se va a dar tal caso.

Las combinaciones imposibles de entrada se denominanindiferencias, valores indiferentes, redundancias o dontcare values, y en la tabla de verdad se representan con elsmbolo X.

Si aparece un smbolo X en una o varias filas de una tabla,nos dara exactamente igual sustituirla por un 1 por un 0.

Ejemplo: funcin que dice si un nmero en BCD es par.

X1111

X0111

X1011

X0011

X1101

X0101

01001

10001

01110

10110

01010

10010

01100

10100

01000

10000

fdcba

+=4

,13,14,15)X(10,11,128)m(0,2,4,6,d)c,b,f(a,

=4

,13,14,15)X(10,11,129)M(1,3,5,7,d)c,b,f(a,

Funciones definidas de forma incompletaFunciones definidas de forma incompleta


23/65


Las formas cannicas se pueden extraer directamente de la tabla de verdad

Primera forma cannica (1FC): suma de minitrminos asociados a las filascon valor 1.

Segunda forma cannica (2FC): producto de maxitrminos asociados a lasfilas con valor 0.

Las formas cannicas son nicas para cada funcin: una funcin tiene unanica expresin en 1FC y una nica expresin en 2FC.

La 1FC y la 2FC de una funcin son equivalentes.

= 4 8,9,12,13)M(1,2,6,7,d)c,b,f(a,

=4

5)10,11,14,1m(0,3,4,5,d)c,b,f(a,

Formas CanFormas Cannicas: resumennicas: resumen


24/65


Conversin de suma de productos a la 1FC:Aplicar la propiedad A+ A=1 : Cada trmino producto no standar semultiplica por un trmino formado por suma de la variable que falta y sucomplemento

Ejemplo: DCABBACBADCBAf ++=),,,(

)()()(

)(

DDCBADDCBACCBABA

DCBACDBADDCBAABC

+++=+=

+=+=

DCABDCBADCBADCBACDBADCBACDBADCBAf ++++++=),,,( Conversin producto de sumas a la 2FC:

Aplicar la propiedad AA=0 : Se aade a cada trmino suma no standar untrmino producto formado por la variable que falta y su complemento

Ejemplo: )()()(),,,( DCBABACBADCBAf ++++++=

DDCBADDCBACCBABA

DCBADCBADDCBACBA

+++++++=++=+

++++++=+++=++

)()()(

)()()(

Formas CanFormas Cannicas: resumennicas: resumen


25/65


Puertas lgicas: dispositivos electrnicos capaces de implementaroperadores lgicos

Para cada operacin lgica (AND, OR, NOT, XOR, NAND, NOR, XNOR)existe la correspondiente puerta lgica que la materializa.

Un circuito lgico se construye a partir de una expresin algebraica de la

funcin lgica que queremos implementar, interconectando puertas lgicasbsicas de acuerdo con dicha expresin.

Una funcin dada puede representarse mediante mltiples expresiones algebraicasequivalentes.

Una funcin dada puede materializarse con diferentes circuitos. Mientras ms sencilla sea la expresin lgica utilizada, ms sencillo ser el circuitoque materialice la funcin buscada.

5. Implementaci5. Implementacin de funciones ln de funciones lgicas: Puertas Lgicas: Puertas Lgicasgicas


26/65


Puertas LPuertas Lgicasgicas

La funcin lgica implementada por una puerta lgica depende de lainterpretacin (convenio) utilizada.

Los nombres dados a las puertas lgicas bsicas coinciden con la funcinlgica que realizan interpretando los valores de sus entradas y salidas

mediante el convenio de lgica positiva.

Estudiaremos las siguientes puertas lgicas bsicas:

Puerta INVERSOR (NOT)

Puerta AND Puerta OR

Puerta NAND

Puerta NOR Puerta XOR

Puerta XNOR

Puertas bsicas

Puertas universales


27/65


Puertas LPuertas Lgicas: INVERSORgicas: INVERSOR

Realiza la operacin lgica de INVERSIN o COMPLEMENTACIN:cambia un nivel lgico al nivel opuesto.

Expresin lgica:

Tabla de verdad:

AS =

01

10

SA

Ejemplo de aplicacin: circuito que genera el complemento a 1 de un nbinario

ANSI/IEEE 91-1984

1

1

Circuito comercial: 74x04


28/65


Puertas LPuertas Lgicas: ANDgicas: AND

Realiza la operacin lgica de MULTIPLICACIN LGICA Expresin lgica:

Tabla de verdad:

BAS =

1

1

0

0

A

00

01

11

00

SB

Ejemplo de aplicacin: La puerta AND como un dispositivo dehabilitacin / desabilitacin


ANSI/IEEE 91-1984


29/65


Puertas LPuertas Lgicas: ORgicas: OR

Realiza la operacin lgica de SUMA LGICA Expresin lgica:

Tabla de verdad:

BAS +=

1

1

0

0

A

00

11

11

10

SB

Ejemplo de aplicacin: La puerta OR como un dispositivo dehabilitacin / desabilitacin

ANSI/IEEE 91-1984



30/65


Puertas LPuertas Lgicas: NANDgicas: NAND

Realiza la operacin lgica de NOT-AND : una funcin AND con salidacomplementada

Expresin lgica:

Tabla de verdad:

BAS =

1

10

0

A

10

11

01

10

SB


ANSI/IEEE 91-1984

Puerta universal: las puertas NAND pueden generar cualquiera de laspuertas bsicas NOT, AND, OR.


31/65


Puertas LPuertas Lgicas: NORgicas: NOR

Realiza la operacin lgica de NOT-OR : una funcin OR con salidacomplementada.

Expresin lgica:

Tabla de verdad:

BAS +=

1

10

0

A

10

01

01

00

SB

ANSI/IEEE 91-1984


Puerta universal: las puertas NOR pueden generar cualquiera de laspuertas bsicas NOT, AND, OR.


32/65


Puertas LPuertas Lgicas: ORgicas: OR-- EXCLUSIVA (XOR)EXCLUSIVA (XOR)

La salida de una puerta OR-exclusiva se pone a nivel alto slo cuando hayun n impar de entradas a nivel alto. En el caso particular de una puerta condos entradas, la salida estar a nivel ALTO cuando las entradas tenganniveles lgicos opuestos.

Expresin lgica: Tabla de verdad:

BAS =

1

1

0

0

A

00

11

01

10

SB

ANSI/IEEE 91-1984


Aplicaciones: comparador, detectores de paridad, sumador

=


33/65


Puertas LPuertas Lgicas: NORgicas: NOR-- EXCLUSIVA (XNOR)EXCLUSIVA (XNOR)

Funcin OR-exclusiva con la salida complementada

Expresin lgica:

Tabla de verdad:

BAS =

1

1

0

0

A

10

01

11

00

SB

ANSI/IEEE 91-1984

Circuito comercial: MC10EL07

Aplicaciones: comparador, detectores de paridad, sumador

=


34/65


Equivalencia entre puertas lEquivalencia entre puertas lgicasgicas

Aplicacin de las leyes De Morgan a las puertas lgicas:

BABA

BABA

+=

=+


35/65


AnAnlisis de circuitoslisis de circuitos combinacionalescombinacionales

X

Y

Z

F

00001111

00110011

01010101

l f d f l6 Si lifi i d f i l i


36/65


Dado que existen mltiples circuitos para implementar una funcin lgicadada, lo mejor es utilizar el circuito ms adecuado para cada situacin.

Criterios posibles para manipular las expresiones lgicas:

Obtener el circuito ms barato reduciendo el nmero de trminos. Obtener el circuito ms rpido.

Obtener el circuito formado por menos circuitos integrados de un tipo dado.

Obtener un circuito sin valores transitorios no deseados (azares, glitches).

Simplificacin: proceso que conduce a reducir el nmero de literales ytrminos de una funcin lgica.

Existen mtodos de simplificacin automticos para ser implementados encomputadores (Quine-McCluskey es el ms conocido).

Se puede simplificar funciones mediante manipulaciones algebraicas (manual,costoso).

Mtodos grficos: Veitch-Karnaugh (manual, sencillo para pocas variables).

6. Simplificaciones de funciones l6. Simplificaciones de funciones lgicasgicas

MM d dt d d V i hV it h K hK h


37/65


Inventado por Veitch a principios de los aos 50, y perfeccionado porKarnaugh.

Se basa en construir unos diagramas adecuados para simplificargrficamente.

Diagrama (mapa, tabla) de Veitch-Karnaugh para una funcin de nvariables:tabla rectangular de 2nceldas, cada una de las cuales est asociada a unacombinacin de variables (y a una fila de la tabla de verdad).

En cada casilla hay un 1 un 0, dependiendo de la fila de la tabla de verdad

asociada.Propiedad principal: cada casilla es adyacente a todas sus vecinas enhorizontal y vertical, es decir, entre una casilla y su vecina slo difiere el valor deuna variable.

Slo son utilizables en la prctica los mapas para funciones de 2, 3, 4, 5 y 6variables.

MMtodo detodo de VeitchVeitch--KarnaughKarnaugh

MMt d dt d d V it hV it h K hK h 2 i bl2 i bl


38/65


El mapa tiene 4 casillas, cada una asociada a una combinacin de los valoresde las variables.

Cada casilla tiene 2 vecinas.

En cada casilla se ha aadido el n de la fila de la tabla de verdad asociada adicha casilla, as como la combinacin de variables que la corresponde.

f(3)f(2)1

f(1)f(0)0

10

ba

ba ba

ba a

b

0 1

2 3

Vecindades:

Casilla 0: 1 y 2.

Casilla 1: 0 y 3.

Casilla 2: 0 y 3.

Casilla 3: 1 y 2.

MMtodo detodo de VeitchVeitch--KarnaughKarnaugh: 2 variables: 2 variables

MMt d dt d d V it hV it h K hK h 2 i bl2 i bl


39/65


Ejemplo:

111

101

010

100f(i)ba

111

010

10ab

0 1

2 3

Tabla de verdad Funcin: f(a,b)=m0+m2+m3=M1

Mapa de V-K:


MMt d dtodo de V it hVeitch K hKarnaugh 3 i bl: 3 variables


40/65


El mapa tiene 8 casillas, y cada casilla tiene 3 vecinas.

f(7)

f(3)

11

f(5)

f(1)

01

f(6)

f(2)

10

f(4)1

f(0)0

00

cba cba abc

0 1 3 2

4 5 7 6

cba cba

cba cba cba cba

Vecindades:

Casilla 0: 1, 2 y 4.



Casilla 3: 1, 2 y 7. Casilla 4: 0, 5 y 6.





MMtodo detodo de VeitchVeitch KarnaughKarnaugh: 3 variables: 3 variables


41/65


Ejemplo:

0

1

11

0

1

01

1

1

10

11

00

00a

bc

0 1 3 2

4 5 7 6

Tabla de verdad Funcin: f(a,b)=m1+m2+m3 +m4 +m6=M0+M5+M7

Mapa de V-K:

0111

1011

0101

1001

1110

1010

1100

0000

f(i)cba




42/65


El mapa tiene 16 casillas, y cada una tiene 4 vecinas.

f(14)f(15)f(13)f(12)11

f(6)f(7)f(5)f(4)01

f(10)f(11)f(9)f(8)10

f(3)

11

f(1)

01

f(2)

10

f(0)00

00

dcba dcba ab

cd

0 1 3 2

4 5 7 6

dcba dcba

12 13 15 14

8 9 11 10

dcba dcba dcba dcba

dcba dcba dcba dcba

dcba dcba dcba dcba

Vecindades: Casilla 0: 1, 2, 4 y 8. Casilla 1: 0, 3, 5 y 9. Casilla 2: 0, 3, 6 y 10.

Casilla 3: 1, 2, 7 y 11. Casilla 4: 0, 5, 6 y 12. Casilla 5: 1, 4, 7 y 13. Casilla 6: 2, 4, 7 y 14.

Casilla 7: 2, 4, 7 y 15. Casilla 8: 0, 9, 10 y 12. Casilla 9: 1, 8, 11 y 13. Casilla 10: 2, 8, 11 y 14.

Casilla 11: 3, 9, 10 y 15. Casilla 12: 4, 8, 13 y 14. Casilla 13: 5, 9, 12 y 15. Casilla 14: 6, 10, 12 y 15. Casilla 15: 7, 11, 13 y 14.




43/65


Funcin:

11111

10111

01011

00011

11101

10101

01001

00001

01110

00110

11010

10010

11100

00100

01000

10000

fdcba

110011

001101

110010

1

11

0

01

0

10

100

00abcd

0 1 3 2

4 5 7 6

12 13 15 14

8 9 11 10

==44

8,9,12,13)M(1,2,6,7,5)10,11,14,1m(0,3,4,5,d)c,b,f(a,


MMtodo detodo de VeitchVeitch-KarnaughKarnaugh: 5 variables: 5 variables


44/65


Tiene 32 casillas, y se construye con 2 mapas superpuestos de 4 variables. Cada casilla tiene 5 vecinas: 4 en su plano ms la de su misma posicin en elotro plano (la casilla 0 es vecina de la 16, la 1 de la 17, etc).

f(14)f(15)f(13)f(12)11

f(6)f(7)f(5)f(4)01

f(10)f(11)f(9)f(8)10

f(3)

11

f(1)

01

f(2)

10

f(0)00

00bc

de

f(30)f(31)f(29)f(28)11

f(22)f(23)f(21)f(20)01

f(26)f(27)f(25)f(24)10

f(19)

11

f(17)

01

f(18)

10

f(16)00

00bc

de

0a = 1a =




45/65


Tiene 64 casillas, y se construye con 4 mapas superpuestos de 4 variables.

Cada casilla tiene 6 vecinas: las 4 de su plano, ms las 2 que estn en su mismaposicin pero en planos adyacentes.

f(14)f(15)f(13)f(12)11

f(6)f(7)f(5)f(4)01

f(10)f(11)f(9)f(8)10

f(3)

11

f(1)

01

f(2)

10

f(0)00

00cd

0b0a ==

ef

f(46)f(47)f(45)f(44)11

f(38)f(39)f(37)f(36)01

f(42)f(43)f(41)f(40)10

f(35)

11

f(33)

01

f(34)

10

f(32)00

00cd

0b1a ==

ef

f(30)f(31)f(29)f(28)11

f(22)f(23)f(21)f(20)01

f(26)f(27)f(25)f(24)10

f(19)

11

f(17)

01

f(18)

10

f(16)00

00cd

1b0a ==

ef

f(62)f(63)f(61)f(60)11

f(54)f(55)f(53)f(52)01

f(58)f(59)f(57)f(56)10

f(51)

11

f(49)

01

f(50)

10

f(48)00

00cd

1b1a ==

ef

Planos adyacentes:

El plano 00 es adyacente a

los planos 01 y 10. El plano 01 es adyacente alos planos 00 y 11. El plano 11 es adyacente alos planos 01 y 10. El plano 10 es adyacente alos planos 11 y 00.

Algunas vecindades:

Casilla 0:1,2,4,8,16,32. Casilla 16:17,18,20,24,0,48. Casilla 55:51,53,54,63,23,39. Casilla 41:40,43,33,45,57,9. Etc.


SimplificaciSimplificacin por Vn por V--K conK con minitminitrminosrminos


46/65


La propiedad que permite simplificar grficamente consiste en que entre cadados casillas vecinas (que comparten un lado, en horizontal o en vertical) slodifiere el valor de una variable si dos casillas vecinas contienen un 1,agrupndolas se puede aplicar la propiedad distributiva para simplificar laexpresin algebraica resultante eliminando la variable que cambia.

Ejemplo: f(a,b)=m1+m2 +m3 +m4 +m6

0

1

11

0

1

01

1

1

10

11

00

00abc

0 1 3 2

4 5 7 6

cab)b(ca

cbacbamm 31

=+=

=+=+

Agrupando m1 con m3

cba)a(cb

cbacbamm 6

=+=

=+=+2

Agrupando m2 con m6

cacbcac)b,f(a, ++=Por tanto:

cab)b(ca

cbacbamm 6

=+=

=+=+4

Agrupando m4

con m6

SimplificaciSimplificacin por Vn por V-K conK con minitminitrminosrminos



47/65


Simplificacin:

Agrupacin de 1s pertenecientes a celdas adyacentes. El objetivo esmaximizar el tamao de los grupos y minimizar el n de grupos.

Un grupo puede contener 1, 2, 4, 8, 16 celdas (potencias de 2)

Cada celda de un grupo tiene que ser adyacente a una o ms celdas delmismo grupo, pero no todas las celdas del grupo tiene que ser adyacentesentre s.

Cada 1 del mapa debe estar incluido en al menos en un grupo.

Determinacin de la operacin producto mnima para cada grupo. Dentrode cada grupo, para obtener la expresin se eliminan las variables que cambian.

Cuando se han obtenido todos los trminos mnimos se suman para obtenerla expresin suma de productos mnima.

Implementacin

Una posible implementacin se realiza con puertas NAND, una por cadatrmino producto y otra por la suma.

SimplificaciSimplificacin por Vn por V K conK con minitminitrminosrminos



48/65


Si cuatro casillas vecinas dos a dos formando una lnea o un rectngulocontienen todas el valor 1, aplicando la propiedad distributiva eliminamos lasdos variables que cambian.

Ejemplo: f(a,b)= m0

+ m1

+m2

+m3

+m6

+m7

1

1

11

0

1

01

1

1

10

01

10

00abc

0 1 3 2

4 5 7 6

[ ] ac)c(bc)c(bacbacbacbacba

mmmm 3210

=+++=

=+++=

=+++Agrupando m0, m1, m2 y m3

Agrupando m6, m7, m2 y m3

bac)b,f(a, +=

Por tanto:[ ] bc)c(ac)c(ab

cbacbacbacba

mmmm 3276

=+++=

=+++=

=+++




49/65


110011

111101

110010

1

11

1

01

1

10

100

00ab

cd

Si ocho casillas vecinas dos a dos formando un rectngulo contienen todasel valor 1, aplicando la propiedad distributiva eliminamos las tres variablesque cambian.

Ejemplo: f(a,b)= m0

+ m1

+m2

+m3

+m4

+m5

+m6

+m7

+m10

+m11

+m14

+m15

( ) ( )[ ] ad)d(cd)d(cbd)d(cd)d(cba dcbadcbadcbadcba

dcbadcbadcbadcba

mmmmmmmm 76543210

==+++++++=

=++++

++++=

=+++++++

...

Agrupando m0, m1, m2, m3, m4, m5, m6 y m7

cac)b,f(a, +=Por tanto:

( ) ( )[ ] cd)d(bd)d(bad)d(bd)d(bacdcbadcbadcbadcbadcbadcbadcbadcba

mmmmmmmm 151411107632

==+++++++=

=++++++++=

=+++++++

...

Agrupando m10, m11, m2, m3, m14, m15, m6 y m7




50/65


Subcubo: agrupacin de 2rcasillas vecinas dos a dos con el mismo valor queforman una lnea, un rectngulo o un paraleleppedo.

El subcubo est compuesto por un nmero de casillas (r) que es potenciade 2 (1 casilla, 2 casillas, 4 casillas, 8 casillas, 16 casillas, etc).

Las casillas que componen el subcubo deben ser vecinas 2 a 2, y ademsestarn alineadas o formarn un rectngulo o un paraleleppedo.

Todas las casillas del subcubo tendrn el mismo valor (algunas puedentener el valor X si sirven para que el subcubo sea ms grande).

En un mapa de V-K de nvariables, un subcubo de 2rcasillas se simplifica as:Las rvariables que cambian se eliminan.El producto de las n-rvariables restantes, que no cambian, constituyen laexpresin simplificada del subcubo.

En un subcubo de 1 casilla no se elimina ninguna variable.En un subcubo de 2 casillas se elimina 1 variable.En un subcubo de 4 casillas se eliminan 2 variables.En un subcubo de 8 casillas se eliminan 3 variables.




51/65


Procedimiento

1. Formar subcubos de 1 con las casillas sueltas (las que no se pueden agruparcon otras).

2. Formar subcubos de 2 con las casillas que slo pueden formar subcubos de 2.

3. Formar subcubos de 4 con las casillas que queden y que puedan formar

subcubos de 4 y no de 8.4. Repetir 3 formando grupos de 8, 16, etc.

5. El proceso termina cuando todas las casillas a 1 estn cogidas en algnsubcubo. De cada subcubo sale un trmino de la expresin simplificada.

Para simplificar la funcin tenemos que incluir todas las casillas con valor 1 (

X) en algn subcubo.

El resultado final del proceso de simplificacin de la funcin es una suma deproductos (SOP, SdP) que depende de cmo escojamos los subcubos.

Se obtiene una funcin ms sencilla cogiendo el mnimo nmero de gruposposibles, y lo ms grandes posibles.


SimplificaciSimplificacin por Vn por V--K conK con maxitmaxitrminosrminos


52/65


Se realiza de forma parecida a como se hace con los minitrminos, con las

siguientes diferencias:

Los subcubos estn formados por casillas con valor 0 X (en losminitrminos se cogan las casillas con 1 X).

Al escribir el trmino simplificado, la complementacin de las variables esla contraria.

Las variables que iran complementadas en minitrminos van sin

complementar en maxitrminos y las variables que iran sin complementar enminitrminos van complementadas en maxitrminos.

El trmino resultante de cada subcubo de casillas a 0 es una suma deliterales (en minitrminos era un producto de literales).

La funcin simplificada resultante es un producto de sumas (POS, PdS)(en minitrminos era una suma de productos).

Implementacin: puertas NOR

Simplificacip n por Vp K con maxitrminos

SimplificaciSimplificacin por Vn por V--KK


53/65


Ejemplo: simplificar por minitrminos y por maxitrminos la funcin f(a,b,c,d)cuya tabla de verdad se indica a continuacin.

11111

00111

01011

10011

01101

10101

01001

10001

01110

10110

X1010

00010

01100

10100

01000

X0000

fdcba

Construimos el mapa de V-K:

010111

10X001

100110

0

11

0

01

1

10

X00

00ab

cd

Paso 1: tomar los 1 que no puedan formar subcubos con otrascasillas

pp pp



54/65


Paso 1: tomar los 1 que no puedan formar subcubos con otras casillas.

010111

10X001

100110

0

11

0

01

1

10

X00

00ab

cd

dcbaS1 =

Paso 2: tomar los 1 que slo puedan formar subcubos de 2 casillas

pp pp



55/65


Paso 2: tomar los 1 que slo puedan formar subcubos de 2 casillas.

010111

10X001

100110

0

11

0

01

1

10

X00

00ab

cd

dcbaS1 =

dcaS2 =

Repetir paso 2?

pp pp



56/65


Paso 2: tomar los 1 que slo puedan formar subcubos de 2 casillas.

010111

10X001

100110

0

11

0

01

1

10

X00

00ab

cd

dcbaS1 =

dcaS2 =

dcaS3 =

Paso 3: tomar los 1 que no estn tomados y puedan formar subcubos de 4 y no de 8

p p



57/65


Paso 3: tomar los 1 que no estn tomados y puedan formar subcubos de 4 y no de8.

010111

10X001

100110

0

11

0

01

1

10

X00

00ab

cd

dcbaS1 =

dcaS2 =

dcaS3 =

dbS4=

Paso 4: no ha lugar porque todos los 1 ya estn cogidos en algn subcubo.

dbdcadcadcbad)c,b,(a,f1 +++=



58/65


Ejemplo: simplificar por minitrminos y por maxitrminos la funcin f(a,b,c,d) cuyatabla de verdad se indica a continuacin.

11111

00111

01011

10011

01101

10101

01001

10001

01110

10110

X1010

00010

01100

10100

01000

X0000

fdcba

Construimos el mapa de V-K:

010111

10X001

100110

0

11

0

01

1

10

X00

00abcd

Paso 1: tomar los 0 que no puedan formar subcubos con otrascasillas



59/65


Paso 1: tomar los 0 que no puedan formar subcubos con otras casillas.

010111

10X001

100110

0

11

0

01

1

10

X00

00

ab

cd

dcbaS1 +++=

Paso 2: tomar los 0 que slo puedan formar subcubos de 2 casillas



60/65


Paso 2: tomar los 0 que slo puedan formar subcubos de 2 casillas NO HAYNINGUNO.

010111

10X001

100110

0

11

0

01

1

10

X00

00

ab

cd

dcbaS1 +++=

Paso 3: tomar los 0 que no estn tomados y puedan formar subcubos de 4 yno de 8



61/65



010111

10X001

100110

0

11

0

01

1

10

X00

00ab

cd

dcbaS1 +++=

dbS2 +=

Repetir paso 3?

SimplificaciSimplificacin por Vn por V--K:K: maxitmaxitrminosrminos


62/65



010111

10X001

100110

0

11

0

01

1

10

X00

00ab

cd

dcbaS1 +++=

dbS2 +=

daS3 +=

Repetir paso 3?



63/65



010111

10X001

100110

0

11

0

01

1

10

X00

00ab

cd

dcbaS1 +++=

dbS2 +=

daS3 +=

caS4 +=

Repetir paso 3?



64/65



010111

10X001

100110

0

11

0

01

1

10

X00

00ab

cd

dcbaS1 +++=

dbS2 +=

daS3 +=

caS4 +=

dcS5 +=

Paso 4: no ha lugar porque todos los 0 ya estn cogidos en algn subcubo.

)d(cc)(a)d(a)d(bd)cba(d)c,b,(a,f2 +++++++=

AplicaciAplicacin a los sistemas digitalesn a los sistemas digitales


65/65


Displaysde 7 segmentos

DecodificadorBCD4 7

a

f b

ce d

g

nodo comn:nivel bajode tensin activa elsegmento

Ctodo comn:nivel alto

de tensin activa elsegmento

a,b,c,d,f,g9

a,b,c,d,e,f,g8

a,b,c7

a,c,d,e,f,g6

a,c,d,f,g5

b,c,f,g4

a,b,d,e,g3

a,b,d,e,g2

b,c1

a,b,c,d,e,f0

SegmentosDgito

tema3_clase

Documents