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. , because the sizes are always added without considering common elements
B.
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. 40 students
B. 30 students
C. 35 students
D. 25 students

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

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

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

Pigeonhole principle Easy
A. 1 person
B. 3 people
C. 4 people
D. 2 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. 5 balls
C. 3 balls
D. 6 balls

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

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

8 A relation on is reflexive when which condition holds?

Relations and their properties Easy
A. for every
B. for every
C. only when
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 or
B. Pairs belonging to both and
C. Pairs belonging to neither relation
D. Only pairs that can be formed by repeatedly composing with

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

Composition Easy
A. When every is related to both and
B. When some satisfies and
C. When belongs to both and
D. When 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.
B. in every case
C.
D. has no relation to any element

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 only
C. An isolated vertex labeled
D. A directed edge from to

14 Which three properties define an equivalence relation?

Equivalence relations Easy
A. Reflexive, antisymmetric, and transitive
B. Symmetric, antisymmetric, and irreflexive
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 sequence with repeated elements
C. A single ordered pair
D. An empty relation

16 Which properties must a partial order have?

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

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

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

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

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

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

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

20 Which edges are normally omitted from a Hasse diagram?

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

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. 30 students
B. 40 students
C. 35 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. 72 integers
B. 74 integers
C. 70 integers
D. 76 integers

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

Pigeonhole principle Medium
A. Exactly one month has no birthdays
B. At least two share a birth month
C. Exactly two share a birth month
D. At least three 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. 11 files
B. 9 files
C. 8 files
D. 10 files

25 Let and . Which statement correctly describes ?

Relations and their properties Medium
A. It is symmetric but not reflexive
B. It is reflexive and antisymmetric only
C. It is reflexive, symmetric, and transitive
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 antisymmetric
B. Irreflexive, symmetric, and transitive
C. Reflexive, antisymmetric, and transitive
D. Reflexive, symmetric, and transitive

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. Reflexivity
B. Symmetry
C. Transitivity
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
C. if divides
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. is comparable only with itself
B. is not a maximal element
C. has no comparable elements
D. and are incomparable

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

Partial and total ordering relations Medium
A. is both a partial order and a total order
B. is symmetric but not antisymmetric
C. is a partial order but not 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. 6 edges
B. 7 edges
C. 5 edges
D. 4 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. A preorder but not a partial order
B. A symmetric and transitive relation only
C. An equivalence relation but not an 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. No vertex lies on a cycle
C. Every edge has its reverse
D. Every edge is a loop

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 nonmodular
B. Modular and complemented
C. Nonmodular and uncomplemented
D. Distributive 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