Algebra de boole

1

Relaciones de orden

Sea R una relaci´n binaria en un conjunto A. Si R satisface las o propiedades reflexiva, antisim´trica y transitiva se dice que R es e una relaci´n de orden. En este caso si a y b son elementos de o A tales que aRb, lo denotaremos por a ≤ b.

Si ≤ verifica la propiedad de que dados a y b en A, entonces a ≤ b o b ≤ a, entonces la relaci´n ≤ se denomina de orden o total.Sean A y B dos conjuntos tales que B ⊆ A y ≤ una relaci´n o de orden en A. Podemos entonces definir varios elementos notables de A: a) Elemento minimal de A es todo aquel elemento a ∈ A tal que si b ≤ a entonces a = b. b) Elemento maximal de A es todo aquel elemento a ∈ A tal que si a ≤ b entonces a = b. c) M´ ınimo de A es el elemento a de A tal que a ≤ b para todo b ∈ A. d) M´ximo de A es elelemento a de A tal que b ≤ a para a todo b ∈ A. e) Cota inferior de B es cualquier elemento a ∈ A tal que a ≤ b para todo b ∈ B. f) Cota superior de B es cualquier elemento a ∈ A tal que b ≤ a para todo b ∈ B. g) ´ Infimo de B, es el m´ximo de las cotas inferiores de B. a h) Supremo de A, es el m´ ınimo de las cotas superiores de B.
1

2

Ret´ ıculos

Definici´n 2.1 Sea L un conjuntoparcialmente ordenado. Se o dice que L es un semiret´ ıculo inferior (resp. superior) si para cualesquiera x e y elementos de L, existen el ´ ınfimo, inf ({x, y}) (resp. el supremo, sup({x, y})) del conjunto {x, y}. Un conjunto ordenado que es a la vez un semiret´culo inferior ı y superior se denomina un ret´culo. ı Ejemplos. a)El conjunto de los n´meros enteros Z con la u Z relaci´n de orden usual. o b)El conjunto de los divisores (en I ) de un n´mero natN u ural n, D(n), con la relaci´n aRb si y s´lo si ”a divide a b” o o es un conjunto parcialmente ordenado. Adem´s, se tiene que a inf ({a, b}) = (a, b) y sup({a, b)} = m.c.m(a, b). c) Sea X un conjunto y A = P(X) el conjunto de todos los subconjuntos de X. A con la relaci´n de inclusic´n. o o Definici´n 2.2 Un semigrupo se llama una banda sicada eleo mento es idempotente. Proposici´n 2.3 La clase de los semiret´culos coincide con al o ı clase de todas las bandas abelianas. Un ret´ ıculo se puede definir tambi´n de manera algebraica: e Definici´n 2.4 Sean L un conjunto y ∨ y ∧ dos operaciones o binarias definidas en L. L se dice un ret´culo si es cerrado para ı ambas operaciones y si se verifican los siguientes axiomas para cualesquiera a,b, c ∈ L : Conmutatividad. 1.a) a ∨ b = b ∨ a y 1.b) a ∧ b = b ∧ a.
2

Asociatividad.2.a) a∨(b∨c) = (a∨b)∨c y 2.b) a∧(b∧c) = (a ∧ b) ∧ c. Absorci´n. 3.a) a ∧ (a ∨ b) = a y 3.b) a ∨ (a ∧ b) = a. o Definici´n 2.5 El dual de cualquier expresi´n en un ret´culo L o o ı es la expresi´n resultante de intercambiar las operaciones ∨ y o ∧. Teorema 2.6 (Principio de Dualidad) El dual de cualquier teoremaen un ret´culo es tambi´n un teorema. ı e Corolario 2.7 (Propiedades idempotentes) Sea L un ret´culo y ı a un elemento de L. Entonces: i) a ∨ a = a. ii) a ∧ a = a. Aplicando las leyes de absorci´n se tiene que o a ∧ a = a ∧ (a ∨ (a ∧ a)) = a Lema 2.8 Sea L un ret´culo y sean a y b elementos de L. Enı tonces: i) a ∧ b = a si y s´lo si a ∨ b = b. o ii) La relaci´n R definida en L por aRb si y s´losi a ∧ b = a o o o a ∨ b = b es una relaci´n de orden en L. o Teorema 2.9 Las definiciones 1.1 y 1.4 son equivalentes. Definici´n 2.10 Sean (L, ∨, ∧) y (L , ∨ , ∧ ) dos ret´ o ıculos y f : L → L . Se dice que f es un homomorfismo de ret´culos si ı f (a ∨ b) = f (a) ∨ f (b) y f (a ∧ b) = f (a) ∧ f (b). Si adem´s se a tiene que f es biyectiva entonces se dice que f es un isomorfismo de ret´culos. ı Dados(L, ∨, ∧) y (L , ∨ , ∧ ) dos ret´culos, se dice que L y L ı son isomorfos si existe un isomorfismo de ret´ ıculos de L en L .
3

3

Ret´ ıculos acotados

Definici´n 3.1 Sea L un ret´culo. Se dice que L es un ret´ o ı ıculo acotado si existen m´nimo,(tambi´n llamado elemento cero 0), ı e y m´ximo(tambi´n llamado elemento uno, 1) para L. a e

Ejemplos. i) En el conjunto de las partes de...