5
$\begingroup$

Prove or disprove $(A + B) \cap C = (A \cap C) +(B \cap C)$

I want to disprove this statement.

$(A+B)$ is the symmetric difference and has the form of $(A \cup B) \backslash (A \cap B)$

I am starting on the left which is $(A + B) \cap C $

If I take the complement definition of $(A+B)$, I would have

$[x: x \in A \cup B \land x \notin A \cap B]$

So I am left with $A \cup B$

now I'm going to use the distributive law $\cap C$ on $A \cup B$

The result would be $(A \cup C) \cap (B \cup C)$

$(A \cup C) \cap (B \cup C) \neq (A \cap C) +(B \cap C)$

because in the middle we have $\cap$ on the left and $+$ on the right... but that's wrong.

What if I let $ C = \emptyset$ ?

Then I would have $(A +B) \cap \emptyset = (A \cap \emptyset) +(B \cap \emptyset )$

I'm going to start at the right this time .. because I've seen some properties already and it's similar to what I did weeks before

$= (A \cap \emptyset) +(B \cap \emptyset )$

Universal Bound Law $A \cap \emptyset = \emptyset$

$= (\emptyset) +(\emptyset )$

If I take the symmetric difference of $= (\emptyset) +(\emptyset )$ it's an empty set.

hmmm now that I think about it...if I approach it this way it looks like I'm proving that they are indeed equal.

$(A + B) \cap \emptyset$ [ distributive law]

$(A \cap \emptyset ) + (B \cap \emptyset)$ [universe bound laws]

$( \emptyset ) + ( \emptyset)$ [symmetric difference]

that's an empty set...

I want to disprove this statement... but how?

edit: another attempt at this problem using set intersection definition

Prove or disprove $(A + B) \cap C = (A \cap C) +(B \cap C)$

Suppose $x \in (A +B) \cap C$, then $[x \in (A +B)] \cap C$ and we have $(x \in A + x \in B) \cap C$

For $x \in A$, by set intersection definition, we have $x \in A \land C$ and $x \in B \land C$

[maybe for $x \in C$, by set intersection definition, we have $x \in A \land C$ and $x \in B \land C$ since C is being distributed, not A. ]

By symmetric difference definition, we have $x \in A \land C + x \in B \land C$

Therefore, $(A \cap C) +(B \cap C)$

Is this correct?!

$\endgroup$
7
  • $\begingroup$ You can just prove it the same way you would prove $(a \text{ xor } b) \land c \equiv (a \text{ xor } b) \land (a \text{ xor } c)$. $\endgroup$
    – DanielV
    Mar 3, 2014 at 10:00
  • $\begingroup$ how though? I mean we are dealing with $+$ here... I don't think just flat out use the distributive law will work on this...and I want to disprove it. $\endgroup$
    – usukidoll
    Mar 3, 2014 at 10:08
  • $\begingroup$ the only way I could think this is to prove the distributive law with that problem. $\endgroup$
    – usukidoll
    Mar 3, 2014 at 10:19
  • 1
    $\begingroup$ The most direct way to prove the statement is to look at the 8 cases of $x \in A$, $x \in B$, and $x \in C$, and evaluate the expressions and show equivalence in all 8 cases. It isn't glorious, but it's very reliable. $\endgroup$
    – DanielV
    Mar 3, 2014 at 10:34
  • $\begingroup$ so I gotta do one for $x \in A$, $x \in B$, and $x \in C$?! balh what if I want to disprove it? That's my original intent. $\endgroup$
    – usukidoll
    Mar 3, 2014 at 10:38

2 Answers 2

1
$\begingroup$

There is a duality between sets and functions. $\cap$ becomes $\land$ , $\cup$ becomes $\lor$, $+$ becomes $\text{ xor }$, $\text{universe minus set}$ becomes $\lnot$. If you wish to be pedantic, you can convert everything manually:

$$x \in (A + B) \cap C$$ $$x \in (A + B) \lor x \in C$$ $$(x \in A \text{ xor } x \in B) \lor x \in C$$

The above statements are equivalences, the same for the rhs:

$$x \in (A \cap C) + (B \cap C)$$ $$...$$ $$(x \in A \land x \in C) \text{ xor } (x \in B \land x \in C)$$

Replace $x \in A$ with $a$, same for $B$ and $C$.

$$(a \text { xor } b ) \land c \equiv (a \land c) \text{ xor } (b \land c)$$

That's how they come up with these set problems; just look at the dual Boolean expression.

$\endgroup$
1
  • $\begingroup$ So I do the same thing except I will have $x \in B$ so that would mean that the place for $x \in B$ would be switched like $x \in (B+A)$?! or $x \in (B+C) \cap A$??? $\endgroup$
    – usukidoll
    Mar 3, 2014 at 11:49
0
$\begingroup$

Use the answer at #697330 but with "$x \in A+B \iff (x \in A \cup B) \wedge \neg (x \in A \cap B) $. The rest of the structure is the same and you'll do a little more propositional calculus, but you'll follow the same path.

$\endgroup$
1
  • $\begingroup$ what does that bring though?! if I use complement definition on $A+B$ I will only have $A \cup B$ which means there are elements in A or B. $\endgroup$
    – usukidoll
    Mar 3, 2014 at 9:10

You must log in to answer this question.

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