GATE CSE 2023 | Memory Based Question: 17 [closed]

Answer 1

This is proof regarding the given question.

Here Binary operation $\Delta$ is defined on the power set of set $x.$ i.e. $2^x.$

Now, say, there are two elements $A$ and $B$ of the set $2^x$ and 

$A \Delta B = (A-B)  \cup (B-A) = (A \cup B) \  – \ (A \cap B) $

$1) $ Closure:

Since, $2^x$ is a power set of set $x$, so it contains all the subsets of set $x$ and so, $(A \cup B) \in 2^x$ and $(A \cap B) \in 2^x$

and so,  $(A \cup B) \  – \ (A \cap B) \in 2^x $ and hence, $A \Delta B \in 2^x \ \ $ $\forall A,B \in 2^x $

$2) $ Associativity:

(i) $A \Delta(B\Delta C) = A \Delta ((B\cup C)  \ – \ (B \cap C)) = A \Delta ((B\cup C)  \ \cap \ (B \cap C)’)$

$= A \Delta ((B\cup C)  \ \cap \ (B’ \cup C’)) = A \cup ((B\cup C)  \ \cap \ (B’ \cup C’)) \ – \ A \cap ((B\cup C)  \ \cap \ (B’ \cup C’)) $

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

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

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

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

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

 

(ii) $(A \Delta B) \Delta C = ((A \cup B) \ – \ (A \cap B)) \Delta C =  ((A \cup B) \ \cap \ (A \cap B)’) \Delta C$

$=  (((A \cup B) \ \cap \ (A \cap B)’) \cup C) \ – \ (((A \cup B) \ \cap \ (A \cap B)’) \cap C)$

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

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

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

Hence, Associativity satisfies. You can prove it using Venn diagram too.

$3)$ Identity:

Say $e \in 2^x$ is an identity element.

$A \Delta e = e \Delta A = A$ for $e \in 2^x$

$A \Delta e = A$ means $(A\cup e) \ –  \ (A \cap e) = A$

It is possible when $(A\cup e) = A$ and $ (A \cap e) = \phi$

$(A\cup e) = A$ is possible when $e=A$ or $e \subset A$ or $e = \phi$

But $e=A$ or $e \subset A$ then $(A \cap e) \neq \phi$ and so, identity element $e = \phi$  

$4)$ Inverse:

Say two elements $A,B \in 2^x$ and are inverse to each other.

$A\Delta B = B \Delta A = \phi$

So, $A\Delta B = \phi $ which means $(A \cup B) \  – \ (A \cap B) = \phi $

It is possible when $(A \cup B)  =  (A \cap B)$ because $(A \cup B)$ can’t be proper subset of $A\cap B$

And $(A \cup B)  =  (A \cap B)$ is possible when $A=B$

So, every element in $2^x$ is its own inverse.

Therefore (B), (D) 

Edit:

One more way to prove associativity is by converting set theory operations to digital logic operations i.e. $\cup$ to $+$ and $\cap$ to $.$

So, $A \Delta B = (A \ – \ B) \cup (B \ – A) = (A \cap B’) \cup (B \cap A’ ) = AB’ + B A’  = A \oplus B$

So, symmetric difference operation in set theory is equivalent to exor operation in digital logic.

Now, $(A \oplus B) \oplus C = (AB’ + BA’) \oplus C = (AB’ + BA’)C’ + (AB’ + BA’)’C$

$= AB’C’ + BA’C’ + (A’+B)(B’+A)C = AB’C’ + BA’C’ + A'B’C + BAC$

$= A(BC + B'C’) + A’(BC’+B'C) = A (B \oplus C)’ + A' (B \oplus C) = = A \oplus (B \oplus C)$

Answer 2

Detailed Video Solution: Group Theory Question

$\color{\red}{\text{ALL Discrete Mathematics Questions:}}$

Question 1: First Order Logic question, P(x) --> Q(x,y)

Question 2: Greedy Graph Coloring Algorithm

Question 3: Permutation question, Separating Permutations of A,B

Question 4: Equivalence Classes, Surjective Function Question