1
$\begingroup$

Are there any general non-trivial methods for solving the following problem?

Suppose one has a collection of subsets $\mathcal{C} \subseteq \mathcal{P}\mathcal{P}\{1,\dots,n\}$. They may be viewed as generating a sub boolean algebra $\langle\mathcal{C}\rangle \subseteq \mathsf{2}^{2^n}$ of the free boolean algebra on $n$ generators.

Let $G \subseteq \langle\mathcal{C}\rangle$ be a subset whose closure under unions contains $\mathcal{C}$. I would like to compute the minimum cardinality over all such sets $G$.

For example:

  1. If $\mathcal{C}$ consists of the $2^n$ atoms then the answer is $2^n$.

  2. If $\mathcal{C}$ consists of the $2^n$ co-atoms then the answer is $\leq 2n$ by choosing $p_1,\neg p_1,\dots,p_n,\neg p_n$.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.