Algebra Booleana

RESUMEN 3er PARCIAL MATEMATICAS PARA LA COMPUTACION.

Algebra booleana.

El término “algebra booleana” se utiliza para describir una diversidad de temas relacionados, que van desde símbolos lógicos y tablas de verdad hasta la aritmética procesada por redes de relevadores eléctricos o computadoras electrónicas. Este capítulo se inicia con el desarrollo de estructuras abstractas llamadas algebras booleanas, empezando a partir de copos y latises. El algebra involucra es una reminiscencia de las tablas de verdad del capítulo. Las funciones de interruptor asociadas con redes electrónicas lógicas dan ejemplos importantes de algebras booleanas y somos capaces de estudiar las redes y sus funciones utilizando las herramientas algebraicas que hemos desarrollado. El capitulo termina con una breve discusión sobre funciones de Karnaugh, una herramienta parecida a los diagramas de Venn, que pueden ser muy útiles para analizar expresiones lógicas relativamente complicadas.

Llamamos a un copo (P, ≤) una latis si todo subconjunto finito tiene mínima cota superior y máxima cota inferior. También introducimos dos operaciones binarias introducimos dos operaciones binarias v y ^ en P donde

Veremos en el teorema 1 que esas operaciones binarias satisfacen las siguientes propiedades:

El teorema 2 nos dira que esas seis propiedades caracterizan a las latises, en el sentido en el que a un conjunto cerrado bajo dos operaciones binarias v y ^ que satisfacen las propiedades puede dársele un orden parcial natural que lo hace una latis. Entonces todo hecho general sobre latises debe ser alguna manera una consecuencia de esas seis propiedades , y siempre que nos encontremos un conjunto con dos operaciones binarias que satisfagan esas condiciones podemos verlo como una latis y concluir inmediatamente que tiene todas las propiedades generales sobre latises. Uno de nuestros objetivos será entonces determinar que es lo que se puede demostrar utilizando únicamente las seis propiedades enlistadas. Llamaremos latis algebraica a cualquier conjunto L con dos operaciones binarias v y ^ que satisfagan estas seis propiedades. Algunas veces escribiremos (L, v, ^) para remarcar nuestro interés en las operaciones v y ^. Leemos x v y como “xunion y” y “x intersección y” para x ^ y.

Consideremos una latis (P, <) y definamos x v y = mcs {x, y } y x ^ y = mci {x, y} entonces (P. v, ^) es una latis algebraica.

Demostración. Las leyes conmutativas son claras. Para examinar la propiedad 2 la consideramos x, y, z E P y sean u = (x v y) vz y V= x v (y v z). como y < u y z<u, el elemento u es una cota superior de {y, z}.

Como y v z es la minima cota superior, tenemos que y v z< u.

También x < x v y < u, asi que u es una cota superior, tenemos que y v z< u.

También x< x v y < u, asi que u es una cota superior de {x, y v z}y por lo tanto x v (y v z) < u.

En otras palabras, V < u. Un razonamiento semejante muestra que u < V y de ahí que u = V.

Para examinar la propiedad 3

La, consideraremos x, y E P. como x < < v w para cualquier w, tenemos que x< < v (x ^ y).

Como x < x y x ^ y < x, el elemento x es una cota superior de {x, x ^ y} y por lo tanto x v (x ^ y) < x.

Entonces x v (x^ y) = x, como deseábamos.

Las propiedades 2Lb y 3Lb tienen demostraciones semejantes.

Antes de demostrar resultados para latises algebraicas, mencionamos un principio de dualidad. Si consideramos una de las seis propiedades que definen a una latis algebraica, y si reemplazamos cada v por ^ y cada ^ por v obtenemos otra de las propiedades, que llamaremos la propiedad dual. Asi 1La y 1Lb son duales una de la otra, etc de esto se sigue que si un teoema o identidad que se cumple para una latis algebraica, esta seguirá siendo verdadera si la dualizamos, esto es, si reemplazamos cada v por ^ y cada ^ por v.

Proposición.

Sea(L, v, ^) una latis algebraica.

a) Las operaciones v y ^ satisfacen las leyes de idempotencia; x v x = x y x^x = x para toda x E L.

b) Para x, y E L tenemos que x v y = y si solo si x ^ y = x.

Demostración.

a) Con y = x v x, la ley de absorción 3La da la identidad x = x v{x ^ (x v x)}. Pero {x ^ (x v x)} = x por la ley de absorción 3Lb, por lo tanto x = x v x. la otra ley de idempotencia se sigue por dualidad.

b) Supongamos que x v y = y. entonces

La otra implicación se sigue por dualidad intercambiando los papeles de x y de y.

Teorema 2.

Sea(L, v, ^) una latis algebraica. Definimos la relación < en L como sigue

X< y si solo si x v y = y

Entonces < es un orden parcial, y (L, <) es una latis en la cual mcs {x, y} = x v y y mci {x, y} = x ^ y para toda x, y E L.

La proporsicion dada mas arriba muestra que podemos definir x < y si solo si x ^ y = x.

Demostración. Verificamos primero si < es un orden parcial. ® como x v x = x por la ley de idempotencia, tenemos que x < x.(AS) supongaos que x < y y y < z, de manera que x v y = y y y v z= z. entonces.

Esto es, x < z como queríamos.

Verifiquemos ahora que mcs{x, y} = x v (x v y) = (x v y) v y = x v y ,

Ladefinicion de < muestra que x < x v y. De manera similar, y < x v y, la definición de < muestra que x < x v y. de manera similar , y < x v y y por lo tanto x v y es una cota superior para {x, y}. para mostrar que x v y es la minima cota superior, consideremos otra cota superior u para { x, y}. entonces x < u y < u, por lo que x v u = y y v u = y en consecuencia

Luego x v y < u. esto muestra que x v y es la mínima cota superior de {x, y}. es decir; x v y = mcs {x, y} un argumento anañpgp (dual) muestra que x ^y = mci {x, y}.

El teorema 1 muestra que si (L, <)es una latis con v y ^ definidas como x v y = mcs{x, y} y x ^ y= mci{x, y} relativos al orden parcial <, entonces (L,v, ^)es una latis algebraica. El teorema 2 dice que si seguimos con la definición de < en L por x < y si solo si x v y = y = y, entonces (L,<) es una latis. ¿es (L, <) la latis con la que empezamos? Esto es, ¿es lo mismo < que < y entonces y = x v y = mcs{x, y} ; por lo tanto x < y. por eso < es el orden parcial < con el que empezamos. Un análisis semejante muestra que si empezamos con una latis algebraica, formamos su copo y después su correspondiente latis algebraica, obtenemos la latis algebraica original.

Consideremos cualquier conjunto S y sea p(s)el conjunto de todos los conjuntos de S. con las operaciones U y n, p(S) es una latis algebraica. Motivados por el teorema 2 definimos para A y B en P (S).

A

...