2
$\begingroup$

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.

2 Answers 2

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.

  • 0
    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.2012-08-12
  • 0
    I just don't understand how to get rid of the C′ ?2012-08-17
  • 0
    @Zee123 can you edit your question & add your steps? In which step did you get stuck?2012-08-17
  • 0
    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?2012-08-17
  • 0
    @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.2012-08-17
1

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.