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:
Minsets generated by \(B_1\) and \(B_2\)
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{.}\)
Example4.3.5.A concrete example of some minsets.
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{.}\)
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.
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{.}\)
Minset normal form is also called canonical form.
Definition4.3.10.Compact Minset Notation.
Let \(\{B_1, B_2,\ldots,B_n\}\) be a set of subsets of set \(A\text{.}\) If \(b\) is equal to 0 or 1 and \(C\) is any set, then \(C^{(b)}\) is defined to be \(C\) if \(b=1\) and \(C^c\) if \(b=0\text{.}\) Then we can denote a minset compactly as an expression \(M_{b_1 b_2 \dots b_n}\) where
Example4.3.11.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
Table4.3.12.
\(M_{11}=B_1\cap B_2=\{0,2\}\)
\(M_{01}=B_1^c\cap B_2 = \emptyset\)
\(M_{10}=B_1\cap B_2^c = \{1\}\)
\(M_{00}=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{?}\)
Answer.
There are seven non-empty minsets. Using the compact notation they are \(M_{000}=\{1\}\text{,}\)\(M_{001}=\{3,8\}\text{,}\)\(M_{010}=\{2\}\text{,}\)\(M_{011}=\{4, 9\}\text{,}\)\(M_{100}=\{7\}\text{,}\)\(M_{101}=\{6\}\) and \(M_{111}=\{5\}\text{.}\)\(M_{110}=B_1 \cap B_2 \cap B_3^c\) is empty.
\(2^7=128\) different subsets can be generated.
There does not exist a set of three subsets that generates all subsets. This is because the maximum number of subsets that can be generated is \(2^8\text{.}\) Another way to look at it is that the minsets are a partition of \(\{1, 2, .... 9\}\) into eight minsets and at least one of those minsets must contain two or more elements. Those elements can’t be separated by any set operations. The logic behind this second way of looking at the problem is going to be formalized in Chapter 7 with the Pigeonhole Principle.
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{.}\)
Answer.
\(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: \(B_1^c\text{,}\)\(B_1\cap B_2\) , \(B_1\cup B_2^c\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\)
