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\), \(U\) by \(\emptyset\text{,}\) and leaving the complement unchanged.

#####
Definition4.4.1Duality 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\), \(\cap \to \cup\), \(\emptyset \to U\) , and \(U\to \emptyset\), then the statement \(S*\) is also true and it is called the dual of the statement \(S\).

#####
Example4.4.2Example 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\).

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

##### 1

State the dual of of each of the following:

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

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

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

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

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

\(\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 of each of the following:

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

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

Answer
\((p \land \neg (\neg q \land p)\lor g)) \Leftrightarrow 0\)

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

Find the maxsets generated by \(B_1\) and \(B_2\). 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.1.4 for maxsets.

AnswerThe maxsets are:

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

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

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

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

##### 6

What is the dual of the expression in Exercise 4.1.5.5 ?