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.

Use the laws of algebra of sets to show that:

$$(A \cup ( B \cap C')) \cap ( A \cup C ) = A$$

Can someone please tell me how to work out such questions and what are the rules that can be used when using laws to prove such quesion.

share|improve this question
    
If this is a homework, then please add the tag (homework). You would still receive help. –  user2468 Aug 12 '12 at 17:06

2 Answers 2

First using distributivity $$(A∪(B∩C'))∩(A∪C) = ((A∪B)∩ (A∪C'))∩(A∪C) $$ then associativity $$ ((A∪B)∩ (A∪C'))∩(A∪C) = \color{teal}{(A∪B)}∩ \color{blue}{(A∪C') ∩ (A∪C)} $$ Can you take it from here?


To show that $\color{teal}{(A∪B)}∩ \color{blue}{(A∪C') ∩ (A∪C)} =A $ we will first show that $$ \color{blue}{(A∪C')∩(A∪C)} = \color{blue}{A} \tag{1}$$ Then we'll use the absorption law to finish with $$ \text{LHS} = \color{teal}{(A∪B)} ∩ \color{blue}{A} = A = \text{RHS}. $$

To prove $(1)$ we use distributivity to get: $$ \color{red}{[A ∩ (A∪C)]} ∪ [C' ∩ (A∪C)] $$ But by absorption law we have $$ \color{red}{A} ∪ [C' ∩ (A∪C)] $$ But $C' ∩ (A∪C) = (C' ∩ A) ∪ (C' ∩ C) = (C' ∩ A) ∪ \phi = (C' ∩ A) .$ So by absorption again we have $$ \color{red}{A} ∪ [C' ∩ (A∪C)] = \color{red}{A} ∪ (C' ∩ A) = A. $$ QED.

share|improve this answer
    
Strictly speaking, your second righthand side ought to be $$(A\cup B)\cap\Big((A\cup C')\cap(A\cup C)\Big)\;.$$ It works: you then use distributivity in the big parenthesis, do a couple of obvious things, and finish with absorption. –  Brian M. Scott Aug 12 '12 at 17:11
    
I just don't understand how to get rid of the C′ ? –  Zee123 Aug 17 '12 at 0:14
    
@Zee123 can you edit your question & add your steps? In which step did you get stuck? –  user2468 Aug 17 '12 at 0:44
    
First using distributivity (A∪(B∩C′))∩(A∪C)=((A∪B)∩(A∪C′))∩(A∪C) then associativity ((A∪B)∩(A∪C′))∩(A∪C)=(A∪B)∩(A∪C′)∩(A∪C) then used complement law to get ((A∪B)∩(A∪C′))∩(A∪C)=(A∪B)∩ ∅ .....but I'm not sure if that's what the next step is or if that's how you get rid of the C′ using this law or if there are other laws that can be used? –  Zee123 Aug 17 '12 at 1:02
    
@Zee123 see my update. I posted the full solution. Let me know if you have more questions. If this is a satisfactory answer, then please consider the accept button to the right below the upvote button. –  user2468 Aug 17 '12 at 3:06

By the laws of algebra, I assume you mean the Boolean Algebra axiom for the Boolean Algebra of Sets. Converting into Boolean notation, you would have that $+$ is $\cup$, $\cdot$ is $\cap$, $0 = \emptyset$, and $1 = X$ where $X$ is the universe of the particular boolean algebra

I will use this frequently, the property of absorption is

$u \cap (u \cup x) = u \text{ and } u \cup (u \cap x) = u$

for all $u$ and $x$. Jech's Set Theory includes it among his axioms, but derives the identity axiom. With the identity axiom (like the definition from wikipedia), you can derive absorption. Depending on what exactly are your boolean algebra axioms, you may or may not need to prove absorption or identity.

By Distributivity,

$$(A \cap (A \cup C)) \cup ((B \cap C') \cap (A \cup C))$$

By absorption,

$A \cap (A \cup C) = A$

So you have

$A \cup ((B \cap C') \cap (A \cup C))$

By associativity of $\cap$

$A \cup (B \cap (C' \cap (A \cup C)))$

By Distributivity

$A \cup (B \cap ((C' \cap A) \cup (C' \cap C)))$

By complementation, $C' \cap C = \emptyset$ so

$A \cup (B \cap (C' \cap A) \cup \emptyset))$

By the identity axiom, $u \cup \emptyset = u$ for any $u$. So

$A \cup (B \cap (C' \cap A))$

By Distibutivity

$A \cup ((B \cap C') \cap A)$

By absorption

$A$

The proof is complete.

share|improve this answer

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.