Mathematics

Set Theory and Relations

355 Questions

Set theory involves the study of collections of objects and includes operations like union, intersection, and finding complements. Questions cover power sets, Cartesian products, and properties of empty sets. This foundational mathematical topic frequently appears in various competitive exams and university entrance tests.

set operationspower setscartesian productsset complementsproperties of empty setsset partitions

Set Theory and Relations Questions

Multiple choice

Which of the following is TRUE?

  1. Every subset of a regular set is regular.

  2. Every finite subset of a non-regular set is regular.

  3. The union of two non-regular sets is not regular.

  4. Infinite union of finite sets is regular.
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

Consider the set $S = \left\{ a , b , c , d \right\}$ . Consider the following 4 partitions $\pi_1,\pi_2,\pi_3,\pi_4$ on $S : \pi_1 = \left\{\overline{abcd}\right\} , \pi_2 = \left\{\overline{ab}, \overline{cd}\right\}, \pi_3 = \left\{\overline{abc}, \overline{d}\right\}, \pi_4 = \left\{\bar{a}, \bar{b}, \bar{c}, \bar{d}\right\}$. Let $\prec$ be the partial order on the set of partitions $S' = \{\pi_1,\pi_2,\pi_3,\pi_4\}$ defined as follows: $ \pi_i \prec \pi_j$ if and only if $\pi_i \text{ refines }\pi_j $. The poset diagram for $ (S',\prec)$ is:

Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

As $\pi$,$\propto$,$\pi$, only if $\pi$ refines $\pi$ $\pi_1$= {$\overline{abcd}$} refines $\pi_2$= {$\overline{ab}$,$\overline{cd}$} $\pi_3$= {$\overline{abc}$,$\overline{d}$} and these both refines  $\pi_4$={$\bar{a}\bar{b}\bar{c}\bar{d}$}

Multiple choice

The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

  1. Q solves the subset-sum problem in polynomial time when the input is encoded in unary

  2. Q solves the subset-sum problem in polynomial time when the input is encoded in binary

  3. The subset sum problem belongs to the class NP

  4. The subset sum problem is NP-hard
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, …, an}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X [i, j], 1$\le$i $\le$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a1, a2, …, a} whose elements sum to j.

Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?

  1. X[1, W]

  2. X[n, 0]

  3. X[n, W]

  4. X[n - 1, n]
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Multiple choice

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, …, an}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X [i, j], 1$\le$i $\ge$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a1, a2, …, a} whose elements sum to j.

Which of the following is valid for 2 $\le$ i $\le$ n and ai $\le$ j $\le$ W?

  1. X[i, j] = X[i - 1, j] vX [i, j - ai]

  2. X[i, j] = X[i - 1, j] vX [i, 1, j - ai]
  3. X[i, j] = X[i - 1, j] $\land$X [i, j - ai]
  4. X[i, j] = X[i - 1, j] $\land$X [i-1, j - ai]
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

Which of the following is TRUE?

  1. Every subset of a regular set is regular.

  2. Every finite subset of a non-regular set is regular.

  3. The union of two non-regular sets is not regular.

  4. Infinite union of finite sets is regular.
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

A set X can be represented by an array x [n] as follows:

x$\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & otherwise \end{cases}$ Consider the following algorithm in which x, y and z are boolean arrays of size n. algorithm zzz (x [ ], y[ ], z [ ] ) { int i; for (i = 0 ; i< n; ++i) z[i] = (x[i] Ù ~y[i]) Ú (~x[i] Ù y[i]) }

The set Z computed by the algorithm is

  1. (X U Y)
  2. (X $\cap$Y)
  3. (X − Y) $\cap$ (Y − X)

  4. (X − Y) U (Y − X)
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

$\text{Here}\ z = (x \land y') \lor (x' \land y)$

Multiple choice

The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

  1. Q solves the subset-sum problem in polynomial time when the input is encoded in unary

  2. Q solves the subset-sum problem in polynomial time when the input is encoded in binary

  3. The subset sum problem belongs to the class NP

  4. The subset sum problem is NP-hard
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, …, an}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X [i, j], 1$\le$i $\le$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a1, a2, …, a} whose elements sum to j.

Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?

  1. X[1, W]

  2. X[n, 0]

  3. X[n, W]

  4. X[n - 1, n]
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Multiple choice

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, …, an}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X [i, j], 1$\le$i $\ge$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a1, a2, …, a} whose elements sum to j.

Which of the following is valid for 2 $\le$ i $\le$ n and ai $\le$ j $\le$ W?

  1. X[i, j] = X[i - 1, j] vX [i, j - ai]

  2. X[i, j] = X[i - 1, j] vX [i, 1, j - ai]
  3. X[i, j] = X[i - 1, j] $\land$X [i, j - ai]
  4. X[i, j] = X[i - 1, j] $\land$X [i-1, j - ai]
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Multiple choice

Let A be a set having 'n' elements. The number of binary operations that can be defined on A, is
  1. $n^{n^2}$
  2. $2^{n^n}$
  3. $n^{2^n}$
  4. $2^{2^n}$
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

By definition, a binary operation defined on a set Y is a function $F : Y X Y \rightarrow ……..$ The domain, i.e. Y X Y has n × n elements (because Y has n elements). Each of ……… elements can be mapped to one of the 'n' elements of Y. So, totally $n^{n^2}$ binary is possible.