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