Discrete Mathematics Questions and Answers – Relations – Partial Orderings

This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Relations – Partial Orderings”.

1. Let a set S = {2, 4, 8, 16, 32} and <= be the partial order defined by S <= R if a divides b. Number of edges in the Hasse diagram of is ______
a) 6
b) 5
c) 9
d) 4
View Answer

          32   	
          /  	
       16  	
       / 	
     8  
   /   \  
  2     4

2. The less-than relation, <, on a set of real numbers is ______
a) not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric
b) a partial ordering since it is asymmetric and reflexive
c) a partial ordering since it is antisymmetric and reflexive
d) not a partial ordering because it is not antisymmetric and reflexive
View Answer

3. If the longest chain in a partial order is of length l, then the partial order can be written as _____ disjoint antichains.
a) l²
b) l+1
c) l
d) l^l
View Answer

4. Suppose X = {a, b, c, d} and π₁ is the partition of X, π₁ = {{a, b, c}, d}. The number of ordered pairs of the equivalence relations induced by __________
a) 15
b) 10
c) 34
d) 5
View Answer

5. A partial order P is defined on the set of natural numbers as follows. Here a/b denotes integer division. i)(0, 0) ∊ P. ii)(a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P. Consider the following ordered pairs:
i. (101, 22) ii. (22, 101) iii. (145, 265) iv. (0, 153)
The ordered pairs of natural numbers are contained in P are ______ and ______
a) (145, 265) and (0, 153)
b) (22, 101) and (0, 153)
c) (101, 22) and (145, 265)
d) (101, 22) and (0, 153)
View Answer

6. The inclusion of ______ sets into R = {{1, 2}, {1, 2, 3}, {1, 3, 5}, {1, 2, 4}, {1, 2, 3, 4, 5}} is necessary and sufficient to make R a complete lattice under the partial order defined by set containment.
a) {1}, {2, 4}
b) {1}, {1, 2, 3}
c) {1}
d) {1}, {1, 3}, {1, 2, 3, 4}, {1, 2, 3, 5}
View Answer

7. Consider the ordering relation a | b ⊆ N x N over natural numbers N such that a | b if there exists c belong to N such that a*c=b. Then ___________
a) | is an equivalence relation
b) It is a total order
c) Every subset of N has an upper bound under |
d) (N,|) is a lattice but not a complete lattice
View Answer

8. Consider the set N* of finite sequences of natural numbers with a denoting that sequence a is a prefix of sequence b. Then, which of the following is true?
a) Every non-empty subset of has a greatest lower bound
b) It is uncountable
c) Every non-empty finite subset of has a least upper bound
d) Every non-empty subset of has a least upper bound
View Answer

9. A partial order ≤ is defined on the set S = {x, b₁, b₂, … b_n, y} as x ≤ b_i for all i and b_i ≤ y for all i, where n ≥ 1. The number of total orders on the set S which contain the partial order ≤ is ______
a) n+4
b) n²
c) n!
d) 3
View Answer

10. Let (A, ≤) be a partial order with two minimal elements a, b and a maximum element c. Let P:A –> {True, False} be a predicate defined on A. Suppose that P(a) = True, P(b) = False and P(a) ⇒ P(b) for all satisfying a ≤ b, where ⇒ stands for logical implication. Which of the following statements cannot be true?
a) P(x) = True for all x S such that x ≠ b
b) P(x) = False for all x ∈ S such that b ≤ x and x ≠ c
c) P(x) = False for all x ∈ S such that x ≠ a and x ≠ c
d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x
View Answer

Sanfoundry Global Education & Learning Series – Discrete Mathematics.

To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]