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

Estructuras algebraicas que son álgebra de Boole

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

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 ${\mathfrak {B}}$ 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:

${\mathfrak {B}}=\{0,1\}$

Donde:

$\varnothing =0$

$U=1\;$

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

${\begin{array}{c|c}a&{\bar {a}}\\\hline 0&1\\1&0\end{array}}$

${\begin{array}{rrcl}{\bar {}}:&{\mathfrak {B}}&\to &{\mathfrak {B}}\\&a&\to &b={\bar {a}}\end{array}}$

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}.

$\forall a\in {\mathfrak {B}}\,:\quad \exists !b\in {\mathfrak {B}}\;/\quad b={\bar {a}}$

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:

${\begin{array}{c|cc}+&0&1\\\hline 0&0&1\\1&1&1\end{array}}$

${\begin{array}{rrcl}+:&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a+b\end{array}}$

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.

$\forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists !c\in {\mathfrak {B}}\;/\quad c=a+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:

${\begin{array}{c|cc}\cdot &0&1\\\hline 0&0&0\\1&0&1\end{array}}$

${\begin{array}{rrcl}\cdot :&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a\cdot b\end{array}}$

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.

$\forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists !c\in {\mathfrak {B}}\;/\quad c=a\cdot 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

Así $(\{0,1\},{\bar {}},+,\cdot )$ es un álgebra de Boole al cumplir los siguientes axiomas:

• 1a: La ley asociativa de la suma:

$\forall a,b,c\in \{0,1\}:\;(a+b)+c=a+(b+c)$

• 1b: La ley asociativa del producto:

$\forall a,b,c\in \{0,1\}:\;(a\cdot b)\cdot c=a\cdot (b\cdot c)$

• 2a: Existencia del elemento neutro para la suma:

$\forall a\in \{0,1\}:\;a+0=a$

• 2b: Existencia del elemento neutro para el producto:

$\forall a\in \{0,1\}:\;a\cdot 1=a$

• 3a: La ley conmutativa de la suma:

$\forall a,b\in \{0,1\}:\;a+b=b+a$

• 3b: La ley conmutativa del producto:

$\forall a,b\in \{0,1\}:\;a\cdot b=b\cdot a$

• 4a: Ley distributiva de la suma respecto al producto:

$\forall a,b,c\in \{0,1\}:\;a+(b\cdot c)=(a+b)\cdot (a+c)$

• 4b: Ley distributiva del producto respecto a la suma:

$\forall a,b,c\in \{0,1\}:\;a\cdot (b+c)=(a\cdot b)+(a\cdot c)$

• 5a: Existe elemento complementario para la suma:

$\forall a\in \{0,1\};\;\exists {\bar {a}}\in \{0,1\}:\;a+{\bar {a}}=1$

• 5b: Existe elemento complementario para el producto:

$\forall a\in \{0,1\};\;\exists {\bar {a}}\in \{0,1\}:\;a\cdot {\bar {a}}=0$

Luego $(\{0,1\},{\bar {}},+,\cdot )$ es álgebra de Boole.

Teoremas fundamentales

Partiendo de estos axiomas se puede demostrar los siguientes teoremas:

• 6a: Ley de idempotencia para la suma:

$\forall a\in \{0,1\}:\;a+a=a$

• 6b: Ley de idempotencia para el producto:

$\forall a\in \{0,1\}:\;a\cdot a=a$

• 7a: Ley de absorción para la suma:

$\forall a\in \{0,1\}:\;a+1=1$

• 7b: Ley de absorción para el producto:

$\forall a\in \{0,1\}:\;a\cdot 0=0$

• 8a: Ley de identidad para la suma:

$\forall a\in \{0,1\}:\;a+0=a$

• 8b: Ley de identidad para el producto:

$\forall a\in \{0,1\}:\;a\cdot 1=a$

• 9: Ley de involución:

$\forall a\in \{0,1\}:\;{\bar {\bar {a}}}=a$

• 10: Ley del complemento:

${\bar {1}}=0$

${\bar {0}}=1$

• 11: Leyes de De Morgan:

$\forall a,b\in \{0,1\}:\;{\overline {a+b}}={\bar {a}}\cdot {\bar {b}}$

$\forall a,b\in \{0,1\}:\;{\overline {a\cdot b}}={\bar {a}}+{\bar {b}}$

Orden en el álgebra de Boole

Partiendo de $(\{0,1\},{\bar {}},+,\cdot )$ álgebra de Boole, dadas dos variables binarias: a, b, que cumplen alguna de estas condiciones:

$\left.{\begin{array}{l}a+b=b\\a\cdot b=a\\{\bar {a}}+b=1\\a\cdot {\bar {b}}=0\end{array}}\right\}\longrightarrow \quad a\leq b$

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

1. $0+1=1$
2. $0\cdot 1=0$
3. ${\bar {0}}+1=1$
4. $0\cdot {\bar {1}}=0$

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:

$0\leq 1$

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

$\left.{\begin{array}{l}0\leq 1\\0\neq 1\end{array}}\right\}\longrightarrow \quad 0<1$

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

Álgebra de conjuntos

Partiendo de un conjunto U, cualesquiera, llamamos conjunto potencia de U, al conjunto de todos los subconjuntos posibles de U y lo denotamos ${\mathcal {P}}(U)$.

A título de ejemplo podemos considerar:

$U=\{a,b,c,d,e,f\}\,$

Que tiene como conjunto potencia:

${\mathcal {P}}(U)={\Big \{}\varnothing ,\{a\},\{b\},\dots ,\{a,b\},\{a,c\},\dots ,\{a,b,c,d,e\},\dots ,U{\Big \}}$

Donde podemos definir:

${\mathfrak {B}}={\mathcal {P}}(U)$

Y como es obvio:

$\varnothing =\varnothing$

$U=U\;$

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

${\begin{array}{rrcl}{}^{C}:&{\mathcal {P}}(U)&\to &{\mathcal {P}}(U)\\&A&\to &B=A^{C}\end{array}}$

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

$\forall A\in {\mathcal {P}}(U)\,:\quad \exists !B\in {\mathcal {P}}(U)\;/\quad B=A^{C}$

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=A^{C}\longrightarrow \quad \forall x\in B:\quad x\in U\;\land \;x\notin A$

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:

${\begin{array}{rrcl}\cup :&{\mathcal {P}}(U)\times {\mathcal {P}}(U)&\to &{\mathcal {P}}(U)\\&(A,B)&\to &C=A\cup B\end{array}}$

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).

$\forall (A,B)\in {\mathcal {P}}(U)\times {\mathcal {P}}(U)\,:\quad \exists !C\in {\mathcal {P}}(U)\;/\quad C=A\cup B$

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:

$C=A\cup B\longrightarrow \quad \forall x\in C:\quad x\in A\;\lor \;x\in B$

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:

${\begin{array}{rrcl}\cap :&{\mathcal {P}}(U)\times {\mathcal {P}}(U)&\to &{\mathcal {P}}(U)\\&(A,B)&\to &C=A\cap B\end{array}}$

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).

$\forall (A,B)\in {\mathcal {P}}(U)\times {\mathcal {P}}(U)\,:\quad \exists !C\in {\mathcal {P}}(U)\;/\quad C=A\cap B$

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:

$C=A\cap B\longrightarrow \quad \forall x\in C:\quad x\in A\;\land \;x\in B$

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

Con lo que podemos plantear: $({\mathcal {P}}(U),{}^{C},\cup ,\cap )$, para un U conocido, como álgebra de Boole si cumple las siguientes axiomas:

• 1a: La ley asociativa de la unión:

$\forall A,B,C\in {\mathcal {P}}(U):\;(A\cup B)\cup C=A\cup (B\cup C)$

• 1b: La ley asociativa de la intersección:

$\forall A,B,C\in {\mathcal {P}}(U):\;(A\cap B)\cap C=A\cap (B\cap C)$

• 2a: Existencia del elemento neutro para la unión:

$\forall A\in {\mathcal {P}}(U):\;A\cup \varnothing =A$

• 2b: Existencia del elemento neutro para la intersección:

$\forall A\in {\mathcal {P}}(U):\;A\cap U=A$

• 3a: La ley conmutativa de la unión:

$\forall A,B\in {\mathcal {P}}(U):\;A\cup B=B\cup A$

• 3b: La ley conmutativa de la intersección:

$\forall A,B\in {\mathcal {P}}(U):\;A\cap B=B\cap A$

• 4a: Ley distributiva de la unión respecto de la intersección:

$\forall A,B,C\in {\mathcal {P}}(U):\;A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

• 4b: Ley distributiva de la intersección respecto a la unión:

$\forall A,B,C\in {\mathcal {P}}(U):\;A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

• 5a: Existe elemento complementario para la unión:

$\forall A\in {\mathcal {P}}(U);\;\exists A^{C}\in {\mathcal {P}}(U):\;A\cup A^{C}=U$

• 5b: Existe elemento complementario para la intersección:

$\forall A\in {\mathcal {P}}(U);\;\exists A^{C}\in {\mathcal {P}}(U):\;A\cap A^{C}=\varnothing$

Concluyendo que $({\mathcal {P}}(U),{}^{C},\cup ,\cap )$ es un álgebra de boole.

Teoremas fundamentales

Partiendo de estos axiomas se puede demostrar los siguientes teoremas:

• 6a: Ley de idempotencia para la unión:

$\forall A\in {\mathcal {P}}(U):\;A\cup A=A$

• 6b: Ley de idempotencia para la intersección:

$\forall A\in {\mathcal {P}}(U):\;A\cap A=A$

• 7a: Ley de absorción para la unión:

$\forall A\in {\mathcal {P}}(U):\;A\cup U=U$

• 7b: Ley de absorción para la intersección:

$\forall A\in {\mathcal {P}}(U):\;A\cap \varnothing =\varnothing$

• 8a: Ley de identidad para la unión:

$\forall A\in {\mathcal {P}}(U):\;A\cup \varnothing =A$

• 8b: Ley de identidad para la intersección:

$\forall A\in {\mathcal {P}}(U):\;A\cap U=A$

• 9: Ley de involución:

$\forall A\in {\mathcal {P}}(U):\;{{A}^{C}}^{C}=A$

• 10: Ley del complemento:

${U}^{C}=\varnothing$

${\varnothing }^{C}=U$

• 11: Leyes de De Morgan:

$\forall A,B\in {\mathcal {P}}(U):\;{(A\cup B)}^{C}={A}^{C}\cap {B}^{C}$

$\forall a,b\in {\mathcal {P}}(U):\;{(A\cap B)}^{C}={A}^{C}\cup {B}^{C}$

Orden en el álgebra de Boole

Dado $({\mathcal {P}}(U),{}^{C},\cup ,\cap )$ álgebra de Boole, podemos comprobar:

1. $A\cup B=B$
2. $A\cap B=A$
3. ${A}^{C}\cup B=U$
4. $A\cap {B}^{C}=\varnothing$

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:

$A\subseteq B$

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

$A\subseteq B\longrightarrow \quad \forall x\in A:\;x\in B$

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:

$\forall A\in {\mathcal {P}}(U):\;{\begin{array}{|l}A\cup U=U\\A\cap U=A\\{A}^{C}\cup U=U\\A\cap {U}^{C}=\varnothing \end{array}}\longrightarrow \quad A\subseteq U$

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:

$\forall B\in {\mathcal {P}}(U):\;{\begin{array}{|l}\varnothing \cup B=B\\\varnothing \cap B=\varnothing \\{\varnothing }^{C}\cup B=U\\\varnothing \cap {B}^{C}=\varnothing \end{array}}\longrightarrow \quad \varnothing \subseteq B$

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

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: ${\mathfrak {B}}$ al conjunto de proposiciones, a fin de ver que la lógica de proposiciones es un álgebra de Boole, además consideraremos:

$\varnothing \longrightarrow \quad \bot =F=falso$

$U\longrightarrow \quad \top =V=verdadero$

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

${\begin{array}{rrcl}\lnot :&{\mathfrak {B}}&\to &{\mathfrak {B}}\\&a&\to &b=\lnot a\end{array}}$

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

$\forall a\in {\mathfrak {B}}\,:\quad \exists !b\in {\mathfrak {B}}\;/\quad b=\lnot {a}$

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:

${\begin{array}{rrcl}\lor :&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a\lor b\end{array}}$

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.

$\forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists !c\in {\mathfrak {B}}\;/\quad c=a\lor 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:

${\begin{array}{rrcl}\land :&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a\land b\end{array}}$

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.

$\forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists !c\in {\mathfrak {B}}\;/\quad c=a\land 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

Así $({\mathfrak {B}},\lnot {},\lor ,\land )$ es un álgebra de Boole al cumple los siguientes axiomas:

• 1a: La ley asociativa de la disyunción:

$\forall a,b,c\in {\mathfrak {B}}:\;(a\lor b)\lor c=a\lor (b\lor c)$

• 1b: La ley asociativa de la conjunción:

$\forall a,b,c\in {\mathfrak {B}}:\;(a\land b)\land c=a\land (b\land c)$

• 2a: Existencia del elemento neutro para la disyunción:

$\forall a\in {\mathfrak {B}}:\;a\lor F=a$

• 2b: Existencia del elemento neutro para la conjunción:

$\forall a\in {\mathfrak {B}}:\;a\land V=a$

• 3a: La ley conmutativa de la disyunción:

$\forall a,b\in {\mathfrak {B}}:\;a\lor b=b\lor a$

• 3b: La ley conmutativa de la conjunción:

$\forall a,b\in {\mathfrak {B}}:\;a\land b=b\land a$

• 4a: Ley distributiva de la disyunción respecto a la conjunción:

$\forall a,b,c\in {\mathfrak {B}}:\;a\lor (b\land c)=(a\lor b)\land (a\lor c)$

• 4b: Ley distributiva de la conjunción respecto al disyunción:

$\forall a,b,c\in {\mathfrak {B}}:\;a\land (b\lor c)=(a\land b)\lor (a\land c)$

• 5a: Existe elemento complementario para la disyunción:

$\forall a\in {\mathfrak {B}};\;\exists \lnot {a}\in {\mathfrak {B}}:\;a\lor \lnot {a}=V$

• 5b: Existe elemento complementario para la conjunción:

$\forall a\in {\mathfrak {B}};\;\exists \lnot {a}\in {\mathfrak {B}}:\;a\land \lnot {a}=F$

Luego $({\mathfrak {B}},\lnot {},\lor ,\land )$ es álgebra de boole.

Teoremas fundamentales

Partiendo de estos axiomas se puede demostrar los siguientes teoremas:

• 6a: Ley de idempotencia para la disyunción:

$\forall a\in {\mathfrak {B}}:\;a\lor a=a$

• 6b: Ley de idempotencia para la conjunción:

$\forall a\in {\mathfrak {B}}:\;a\land a=a$

• 7a: Ley de absorción para la disyunción:

$\forall a\in {\mathfrak {B}}:\;a\lor V=V$

• 7b: Ley de absorción para la conjunción:

$\forall a\in {\mathfrak {B}}:\;a\land F=F$

• 8a: Ley de identidad para la disyunción:

$\forall a\in {\mathfrak {B}}:\;a\lor F=a$

• 8b: Ley de identidad para la conjunción:

$\forall a\in {\mathfrak {B}}:\;a\land V=a$

• 9: Ley de involución:

$\forall a\in {\mathfrak {B}}:\;\lnot \lnot a=a$

• 10: Ley de complemento:

$\lnot V=F$

$\lnot F=V$

• 11: Leyes de De Morgan:

$\forall a,b\in {\mathfrak {B}}:\;\lnot ({a\lor b})=\lnot {a}\land \lnot {b}$

$\forall a,b\in {\mathfrak {B}}:\;\lnot ({a\land b})=\lnot {a}\lor \lnot {b}$

Orden en el álgebra de Boole

Sabiendo que $({\mathfrak {B}},\lnot {},\lor ,\land )$ es álgebra de Boole, se puede comprobar que:

1. $a\lor b=b$
2. $a\land b=a$
3. $\lnot a\lor b=V$
4. $a\land \lnot b=F$

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:

$a\preccurlyeq b$

Así por ejemplo dadas las proposiciones:

• a= Llueve mucho
• b= Llueve

podemos ver:

• $a\lor b=b$

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.

• $a\land b=a$

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.

• $\lnot a\lor b=V$

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.

• $a\land \lnot b=F$

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:

$llueve\;mucho\preccurlyeq llueve$

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.