Álgebra de Boole

Los sistemas que se consideran como un álgebra de Boole, son aparentemente distintos pero obedecen a un mismo conjunto de leyes.




En este post, aprenderemos cómo determinar si un sistema constituye un álgebra de Boole. Para explicarlo, usaremos un conjunto S con las siguientes características: tiene las operaciones binarias "+" y "." , la operación  unaria " ' " y los elementos neutros "0" y "1". Con lo que tendríamos el sistema (S, +, . , ' , 0, 1) .

Para que este sistema forme un álgebra de Boole, debe cumplir las siguientes leyes:


Leyes asociativas: ∀x, y, z ∈ S

• x + (y + z) = (x + y) + z
• x . (y . z) = (x . y) . z

Leyes conmutativas: ∀x, y ∈ S

• x + y = y + x
• x . y = y . x

Leyes distributivas: ∀x, y, z ∈ S

• x . (y + z) = (x . y) + (x . z)
• x + (y . z) = (x + y) . (x + z)

Leyes de identidad: ∀x ∈ S

• x + 0 = x
• x . 0 = 0
• x + 1 = 1
• x . 1 = x

Leyes de complementación: ∀x ∈ S

• x + x' = 1
• x . x' = 0
• 0' = 1
• 1' = 0

RESUMEN: Para que un sistema constituya un Álgebra de Boole, debe tener las operaciones binarias, la operación unaria, los elementos neutros y cumplir todas las leyes enunciadas anteriormente. Por lo que, como todo, es más sencillo demostrar que un sistema no es un Álgebra de Boole, ya que bastaría con probar que no cumple con alguna de las leyes en lugar de tener que probar todas.

  

TEOREMA: Si  B = (S, +, . , ', 0 , 1) es un Álgebra de Boole, entonces se cumplen las siguientes propiedades: 

Leyes de idempotencia:

• x + x = x
• x . x = x

Leyes de absorción:

• x + (x . y) = x
• x . (x + y) = x

Ley de involución:

• (x')' = x

Leyes de DeMorgan:

• (x + y)' = x' . y'
• (x . y)' = x' + y'

Llegando a este punto, las leyes que debe cumplir y las que el teorema asegura que se cumplen, nos recuerdan las que ya vimos para lógica proposicional. Y ahora ya tenemos los conceptos y herramientas para probar que dicha lógica constituye un Álgebra de Boole, como habíamos anticipado en el primer post del tema.

Si queremos probarlo, simplemente reemplazamos nuestro conjunto S por uno nuevo L con las operaciones (L, v, ^ , ¬ , V, F) y verificamos que se cumplan todas las leyes que la definición establece. Y, en efecto, veremos que sí se cumple como ya mostramos en los post relativos a lógica proposicional.

Para terminar, daremos como otro ejemplo del Álgebra de Boole, lo que conocemos como Álgebra de conjuntos: (P(x) , ∪ , ∩ ,  ^c  , ∅, U) 

Podemos probar que cumple con todas las leyes:

Leyes asociativas:                                         Leyes conmutativas:


x ∪ (y ∪ z) = (x ∪ y) ∪ z                              x∪ y = y ∪ x
x ∩ (y∩ z) = (x∩ y) ∩ z                                x∩ y = y∩ x

Leyes distributivas:                                       Leyes de identidad:

x ∪ ( y ∩ z) = (x ∪ y) ∩ (x ∪ z)                     x ∪ ∅  = x         x ∪ U  = U   

x ∩ ( y ∪ z) = (x ∩ y) ∪ (x ∩ z)                     x ∩  ∅ = ∅        x∩U  = x                   

Leyes de complementación:

x ∪  x^c = U              ∅ ^c = U

x ∩  x^c = ∅            U ^c = ∅