Let $B_1$ and $B_2$ be subsets of a set $A$. 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:

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?

##### Definition4.3.4Minset

Let $\{B_1, B_2,\ldots,B_n\}$ be a set of subsets of set $A$. 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:

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:

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$.

##### Proof

One of the most significant fact 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$.

• 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

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$, $\{-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\}$.

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

2. How many elements of the power set of $U$ can be generated by $A$, $B$, and $C$? Compare this number with $\mid\mathcal{P}(U)\mid$. Give an example of one subset that cannot be generated by $A$, $B$, and $C$.

##### 2

1. 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\}$.

2. How many different subsets of $\{1, 2, . . . ,9\}$ can you create using $B_1, B_2$, and $B_3$ with the standard set operations?

3. 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\}$.

##### 4

Let $B_1, B_2$, and $B_3$ be subsets of a universal set $U$,

1. Symbolically list all minsets generated by $B_1, B_2$, and $B_3$.

2. Illustrate with a Venn diagram all minsets obtained in part (a).

3. Express the following sets in minset normal form: $B_1^c$, $B_1\cap B_2$ , $B_1\cup B_2^c$.

##### 5

1. Partition $A = \{0, 1, 2, 3, 4, 5\}$ with the minsets generated by $B_1= \{0, 2, 4\}\text{ }$and $B_2= \{1, 5\}$.

2. How many different subsets of $A$ can you generate from $B_1 \textrm{ and } B_2$?

If $\left\{B_1, B_2, \ldots , B_n\right\}$ is a partition of $A$, how many minsets are generated by $B_1, B_2, \ldots , B_n$?
Let $S$ be a finite set of $n$ elements. Let $B_i$ ,, i = 1, 2, \ldots , $k$ be nonempty subsets of $S$. 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$. Even for $k < \log _2 n$, it may happen that two distinct minset normal-form expressions equal the same subset of $S$. Determine necessary and sufficient conditions for distinct normal-form expressions to equal distinct subsets of $S$.