ads Minsets

Section 4.3 Minsets

Subsection 4.3.1 Definition of Minsets

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:

described in detail following the image — 🔗
Figure 4.3.1. Venn Diagram of Minsets

🔗

Table 4.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} .

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?

🔗

Table 4.3.3. Three of the minsets generated by

B_{1},

B_{2},

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}

🔗

Definition 4.3.4. Minset.

🔗

Let

{B_{1}, B_{2}, \dots, B_{n}}

be a set of subsets of set

A .

Sets of the form

D_{1} \cap D_{2} \cap \dots \cap D_{n},

where each

D_{i}

may be either

B_{i}

B_{i}^{c},

is called a minset generated by

B_{1},

B_{2},...

and

B_{n} .

Example 4.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} .

How can we use set operations to and produce a partition of

A ?

As a first attempt, we might try these three sets:

Table 4.3.6.

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:

Table 4.3.7.

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}

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.

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},

B_{1} \cap B_{2}^{c}

and

B_{1}^{c} \cap B_{2}^{c} .

Hence, we have a partition of

A .

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

” The answer is

2^{number of nonempty minsets},

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 .

With only six elements in

A,

there could be six minsets, each containing a single element. In that case we could generate the whole power set of

A .

🔗

Subsection 4.3.2 Properties of Minsets

🔗

Theorem 4.3.8. Minset Partition Theorem.

🔗

Let

A

be a set and let

B_{1},

B_{2}

\dots

B_{n}

be subsets of

A .

The set of nonempty minsets generated by

B_{1},

B_{2}

\dots

B_{n}

is a partition of

A .

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},

B_{2}

\dots,

B_{n},

using the standard set operations can be obtained in a standard form by taking the union of selected minsets.

🔗

Definition 4.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 .$
Minset normal form is also called canonical form.

🔗

Definition 4.3.10. Compact Minset Notation.

🔗

Let

{B_{1}, B_{2}, \dots, B_{n}}

be a set of subsets of set

A .

b

is equal to 0 or 1 and

C

is any set, then

C^{(b)}

is defined to be

C

b = 1

and

C^{c}

b = 0 .

Then we can denote a minset compactly as an expression

M_{b_{1} b_{2} \dots b_{n}}

where

M_{b_{1} b_{2} \dots b_{n}} = B_{1}^{b_{1}} \cap B_{2}^{b_{2}} \cap \dots \cap B_{n}^{b_{n}}

Example 4.3.11. Another Concrete Example of Minsets.

Let

U = {- 2, - 1, 0, 1, 2},

B_{1} = {0, 1, 2},

and

B_{2} = {0, 2} .

Then

Table 4.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}} .

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

🔗

Exercises 4.3.3 Exercises

🔗

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, and C .$
How many elements of the power set of $U$ can be generated by $A,$ $B,$ and $C ?$ Compare this number with $∣ P (U) ∣ .$ Give an example of one subset that cannot be generated by $A,$ $B,$ and $C .$

Answer.

${1}, {2, 3, 4, 5}, {6}, {7, 8}, {9, 10}$
$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 ∣ s has length 2},

and

B_{2} = {s ∣ s starts with a 0} .

Answer.

B_{1} = {00, 01, 10, 11}

and

B_{2} = {0, 00, 01}

generate minsets

{00, 01}, {0}, {10, 11},

and

{λ, 1} .

Note:

λ

is the null string, which has length zero.

🔗

4.

🔗

Let

B_{1}, B_{2},

and

B_{3}

be subsets of a universal set

U,

🔗

Symbolically list all minsets generated by $B_{1}, B_{2},$ and $B_{3} .$
Illustrate with a Venn diagram all minsets obtained in part (a).
Express the following sets in minset normal form: $B_{1}^{c},$ $B_{1} \cap B_{2}$ , $B_{1} \cup B_{2}^{c} .$

🔗

5.

🔗

Partition $A = {0, 1, 2, 3, 4, 5}$ with the nonempty minsets generated by $B_{1} = {0, 2, 4}$ and $B_{2} = {1, 5} .$
How many different subsets of $A$ can you generate from $B_{1} and B_{2} ?$

Answer.

$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^{3},$ since there are 3 nonempty minsets.

🔗

6.

🔗

{B_{1}, B_{2}, \dots, B_{n}}

is a partition of

A,

how many minsets are generated by

B_{1}, B_{2}, \dots, B_{n} ?

🔗

7.

🔗

Prove Theorem 4.3.8

Answer.

Let

a \in A .

For each

i,

a \in B_{i},

a \in B_{i}^{c},

since

B_{i} \cup B_{i}^{c} = A

by the complement law. Let

D_{i} = B_{i}

a \in B_{i},

and

D_{i} = B_{i}^{c}

otherwise. Since

a

is in each

D_{i},

it must be in the minset

D_{1} \cap D_{2} \dots \cap D_{n} .

Now consider two different minsets

M_{1} = D_{1} \cap D_{2} \dots \cap D_{n},

and

M_{2} = G_{1} \cap G_{2} \dots \cap G_{n},

where each

D_{i}

and

G_{i}

is either

B_{i}

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} \dots \cap D_{n} \cap G_{1} \cap G_{2} \dots \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 .

◻

You have attempted 1 of 1 activities on this page.

Prev Top Next