Primer taller arquitectura de computadores

Repaso de compuertas lógicas y sus tablas de verdad

Tablas de verdad Compuertas lógicas

1. Dado el siguiente circuito lógico, halle la función (Fo) booleana

Fo = ________ + __________

Fo =
 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad
1.1 Con la anterior información llene la siguiente tabla de verdad:

x y z Fo x y z Fo
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 1 0 1 1 0
1 1 1 1 1 1

Postulado 2 a) x + 0 = x b) x . 1 = x
Postulado 5 a) x + x’ = 1 b) x . x’ = 0
Teorema 1 a) x + x = x b) x . x = x
Teorema 2 a) x + 1 = 1 b) x . 0 = 0
Teorema 3 involución (x’)’ = x
Teorema 3 conmutativo a) x + y = y + x b) xy = yx
Teorema 4 asociativo a) x + (y + z) = (x + y) +z b) x (yz) = (xy) z
Postulado 4 distributivo a) x (y + z) = xy +xz b) x + yz = (x + y)(x+z)
Teorema 5 morgan a) ( x + y)’ = x’ y’ b) (xy) = x’ + y’
Teorema 6 absorción a) x + xy = x b) x (x + y) = x
Teorema x+yz = (x+y)(x+z)

2. Simplificar las siguientes expresiones

xy+x´z+yz =
x(x´+y) =
x+x´y =
x´+y´z+x´z+y =
 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad

3. Conceptos mapas de karnaugh

Es la representación gráfica de una función booleana más utilizada en sistemas digitales.

Existe una relación uno a uno entre un mapa y una tabla de verdad. Una tabla tiene un renglón por
cada mintérmino; y un mapa, como se verá, tiene un casillero o cuadro para cada mintérmino. El
mapa también puede ser considerado una extensión de los diagramas de Venn. Consideremos un
diagrama de Venn para dos variables A y B:

A B

AB’ AB A’B

A’B’

Si el orden de la variable para la asignación del código de min términos es AB, se puede rotular el
diagrama con el número decimal asociado al min término, queda:

A B
2 3 1

Puede observarse que resultan áreas desiguales para cada mintérmino; y que el gráfico refleja las
adyacencias entre min términos, pero no tan claramente como un 2-cubo, el cual se muestra en la
figura siguiente:
0 A
2

1 3
B
C
 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad

En un mapa de Karnaugh se adopta un área igual, de forma cuadrada, para cada mintérmino; y
además, estos cuadrados se disponen de tal forma que reflejen las adyacencias. Se ha superpuesto
el 2-cubo, con un mapa de dos variables.
A
B 0 1
0 2 A
0

1 1 3

B f(A,B)
C
La identificación de los cuadros con el número del mintérmino, depende de la elección del orden de
las variables que se haya elegido para la representación decimal equivalente. Por ejemplo, para dos
variables A y B:

B B
A 0 1 A 0 1
0 1 0 2
0 0

2 3 1 3
1 1

f(A,B) f(B,A)

La representación de funciones mediante mapas, se logra marcando los mintérminos presentes con
un "1"; los ceros suelen omitirse.

Por ejemplo, las funciones AND y OR , de dos variables, se representan en mapas según:

B B
A 0 1 A 0 1
0 1 0 1
0 0 0 0 1
2 3 2 3
1 0 1 1 1 1
Nótese que f1=m3 ; y que f2=m1+m2+m3.

f1(A,B)=AB f2(A,B)=A + B
 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad
Mapa para tres variables.
Para tres variables A, B y C, se ilustran los mintérminos en un diagrama de Venn y en un 3-cubo:

B
A B 2 6
4 6 2
0 A
7 4
5 3
3
7
1 0 1 5
C
C

La siguiente figura muestra un desarrollo de un 3-cubo. Nótese que al abrir las caras del cubo, los
mintérminos que están a distancia uno, quedan adyacentes(exceptuando los de la cara que no se
representa en el plano). Los códigos de los mintérminos quedan ordenados según código Gray. El 3-
cubo muestra también la propiedad del código Gray de ser reflejado.

B B=1
A=0
2 A=1
6
4 2 6
0 A 0
C=0 4
3
7
1 3 7
5 C=1 5
1
C
f(A, B, C)
f(A, B, C)

El siguiente diagrama muestra el desarrollo de un 3-cubo sobre el mapa de Karnaugh de tres

variables:
AB
C 00 01 11 10
0 2 6 4
0

1
1 3 7 5

f(A, B, C)
 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad
Nótese que m0 es adyacente a m1, m2 y m4. Entonces, en un mapa de Karnaugh se considera que
los bordes son coincidentes, lo cual también refleja que la propiedad del código Gray de ser cíclico.
Es decir, un cilindro en este caso, y se suele mostrar el desarrollo en el plano.

El mapa para tres variables puede obtenerse con dos mapas de dos variables.
Resulta práctico colocar en un borde de cada cuadrado el número del mintérmino. De esta forma,
resulta cómodo expresar una forma canónica en un mapa.

5.2. Formas de Mapas

A continuación se ilustran mapas, para 3, 4 y 5 variables. Los valores de columnas y renglones se
ordenan empleando código Gray, para reflejar mejor las adyacencias. El orden de las variables, para
la representación decimal equivalente del mintérmino, figura en la base del mapa.

AB
CD 00 01 11 10
0 4 12 8
AB 00
C 00 01 11 10
0 2 6 4 1 5 13 9
0 01
1 3 7 5 3 7 15 11
1 11
2 6 14 10
f(A, B, C) 10

f(A, B, C, D)
Nótese que el mapa de 5 variables se obtiene a partir de dos mapas para n = 4. A uno se le antecede
un cero en la codificación de las columnas y al otro un 1.
 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad
ABC
DE 000 001 011 010 110 111 101 100
0 4 12 8 24 28 20 16
00

1 5 13 9 25 29 21 17
01
3 7 15 11 27 31 23 19
11

2 6 14 10 26 30 22 18
10

f(A, B, C, D, E)

Sin embargo esta forma de generar mapas, no refleja bien las adyacencias. Otra forma es una
representación en el espacio:

A=1 100 101 111 110

16 20 28 24

A=0
17 21 29 25

19 23 31 27
ABC
DE 000 001 011 010 18 22 30 26
0 4 12 8
00
1 5 13 9
01 f(A, B, C, D, E)

3 7 15 11
11
2 6 14 10
10
 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad

Mapas para 6 o más variables son difíciles de manejar.

5.3.- Manejo de Mapas

Los siguientes conceptos son útiles en la manipulación de mapas:

 Un mapa de n variables tiene 2n cuadros.

 Cada bloque o casillero de un mapa de n variables, tiene n bloques adyacentes; es decir, los
códigos binarios de los mintérminos están a distancia uno.

 Un bloque está asociado a un producto que contiene las n variables, pudiendo éstas estar o no
complementadas.

 Agrupando dos bloques adyacentes, se logra una expresión tipo producto de (n-1) variables.
Esto empleando: .
a  ab  ab
Esto, considerando que dos bloques adyacentes difieren en sólo una variable, ya que están a
distancia 1. Los bloques pueden agruparse en un número que es una potencia de dos; es decir:
2, 4, 8, 16...

 Agrupando 2k bloques, que forman un k-cubo, la expresión booleana asociada es la que resulta
de eliminar k variables de las n correspondientes a un mintérmino.

Ejemplo: Los siguientes mapas ilustran el concepto de agrupaciones.

AB AB
CD 00 01 11 10 CD 00 01 11 10
0 4 12 8 0 4 12 8
00 0 0 1 1 00 0 0 1 0
1 5 13 9 1 5 13 9
01 0 0 1 1 01 0 0 1 0

3 7 15 11 3 7 15 11
11 0 0 1 1 11 0 0 1 0
2 6 14 10 2 6 14 10
10 0 0 1 1 10 0 0 1 0

f(A, B, C, D)=A f(A, B, C, D)=AB

 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad

AB AB
CD 00 01 11 10 CD 00 01 11 10
0 4 12 8 0 4 12 8
00 0 0 0 0 00 0 0 0 0

1 5 13 9 1 5 13 9
01 0 0 0 0 01 0 0 0 0

3 7 15 11 3 7 15 11
11 0 0 1 0 11 0 0 1 0

2 6 14 10 2 6 14 10
10 0 0 1 0 10 0 0 0 0

f(A, B, C, D)=ABC f(A, B, C, D)=ABCD

Para n = 4:

 Un mintérmino se expresa como un producto de 4 variables.

 Una agrupación de 2 mintérminos, que forman un 1-cubo (o que son adyacentes), puede
expresarse en tres variables.

 Una agrupación de 4 mintérminos, que forman un 2-cubo, se expresa en dos variables.

 Una agrupación de 23 mintérminos (que forman un 3-cubo), reduce en 3 las variables; es decir,
esta agrupación puede expresarse como una variable.

 Una agrupación de los 24 mintérminos (forman un 4-cubo), puede expresarse como 1. Es decir,
en 0 variables.

 Nótese que bajo el mapa suele escribirse la función que éste representa.

Además, la lectura de la expresión asociada a un grupo, se efectúa por la intersección de las

zonas donde cada variable toma valores iguales a uno.

 El número de grupos de un literal, en caso de n variables, es:

n 1 n!
  2  2  2n
1 1!(n  1)!
 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad

En el ejemplo anterior, se tienen 8 grupos:

A, B, C, D, A, B , C , D
 Los grupos de 2 literales, en caso de n variables, está dado por: 2n ( n-1).

En el ejemplo anterior, con n=4, se tienen 24 grupos:

AB, A'B, AB', A'B'

n AC, A'C, AC', A'C'
k
AD, A'D, AD', A'D'

BC, B'C, BC', B'C'

2k

 Los grupos de k literales, cuando se tienen n variables, quedan dados por:

n!
2k
k!(n  k )!
Con k  n
 Cuando k es igual a n, se logra el número de mintérminos.
 Debido al alto número de subcubos, es importante ejercitarse en ubicarlos en el mapa. Los
menos obvios son aquellos que se encuentran en los bordes.

Ejemplos de estos casos, para n=4:

b d , cb , b d a , ba d
Uso de mapas

 La obtención del mapa, a partir de una forma canónica es asunto trivial, si los casilleros han sido
rotulados con los números decimales de los mintérminos.

Ejemplo: obtener el mapa de f(A, B, C) =  m(1, 2, 5)

AB
Se tiene:
C 00 01 11 10
0 2 6 4
0 1

1 3 7 5
1 1 1
 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad

 La obtención del mapa, a partir de una forma “suma de productos” puede obtenerse empleando
los conceptos desarrollados en manejo de mapas.
Ejemplo. Obtener el mapa de la siguiente función:

f(A, B, C)  AC  BC  ABC

Un min término tiene 3 literales; una agrupación de dos min términos tiene una expresión
dependiente de dos variables.

Para aclarar el método, se dibujará un mapa para cada producto. Con un poco de experiencia,
todos los productos pueden dibujarse en el mismo mapa.

AB AB
C 00 01 11 10 C 00 01 11 10
0 2 6 4 0 2 6 4
0 0 1 1
1 3 7 5 1 3 7 5
1 1 1 1

f(A, B, C)=A'C f(A, B, C)=BC'

Y para A'BC: Finalmente:

AB AB
C 00 01 11 10 C 00 01 11 10
0 2 6 4 0 2 6 4
0 0 1 1

1 3 7 5 1 3 7 5
1 1 1 1 1

f(A, B, C)=A'BC f(A, B, C)=A'C+BC'+A'BC

 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad

El mapa anterior permite escribir la forma canónica:

f ( A, B, C )   m(1,2,3,6)
Nótese que el producto A'BC está incluido en A'C

Los mintérminos se marcan sólo una vez. Esto por idempotencia, ya que: mi + mi = mi

 Para demostrar teoremas, y también para verificar alguna proposición del álgebra de
Boole.

Ejemplo: Demostrar
a b  ab

En un mapa se tienen:

A A
B 0 1 B 0 1
0 2 0 1
0 1 0 1
1 3 2 3
1 1 1 1

f(A,B)=A'B' f(A,B)=A+B

Negando cualquiera de los mapas se logra demostrar lo pedido.

 Dadas dos funciones, si se desea probar su equivalencia, la aplicación de los mapas simplifica
largas demostraciones algebraicas. Sólo es preciso obtener un mapa para cada una de las
funciones, y luego comparar las formas canónicas.

 La principal aplicación de los mapas es la minimización de funciones. Esto se verá a

continuación.
 Primer taller arquitectura de computadores
Repaso de compuertas lógicas y sus tablas de verdad
Ejercicios a entregar

1.- Obtenga las expresiones simplificadas en sumas de productos de las siguientes funciones de

booles.

(a) f ( x, y , z )   (2,3,6,7)
(b) f ( A, B, C , D)   (7,13,14,15)
(c) f ( A, B, C , D)   (4,6,7,15)
(d) f ( A, B, C , D)   (2,3,12,13,14,15)

2.- Obtenga las expresiones simplificadas en suma de productos de las siguientes expresiones
booleanas.

(a) xy  x' y' z'  x' yz'

(b) A' B  BC '  B' C'

(c) a' b'  bc  a' bc'

(d) xy' z  xyz'  x' yz  xyz

(e) D( A'  B)  B' (C  AD)

(f) ABD  A' C' D'  A' B  A' CD'  AB' D'

(g) A' B' C' D'  A' C' D'  AC ' D'  B' CD'  A' BCD  BC ' D'

Elaboró: Ing. JOEL CARROLL VARGAS M.Sc