Discrete Mathematics Questions and Answers

Answer: B

P is true and Q is false: \(R\) is reflexive but not transitive.

Reflexive: \((a,b)R(a,b)\) holds because \(a \le a\).

Not transitive: take \((1,5)R(2,1)\), true since \(1 \le 2\), and \((2,1)R(0,3)\), true since \(1 \le 3\). But \((1,5)R(0,3)\) needs \(1 \le 0\) or \(5 \le 3\), and both fail. The “or” lets each step use a different coordinate, so the chain does not carry through.

Hence options calling \(R\) transitive, or not reflexive, are wrong.

Answer: D

The count is \(2\binom{n}{2k}(n-2k)!\,(k!)^{2}\).

Build a separating permutation in steps:

1. Choose the 2k positions that the members of \(A \cup B\) will occupy: \(\binom{n}{2k}\) ways.
2. Fill the other \(n - 2k\) positions with the remaining elements: \((n-2k)!\) ways.
3. Decide which set comes first in the chosen positions: 2 ways. The first k of those positions then hold that set and the last k the other.
4. Arrange A within its k positions and B within its k positions: \(k!\,k! = (k!)^{2}\) ways.

Multiplying gives the answer. The option without the factor 2 counts only one of the two orders, the option without \((k!)^{2}\) forgets to arrange the members inside each set, and \(n!\) counts every permutation, separating or not.

Answer: D

The answer is S1 and ~S2: S1 is true and S2 is false.

A set is determined only by which elements it contains; repetition and order are ignored. Listing 2 twice or 5 five times in A adds nothing, so A = {1, 2, 3, 4, 5} = B, and S1 is true.

C = {1} has one element. D = {1, {1}} has two: the number 1 and the set {1}. Since {1} is an element of D but not of C, the sets differ and S2 is false. So the true combination is S1 and the negation of S2, which rules out the other three options.

Answer: C

The basic operations on sets are union, intersection, difference and subset.

A set abstract data type is defined by the operations of set theory: union (elements in either set), intersection (elements in both), difference (elements in one but not the other) and the subset test, along with membership.

Push and pop are stack operations. Insert and delete belong to many structures (lists, trees) and do not define a set. Traversing and merging are general operations on lists and files, not the defining operations of sets.