13.3: Álgebras booleanas

Para definir un álgebra booleana, necesitamos el concepto adicional de complementación. Una celosía debe tener tanto un elemento mayor como un elemento mínimo para que se lleve a cabo la complementación. La siguiente definición nos ahorrará algunas palabras en el resto de esta sección.

Definición\(\PageIndex{1}\): Bounded Lattice

Una celosía acotada es una celosía que contiene tanto un elemento mínimo como un elemento mayor.

Usamos los símbolos\(\pmb{0}\) y\(\pmb{1}\) para los elementos menores y mayores de una celosía acotada en el resto de esta sección.

Definición\(\PageIndex{2}\): The Complement of a Lattice Element

Dejar\([L; \lor ,\land ]\) ser una celosía acotada. Si\(a \in L\text{,}\) entonces\(a\) tiene un complemento si existe\(b \in L\) tal que

\ begin {ecuación*}\ begin {array} {c} a\ lor b =\ pmb {1}\\\ textrm {y}\\ a\ land b =\ pmb {0}\\\ end {array}\ end {ecuación*}

Observe que por las leyes conmutativas para celosías, si\(b\) complementa\(a\text{,}\) entonces\(a\) complementa\(b\text{.}\)

Definición\(\PageIndex{3}\): Complemented Lattice

Dejar\(\mathcal{L}=[L; \lor ,\land ]\) ser una celosía acotada. \(\mathcal{L}\)es una celosía complementada si cada elemento de\(L\) tiene un complemento en\(L\text{.}\)

Ejemplo\(\PageIndex{1}\): Set Complement is a Complement

En el Capítulo 1, definimos el complemento de un subconjunto de cualquier universo. Esto resulta ser un ejemplo concreto del concepto general que acabamos de definir, pero razonaremos a través de por qué este es el caso aquí. Vamos\(L = \mathcal{P}(A)\text{,}\) donde\(A = \{a, b, c\}\text{.}\) Entonces\([L; \cup , \cap ]\) es una celosía acotada con\(0 = \emptyset\) y\(1 = A\text{.}\) Para encontrar el complemento, si existe, de\(B = \{a, b\} \in L\text{,}\) por ejemplo, queremos\(D\) tal que

\ begin {ecuación*}\ begin {array} {c}\ {a, b\}\ cap D =\ emptyset\\ y\\\ {a, b\}\ copa D = A\\\ end {array}\ end {ecuación*}

No es demasiado difícil verlo\(D = \{c\}\text{,}\) ya que necesitamos incluir para\(c\) hacer verdadera la primera condición y no podemos incluir\(a\) o\(b\) si la segunda condición es para ser verdadera. Por supuesto que así es precisamente como definimos\(A^c\) en el Capítulo 1. Ya que se puede demostrar que cada elemento de\(L\) tiene un complemento (ver Ejercicio 1),\([L; \cup , \cap ]\) es una celosía complementada. Tenga en cuenta que si\(A\) hay algún conjunto y\(L = \mathcal{P}(A)\text{,}\) luego\([L; \cup , \cap ]\) es una celosía complementada donde el complemento de\(B \in L\) es\(B ^c = A - B\text{.}\)

En Ejemplo\(\PageIndex{1}\), observamos que el complemento de cada elemento de\(L\) es único. ¿Es esto siempre cierto en una celosía complementada? La respuesta es no. Considera lo siguiente.

Ejemplo\(\PageIndex{2}\): A Lattice for Which Complements are Not Unique

Dejar\(L = \{1, 2, 3, 5, 30\}\) y considerar la celosía\([L; \lor, \land ]\) (bajo “divide”). El elemento mínimo de\(L\) es 1 y el elemento mayor es 30. Calculemos el complemento del elemento\(a = 2\text{.}\) Queremos determinar\(\bar{a}\) tal que\(2 \land \bar{a} = 1\) y\(2 \lor \bar{a} = 30\text{.}\) Ciertamente,\(\bar{a} = 3\) funciona, pero también\(\bar{a} = 5\text{,}\) lo hace el complemento de\(a = 2\) en esta celosía no es único. Sin embargo,\([L; \lor , \land ]\) sigue siendo una celosía complementada ya que cada elemento sí tiene al menos un complemento.

Definición \(\PageIndex{4}\): Complementation as an Operation

Si una celosía complementada tiene la propiedad de que el complemento de cada elemento es único, entonces consideramos que la complementación es una operación unaria. La notación habitual para el complemento de\(a\) es\(\bar{a}\text{.}\)

El siguiente teorema nos da una idea de cuándo ocurre la singularidad de los complementos.

Teorema\(\PageIndex{1}\): One Condition for Unique Complements

Si\([L; \lor ,\land ]\) se trata de una red distributiva complementada, entonces el complemento de cada elemento\(a \in L\) es único.

Prueba

Dejar\(a \in L\) y asumir al contrario que\(a\) tiene dos complementos, a saber\(a_1\) y\(a_2\text{.}\) Entonces por la definición de complemento,

\ begin {ecuación*}\ begin {array} {c} a\ land a_1 = 0\ textrm {y} a\ lor a_1 = 1,\\ y\\ a\ land a_2 = 0\ textrm {y} a\ lor a_2 = 1,\\\ end {array}\ text {.} \ end {ecuación*}

Entonces

\ begin {ecuation*}\ begin {split} a_1 & =a_1\ land\ pmb {1} = a_1\ land\ left (a\ lor a_2\ right)\\ &=\ left (a_1\ land a\ right)\ lor\ left (a_1\ land a_2\ right)\\ &=\ pmb {0}\ lor\ left (a_1\ land a_2 right\)\\ &=a_1\ land a_2\\\\\ end {split}\ end {ecuación*}

Por otra parte,

\ begin {ecuation*}\ begin {split} a_2 &= a_2\ land\ pmb {1} = a_2\ land\ left (a\ lor a_1\ right)\\ &=\ left (a_2\ land a\ right)\ lor\ left (a_2\ land a_1\ right)\\ &=\ pmb {0}\ lor\ left (a_2\ land a_1 derecho\)\\ &= a_2\ tierra a_1\\ &= a_1\ tierra a_2\\\\ final {dividir}\ final {ecuación*}

De ahí lo\(a_1 = a_2\text{,}\) que contradice la suposición que\(a\) tiene dos complementos diferentes.

Definición \(\PageIndex{5}\): Boolean Algebra

Un álgebra booleana es una celosía que contiene un elemento mínimo y un elemento mayor y que es a la vez complementada y distributiva. La notación\([B; \lor , \land, \bar{\hspace{5 mm}}]\) se utiliza para denotar el álgebra booleana con operaciones join, meet y complementation.

Dado que el complemento de cada elemento en un álgebra booleana es único (por Teorema\(\PageIndex{1}\)), la complementación es una operación unaria válida sobre el conjunto en discusión, razón por la cual la enumeraremos junto con las otras dos operaciones para enfatizar que estamos discutiendo un conjunto junto con tres operaciones. También, para ayudar a enfatizar la distinción entre celosías y celosías que son álgebras booleanas, usaremos la letra\(B\) como símbolo genérico para el conjunto de un álgebra booleana; es decir,\([B; \lor , \land, \bar{\hspace{5 mm}} ]\) representará un álgebra booleana general.

Ejemplo\(\PageIndex{3}\): Boolean Algebra of Sets

Dejar\(A\) ser cualquier conjunto, y dejar\(B = \mathcal{P}(A)\text{.}\) Entonces\([B; \cup, \cap, {}^c]\) es un álgebra booleana. Aquí,\({}^c\) representa el complemento de un elemento de\(B\) con respecto a\(A\text{,}\)\(A-B\text{.}\)

Este es un ejemplo clave para nosotros ya que todas las álgebras booleanas finitas y muchas álgebras booleanas infinitas se parecen a este ejemplo para algunos\(A\text{.}\) De hecho, una mirada a las leyes básicas del álgebra booleana en la Tabla\(\PageIndex{1}\), en comparación con las leyes establecidas del Capítulo 4 y las leyes básicas de la lógica de Capítulo 3, indica que los tres sistemas se comportan igual; es decir, son isomórficos.

Ejemplo\(\PageIndex{4}\): Divisors of 30

Un ejemplo algo menos estándar de álgebra booleana se deriva de la red de divisores de 30 bajo la relación “divide”. Si examina el diagrama de orden para esta celosía, verá que es estructuralmente igual que el álgebra booleana de subconjuntos de un conjunto de tres elementos. Por lo tanto, las operaciones de unión, encuentro y complementación actúan igual que unión, intersección y complementación de conjuntos. Podríamos conjeturar que la celosía de los divisores de cualquier entero producirá un álgebra booleana, pero es sólo el caso de ciertos enteros. Prueba algunos enteros para ver si puedes identificar lo que es necesario para producir un álgebra booleana.

Tabla\(\PageIndex{1}\): Leyes básicas del álgebra booleana

Leyes conmutativas	\(a\lor b = b\lor a\)	\(a \land b = b \land a \)
Leyes asociativas	\(a \lor (b \lor c) = (a \lor b) \lor c \)	\(a \land (b \land c) = (a \land b) \land c\)
Leyes Distributivas	\(a \land (b \lor c) = (a \land b) \lor (a \land c)\)	\(a \lor (b \land c) = (a \lor b) \land (a \lor c)\)
Leyes de Identidad	\(a \lor 0 = 0 \lor a = a\)	\(a \land 1= 1 \land a = a\)
Leyes Complementarias	\(a \lor \bar{a} = 1 \)	\(a \land \bar{a}= 0\)
Leyes idempotentes	\(a \lor a = a\)	\(a \land a = a\)
Leyes nulas	\(a \lor 1 = 1\)	\(a \land 0 = 0 \)
Leyes de Absorción	\(a \lor (a \land b) = a\)	\(a \land (a \lor b) = a \)
Leyes de DeMorgan	\(\overline{a \lor b} = \bar{a} \land \bar{b}\)	\(\overline{a \land b} = \bar{a} \lor \bar{b} \)
Ley de Involución	\(\overline{\bar{a}} = a\)

Los “emparejamientos” de las leyes del álgebra booleana nos recuerda el principio de dualidad, que declaramos para un álgebra booleana.

Definición\(\PageIndex{6}\): Principle of Duality for Boolean Algebras

Let\(\mathcal{B}=[B; \lor, \land, \hspace{1 mm}^c]\) be a Boolean algebra under\(\preceq\text{,}\) and let\(S\) be a true statement for\(\mathcal{B}\text{.}\)\(S^*\) If is get from\(S\) reemplazando\(\preceq\) con\(\succeq\) (esto equivale a voltear la gráfica al revés),\(\lor\)\(\land\text{,}\)\(\land\) con\(\lor\text{,}\) \(\pmb{0}\)con\(\pmb{1}\text{,}\) y\(\pmb{1}\) con\(\pmb{0}\text{,}\) entonces también\(S^*\) es una verdadera afirmación en\(\mathcal{B}\text{.}\)

Ejercicios

Ejercicio\(\PageIndex{1}\)

Determinar el complemento de cada elemento\(B \in L\) en Ejemplo\(\PageIndex{1}\). ¿Esta celosía es un álgebra booleana? ¿Por qué?

Responder

\(\begin{array}{cc} B & \textrm{ Complement of } B \\ \hline \begin{array}{c} \emptyset \\ \{a\} \\ \{b\} \\ \{c\} \\ \{a,b\} \\ \{a,c\} \\ \{b,c\} \\ A \\ \end{array} & \begin{array}{c} A \\ \{b,c\} \\ \{a,c\} \\ \{a,b\} \\ \{c\} \\ \{b\} \\ \{a\} \\ \emptyset \\ \end{array} \\ \end{array}\)

Esta celosía es un álgebra booleana ya que es una celosía distributiva complementada.

Ejercicio\(\PageIndex{2}\)

1. Determinar el complemento de cada elemento de\(D_6\) in\(\left[D_6; \lor , \land \right]\text{.}\)
2. Repita la parte a usando la celosía del Ejemplo 13.2.2.
3. Repita la parte a usando la celosía en el Ejercicio 13.1.1.
4. ¿Las celosías están en las partes a, b y c álgebras booleanas? ¿Por qué?

Ejercicio\(\PageIndex{3}\)

Determinar cuáles de las celosías del Ejercicio 13.1.3 de la Sección 13.1 son álgebras booleanas.

Responder

a y g.

Ejercicio\(\PageIndex{4}\)

Dejar\(A = \{a, b\}\) y\(B = \mathcal{P}(A)\text{.}\)

1. Demostrar que\([B; \cup, \cap, \hspace{1 mm}^c ]\) es un álgebra booleana.
2. Escriba las tablas de operaciones para el álgebra booleana.

Ejercicio\(\PageIndex{5}\)

Se puede demostrar que la siguiente declaración,\(S\text{,}\) es válida para cualquier álgebra booleana\([B; \lor , \land, -]\):\((a \land b) = a\) si y solo si\(a \leq b\text{.}\)

1. Escribir el dual,\(S^*\text{,}\) de la declaración\(S\text{.}\)
2. Escribir el enunciado\(S\) y su dual,\(S^*\text{,}\) en el lenguaje de los conjuntos.
3. ¿Las afirmaciones de la parte b son verdaderas para todos los conjuntos?
4. Escribir el enunciado\(S\) y su dual,\(S^*\text{,}\) en el lenguaje de la lógica.
5. ¿Las afirmaciones en la parte d son ciertas para todas las proposiciones?

Responder

1. \(\displaystyle S^*:a \lor b= a \textrm{ if } a \geq b\)
2. El dual de\(S:A\cap B = A\textrm{ if }A \subseteq B\) es\(S^*:A \cup B = A\textrm{ if } A \supseteq B\)
3. Sí
4. El dual de\(S:p \land q\Leftrightarrow p\textrm{ }\textrm{ if } p\Rightarrow q\) es\(S^*:p \lor q\Leftrightarrow p \textrm{ if } q\Rightarrow p\)
5. Sí

Ejercicio\(\PageIndex{6}\)

Declarar la dualidad de:

1. \(a \lor (b \land a) = a\text{.}\)
2. \(a \lor \left(\overline{\left(\bar{b} \lor a\right) \land b}\right) = 1\text{.}\)
3. \(\left(\overline{a \land \bar{b}}\right) \land b = a\lor b\text{.}\)

Ejercicio\(\PageIndex{7}\)

Formular una definición para álgebras booleanas isomórficas.

Responder

\([B; \land, \lor, -]\)es isomórfico a\([B';\land, \lor, \tilde{}]\) si y solo si existe una función\(T:B \to B'\) tal que

1. \(T\)es una biyección;
2. \(\displaystyle T(a\land b)=T(a)\land T(b)\quad \textrm{ for} \textrm{ all } a,b\in B\)
3. \(\displaystyle T(a\lor b)=T(a)\lor T(b)\quad \textrm{ for} \textrm{ all } a, b \in B\)
4. \(T(\bar{a})=\tilde{T(a)}\quad \textrm{ for all } a\in B\text{.}\)

Ejercicio\(\PageIndex{8}\)

Para qué enteros positivos,\(n\text{,}\) ¿la celosía\([D_n,\mid]\) produce un álgebra booleana?