NOTAS DE CLASE

CIRCUITOS DIGITALES

4 – PRINCIPIOS DE DISENO LOGICO

COMBINATORIO

PROFESOR: GERMAN MORALES Z.

ENERO DE 2008
4. Simplificación de circuitos lógicos

La simplificación de los circuitos lógicos es la aplicación más importante del

algebra booleana .. Básicamente la simplificación tiene por objeto disminuir el
costo, el espacio, el consumo de energía y aumentar la velocidad, si es posible,
de un circuito lógico mediante la eliminación de bloques lógicos innecesarios, o
mediante la sustitución de un bloque por otro que tenga menos entradas. Para
lograrlo obtenemos primeramente la descripción algebraica de un circuito, la
simplificamos mediante los teoremas booleanos y luego obtenemos el nuevo
circuito simplificado.

4.1 Algebra de Boole.

El algebra de Boole son las matemáticas que se utilizan para los sistemas
digitales. Como hemos visto las expresiones y operaciones básicas booleanas
son la función AND, OR y NOT de las cuales podemos obtener las NAND,
NOR.

Las leyes básicas del algebra de Boole ( la ley conmutativa, la ley asociativa y
la ley distributiva) son las mismas que las del algebra ordinaria..Existen reglas y
teoremas que deben ser aplicados correctamente.

4.1.1 Teoremas de una sola variable

La primera serie de teoremas se relaciona con la operación AND que sólo

comprende una variable que llamaremos x, pero que puede ser cualquier
variable.

(1) X ⋅0 = 0
(2) X ⋅1 = X
(3) X ⋅X = X
(4) X ⋅ X =0

es muy sencillo comprobar cualquiera de esos teoremas si los probamos con x

= 0 y también con x = 1. si el teoremas es aplicable en ambos casos debe ser
correcto, porque x es una variable booleana que por definición solo puede tener
dos valores.

El teorema (1) expresa que si una variable se interfecta con 0, el resultado

debe ser 0 y esto puede comprobarse si sustituimos x tanto con 0 (0*0 = 0)
como con 1 (1*0 = 0), ya que ambos casos satisfacen la definición de la
operación y dada en la tabla 4.1. el teorema (2) expresa que una variable que
se interfecta con 1 no cambia, (0*1 = 0,1*1 = 1) y el teorema (3) expresa que
una variable intersectada a si misma tampoco cambia, (0*0 = 0, 1*1 = 1). El
teorema (4) expresa que el resultado de una variable que intersecta a su
inversa siempre es 0, porque ya sea la variable o su inversa es siempre 0, (0*1
= 0, 1*0 = 0).
La segunda serie de teoremas se refiere a la operación OR y a una sola
variable x.
 (5) X +0 = X
(6) X +1 = 1
(7) X+X =X
(8) X + X =1

Los teoremas (5) y (7) expresan que si una variable se une con 0 o consigo
misma no sufre cambio. El teorema (6) expresa que un 1 unido a cualquier
cosa da por resultado 1 y el teorema (8) expresa que una variable unida con su
inversa siempre da por resultado 1, porque ya sea la variable o su inversa debe
ser 1. como los cuatro primeros teoremas, éstos pueden comprobarse si
sustituimos x por el valor 0 y luego por el valor de 1.
El teorema (9) confirma la doble inversión de una variable:

(9) X =X

Un punto importante que hay que recordar cuando se aplican estos teoremas
es que la variable x puede representar no sólo una variable aislada sino
también una expresión algebraica completa. Por ejemplo, podemos simplificar
A ⋅ B ⋅ C ⋅ 0 si hacemos x igual a la expresión A ⋅ B ⋅ C sustituyendo x por A ⋅ B ⋅ C
en el teorema (1), X ⋅ 0 = 0 , tenemos ( A ⋅ B ⋅ C ) ⋅ 0 = 0 . como otro ejemplo
A ⋅ B ⋅ A ⋅ B puede simplificarse si se sustituye x por A ⋅ B en el teorema (3),
X ⋅ X = X , lo que da por resultado ( A ⋅ B) ⋅ ( A ⋅ B) = A ⋅ B .

En el tercer ejemplo A ⋅ B ⋅ B puede simplificarse si B ⋅ B se sustituye por 0 de

acuerdo con el teorema (4), X ⋅ X = 0 , lo que nos da A ⋅ 0 = 0 de acuerdo con el
teorema (1), X ⋅ 0 = 0 .
Para demostrar cómo pueden usarse estos teoremas para simplificar circuitos
lógicos, trataremos de simplificar el circuito de la figura 4.10.

A⋅ A + B + B ⋅ B +C = 0 + B + B ⋅ B +C teo.(4); X ⋅ X = 0
= B + B ⋅ B +C teo.(5); X + 0 = X
= B + B +C teo.(3); X ⋅ X = X
= B +C teo.(7); X + X = X

Por consiguiente el circuito de la figura 4.10. puede reemplazarse con un solo

bloque OR con entradas B y C, porque por cada serie de valores de entrada los
niveles de salida tanto del circuito original como del simplificado siempre serán
iguales.

Fig. 4.10. Circuito que puede simplificarse utilizando teoremas de una sola
variable.

4.1.2. Descomposición en factores y expansión

Podemos emplear el teorema (14) para demostrar tanto la descomposición en
factores como la expansión:

(14) X*Y + X*Z= X*(Y+Z)

Ese teorema expresa que si una variable aparece 814) en cada termino
considerado como (un grupo de variables intersectadas) de una expresión, la
variable puede sacarse como factor e intersectar al resto de la expresión.
La fig. 4.12 muestra dos circuitos que son equivalentes según el teorema (14).
Como ejemplo de descomposición en factores, el teorema se aplica a la
expresión

A*B*C + A*C*D*E= A*C*(B+D*E)

Fig. 4.12. Dos circuitos equivalentes que demuestra el Teorema (14).

Empleando el mismo teorema (14) se puede demostrar la expansión. Si una

variable x interfecta una expresión y+z, podemos intersectarla separadamente
con cada parte de la expresión.
Como ejemplo, aplicamos el teorema a la expresión siguiente:

A*C*D*(B+E*F)= A*B*C*D + A*C*D*E*F

Como otro ejemplo podemos expandir (A+B) * (C+D) si tratamos primeramente

(A+B) como si fuera una sola variable.

(A+B) * (C+D) = (A+B) * C + (A+B)*D

= A*C+B*C +A*D+B*D

Si invertimos esa secuela para volver a la expresión original, será una

descomposición en factores.

4.1.3. Propiedades de las operaciones AND y OR

Algunas propiedades generales de las operaciones AND y OR pueden

expresarse mediante los siguientes teoremas de variables múltiples:

(9) X ⋅ Y = Y ⋅ X
(10) X + Y = Y + X
(11) X ⋅ (Y ⋅ Z ) = X ⋅ Y ⋅ Z
 (12) X + (Y + Z) = X + Y + Z

Los teoremas (10) y (11) expresan que el orden de las variables no afecta las
operaciones AND u OR y además expresan siempre que las entradas de los
bloques AND y OR son idéntica e intercambiables. Los teoremas (12) y (13)
expresan que el orden en que se ejecutan las operaciones AND y OR no afecta
el resultado final. Para encontrar x+y+z, podemos reunir cualquier par de ellas
y reunir el resultado de las mismas con la tercera. Aplicando esto a los circuitos
lógicos como se ve en la figura 4.11, podemos reunir dos entradas a un tiempo
o las tres a un tiempo y los resultados serán equivalentes.

Fig. 4.11. dos circuitos equivalentes para obtener x+y+z.

4.1.4. Descomposición en factores y expansión

Podemos emplear el teorema (14) para demostrar tanto la descomposición en

factores como la expansión:

(14) X ⋅ Y + X ⋅ Z = X ⋅ (Y + Z )

Ese teorema expresa que si una variable aparece 814) en cada termino
considerado como (un grupo de variables intersectadas) de una expresión, la
variable puede sacarse como factor e intersectar al resto de la expresión.
La fig. 4.12 muestra dos circuitos que son equivalentes según el teorema (14).
Como ejemplo de descomposición en factores, el teorema se aplica a la
expresión

A ⋅ B ⋅ C + A ⋅ C ⋅ D ⋅ E = A ⋅ C ⋅ (B + D ⋅ E)

Fig. 4.12. Dos circuitos equivalentes que demuestra el Teorema (14).

Empleando el mismo teorema (14) se puede demostrar la expansión. Si una
variable x interfecta una expresión y+z, podemos intersectarla separadamente
con cada parte de la expresión.
Como ejemplo, aplicamos el teorema a la expresión siguiente:
 A ⋅ C ⋅ D ⋅ (B + E ⋅ F ) = A ⋅ B ⋅ C ⋅ D + A ⋅ C ⋅ D ⋅ E ⋅ F

Como otro ejemplo podemos expandir (A+B) * (C+D) si tratamos primeramente

(A+B) como si fuera una sola variable.

( A + B) ⋅ ( A + C ) = ( A + B) ⋅ C + ( A + B) ⋅ D
= A ⋅C + B ⋅C + A ⋅ D + B ⋅ D

Si invertimos esa secuela para volver a la expresión original, será una

descomposición en factores.

4.1.5. Teorema de simplificación

Los siguientes teoremas son muy útiles para simplificar circuitos lógicos.

X ⋅Y + X ⋅Y = X (15)
X + X ⋅Y = X (16)
X + X ⋅Y = X +Y (17)
X ⋅ Y + X ⋅ Z + Y ⋅ Z = X ⋅ Y + X .Z (18)

Véase el teorema (15). Como y e y deben ser ya sea 0 y 1 o 1 y 0, por lo tanto,

sin que importe cual sea el valor de y una x se interfecta con 0 mientras que la
otra x se interfecta con 1. Por lo tanto, x*0 + x*1 = x. este teorema puede
comprobarse como

X ⋅Y + X ⋅Y = X ⋅ (Y +Y ) Teo. (14)
= X ⋅1 Teo. (8)
=X Teo. (2)

Cuando se aplica ese teorema a un circuito a un circuito lógico puede eliminar

dos bloques and y or.
El teorema (16) muestra que x*y pueden eliminarse (hacerse iguales a 0) si se
une con x, porque cuando x=0, x*y=0 * y=0.
Cuando x=1, no importa a que sean iguales x*y, ya que 1 unido con cualquier
cosa es igual a 1 (teorema 6). El teorema puede comprobarse como sigue:

X + X ⋅ Y = X ⋅1 + X ⋅ Y Teo. (2)
= X ⋅ (1 +Y ) Teo. (14)
= X ⋅1 Teo. (6)
=X Teo. (2)

La aplicación de este teorema puede eliminar un bloque and u or.

El teorema (17) muestra que cuando x*y se reúne con x, podemos cambiar la x
a 1, porque cuando x no es 1, x=0 y x=1.
En este caso no importa el valor x*y, ya que 1 unido con cualquier cosa es igual
a 1. El teorema (17) puede comprobarse del modo siguiente:

X + X ⋅ Y = X ⋅1 + X ⋅ Y Teo. (2)
= X ⋅ (Y +Y ) + X ⋅Y Teo. (8)
= X ⋅ (Y +Y +Y ) + X ⋅Y Teo. (7)
 = X ⋅Y + X ⋅Y + X ⋅Y + X ⋅Y Teo. (14)
= X ⋅ (Y +Y ) +Y ⋅ ( X + X ) Teo. (14)
= X ⋅1 + Y ⋅1 Teo. (8)
= X +Y Teo. (2)

La aplicación de este teorema puede eliminar un bloque and.

El teorema (18) muestra que si x se interfecta con la variable y y x se interfecta
con la variable z, entonces puede eliminarse la intersección de y y z. la única
forma de que y*z pueda afectar el valor de la expresión es que y*z= 1, lo que
solo puede ocurrir cuando, tanto y como z son 1. Sin embargo, si ambas son 1
entonces ya sea x*y o x*z deben ser también 1. Porque ya sea x o x siempre
deben ser 1. Como ya sea x*y o x*z será 1 cuando y *z es 1, entonces y*z debe
eliminarse, porque 1+1=1. Este teorema puede comprobarse como sigue:

X ⋅ Y + X ⋅ Z + Y ⋅ Z = X ⋅ Y ⋅1 + X ⋅ Z ⋅1 + Y ⋅ Z ⋅ 1 Teo. (2)
= X ⋅Y ⋅ ( Z + Z ) + X ⋅ Z ⋅ (Y +Y ) +Y ⋅ Z ⋅ ( X + X ) Teo. (8)
= X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z
Teo. (14)
= X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z + X ⋅Y ⋅ Z Teo. (7)
= X ⋅Y ⋅ ( Z + Z ) + X ⋅ Z ⋅ (Y +Y ) Teo. (14)
= X ⋅ Y ⋅1 + X ⋅ Z ⋅1 Teo. (8)
= X ⋅Y + X ⋅ Z Teo. (2)

La aplicación de este teorema puede eliminar un bloque and.

4.1.6. Teoremas de inversión

Los teoremas (19) y (20) describen la inversión de las expresiones que

contienen variables que interceptan o unen.

X ⋅Y = X +Y (19)
X +Y = X ⋅Y (20)

Cuando se invierten esas expresiones se invierte cada variable, y la operación

se cambia de AND a OR, o de OR a AND.
La mejor forma de comprobar esos teoremas consiste en emplear una tabla de
combinaciones que permita la comparación de los valores de ambos de una
ecuación para cada posible combinación de valores de variables x e y.

Tabla 4.4. Tabla de combinaciones que se emplea para comprobar el teorema

(19)

(1) (2) (3) (4) (5) (6) (7)

x y x*y x*y x y x+y
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0
Las columnas 1 y 2 de la Tabla 4.4 muestran las cuatro posibles
combinaciones de valores para x e y. La columna 3 muestra los valores de la
expresión x * y obtenidos cuando se intersectan los valores de las columnas 1 y
2. La columna 4 muestra los valores de x*y o sea la inversión de x * y que se
obtienen invirtiendo los valores de la columna 3.

Para comprobar que x* y = x + y, debemos ahora registrar los valores de x+y

comprarlos con los de x * y. Para hacerlo podemos obtener primeramente de x
e y en las columnas 5 y 6 invirtiendo las columnas 1 y 2 respectivamente.
Obtenemos los valores de x + y en la columna 7 si se unen las columnas 5 y 6.

Tabla 4.5. Tabla de combinaciones empleadas para comprobar el teorema (20)

x y x+y x+y x y x* y
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Comparando las columnas 4 y 7 vemos que las dos son iguales para cada
posible combinación de valores de x e y.
El teorema (20) puede comprobarse del mismo modo empleando la Tabla 4.5.

4.2. Aplicación de los teoremas

La aplicación de estos teoremas no siempre puede ser evidente, como se verá

en los ejemplos siguientes. El problema principal consiste en decidir cuáles
teoremas hay que aplicar y en que orden, porque a menudo hay varios caminos
que pueden seguirse.

En general si esos caminos se siguen en la forma adecuada llevarán al circuito

más sencillo, excepto como ocurre a menudo, cuando los circuitos pueden
simplificarse en otros dos o más circuitos distintos aunque igualmente sencillos.

Fig.4.13. Circuito que se simplifica en el ejemplo 1.

Ejemplo 1. Simplifíquese el circuito de la Fig. 4.13.

Solución:

A ⋅ B ⋅ C + A ⋅ B ⋅ (C + D ) = A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ D Teo.(14)
= A⋅ B + A⋅ B ⋅ D Teo(15)
= A⋅ B Teo(16)

Se obtiene el mismo resultado cuando se sigue el método:

A ⋅ B ⋅ C + A ⋅ B ⋅ (C + D ) = A ⋅ B ⋅[C + (C + D )] Teo(14)
= A ⋅ B ⋅ (C +C + D ) Teo(13)
= A ⋅ B ⋅ (1 + D ) Teo(8)
= A ⋅ B ⋅1 Teo(6)
= A⋅ B

La Fig. 4.14 muestra el circuito simplificado.

Ejemplo 2. Simplifíquese el circuito de la Fig. 4.15.

Fig.4.15. Circuito que se simplifica en el ejemplo 2.

Solucion:

A ⋅ B ⋅ C + A ⋅ B + ( A + B +C ) + A ⋅ B ⋅ C + B ⋅ C + A ⋅ B ⋅ C
= A ⋅ B ⋅C + A ⋅ B + A ⋅ B ⋅C + A ⋅ B ⋅C + B ⋅C + A ⋅ B ⋅C TEO(20)
= A ⋅C + A ⋅ B + A ⋅C + B ⋅C TEO(15)

En este puntó el teorema (18) puede aplicarse en dos formas distintas, que
darán por resultado dos circuitos diferentes aunque iguales.

= A ⋅C + A ⋅C + B ⋅C

= A ⋅C + A ⋅ B + A ⋅C

En vez de aplicar el teorema (15) aplicaremos el (16), pero de todos modos

obtendremos los mismos resultados.

A ⋅ B ⋅ C + A ⋅ B + ( A + B +C ) + A ⋅ B ⋅ C + B ⋅ C + A ⋅ B ⋅ C

= A ⋅ B ⋅C + A ⋅ B + A ⋅ B ⋅C + A ⋅ B ⋅C + B ⋅C + A ⋅ B ⋅C TEO(20)

= A ⋅ B + A ⋅ B ⋅C + A ⋅ B ⋅C + B ⋅C TEO(16)

= A ⋅ ( B + B ⋅ C ) +C ⋅ ( B + A ⋅ B ) TEO(14)

= A ⋅ ( B +C ) +C ⋅ ( B + A) TEO(17)

= A ⋅ B + A ⋅C + B ⋅C + A ⋅C TEO(14)

= A ⋅C + B ⋅C + A ⋅C = A ⋅ B + A ⋅C + A ⋅C TEO(18)

Fig. 4.16. solucion del ejemplo 2.

Fig. 4.17. Solución alternativa del ejemplo 2.

Ejemplo 3. Simplifíquese el circuito de la fig. 4.18.

Solucion:

A ⋅ B ⋅ C + A ⋅ C ⋅ ( B ⋅ D ) + ( A + B +C ) + A ⋅ C ⋅ ( A ⋅ B ⋅ C ⋅ D ) + A ⋅ B ⋅ C ⋅ D

A ⋅ B ⋅ C + A ⋅ B ⋅ C ⋅ D + ( A ⋅ B ⋅ C ) + A ⋅ C ⋅ ( A + B +C + D) + A ⋅ B ⋅ C ⋅ D
TEO(12), TEO(20), TEO(19)

A ⋅ B ⋅C + A ⋅ B ⋅C ⋅ D + A ⋅ B ⋅C + A ⋅ A ⋅C + A ⋅ B ⋅C + A ⋅C ⋅C + A ⋅C ⋅C + A ⋅C ⋅ D + A ⋅ B ⋅C ⋅ D
TEO(14)

Fig. 4.18. Circuito que se simplifica en el ejemplo 3.

= A ⋅ B ⋅ C + A ⋅ B ⋅ C ⋅ D + A ⋅ B ⋅ C + A ⋅ A ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ C ⋅ D + A ⋅ B ⋅ C ⋅ D TEO.
(4)
= A ⋅ D ⋅ (C + B + C ) + A ⋅ B ⋅ C ⋅ D + A ⋅ B ⋅ C + A ⋅ B ⋅ C ⋅ D Teo. (14)
= A ⋅ D ⋅ (1 + B ) + A ⋅ B ⋅ C ⋅ D + A ⋅ B ⋅ C + A ⋅ B ⋅ C ⋅ D Teo. (8)
= A ⋅ D + A ⋅ B ⋅C ⋅ D + A ⋅ B ⋅C + A ⋅ B ⋅C ⋅ D Teo. (6)
= D ⋅ ( A + A ⋅ B ⋅ C ) + B ⋅ C ⋅ ( A + A ⋅ D) Teo. (14)
= D ⋅ ( A + B ⋅C ) + B ⋅C ⋅ ( A + D) Teo. (17)
= A ⋅ D + B ⋅C ⋅ D + A ⋅ B ⋅C + B ⋅C ⋅ D Teo. (14)
= A ⋅ D + B ⋅C ⋅ D + B ⋅C ⋅ D Teo. (18)
Tabla de los teoremas

• Teoremas de una sola variable

(1) X ⋅ 0 = 0
(2) X ⋅1 = X
(3) X ⋅ X = X
(4) X ⋅ X = 0
(5) X + 0 = X
(6) X + 1 = 1
(7) X + X = X
(8) X + X =1
(9) X = X
• Propiedades de las operaciones AND y OR:

(10) X ⋅Y = Y ⋅ X
(11) X ⋅ (Y ⋅ Z ) = X ⋅ Y ⋅ Z
(12) X +Y = Y + X
(13) X + (Y + Z ) = X + Y + Z

• descomposición en factores y expansion:

(14) X ⋅ Y + X ⋅ Z = X ⋅ (Y + Z )

• Teoremas de simplificación:

(15) X ⋅Y + X ⋅Y = X
(16) X + X ⋅Y = X
(17) X + X ⋅Y = X +Y
(18) X ⋅Y + X ⋅ Z +Y ⋅ Z = X ⋅Y + X ⋅ Z
(19) X ⋅Y = X +Y
(20) X +Y = X ⋅Y
4.3. Formas canónicas de una función.

Una función booleana puede ser expresada algebraicamente de diferentes

formas. Las formas canónicas facilitan los procedimientos de simplificación
para las expresiones booleanas generando circuitos lógicos mas deseables.

Estas formas canónicas tienen términos suma (maxiterminos) esto es una

suma lógica formada por una operación OR entre los literales Ej: X+Y+Z o
términos sumas (miniterminos) esto es por un producto lógico formado una
operación AND entre literales Ej: XYZ.

Una variable binaria puede aparecer en su forma normal (x) o en la forma e

complemento (x'). Considérese ahora dos variables binarias x y y combinadas
con la operación AND; como cada variable puede aparecer de cualquier forma,
habrá cuatro combinaciones posibles: x'y', x'y, xy' y xy. Cada no de estos
cuatro términos AND se llaman términos mínimos (miniterminos) de un
producto normalizado. De igual manera, se pueden cambiar n variables para
formar 2n términos mínimos. Los 2n diferentes términos mínimos pueden
determinarse por un método similar al mostrado en Tabla 4-1 para tres
variables. Los números binarios de 0 a 2n -1 se listan bajo las n variables. Cada
término mínimo se obtiene de un término AND de n variables con cada variable
tildada, si el bit correspondiente al número binario es 0 y si no está tildada a 1.
Un símbolo para cada término mínimo se ilustra en la tabla en la forma de m j,
donde j denota, el equivalente decimal del número binario del término mínimo
correspondiente.

Tabla 4-1 Términos mínimos y máximos para tres variables binarias

Términos mínimos Términos máximos
x y z Término Designación Término Designación

0 0 0 x'y'z' m0 x+y+z M0
0 0 1 x'y'z m1 x + y + z' M1
0 1 0 x'yz' m2 x + y'+ z M2
0 1 1 x'yz m3 . x + y' + z' M3
1 0 0 xy'z' m4 x' + y + z M4
1 0 1 xy'z m5 x' + y + z' M5
1 1 0 xyz' m6 x' + y' + z M6
1 1 1 xyz m7 x' + y' + z' M7

De manera similar, las n variables formando un término OR, con cada variable
tildada o no tildada, darán 2n combinaciones posibles llamadas términos
máximos (maxiterminos) de las sumas normalizadas. Los ocho términos
máximos de las tres variables, conjuntamente con la simbología asignada, se
listan en la Tabla 4-1. Cualesquier 2n términos para n .variables pueden
determinarse de manera similar. Cada término máximo se obtiene de un
término OR de n variables con cada variable no tildada el correspondiente bit
es 0 y tildada si es 1.* Nótese que cada término máximo es el complemento de
su correspondiente término mínimo y viceversa.

Una función de Boole puede ser expresada algebraicamente a partir una tabla
de verdad dada, conformando un término mínimo por cada combinación de las
variables que producen un 1 en la función para luego, tener la OR de todos los
combinaciones 001, 100, 111 como x'y'z, xy’z' y x y z respectivamente. Como
cada uno de estos términos mínimos resulta en f1 = 1, se tiene:

Tabla 2-4 Funciones de tres variables

x y z Función f1) Función f2

0 0 0 0 0
0 0 l 1 0
0 1 0 0 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

f1 = x'y'z + xy'z' + .xyz = m1 + m4 + m7

De manera similar, se puede fácilmente verificar que:

f2 = x’yz + xy’z + xyz’+ xyz = m3 +m5 +m6 +m7

Considérese ahora el complemento de una función de Boole. Este puede

leerse de una tabla de verdad formando un término mínimo por cada
combinación que produce un cero y luego haciendo la función OR de esos
términos. El complemento de f1 se lee así:

f1 = x 'y' z' + x'yz' + x'yz + xy’z + xyz’

Si se obtiene el complemento de f’1 se obtiene la función f1 :

f1 = (x + y + z)(x + y' + z)(x + y' + z')(x' + y + z')(x' + y' + z) = M0 •M2 •M3 • M5 •M6

De igual manera, es posible leer la expresión f2 de la tabla:

f2 = (x + y + z)(x + y + z')(x + y' + z)(x' + y + z) = M0 •M1 •M2 • M4

4.3.1. Suma de términos mínimos

Se había dicho antes que para n variables binarias, se pueden obtener 2n

términos mínimos diferentes y que cualquier función de Boole puede
expresarse como una suma de términos mínimos. Los términos mínimos cuya
suma define la función de Boole son aquellos que dan el 1 de la función en una
tabla de verdad. Como la función puede ser 1 ó 0 para cada término mínimo y
ya que hay 2n términos mínimos, se pueden calcular las funciones posibles
que pueden formarse con n variables como 22n. Algunas veces es conveniente
expresar la función de Boole en la forma de suma de términos mínimos. Si no
está en esta forma, se puede llegar a ella expandiendo primero la expresión a
una suma de términos AND. Luego se inspecciona cada término para ver si
contiene todas las variables (dominio de la función). Si le hace falta una o más
variables, se aplica la función AND con una expresión tal como x + x', donde x
sea una de las variables faltantes. El siguiente ejemplo aclara este
procedimiento.

EJEMPLO: Expresar la función de Boole F = A + B'C como suma de términos

mínimos. La función tiene tres variables:

A, B y C. Como el primer término A no tiene las otras dos variables por tanto:

A = A(B + B') = AB + AB'

Como la expresión carece de una variable:

A = AB(C + C') + AB'(C + C')

= ABC + ABC' + AB'C + AB'C'

El segundo término B'C carece también de una variable:

B'C = B'C(A + A') = AB'C + A'B'C

Combinando todos los términos se obtendrá:

F= A+B'C = ABC + ABC' + AB'C + AB'C' + AB'C + A'B'C

Pero como AB'C aparece dos veces, y de acuerdo al teorema (x + x = x), es

posible quitar uno de ellos. Rearreglando los términos en orden ascendente se
obtendrán finalmente:

F = A'B'C + AB'C' + AB'C + ABC' + ABC = m1 + m4 + m5 + m6 + m7

Es conveniente algunas veces, expresar la función de Boole cuando está

compuesta de una suma de términos mínimos por medio de la siguiente forma
simplificada:

F(A, B, C) = ∑(1,4, 5, 6, 7)

El símbolo de sumatoria implica los términos a los cuales se les aplica la

función OR o Los términos entre paréntesis son los términos mínimos de la
función. Las letras entre paréntesis a continuación de la F forman la lista de las
variables en el orden tomado cuando el término mínimo se convierte en un
término AND.

4.3.2. Producto de términos máximos

Cada una de las 22n funciones de n variables binarias pueden expresarse como
un producto de términos máximos. Para expresar las funciones de Boole como
un producto de términos máximos se debe primero llevar a una forma de
términos OR Esto puede lograrse usando la ley distributiva x + yz= (x+y)(x+z) y
si hay una variable x faltante en cada término OR se le aplicará la función OR
conjuntamente con xx'. Este procedimiento se clarifica por medio del siguiente
ejemplo:

EJEMPLO: Expresar la función de Boole F = xy + x'z como un producto en la

forma de términos máximos. Primero conviértase la función a términos OR
usando la ley distributiva:

F= xy + x'z = (xy + x')(xy + z) = (x + x')(y + x')(x + z)(y + z) = (x' + y)(x + z)(y + z)

La función tiene tres variables: x, y y z. A cada término OR le hace falta una

variable, por tanto:

x' + y = x' + y + zz’ = (x' + y + z)(x' + y + z')

x + z = x + z + yy' = (x +y + z)(x +y' + z)
y + z = y + z + xx' = (x + y + z)(x' + y + z)

Combinando todos los términos y quitando aquellos que aparezcan más de una
vez se obtendrá finalmente:

F = (x + y + z)(x + y' + z)(x' + y + z)(x' + y + Z') = M0 M2 M4 M5

Una forma conveniente de expresar esta función es de la siguiente manera:

F(x,y, z) = π(0, 2, 4, 5)

El símbolo de producto π denota la aplicación de la función AND a los

términos máximos. Los números representan los términos máximos de la
función.

4.4. Método del Mapa de Karnaugh

Los mapas de Karnaugh constituyen un método sencillo y apropiado para la

minimización de funciones lógicas El tamaño del mapa depende del número de
variables, y el método de minimización es efectivo para expresiones de hasta 6
variables.

Representación de funciones con mapas de Karnaugh.

Un mapa de Karnaugh es una representación gráfica de una tabla de verdad, y
por lo tanto existe una asociación univoca entre ambas la tabla de verdad tiene
una fila por cada rminitermino. Mientras que el mapa de Karnaugh tiene una
celda por cada rminitermino De manera análoga, también existe una
correspondencia unívoca entre las filas de la tabla de verdad y las celdas del
mapa de Karnaugh si se utilizan maxiterminos

Mapas de Karnaugh de 2 variables

Consideremos ahora dos variables A y B que deben tener una representación

en K Cuatro son las formas posibles de combinar A y B A=0 y B=0, A=0 y B=1,
A=1 y B=0. A=1 y B=1

Sea f una función de 2 variables f (A,B)

Para elaborar el mapa de Karnaugh tendremos 22 = 4 combinaciones. En la
figura se muestra la tabla de verdad con la lista de los miniterminos y el lugar
que ocupa cada uno de ellos en un mapa

Mapas de Karnaugh de 3 variables

Sea f una función de 3 variables f (A.B.C)

Para elaborar el mapa de Karnaugh tendremos 23 = 8 combinaciones.
Antes de seguir con 4. 5 y 6 variables veamos como se representa una función
en un mapa de Karnaugh

1. Desde la tabla de verdad

Supongamos que tenemos la siguiente tabla de verdad para una función de 3

variables f(ABC):

2. Directamente desde una función.

Para este caso la función puede ser o no canónica. Si es canónica. Por ejemplo
la función A’B’C + A’BC’ + ABC’ + ABC

Si no es canónica. Pruebe a representar la función f( A,B,C)= AB +AB’C +

A’B’C
Problema Probar con Mapas de Karnaugh que ABC + ABC + ABC + ABC = AC
+ BC

Mapas de Karnaugh de 4 variables

Sea f una función de 4 variables: f(A.B.C.D)

Para elaborar el mapa de Karnaugh tendremos 24 = 16 combinaciones

Mapas de Karnaugh de 5 variables

Sea f una función de 5 variables: f (A.B,C,D,E)
Para elaborar el mapa tendremos 25 = 32 combinaciones

Mapas de Karnaugh de 6 variables

Sea f una función de 6 variables: f (A.B.C.D.E.F)

Para elaborar el mapa tendremos 2a = 64 combinaciones
Simplificación de funciones con mapas de Karnaugh

Obtener la función de un Mapa de Karnaugh es el procedimiento inverso a la

de la realización del mapa Un término de la función coloca uno o más 'unos' en
el mapa de Karnaugh Tomar esos unos, agrupándolos de la forma adecuada,
nos permite obtener los términos de la función.

Utilizaremos los Mapas de Karnaugh para obtener una función mínima de dos
niveles Suma de Productos. Forma de dos niveles

ADYACENCÍA LOGICA
Terminología para la simplificación Implicante Primo, Implicante Primo
Esencial

Implicante: Conjunto de unos en un mapa de Karnaugh que representa un

término producto de variables. Se denomina Implicante porque cuando este
término toma el valor ‘1’ implica que también la función toma el valor 1. Un
rminitermino solo es un Implicante Primo. Implicante que no está incluido
completamente dentro de otro Implicante no puede combinarse con otro
Implicante para eliminar un literal.

Implicante Primo Esencial. Implicante primo que contiene uno o más

miniterminos que no están incluidos en cualquier otro Implicante primo.

Algoritmo de minimización mediante mapas de Karnaugh.

1 Identificar los implicantes primos. Para este se busca obtener los grupos
con mayor cantidad de unos adyacentes Los grupos deben contener un
numero de unos que son potencias de 2

2 Identificar todos los implicantes primos esenciales

3 La expresión mínima se obtiene seleccionando todos los implicantes

primos esenciales y el menor número de implicantes primos para cubrir
los miniterminos no incluidos en los implicantes primos esenciales

Ejemplo Simplificar lo función

F = AB’C’D + A’B’CD + A’BC’D’ + ABC’D’ + A’BCD’ + ABCD + A’B’C’D +

A’B’C’D’ + ABCD’

Minimización en mapas de Karnaugh de 5 variables

Simplificar la función =  m(2,8,11,15,18,20,21,27,28,29,31).

Se coloca un 1 en los miniterminos
Minimización en mapas de Karnaugh de 6 variables Obtengo una función
mínima para el siguiente mapa de Karnaugh
 PROBLEMAS MAPAS DE KARNAUGH
EJEMPLO 7. Hay 5 personas que actúan como jueces en un competencia
dada. El voto de cada uno de ellos se indica con un 1 (pasa) o 0 (fracasa) en
un línea de señal. Las 5 líneas de señal son las entradas a un circuito
lógico combinacional. Las reglas de la competencia permiten sólo la
disensión de un voto. Si la votación es 2-3 o 3-2, la competencia debe
continuar. El circuito lógico debe tener dos salidas, XY. Si el voto es 4-1
o 5-0 para pasar, XY=11. Si el voto es 4-1 o 5-0 para fracasar, XY=00; si
el voto es 3-2 o 2-3 para continuar, XY=10.

2. Un número primo es aquel que sólo es divisible entre si mismo y la unidad.

Diseñe un circuito lógico mínimo que detecte todos los números
primos entre 0 y 31. La salida F(A, B, C, D, E), donde A es la variable de
mayor peso binario, será igual a 1, si y sólo si los cinco bits de entrada
representan un número primo. Realice el logigrama utilizando
inversores y compuertas No Y.
3. En uno de los laboratorios de una compañía químico farmacéutica se
elaboran 14 distintas soluciones a partir de las componentes W, X, Y y Z.
Estas sustancias pesan 800, 400, 200 y 100 mg, respectivamente. Las
soluciones depositadas en frascos se transportan por medio de una banda hasta
una báscula. Si el peso indicado en la báscula es uno de los siguientes: 200,
500, 700, 800, 1100, 1400 o 1500 mg, entonces un dispositivo
electromecánico F, después de agregar al compuesto la sustancia Q, sellará
el frasco sobre la báscula y lo apartará de la banda; de otro modo, el frasco
permanecerá abierto y la banda lo transportará hacia otra etapa del proceso.
Además, por las condiciones previas del proceso, no es posible que
lleguen a la báscula ni frascos vacíos, ni frascos que contengan las siguientes
sustancias: WY, YZ, WX o WZ; todas las demás combinaciones sí
pueden llegar hasta la báscula.

4. En la torre de control de un patio de ferrocarril,un controlador debe

seleccionar la ruta de los furgones de carga que entran a una sección del patio,
mismos que provienen del punto A, como puede verse en el tablero de control
de la figura adjunta. Dependiendo de las posiciones de los conmutadores, un
furgón puede llegar a uno cualesquiera de los cuatro destinos. Otros furgones
pueden llegar desde los puntos B o C.
Diseñe un circuito, con inversores y compuertas No O, que reciba como
entradas las señales S1 a S5, indicadores de las posiciones de los conmutadores
correspondientes, y que encienda una lámpara D0 a D3, indicando el destino al
que llegará el furgón proveniente de A.
Para los casos en que los furgones puedan entrar de B o C (S2 o S3 en la
posición 0), todas las lámparas de salida deben encenderse, indicando
que un furgón proveniente de A, no puede llegar con seguridad a su
destino.
NOTA: S1 bit de mayor peso binario.

5. Un circuito lógico tiene 5 entradas A, B, C, D y E (donde A es la de mayor

peso binario). Cuatro de las entradas representan un dígito decimal en
BCD (Decimal Codificado en Binario, por sus siglas en inglés). La primera
entrada, A, es de control.
Cuando el control está en 0 lógico, la salida Z e igual a 0 si el número
decimal es impar y 1 si es par.
Cuando el control está en 1 lógico, la salida Z es igual a 1 cuando la
entrada en múltiplo de 3, en caso contrario es 0.
Considerando las condiciones irrelevantes, diseñe un circuito mínimo
utilizando sólo inversores y compuertas No O.
NOTA: Considere al 0 como un número par.

6. Un técnico de un laboratorio químico tiene 4 productos A, B, C y D. Cada

producto debe encontrarse en uno cualesquiera de dos recipientes
de almacenamiento.
Periódicamente, se requiere cambiar uno o más productos de un recipiente a
otro. La naturaleza de los productos es tal, que es peligroso guardar A y B juntos
a menos que D esté presente en el mismo recipiente. También es peligroso
almacenar B y C juntos a menos que D esté presente.
Este proceso no permite que alguno de los tanques esté vacío.
Obtener el circuito mínimo de la expresión de una variable Z que deberá tener
el valor de 0 para cada situación peligrosa de almacenamiento, utilizando sólo
inversores y compuertas No O.
NOTA: Considere a A como la variable de mayor peso binario.
7. Un posicionador de eje, proporciona una señal de 4 bits que indica la
posición de un eje en pasos de 30°. Utilizando el código de Gray, el cual se
muestra en la siguiente tabla, diseñe un circuito (realización mínima de suma
de productos) que produzca una salida que indique en dónde se encuentra el
eje.
POSICIÓN SALIDA DEL POSICIÓN SALIDA DEL
DEL EJE DECODIFICADOR DEL EJE DECODIFICADOR

0°<= P <=30° 0 0 1 1 180°< P <=210° 1 1 0 0

30°< P <=60° 0 0 1 0 210°< P <=240° 1 1 0 1
60°< P <=90° 0 1 1 0 240°< P <= 270° 1 1 1 1
90°< P <=120° 0 1 1 1 270°< P <=300° 1 1 1 0
120°< P <=150° 0 1 0 1 300°< P <=330° 1 0 1 0
150°< P <=180° 0 1 0 0 330°< P <=360° 1 0 1 1

8. Obtener el diagrama lógico mínimo, de un circuito de 5 entradas: Dos de

datos A y B y tres de control C2, C1 y C0.
La función de salida depende de los ocho posibles estados de las señales de
control, de acuerdo a la siguiente tabla:

CONTROL (DECIMAL) F

0 1

1 A+B

2 (A B)'

3 A OEX B

4 (A OEX B)'

5 AB

6 (A + B)'

7 0

Considere a C2 y A como las variables de mayor peso binario,

respectivamente.
9. El sistema nervioso humano, incluyendo el cerebro, está hecho de células
especializadas llamadas neuronas. Cada neurona tiene sinapsis (puntos de
interconexión, como se muestra en la figura adjunta) de excitación y
sinapsis de inhibición. Una neurona produce una salida 1 si el número de
sinapsis de excitación con pulsos 1 excede el número de sinapsis de
inhibición con pulsos 1 por al menos el valor de umbral de la neurona.

Determine la función booleana f(a,b,c,d,e) de emisión de pulsos a través del

canal de salida (axón) en el modelo de la figura, bajo las siguientes condiciones:
(C1) Valor del umbral = 1 [es decir, se produce una salida 1 si el número de
sinapsis de excitación con pulsos 1, excede por al menos uno el número de
sinapsis de inhibición con pulsos 1], y
(C2) Siempre que haya al menos un pulso 1 en alguna sinapsis del puerto de
excitación, habrá al menos un pulso 1 en alguna sinapsis del puerto de
inhibición [es decir, no es posible -en este modelo restringido- que existan
pulsos 1 en el puerto de excitación si no existe al menos un pulso 1 en el
puerto de inhibición].
Minimizar f(a, b, c, d, e) haciendo uso de las condiciones irrelevante
(C2). Realizar el logigrama utilizando inversores y compuertas No Y.

10. Textura es la organización de una superficie como un conjunto de elementos

repetidos. En un proceso automático para clasificar texturas artificiales, un
sensor de 4 puntos (figura adjunta) envía señales a un circuito combinatorio
cuya tarea es discriminar (emitiendo pulsos 1) los siguientes elementos:

En todos los casos que inspecciona el sensor se activan al menos 2 puntos

de la rejilla (es decir, no se presentan casos en los cuales se activa tan solo
un punto ni casos en los que no se activa ningún elemento)
Minimizar la función booleana f(a,b,c,d,e) a la salida del circuito
discriminador, haciendo uso de las condiciones irrelevantes. Realizar el
circuito mediante inversores y compuertas No O.

11. En una fábrica un dispositivo con 5 fotoceldas (figura adjunta), registra

los caracteres formados abriendo pequeñas ranuras en una tarjeta de control. Si
en la tarjeta registrada hay uno de los símbolos:

(Para el símbolo I son válidas las dos posiciones), entonces el dispositivo

acciona un taladro.
En el proceso no hay tarjetas con alguno de los caracteres adjuntos:
Diseñe un circuito combinatorio a la salida del dispositivo que acciona el
taladro? Minimizar la función.
12. Se desea diseñar e instrumentar un circuito combinatorio mínimo de
dos entradas con dos bits cada una, sobre las cuales se codifican dos de los
cuatro tipos de sangre existentes y a su salida se obtenga una señal que
informe sobre la posibilidad o imposibilidad de la transfusión de uno
de ellos sobre el otro, dadas las siguientes reglas de compatibilidad entre ellos.
Los tipos de sangre son 4: A, B, AB y O.
El tipo O puede donar a cualquier otro tipo, pero sólo puede recibir de él
mismo.
El tipo AB puede recibir de cualquier otro tipo pero sólo puede donar a AB.
La clase A puede donar a A o a AB y recibir de A u O únicamente.
Por último, el tipo B puede donar al mismo B o al tipo AB y recibir de B u O.
La señal de salida deberá ser 1 cuando la transfusión propuesta en las entradas
sea permitida.
13. En un sistema de detección luminosa que tiene el arreglo mostrado en la
figura adjunta, se genera una señal de salida con valor de 1 únicamente
cuando dos fotoceldas adyacentes están activadas, siempre y cuando la
fotocelda del centro esté también activada.
NOTA: No es posible, en este sistema, que exista una señal de salida 0 o 1
si no hay al menos tres fotoceldas activadas.
Considerando a A como la variable más significativa, obtener el logigrama
mínimo, considerando las condiciones indiferentes y utilizando sólo
inversores y compuertas No Y.
 14. Un robot de juguete -llamado U-2- está diseñado para ser capaz de seguir
una trayectoria (previamente programada por medio de controles que el robot
tiene en la espalda) avanzando cuadro por cuadro en una área de 5x6 cuadros.
El robot U-2 puede realizar una de las cuatro acciones siguientes:
(D) Girar (sobre su eje vertical) 90° a la derecha y luego avanzar al
centro del siguiente cuadro si su pequeño cerebro recibe la señal binaria
01.
(I) Girar 90° a la izquierda y luego avanzar al centro del siguiente
cuadro si su diminuto cerebro percibe la señal binaria 10.
(F) Avanzar al frente un cuadro si su cerebro recibe la señal 00.
(A) Hacer alto si su cerebro recibe la señal 11.

Programar el robot para que recorra el laberinto de la Figura (a).

Determinar las funciones booleanas del par de estímulos binarios
que recibe el minicerebro del robot durante este recorrido y minimizarlas
mediante mapas de Karnaugh. (En este problema hay condiciones
irrelevantes -parte de la solución consiste en encontrarlas).
Los controles en la espalda del U-2 están localizados en dos áreas: En el área I
se indicará el cuadro inicial mediante los controles de dos posiciones a, b, c, d y
e [como se muestra en la Figura (c)]; si el control a se presiona del lado
derecho, el peso de la variable a se contabilizará para determinar el número
asignado al cuadro inicial (lo mismo ocurrirá para el resto de las variables). En
el área II se programa la trayectoria por medio de 30 controles de tres
posiciones cada uno.
 P4 P3 P2 P1
0 0 0 0 0 0
1 0 0 0 0 1
2 0 0 0 1 0
3 0 0 0 1 1
4 0 0 1 0 0
5 0 0 1 0 1
6 0 0 1 1 0
7 0 0 1 1 1
8 0 1 0 0 0
9 0 1 0 0 1
10 0 1 0 1 0
11 0 1 0 1 1
12 0 1 1 0 0
13 0 1 1 0 1
14 0 1 1 1 0
15 0 1 1 1 1
16 1 0 0 0 0
17 1 0 0 0 1
18 1 0 0 1 0
19 1 0 0 1 1
20 1 0 1 0 0
21 1 0 1 0 1
22 1 0 1 1 0
23 1 0 1 1 1
24 1 1 0 0 0
25 1 1 0 0 1
26 1 1 0 1 0
27 1 1 0 1 1
28 1 1 1 0 0
29 1 1 1 0 1
30 1 1 1 1 0
31 1 1 1 1 1

ED\CBA 000 001 011 010 110 111 101 100 ED\CBA 000 001 011 010 110 111 101 100

00 00

01 01

11 11

10 10

ED\CBA 000 001 011 010 110 111 101 100 ED\CBA 000 001 011 010 110 111 101 100

00 00

01 01
11 11

10 10

P4 P3 P2 P1 S4 S3 S2 S1
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
12 1 1 0 0
13 1 1 0 1
14 1 1 1 0
15 1 1 1 1

DC\BA 00 01 11 10 DC\BA 00 01 11 10 DC\BA 00 01 11 10

00 00 00
01 01 01
11 11 11
10 10 10

DC\BA 00 01 11 10 DC\BA 00 01 11 10 DC\BA 00 01 11 10

00 00 00
01 01 01
11 11 11
10 10 10

CB\A 0 1 CB\A 0 1 CB\A 0 1 CB\A 0 1

00 00 00 00
01 01 01 01
11 11 11 11
10 10 10 10