Download Tema 2 Teoría de la conmutación. Álgebra de Boole • Álgebra de

Tema 2
Teoría de la conmutación. Álgebra de Boole
• Álgebra de Boole
Definiciones y axiomas
Propiedades
• Variables y funciones booleanas
Definiciones
Propiedades
Formas de representación
Funciones booleanas y circuitos combiancionales
• Puertas lógicas
Puertas lógicas fundamentales
Puertas lógicas derivadas
Sist. Electrónicos Digitales
1
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Álgebra de Boole
Sist. Electrónicos Digitales
2
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Definición de Álgebra de Boole
Un conjunto es un álgebra de Boole se verifica:
a) Es un conjunto finito B con al menos dos elementos, N (elemento nulo), U
(elemento universal), y tres operaciones: dos binarias y una unaria
( B, *, +, )
N ∈ B
U ∈ B
b) Cumple los 6 axiomas de HUNTINGTON
Sist. Electrónicos Digitales
3
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Axiomas de HUNTINGTON
1.
Las operaciones *, + ,⎯ , deben ser cerradas
⎧ x*y ∈ B
⎪
∀x,y ∈ B ⎨ x + y ∈ B
⎪ x ∈B
⎩
2.
Operaciones con N,U
x*N=N
x*U=x
3.
x+N=x
x+U=U
Conmutatividad
x*y=y*x
x+y=y+x
Sist. Electrónicos Digitales
4
J.F. Martín
Tema 2
4.
Teoría de la conmutación. Álgebra de Boole
Distributiva.
x * (y + z) = (x * y) + (x * z )
x + (y * z) = (x + y) * (x + z)
5.
Complementatividad.
⎧x * x = N
∀x ∈ B,∃ x ∈ B / ⎨
⎩x + x = U
6.
Hay por lo menos dos elementos distintos en B.
Sist. Electrónicos Digitales
5
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Propiedades del Álgebra de Boole
1.
Propiedad de Idempotencia
x*x=x
x+x=x
2.
Propiedad Asociativa
x*(y*z)=(x*y)*z
x+(y+z)=(x+y)+z
Sist. Electrónicos Digitales
6
J.F. Martín
Tema 2
3.
Teoría de la conmutación. Álgebra de Boole
Propiedad de Absorción
x+(x*y)=x
x*(x+y)=x
4.
Ley del consenso
x+(x*y)=x+y
x*(x+y)=x*y
5.
Ley de involución
(x) = x
Sist. Electrónicos Digitales
7
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Se puede demostrar que B={0,1}, N=0, U=1, junto con las operaciones * , + ,⎯ ,
definidas por las siguientes tablas de verdad, forman un álgebra de boole.
+
0
1
*
0
1
⎯
0
0
1
0
0
0
0 1
1
1
1
1
0
1
1 0
OR
Sist. Electrónicos Digitales
AND
8
NOT
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Variables y funciones booleanas
Sist. Electrónicos Digitales
9
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Definiciones
Definimos constante sobre B, a todo elemento de B
Definimos variable de B, todo símbolo x que representa a cualquier elemento de B
Definimos literal de B, a toda constante ó variable
Definimos función booleana a la aplicación:
f : Bn → B
donde: Bn = B × B × .... × B / x = (x1,x 2 , .... ,x n ) ∈ Bn
Sist. Electrónicos Digitales
10
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Definimos función constante a la función fa :
fa : Bn → B / ∀ (x1,x 2 , .... ,xn ) ∈ Bn , fa (x1,x 2 , .... ,xn ) = a ∈ B
Definimos función proyección fp :
fp : Bn → B / ∀ (x1,x 2 , .... ,xn ) ∈ Bn , fp (x1,x 2 , .... ,xn ) = xi
donde xi es una variable de B
Definimos función degenerada a la función fd:
fd : Bn → B / ∀ x,z ∈ Bn , fd (x) = fd (z)
Definimos función parcialmente especificada a la aplicación:
fd : Bn → B3
Sist. Electrónicos Digitales
donde B3 = {0,1,#}
11
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Definimos término producto a todo literal o producto de literales, en los que cada
variable aparece como máximo una vez.
Definimos mintérmino o producto canónico al término producto de una función, que
está formado por las n variables de dicha función, apareciendo éstas una sola vez de
forma complementada o sin complementar.
Definimos forma normal disyuntiva de una función, a su representación algebraica,
que consta de un sólo término producto o de la suma de varios de ellos.
Definimos término suma a todo literal o suma lógica de literales, en las que cada
variable aparece como máximo una vez.
Definimos maxtérmino o suma canónica al término suma de una función, que está
formado por las n variables de dicha función, apareciendo éstas una sola vez de
forma complementada o sin complementar.
Definimos forma normal conjuntiva de una función, a su representación algebraica,
que consta de un sólo término suma o del producto de varios de ellos.
Sist. Electrónicos Digitales
12
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Para n variables podemos formar 2n mintérminos y 2n maxtérminos.
Notación para mintérminos y maxtérminos:
x1 * x 2 * .... * xn-1 * xn = m0
x1 * x 2 * .... * xn-1 * xn = m1
x1 * x 2 * .... * xn-1 * xn = m2
x1 + x 2 + .... + xn-1 + xn = M0
x1 + x 2 + .... + xn-1 + xn = M1
x1 + x 2 + .... + xn-1 + xn = M2
x1 * x 2 * .... * xn-1 * xn = m3
............................
x1 * x 2 * .... * xn-1 * xn = m2n −1
x1 + x 2 + .... + xn-1 + xn = M3
............................
x1 + x 2 + .... + xn-1 + xn = M2n −1
Definimos vector asociado a un mintérmino mi de n variables, al obtenido colocando 1
en las posiciones correspondientes a las variables NO complementadas, y colocando
0 en las posiciones correspondientes a las variables complementadas.
Ejp:
m = x * x * x * x → 0101
5
1
2
3
4
Definimos vector asociado a un maxtérmino Mi de n variables, al obtenido colocando
0 en las posiciones correspondientes a las variables NO complementadas, y
colocando 1 en las posiciones correspondientes a las variables complementadas.
Ejp:
M = x + x + x + x → 1010
10
Sist. Electrónicos Digitales
1
2
3
13
4
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Propiedades
Dadas las funciones booleanas, f, g, las siguientes funciones f*g, f+g, g , también son
booleanas.
f*g(x) = f(x) * g(x) ∀x = (x1,x 2 , .... ,xn ) ∈ Bn
f+g(x) = f(x) + g(x) ∀x = (x1,x 2 , .... ,xn ) ∈ Bn
g(x) = g(x)
∀x = (x1,x 2 , .... ,x n ) ∈ Bn
Teorema de Dualidad.
Si a una identidad o teorema de conmutación se sustituyen {+,*,0,1} por
{*,+,1,0} respectivamente, se obtiene otra identidad o teorema dual al original.
Teorema de DeMORGAN.
x1 + x 2 + .... + x n = x1 * x 2 * .... * xn
x1 * x 2 * .... * xn = x1 + x 2 + .... + xn
Sist. Electrónicos Digitales
14
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Teorema de SHANON (Teorema generalizado de DeMorgan).
f(x1,x 2 , .... , x n ,*,+,0,1) = f(x1,x 2 , .... , xn ,+,*,1,0)
Teorema de los mintérminos para n variables.
2n −1
∑ m (x ,x , .... ,x
i=0
i
1
2
n
) =1
Teorema de los maxtérminos para n variables.
2n −1
∏ M (x ,x , .... ,x
i=0
Sist. Electrónicos Digitales
i
1
2
15
n
)=0
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Teorema del desarrollo de Shanon, para mintérminos, para una función f(x) = f(x1,x2,
.... ,xn), de n variables.
f(x) =
=
[(x1 * x2
* ....* xn ) * f(0,0, ... ,0)] + [(x1 * x 2 * ....* xn ) * f(0,0, ... ,1)] +
+ ............................................ + [(x1 * x 2 * ....* xn ) * f(1,1, ... ,1)] =
[m0
* f(0,0, ... ,0)] + [m1 * f(0,0, ... ,1)] + ......... + ⎡⎣m2n -1 * f(1,1, ... ,1)⎤⎦
Teorema del desarrollo de Shanon, para maxtérminos, para una función f(x) = f(x1,x2,
.... ,xn), de n variables.
f(x) =
=
[(x1 + x 2 +
.... + xn ) + f(0,0, ... ,0)] * [(x1 + x 2 + .... + xn ) + f(0,0, ... ,1)] *
* ............................................ * [(x1 + x2 + .... + xn ) + f(1,1, ... ,1)] =
[M0 + f(0,0, ... ,0)] * [M1 + f(0,0, ... ,1)] *
Sist. Electrónicos Digitales
16
......... * ⎡⎣M2n -1 + f(1,1, ... ,1)⎤⎦
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Como consecuencia del teorema del desarrollo de Shanon para mintérminos,
tenemos que toda función f(x), admite una representación, que denominaremos
forma canónica disyuntiva, formada por la suma de los mintérminos cuyos vectores
asociados VK verifican que f(VK)=1.
f(x) = ∑ mk
donde f(Vk ) = 1
Como consecuencia del teorema del desarrollo de Shanon para maxtérminos,
tenemos que toda función f(x), admite una representación, que denominaremos
forma canónica conjuntiva, formada por el producto de los maxtérminos cuyos
vectores asociados VK verifican que f(VK)=0.
f(x) = ∏ Mk
Sist. Electrónicos Digitales
donde f(Vk ) = 0
17
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Teorema para obtener la función complementada de una dada en forma canónica
disyuntiva.
Dada una función g(x), expresada en forma canónica disyuntiva, su función
complementada g(x) , estará dada por la suma de los mintérminos que no
aparecen en g(x).
Teorema para obtener la función complementada de una dada en forma canónica
conjuntiva.
Dada una función g(x), expresada en forma canónica conjuntiva, su función
complementada g(x), estará dada por el producto de los maxtérminos, que no
aparecen en g(x).
Sist. Electrónicos Digitales
18
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Formas de representación
a) Esquemas de Circuitos
Un circuito electrónico, descrito a nivel de dispositivos, puede ser considerado
como una forma de representar a la función booleana que implementa
b) Diagrama de puertas lógicas
Consiste en representar una función, mediante su implementación utilizando
puertas lógicas
c) Expresión algebraica
Permite una representación más compacta, pero la información se presenta
más oculta
Sist. Electrónicos Digitales
19
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
d) Métodos de enumeración
d.1)Tabla de verdad.
Listado que de forma explícita representa el
resultado de la función, para cada una y todas las
combinaciones de las entradas
d.2) Vector de valores.
Vector formado por el resultado de la función, en el
orden creciente de las combinaciones en las
variables de entrada
d.3) Mintérminos.
La función en forma canónica disyuntiva
d.4) Maxtérminos.
La función en forma canónica conjuntiva
e) Mapas de Karnaugh
Es una representación gráfica de la tabla de verdad mediante una matriz
bidimensional, donde cada posible combinación de los valores binarios de las
variables de entrada, está representada por una celda ó casilla. Las entradas
están ordenadas en código Gray, de forma que dos casillas adyacentes
(horizontal ó verticalmente), sólo tienen distinto valor en una de las entradas
Sist. Electrónicos Digitales
20
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Mapas de Karnaugh de 3 variables y de 4 variables
x1,x2
x3
00
01
11
x1,x2
x3,x4
10
00
01
11
10
0
0
2
6
4
00
0
4
12
8
1
1
3
7
5
01
1
5
13
9
11
3
7
15
11
10
2
6
14
10
Sist. Electrónicos Digitales
21
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Mapa de Karnaugh de 5 variables
x2,x3
x4,x5
00
01
11
x2,x3
x4,x5
10
00
01
11
10
00
0
4
12
8
00
16
20
28
24
01
1
5
13
9
01
17
21
29
25
11
3
7
15
11
11
19
23
31
27
10
2
6
14
10
10
18
22
30
26
x1 = 0
Sist. Electrónicos Digitales
x1 = 1
22
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Mapa de Karnaugh de 6 variables
x3,x4
x5,x6
00
01
00
0
01
1
11
3
10
2
11
4
5
7
6
10
12
8
13
15
14
x3,x4
x5,x6
9
11
10
x1x2= 00
x3,x4
x5,x6
00
01
00
01
11
10
00
16
20
28
24
01
17
21
29
25
11
19
23
31
27
10
18
22
30
26
x1x2= 01
11
x3,x4
x5,x6
10
00
01
11
10
00
32
36
44
40
00
48
52
60
56
01
33
37
45
41
01
49
53
61
57
11
35
39
47
43
11
51
55
63
59
10
34
38
46
42
10
50
54
62
58
x1x2= 10
Sist. Electrónicos Digitales
x1x2= 11
23
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Funciones booleanas y circuitos combinacionales
x1
x2
z1
z2
xm
zn
Para implementar un circuito digital combinacional de m entradas y n salidas, será
necesario implementar n funciones booleanas cada una de ellas dependiente de m
variables.
f1(x1 , x 2 , ..... , xm )
f2 (x1 , x 2 , ..... , xm )
.................
fn (x1 , x 2 , ..... , xm )
Sist. Electrónicos Digitales
24
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Puertas lógicas
Sist. Electrónicos Digitales
25
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Puertas lógicas fundamentales
NOT
x
z
NOT
z=x
AND
x
z
z=xy
y
OR
x
z
z=x+y
y
Sist. Electrónicos Digitales
26
0
1
1
0
AND
0
1
0
0
0
1
0
1
OR
0
1
0
0
1
1
1
1
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
• Puertas lógicas derivadas
XOR
x
z=x ⊕ y=xy+xy
z
y
NAND
x
z
z= xy
y
NOR
x
z
y
z= x+y
XNOR
x
z
y
Sist. Electrónicos Digitales
z= x ⊕ y
27
XOR
0
1
0
0
1
1
1
0
NAND
0
1
0
1
1
1
1
0
NOR
0
1
0
1
0
1
0
0
XNOR
0
1
0
1
0
1
0
1
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Ejemplo de función booleana
Sist. Electrónicos Digitales
28
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Diagrama de circuitos
vx3
vx1
vx4
vz
vx2
Sist. Electrónicos Digitales
29
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Diagrama de puertas lógicas
Sist. Electrónicos Digitales
30
J.F. Martín
Tema 2
Expresión algebraica
Tabla de verdad
Sist. Electrónicos Digitales
Teoría de la conmutación. Álgebra de Boole
f(x1, x 2 , x 3 , x 4 ) = (x1 * x 2 ) + (x 3 * x 4 )
x1 x2 x3 x4
z
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
1
1
1
0
1
1
1
0
1
1
1
0
0
0
0
0
31
J.F. Martín
Tema 2
Teoría de la conmutación. Álgebra de Boole
Vector de salida
f(x1,x2,x3,x4) = (1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,0)
Forma canónica disjuntiva
f(x1,x 2 ,x 3 ,x 4 ) =
∑ m(0,1,2,4,5,6,8,9,10)
Forma canónica conjuntiva
f(x1,x 2 ,x 3 ,x 4 ) =
∏ M(3,7,11,12,13,14,15)
Mapa de Karnaugh.
Sist. Electrónicos Digitales
x1,x2
x3,x4
00
01
11
10
00
1
1
0
1
01
1
1
0
1
11
0
0
0
0
10
1
1
0
1
32
J.F. Martín