SISTEMAS

COMBINACIONALES

ELT 3890 AUTOMÁTICA I

MSc. Ing. Ramiro Franz Aliendre García

Ingeniería Eléctrica e Ingeniería Electrónica
Facultad Nacional de Ingeniería
UNIVERSIDAD TÉCNICA DE ORURO

Bibliografía:

 DISEÑO DIGITAL – Morris Mano

Tercera Edición
2001

1
LÓGICA BINARIA
 Algebra booleana
 Valores binarios
 Dos valores discretos (verdadero o falso)
 Operaciones lógicas:
 AND, OR, NOT
 Tablas de verdad

Circuitos de “switcheo”

 Pulsadores, transistores: “on-off”

L=AB L=A+B

2
Señales binarias

 Señales eléctricas:
tensiones o corrientes
 Dos niveles de voltaje
separados: lógico-1 y
lógico-0
 La región intermedia
es atravesada sólo en
la transición de
estados
5

Compuertas lógicas

 Circuitos que operan con una o más

señales de entrada para producir una
señal de salida

3
Compuertas lógicas (cont.)

 Las entradas x y y pueden ser: 00, 10,

11 o 01:

Compuertas lógicas (cont.)

 Compuertas de tres o más entradas

4
ÁLGEBRA DE BOOLE
 Herramienta matemática que permite modelar
Sistemas Digitales.
 Desarrollada por el matemático inglés George
Boole (1854) y propuesta en su libro “Una
investigación sobre las leyes del
pensamiento”.
 En 1938 C.E. Shannon introduce el algebra
booleana de dos valores llamada algebra de
conmutación.
 Para definir formalmente se utiliza los
postulados desarrollados por E.V. Huntington
de 1904.
9

Definición axiomática

Un conjunto de elementos: B, y dos

operadores binarios + y 
Ax1. Cerradura c.r.a. operador + ()
a) x, y  B  x+y  B
b) x, y  B  xy  B
Ax2. Un elemento de identidad c.r.a.
operador + ()
a) x+0=0+x=x
b) x1=1x=x
10

5
Definición axiomática (cont.)

Ax3. Conmutativa c.r.a. + ()

a) x+y=y+x
b) xy=yx
Ax4.  es distributivo sobre +
a) x(y+z)=(xy)+(xz)
+ es distributivo sobre 
b) x+(yz)=(x+y)(x+z)

11

Definición axiomática (cont.)

Ax5.  x  B $ x’  B
(complemento de x) :
a) x+x’=1
b) xx’=0
Ax6. $ al menos dos elementos
x, y  B, : xy

12

6
Algunas diferencias

 No se incluye la ley asociativa, pero se

deduce de los otros axiomas
 La ley distributiva de + sobre  no se
cumple para el álgebra ordinaria
 El operador complemento no se
cumple para el algebra ordinaria

13

Algebra booleana de dos valores

 Conjunto B={0,1}, con reglas para los

operadores binarios + y 

 Cumple con los postulados de

Huntington

14

7
TEOREMAS Y PROPIEDADES

 Principio de dualidad: toda expresión

algebraica sigue siendo válida, si se
intercambian los operadores OR y AND
y se sustituyen los ceros por los unos y
los unos por los ceros

15

TEOREMAS Y PROPIEDADES (cont.)

 Seis teoremas y cuatro axiomas

(postulados)

16

8
Teoremas básicos

Tr1. a) x+x=x
x+x =(x+x)1 Ax2b)
=(x+x)(x+x’) Ax5a)
=x+xx’ Ax4b)
=x+0 Ax5b)
=x Ax2a)
b) xx=x

17

Teoremas básicos (cont.)

Tr2. a) x+1=1
x+1=1(x+1) Ax2b)
=(x+x’)(x+1) Ax5a)
=x+x’1 Ax4b)
=x+x’ Ax2b)
=1 Ax5a)
b) x0=0

18

9
Teoremas básicos (cont.)
Tr3. Involución: (x’)’=x

Tr4. Asociatividad:
a) x+(y+z)=(x+y)+z=x+y+z
b) x(yz)=(xy)z=xyz

Tr5. De Morgan:
a) (x+y)’=x’y’
b) (xy)’= x’+y’
19

Teoremas básicos (cont.)

Tr6. Absorción
a) x+xy=x
x+xy =x1+xy Ax2b)
=x(1+y) Ax4a)
= x(y+1) Ax3a)
=x1 Tr2a)
=x Ax2b)
b) x(x+y)=x

20

10
Teoremas básicos (cont.)

Demostración por tablas de verdad Tr6a)

21

Teoremas básicos (cont.)

Demostración por tablas de verdad Tr5a)

22

11
Precedencia

Para evaluar expresiones booleanas:

1. Paréntesis
2. NOT
3. AND (multiplicación)
4. OR (suma)

23

FUNCIONES BOOLEANAS

 Función booleana descrita por una

expresión algebraica y consta de
variables binarias, las cttes. 1 y 0, y
los símbolos de operación
 Para una valor dado de las variables, la
función puede ser 1 o 0. Ejemplos:
F1=x + y’z
F2=x’y’z + x’yz + xy’

24

12
FUNCIONES BOOLEANAS (cont.)
 F1 igual a 1 si x es 1 o si tanto y’ como
z son 1. F1 igual a cero en otros casos
 Función booleana expresa la relación
lógica entre variables binarias
 Se evalúa determinando el valor
binario de la expresión, para todos los
posibles valores de las variables:
TABLA DE VERDAD
 Número de filas: 2n, n número de
variables de la función.
25

FUNCIONES BOOLEANAS (cont.)

 Tabla de verdad para F1 y F2

26

13
FUNCIONES BOOLEANAS (cont.)

 Implementación con compuertas de F1

27

FUNCIONES BOOLEANAS (cont.)

 Una sola representación en tabla de

verdad, en forma algebraica varias
representaciones. Ejemplo, para F2:

F2 = x’y’z + x’yz + xy’

= x’z(y’ + y) + xy’
= x’z + xy’

28

14
FUNCIONES BOOLEANAS (cont.)

29

Manipulación algebraica
 Circuito más sencillo, si se reduce la
expresión algebraica. Ejemplos:

1. x + x’y = (x + x’)(x + y)
= 1(x+y)
= x+y
2. xy + x’z + yz = xy + x’z + yz(x + x’)
= xy + x’z + xyz + x’yz
= xy(1 + z) + x’z(1 + y)
= xy + x’z

30

15
Complemento de una función

 Teoremas de DeMorgan generalizados:

(A+B+C+ … +F)’ = A’B’C’ … F’
(ABC … F)’ = A’+B’+C’+ … +F’
Ejemplo: F1 = x’yz’ + x’y’z
F1’ = (x’yz’ + x’y’z)’
= (x’yz’)’(x’y’z)’
= (x + y’ + z)(x + y + z’)

31

Complemento de una función (cont.)

Ejemplo: F2=x(y’z’+yz)
F2’ =[x(y’z’+yz)]’
=x’+(y’z’+yz)’
=x’+(y’z’)’(yz)’
=x’+(y+z)(y’+z’)

32

16
FORMAS CANÓNICAS

 n variables, directas o negadas, que

forman un término AND, dan lugar a 2n
combinaciones llamadas mintérminos o
producto estándar
 n variables, directas o negadas, que
forman un término OR, dan lugar a 2n
combinaciones llamadas maxtérminos
o suma estándar.

33

Mintérminos y maxtérminos

 Para tres variables:

 Cada maxtérmino es el complemento

del mintérmino correpondiente
34

17
Mintérminos y maxtérminos (cont.)

 Una función booleana puede ser expre-

sada a partir de una tabla de verdad,
formando un mintérmino para cada
combinación de variables que produce
un 1. Ejemplo:

35

Mintérminos y maxtérminos (cont.)

f1 = x’y’z+xy’z’+xyz = m1+m4+m7
f2 = x’yz+xy’z+xyz’+xyz=m3+m5+m6+m7
36

18
Mintérminos y maxtérminos (cont.)

 Propiedad importante: toda función

booleana se puede expresar como
suma (OR) de mintérminos
 El complemento de f1 (mintérminos
donde la función es 0):

37

Mintérminos y maxtérminos (cont.)

f1’= x’y’z’+x’yz’+x’yz+xy’z+xyz’
= m0+m2+m3+m5+m6
38

19
Mintérminos y maxtérminos (cont.)
f1’ = x’y’z’+x’yz’+x’yz+xy’z+xyz’
= m0+m2+m3+m5+m6
(f1’)’ = f1
= (x+y+z)(x+y’+z)(x’+y+z)(x’+y+z’)(x’+y’+z)
= M 0  M2  M3  M5  M 6

 Para f2:
f2 = (x+y+z)(x+y+z’)(x+y’+z)(x’+y+z)
= M0 M 1 M2 M 4
39

Suma de mintérminos
 Ejemplo:
F = A+B’C
= A (B+B’) + B’C
= AB +AB’ + B’C
= AB(C+C’)+AB’(C+C’)+(A+A’)B’C
= ABC+ABC’+ AB’C + AB’C’+A’B’C
F = A’B’C +AB’C’+AB’C+ABC’+ ABC
= m1 + m4 + m5 + m6 + m7
F = S (1, 4, 5, 6, 7)
40

20
Suma de mintérminos (cont.)
 También mediante la tabla de verdad:
F = A+B’C

41

Producto de maxtérminos

 Primero poner en formato OR:

x + yz = (x + y)(x + z)

 Ejemplo: F = xy + x’z
F = (xy + x’) (xy + z)
= (x + x’)(y + x’)(x + z)(y + z)
= (x’ + y)(x + z)(y + z)

42

21
Producto de maxtérminos (cont.)
 Función de tres variables, a cada
término OR le falta una variable:
x’ + y = x’ + y + zz’
= (x’+y+z)(x’+y+z’)
x + z = x + z + yy’
= (x+y+z)(x+y’+z)
y + z = xx’ + y + z
= (x+y+z)(x’+y+z)

43

Producto de maxtérminos

F = (x+y+z)(x+y’+z)(x’+y+z)(x’+y+z’)
= M0 M 2 M4 M 5

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

44

22
Conversión entre formas canónicas

Ejemplo:
F(A, B, C)=S(1, 4, 5, 6, 7)
Su complemento es:
F’(A, B, C)= S(0, 2, 3)= m0+m2+m3
Complemento de F’ (teor. DeMorgan):
F= (m0+m2+m3)’ = m0’m2’m3’
= M0M2M3 = P (0, 2, 3)

45

Conversión entre formas canónicas (cont.)

 Es evidente:
mj’ = Mj
 También:
Suma mintérminos=Producto maxtérminos
 Procedimiento general: Intercambiar
los símbolos S y P e incluir sólo los
números faltantes en la forma original
 (S de 1’s, P de 0’s)

46

23
Conversión entre formas canónicas (cont.)

 También es posible convertir la

expresión algebraica en suma de
mintérminos o producto de
maxtérminos mediante la tabla de
verdad. Ejemplo:
F = xy + x’z

47

Conversión entre formas canónicas (cont.)

F = S(1, 3, 6, 7)

F = P(0, 2, 4, 5)

48

24
Formas estándar

 En las formas canónicas están

presentes todas las variables en cada
término
 Forma estándar, los términos pueden
contener uno, dos o más variables
 Suma de productos:
F1 = y’ + zy+ x’yz’
 Producto de sumas:
F2 = x(y’+z)(x’+y+z’+w)
49

Formas estándar (cont.)

 Implementación de dos niveles:

50

25
Formas estándar (cont.)

 Función en forma no estándar:

F3=AB + C(D + E)
F3=AB + CD + CE

51

COMPUERTAS DIGITALES

52

26
MINIMIZACIÓN DE FUNCIONES
LÓGICAS: MAPAS K
 La complejidad de las compuertas,
programa de PLC o lógica cableada
relacionada directamente con la
complejidad de la expresión algebraica
 Minimización algebraica carece de
reglas específicas
 Método del mapa, mapa de Karnaugh o
mapa K, procedimiento sencillo y
directo.

53

MINIMIZACIÓN DE FUNCIONES
LÓGICAS: MAPAS K (cont.)

 Mapa K, procedimiento sencillo y directo

para minimizar funciones lógicas
 Una forma gráfica de la tabla de verdad
 Aplicable si número de variables es < 7
 Un gráfico compuesto de cuadros, cada
cuadro representa un mintérmino
 La función se reconoce por el área de
cuadros cuyos mintérminos están
incluidos en la función
54

27
MINIMIZACIÓN DE FUNCIONES
LÓGICAS: MAPAS K (cont.)

 Función simplificada generada: en una

de las dos formas estándar
 Función más simple: menor número
de términos y menor número de
variables por término
 La expresión simplificada no es única

55

Mapa de dos variables

 Dos variables: 4 mintérminos, mapa
de 4 cuadros

x' = fila 0; x = fila 1

y' = columna 0; y = columna 1 56

28
Mapa de dos variables (cont.)
 Ejemplo:

m1 + m2 + m3 = x’y + xy’ + xy = x + y
57

Mapa de tres variables

 Ocho mintérminos
 Dos cuadros adyacentes difieren en un
bit. Agrupación de 1, 2, 4, 8 cuadros
yz
x

58

29
Mapa de tres variables (cont.)
yz
x

 m5=xy’z: fila 1 columna 01  101b=5d

 4 cuadros con valor 1, 4 cuadros con
valor 0 para cada variable
59

Mapa de tres variables (cont.)

 Utilidad: dos cuadros adyacentes difie-
ren en una sola variable, ej: y - y’
yz
x

m5+m7 = xy’z+xyz = xz(y+y’) = xz 60

30
Mapa de tres variables (cont.)

 Ejemplo: F = S(2, 3, 4, 5)

m2+m3 = x’y
m4+m5 = xy’ 61

Mapa de tres variables (cont.)

 Ejemplo: F = S(3, 4, 6, 7)

m3+m7 = yz
m4+m6 = xz’ 62

31
Mapa de tres variables (cont.)
 Cuatro cuadros adyacentes
yz
x

m0+m2+m4+m6 = x'y'z'+x'yz'+xy'z'+xyz‘
= x'z'(y'+y) + xz'(y'+y)
= x'z' + xz‘ = z'(x'+x)= z' 63

Mapa de tres variables (cont.)

 Ejemplo: F = S(0, 2, 4, 5, 6)

m0+m2+m4+m6 = z’
m4+m5 = xy’ 64

32
Mapa de tres variables (cont.)
 Ejemplo: F = A'C + A'B + AB'C + BC

A’C = m1+m3
A’B = m2+m3
AB’C = m5
BC = m3+m7 65

Mapa de tres variables (cont.)

m1+m3+m5+m7 = C
m2+m3 = A’B
F( A, B, C) = S(1, 2, 3, 5, 7) = C + A’B 66

33
MAPA DE CUATRO VARIABLES
 Mapa con 16 mintérminos, se mantiene
la adyacencia. Combinaciones de 1, 2,
4, 8 y 16 cuadros

67

MAPA DE CUATRO VARIABLES (cont.)

Ejemplo:
F(w,x,y,z) = S(0,1,2,4,5,6,8,9,12,13,14)

m0+m1+m4+m5+
m8+m9+m12+m13 = y’
m0+m2+m4+m6=w’z’
1 m4+m6+m12+m14=xz’
F=y’+w’z’+xz’

68

34
MAPA DE CUATRO VARIABLES (cont.)
 Ejemplo
F = A’B’C’ + B’CD’ + A’BCD’ + AB’C’

m0+m2+m8+m10=B’D’
m0+m1+m8+m9=B’C’
m2+m6=A’CD’
F=B’D’+B’C’+A’CD’

69

IMPLICANTES PRIMOS

 Al escoger cuadros adyacentes, cubrir

todos los mintérminos
 Minimizar el número de términos y
evitar redundantes
 Implicante primo: término de producto
que se obtiene combinando el mayor
número de cuadros adyacentes
 Implicante primo esencial: cuadro
cubierto sólo por un i.p. Un i.p.e. debe
ser incluido 70

35
IMPLICANTES PRIMOS (cont.)
 Ejemplo:
F = S4(0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15)

1 1

71

IMPLICANTES PRIMOS (cont.)

1 1

F = BD + B’D’ + CD + AD
72

36
IMPLICANTES PRIMOS (cont.)

1 1

F = BD + B’D’ + CD + AB’
73

IMPLICANTES PRIMOS (cont.)

1 1

F = BD + B’D’ + B’C + AD
74

37
IMPLICANTES PRIMOS (cont.)

1 1

F = BD + B’D’ + B’C + AB’

75

MAPA DE CINCO VARIABLES

 El uso de mapas para más de cuatro

variables no es sencillo.
 Para 5 variables: 32 cuadros, para 6
variables: 64 cuadros.
 Para muchas variables, muchos
cuadros. Combinar cuadros adyacentes
es muy complicado

76

38
MAPA DE CINCO VARIABLES (cont.)

77

MAPA DE CINCO VARIABLES (cont.)

 Ejemplo:
F = S5(0, 2, 4, 6, 9, 13, 21, 23, 25, 29, 31)

F = A’B’E’ + ACE + BD’E

78

39
SIMPLIFICACIÓN DE PRODUCTO DE
SUMAS
 Ejemplo:
F = S4(0, 1, 2, 5, 8, 9, 10)

F’ = AB + CD + BD’ 79

SIMPLIFICACIÓN DE PRODUCTO DE
SUMAS (cont.)
F’ = AB + CD + BD’
Aplicando el teorema de DeMorgan:
F = (A’ + B’)(C’ + D’)(B’ + D)
Forma de producto de sumas

80

40
CONDICIONES DE INDIFERENCIA

 El valor de una función no está especi-

ficada para ciertas combinaciones de
las variables
 Las condiciones de indiferencia pueden
ser utilizadas en minimización lógica
 Ejemplo:
F = S4(1, 3, 7, 11, 15)
Condiciones de indiferencia:
d = S4(0, 2, 5)
81

CONDICIONES DE INDIFERENCIA
(cont.)

F = yz + w’x’
F = yz + w’z 82

41
CONDICIONES DE INDIFERENCIA
(cont.)
 Una vez que se decide que términos de
indiferencia intervienen en la función,
se incluye a los términos que no
estaban especificados
F = yz + w’x’ = S4(0, 1, 2, 3, 7, 11, 15)
F = yz + w’z = S4(1, 3, 5, 7, 11, 15)
 Cualquiera de las expresiones es
aceptable
 También se usa para el producto de
sumas
83

PREGUNTAS????

84

42