3
$\begingroup$

Prove: $[ (A \cap B) \cup C ]\cap (A^c\cup C) = C$

My attempt:

$(A\cup C)\cap(B\cup C)\cap(A^c\cup C) = C$ I used the distributive property,

but this is where I'm lost at. I think that I need to get A and $A^c$ together. So I should use the commutative property.

$(A\cup C)\cap(A^c\cup C)\cap(B\cup C) = C$ Should I distribute $(A\cup C)\cap(A^c\cup C)$?

My original post of this question was incorrect. Sorry about that.

  • 0
    To your last question-yes. If you "anti-distribute" on $(A\cup C)\cap(A^c\cup C)$ the $A$'s will disappear. Then you just have $B$ to get rid of.2011-02-02

4 Answers 4

5
  1. What is $(A\cup C)\cap(A^c\cup C)$ ? Try finding the anwser this way: if $a \in (A\cup C)$ and $a \in (A^c\cup C)$, where must $a$ be?

  2. What must $C \cap (B \cup C)$ be?

Note that the operation of intersection is associative, i.e. $(A \cap B) \cap C = A \cap (B \cap C)$.

  • 0
    I think I see now. Once we establish that $a\in (A \cup C) $ then it must also be $a\in (A^c \cup C)$ this gives us $(U \cap C)$ which is C and $C\cap(B\cup C) is C $2011-02-02
1

Another pattern to look for in this problem is to -un-distribute $C$, that is pull out the $C$ from the two main parts being intersected. That is,

$[(A\cap B)\cup C]∩(A^c\cup C) \rightarrow [((A\cap B) \cap A^c) \cup C]$

Then you can notice something in that intersection about $A$ and $A^C$ that will eliminate that entire part not involving $C$.

Two general strategies for solving equivalence problems by just playing with the syntax is to

  • rewrite to simpler things, like using an identity like distribution to reduce the length of the 'phrases' (the shortest set of things operated on). This can be very automatic (apply any identity that fits but always in one direction), but sometimes you get stuck, where you don't think you can simplify any further.
  • look for patterns to undo. Here you can ignore complexity in the syntax and consider one complex part as replaced by some new variable. Then with this new variable the syntax you have might match one side of an identity you already know. This is where a little experience helps, knowing identities that might be useful.

Another strategy is to try to think of what the (convoluted) syntax -means- (for example by some visualization like a Venn diagram, or thinking of an intersection as somehow below' both the sets being intersected)

  • 0
    Oh, reading the other answer I realize that, though my strategies are very general, there are specific strategies one can follow, and for proving set identities, one specific strategy is to show that every member of one side is a member of the other side (and vice versa).2011-02-04
0

Since this is an old question, I feel comfortable giving a complete solution, instead of hints. For me, the simplest way to solve this kind of problem is to reason at the level of logic, after translating set theory definitions to the level of elements.

In this case we can calculate which elements $\;x\;$ are in the set on the left hand side by simplifying: \begin{align} & x \in [ (A \cap B) \cup C ] \cap (A^c\cup C) \\ \equiv & \;\;\;\;\;\text{"expand the definitions of $\;\cap\;$, $\;\cup\;$ (twice), $\;\cap\;$ again, and $\;^c\;$"} \\ & ((x \in A \land x \in B) \lor x \in C) \land (x \not\in A \lor x \in C) \\ \equiv & \;\;\;\;\;\text{"logic: extract common disjunct $\;x \in C\;$ out of both conjuncts"} \\ & (x \in A \land x \in B \land x \not\in A) \lor x \in C \\ \equiv & \;\;\;\;\;\text{"logic: contradiction"} \\ & (\text{false} \land x \in B) \lor x \in C \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & x \in C \\ \end{align} This completes the proof of the original statement.

0

$[ (A \cap B) \cup C ]\cap (A^c\cup C) = C$

$(C \cup A) \cap (C \cup B) \cap (A^c\cup C) = C$

$C \cup (A \cap A^c \cap B) = C$

$C \cup (\emptyset \cap B) = C$

$C \cup \emptyset = C$

$C = C$