GATE CS Sets, Relations and Functions questions

Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is the number of sets $X_j$ that contain the element $i.$ That is $f(i)=\left | \left\{j \mid i\in X_j \right\} \right|$ then $\sum_{i=1}^{m} f(i)$ is:

Given a set of elements $N = {1, 2, ..., n}$ and two arbitrary subsets $A⊆N$ and $B⊆N$, how many of the n! permutations $\pi$ from $N$ to $N$ satisfy $\min(\pi(A)) = \min(\pi(B))$, where $\min(S)$ is the smallest integer in the set of integers $S$, and $\pi$(S) is the set of integers obtained by applying permutation $\pi$ to each …

Let $E, F$ and $G$ be finite sets. Let $X = (E ∩ F) - (F ∩ G)$ and $Y = (E - (E ∩ G)) - (E - F)$. Which one of the following is true?

A relation $R$ is defined on ordered pairs of integers as follows: $$(x,y)R(u,v) \text{ if } x<u \text{ and } y>v$$ Then $R$ is:

Let $X,Y,Z$ be sets of sizes $x, y$ and $z$ respectively. Let $W = X \times Y$ and $E$ be the set of all subsets of $W$. The number of functions from $Z$ to $E$ is

The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be:

Let $f: B \to C$ and $g: A \to B$ be two functions and let $h = f o g$. Given that $h$ is an onto function which one of the following is TRUE?

Let $R$ and $S$ be any two equivalence relations on a non-empty set $A$. Which one of the following statements is TRUE?

Let $A, B$ and $C$ be non-empty sets and let $X = ( A - B ) - C$ and $Y = ( A - C ) - ( B - C ).$ Which one of the following is TRUE?

Consider the binary relation: $S= \left\{\left(x, y\right) \mid y=x+1 \text{ and } x, y \in \left\{0, 1, 2\right\} \right\}$ The reflexive transitive closure is $S$ is

Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows: $g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$. Let $p_i$ denote the i-th prime number $\left(p_1 = 2\right)$. For a non-empty string $s=a_1 \dots a_n$, where each $a_i \in \Sigma$, define $f(s)= \Pi^n_{i=1}P_i^{g(a_i)}$. For a non-empty …

Let $f : A \to B$ be an injective (one-to-one) function. Define $g : 2^A \to 2^B$ as: $g(C) = \left \{f(x) \mid x \in C\right\}$, for all subsets $C$ of $A$. Define $h : 2^B \to 2^A$ as: $h(D) = \{x \mid x \in A, f(x) \in D\}$, for all subsets $D$ of $B$. Which of the following statements is always true?

Consider the set $\{a, b, c\}$ with binary operators $+$ and $*$ defined as follows: …

Let $(S, \leq)$ be a partial order with two minimal elements a and b, and a maximum element c. Let P: S $\to$ {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) $\implies$ P(y) for all $x, y \in S$ satisfying $x \leq y$, where $\implies$ stands for logical implication. Which of the following statements …

The binary relation $S= \phi \text{(empty set)}$ on a set $A = \left \{ 1,2,3 \right \}$ is

Let $f: A \rightarrow B$ a function, and let E and F be subsets of $A$. Consider the following statements about images. $S_1: f(E \cup F) = f(E) \cup f(F)$ $S_2: f(E \cap F)=f(E) \cap f(F)$ Which of the following is true about S1 and S2?

Consider the following statements: $S_1:$ There exists infinite sets $A$, $B$, $C$ such that $A \cap (B \cup C)$ is finite. $S_2:$ There exists two irrational numbers $x$ and y such that $(x+y)$ is rational. Which of the following is true about $S_1$ and $S_2$?

Consider the following relations: $R_1\:(a,b)$ iff $(a+b)$ is even over the set of integers $R_2 \:(a,b)$ iff $(a+b)$ is odd over the set of integers $R_3 \:(a,b)$ iff $a.b > 0$ over the set of non-zero rational numbers $R_4\:(a,b)$ iff $|a-b| \leq 2$ over the set of natural numbers Which of the following statements is correct?

Let $P(S)$ denotes the power set of set $S.$ Which of the following is always true?

A relation $R$ is defined on the set of integers as $xRy$ iff $(x + y)$ is even. Which of the following statements is true?