Section 6.3 Minsets
¶Subsection 6.3.1 Definition of Minsets
Let \(B_1\) and \(B_2\) be subsets of a set \(A\text{.}\) Notice that the Venn diagram of Figure 6.3.1 is naturally partitioned into the subsets \(A_1\text{,}\) \(A_2\text{,}\) \(A_3\text{,}\) and \(A_4\text{.}\) Further we observe that \(A_1\text{,}\) \(A_2\text{,}\) \(A_3\text{,}\) and \(A_4\) can be described in terms of \(B_1\) and \(B_2\) as follows:
| \(A_1=B_1\cap \overline{B_{2}}\) |
| \(A_2=B_1\cap B_2\) |
| \(A_3= \overline{B_{1}}\cap B_2\) |
| \(A_4= \overline{B_{1}}\cap \overline{B_{2}}\) |
Each \(A_i\) is called a minset generated by \(B_1\) and \(B_2\text{.}\) We note that each minset is formed by taking the intersection of two sets where each may be either \(B_k\) or its complement, \(\overline{B_{k}}\text{.}\) Note also, given two sets, there are \(2^{2}=4\) minsets.
Minsets are occasionally called minterms.
The reader should note that if we apply all possible combinations of the operations intersection, union, and complementation to the sets \(B_1\) and \(B_2\) of Figure 1, the smallest sets generated will be exactly the minsets, the minimum sets. Hence the derivation of the term minset.
Next, consider the Venn diagram containing three sets, \(B_1\text{,}\) \(B_2\text{,}\) and \(B_3\text{.}\) Draw it right now and count the regions! What are the minsets generated by \(B_1\text{,}\) \(B_2\text{,}\) and \(B_3\text{?}\) How many are there? Following the procedures outlined above, we note that the following are three of the \(2^3=8\) minsets. What are the others?
| \(B_1\cap B_2\cap \overline{B_{3}}\) |
| \(B_1\cap \overline{B_{2}}\cap B_3\) |
| \(B_1\cap \overline{B_{2}}\cap \overline{B_{3}}\) |
Definition 6.3.4. Minset.
Let \(\{B_1, B_2,\ldots,B_n\}\) be a set of subsets of set \(A\text{.}\) Sets of the form \(D_1\cap D_2\cap \cdots \cap D_n\text{,}\) where each \(D_i\) may be either \(B_i\) or \(\overline{B_{i}}\text{,}\) is called a minset generated by \(B_1\text{,}\) \(B_2\text{,...}\) and \(B_n\text{.}\)
Example 6.3.5. A concrete example of some minsets.
Consider the following concrete example. Let \(A = \{1, 2, 3, 4, 5, 6\}\) with subsets \(B_1 = \{1,3,5\}\) and \(B_2= \{1,2,3\}\text{.}\) How can we use set operations applied to \(B_1\) and \(B_2\) and produce a list of sets that contain elements of \(A\) efficiently without duplication? As a first attempt, we might try these three sets:
| \(B_1\cap B_2=\{1,3\}\) |
| \(\overline{B_{1}}=\{2,4,6\}\) |
| \(\overline{B_{2}}=\{4,5,6\}\text{.}\) |
We have produced all elements of \(A\) but we have 4 and 6 repeated in two sets. In place of \(\overline{B_{1}}\) and \(\overline{B_{2}}\text{,}\) let's try \(\overline{B_{1}}\cap B_2\) and \(B_1\cap \overline{B_{2}}\text{,}\) respectively:
| \(\overline{B_{1}}\cap B_2=\{2\}\) and |
| \(B_1\cap \overline{B_{2}}=\{5\}\text{.}\) |
We have now produced the elements 1, 2, 3, and 5 using \(B_1\cap B_2\text{,}\) \(\overline{B_{1}}\cap B_2\) and \(B_1\cap \overline{B_{2}}\) yet we have not listed the elements 4 and 6. Most ways that we could combine \(B_1\) and \(B_2\) such as \(B_1\cup B_2\) or \(B_1\cup \overline{B_{2}}\) will produce duplications of listed elements and will not produce both 4 and 6. However we note that \(\overline{B_{1}}\cap \overline{B_{2}}= \{4, 6\}\text{,}\) exactly the elements we need. Each element of \(A\) appears exactly once in one of the four minsets \(B_1\cap B_2\) , \(\overline{B_{1}}\cap B_2\text{,}\) \(B_1\cap \overline{B_{2}}\) and \(\overline{B_{1}}\cap \overline{B_{2}}\text{.}\) Hence, we have a partition of \(A\text{.}\)
Subsection 6.3.2 Properties of Minsets
Theorem 6.3.8. Minset Partition Theorem.
Let \(A\) be a set and let \(B_1\text{,}\) \(B_2\) \(\ldots\) , \(B_n\) be subsets of \(A\text{.}\) The set of nonempty minsets generated by \(B_1\text{,}\) \(B_2\) \(\ldots\) , \(B_n\) is a partition of \(A\text{.}\)
Proof.
The proof of this theorem is left to the reader.
One of the most significant facts about minsets is that any subset of \(A\) that can be obtained from \(B_1\text{,}\) \(B_2\) \(\ldots\text{,}\) \(B_n\text{,}\) using the standard set operations can be obtained in a standard form by taking the union of selected minsets.
Definition 6.3.9. Minset Normal Form.
A set is said to be in minset normal form when it is expressed as the union of zero or more distinct nonempty minsets.
Notes:
The union of zero sets is the empty set, \(\emptyset\text{.}\)
Minset normal form is also called canonical form.
Example 6.3.10. Another Concrete Example of Minsets.
Let \(U = \{-2,-1,0,1,2\}\text{,}\) \(B_1= \{0,1,2\}\text{,}\) and \(B_2= \{0,2\}\text{.}\) Then
| \(B_1\cap B_2=\{0,2\}\) |
| \(\overline{B_{1}}\cap B_2 = \emptyset\) |
| \(B_1\cap \overline{B_{2}} = \{1\}\) |
| \(\overline{B_{1}}\cap \overline{B_{2}} = \{-2,-1\}\) |
In this case, there are only three nonempty minsets, producing the partition \(\{\{0,2\},\{1\},\{-2,-1\}\}\text{.}\) An example of a set that could not be produced from just \(B_1\) and \(B_2\) is the set of even elements of \(U\text{,}\) \(\{-2,0,2\}\text{.}\) This is because \(-2\) and \(-1\) cannot be separated. They are in the same minset and any union of minsets either includes or excludes them both. In general, there are \(2^3= 8\) different minset normal forms because there are three nonempty minsets. This means that only 8 of the \(2^5=32\) subsets of \(U\) could be generated from any two sets \(B_1\) and \(B_2\text{.}\)
Exercises 6.3.3 Exercises for Section 6.3
¶1.
Consider the subsets \(A = \{1, 7, 8\}\text{,}\) \(B = \{1, 6, 9, 10\}\text{,}\) and \(C = \{1, 9, 10\}\text{,}\) where \(U = \{1,2, . . . , 10\}\text{.}\)
List the nonempty minsets generated by \(A, B, \textrm{ and } C\text{.}\)
How many elements of the power set of \(U\) can be generated by \(A\text{,}\) \(B\text{,}\) and \(C\text{?}\) Compare this number with \(\mid\mathcal{P}(U)\mid\text{.}\) Give an example of one subset that cannot be generated by \(A\text{,}\) \(B\text{,}\) and \(C\text{.}\)
\(\{1\}, \{2, 3, 4, 5\}, \{6\}, \{7, 8\}, \{9, 10\}\)
\(2^5\) , as compared with \(2^{10}\text{.}\) \(\{1, 2\}\) is one of the 992 sets that can't be generated.
2.
Partition \(\{1, 2, .... 9\}\) into the minsets generated by \(B_1= \{5, 6,7\}\text{,}\) \(B_2 = \{2, 4, 5, 9\}\text{,}\) and \(B_3 = \{3, 4, 5, 6, 8, 9\}\text{.}\)
How many different subsets of \(\{1, 2, . . . ,9\}\) can you create using \(B_1, B_2\text{,}\) and \(B_3\) with the standard set operations?
Do there exist subsets \(C_1, C_2, C_3\) whose minsets will generate every subset of \(\{1,2, . . . ,9\}\text{?}\)
3.
Partition the set of strings of 0's and 1's of length two or less, using the minsets generated by \(B_1=\{s \mid s \textrm{ has length } 2\}\text{,}\) and \(B_2= \{s \mid s \textrm{ starts with a } 0\}\text{.}\)
\(B_1= \{00, 01, 10, 11\}\) and \(B_2 = \{0, 00, 01\}\) generate minsets \(\{00, 01\}, \{0\}, \{10, 11\}\text{,}\) and \(\{\lambda , 1\}\text{.}\) Note: \(\lambda\) is the null string, which has length zero.
4.
Let \(B_1, B_2\text{,}\) and \(B_3\) be subsets of a universal set \(U\text{,}\)
Symbolically list all minsets generated by \(B_1, B_2\text{,}\) and \(B_3\text{.}\)
Illustrate with a Venn diagram all minsets obtained in part (a).
Express the following sets in minset normal form: \(\overline{B_{1}}\text{,}\) \(B_1\cap B_2\) , \(B_1\cup \overline{B_{2}}\text{.}\)
5.
Partition \(A = \{0, 1, 2, 3, 4, 5\}\) with the minsets generated by \(B_1= \{0, 2, 4\}\text{ }\)and \(B_2= \{1, 5\}\text{.}\)
How many different subsets of \(A\) can you generate from \(B_1 \textrm{ and } B_2\text{?}\)
\(B_1\cap B_2=\emptyset\text{,}\) \(B_1\cap \overline{B_{2}}=\{0,2,4\}\text{,}\) \(\overline{B_{1}}\cap B_2=\{1,5\}\text{,}\) \(\overline{B_{1}}\cap \overline{B_{2}}=\{3\}\)
\(2^3\text{,}\) since there are 3 nonempty minsets.
6.
If \(\left\{B_1, B_2, \ldots , B_n\right\}\) is a partition of \(A\text{,}\) how many minsets are generated by \(B_1, B_2, \ldots , B_n\text{?}\)
7.
Prove Theorem 6.3.8
Let \(a\in A\text{.}\) For each \(i\text{,}\) \(a\in B_i\text{,}\) or \(a\in \overline{B_i}\text{,}\) since \(B_i\cup \overline{B_i}=A\) by the complement law. Let \(D_i=B_i\) if \(a\in B_i\text{,}\) and \(D=\overline{B_i}\) otherwise. Since \(a\) is in each \(D_i\text{,}\) it must be in the minset \(D_1\cap D_2 \cdots \cap D_n\text{.}\) Now consider two different minsets \(M_1= D_1\cap D_2\cdots \cap D_n\text{,}\) and \(M_2=G_1\cap G_2\cdots \cap G_n\text{,}\) where each \(D_i\) and \(G_i\) is either \(B_i\) or \(\overline{B_i}\text{.}\) Since these minsets are not equal, \(D_i\neq G_i\text{,}\) for some \(i\text{.}\) Therefore, \(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{,}\) since two of the sets in the intersection are disjoint. Since every element of A is in a minset and the minsets are disjoint, the nonempty minsets must form a partition of A. \(\square\)
8.
Let \(S\) be a finite set of \(n\) elements. Let \(B_i\) ,, i = 1, 2, \ldots , \(k\) be nonempty subsets of \(S\text{.}\) There are \(2^{2^k}\) minset normal forms generated by the \(k\) subsets. The number of subsets of \(S\) is \(2^n\text{.}\) Since we can make \(2^{2^k} > 2^n\) by choosing \(k \geq \log _2 n\text{,}\) it is clear that two distinct minset normal-form expressions do not always equal distinct subsets of \(S\text{.}\) Even for \(k < \log _2 n\text{,}\) it may happen that two distinct minset normal-form expressions equal the same subset of \(S\text{.}\) Determine necessary and sufficient conditions for distinct normal-form expressions to equal distinct subsets of \(S\text{.}\)