GATE CS 2006 Q22 — Sets, Relations and Functions

We can simplify the set expressions for $X$ and $Y$ using standard set theory identities. Recall that for any sets $A$ and $B$, the set difference is defined as $A - B = A \cap B^c$.

Step 1: Simplify $X$

$$\begin{align*} X &= (E \cap F) - (F \cap G) \\ &= (E \cap F) \cap (F \cap G)^c \\ &= (E \cap F) \cap (F^c \cup G^c) \quad \text{(by De Morgan's Law)} \\ &= (E \cap F \cap F^c) \cup (E \cap F \cap G^c) \quad \text{(by Distributive Law)} \\ &= \emptyset \cup (E \cap F \cap G^c) \quad \text{(since } F \cap F^c = \emptyset\text{)} \\ &= E \cap F \cap G^c \end{align*}$$

Step 2: Simplify $Y$

Let us first simplify the components of $Y = (E - (E \cap G)) - (E - F)$:

• First component: $$E - (E \cap G) = E \cap (E \cap G)^c = E \cap (E^c \cup G^c) = (E \cap E^c) \cup (E \cap G^c) = \emptyset \cup (E \cap G^c) = E \cap G^c$$
• Second component: $$E - F = E \cap F^c$$

Now, substitute these back into the expression for $Y$:

$$\begin{align*} Y &= (E \cap G^c) - (E \cap F^c) \\ &= (E \cap G^c) \cap (E \cap F^c)^c \\ &= (E \cap G^c) \cap (E^c \cup F) \quad \text{(by De Morgan's Law)} \\ &= (E \cap G^c \cap E^c) \cup (E \cap G^c \cap F) \quad \text{(by Distributive Law)} \\ &= \emptyset \cup (E \cap F \cap G^c) \quad \text{(since } E \cap E^c = \emptyset\text{)} \\ &= E \cap F \cap G^c \end{align*}$$

Since both $X$ and $Y$ simplify to $E \cap F \cap G^c$, we have $X = Y$.