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\), \(A_2\), \(A_3\), and \(A_4\). Further we observe that \(A_1\), \(A_2\), \(A_3\), and \(A_4\) can be described in terms of \(B_1\) and \(B_2\) as follows:

\(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\)

Table4.3.2Minsets generated by two sets

Each \(A_i\) is called a minset generated by \(B_1\) and \(B_2\). 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\). 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 4.3.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\), \(B_2\), and \(B_3\). Draw it right now and count the regions! What are the minsets generated by \(B_1\), \(B_2\), and \(B_3\)? 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 B_3^c\)

\(B_1\cap B_2^c\cap B_3\)

\(B_1\cap B_2^c\cap B_3^c\)

Table4.3.3Three of the minsets generated by \(B_1\), \(B_2\), and \(B_3\)

Definition4.3.4Minset

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\), where each \(D_i\) may be either \(B_i\) or \(B_i^c\), is called a minset generated by \(B_1\), \(B_2\),... and \(B_n\).

Example4.3.5A 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\}\). 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\}\)

\(B_1^c=\{2,4,6\}\)

\(B_2^c=\{4,5,6\}\).

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\), let's try \(B_1^c\cap B_2\) and \(B_1\cap B_2^c\), respectively:

\(B_1^c\cap B_2=\{2\}\) and

\(B_1\cap B_2^c=\{5\}\).

We have now produced the elements 1, 2, 3, and 5 using \(B_1\cap B_2\), \(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\}\), exactly the elements we need. Each element of \(A\) appears exactly once in one of the four minsets \(B_1\cap B_2\) , \(B_1^c\cap B_2\), \(B_1\cap B_2^c\) and \(B_1^c\cap B_2^c\). Hence, we have a partition of \(A\text{.}\)

Theorem4.3.6Minset Partition Theorem

Let \(A\) be a set and let \(B_1\), \(B_2\) \(\ldots\) , \(B_n\) be subsets of \(A\text{.}\) The set of nonempty minsets generated by \(B_1\), \(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\), \(B_2\) \(\ldots\), \(B_n\), using the standard set operations can be obtained in a standard form by taking the union of selected minsets.

Definition4.3.7Minset 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.

Example4.3.8Another Concrete Example of Minsets

Let \(U = \{-2,-1,0,1,2\}\), \(B_1= \{0,1,2\}\), and \(B_2= \{0,2\}\). Then

\(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\}\}\). 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\}\). 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\).

Subsection4.3.1Exercises for Section 4.3¶ permalink

1

Consider the subsets \(A = \{1, 7, 8\}\), \(B = \{1, 6, 9, 10\}\), and \(C = \{1, 9, 10\}\), where \(U = \{1,2, . . . , 10\}\).

List the nonempty minsets generated by \(A, B, \textrm{ and } C\).

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\). 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}\). \(\{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\}\), \(B_2 = \{2, 4, 5, 9\}\), and \(B_3 = \{3, 4, 5, 6, 8, 9\}\).

How many different subsets of \(\{1, 2, . . . ,9\}\) can you create using \(B_1, B_2\), 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\}\)?

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\}\), and \(B_2= \{s \mid s \textrm{ starts with a } 0\}\).

Let \(a\in A\). For each \(i\), \(a\in B_i\), or \(a\in B_i{}^c\), since \(B_i\cup B_i{}^c=A\) by the complement law. Let \(D_i=B_i\) if \(a\in B_i\), and \(D=B_i{}^c\) otherwise. Since \(a\) is in each \(D_i\), it must be in the minset \(D_1\cap D_2 \cdots \cap D_n\). Now consider two different minsets \(M_1= D_1\cap D_2\cdots \cap D_n\), and \(M_2=G_1\cap G_2\cdots \cap G_n\), where each \(D_i\) and \(G_i\) is either \(B_i\) or \(B_i{}^c\). Since these minsets are not equal, \(D_i\neq G_i\), for some \(i\). 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\), 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\). Since we can make \(2^{2^k} > 2^n\) by choosing \(k \geq \log _2 n\), 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\), 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{.}\)