39

x9 Intermedio: Propiedades de las algebras booleanas

En este segundo apartado \algebraico" se estudian algunas propiedades ele-

mentales de las algebras booleanas. En el apartado precedente se denio esta

estructura como un retculo distributivo complementado.

Armacion 9.1. En un algebra booleana, cada elemento tiene un unico

complemento.

Demostracion. Sean c1 y c2 complementos de un mismo elemento a en un

algebra booleana. Como el retculo es distributivo se tiene lo siguiente.

c1 = c1 ^ 1 = c1 ^ (a _ c2) = (c1 ^ a) _ (c1 ^ c2) = 0 _ (c1 ^ c2) = c1 ^ c2

De manera simetrica se obtiene c2 = c2 ^ c1, luego c1 = c2.

En adelante, el complemento de un elemento a de un algebra booleana se de-

nota a0. Tambien, en adelante el algebra booleana cuyo conjunto subyacente

es B se denota B, con negrilla.

Ejemplo 9.2. Si X es un conjunto cualquiera, el conjunto de partes P(X)con la relacion de contenencia es un algebra booleana.

Ejemplo 9.3. El conjunto f0; 1g con 0 < 1 es un algebra booleana, quede aqu en adelante se denotara 2. En realidad es un caso particular del

anterior, pues este conjunto ordenado es isomorfo al conjunto de partes de

un conjunto con un solo elemento. En este caso, las operaciones tambien se

pueden presentar mediante tablas.

a a0

1 0

0 1

a b a ^ b a _ b1 1 1 1

1 0 0 1

0 1 0 1

0 0 0 0

40

Ejemplo 9.4. Si X es un conjunto innito entonces Pfc(X) denota el con-junto de partes nitas y conitas de X, esto es, F 2 Pfc(X) si F X conF nito o bien F c nito. El conjunto Pfc(X) con la relacion de contenenciaes un algebra booleana. En realidad, se trata de una subalgebra de P(X).

Armacion 9.5. Si B un algebra booleana entonces para cada a; b 2 B setiene lo siguiente.

1. a00 = a

2. (a _ b)0 = a0 ^ b0

3. (a ^ b)0 = a0 _ b0

4. a b si y solo si a0 _ b = 1

Las igualdades (2 ) y (3 ) se conocen como las leyes de De Morgan.

Demostracion.

1. Basta observar que, por denicion,

a0 ^ a = 0 a0 _ a = 1

luego a es un complemento de a0, al igual que a00. Por la armacion 9.1 se

obtiene a = a00.

2. Para demostrar la primera ley de De Morgan se tiene

(a _ b) ^ (a0 ^ b0) = [a ^ (a0 ^ b0)] _ [b ^ (a0 ^ b0)]= (0 ^ b0) _ (0 ^ a0) = 0 _ 0 = 0

y por otro lado

(a _ b) _ (a0 ^ b0) = [(a _ b) _ a0] ^ [(a _ b) _ b0]= (b _ 1) ^ (a _ 1) = 1 ^ 1 = 1

41

luego por el caracter unico del complemento se tiene a0 ^ b0 = (a _ b)0.3. Esta ley de De Morgan se prueba de manera simetrica a la anterior.

4. Si a b entonces a0_ b a0_a = 1 luego a0_ b = 1. Al reves, si a0_ b = 1entonces a = a^ 1 = a^ (a0 _ b) = (a^ a0)_ (a^ b) = 0_ (a^ b) = a^ b perosiempre a ^ b b y as, en este caso, a b.

El hecho siguiente es comun a muchas estructuras algebraicas.

Armacion 9.6. Sea B un algebra booleana. Para cualquier conjunto X,

el conjunto de las funciones de X en B, denotado

BX = ff : X ! B f es funciong;tambien es un algebra booleana.

Demostracion. Se dene la relacion entre funciones como sigue: f gsi f(x) g(x) para cada x 2 X. Se verica (ejercicio 9.7) que esta es unarelacion de orden; que cada par de funciones f , g tiene mci f^g denida como(f ^ g)(x) = f(x)^ g(x) y mcs f _ g denida como (f _ g)(x) = f(x)_ g(x);que este retculo es distributivo; que el maximo es la funcion constante 1 y

el mnimo la funcion constante 0; que el complemento de la funcion f esta

denida como f 0(x) =f(x)

0para cada x 2 X.

Ahora se puede dar otra representacion al algebra de partes.

Armacion 9.7. Sea X cualquier conjunto. El algebra booleana P(X) delos subconjuntos de X (ejemplo 9.2) y el algebra booleana de funciones 2X

(ejemplo 9.3, armacion 9.6) son isomorfas, lo cual se simboliza

P(X) = 2X :

Como siempre en Matematicas, \isomorfas" signica que entre ellas existe

una funcion biyectiva que preserva toda la estructura.

42

Demostracion. La funcion : P(X) ! 2X asigna a cada subconjunto sufuncion caracterstica, esto es, para S X la funcion S : X ! f0; 1g sedene como sigue.

S(x) =

8