## Friday, April 16, 2010

### how to prove it - ch1, sec1.4(operations on sets) ex

This section introduces set operations: Intersection, Union and Difference ($\cap , \cup$ and \)

Most important take away of this section is that, there are two main ways to prove equivalence of two sets
1. By drawing venn diagrams
2. By converting set operations into logic statements(with logic connectives) and then using logical equivalences. Following are the conversion of 3 basic set operations...
x $\in$ $A \cup B$ = $(x \in A) \lor (x \in B)$
x $\in$ $A \cap B$ = $(x \in A) \land (x \in B)$
x $\in$ $A \setminus B$ = $(x \in A) \land \lnot(x \in B)$

Ex-1(a) {3, 12}
Ex-1(b) {1,3,7,12,20,35} \ {x | x is a prime} = {1,12,20,35}
Ex-1(c) {1,3,12,35} $\cup$ ({3,7,12,20} \ {x | x is a prime}) = {1,3,12,35} $\cup$ {12,20} = {1,3,12,20,35}

Ex-2(a) {United States, Germany, China, Australia, France, India, Brazil}
Ex-2(b) {Germany} \ {x | x is a country in Europe} = {}
Ex-2(c) {Germany, France} \ A = {France}

Ex-4 look in the attached pic

Ex-5(a)
x $\in$ $A \setminus (A \cap B)$
= $(x \in A) \land x \notin (A \cap B)$
= $(x \in A) \land \lnot((x \in A) \land (x \in B))$
= $(x \in A) \land (\lnot (x \in A) \lor \lnot (x \in B))$
= $((x \in A) \land \lnot (x \in A)) \lor ((x \in A) \land \lnot (x \in B))$
= $(x \in A) \land \lnot (x \in B)$
= $x \in A \setminus B$

Ex-5(b)
x $\in$ $A \cup (B \cap C)$
= $(x \in A) \lor (x \in (B \cap C))$
= $(x \in A) \lor ((x \in B) \land (x \in C))$
= $((x \in A) \lor (x \in B)) \land ((x \in A) \lor (x \in C))$
= $(x \in A \cup B) \land (x \in A \cup C)$
= $x \in (A \cup B) \cap (A \cup C)$

Ex-6 look in the attached pic

Ex-7(a)

x $\in$ $(A \cup B) \setminus C$
= $(x \in (A \cup B)) \land (x \notin C)$
= $((x \in A) \lor (x \in B)) \land (x \notin C)$
= $((x \in A) \land (x \notin C)) \lor ((x \in B) \land (x \notin C))$
= $(x \in A \setminus C) \lor (x \in B \setminus C)$
= $x \in (A \setminus C) \cup (B \setminus C)$

Ex-7(b)

x $\in$ $A \cup (B \setminus C)$
= $(x \in A) \lor x \in (B \setminus C)$
= $(x \in A) \lor ((x \in B) \land \lnot(x \in C))$
= $((x \in A) \lor (x \in B)) \land ((x \in A) \lor \lnot(x \in C))$
= $(x \in (A \cup B)) \land \lnot((x \in C) \land \lnot(x \in A))$
= $(x \in (A \cup B)) \land \lnot(x \in (C \setminus A))$
= $x \in (A \cup B) \setminus (C \setminus A)$

Ex-8

(a) x $\in$ $(A \setminus B) \setminus C$
= $(x \in (A \setminus B)) \land (x \notin C)$
= $((x \in A) \land (x \notin B)) \land (x \notin C)$
= $(x \in A) \land (x \notin B) \land (x \notin C)$
= $(x \in A) \land \lnot((x \in B) \lor (x \in C))$
= $(x \in A) \land \lnot(x \in (B \cup C))$
= $x \in A \setminus (B \cup C)$

(b) x $\in$ $A \setminus (B \setminus C)$
= $(x \in A) \land \lnot(x \in (B \setminus C))$
= $(x \in A) \land \lnot((x \in B) \land \lnot(x \in C))$
= $(x \in A) \land ((x \notin B) \lor (x \in C))$
= $((x \in A) \land (x \notin B)) \lor ((x \in A) \land (x \in C))$
= $(x \in (A \setminus B)) \lor (x \in (A \cap C))$
= $x \in (A \setminus B) \cup (A \cap C)$

(c) from analysis of b, clearly b and c are same

(d) x $\in$ $(A \setminus B) \cap (A \setminus C)$
= $(x \in (A \setminus B)) \land (x \in (A \setminus C))$
= $((x \in A) \land (x \notin B)) \land ((x \in A) \land (x \notin C))$
= $((x \in A) \land (x \in A)) \land ((x \notin B) \land (x \notin C))$
= $(x \in A) \land \lnot((x \in B) \lor (x \in C))$
= $(x \in A) \land \lnot(x \in (B \cup C))$
= $x \in A \setminus (B \cup C)$

(e) from analysis of a and d, clearly a,d and e are same

Ex-9
A = {1,2,3)
B = {2,4}

$(A \cup B)$ = {1,2,3,4}
$(A \cup B) \setminus B$ = {1,3} , which is not A

Ex-11(a) Look in the attached pic, its clear that $(A \cup B) \setminus C \hspace{2} \subseteq \hspace{2} A \cup (B \setminus C)$

Ex-11(b)
Clearly, for two can be made non-equal by making $A \cap C$ non-empty
A = {1,2,3,4}
B = {3,4,5,6}
C = {0,2,3,4,7}

$(A \cup B) \setminus C$ = {1,5,6}
$A \cup (B \setminus C)$ = {1,2,3,4,5,6}

Rest of the exercises are pretty similar to the ones done, so I'm passing them :)