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.

Suppose we have four sets A, B, C and X.

How can one prove the following identity:

$(A \cap B \cap C \cap \neg X) \cup ( \neg A \cap C) \cup ( \neg B \cap C) \cup (C \cap X)=C$

I tried to apply here any of basic set identities like Distributive Law or Associative Law but it led me to nothing.

Any help would be appreciated, then.

share|improve this question
    
Can't you just prove it by showing that if $x \in C$, then $x \in $LHS, and vice-versa? It looks like you could use DeMorgan's laws, but this might just be shorter! –  Prahlad Vaidyanathan Oct 28 '13 at 11:56

1 Answer 1

up vote 3 down vote accepted

Prahlad Vaidyanathan’s suggestion in the comments is probably the easiest way to go, but an algebraic proof is certainly possible. First note that $$(\neg A\cap C)\cup(\neg B\cap C)=(\neg A\cup\neg B)\cap C$$ by one of the distributive laws. Then $C\cap X=X\cap C$, and

$$\big((\neg A\cup\neg B)\cap C\big)\cup(X\cap C)=\big(\neg A\cup\neg B\cup X\big)\cap C$$

by one of the distributive laws. Thus, the original lefthand side is equal to

$$(A\cap B\cap C\cap\neg X)\cup\big((\neg A\cup\neg B\cup X)\cap C\big)\;.\tag{1}$$

Now use one of the De Morgan laws and the fact that $\neg(\neg Y)=Y$ to see that

$$\neg A\cup\neg B\cup X=\neg(A\cap B\cap\neg X)\;,$$

so that $(1)$ is equal to

$$\Big((A\cap B\cap\neg X)\cap C\Big)\cup\Big(\neg(A\cap b\cap\neg N)\cap C\Big)\;,$$

and use a distributive law to pull out the $C$ and get

$$\Big((A\cap B\cap\neg X)\cup\neg(A\cap B\cap\neg X)\Big)\cap C\;.\tag{2}$$

Finally, use the fact that $Y\cup\neg Y$ is the universal set, which I’ll call $U$, so that $(2)$ is $$U\cap C=C\;.$$

share|improve this answer
    
Just one question. How many examples must I solve to start easily decompose such identities to simple parts according to set identities laws? I didn't see all those parts, until you showed them :( –  Dragon Oct 28 '13 at 12:27
1  
@Dragon: That seems to vary enormously from one person to another. I can tell you some of what went through my mind, if that helps: every term on the lefthand side included an intersection with $C$, so in principle I could have factored $C$ out and got $$\text{ugly expression}\cap C\;.$$ This equals $C$ if and only if $\text{ugly expression}\supseteq C$. Instead of trying to deal with this all at once, I did it in smaller, simpler chunks: I just kept pulling out $C$ and combining what was left, starting with the simplest bits. –  Brian M. Scott Oct 28 '13 at 12:34
    
Thanks a lot for detailed explanation. I need more practice for sure. –  Dragon Oct 28 '13 at 12:37
    
@Dragon: You’re welcome. –  Brian M. Scott Oct 28 '13 at 12:45

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.