Answer to Question #253044 in Discrete Mathematics for Alina

Question

Question#1

Use algebra of sets to prove the following:

i. (𝐵 − 𝐴) ∪ (𝐶 − 𝐴) = (𝐵 ∪ 𝐶) − 𝐴

ii. [(𝐵 − 𝐴) ^c∩ 𝐴] − 𝐴^c= 𝐴

iii. (𝐴𝑐 ∪ 𝐵)^c ∩ A^c= ∅

Question#2

Use Mathematical induction to prove the following generalization of one

of De Morgan’s law: ⋃ⁿ_j=1 𝐴_j= ⋃ⁿ_j=1 A_j

Question#3

Prove that (𝐴 ∪ 𝐵 ∪ 𝐶) ′ = 𝐴′ ∩ 𝐵 ′ ∩ 𝐶 ′

Answer 1

i. $(B\cup C)-A=(B\cap C)\cap \overline {A}=[distribution\space low]=$

$(B\cap \overline {A})\cup(C\cap \overline{A})=(B-A)\cup(C-A)$

ii 

$[(B-A)^c\cap A]-A^c=[(B\cap A^c)^c\cap A]\cap (A^c)^c=[Morgan \space low, double \space complement \space low]=(B^c\cup(A^c)^c)\cap A)\cap A=(B^c\cup A)\cap(A\cap A)=[idempotent \space law]=(B^c\cup A)\cap A=A.\space because A\subset (B^c\cup A)$

iii.

$(A^c\cup B)^c\cap A^c=[Morgan\space low]=((A^c)^c\cap B^c\cap A^c=[double\space complement]=A\cap B^c\cap A^c=[commutativity\space and \space associativity \space of \space \cap]=(A\cap A^c)\cap B=[properties \space of\space complement]=\empty\cap B=\empty$

Question 2/

1) Basis of induction, n=2

$\left(\bigcup_{j=1}^{2}A_j\right)^c=(A_1\cup A_2)^c=[Morgan\space law]=A_1^c\cap A_2^c=\bigcap_{j=1}^{2}A_j^c$

2) Induction step, let the statement is true for n=k, i.e.

$\left(\bigcup_{j=1}^{k}A_j\right)^c=$ $\bigcap_{j=1}^{k}A_j^c$

Considerthe case n=k+1:

$\left(\bigcup_{j=1}^{k+1}A_j\right)^c=\left(\bigcup_{j=1}^{k}A_j\cup A_{k+1}\right)^c=[Morgan\space law]=$

$\left(\bigcup_{j=1}^{k}A_j\right)^c\cap A_{k+1}^c=[induction\space hypothesis]$ =$\bigcap_{j=1}^{k}A_j^c\cap A_{k+1}^c=\bigcap_{j=1}^{k+1}A_j^c$ , so statement is true for n=k+1, induction step is verified, therefore the statement is proved by math inductionmethod.

Question 3.

$Let \space A_1=A,A_2=B,A_3=C$

Then $(A\cup B\cup C)^c=$ $\left(\bigcup_{j=1}^{3}A_j\right)^c=[Question\space 2]=$ $\bigcap_{j=1}^{3}A_j^c=(A_1\ \cap A_3)=A\cap B\cap C$