2
$\begingroup$

I'm having trouble simplifying this set theory expression

$$\begin{align} (A \cap B) \cup (A \cap B \cap C' \cap D) \cup (A'\cap B) & \end{align} $$

In the books says that absorption law can help, but I do not understand why

$$\begin{align} (A \cup A') \cap B = U \cap B = B & \end{align} $$

Can someone guide me in how do this please, just a hint please? I am stuck

$\endgroup$
4
  • $\begingroup$ I assume $A,B,C,D\subset U$ for a given set $U$ und $A':=U\setminus A$? $\endgroup$
    – Hirshy
    Jun 17, 2015 at 12:11
  • $\begingroup$ Is the third term $A'\cap B$ instead of $A'\cup B$? $\endgroup$ Jun 17, 2015 at 12:14
  • $\begingroup$ The problem does not say anything about it, just say simplify and in the solution manual says that using that law $\endgroup$
    – Learner
    Jun 17, 2015 at 12:14
  • $\begingroup$ @ClémentGuérin yes sorry, I already edit $\endgroup$
    – Learner
    Jun 17, 2015 at 12:15

7 Answers 7

4
$\begingroup$

We have :

$$(A \cap B) \cup (A \cap B \cap C' \cap D) \cup (A'\cap B)=((A \cap B) \cup (A'\cap B))\cup (A \cap B \cap C' \cap D)$$

You just use here the associativity and comutatitivity of $\cup$. Now :

$$(A \cap B) \cup (A'\cap B)=(A\cup A')\cap B=U\cap B=B$$

I used distribution of $\cap$ with respect to $\cup$. Then $A\cup A'=U$ because $A\cup A'$ consists by definition of elements of $U$ which are in $A$ or not in $A$ (clearly, all elements of $U$ verify this). Then $U\cap B=B$ because $B\subseteq U$. Now you have :

$$(A \cap B) \cup (A \cap B \cap C' \cap D) \cup (A'\cap B)=B\cup (A \cap B \cap C' \cap D)$$

And I will let you finish...

$\endgroup$
2
  • $\begingroup$ Thank you for answering I will solve the other part $\endgroup$
    – Learner
    Jun 17, 2015 at 13:03
  • $\begingroup$ You seem to have a typo. In line 4 it should say "because $A\cup A'$ consists by definition...". $\endgroup$
    – Hirshy
    Jun 17, 2015 at 13:06
4
$\begingroup$

To prove these, you need logic laws, which in turn are proved using truth tables.

Absorption law: $\color{#00F}X\cup (\color{#00F}X\cap \color{#F00}Y)=\color{#00F}X$, which is simple to prove: you prove $$(x\in X\cup(X\cap Y))\iff (x\in X)$$

In this case:

$$(\color{#00F}{A \cap B}) \cup ((\color{#00F}{A \cap B}) \cap (\color{#F00}{C' \cap D})) \cup (A'\cap B)$$

$$\stackrel{\text{Absorp}}=(\color{#00F}{A\cap B})\cup (A'\cap B)\stackrel{\text{Distr}}=(A\cup A')\cap B\stackrel{\text{Compl}}=U\cap B\stackrel{\text{Ident}}=B$$

Distr - distributive law. Proof:

$$(x\in ((X\cup Y)\cap Z))\iff ((x\in (X\cup Y))\wedge (x\in Z))$$

$$\iff (((x\in X)\lor (x\in Y))\wedge (x\in Z))$$ $$\iff (((x\in X)\wedge (x\in Z))\lor ((x\in Y)\wedge (x\in Z)))$$

$$\iff ((x\in X\cap Z)\lor (x\in Y\cap Z))\iff (x\in ((X\cap Z)\cup (Y\cap Z)))$$

Compl - complement law, Ident - identity law. They are both trivial: you prove $$(x\in A\cup A')\iff (x\in U), \ \ \ \ \ \ (x\in U\cap B)\iff (x \in B),$$

respectively.

$\endgroup$
2
$\begingroup$

I assume that $A,B,C,D\subset U$ and $A':=U\setminus A$ (it should say something like that in the question, otherwise you have to clarify the notation you're using in the book).

Let $A\subset U$ for any set $U\neq\emptyset$. Then we define the absolute complement of $A$ in $U$, meaning everything that is "outside of $A$ but still in $U$", as $A':=U\setminus A$.

As $A\subset U$ we can write $A=\{x\in U \wedge x\in A\}$ and $A'=\{x\in U\wedge x\notin A\}$. Thus if we look at the union $A\cup A'$ we get $$A\cup A'=\{x\in U \wedge x\in A\} \cup \{x\in U\wedge x\notin A\} =\{(x\in U\wedge x\in A)\vee (x\in U \wedge x\notin A\}.$$

Every $x$ that fulfills $x\in U \wedge x\in A$ lies in this union; these are all $x$ "inside of $A$". Every $x$ that fulfils $x\in U\wedge x\notin A$ lies in this union; these are all $x$ "outside of $A$".

As there are no other $x\in U$ (either $x\in A$ or $x\notin A$), we get $A\cup A'=U$.

$\endgroup$
2
$\begingroup$

Use distributivity and comuutativity of $\,\cap\,$ and $\,\cup$: \begin{align} (A \cap B) \cup &(A \cap B \cap C' \cap D) \cup (A'\cap B)=\bigl((A \cap B) \cup (A'\cap B)\bigr)\cup (A \cap B \cap C' \cap D) \\ & =\bigl((A \cup A')\cap B\bigr)\cup (A \cap B \cap C' \cap D)= (U\cap B)\cup (A \cap B \cap C' \cap D)\\ &=B\cup (A \cap B \cap C' \cap D)\qquad\text{since}\enspace B\subset U. \end{align}

$\endgroup$
2
$\begingroup$

Hint 1: Note that $P\cup (P \cap Q) = P$, can you find such P or Q in your expression? (possibly a larger set)

Hint 2: $(P\cap Q) \cup (R \cap Q) = (P \cup R)\cap Q$, do you see any such use in this equation (so you may then get to using the absorbtion law)?

$\endgroup$
1
$\begingroup$

(A intersection B) Union (A' intersection B)is B. Then what remains is to have the union of B and the content of the large bracket, that is B union(AnBnC'nD). This can still be expressed in other way round using Morgan's.

$\endgroup$
1
$\begingroup$

Starting with your second question, recall that $A'$ is the set of all things that aren't in $A$. Well, $A \cup A'$ is all things in $A$ together with all things not in $A$. In other words, it's all things, since for any given thing, it's either in $A$ or it isn't. That's why $A \cup A' = U$.

Now to your first question, we simply rearrange:

\begin{align} (A \cap B) \cup (A \cap B \cap C' \cap D) \cup (A'\cap B) &= (A \cap B) \cup (A'\cap B) \cup (A \cap B \cap C' \cap D) \\ &= ((A \cap B) \cup (A'\cap B)) \cup (A \cap B \cap C' \cap D) \\ &= ((A \cup A') \cap B) \cup (A \cap B \cap C' \cap D) \\ &= (U \cap B) \cup (A \cap B \cap C' \cap D) \\ &= B \cup (A \cap B \cap C' \cap D) \end{align}

The first line is from commutativity of $\cup$.

The second is from associativity of $\cup$.

The third is from distributivity of $\cap$ over $\cup$.

The fourth is from your second question.

The fifth is because $B \subseteq U$; since everything in $B$ is in $U$, the intersection (that is, the set of elements that both sets have in common) is just $B$. See if you can use this principle to finish.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .