Resulta que usted puede obtener con sólo $\lceil \lg n\rceil$ conjuntos, donde $\lg$ como de costumbre denota el logaritmo de la base de $2$. Me voy a dar una construcción, y demostrar que es óptimo.
Tenga en cuenta que usted puede construir todos los embarazos únicos con el conjunto de operaciones de la si y sólo si se puede construir todos los subconjuntos de a $[n]=\{1,\ldots,n\}$; puede ser útil pensar en éste como un equivalente de la meta.
Para cada una de las $i\ge 0$, vamos a $S_i$ ser el subconjunto de $[n-1]$ cuyo binario expansiones contienen un $1$ $i$- ésima posición. (No necesitamos incluir $n$ en cualquiera de nuestros conjuntos; es innecesario, ya que la unión de la $S_i$'s $[n-1]$, por lo que podemos obtener el singleton $\{n\}$ complementando.) Por lo $S_i$ es no vacío, precisamente, al $n-1\ge 2^i$, es decir,$i<\lg n$. Así, el vacío $S_i$'s están indexadas de $0,\ldots \lceil \lg n\rceil-1$.
Es fácil ver cómo llegar cualquier singleton $\{k\}$ de la $S_i$'s: mira el binario de expansión de $k$; si el $i$-ésimo bit de $k$$1$$k\in S_i$, de lo contrario $k\in \bar{S_i}$. La intersección de los juegos correctos para cada una de las $i$ deja el singleton $k$.
El hecho de que esta construcción es la óptima se sigue inmediatamente del hecho de que el libre Boolean algebra generada por $m$ elementos contiene $2^{2^m}$ elementos.
En un poco más de detalle: la colección de todos los subconjuntos de un conjunto dado forma una llamada álgebra Booleana, en virtud de la correspondencia $\wedge\leftrightarrow\cup$, $\vee\leftrightarrow\cap$, y $\neg\leftrightarrow\textrm{complement}$. Aproximadamente, el libre álgebra Booleana $FA(m)$ $m$ generadores es el "más grande" del álgebra Booleana que puede ser generado a partir de los generadores; los elementos de $FA(m)$ son todos de la no-equivalentes las expresiones Booleanas que pueden formarse a partir de los da $m$ elementos. Es un resultado estándar que $|FA(m)|=2^{2^m}$. Cualquier álgebra de boole $\mathcal{A}$, que puede ser generado por $m$ elementos es un cociente de $FA(m)$, por lo que, en particular, $\mathcal{A}$ no pueden tener más de $2^{2^m}$ elementos.
Para resumir, si $m$ subconjuntos de a $[n]$ puede generar todos los subconjuntos mediante el conjunto de operaciones, entonces debemos tener $2^{2^m}\ge 2^n$, es decir,$m\ge \lceil\lg n\rceil$. El dado de la construcción alcanza esta obligado.
Usted puede convertir esto en un bonito truco de cartas. Tener a alguien que piensa de una tarjeta, repartir la baraja en dos grupos, pídales que la pila de la tarjeta, recoger las tarjetas y repita 5 veces más. A continuación, puedes adivinar su tarjeta. El punto es que, en el $i$-ésima etapa, los dos pilas corresponden a los conjuntos de $S_i$$\bar{S_i}$.
