Back to Subject

Unit 3: Counting Principles and Relations - Practice Quiz

MTH401 — Discrete Mathematics 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 For two finite sets and , which formula gives ?

Principle of Inclusion-Exclusion Easy
A.
B. , because the sizes are always added without considering common elements
C.
D.

2 In a class, 20 students study Mathematics, 15 study Computer Science, and 5 study both. How many study at least one of the two subjects?

Principle of Inclusion-Exclusion Easy
A. 35 students
B. 40 students
C. 25 students
D. 30 students

3 If 6 objects are placed into 5 boxes, what must be true?

Pigeonhole principle Easy
A. Every box contains one object
B. Some box contains at least two objects
C. Exactly one box remains empty
D. Every box contains at least two objects

4 Among 13 people, at least how many must have been born in the same month?

Pigeonhole principle Easy
A. 4 people
B. 2 people
C. 1 person
D. 3 people

5 If objects are distributed among boxes, the generalized pigeonhole principle guarantees that some box contains at least how many objects?

Generalized pigeonhole principle Easy
A.
B.
C.
D.

6 If 25 balls are placed into 6 boxes, at least one box must contain at least how many balls?

Generalized pigeonhole principle Easy
A. 4 balls
B. 3 balls
C. 6 balls
D. 5 balls

7 A relation from a set to a set is any subset of which set?

Relations and their properties Easy
A.
B.
C. The set containing every possible subset of both and
D.

8 A relation on is reflexive when which condition holds?

Relations and their properties Easy
A. for every
B. only when
C. for every
D. for every

9 A relation is symmetric if implies which statement?

Relations and their properties Easy
A.
B.
C.
D.

10 If and are relations from to , what does contain?

Combining relation Easy
A. Pairs belonging to both and
B. Only pairs that can be formed by repeatedly composing with
C. Pairs belonging to neither relation
D. Pairs belonging to or

11 Let be a relation from to and a relation from to . When is ?

Composition Easy
A. When belongs to both and
B. When and
C. When every is related to both and
D. When some satisfies and

12 In the matrix of a relation , what does an entry of in row and column usually indicate?

Representing relation using matrices and graph Easy
A. in every case
B. has no relation to any element
C.
D.

13 In a directed graph representing a relation on , what represents ?

Representing relation using matrices and graph Easy
A. An undirected edge with no direction
B. A directed edge from to
C. A directed edge from to only
D. An isolated vertex labeled

14 Which three properties define an equivalence relation?

Equivalence relations Easy
A. Symmetric, antisymmetric, and irreflexive
B. Reflexive, antisymmetric, and transitive
C. Reflexive, asymmetric, and non-transitive
D. Reflexive, symmetric, and transitive

15 What do the equivalence classes of an equivalence relation on a set form?

Equivalence relations Easy
A. A partition of the set
B. A single ordered pair
C. An empty relation
D. A sequence with repeated elements

16 Which properties must a partial order have?

Partial and total ordering relations Easy
A. Reflexive, symmetric, and antisymmetric
B. Irreflexive, symmetric, and transitive
C. Reflexive, symmetric, and transitive
D. Reflexive, antisymmetric, and transitive

17 What additional condition distinguishes a total order from a partial order?

Partial and total ordering relations Easy
A. Every pair of elements is comparable
B. No element is related to itself
C. Each element has exactly one successor
D. Every pair of elements is equivalent

18 A partially ordered set is a lattice if every pair of elements has which two elements?

Lattice Easy
A. A reflexive pair and a symmetric pair
B. A greatest lower bound and a least upper bound
C. A predecessor and a successor
D. A greatest element and a least element

19 A nonempty subset of a lattice is a sublattice when it is closed under which operations?

Sub lattice Easy
A. Composition and inversion
B. Meet and join
C. Union and difference
D. Addition and subtraction

20 Which edges are normally omitted from a Hasse diagram?

Hasse diagram and its components Easy
A. Every edge connected to a maximal element
B. Reflexive and transitive edges
C. Only edges between comparable elements
D. All covering-relation edges

21 In a class of 120 students, 65 study Mathematics, 50 study Physics, and 30 study both subjects. How many students study neither Mathematics nor Physics?

Principle of Inclusion-Exclusion Medium
A. 35 students
B. 30 students
C. 40 students
D. 25 students

22 How many integers from 1 through 100 are divisible by at least one of , , or ?

Principle of Inclusion-Exclusion Medium
A. 70 integers
B. 72 integers
C. 76 integers
D. 74 integers

23 A group contains 13 people. What can be guaranteed about their birth months?

Pigeonhole principle Medium
A. At least three share a birth month
B. At least two share a birth month
C. Exactly one month has no birthdays
D. Exactly two share a birth month

24 A computer stores 73 files in 8 folders. What is the minimum number of files that must be in at least one folder?

Generalized pigeonhole principle Medium
A. 10 files
B. 8 files
C. 11 files
D. 9 files

25 Let and . Which statement correctly describes ?

Relations and their properties Medium
A. It is symmetric but not reflexive
B. It is reflexive, symmetric, and transitive
C. It is reflexive and antisymmetric only
D. It is transitive but not symmetric

26 Consider the relation on the integers defined by if and only if . Which properties does have?

Relations and their properties Medium
A. Reflexive, symmetric, and transitive
B. Reflexive, antisymmetric, and transitive
C. Irreflexive, symmetric, and transitive
D. Reflexive, symmetric, and antisymmetric

27 If and are equivalence relations on the same set, which combined relation is always an equivalence relation?

Combining relation Medium
A.
B.
C.
D.

28 Let and . Using , find .

Composition Medium
A.
B.
C.
D.

29 For on , what is ?

Composition Medium
A.
B.
C.
D.

30 A relation on has matrix Which set of ordered pairs represents ?

Representing relation using matrices and graph Medium
A.
B.
C.
D.

31 A directed graph of a relation on contains every loop and the edges , , , and , but not . Which property is disproved specifically by the path ?

Representing relation using matrices and graph Medium
A. Symmetry
B. Transitivity
C. Reflexivity
D. Antisymmetry

32 On the integers, define when . Which elements of belong to the equivalence class of ?

Equivalence relations Medium
A.
B.
C.
D.

33 Which relation on the set of integers is an equivalence relation?

Equivalence relations Medium
A. if divides
B. if divides
C. if
D. if

34 Consider the power set ordered by set inclusion. Why is this ordering not a total order?

Partial and total ordering relations Medium
A. has no comparable elements
B. and are incomparable
C. is comparable only with itself
D. is not a maximal element

35 On , define if divides . Which statement is correct?

Partial and total ordering relations Medium
A. is symmetric but not antisymmetric
B. is a partial order but not a total order
C. is both a partial order and a total order
D. is transitive but not reflexive

36 In the lattice of positive divisors of ordered by divisibility, what are the meet and join of and , respectively?

Lattice Medium
A. Meet , join
B. Meet , join
C. Meet , join
D. Meet , join

37 In the lattice ordered by inclusion, let and . What are and ?

Lattice Medium
A. and
B. and
C. and
D. and

38 Let be the lattice of positive divisors of under divisibility. Which subset is a sublattice of ?

Sub lattice Medium
A.
B.
C.
D.

39 For the poset , which elements are the unique minimal and maximal elements in its Hasse diagram?

Hasse diagram and its components Medium
A. Minimal: ; maximal:
B. Minimal: ; maximal:
C. Minimal: ; maximal:
D. Minimal: ; maximal:

40 Consider the poset ordered by divisibility. How many edges appear in its Hasse diagram?

Hasse diagram and its components Medium
A. 4 edges
B. 7 edges
C. 5 edges
D. 6 edges

41 How many surjective functions exist from an -element set to a -element set?

Principle of Inclusion-Exclusion Hard
A.
B.
C.
D.

42 How many integers in are divisible by none of , , and ?

Principle of Inclusion-Exclusion Hard
A.
B.
C.
D.

43 A subset is selected from . What is the minimum subset size that guarantees two selected numbers differ by exactly ?

Pigeonhole principle Hard
A.
B.
C.
D.

44 What is the least number of distinct integers that must be chosen from to guarantee that at least five chosen integers have the same remainder upon division by ?

Generalized pigeonhole principle Hard
A.
B.
C.
D.

45 Among points placed inside a square of side length , what distance between two points is guaranteed at most?

Generalized pigeonhole principle Hard
A.
B.
C.
D.

46 On , define if and only if divides . Which classification is correct?

Relations and their properties Hard
A. An equivalence relation but not an order
B. A symmetric and transitive relation only
C. A preorder but not a partial order
D. A partial order but not a total order

47 On , define when or . How many equivalence classes does have?

Relations and their properties Hard
A.
B.
C.
D.

48 Let and be equivalence relations on the same set. Which statement is always true?

Combining relation Hard
A. is an equivalence relation
B. is an equivalence relation
C. is an equivalence relation
D. is an equivalence relation

49 On , let and . How many ordered pairs belong to ?

Combining relation Hard
A.
B.
C.
D.

50 Let and . Using , what is ?

Composition Hard
A.
B.
C.
D.

51 For a relation on a finite set, which condition is equivalent to transitivity?

Composition Hard
A.
B.
C.
D.

52 A relation on has matrix . How many entries equal in the Boolean matrix ?

Representing relation using matrices and graph Hard
A.
B.
C.
D.

53 A directed graph represents a relation on a finite set. Which graph condition is equivalent to being both symmetric and antisymmetric?

Representing relation using matrices and graph Hard
A. Every vertex has a loop
B. Every edge is a loop
C. No vertex lies on a cycle
D. Every edge has its reverse

54 How many equivalence relations on satisfy and ?

Equivalence relations Hard
A.
B.
C.
D.

55 Let on . How many ordered pairs are in the smallest equivalence relation containing ?

Equivalence relations Hard
A.
B.
C.
D.

56 A poset is the disjoint union of a chain of length and a chain of length , with no comparabilities between the chains. How many total orders extend this partial order?

Partial and total ordering relations Hard
A.
B.
C.
D.

57 In the lattice with bottom , top , and three pairwise incomparable middle elements, which description is correct?

Lattice Hard
A. Distributive and complemented
B. Distributive and nonmodular
C. Nonmodular and uncomplemented
D. Modular and complemented

58 In the Boolean lattice ordered by inclusion, which family is a sublattice?

Sub lattice Hard
A.
B.
C.
D.

59 The poset has the componentwise order, where is an -element chain. How many edges are in its Hasse diagram?

Hasse diagram and its components Hard
A.
B.
C.
D.

60 For the divisibility poset on , how many cover relations appear as edges in the Hasse diagram?

Hasse diagram and its components Hard
A.
B.
C.
D.
Previous MCQ
Unit 2
Next MCQ
Unit 4