The two expressions $A \cap \left(B \cap C\right)$ and $\left(A \cap B\right) \cap C$ are equivalent.

Each side reduced to $A \cap B \cap C$ as shown below by applying well-known set identities.

---

Truth Table Procedure

Two set expressions are equivalent if their truth tables are equivalent.

To construct a truth table for a set expression:

1. Imagine an arbitrary element $x$.

2. For any set $S$, either $x \in S$ or $x \notin S$. These correspond to true $(T)$ and false $(F)$ in our truth table.

3. Enumerate every possible combination of set membership statuses for $x$, for all component sets $A, B, C, \ldots$ in the expression.

   • The universal set $\mathbb{U}$ contains every element, so $x \in \mathbb{U}$ is always true.

   • The empty set $\emptyset$ contains no elements, so $x \in \emptyset$ is always false.

4. Then, for each combination, solve each sub-expression $S_{sub}$ for $x \in S_{sub}$, based on the set membership of the previous sub-expressions.

5. The truth tables are equivalent if and only if the last row of the truth table, corresponding to the entire expression $S$, is identical.

That is, given two set expressions $S_1$ and $S_2$, with component sets $A, B, C, \ldots$,
$S_1 = S_2$ if and only if every combination of set memberships for an arbitrary element $x$ in the component sets produces $x \in S_1 = x \in S_2$.

---

Reduce By Identities

We do not always need to solve each unmodified expression to get the answer.

We can reduce a complex expression to a simpler, equivalent one by substituting out sub-expressions using well-known set identities.

Note: Simplification is provided on a best-effort basis. There may exist better simplifications not discovered.

Left-Hand Side

$A \cap \left(B \cap C\right) = A \cap B \cap C$, shown by the following:

\[\begin{array}{c|l|l} \textbf{Step} & \textbf{Expression} & \textbf{Identity Used} \\\hline1 & A \cap \left(B \cap C\right) & \\\hline2 & A \cap B \cap C & S_{1} \cap \left(S_{2} \cap S_{3}\right) = S_{1} \cap S_{2} \cap S_{3} \\\end{array}\]

The simplification can be validated by comparing truth tables:

Right-Hand Side

$\left(A \cap B\right) \cap C = A \cap B \cap C$, shown by the following:

\[\begin{array}{c|l|l} \textbf{Step} & \textbf{Expression} & \textbf{Identity Used} \\\hline1 & \left(A \cap B\right) \cap C & \\\hline2 & A \cap \left(B \cap C\right) & \left(S_{1} \cap S_{2}\right) \cap S_{3} = S_{1} \cap \left(S_{2} \cap S_{3}\right) \\\hline3 & A \cap B \cap C & S_{1} \cap \left(S_{2} \cap S_{3}\right) = S_{1} \cap S_{2} \cap S_{3} \\\end{array}\]

The simplification can be validated by comparing truth tables:

---

Venn Diagrams

For smaller numbers of component sets, the truth tables can also effectively be expressed as Venn diagrams.

Each section of the Venn diagram is analogous to one combination of set memberships for an arbitrary element $x$.