Skip to main content
\(\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

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:

Minsets generated by \(B_1\) and \(B_2\)
Figure4.3.1Venn Diagram of Minsets
\(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\). 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\).

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

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

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

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

Answer
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\)?

Answer
6

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

7

Prove Theorem 4.3.6

Answer
8

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