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.4The Duality Principle

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}\). 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 \), \(\cap \) by \(\cup \), \(\emptyset \) by \(U\), \(U\) by \(\emptyset\), 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.

Subsection4.4.1Exercises for Section 4.4

1

State the dual of of each of the following:

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

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

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

Answer
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:

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

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

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

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

  2. Write out the definition of maxset normal form.

  3. Repeat Exercise 4.3.1.4 for maxsets.

Answer