4.3: Minsets

Definición de Minsets

Dejar\(B_1\) y\(B_2\) ser subconjuntos de un conjunto\(A\text{.}\) Observe que el diagrama de Venn de la Figura\(\PageIndex{1}\) está naturalmente dividido en los subconjuntos\(A_1\text{,}\)\(A_2\text{,}\)\(A_3\text{,}\) y\(A_4\text{.}\) Además observamos eso\(A_1\text{,}\)\(A_2\text{,}\)\(A_3\text{,}\) y se\(A_4\) puede describir en términos de\(B_1\) y de\(B_2\) la siguiente manera:

Figura\(\PageIndex{1}\): Venn Diagrama de Minsets

Tabla\(\PageIndex{1}\): Minsets generados por dos conjuntos

\(A_1=B_1\cap B_2^c\)

\(A_2=B_1\cap B_2\)

\(A_3=B_1^C\cap B_2\)

\(A_4=B_1^c\cap B_2^c\)

Cada\(A_i\) is called a minset generado por\(B_1\) and \(B_2\text{.}\) We note that each minset se forma tomando la intersección de dos conjuntos donde cada uno puede ser cualquiera de los\(B_k\) or its complement, \(B_k^c\text{.}\) Note also, given two sets, there are \(2^{2}=4\) minsets.

Ocasionalmente, los minsets se llaman minterms.

El lector debe tener en cuenta que si aplicamos todas las combinaciones posibles de intersección de operaciones, unión y complementación a los conjuntos\(B_1\) y\(B_2\) de Figura\(\PageIndex{1}\), los conjuntos más pequeños generados serán exactamente los minsets, los conjuntos mínimos. De ahí la derivación del término minset.

A continuación, considera el diagrama de Venn que contiene tres conjuntos,\(B_1\text{,}\)\(B_2\text{,}\) y ¡\(B_3\text{.}\)Dibuja ahora mismo y cuenta las regiones! ¿Cuáles son los minsets generados por\(B_1\text{,}\)\(B_2\text{,}\) y\(B_3\text{?}\) cuántos hay? Siguiendo los procedimientos señalados anteriormente, observamos que los siguientes son tres de los\(2^3=8\) minsets. ¿Cuáles son los demás?

Tabla\(\PageIndex{2}\): Tres de las minsets generadas por\(B_1\),\(B_2\), y\(B_3\)

\(B_1\cap B_2\cap B_3^c\)

\(B_1\cap B_2^c\cap B_3\)

\(B_1\cap B_2^c\cap B_3^c\)

Definición \(\PageIndex{1}\): Minset

Dejar\(\{B_1, B_2,\ldots,B_n\}\) ser un conjunto de subconjuntos de\(A\text{.}\) conjuntos conjuntos de la forma\(D_1\cap D_2\cap \cdots \cap D_n\text{,}\) donde cada uno\(D_i\) puede ser\(B_i\) o\(B_i^c\text{,}\) se llama un minset generado por\(B_1\text{,}\)\(B_2\text{,...}\) y\(B_n\text{.}\)

Ejemplo\(\PageIndex{1}\): A Concrete Example of Some Minsets

Considera el siguiente ejemplo concreto. Dejar\(A = \{1, 2, 3, 4, 5, 6\}\) con subconjuntos\(B_1 = \{1,3,5\}\) y\(B_2= \{1,2,3\}\text{.}\) cómo podemos usar operaciones de conjunto aplicadas a y producir una partición de\(A\text{?}\) Como primer intento, podríamos probar estos tres conjuntos:

Mesa\(\PageIndex{3}\)

\(B_1\cap B_2=\{1,3\}\)

\(B_1^c=\{2,4,6\}\)

\(B_2^c=\{4,5,6\}\text{.}\)

Hemos producido todos los elementos de\(A\) pero tenemos 4 y 6 repetidos en dos series. En lugar de\(B_1^c\) y\(B_2^c\text{,}\) vamos a tratar\(B_1^c\cap B_2\) y\(B_1\cap B_2^c\text{,}\) respectivamente:

Mesa\(\PageIndex{4}\)

\(B_1^c\cap B_2=\{2\}\)y

\(B_1\cap B_2^c=\{5\}\text{.}\)

Ahora hemos producido los elementos 1, 2, 3 y 5 usando\(B_1\cap B_2\text{,}\)\(B_1^c\cap B_2\) y\(B_1\cap B_2^c\) sin embargo no hemos enumerado los elementos 4 y 6. La mayoría de las formas en las que podríamos combinar\(B_1\) y\(B_2\) como\(B_1\cup B_2\) o\(B_1\cup B_2^c\) producirán duplicaciones de elementos listados y no producirán tanto 4 como 6. Sin embargo observamos que\(B_1^c\cap B_2^c= \{4, 6\}\text{,}\) exactamente los elementos que necesitamos.

Después de experimentar más, podríamos llegar a la conclusión de que cada elemento de\(A\) aparece exactamente una vez en uno de los cuatro minsets\(B_1\cap B_2\),\(B_1^c\cap B_2\text{,}\)\(B_1\cap B_2^c\) y\(B_1^c\cap B_2^c\text{.}\) por lo tanto, tenemos una partición de\(A\text{.}\) De hecho esta es la partición más fina de\(A\) en que todas las demás particiones nos podría generar consistir en uniones seleccionadas de estos minsets.

En este punto, podríamos preguntar y poder responder a la pregunta “A partir de cuántos subconjuntos diferentes de nuestro universo podemos generar\(B_1\) y\(B_2\text{?}\)” La respuesta es\(2^{\textrm{number of nonempty minsets}}\text{,}\) cual es\(2^4=16\) en este caso. Observe que en general, sería imposible encontrar dos conjuntos a partir de los cuales podríamos generar todos los subconjuntos\(A=\{1, 2, 3, 4, 5, 6\}\) ya que nunca habrá más de cuatro minsets no vacíos. Si nos permitiéramos tres subconjuntos y tratáramos de generar todos los conjuntos a partir de ellos, entonces el número de minsets sería\(2^3 =8\text{.}\) Con solo seis elementos en podría\(A\text{,}\) haber seis minsets, cada uno conteniendo un solo elemento. En ese caso podríamos generar todo el conjunto de potencia de\(A\text{.}\)

Propiedades de Minsets

Teorema\(\PageIndex{1}\): Minset Partition Theorem

Dejar\(A\) ser un conjunto y dejar\(B_1\text{,}\)\(B_2\)\(\ldots\),\(B_n\) ser subconjuntos de\(A\text{.}\) El conjunto de minsets no vacíos generados por\(B_1\text{,}\)\(B_2\)\(\ldots\),\(B_n\) es una partición de\(A\text{.}\)

Prueba

La prueba de este teorema se deja al lector.

Uno de los hechos más significativos sobre minsets es que cualquier subconjunto de los\(A\) que se puede obtener\(B_1\text{,}\)\(B_2\)\(\ldots\text{,}\)\(B_n\text{,}\) usando las operaciones de conjunto estándar se puede obtener en una forma estándar tomando la unión de minsets seleccionados.

Definición \(\PageIndex{2}\): Minset Normal Form

Se dice que un conjunto está en forma normal minset cuando se expresa como la unión de cero o más minsets distintos no vacíos.

Nota\(\PageIndex{1}\)

• La unión de conjuntos cero es el conjunto vacío,\(\emptyset\text{.}\)
• La forma normal de minset también se llama forma canónica.

Ejemplo\(\PageIndex{2}\): Another Concrete Example of Minsets

Let\(U = \{-2,-1,0,1,2\}\text{,}\)\(B_1= \{0,1,2\}\text{,}\) y\(B_2= \{0,2\}\text{.}\) Entonces

Mesa\(\PageIndex{5}\)

\(B_1\cap B_2=\{0,2\}\)

\(B_1^c\cap B_2 = \emptyset\)

\(B_1\cap B_2^c = \{1\}\)

\(B_1^c\cap B_2^c = \{-2,-1\}\)

En este caso, sólo hay tres minsets no vacíos, produciendo la partición\(\{\{0,2\},\{1\},\{-2,-1\}\}\text{.}\) Un ejemplo de un conjunto que no se pudo producir a partir de solo\(B_1\) y\(B_2\) es el conjunto de elementos pares de\(U\text{,}\)\(\{-2,0,2\}\text{.}\) Esto es porque\(-2\) y\(-1\) no se puede separar. Están en el mismo minset y cualquier unión de minsets los incluye o excluye a ambos. En general, hay\(2^3= 8\) diferentes formas normales minset porque hay tres minsets no vacíos. Esto significa que solo 8 de los\(2^5=32\) subconjuntos de\(U\) podrían generarse a partir de dos conjuntos cualesquiera\(B_1\) y\(B_2\text{.}\)

Ejercicios

Ejercicio\(\PageIndex{1}\)

Considere los subconjuntos\(A = \{1, 7, 8\}\text{,}\)\(B = \{1, 6, 9, 10\}\text{,}\) y\(C = \{1, 9, 10\}\text{,}\) dónde\(U = \{1,2, . . . , 10\}\text{.}\)

1. Enumere los minsets no vacíos generados por\(A, B, \textrm{ and } C\text{.}\)
2. Cuántos elementos del conjunto de potencia de\(U\) pueden ser generados por\(A\text{,}\)\(B\text{,}\) y\(C\text{?}\) Comparar este número con\(\mid\mathcal{P}(U)\mid\text{.}\) Dar un ejemplo de un subconjunto que no puede ser generado por\(A\text{,}\)\(B\text{,}\) y\(C\text{.}\)

Contestar

1. \(\displaystyle \{1\}, \{2, 3, 4, 5\}, \{6\}, \{7, 8\}, \{9, 10\}\)
2. \(2^5\), en comparación con\(2^{10}\text{.}\)\(\{1, 2\}\) es uno de los 992 conjuntos que no se pueden generar.

Ejercicio\(\PageIndex{2}\)

1. Partición\(\{1, 2, .... 9\}\) en los minsets generados por\(B_1= \{5, 6,7\}\text{,}\)\(B_2 = \{2, 4, 5, 9\}\text{,}\) y\(B_3 = \{3, 4, 5, 6, 8, 9\}\text{.}\)
2. ¿Cuántos subconjuntos diferentes\(\{1, 2, . . . ,9\}\) se pueden crear usando\(B_1, B_2\text{,}\) y\(B_3\) con las operaciones de conjunto estándar?
3. ¿Existen subconjuntos\(C_1, C_2, C_3\) cuyos minsets generarán cada subconjunto de\(\{1,2, . . . ,9\}\text{?}\)

Ejercicio\(\PageIndex{3}\)

Particionar el conjunto de cadenas de 0 y 1 de longitud dos o menos, usando los minsets generados por\(B_1=\{s \mid s \textrm{ has length } 2\}\text{,}\) y\(B_2= \{s \mid s \textrm{ starts with a } 0\}\text{.}\)

Contestar

\(B_1= \{00, 01, 10, 11\}\)y\(B_2 = \{0, 00, 01\}\) generar minsets\(\{00, 01\}, \{0\}, \{10, 11\}\text{,}\) y\(\{\lambda , 1\}\text{.}\) Nota:\(\lambda\) es la cadena nula, que tiene longitud cero.

Ejercicio \(\PageIndex{4}\)

Dejar\(B_1, B_2\text{,}\) y\(B_3\) ser subconjuntos de un conjunto universal\(U\text{,}\)

1. Listar simbólicamente todos los minsets generados por\(B_1, B_2\text{,}\) y\(B_3\text{.}\)
2. Ilustrar con un diagrama de Venn todos los minsets obtenidos en la parte (a).
3. Exprese los siguientes conjuntos en forma normal minset:\(B_1^c\text{,}\)\(B_1\cap B_2\),\(B_1\cup B_2^c\text{.}\)

Ejercicio\(\PageIndex{5}\)

1. Partición\(A = \{0, 1, 2, 3, 4, 5\}\) con los minsets generados por\(B_1= \{0, 2, 4\}\text{ }\) y\(B_2= \{1, 5\}\text{.}\)
2. ¿Cuántos subconjuntos diferentes\(A\) puedes generar a partir de\(B_1 \textrm{ and } B_2\text{?}\)

Contestar

1. \(B_1\cap B_2=\emptyset\text{,}\) \(B_1\cap B_2^c=\{0,2,4\}\text{,}\) \(B_1^c\cap B_2=\{1,5\}\text{,}\) \(B_1^c\cap B_2^c=\{3\}\)
2. \(2^3\text{,}\)ya que hay 3 minsets no vacíos.

Ejercicio\(\PageIndex{6}\)

Si\(\left\{B_1, B_2, \ldots , B_n\right\}\) es una partición de\(A\text{,}\) cuántos minsets son generados por\(B_1, B_2, \ldots , B_n\text{?}\)

Ejercicio\(\PageIndex{7}\)

Demostrar teorema\(\PageIndex{1}\).

Contestar

Dejar\(a\in A\text{.}\) Para cada uno\(i\text{,}\)\(a\in B_i\text{,}\) o\(a\in B_i{}^c\text{,}\) desde\(B_i\cup B_i{}^c=A\) por la ley del complemento. Dejar\(D_i=B_i\) si\(a\in B_i\text{,}\) y de\(D_i=B_i{}^c\) otra manera. Ya que\(a\) está en cada uno\(D_i\text{,}\) debe estar en el minset\(D_1\cap D_2 \cdots \cap D_n\text{.}\) Ahora considera dos minsets diferentes\(M_1= D_1\cap D_2\cdots \cap D_n\text{,}\) y\(M_2=G_1\cap G_2\cdots \cap G_n\text{,}\) donde cada uno\(D_i\) y\(G_i\) es\(B_i\) o\(B_i{}^c\text{.}\) ya que estos minsets no son iguales,\(D_i\neq G_i\text{,}\) para algunos\(i\text{.}\) Por lo tanto, \(M_1\cap M_2=D_1\cap D_2 \cdots \cap D_n\cap G_1\cap G_2\cdots \cap G_n=\emptyset\text{,}\)ya que dos de los conjuntos en la intersección son disjuntos. Dado que cada elemento de\(A\) está en un minset y los minsets son disjuntos, los minsets no vacíos deben formar una partición de\(A\text{.}\)\(\square\)

Ejercicio\(\PageIndex{8}\)

Let\(S\) Ser un conjunto finito de\(n\) elementos. Dejar\(B_i\text{,}\)\(i = 1, 2, \ldots , k\) ser subconjuntos no vacíos de\(S\text{.}\) Hay\(2^{2^k}\) minset formas normales generadas por los\(k\) subconjuntos. El número de subconjuntos de\(S\) es\(2^n\text{.}\) Dado que podemos hacer\(2^{2^k} > 2^n\) eligiendo está\(k \geq \log _2 n\text{,}\) claro que dos expresiones minset de forma normal distintas no siempre son iguales a subconjuntos distintos de\(S\text{.}\) Incluso\(k < \log _2 n\text{,}\) porque puede suceder que dos expresiones de forma normal minset distintas sean iguales el mismo subconjunto de\(S\text{.}\) Determinar condiciones necesarias y suficientes para que distintas expresiones de forma normal sean iguales a subconjuntos distintos de\(S\text{.}\)