Discrete Mathematics Study Center

Membership Tables

We combine sets in much the same way that we combined propositions. Asking if an element $x$ is in the resulting set is like asking if a proposition is true. Note that $x$ could be in any of the original sets.

What does the set $A \cup (B \cap C)$ look like? We use $1$ to denote the presence of some element $x$ and $0$ to denote its absence.

$\begin{array}{ccc|cc} A & B & C & B \cap C & A \cup (B \cap C) \\\hline 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array}$

This is a membership table. It can be used to draw the Venn diagram by shading in all regions that have a $1$ in the final column. The regions are defined by the left-most columns.

Venn diagram for the above membership table

We can also use membership tables to test if two sets are equal. Here are two methods of showing if $\overline{A \cap B} = \overline{A} \cup \overline{B}$ :

Showing each side is a subset of the other: $\begin{array}{lll} x \in \overline{A \cap B} & \rightarrow & x \notin A \cap B \\ & \rightarrow & \neg(x \in A \cap B) \\ & \rightarrow & \neg(x \in A \land x \in B) \\ & \rightarrow & \neg(x \in A) \lor \neg(x \in B) \\ & \rightarrow & x \notin A \lor x \notin B \\ & \rightarrow & x \in \overline{A} \lor x \in \overline{B} \\ & \rightarrow & x \in \overline{A} \cup \overline{B} \end{array}$ $\begin{array}{lll} x \in \overline{A} \cup \overline{B} & \rightarrow & x \notin A \lor x \notin B \\ & \rightarrow & \neg(x \in A) \lor \neg(x \in B) \\ & \rightarrow & \neg(x \in A \land x \in B) \\ & \rightarrow & \neg(x \in A \cap B) \\ & \rightarrow & x \notin A \cap B \\ & \rightarrow & x \in \overline{A \cap B} \end{array}$
Using membership tables: $\begin{array}{ccc|ccccc} A & B & C & A \cap B & \bf \overline{A \cap B} & \overline{A} & \overline{B} & \bf \overline{A} \cup \overline{B} \\\hline 1 & 1 & 1 & 1 & \bf0 & 0 & 0 & \bf0 \\ 1 & 1 & 0 & 1 & \bf0 & 0 & 0 & \bf0 \\ 1 & 0 & 1 & 0 & \bf1 & 0 & 1 & \bf1 \\ 1 & 0 & 0 & 0 & \bf1 & 0 & 1 & \bf1 \\ 0 & 1 & 1 & 0 & \bf1 & 1 & 0 & \bf1 \\ 0 & 1 & 0 & 0 & \bf1 & 1 & 0 & \bf1 \\ 0 & 0 & 1 & 0 & \bf1 & 1 & 1 & \bf1 \\ 0 & 0 & 0 & 0 & \bf1 & 1 & 1 & \bf1 \\ \end{array}$ Since the columns corresponding to the two sets match, they are equal.

It is not sufficient to simply draw the Venn diagrams for two sets to show that they are equal: you need to show why your Venn diagram is correct (typically with a membership table).

There is an additional way to prove two sets are equal, and that is to use set identities. In the following list, assume $A$ and $B$ are sets drawn from a universe $U$ .

Identity Law: $A \cup \emptyset = A$ , $A \cap U = A$
Idempotent Law: $A \cup A = A$ , $A \cap A = A$
Domination Law: $A \cup U = U$ , $A \cap \emptyset = \emptyset$
Complementation Law: $\overline{\overline{A}} = A$
Commutative Law: $A \cup B = B \cup A$ , $A \cap B = B \cap A$
Associative Law: $A \cup (B \cup C) = (A \cup B) \cup C$ , $A \cap (B \cap C) = (A \cap B) \cap C$
Distributive Law: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ , $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
Absorption Law: $A \cup (A \cap B) = A$ and $A \cap (A \cup B) = A$
De Morgan's Law: $\overline{A \cap B} = \overline{A} \cup \overline {B}$ , $\overline{A \cup B} = \overline{A} \cap \overline {B}$
Complement Law: $A \cup \overline{A} = U$ , $A \cap \overline{A} = \emptyset$
Difference Equivalence: $A \setminus B = A \cap \overline{B}$

Note the similarities to logical equivalences! Here are some examples of how to determine if two sets are equal:

Is $(A \setminus C) \cap (B \setminus C)$ equal to $(A \cap B) \cap \overline{C}$ ? First, we can use a membership table: $\begin{array}{ccc|cccccc} A & B & C & A \setminus C & B \setminus C & \bf (A \setminus C) \cap (B \setminus C) & A \cap B & \overline{C} & \bf (A \cap B) \cap \overline{C} \\\hline 1 & 1 & 1 & 0 & 0 & \bf0 & 1 & 0 & \bf0 \\ 1 & 1 & 0 & 1 & 1 & \bf1 & 1 & 1 & \bf1 \\ 1 & 0 & 1 & 0 & 0 & \bf0 & 0 & 0 & \bf0 \\ 1 & 0 & 0 & 0 & 0 & \bf0 & 0 & 1 & \bf0 \\ 0 & 1 & 1 & 0 & 0 & \bf0 & 0 & 0 & \bf0 \\ 0 & 1 & 0 & 0 & 1 & \bf0 & 0 & 1 & \bf0 \\ 0 & 0 & 1 & 0 & 0 & \bf0 & 0 & 0 & \bf0 \\ 0 & 0 & 0 & 0 & 0 & \bf0 & 0 & 1 & \bf0 \\ \end{array}$ Since the columns corresponding to the two sets match, they are equal. We can also use set identities: $\begin{array}{llll} (A \setminus C) \cap (B \setminus C) & = & (A \cap \overline{C}) \cap (B \cap \overline{C}) & \text{Difference Equivalence} \\ & = & (A \cap B) \cap (\overline{C} \cap \overline{C}) & \text{Associative Law} \\ & = & (A \cap B) \cap \overline{C} & \text{Idempotent Law} \\ \end{array}$
Is $(A \setminus C) \cap (C \setminus B)$ equal to $A \setminus B$ ? Let's use some set identities: $\begin{array}{llll} (A \setminus C) \cap (C \setminus B) & = & (A \cap \overline{C}) \cap (C \cap \overline{B}) & \text{Difference Equivalence} \\ & = & (A \cap \overline{B}) \cap (C \cap \overline{C}) & \text{Associative Law} \\ & = & (A \cap B) \cap \emptyset & \text{Complement Law} \\ & = & \emptyset & \text{Domination Law} \\ \end{array}$ Note that, in general, $A \setminus B \neq \emptyset$ (\eg, let $A=\{1,2\},B=\{1\}$ ). Therefore, these sets are not equal. (Note the similarity to finding truth settings that invalidate an argument!)