10
$\begingroup$

I ran into a simple question, but I need an expert help me more to understand more:

The following is True:

$ A - (C \cup B)= (A-B)-C$

$ C - (B \cup A)= (C-B)-A$

$ B - (A \cup C)= (B-C)-A$

and the following is False:

$ A - (B \cup C)= (B-C)-A$

this is an interview question, but how we can check the these sentence as true or false quickly?

$\endgroup$
  • 4
    $\begingroup$ The first three are all the same (with the sets relabeled). Looking at the first, the set is elements in $A$ that are not in $B$ or $C$. The fourth is obviously false in general, because one side contains some elements in $A$ and the other does not. $\endgroup$ – almagest May 16 '16 at 10:33
  • $\begingroup$ @almagest is it possible to make more clarity for forth one? $\endgroup$ – user4249446 May 16 '16 at 10:38
  • 2
    $\begingroup$ @user4249446 All you need is a single counter example. Suppose $A$ is non-empty and $B,C$ are both empty. Then the lefthand side is $A$ but the righthand side is empty. $\endgroup$ – almagest May 16 '16 at 10:54
  • $\begingroup$ Please submit as an answer. I get it. thanks @almagest $\endgroup$ – user4249446 May 16 '16 at 10:57
  • 1
    $\begingroup$ Why don't use de Morgan's Laws? For example, $A-(C\cup B)=A\cap (C\cup B)^c=A\cap C^c\cap B^c=(A\cap B^c)\cap C^c=(A-B)-C$. $\endgroup$ – user 170039 May 16 '16 at 15:21
13
$\begingroup$

In my opinion, in the case of only 3 sets, it is most straightforward to draw the corresponding Venn diagram

3-set Venn diagram

and find out the resulting subset when you apply the operations on both sides of your equalities. In an interview, I think it would show sense of intuition; you shouldn't be afraid of drawing little diagrams for simple math questions.

EDIT: After thinking about it, this is more about pragmatism than intuition. Here you won't have to find the right trick, or use too much brainpower, and you will be able to apply this even if put under the stress of the interview.

Which is not to say you won't find other answers helpful if you have to actually prove/disprove the predicates, or if you want to show that you are, in fact, able to find tricks.

$\endgroup$
11
$\begingroup$

To think through things quickly, you can see that $A-(C\cup B) = (A-B)-C$ is true, because on the left, you're taking a set $A$ and getting rid of anything in either $C$ or $B$, while on the right, you're taking $A$, first getting rid of anything in $B$, and then getting rid of anything in $C$. The next two are similar (so similar, in fact, that it would slow me down wondering why they would, in effect, ask the same question three times in a row). Finally, $A-(B\cup C)=(B-C)-A$ has to be false (in general) because on the left you only have stuff in $A$ while on the right you're getting rid of $A$.

Note, none of this constitutes rigorous proof. I'm just addressing the OP's request for a quick way to assess the equalities.

$\endgroup$
  • 2
    $\begingroup$ It's rigorous enough for me, and exactly what I was going to say. $\endgroup$ – DanielWainfleet May 16 '16 at 15:57
10
$\begingroup$

The first three are all the same (with the sets relabeled). Looking at the first, the set is elements in $A$ that are not in $B$ or $C$. So the first three are all true.

The fourth is false in general. All we need is a single counter example. Suppose $A$ is non-empty, but $B,C$ are both empty. Then the lefthand side is just $A$ and is non-empty, but the righthand side is empty.

$\endgroup$
8
$\begingroup$

Indicator functions can be used. In general:

  • $1_{A^c}=1-1_A$
  • $1_{A\cap B}=1_A1_B$

This can be used to find:

  • $1_{A\cup B}=1_A+1_B-1_A1_B$
  • $1_{A-B}=1_A-1_A1_B$

Application on first:

$1_{A-(C\cup B)}=1_A-1_A(1_C+1_B-1_C1_B)$ $1_{(A-B)-C}=1_{A-B}-1_{A-B}1_C=(1_A-1_A1_B)-(1_A-1_A1_B)1_C$

Both result in $1_A-1_A1_C-1_A1_B+1_A1_B1_C$ so the sets are equal.

$\endgroup$
  • $\begingroup$ there is a typo... $\endgroup$ – user4249446 May 16 '16 at 11:11
  • 1
    $\begingroup$ @user4249446 I am overlooking it. Feel free to edit and repair. $\endgroup$ – drhab May 16 '16 at 11:15
  • $\begingroup$ in last line I think you should add "," $\endgroup$ – user4249446 May 16 '16 at 11:16
  • 1
    $\begingroup$ @user4249446 You mean ",so" instead of "so"? $\endgroup$ – drhab May 16 '16 at 11:19
  • 2
    $\begingroup$ That's not a typo $\endgroup$ – The Great Duck May 16 '16 at 22:01
6
$\begingroup$

The fourth one looks immediately wrong because A is once on the left side and once on the right side of the minus. So picking a different A with more elements would on one side add elements to the solution and on the other side remove them.

With that knowledge, picking A non empty and B, C empty shows the statement is nonsense.

$\endgroup$
  • $\begingroup$ +1 for the (obvious?) counterexample. Always look out for corner cases, in this example,empty sets. $\endgroup$ – Jasper May 17 '16 at 10:04
  • $\begingroup$ Not nonsense, merely false. $\endgroup$ – Henning Makholm Jul 31 '18 at 9:35
3
$\begingroup$

The first three equalities are the same So you should prove one. For this, there are some ways but I first note an intuition, then a simple proof via De-morgan's law.

Intuition. To have $A - (C \cup B)$, you exclude from $A$, all elements that are in $C$ and all elements that are in $B$, outright. To have $(A-B)-C$, you exclude from $A$, 1st all elements that are in $B,$ and then all elements that are in $C.$

Proof.
\begin{align*} x\in A - (C \cup B) &\iff x\in A \land x\notin C \cup B \\&\iff x\in A \land (x\notin C \land x\notin B)\\&\iff (x\in A \land x\notin B)\land x\notin C\iff x\in (A-B)-C \end{align*}


Inorder to show that the 4th equality is false let $A=\{1\}$, $B=\{2,3\}$, and $C=\{2\}$. Then $A - (B \cup C)=\{1\}$, while $(B-C)-A=\{3\}$

$\endgroup$
2
$\begingroup$

To check quickly, you can use the boolean logic, i.e. replacing the set $A$ with statement $a = (x \in A)$. Thus you get (using $A - B = A \cap B^C \Leftrightarrow a*\neg b$ ):

$$a * \neg (b+c) = (b*\neg c)*\neg a$$

$$a * \neg b * \neg c = (b*\neg c)*\neg a$$

this should be equal for all $a,b,c$, but for $(1,0,0)$ we have

$$1 = 1*\neg 0*\neg 0 = (0*\neg 0) *\neg 1 = 0$$

which is contradiction.

$\endgroup$
1
$\begingroup$

You can develop a tactile/visual sense of sets.

1) A - (B $\cup$ C) is all the elements of A with the elements of B and C removed. (A - B) - C is all the elements of A with first the elements of B removed and then all the elements of C removed. Those are the same things.

2 and 3. ditto.

4) A - (B $\cup$ C) is all the elements of A with the elements of B and C removed. (B - C)-A is the elements of B with the elements of C and then the elements of A removed. Those are completely different things.

$\endgroup$
1
$\begingroup$

Try to understand what the sets are, in other words you need to think about them intuitively.

The first three are of the same format. For the first $A- (B\cup C)$ this is just all the elements of $A$ where we subtract all the elements that are in $B$ or in $C$ (or in both). Now $A-B$ is the elements of $A$ and we remove all the elements of $B$. Then we proceed and remove from there all the elements of $C$ so in total we have all the elements of $A$ minus the elements that belong to $B$ or $C$ (or both). Hence in total we have the same sets.

Now for the false part $ A - (B \cup C)= (B-C)-A$: the right hand side are the elements of $B$ where we have removed something. The left hand side are the elements of $A$ where we have removed something. But $A$ and $B$ can be totally different sets so they cannot be possibly every time equal to each other.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.