Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

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:
  1. \(A \cup (B \cap A) = A\text{.}\)
  2. \(\displaystyle A \cup \left(\left(B^c \cup A\right) \cap B\right)^c = U\)
  3. \(\displaystyle \left(A \cup B^c\right)^c \cap B =A^c\cap B\)
Answer.
  1. \(\displaystyle A\cap (B\cup A)=A\)
  2. \(\displaystyle A \cap \left(\left(B^c\cap A\right)\cup B\right)^c=\emptyset\)
  3. \(\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.
Answer.
Let \(E\) be a true logical equivalence involving conjuction, disjunction, negation, contradiction and tautology (\(\land, \lor, \neg, \vec{0}, \vec{1}\text{,}\) resp.)). Then the logical equivalence \(E^*\) obtained by exchanging conjuction and disjuction (\(\land \leftrightarrow \lor\)), and exchanging contradiction and tautology (\(\vec{0} \leftrightarrow \vec{1}\)) is also true. Note that there is no simple duel for the conditional operator, but one can use the fact that \(p \rightarrow q\) is equivalent to \(\neg p \lor q\text{,}\) which would have dual \(\neg p \land q\text{.}\)

3.

Write the dual of each of the following:
  1. \(\displaystyle p\lor \neg ((\neg q\lor p)\land q)\Leftrightarrow 1\)
  2. \((\neg (p \land (\neg q )) \lor q) \Leftrightarrow (\neg p \lor q)\text{.}\)
Answer.
  1. \(\displaystyle p \land \neg ((\neg q \land p)\lor q) \Leftrightarrow 0\)
  2. \(\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.
Answer.
Definition 4.4.3. Maxset.
Let \(\{B_1, B_2,\ldots,B_n\}\) be a set of subsets of set \(A\text{.}\) Sets of the form \(S_1\cup S_2\cup \cdots \cup S_n\text{,}\) where each \(S_i\) may be either \(B_i\) or \(B_i^c\text{,}\) is called a maxset generated by \(B_1\text{,}\) \(B_2\text{,...}\) and \(B_n\text{.}\)
Note that the set of maxsets is not a partition of \(A\text{,}\) however one can prove that every set generated by the \(B_i\)’s is the intersection of maxsets.

5.

Let \(A = \{1,2, 3,4, 5, 6\}\) and let \(B_1 = \{1, 3, 5\}\) and \(B _2 = \{1,2, 3\}\text{.}\)
  1. 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?
  2. Write out the definition of maxset normal form.
  3. Repeat Exercise 4.3.3.4 for maxsets.
Answer.
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 ?
Answer.
The dual is \(A\cup ( B_1 \cap B_2\cap \dots \cap B_n) = (A \cup B_1) \cap (A \cup B_2 ) \cap \dots \cap (A\cup B_n)\text{.}\)
You have attempted of activities on this page.
PrevTopNext