Algebra De Boole

Fundamentos de los Computadores. Álgebra de Boole. 1

3. ÁLGEBRA DE BOOLE

ü Un sistema de elementos B y dos operaciones binarias cerradas (· ) y (+) se

denomina ALGEBRA de BOOLE siempre y cuando se cumplan las

siguientes propiedades:

1.- Propiedad conmutativa:

A + B = B + A

A · B = B · A

2. Propiedad distributiva:

A· (B+C) = A· B + A· C

A + B· C = (A+B)· (A+C)

3. Elementos neutros diferentes

A + 0 = A

A · 1 = A

4. Siempre existe el complemento de A, denominado A’

A + A’ = 1

A · A’ = 0

ü PRINCIPIO DE DUALIDAD: cualquier teorema o identidad algebraica

deducible de los postulados anteriores puede transformarse en un segundo

teorema o identidad válida sin mas que intercambiar (+) por (· ) y 1 por 0.

ü CONSTANTE: cualquier elemento del conjunto B

ü VARIABLE: símbolo que representa un elemento arbitrario del álgebra, ya

sea constante o fórmula completa.

TEOREMAS:

Teorema 1: el elemento complemento A’ es único.

Teorema de los elementos nulos: para cada elemento de B se verifica:

A+1 = 1

A· 0 = 0

Teorema 3: cada elemento identidad es el complemento del otro.

0’=1

1’=0

Fundamentos de los Computadores. Álgebra de Boole. 2

Teorema de idempotencia: para cada elemento de B, se verifica:

A+A=A

A· A=A

Teorema de involución: para cada elemento de B, se verifica:

(A’)’ = A

Teorema de absorción: para cada par de elementos de B, se verifica:

A+A· B=A

A· (A+B)=A

Teorema 7: para cada par de elementos de B, se verifica:

A + A’· B = A + B

A · (A’ + B) = A · B

LEYES DE DEMORGAN: para cada par de elementos de B, se verifica:

(A+B)’ = A’· B’

(A· B)’ = A’ + B’

Teorema de asociatividad: cada uno de los operadores binarios (+) y (· ) cumple

la propiedad asociativa:

A+(B+C) = (A+B)+C

A· (B· C) = (A· B)· C

ÁLGEBRA DE CONMUTACIÓN

UN ÁLGEBRA DE BOOLE ES UN SISTEMA DE ELEMENTOS B={0,1} Y

LOS OPERADORES DEFINIDOS DE LA SIGUIENTE FORMA

A B A+B A· B A A’

0 0 0 0 0 1

0 1 1 0 1 0

1 0 1 0

1 1 1 1

OPERADOR + à OPERADOR OR

OPERADOR · à OPERADOR AND

OPERADOR ‘ à OPERADOR NOT

Fundamentos de los Computadores. Álgebra de Boole. 3

FUNCIONES EN EL ÁLGEBRA DE BOOLE

Función completa es una función que se encuentra definida para todas las

combinaciones de las variables de entrada.

Tabla de VERDAD: forma de representación de funciones, dando el valor de la

función para cada combinación de entrada.

X1 X2 X3 F(X1, X2, X3)

0 0 0 F(0,0,0)

0 0 1 F(0,0,1)

0 1 0 F(0,1,0)

0 1 1 F(0,1,1)

1 0 0 F(1,0,0)

1 0 1 F(1,0,1)

1 1 0 F(1,1,0)

1 1 1 F(1,1,1)

Fórmulas de conmutación: expresión de una función

ü 1 y 0 son fórmulas

ü Xi es una fórmula si pertenece a {0,1}

ü Si A es una fórmula, A’ también lo es

ü Si A y B son fórmulas, A+B y A· B también lo son

ü Nada más es una fórmula, a menos que sigan los puntos anteriores un

número finito de pasos.

Cada fórmula describe una única función.

Dos fórmulas son equivalentes (A=B) si expresan la misma función de

conmutación.

Ø Un LITERAL es una variable A o complemento de una variable A’

Ø Un TÉRMINO PRODUCTO es una operación AND de un número de

literales.

Ø Una fórmula normal disyuntiva es una suma de términos productos.

Ø Un TÉRMINO SUMA es una operación OR de un número de literales.

Ø Una fórmula normal conjuntiva es un producto de términos sumas.

Fundamentos de los Computadores. Álgebra de Boole. 4

EXPRTESIÓN EN SUMA DE PRODUCTOS

Ø MINTÉRMINO (mi): término producto en el que aparecen todas las

variables, ya sean complementadas o sin complementar.

Ø Fórmula Canónica Disyuntiva o de Mintérminos: suma de mintérminos.

Dada la lista completa de mintérminos y asignando 1’s y 0’s

arbitrariamente a las variables, siempre hay un, y sólo un, mintérmino que

toma el valor 1.

Un mintérmino es un término producto que es 1 exactamente en una línea

de la tabla de Verdad.

La fórmula compuesta por todos los mintérminos será idénticamente 1.

Cada fórmula de conmutación puede expresarse como suma de

mintérminos. Y esa fórmula es única.

NOTACIÓN: Un mintérmino se designa por “mi” siendo i el número

decimal correspondiente de la tabla de verdad. El 0 se asocia a la variable

complementada y el 1 a la variable sin complementar.

EJEMPLO:

X Y Z F(X,Y,Z)

0 0 0 1

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

F(X,Y,Z) = X’· Y’· Z’ + X’· Y· Z’ + X’· Y· Z + X· Y· Z

F(X,Y,Z) = m0 + m2 + m3 +m7 = S m(0,2,3,7)

Fundamentos de los Computadores. Álgebra de Boole. 5

EXPRESIÓN EN PRODUCTO DE SUMAS

Ø MAXTÉRMINO (Mi): término suma en el que aparecen todas las variables,

ya sean complementadas o sin complementar.

Ø Fórmula Canónica Conjuntiva o de Maxtérminos: producto de

...