Download TEMA III - BUCOMSEC

Informática Básica
Tema III: Algebra de Boole. Simplificación
y diseño lógico
TEMA III
1. ÁLGEBRA DE BOOLE.
1.1 Definición y Postulados (axiomas).
1.2 Teoremas básicos.
2. PUERTAS LÓGICAS DIGITALES.
3. FUNCIONES LÓGICAS.
3.1 Definición.
3.2 Complemento de una función. Teoremas de De Morgan.
3.3 Forma canónica (o estándar).
3.4 Equivalencia entre formas de representación.
3.5 Tablas de verdad.
4. SIMPLIFICACIÓN DE FUNCIONES LÓGICAS.
4.1 Utilización del Álgebra de Boole.
4.2 Minimización mediate Tablas (o Mapas) de Karnaugh.
4.3 Funciones incompletamente especificadas. Indiferencias.
5. IMPLEMENTACIÓN DE FUNCIONES CON PUERTAS NAND Y NOR.
Bibliografía:
•Fundamentos de Sistemas Digitales. T.L. Floyd. Prentice Hall 2000
•Diseño Digital. Principios y Prácticas. J.F. Wakerly. Prentice Hall 1992
•Sistemas Electrónicos Digitales. E. Mandado. Marcombo 1998.
•Analisis y Diseño de Circuitos Lógicos Digitales. V.P. Nelson. Prentice Hall 1996
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
1
ALGEBRA DE BOOLE. DEFINICIÓN Y POSTULADOS
Es un conjunto de elementos que pueden tomar dos valores
perfectamente diferenciados (que representaremos con 0 y 1)
relacionados por los operadores + (suma lógica) y · (producto lógico), que
cumplen los siguientes axiomas:
TEMA III
1. Ambas operaciones son conmutativas:
a+b=b+a
a ·b = b · a
2. Existen dos elementos neutros, uno por operación:
0+a=a
a·1=a
3. Cada operación es distributiva respecto a la otra:
a·(b+c) = (a·b) + (a·c)
a+(b·c) = (a+b)·(a+c)
4. Para todo elemento a existe un elemento complementario a , que
cumple:
a + a =1
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
a ⋅a = 0
2
ALGEBRA DE BOOLE. TEOREMAS BÁSICOS
1)Principio de dualidad.
Cada identidad deducida de los anteriores postulados
permanece válida si las operaciones + y · y los elementos 0 y 1 se
intercambian entre si.
2)
TEMA III
a + 1 = 1
∀a ∈ B
a ⋅ 0 = 0
2) Idempotencia:
a + a = a
∀a ∈ B
a ⋅a = a 
3) Ley de Absorción:
a + a ⋅ b = a
∀a , b ∈ B
a ⋅ (a + b ) = a 
4) Involución:
a =a
∀a ∈ B
5) Asociatividad:
a + ( b + c) = (a + b ) + c 
∀a , b, c ∈ B
a ⋅ ( b ⋅ c) = (a ⋅ b ) ⋅ c

6) Teoremas de De Morgan:
a + b = a ⋅ b 
∀a , b ∈ B
a ⋅ b = a + b 
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
3
PUERTAS LÓGICAS DIGITALES
INVERSOR:
TEMA III
a
0
1
PUERTA AND:
a
0
0
1
1
PUERTA OR:
a
0
0
1
1
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
f
1
0
b
0
1
0
1
b
0
1
0
1
f
0
0
0
1
f
0
1
1
1
4
PUERTAS LÓGICAS DIGITALES
TEMA III
PUERTA NAND:
a
0
0
1
1
b
0
1
0
1
f
1
1
1
0
a
0
0
1
1
b
0
1
0
1
f
1
0
0
0
a
0
0
1
1
b
0
1
0
1
f
0
1
1
0
PUERTA NOR:
PUERTA OR EXCLUSIVA (EXOR):
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
5
FUNCIONES LÓGICAS. DEFINICIÓN
Una función lógica es un conjunto de variables relacionadas
entre si por las operaciones básicas definidas:
f = f (a , b, c,...)
f1 (a , b, c) = abc + ab c + abc + abc
TEMA III
f 2 (a , b, c, d) = a + bc + a ( b + d)(c + d )
Toda función booleana se comporta como una variable del
sistema.
Teorema de De Morgan generalizado
El complemento de una función se obtiene complementando
todas las variables que intervengan e intercambiando las
operaciones suma y producto:
f (A, B, C,...,+,⋅) = f ( A, B, C ,...,⋅,+ )
por ejemplo, desarrollemos la función:
f (A, B, C, D, E ) = [(A + C) D + BE](D + E )
f (A, B, C, D, E) = [(A + C) D + BE](D + E ) = ( A C + D)( B + E ) + D E
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
6
Forma canónica (o estándar)
Se llama término canónico de una función lógica a todo producto
o suma en la cual aparecen todas las variables que forman parte de
la función, bien sea en su forma directa o inversa.
f (a , b, c) = abc + ab c + ac + bc
abc y ab c son productos canónicos.
TEMA III
f (a , b, c, d ) = (a + b + c )(a + b + c + d )(a + c + d )(a + b + c + d )
(a + b + c + d ) y ( a + b + c + d )
son sumas canónicas
Las expresiones en forma canónica suelen expresarse a través de
su equivalente numérico.
f (a , b, c) = ab c + ab c + ab c + abc
ab c = 000 2 = 010
ab c = 010 2 = 210
ab c = 100 2 = 410
abc = 1112 = 710
f (a , b, c) = ab c + ab c + ab c + abc = ∑ (0,2,4,7)
3
De la misma forma:
f (a , b, c, d ) = (a + b + c + d)(a + b + c + d )(a + b + c + d )(a + b + c + d ) =
= ∏ (13,9,14,0)
4
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
7
Equivalencia entre formas de representación
Toda función del álgebra de Boole se puede expresar de la forma:
f (a , b, c,...) = a ⋅ f (1, b, c,...) + a ⋅ f (0, b, c,...)
TEMA III
f (a , b, c,...) = [a + f (0, b, c,...)] ⋅ [a + f (1, b, c,...)]
Si desarrollamos la primera expresión obtendremos que podemos
expresar la función como la suma de todos los productos canónicos
afectados por un coeficiente igual al valor que toma la función al
sustituir cada variable por 1 ó 0 según el producto canónico figure
de forma directa o inversa respectivamente:
f (a , b, c,...) = abc... ⋅ f (1,1,1,...) + ab c... ⋅ f (0,0,0,...)
[1]
Repitiendo el proceso para la segunda expresión obtendremos:
f (a , b, c,...) = [a + b + c + ... + f (0,0,0,...)] ⋅ [a + b + c + ... + f (1,1,1,...)]
[2]
De la expresión [1] se deduce que toda función se puede representar
mediante la suma de todos los productos canónicos multiplicados
por un coeficiente igual a 1 si el término forma parte de la función e
igual a 0 si no forma parte de ella.
De la expresión [2] se deduce que la expresión canónica de sumas
canónicas de una función es igual al producto de todas las sumas
canónicas posibles, sumando a cada una de ellas un coeficiente igual
a 0 si el término forma parte de la función e igual a 1 si no forma
parte de ella.
Utilizando la notación numérica para expresar los términos
canónicos, ambas ecuaciones [1] y [2] se pueden expresar de la
forma siguiente:
2 n −1
2 n −1
i =0
i =0
f (a , b, c,...) = ∑ f (i)i = ∏ f (2 n − 1 − i) + i
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
8
TEMA III
Tablas de Verdad
La tabla de verdad de una función lógica es una forma de
representación de la misma, en la que se indica el valor 0 ó 1 que
toma la función para cada una de las combinaciones posibles de las
variables de las cuales depende expresadas en forma de suma de
productos.
abc
000
001
010
011
100
101
110
111
f
0
1
0
1
1
0
0
1
f = abc + abc + ab c + abc
f = ∑ (1,3,4,7)
3
f = ∏ (1,2,5,7)
3
SIMPLIFICACIÓN DE FUNCIONES
Mediante el Álgebra de Boole
Se basa en la utilización sistemática de los postulados o axiomas, y
teoremas y leyes ya comentadas. A partir de la expresión canónica,
básicamente se apoya en la propiedad:
abc + ... + abc = bc + ...
(a + b + c)(a + b + c)... = (b + c)...
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
9
Simplificación mediante Tablas (o Mapas) de Karnaugh
Se basa en sistematizar la aplicación del método algebraico ya
descrito mediante la construcción de tablas
De 3 variables:
bc
a
TEMA III
0
1
De 4 Variables:
cd
ab
00
01
11
10
00
01
11
10
0
1
3
2
4
5
7
6
00
01
11
10
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
De 5 Variables:
cde
ab
00
01
11
10
000
001
011
010 110
111
101
100
0
1
3
2
6
7
5
4
8
9
11
10
14
15
13
12
24
25
27
26
30
31
29
28
16
17
19
18
22
23
21
20
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
10
Simplificación mediante Tablas de Karnaugh. Ejemplos
f = ∑ (0,2,3,4,6,7,8,10)
4
cd
00
01
11
10
00
1
0
1
1
01
1
0
1
1
11
0
0
0
0
10
1
0
0
1
TEMA III
ab
ad
ac
bd
f = a d + b d + ac
(c + d )
cd
00
01
11
10
00
1
0
1
1
01
1
0
1
1
11
0
0
0
0
10
1
0
0
1
ab
(a + b )
(a + d )
f = (a + d )(a + b )(c + d )
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
11
Simplificación mediante Tablas de Karnaugh. Ejemplos
f = ∑ (0,2,4,6,9,13,16,18,20,22,26,29,30,31)
5
cde
TEMA III
ab
00
000
001
011
010 110
1
0
0
1
1
111
101
100
0
0
1
01
0
1
0
0
0
0
1
0
11
0
0
0
1
1
1
1
0
10
1
0
0
1
1
0
0
1
be
ab d e
abce
ad e
f = (abde + abce + b e + ade )
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
12
TEMA III
Funciones incompletas
Son aquellas que no tienen un valor definido para todas las posibles
combinaciones de las variables de las que dependen
abc f
000 0
001 X
010 X
011 1
100 1
101 0
110 X
111 0
f = ∑ (3,4) + ∑ (1,2,6)
∅
3
bc
00
01
11
10
0
0
X
1
X
1
1
0
0
X
a
f = ab + a c
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
13
Implementación de funciones con puertas NAND y NOR
La puerta NAND como elemento universal
Inversor
TEMA III
a
a
a
a
≡
Puerta AND
a
b
a·b
a
b
≡
a ⋅b
a·b
Puerta OR
≡
a
b
a+b
a
a
b
b
a+b
≡
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
14
Implementación de funciones con puertas NAND y NOR
La puerta NOR como elemento universal
Inversor
TEMA III
a
a
a
a
≡
Puerta OR
a
b
a
b
a+b
a+b
a+b
Puerta AND
≡
a
b
a·b
a
a
b
b
a·b
≡
Tema III. Algebra de
Boole. Simplificación y
Diseño Lógico
15