GATE CS Sets, Relations and Functions questions

The number of onto functions (surjective functions) from set $X = \{1, 2, 3, 4\}$ to set $Y=\{a,b,c\}$ is ______.

The cardinality of the power set of $\{0, 1, 2, \dots , 10\}$ is _______

Let $R$ be the relation on the set of positive integers such that $aRb$ and only if $a$ and $b$ are distinct and let have a common divisor other than $1.$ Which one of the following statements about $R$ is true?

The number of divisors of $2100$ is ____.

Let $R$ be a relation on the set of ordered pairs of positive integers such that $((p,q),(r,s)) \in R$ if and only if $p-s=q-r$. Which one of the following is true about $R$?

Suppose $U$ is the power set of the set $S = \{1, 2, 3, 4, 5, 6\}$. For any $T \in U$, let $|T|$ denote the number of elements in $T$ and $T'$ denote the complement of $T$. For any $T, R \in U \text{ let } T \backslash R$ be the set of all elements in $T$ which are not in $R$. Which one of the following is true?

Let $\#$ be the binary operator defined as $X\#Y = X'+Y'$ where $X$ and $Y$ are Boolean variables. Consider the following two statements. $(S_1)$ $(P\#Q)\#R = P\#(Q\#R)$ $(S_2)$ $Q\#R = (R\#Q)$ Which are the following is/are true for the Boolean variables $P, Q$ and $R$?

Let ܵ$S$ denote the set of all functions $f:\{0,1\}^4 \to \{0,1\}$. Denote by $N$ the number of functions from S to the set $\{0,1\}$. The value of $\log_2 \log_2N$ is _______.

Consider the following relation on subsets of the set $S$ of integers between $1$ and $2014$. For two distinct subsets $U$ and $V$ of $S$ we say $U\:<\:V$ if the minimum element in the symmetric difference of the two sets is in $U$. Consider the following two statements: $S1$: There is a subset of $S$ that is larger than every other …

The number of distinct positive integral factors of $2014$ is _____________

A non-zero polynomial $f(x)$ of degree 3 has roots at $x=1$, $x=2$ and $x=3$. Which one of the following must be TRUE?

Consider the set of all functions $f:\{0,1, \dots,2014\} \to \{0,1,\dots, 2014\}$ such that $f\left(f\left(i\right)\right)=i$, for all $0 \leq i \leq 2014$. Consider the following statements: $P$. For each such function it must be the case that for every $i,f(i) = i$. $Q$. For each such function it must be the case that for some $i,f(i)=i$. …

Let $X$ and $Y$ be finite sets and $f:X \to Y$ be a function. Which one of the following statements is TRUE?

A binary operation $\oplus$ on a set of integers is defined as $x \oplus y = x^{2}+y^{2}$. Which one of the following statements is TRUE about $\oplus$?

How many onto (or surjective) functions are there from an $n$-element $(n ≥ 2)$ set to a $2$-element set?

What is the possible number of reflexive relations on a set of $5$ elements?

Consider the binary relation $R = \left\{(x,y), (x,z), (z,x), (z,y)\right\}$ on the set $\{x,y,z\}$. Which one of the following is TRUE?

If $P, Q, R$ are subsets of the universal set U, then $$(P\cap Q\cap R) \cup (P^c \cap Q \cap R) \cup Q^c \cup R^c$$ is

What is the maximum number of different Boolean functions involving $n$ Boolean variables?

Let $S$ be a set of $n$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $S$ are: