Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that:

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

(cmp = complement)

Now, one way to solve this is to take a small universe $U$, say $U$ = {a, b, c, d, e, f, g}, draw the Venn diagram, figure out the union-ed parts of the equation and prove it.

How can we do this purely algebraically? using the laws of sets like the idempotent law, duality, domination, absorption etc?

share|improve this question
1  
"The members of C are in A, in B or in neither of these." –  Myself Jul 3 '11 at 16:54

1 Answer 1

up vote 4 down vote accepted

The algebraic way to solve this is to remember that union and intersection are distributive over one another, therefore:

$$\begin{align} & (A^c\cap B^c\cap C) \cup (B\cap C) \cup (A\cap C) &=&(\text{un-distribute } \cap C) \\ & \Big( (A^c\cap B^c) \cup B \cup A\Big)\cap C &=&(\text{distribute }\cup B) \\ & \Big( (A\cup B)^c \cup (B\cup A)\Big)\cap C &=&(\text{de Morgan's law}) \\ & &=&C \end{align}$$

(As Theo suggested, using de Morgan's law shortens the proof.)

share|improve this answer
    
Thanks both of you for the insights. I've to brush up with the rules though. Doing this after a long, long time. –  IntelligentMoron Jul 3 '11 at 17:30
    
This is a nice way of inserting reasons in a sequence of aligned equalities. –  Jay Apr 26 at 20:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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