13.5: Álgebras booleanas finitas como n-tuplas de 0's y 1's

Última actualización
Guardar como PDF

Page ID: 117188

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

De la sección anterior sabemos que todas las álgebras booleanas finitas son de orden\(2^n\text{,}\) donde\(n\) está el número de átomos en el álgebra. Por lo tanto, podemos describir completamente cada álgebra booleana finita por el álgebra de conjuntos de poder. ¿Hay una forma más conveniente, o al menos alternativa, de definir álgebras booleanas finitas? En el Capítulo 11 encontramos que podríamos producir nuevos grupos tomando productos cartesianos de grupos previamente conocidos. Imitamos este proceso para álgebras booleanas.

El álgebra booleana no trivial más simple es el álgebra booleana en\(B_2=\{0, 1\}\text{.}\) el conjunto El ordenamiento encendido\(B_2\) es el natural,\(0 \leq 0, 0\leq 1, 1\leq 1\text{.}\) Si tratamos a 0 y 1 como los valores de verdad “falso” y “verdadero”, respectivamente, vemos que las operaciones booleanas\(\lor (\textrm{join})\) y no\(\land (\textrm{meet})\) son más que las operación lógica con los mismos símbolos. La operación booleana,\(-\text{,}\) (complementación) es la lógica\(\neg\) (negación). De hecho, es por ello que estos símbolos fueron elegidos como los nombres de las operaciones booleanas. Las mesas de operaciones para\(\left[B_2;\lor ,\land, - \right]\) son simplemente las de “o”, “y” y “no”, que repetimos aquí.

\ begin {ecuation*}\ begin {array} {lcr}\ begin {array} {c|cc}\ lor & 0 & 1\\ hline 0 & 0 & 0 & 1\\ 1 & 1 & 1\\\ end {array} &\ begin {array} {c|cc}\ land & 0 & 1\\ hline 0 & 0 & 0\\ 1 & 0 & 1\\ end\ {array} &\ begin {array} {c|c} u &\ overset {-} {u}\\\ hline 0 & 1\\ 1 & 0\\\ end {array}\ end {array}\ end {ecuación*}

Por el Teorema 13.4.2 y sus corolarios, todas las álgebras booleanas de orden 2 son isomórficas a ésta.

Sabemos que si formamos\(B_2\times B_2=B_2^2\) obtenemos el conjunto\(\{(0, 0), (0, 1), (1, 0), (1, 1)\}\text{,}\) un conjunto de orden 4. Definimos operaciones en\(B_2^2\) la forma natural, es decir componentwise, de manera que\((0, 1)\lor (1, 1)=(0\lor 1, 1\lor 1)=(1, 1)\text{,}\)\((0, 1)\land (1, 1)=(0\land 1, 1\land 1)=(0, 1)\) y\(\overline{(0, 1)} = \left(\bar{0}, \bar{1}\right)=(1, 0)\text{.}\) Afirmamos que\(B_2^2\) es un álgebra booleana bajo las operaciones componentwise. De ahí,\(\left[B_2^2; \lor , \land, \bar{}\hspace{3 pt}\right]\) es un álgebra booleana de orden 4. Dado que todas las álgebras booleanas de orden 4 son isomórficas entre sí, hemos encontrado una manera sencilla de describir todas las álgebras booleanas de orden 4.

Es bastante claro que podemos describir cualquier álgebra booleana de orden 8 considerando\(B_2\times B_2\times B_2=B_2^3\) y, más generalmente, cualquier álgebra booleana de orden\(2^n\) con\(B_2^n=B_2\times B_2\times \cdots \times B_2\) (\(n\)factores).

Ejercicios

Ejercicio\(\PageIndex{1}\)

Escriba las tablas de operaciones para\(\left[B_2^2; \lor , \land, - \right].\)
Dibuja el diagrama de Hasse\(\left[B_2^2; \lor , \land, - \right]\) y compara tus resultados con la Figura 6.3.1.
Encuentra los átomos de este álgebra booleana.

Contestar

\ begin {ecuación*}\ begin {array} {lc}\ begin {array} {c|cccc}\ lor & (0,0) & (0,1) & (1,0) & (1,1) & (1,1)\\ hline (0,0) & (0,0) & (0,1) & (1,0) & (1,1)\\ (0,1) & (0,1) & (1,1)\ (1,0) y (1,0) y (1,1) y (1,0) y (1,1)\\ (1,1) y (1,1) y (1,1) & (1,1) & (1,1)\\\ end {array} &\\\ begin {array} {c|cccc}\ land & (0,0) & (0,1) & (1,0) & (1,1)\\ hline (0,0) & (0,0) & (0,0) & (0,0) & (0,0) & (0,0)\ (0,1) & (0,0) & (0,0) & (0,1)\\ (1,0) & (0,0) & (0,0) & (1,0) & (1,0)\\ (1,1) & amp; (0,0) & (0,1) & (1,0) & (1,1)\\\ end {array} &\ begin {array} {c|c} u &\ overset {\ pmb {\ _}} {u}\\\ hline (0,0) & (1,1)\\ (0,1) & (1,0)\\ (1,0) & (0,1)\\ (1,1) & (0,0)\\\ end {array}\\\ end {array}\ end {ecuación*}
Las gráficas son isomórficas.
(0, 1) y (1,0)

Ejercicio\(\PageIndex{2}\)

Escriba las tablas de operaciones para\(\left[B_2^3; \lor , \land, - \right].\)
Dibuja el diagrama de Hasse para\(\left[B_2^3; \lor , \land , - \right]\)

Ejercicio\(\PageIndex{3}\)

Listar todos los átomos de\(B_2^4\text{.}\)
Describir los átomos de\(B_2^n, n \geq 1\text{.}\)

Contestar

\((1, 0, 0, 0)\text{,}\)\((0, 1, 0, 0)\text{,}\)\((0, 0, 1, 0)\text{,}\)y\((0, 0, 0, 1)\) son los átomos.
Las\(n\) -tuplas de bits con exactamente uno 1.

Ejercicio\(\PageIndex{4}\)

El teorema 13.4.2 nos dice que podemos pensar en cualquier álgebra booleana finita en términos de conjuntos. En el Capítulo 4, definimos minsets Definición 4.3.1 y minset forma normal Definición 4.3.2. Reformulen estas definiciones en el lenguaje del álgebra booleana. La generalización de minsets se llaman minterms.