Ir al contenido principal

Á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 ∪  xc = U              ∅ c = U
x ∩  xc = ∅            U c = ∅




Comentarios

Entradas populares de este blog

C: Ejemplos: Congruencia de Zeller (nivel básico) ...

La Congruencia de Zeller es un algoritmo que se atribuye al matemático alemán Julius Christian Johannes Zeller que vivió en el siglo XIX. Este algoritmo nos permite determinar el día de la semana que le corresponde a una fecha determinada del calendario Gregoriano. La fórmula que nosotros usaremos (con algunas modificaciones respecto de la original para poder usarla en  informática) es la siguiente: Donde h es el día de la semana (entre 0 y 6), J es año/100 (la centuria) y K es año mod 100 (el año de la centuria). Y hay que tener en cuenta que los meses de enero y febrero cuentan como el mes 13 y 14 del año anterior. Ahora que tenemos la fórmula, programemos el algoritmo en C mediante el uso de una función: Analicemos el código paso a paso: Tenemos en cuenta el caso de enero y febrero: Dijimos que estos meses corresponden a los meses 13 y 14 del año anterior por lo que los asignamos como corresponde (mes + 12 , que dará 13 para enero y 14 para febrero) y le ...

C: Conversiones de tipo (casting) en C...

El casting o simplemente cast  nos permite hacer una conversión explícita de un tipo de dato a otro, a criterio del programador siempre y cuando estos tipos sean compatibles. Este cast se realiza a través de un operador de conversión de tipos (type casting operator) y es un recurso a tener en cuenta ya que hay situaciones en que nos puede resultar de gran utilidad. Hacer uso de un cast es tan sencillo como poner (tipo de dato)  delante de la expresión o variable a convertir. Veamos un ejemplo: Declaramos una variable de tipo int con un identificador tan creativo como "a" y le realizamos diferentes cast a a para mostrarlo como si fuera un float, un double y un char en un printf. Lo que obtendríamos en pantalla sería lo siguiente: Donde tenemos el valor de nuestro a, a convertido en float y double (mostrándolo con 3 cifras decimales) y a convertido en char. Si vemos este último caso, al hacer la conversión de "a" a char toma a como el código ascii de...

Algoritmos: Estructuras de control en pseudocódigo...

Como vimos anteriormente , el bloque de instrucciones es importante para nuestro algoritmo ya que a través del mismo lo resolveremos. Para ello, este bloque se valdrá de tres tipos de estructuras de control: Estructura secuencial. Estructuras selectivas. Estructuras iterativas.   Estructura secuencial: En esta estructura las instrucciones se colocan ordenadas en forma secuencial, una debajo de la otra y se ejecutan en el orden en que están escritas, como ya vimos en el gráfico de la entrada anterior. Estructuras de selección: Dentro de este tipo de estructuras veremos 3 diferentes: si , si...sino , según . SI (selección): En esta estructura de selección, las instrucciones dependen de una condición para ejecutarse. El algoritmo analiza el resultado de dicha condición booleana (se cumple o no) y realiza la acción correspondiente a ese resultado. Si no se cumple la condición no hace nada. SI...SINO (selección doble): Esta estructura funciona de la misma manera que la selección tradici...