# Set Expressions Simplification

I was asked to find the value of $$(A \cap \overline{B})\cup(A \cap B)$$ for any two sets $A$ and $B$.

When solving this type of problems, can I translate the expression to a logic expression and then simplify it? If so, how would I simplify the following expression? I got $A$ as the answer by thinking logically, but I am not sure how to do it mechanically. $$(A ∧ ¬B) ∨ (A ∧ B)$$

This is what I did, but I was stuck:

$$(A ∧ ¬B) ∨ (A ∧ B) ⇔$$ $$((A ∧ ¬B) ∨ A) ∧ ((A ∧ ¬B) ∨ B) ⇔$$ $$(A ∨ A) ∧ (A ∨ ¬B) ∧ (B ∨ A) ∧ (B ∨ ¬B) ⇔$$ $$A ∧ (¬B ∨ A) ∧ (A ∨ B) ∧ U$$

Thanks.

• Distributivity: $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$. Now use $C=\overline{B}$, so your expression is $A\cap(\overline{B}\cup B)=A$. With Boolean expressions it's the same. – egreg Feb 14 '18 at 22:31
• If you mean $(\color{blue}{A \cap} \overline B) \cup (\color{blue}{A \cap} B)$, then we can "factor out" the set A: $\color{blue}{A\cap} (\overline B \cup B) = A\cap U = A$ – Namaste Feb 14 '18 at 23:05

No you can't use logic operations $\lnot, \land, \lor, etc.$ directly on sets, because sets are not propositions.

For example, when discussing sets themselves, we have $(A \cap \overline{B})\cup(A \cap B)$, and it makes absolutely no sense to translate this simply replace set relations with propositional relations, equating $(A \cap \overline{B})\cup(A \cap B)$ with $(A\land \lnot B)\cup (A \land B)$. The second expression is utterly meaningless

But you can use logic operations/relations on propositions by rewriting a set in terms of what it means for an element to belong to that set, and in that case, we essentially unpack the meaning of set union, set complement, set intersection, etc.

In this case, you have

Let's chase an element in the above set, to unpack what it means; and line by line we can do so entirely with biconditionals:

So \begin{align} x \in (A\cap \overline B) \cup (A\cap B) &\iff x \in (A\cap \overline B) \lor x \in (A\cap B)\\ \\ &\iff (x \in A \land x\notin B)\lor (x \in A \land x \in B)\\ \\ &\iff x\in A \land (\underbrace{(x\notin B) \lor (x \in B))}_{\text{tautology} \top}\\ \\ &\iff (x\in A)\land \top\\ \\ &\iff x \in A\end{align}

Hence $$x \in (A\cap \overline B) \cup (A\cap B) \iff x \in A$$

Hence, $$\big((A\cap \overline B) \cup (A\cap B)\big) = A$$

Forgetting your misuse of logic relations among sets, you could have saved some time, when you reached this step: $(A ∧ ¬B) ∨ (A ∧ B)$

$(A\cap \overline B) \cup (A\cap B)$ corresponds to $(x\in A \land x \notin B)\lor (x\in A \land x\in B)$

Then, we can notice that $A$, or rather $x \in A$ appears in both sets on each side of $\cup$ ($\lor$).

So we can use what I sometimes called "reverse distribution", in this case $A \cap (\overline B \cup B)$. Using logic, we have $x \in A \land (\notin B \lor x\in B)$. In terms of sets, we have $A\cap U$, where $U$ is the universal set containing A. In terms of logic, we have that $x \in A \land \top$, where $\top$ means always true for any set: any element is either an element of any given set, or it is not: always true. $A\cap U = A$, and $x\in A \land \top \iff x \in A$

• Thank you for the clear explanation, that makes a lot of sense. So in a way, set identities may be identical to logical operation identities, but they are not the same thing. I just have one quick question: when you simplified $(x \in A \land x\notin B)\lor (x \in A \land x \in B)\\ \\$ to $x\in A \land \underbrace{(x\notin B) \lor (x \in B))}_{\text{tautology} \top}\\ \\$, was there a rule that you used? Is it okay to just pull out $x\in A$? Thanks. – Philip Kuo Feb 15 '18 at 1:58
• @PhilipKuo What you can do with sets is isomorph to what you can do with logic, but they are not the same thing. Also, The 'pulling out' of $x \in A$ is through the use of a rule called Distribution: $P\land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R)$ ... going from right to left. Finally, since you're new here: if amWhy's Answer was to your satisfaction, you can Accept it by clicking on the check mark next to it. – Bram28 Feb 15 '18 at 13:01
• @Bram28 I got it, it is a lot clearer now. Thanks. – Philip Kuo Feb 15 '18 at 16:33
• @PhilipKuo You're welcome! :) – Bram28 Feb 15 '18 at 16:45

Technically that should be as follows, but yes, you show how the set is built using boolean algebra expressions, then simplify the result.

$$(A\cap\overline B)\cup(A\cap B)~{=\{x:(x\in A\wedge x\notin B)\vee(x\in A\wedge x\in B)\}\\ = \{x: x\in A\wedge(x\notin B\vee x\in B)\}\\ =\{x:x\in A\wedge \top\}\\ = A}$$