Reticulados Y Algebras De Boole

RETICULADOS Definición: Un C.O. (A , ≤) es un reticulado si cualquier subconjunto con dos elementos tiene ínfimo y tiene supremo. Nota: Si "≤" es un orden sobre A entonces la relación opuesta "≤-1" también es un orden sobre A. Observaciones: 1) Dado el diagrama de Hasse de (A , ≤), para dibujar el diagrama de Hasse de (A , ≤-1) "se invierte" el diagrama. 2) Si (A , ≤) es un reticulado entonces (A, ≤-1) es también un reticulado, que recibe el nombre de reticulado dual del anterior y suele representarse por A*. 3) Vale que: (A*)* = A.

A → A* → (A*)* = A ≤ ≤-1 (≤-1)-1 = ≤


Definición: Sea (A,≤) un reticulado con primer elemento 0 y último
.

elemento 1. Dado a∈ A

se dice que b∈ A es un complemento de a si ∈

verifica que: a ∧ b = 0 y a ∨ b = 1. Definición: Dado un conjuntoA, una operación binaria ∗ sobre A es una operación que verifica x ∗ y ∈ A , cualesquiera sean x, y ∈ A. Definamos ahora, los reticulados algebraicamente. Definición: Sean A ≠ ∅ y “+”, “.” operaciones binarias definidas sobre A. Diremos que (A, +, .) es un reticulado, y escribiremos (A, +, .)∈ L , si para todo x, y, z ∈ A, se verifican: (1) Asociativa: (x + y) + z = x + (y + z) (x . y) . z = x . (y. z) (3) Idempotencia: x + x = x x.x=x (2) Conmutativa: x + y = y + x x.y=y.x (4) Leyes de absorción: x + (x . y) = x x . (x+y) = x


Observación: En reticulados es usual considerar el orden “≤” de la siguiente manera: ó x ≤ y si y sólo si x . y = x x ≤ y si y sólo si x + y = y

Esta observación la enunciamos en los siguientes lemas: Lemas: (1) Sea (A, +, .)∈ L entonces (A , ≤) es un C.O.en el que todo par de elementos tiene ínfimo y supremo, donde el ínfimo es (x . y) y el supremo es (x + y) cualesquiera sean x, y ∈ A. (2) Sea (A , ≤) un C.O. en el que todo par de elementos tiene ínfimo y supremo, entonces definiendo x + y = x ∨ y y x . y = x ∧ y cualesquiera sean x, y ∈ A, se tiene que (A, +, .)∈ L . Observación: Para obtener ejemplos de reticulados basta con considerar diagramasde Hasse que sean C.O. donde todo par de elementos tenga ínfimo y supremo y escribir las tablas correspondientes.


Definición: Sean (A, +, .)∈ L y X ⊆ A, X ≠ ∅. Entonces diremos que X es un subreticulado de A si “+” y “.” en A de dos elementos cualesquiera de X, pertenece a X. Observación: Si X es un subreticulado de A entonces X es un subconjunto ordenado de A. Definición: Diremos que (A,+,.) es un reticulado distributivo, y escribiremos (A, +, .)∈ D si cualesquiera sean x, y, z ∈ A, se verifican: (1) (A, +, .)∈ L (2) Valen las leyes distributivas: (D1) x . (y + z) = x . y + x . z (D2) x + (y . z) = (x + y).(x + z)


Definición: Diremos que (A, +, .) es un reticulado distributivo con primer y último elemento, y escribiremos (A, +, .)∈ D A, se verifican: (1) (A, +, .)∈ D (2) 1 +x = 1 ∧ 0 . x = 0. Teorema: Si (A, +, .)∈ L entonces las propiedades siguientes son equivalentes cualesquiera sean x, y, z ∈ A: (D1) x . (y + z) = (x . y) + (x . z) (D2) x + (y . z) = (x + y).(x + z)
0,1

, si cualesquiera sean x, y, z ∈

Proposición: Toda cadena es un reticulado distributivo.

Teorema: En un reticulado distributivo vale la ley de cancelamiento. Esto es: Si x . c = y . c yx + c = y + c entonces x = y.


Teorema: Todo subreticulado de un reticulado distributivo es un reticulado distributivo. Los únicos reticulados que no son distributivos son:

que se los denomina N5 y M5 respectivamente. Veamos que no verifican x . (y + z) = (x . y) + (x . z) ó x + (y . z) = (x + y).(x + z) ▪ N5 no es distributivo ya que: a + (b . c) = a + 0 = a (a + b).(a + c) = b . 1 = bde donde a + (b . c) ≠ (a + b).(a + c). ▪ M5 no es distributivo ya que: a . (b + c) = a . 1 = a (a . b) + (a . c) = 0 + 0 = 0 de donde a . (b + c) ≠ (a . b) + (a . c)


Teorema: Sea (A, +, .)∈ L. A no es distributivo si y sólo si contiene a M5 o N5 como subreticulados. Dentro de los reticulados vamos a estudiar elementos especiales: Definiciones: Sea (A, +, .)∈ L y 0∈ A el primer elemento,...