Álgebra/Álgebra de Boole/Estructuras algebraicas que son álgebra de Boole

De Wikilibros, la colección de libros de texto de contenido libre.
Ir a la navegación Ir a la búsqueda

Estructuras algebraicas que son álgebra de Boole[editar]

Hay numerosos casos de distintos análisis de estructuras algebraicas que corresponden al álgebra de Boole, aunque en apariencia son muy diferentes, su estructura es la misma. Vamos a ver algunos de ellos, con el propósito de hacer palpable las similitudes en la estructura y los distintos ámbitos de aplicación y distinta terminología para referirse a las operaciones o a las variables.

Lógica binaria[editar]

Una serie de temas, aparentemente tan distintos, tiene dos cosas en común, la lógica binaria basada en los ceros y los unos y el álgebra de Boole, posiblemente la forma más conocida de esta álgebra, que en ocasiones da lugar a la interpretación que el álgebra de Boole es la lógica binaria exclusivamente, así el conjunto en este caso está formado por dos elementos {0,1}, o {F, V}, o {no, sí}, dos valores contrapuestos, que son las dos posibles alternativas entre dos situaciones posibles, aquí, sin pérdida de la generalidad, tomaremos el conjunto: {0,1} como ya hemos dicho:

Donde:

  • La operación unaria interna, que llamaremos negación:

La operación unaria interna negación, definimos una aplicación que a cada elemento a de {0,1}, le asigna un b de {0,1}.

Para todo elemento a en {0.1}, se cumple que existe un único b en {0,1}, tal que b es la negación de a. Como se ve en la tabla.

  • La operación binaria interna, que llamaremos suma:

Con la operación suma definimos una aplicación que, a cada par ordenado (a, b) de B por B, le asigna un c de B.

Para todo par ordenado (a,b) en B por B, se cumple que existe un único c en B, tal que c es el resultado de sumar a con b.

  • la operación binaria interna, que llamaremos producto:

Con la operación producto definimos una aplicación que, a cada par ordenado (a, b) de B por B, le asigna un c de B.

Para todo par ordenado (a, b) en B por B, se cumple que existe un único c en B, tal que c es el resultado del producto a y b. Como se puede ver en la tabla.

Axiomas[editar]

Así es un álgebra de Boole al cumplir los siguientes axiomas:

  • 1a: La ley asociativa de la suma:
  • 1b: La ley asociativa del producto:
  • 2a: Existencia del elemento neutro para la suma:
  • 2b: Existencia del elemento neutro para el producto:
  • 3a: La ley conmutativa de la suma:
  • 3b: La ley conmutativa del producto:
  • 4a: Ley distributiva de la suma respecto al producto:
  • 4b: Ley distributiva del producto respecto a la suma:
  • 5a: Existe elemento complementario para la suma:
  • 5b: Existe elemento complementario para el producto:

Luego es álgebra de Boole.

Teoremas fundamentales[editar]

Partiendo de estos axiomas se puede demostrar los siguientes teoremas:

  • 6a: Ley de idempotencia para la suma:
  • 6b: Ley de idempotencia para el producto:
  • 7a: Ley de absorción para la suma:
  • 7b: Ley de absorción para el producto:
  • 8a: Ley de identidad para la suma:
  • 8b: Ley de identidad para el producto:
  • 9: Ley de involución:
  • 10: Ley del complemento:
  • 11: Leyes de De Morgan:

Orden en el álgebra de Boole[editar]

Partiendo de álgebra de Boole, dadas dos variables binarias: a, b, que cumplen alguna de estas condiciones:

entonces a es menor o igual que b. Dados los valores binarios 0 y 1, podemos ver:

Estas cuatro condiciones son equivalentes y el cumplimiento de una de ellas supone el cumplimiento de las otras, en este caso es sencillo comprobarlas todas. Luego podemos decir que 0 antecede a 1 y lo denotamos:

Si además sabemos que 0 y 1 son valores distintos:

El valor binario 0 es menor que el valor binario 1.

Álgebra de conjuntos[editar]

DosConjuntos100.svg

Partiendo de un conjunto U, cualesquiera, llamamos conjunto potencia de U, al conjunto de todos los subconjuntos posibles de U y lo denotamos .

A título de ejemplo podemos considerar:

Que tiene como conjunto potencia:

Donde podemos definir:

Y como es obvio:

  • La operación unaria interna, que llamaremos complemento:
UnConjunto02.svg

En esta operación definimos una aplicación que, a cada elemento A de P(U), le asigna un B de P(U).

Para todo elemento A en P(U), se cumple que existe un único B en P(U), tal que B es el complemento A.

Definiendo el complemento de un conjunto así:

B es el complemento de A, si se cumple que para todo x que pertenezca a B, x pertenece a U y x no pertenece a A.

  • La primera operación binaria la llamaremos unión:
DosConjuntos02.svg

Con esta operación binaria interna definimos una aplicación que, a cada par ordenado (A, B) de P(U) por P(U), le asigna un C de P(U).

Para todo par ordenado (A,B) en P(U) por P(U), se cumple que existe un único C en P(U), tal que C es la unión A y B.

Definiendo la unión de dos conjuntos como:

El conjunto C es la unión de A y B, si para todo elemento x de C, se cumple que x es elemento de A o de B

  • La segunda operación binaria la llamaremos intersección:
DosConjuntos08.svg

Con lo que definimos una aplicación que, a cada par ordenado (A, B) de P(U) por P(U), le asigna un C de P(U).

Para todo par ordenado (A,B) en P(U) por P(U), se cumple que existe un único C en P(U), tal que C es la intersección A y B.

Definiendo la intersección de dos conjuntos como:

El conjunto C es la intersección de A y B, si para todo elemento x de C, se cumple que x es elemento de A y de B.

Axiomas[editar]

Con lo que podemos plantear: , para un U conocido, como álgebra de Boole si cumple las siguientes axiomas:

  • 1a: La ley asociativa de la unión:
  • 1b: La ley asociativa de la intersección:
  • 2a: Existencia del elemento neutro para la unión:
  • 2b: Existencia del elemento neutro para la intersección:
  • 3a: La ley conmutativa de la unión:
  • 3b: La ley conmutativa de la intersección:
  • 4a: Ley distributiva de la unión respecto de la intersección:
  • 4b: Ley distributiva de la intersección respecto a la unión:
  • 5a: Existe elemento complementario para la unión:
  • 5b: Existe elemento complementario para la intersección:

Concluyendo que es un álgebra de boole.

Teoremas fundamentales[editar]

Partiendo de estos axiomas se puede demostrar los siguientes teoremas:

  • 6a: Ley de idempotencia para la unión:
  • 6b: Ley de idempotencia para la intersección:
  • 7a: Ley de absorción para la unión:
  • 7b: Ley de absorción para la intersección:
  • 8a: Ley de identidad para la unión:
  • 8b: Ley de identidad para la intersección:
  • 9: Ley de involución:
  • 10: Ley del complemento:
  • 11: Leyes de De Morgan:

Orden en el álgebra de Boole[editar]

Dado álgebra de Boole, podemos comprobar:

Para los conjuntos A y B que cumplen estas propiedades, podemos decir que A antecede a B, que en el caso de conjuntos se diría A es igual o un subconjunto de B y lo denotamos:

Entendiéndose que A es igual o un subconjunto de B cuando:

DosConjuntos218.svg

El conjunto A es igual o un subconjunto de B, si para todo elemento x que pertenezca a A, x pertenece a B.

También se puede comprobar:

Para todo A de las partes de U, si se cumple que: la unión de A y U es U, la intersección de A y U es A, la unión del complemento de A y U es U, la intersección de A y el complemento de U es el conjunto vacío, entonces A es igual o un subconjunto de U.

Esta conclusión forma parte de la definición de las partes de U, pero se puede llegar a ella por el cumplimiento de una de las cuatro condiciones expuestas, como ya se mencionó, las cuatro condiciones son equivalentes y el cumplimiento de una de ellas implica el cumplimiento de las demás.

Aplicando el mismo razonamiento podemos ver:

Siendo B un conjunto de las partes de U, llegando a la conclusión de que el conjunto vacío es igual o un subconjunto de B.

Lógica proposicional o de predicados[editar]

Una proposición, o un predicado, es un valor de verdad que puede expresarse de forma verbal o con expresiones o relaciones matemática o lógica, por ejemplo:

  • 'Hoy es miércoles.'
  • 'El edificio es alto.'
  • 'El perro está ladrando.'

Son proposiciones expresadas verbalmente, y también lo son:

  • 'x = 3'
  • 'mcd(a, b) = 2n + 1'

Dado que cada una de ellas puede ser verdadera o falsa, las proposiciones suelen designarse con letra:

  • p= 'Llueve'
  • q= 'Llueve mucho'
  • r= 'Llevo paraguas'
  • s= 'La calle está mojada'

Las afirmaciones verdadero y falso también son proposiciones, designaremos con: al conjunto de proposiciones, a fin de ver que la lógica de proposiciones es un álgebra de Boole, además consideraremos:

  • La operación unaria interna, que llamaremos negación:

La operación unaria interna negación, definimos una aplicación que a cada proposición a, le asigna otra poposición b.

Para toda proposición a, se cumple que existe una única proposición b, tal que b es la negación de a.

  • La primera operación binaria interna, que llamaremos disyunción:

Con la operación disyunción, definimos una aplicación que a cada par ordenado (a, b) de B por B, le asigna un c de B.

Para todo par ordenado (a,b) en B por B, se cumple que existe un único c en B, tal que c es el resultado de la disyunción de a y b.

  • La segunda operación binaria interna, que llamaremos conjunción:

Con la operación conjunción definimos una aplicación que, a cada par ordenado (a, b) de B por B, le asigna un c de B.

Para todo par ordenado (a, b) en B por B, se cumple que existe un único c en B, tal que c es el resultado de la conjunción de a y b.

Axiomas[editar]

Así es un álgebra de Boole al cumple los siguientes axiomas:

  • 1a: La ley asociativa de la disyunción:
  • 1b: La ley asociativa de la conjunción:
  • 2a: Existencia del elemento neutro para la disyunción:
  • 2b: Existencia del elemento neutro para la conjunción:
  • 3a: La ley conmutativa de la disyunción:
  • 3b: La ley conmutativa de la conjunción:
  • 4a: Ley distributiva de la disyunción respecto a la conjunción:
  • 4b: Ley distributiva de la conjunción respecto al disyunción:
  • 5a: Existe elemento complementario para la disyunción:
  • 5b: Existe elemento complementario para la conjunción:

Luego es álgebra de boole.

Teoremas fundamentales[editar]

Partiendo de estos axiomas se puede demostrar los siguientes teoremas:

  • 6a: Ley de idempotencia para la disyunción:
  • 6b: Ley de idempotencia para la conjunción:
  • 7a: Ley de absorción para la disyunción:
  • 7b: Ley de absorción para la conjunción:
  • 8a: Ley de identidad para la disyunción:
  • 8b: Ley de identidad para la conjunción:
  • 9: Ley de involución:
  • 10: Ley de complemento:
  • 11: Leyes de De Morgan:

Orden en el álgebra de Boole[editar]

Sabiendo que es álgebra de Boole, se puede comprobar que:

Para las proposiciones: a, b que cumplen alguna de estas condiciones se puede afirmar que a antecede a b. Que en el caso de proposiciones o predicados se dice que a es tanto o más fuerte que b, o que b es más débil que a, y lo representamos:

Así por ejemplo dadas las proposiciones:

  • a= Llueve mucho
  • b= Llueve

podemos ver:

Si: llueve mucho o llueve entonces llueve.

Si se da la circunstancia de cualesquiera de dos, que llueve mucho o llueve, claramente llueve en cualquier caso.

Si: llueve mucho y llueve entonces llueve mucho.

Si afirmamos que llueve mucho y que llueve, y se cumplen las dos circunstancias entonces es que llueve mucho.

Si: no llueve mucho o llueve es verdadero.

No llueve mucho indica que puede que llueva poco o que no llueva, si no llueve mucho o llueve abarca todas las posibilidades, desde tiempo seco a muy lluvioso, luego la afirmación es verdadera en todo caso.

Si: llueve mucho y no llueve es falso.

Si afirmamos que llueve mucho y simultáneamente que no llueve, la afirmación es claramente falsa.

La afirmación más restrictiva es la más fuerte y la menos restrictiva la más débil, en este caso:

La proposición llueve mucho es tanto o más fuerte que llueve, la afirmación llueve mucho es un caso particular o el mismo caso de llueve.