$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## Section4.3Minsets

### Subsection4.3.1Definition of Minsets

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:

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

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

### Subsection4.3.2Properties of Minsets

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$, $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.9Minset 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.

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

### SubsectionExercises for Section 4.3

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

1. $\{1\}, \{2, 3, 4, 5\}, \{6\}, \{7, 8\}, \{9, 10\}$

2. $2^5$ , as compared with $2^{10}$. $\{1, 2\}$ is one of the 992 sets that can't be generated.

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

$B_1= \{00, 01, 10, 11\}$ and $B_2 = \{0, 00, 01\}$ generate minsets $\{00, 01\}, \{0\}, \{10, 11\}$, and $\{\lambda , 1\}$. Note: $\lambda$ is the null string, which has length zero.

###### 4

Let $B_1, B_2$, and $B_3$ be subsets of a universal set $U\text{,}$

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

1. $B_1\cap B_2=\emptyset$, $B_1\cap B_2^c=\{0,2,4\}$, $B_1^c\cap B_2=\{1,5\}$, $B_1^c\cap B_2^c=\{3\}$

2. $2^3$, 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$?

###### 7

Prove Theorem 4.3.8

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