Let \(B_1\) and \(B_2\) be subsets of a set \(A\text{.}\) Notice that the Venn diagram of Figure 4.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:
Figure4.3.1.Venn Diagram of Minsets
Table4.3.2.Minsets generated by two sets
\(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\)
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, \(B_k^c\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?
Table4.3.3.Three of the minsets generated by \(B_1\text{,}\)\(B_2\text{,}\) and \(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\)
Definition4.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 \(B_i^c\text{,}\) is called a minset generated by \(B_1\text{,}\)\(B_2\text{,...}\) and \(B_n\text{.}\)
Consider the following 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 to and produce a partition of \(A\text{?}\) As a first attempt, we might try these three sets:
Table4.3.6.
\(B_1\cap B_2=\{1,3\}\)
\(B_1^c=\{2,4,6\}\)
\(B_2^c=\{4,5,6\}\text{.}\)
We have produced all elements of \(A\) but we have 4 and 6 repeated in two sets. In place of \(B_1^c\) and \(B_2^c\text{,}\) let’s try \(B_1^c\cap B_2\) and \(B_1\cap B_2^c\text{,}\) respectively:
Table4.3.7.
\(B_1^c\cap B_2=\{2\}\) and
\(B_1\cap B_2^c=\{5\}\text{.}\)
We have now produced the elements 1, 2, 3, and 5 using \(B_1\cap B_2\text{,}\)\(B_1^c\cap B_2\) and \(B_1\cap B_2^c\) 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 B_2^c\) will produce duplications of listed elements and will not produce both 4 and 6. However we note that \(B_1^c\cap B_2^c= \{4, 6\}\text{,}\) exactly the elements we need.
After more experimenting, we might reach a conclusion that each element of \(A\) appears exactly once in one of the four minsets \(B_1\cap B_2\) , \(B_1^c\cap B_2\text{,}\)\(B_1\cap B_2^c\) and \(B_1^c\cap B_2^c\text{.}\) Hence, we have a partition of \(A\text{.}\) In fact this is the finest partition of \(A\) in that all other partitions we could generate consist of selected unions of these minsets.
At this point, we might ask and be able to answer the question “How many different subsets of our universe can we generate from \(B_1\) and \(B_2\text{?}\)” The answer is \(2^{\textrm{number of nonempty minsets}}\text{,}\) which is \(2^4=16\) in this case. Notice that in general, it would be impossible to find two sets from which we could generate all subsets of \(A=\{1, 2, 3, 4, 5, 6\}\) since there will never be more than four nonempty minsets. If we allowed ourselves three subsets and tried to generat all sets from them, then the number of minsets would be \(2^3 =8\text{.}\) With only six elements in \(A\text{,}\) there could be six minsets, each containing a single element. In that case we could generate the whole power set of \(A\text{.}\)
Subsection4.3.2Properties of Minsets
Theorem4.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{.}\)
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.
Definition4.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{.}\)
Let \(U = \{-2,-1,0,1,2\}\text{,}\)\(B_1= \{0,1,2\}\text{,}\) and \(B_2= \{0,2\}\text{.}\) Then
Table4.3.11.
\(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\}\)
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{.}\)
Exercises4.3.3Exercises
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{.}\)
\(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{.}\)
Let \(a\in A\text{.}\) For each \(i\text{,}\)\(a\in B_i\text{,}\) or \(a\in B_i{}^c\text{,}\) since \(B_i\cup B_i{}^c=A\) by the complement law. Let \(D_i=B_i\) if \(a\in B_i\text{,}\) and \(D_i=B_i{}^c\) 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 \(B_i{}^c\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\text{.}\)\(\square\)
8.
Let \(S\) be a finite set of \(n\) elements. Let \(B_i\text{,}\)\(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{.}\)
