## Section 4.4 The Duality Principle

### Subsection 4.4.1

In Section 4.2, we observed that each of the Table 4.2.1 labeled 1 through 9 had an analogue \(1^{\prime}\) through \(9^{\prime}\text{.}\) We notice that each of the laws in one column can be obtained from the corresponding law in the other column by replacing \(\cup\) by \(\cap \text{,}\) \(\cap \) by \(\cup \text{,}\) \(\emptyset \) by \(U\text{,}\) \(U\) by \(\emptyset\text{,}\) and leaving the complement unchanged.

###### Definition 4.4.1. Duality Principle for Sets.

Let \(S\) be any identity involving sets and the operations complement, intersection and union. If \(S*\) is obtained from \(S\) by making the substitutions \(\cup \to \cap\text{,}\) \(\cap \to \cup\text{,}\) \(\emptyset \to U\) , and \(U\to \emptyset\text{,}\) then the statement \(S*\) is also true and it is called the dual of the statement \(S\text{.}\)

###### Example 4.4.2. Example of a dual.

The dual of \((A \cap B) \cup \left(A \cap B^c \right) = A\) is \((A\cup B)\cap \left(A\cup B^c\right)=A\text{.}\)

One should not underestimate the importance of this concept. It gives us a whole second set of identities, theorems, and concepts. For example, we can consider the dual of *minsets* and *minset normal form* to obtain what is called *maxsets* and *maxset normal form*.

### Exercises 4.4.2 Exercises

###### 1.

State the dual of each of the following:

\(A \cup (B \cap A) = A\text{.}\)

\(\displaystyle A \cup \left(\left(B^c \cup A\right) \cap B\right)^c = U\)

\(\displaystyle \left(A \cup B^c\right)^c \cap B =A^c\cap B\)

\(\displaystyle A\cap (B\cup A)=A\)

\(\displaystyle A \cap \left(\left(B^c\cap A\right)\cup B\right)^c=\emptyset\)

\(\displaystyle \left(A\cap B^c\right)^c\cup B=A^c\cup B\)

###### 2.

Examine Table 3.4.3 and then write a description of the principle of duality for logic.

###### 3.

Write the dual of each of the following:

\(\displaystyle p\lor \neg ((\neg q\lor p)\land q)\Leftrightarrow 1\)

\((\neg (p \land (\neg q ))) \lor q\Leftrightarrow (\neg p \lor q)\text{.}\)

\(\displaystyle (p \land \neg (\neg q \land p)\lor q) \Leftrightarrow 0\)

\(\displaystyle (\neg (p \lor (\neg q)))\land q \Leftrightarrow ((\neg p) \land q)\)

###### 4.

Use the principle of duality and the definition of minset to write the definition of maxset.

###### 5.

Let \(A = \{1,2, 3,4, 5, 6\}\) and let \(B_1 = \{1, 3, 5\}\) and \(B _2 = \{1,2, 3\}\text{.}\)

Find the maxsets generated by \(B_1\) and \(B_2\text{.}\) Note the set of maxsets does not constitute a partition of \(A\text{.}\) Can you explain why?

Write out the definition of maxset normal form.

Repeat Exercise 4.3.3.4 for maxsets.

The maxsets are:

\(\displaystyle B_1\cup B_2=\{1,2,3,5\}\)

\(\displaystyle B_1\cup B_2{}^c=\{1,3,4,5,6\}\)

\(\displaystyle B_1{}^c\cup B_2=\{1,2,3,4,6\}\)

\(\displaystyle B_1{}^c\cup B_2{}^c=\{2,4,5,6\}\)

They do not form a partition of \(A\) since it is not true that the intersection of any two of them is empty. A set is said to be in maxset normal form when it is expressed as the intersection of distinct nonempty maxsets or it is the universal set \(U\text{.}\)

###### 6.

What is the dual of the expression in Exercise 4.1.5.5 ?