Дискретная математика

1. Which of the following sentences is a proposition?

o Can you help me? o Take this pencil. Ox + 2 = 6

o Why should you study discrete mathematics?

2. Let p be a proposition. The statement “It is not the case that p” is denoted by o p p

o p p

3. Let p and q be propositions. The proposition that is true when both p and q are true and is false otherwise is denoted by

o p  q

o p  q

o p  q

o p  q

4. Let p and q be propositions. The proposition that is false when p and q are both false

and is true otherwise is denoted by o p  q

o p  q

o p  q

o p  q

5. Let p and q be propositions. The proposition that is true when exactly one of p and q is true and is false otherwise is denoted by

o p  q

o p  q

o p  q

o p  q

6. Let p and q be propositions. The proposition that is false when p is true and q is false and is true otherwise is denoted by

o p  q

o p  q

o p  q

o p  q

7. Let p and q be propositions. The proposition that is true when p and q have the same truth values and is false otherwise is denoted by

o p  q

o p  q

o p  q

o p  q

8. Find the converse of p q .

9. Find the contrapositive of p  q . o q p

o p q o q p o p  q

10. Find the bitwise OR of the bit strings 1011 0010 and 0110 0110.

o 0010 0011 o 0011 0011 o 1010 1001

 1111 0110 o 0111 1100

11. Find the bitwise AND of the bit strings 1010 1010 and 1001 1001.

o 1011 1011 o 0011 0011 o 1100 1100 o 0101 0101

12. Find the bitwise XOR of the bit strings 0111 0101 and 1101 0101.

o 1111 0111 o 0101 0100

 1010 0000 o 0110 1010 o 1101 0101

14. Construct the truth table for the proposition p(qr).



o

15. Let p, q and r be the propositions “You get an A on the final exam”, “You do every exercise in this book” and “You get an A in this class” respectively. Write the proposition “Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class” using p, q and r and logical connectives.

o r(pq) o (pq)r o (pq)r

o r(pq)

16. Let p and q be the propositions “You get an A on the final exam” and “You get an A in this class” respectively. Write the proposition “To get an A in this class, it is necessary for you to get an A on the final” using p, q and logical connectives.

o q  p o q  p

o p  q

18. Find the implication that is false.

o If 2 + 3 = 6, then God exists.

o If 2 + 3 = 4, then 3 + 3 = 5.

o If pigs can fly, then 1 + 3 = 5.

o If 2 + 3 = 5, then 1 + 3 = 4.

19. Let p and q be the propositions “It is below freezing” and “It is snowing” respectively.

Express the proposition (pq)(pq)as an English sentence.

o It is below freezing or snowing, but it is not snowing only if it is below freezing.

o It is either below freezing or snowing, and it is not below freezing if it is snowing.

 It is either below freezing or it is snowing, but it is not snowing if it is below freezing. o It is below freezing but not snowing.

o If it is below freezing, then it is not snowing.

20. Let p and q be the propositions “You miss the final examination” and “You pass the course” respectively. Express the proposition p q as an English sentence.

o That you don’t miss the final examination is necessary for passing the course.

 If you don’t miss the final examination then you pass the course, and conversely. o Missing the final examination is sufficient for passing the course by you.

o You don’t miss the final examination or you pass the course. o If you don’t pass the course, you miss the final examination.

21. A compound proposition is a tautology if

o it is always false, no matter what the truth values of the propositions that occur in it.

o it is always true whenever each of the propositions that occur in it is true.

o it is only false when each of the propositions that occur in it is false.

o it is always true whenever all the propositions that occur in it have the same truth values.

22. The propositions p and q are logically equivalent if

o p  q is a tautology.

o (pq)(qp)is a tautology.

23. Find the proposition that is a tautology.

o (pq)(qp)

o (pq)(pq)

o (pq)(qp)

o (pq)(qp)

24. Which of the following logical equivalences is a distributive law?

o p(qr)(pq)r

 p(qr)(pq)(pr)

o pqqp

o p(qr)p(qr)

o pqqp

25. Find the proposition that is logically equivalent to p  q .

26. Find the proposition that is logically equivalent to p q .

o ( p q)

o (pq)(qp)

o (pq) o p  q

27. A proposition is a contingency if

o it is both a tautology and a contradiction o it is not a contradiction

 it is neither a tautology nor a contradiction o it is not a tautology

o it is not logically equivalent to any tautology

28. Find a compound proposition involving the propositions p, q and r that is true when p and q are false and r is true, but is false otherwise.

o p q r

o (pq)r o (pq)r o (pq)r

29. Find a compound proposition involving the propositions p, q and r that is false when p is false and q and r are true, but is true otherwise.

o pqr o pqr

o p(qr) o pqr

30. Find a compound proposition involving the propositions p, q and r that is true when p and q are true and r is false, but is false otherwise.

o (pr)(qr) o (pq)r

o r(pq) o (pq)r

31. Let P(x) be the statement “x spends less than three hours every weekday in class”, where the universe of discourse for x is the set of students. Express the proposition

“ xP(x)” in English.

o Every student doesn’t spend more than three hours every weekday in class.

o There is a student who doesn’t spend more than three hours every weekday in class. o There is a student who spends less than two hours every weekday in class.

 There is a student who spends no less than three hours every weekday in class. o Every student spends no more than six hours every weekday in class.

32. Let P(x, y) be the statement “x has taken y”, where the universe of discourse for x is the set of all students in your class and for y is the set of all computer courses at your

school. Express the proposition yxP(x,y) in English.

o There is a student at your class who has taken all computer courses at your school.

o There is a computer course at your school taken by at least one student in your class.

o For every student in your class there is a computer course at your school taken by him (or her).

33. Let P(x) be the statement “x can speak Kazakh” and let Q(x) be the statement “x knows the computer language Delphi”, where the universe of discourse for x is the set of all students at your university. Express the sentence “There is a student at your university who can speak Kazakh but who doesn’t know Delphi” in terms of P(x), Q(x),

quantifiers and logical connectives.

o x(P(x)Q(x))

 x(P(x)Q(x)) o x(P(x)Q(x)) o x(Q(x)P(x))

o x(P(x)Q(x))

34. Let S(x, y) be the statement “x + y = x  y”, where the universe of discourse for both variables is the set of integers. Which of the following statements is true?

o xyS(x,y) o xyS(x,y) o yxS(x,y) o yxS(x,y)

35. Let S(x, y) be the statement “x + 3y = 3x – y”, where the universe of discourse for both variables is the set of integers. Which of the following statements is true?

o xyS(x,y)

o xyS(x,y)

o xyS(x,y)

o yxS(x,y)

36. Rewrite the statement уxP(x,y) so that negations appear only within predicates

(that is, so that no negation is outside a quantifier or an expression involving logical connectives).

o yxP(x,y) o yxP(x,y) o xyP(x,y)

o xyP(x,y)

y(P(y)xS(x,y))

37. Rewrite the statement so that negations appear only within predicates (that is, so that no negation is outside a quantifier or an expression involving logical connectives).

o y(P(y)xS(x,y)) o y(P(y)xS(x,y)) o x(S(x,y)yP(y))

 y(P(y)xS(x,y)) o y(P(y)xS(x,y))

y(xP(,y)xR(x,y))

38. Rewrite the statement so that negations appear only within predicates (that is, so that no negation is outside a quantifier or an expression involving logical connectives).

o y(xP(x,y)xR(,y))

o x(yP(x,y)yR(x,y)) o y(xP(x,y)xR(x,y)) o y(xP(x,y)xR(x,y))

y(xzP(x,y,z)xzS(x,y,z))

39. Rewrite the statement so that negations appear only within predicates (that is, so that no negation is outside a quantifier or an expression involving logical connectives).

o y(xzP(x,y,z)xzS(x,y,z)) o y(xzPyx(,,)xzS(x,y,z))

o x(yzP(x,y,z)yzS(x,y,z))

 y(xzPyx(,,)xzS(x,y,z)) o xz(yP(x,y,z)yS(x,y,z))

40. Which of the following statements is true if the universe of discourse for all variables is the set of all integers?

o n(n2 8)

o n(n2 1)

o nm(nm3)

o nm(nmn2m2)

41. Which of the following statements is true if the universe of discourse of each variable is the set of real numbers?

o xy(xy2)

o xy(xy4)

o xy(xyyx)

o yx(x3 y)

42. When the statement yxP(x,y) is false?

o For every y there is an x for which P(x, y) is true. o There is an x such that P(x, y) is false for every y. o There is a pair x, y for which P(x, y) is false.

 There is a y such that P(x, y) is false for every x. o For every y there is an x for which P(x, y) is false.

43. When the statement yxP(x,y) is true?

o For every y there is an x for which P(x, y) is true. o For every x there is a y for which P(x, y) is false. o There is a pair x, y for which P(x, y) is true.

o There is an x for which P(x, y) is true for every y.

44. Let W(x, y) mean that x has visited y, where the universe of discourse for x is the set of all students in your school and the universe of discourse for y is the set of all Web

xyz((xy)(W(x,z)W(y,z)))

sites. Express the statement by a simple English sentence.

o For every Web site there exist two students who have visited it.

45. Let Q(x, y) be the statement “x has been a contestant on y”. Express the sentence “At least two students from your school have been contestants on Wheel of Fortune” in terms of Q(x, y), quantifiers, and logical connectives, where the universe of discourse for x is the set of all students at your school and for y is the set of all quiz shows on television.

o x(Qx,WheelzQxzxofF)Q(x,Fort)rtunz(f(,

121 2 12

xy(Q(x,WheelofFortune)xyQ(y,WheelofFortun))

o yxx((Qx,y)Q(x,y))Q(x,WheelofFortune))

12 1 2 1

o x(Q(x,WheelofFortun)z(xQ(z,WhofFortun)))eel

46. List the members of the set {x | x is a negative integer greater than (– 8)}.

o {– 8, –7, – 6, – 5, – 4, – 3, – 2, –1}

o {–9, –10, –11, …}

 {– 7, – 6, – 5, – 4, – 3, – 2, –1} o {0, 1, 2, 3, 4, 5, 6, 7}

o {9, 10, 11, 12, …}

47. List the members of the set {x | x is an integer such that x 2  5 }.

o {5; 5}

o {25}

o {–2, –1, 0, 1, 2} o {– 5; 5}

48. Find the power set of {0, 1}.

o {, {0, 1}}

o {{0}, {1}, {0, 1}} o {{0}, {1}}

 {, {0}, {1}, {0, 1}} o {, {1}}

49. Let A = {1, 2, 3, 4, 5}, B = {2, 4, 6, 8} and C = {2, 4}. Which of the following statements is true?

o ABC

 ABC

o ACB

o BCA

o BAC

50. Let A = {a, b, c, d, e, f}, B = {b, d, f, g, h, s} and C = {m, n, o, p, r, d, f}. Find (AC)B.

o {b, m, n, o, p, r, d , f} o {a, b, c, d, e, f}

o {m, n, o, p, r, d, f} o {b, d, e, f, g, h, r}

51. Let A = {0, 1, 2}, B = {y, z} and C = {b, c}. Find CBC.

o {(0, y, b), (1, y, b), (2, y, b), (0, z, b), (1, z, c), (2, z, c), (0, y, c), (1, y, c), (2, y, c)}

 {(b, y, b), (b, y, c), (b, z, b), (b, z, c), (c, y, b), (c, y, c), (c, z, b), (c, z, c)} o {(b, y),(b, z), (c, y), (c, z)}

o {(b, 0), (b, 1), (b, 2), (c, 0), (c, 1), (c, 2), (0, y), (1, y), (2, y)} o {(b, y, c), (c, y, b), (b, z, c), (c, z, b)}

52. Let U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} be the universal set, and let A = {0, 1, 3, 4, 7, 8}, B = {0, 2, 4, 6, 7, 8, 9}. Find A  B .

 {5} o 

o {0, 1, 2, 4, 6, 7, 8, 9}

o {0, 1, 2, 3, 4, 6, 7, 8, 9} o {0, 4, 7, 8}

53. Let U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} be the universal set, and let A = {0, 1, 3, 4, 7, 8}, B = {0, 2, 4, 6, 7, 8, 9}. Find B  A .

o {2, 6, 9} o {1, 3}

o {5}

 {0, 1, 3, 4, 5, 7, 8} o 

54. A set A is a proper subset of a set B if

o every element of A is also an element of B

o there is an element of B that is not an element of A

 every element of A is also an element of B and A  B. o there is an element of A that is also an element of B o B – A  and A  B .

55. Let A be a set. The power set of A is

o the set of all proper subsets of A o {, A}

o the set of all finite subsets of A

o the set of all proper subsets of A and the empty set.

56. Let A and B be sets. The Cartesian product of A and B is o {(a,b)|(aAbB)(aAbB)}

 the set of all ordered pairs (a, b) where a  A and b  B o the set of all ordered pairs (b, a) where a  A and b  B

o the set of all two-element sets {a, b} where a  A and b  B

57. Let A and B be sets. The union of A and B is o {x|(xAxB)(xAxB)}

 the set that contains those elements that are either in A or in B, or in both. o the set that contains those elements that are only either in A or in B.

o the set that contains those elements that are in both A and B. o the set that contains those elements that are in A but not in B.

58. Let A and B be sets. The intersection of A and B is

o the set that contains those elements that are either in A or in B, or in both. o the set that contains those elements that are in A but not in B.

o {x|(xA)(xB)}

o the set that contains those elements that are only either in A or in B.

59. Let U = {1, 2, 3, 4, 5, 6, 7, 8} be the universal set, and A = {1, 3, 4, 5, 8}, B = {2, 4, 5, 7, 8}. Find the complement of A.

i1

o {4, 5, 6, …} o {1, 2, 3, …} o {4, 5, 6, 7} o {1, 2, 3, 4}

62. Let f be a function from A to B. Then the codomain of f is

o the set A

o {b  B | there is an element a  A such that f(a) = b} o { a  A | there is an element b  B such that f(a) = b} o {b  B | there is no a  A with f(a) = b}

63. Let f be the function that assigns the first three bits of a bit string of length 3 or greater to that string. Then the codomain of f is

o {00, 01, 10, 11}

o the set of all bit strings of length 3 or greater

 {000, 001, 010, 100, 011, 101, 110, 111} o {0, 1}

o 

64. Let A = {a, b, c, d, e, g, h} and B = {0, 1, 3, 4, 5} with f(a) = 3, f(b) = 2, f(c) = 4, f(d) = 0, f(e) = 5, f(g) = 1 and f(h) = 3. Find the image of S = {c, d, e, g}.

o {4, 0, 3, 1}

o {0, 1, 2, 3, 4, 5} o {4, 0, 5, 1, 3}

 {0, 1, 4, 5} o {1, 2, 3, 4}

65. A function f: A  B is said to be injective …

o iff for every element b  B there is an element a  A with f(a) = b. o if f(x) < f(y) whenever x < y and x and y are in the domain of f.

o if f(x) ≠ f(y) implies that x ≠ y for all x and y in the domain of f.

o iff for every element a  A there is an element b  B with f(a) = b.

66. A function f: A  B is said to be surjective …

o iff for every element a  A there is an element b  B with f(a) = b.

 iff for every element b  B there is an element a  A with f(a) = b. o if f(x) < f(y) whenever x < y and x and y are in the domain of f.

o if f(x) > f(y) whenever x < y and x and y are in the domain of f. o iff f(x) = f(y) implies that x = y for all x and y in the domain of f.

67. The function f is a one-to-one correspondence, or a bijection, if

o it is either one-to-one or onto. o it is one-to-one but not onto. o it is onto but not one-to-one.

o the codomain and the range of f coincide.

68. Let f and g be the functions from the set of integers to the set of integers defined by f(x) = 3x – 4 and g(x) = 4x – 3. Find the composition of g and f.

o 12x – 13

 12x – 19 o 7x – 7

o 7x – 12 o x + 1

69. Let f be the function that assigns to each positive integer its first digit. Find the range of f.

o {xZ|x0}

o {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

o {x | x is an integer and x ≥ 0}

 {1, 2, 3, 4, 5, 6, 7, 8, 9} o the set of integers.

70. Find 1,98.

 2

o 1

o 1,01

o 0

o 1, 02

o –2,34

o 0

73. Find –2,34.

74. Find 1/10 + 9/10.

o 9/10

 1

o 0 o 2

o 1/10

75. Find 1/10 +9/10.

o 0

76. Find 1/3+ 1/3+1/3.

o 1/3 o 2/3

 2

o 1 o 0

77. Which of the following functions from {a, b, c, d} to itself is one-to-one?

o f(a) = c, f(b) = d, f(c) = b, f(d) = b o f(a) = a, f(b) = b, f(c) = d, f(d) = d o f(a) = a, f(b) = a, f(c) = a, f(d) = a o f(a) = d, f(b) = a, f(c) = a, f(d) = d

78. Which of the following functions from R to R is a bijection?

 f(x)6x5 o f(x)4x29

o f(x)x2 1 x4 1

o f(x) 1 x6 1

o f(x) x5 x10

79. Let S = {–3, 0, 3, 7}. Find f(S) if f(x) = ( x 2 + 2)/3.

o {0, 3, 17}

o {–2, 0, 3, 16} o {–3, 0, 3, 7}

81. Find 2/3 – 4/3.

o – 2/3

o 2

 0

o 1 o 3

82. There are 20 mathematics majors and 40 computer science majors at a college. How many ways are there to pick one representative who is either a mathematics major or a computer science major?

o 800 o 20 o 40  60 o 80

83. There are 20 mathematics majors and 40 computer science majors at a college. How many ways are there to pick two representatives, so that one is a mathematics major and another is a computer science major?

o 60 o 20

 800 o 40 o 80

84. How many bit strings of length 7 begin and end with a 0?

o 128  32 o 64 o 256 o 16

85. How many strings of five English letters that are start with B are there if letters can be repeated?

86. A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark. How many socks must he take out to be sure that he has at least three socks of the same color?

 5

o 3

o 15

o 4 o 6

87. A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark. How many socks must he take out to be sure that he has at least three brown socks?

o 3 o 5 o 4

 15 o 12

88. A bowl contains 8 red balls and 8 green balls. A woman selects balls at random without looking at them. How many balls must she select to be sure of having at least four balls of the same color?

o 12

o 8

 7

o 4 o 6

89. A bowl contains 8 red balls and 8 green balls. A woman selects balls at random without looking at them. How many balls must she select to be sure of having at least four red balls?

o 11  12

o 4 o 7 o 8

90. How many bit strings of length 5 begin with a 1?

o 64  16 o 32

o 8 o 5

91. How many bit strings are there of length four or less?

o 16

o 8 o 4

 31 o 32

92. Find a decreasing subsequence of maximal length in the sequence 13, 14, 7, 6, 15, 22, 10, 4, 25, 1.

o 13, 14, 15, 22, 25

o 25, 22, 15, 14, 13, 10, 7, 6, 4, 1

 14, 7, 6, 4, 1 o 22, 10, 4, 1 o 6, 15, 22, 25

93. How many permutations of {1, 2, 3, 4, 5} end with 3?

o 120

o 4

o 12  24

o 6

94. Let S = {1, 2, 3, 4, 5}. How many 3-permutations of S are there?

o 120  60 o 10 o 24

o 4

95. Let A = {a, b, c, d, e, f}. How many 4-combinations of A are there?

96. Fifty tickets, numbered 1, 2, 3, …, 50, are sold to 50 different people for a drawing. Six different prizes are awarded, including a grand prize (a trip to Moscow). How many ways are there to award the prizes if the person holding ticket 13 wins the grand prize?

o P(50, 5) o C(50, 6)

 P(49, 5) o C(49, 5) o P(49, 6)

97. Find the coefficient of x 7 y 5 in (x  y)12 .

o 664

 792 o 21 o 72

o 99

98. Find the coefficient of x 4 y 2 in (3x5y)6 . o 3  53

o 34  52  35  53

o 15 o –15

99. How many different strings can be made from the letters in STATISTICS, using all the letters?

101. A croissant shop has plain croissants, cherry croissants, chocolate croissants, almond croissants, apple croissants and broccoli croissants. How many ways are there to choose a dozen croissants?

o 12376 o 924

 6188 o 210 o 3003

102. How many ways are there to choose eight coins from a piggy bank containing 100 identical pennies and 80 identical nickels?

o P(100, 80) o 36

100! o 80!8!

o C(100, 8) + C(80, 8)

R1  R2 .

103. How many different strings can be made from the letters in ORONO, using all the letters?

104. Find P(8, 5).

o 336 o 56

 6720 o 28

o 72

105. Find C(8, 4).

106. List the ordered pairs in the relation R from A = {0, 1, 2, 3, 4} to B = {0, 1, 2, 3} where (a, b)  R if and only if a + b = 3.

o {(0, 3), (1, 2), (2, 1), (3, 0), (4, –1)}

o {(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}

 {(0, 3), (1, 2), (2, 1), (3, 0)} o {(0, 0), (1, 1), (2, 2), (3, 3)}

o {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (3, 4)}

107. Let R1 = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4)} and R2 = {(1, 2), (2, 1), (2, 4), (3, 1), (3,

2), (3, 4)} be relations from {1, 2, 3} to {1, 2, 3, 4}. Find

o {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4)}

o {(1, 1), (2, 2), (2, 3), (3, 3)}

o {(1, 1), (2, 1), (2, 4), (3, 1), (3, 2)} o {(1, 1), (1, 2), (2, 2), (3, 3), (3, 4)}

108. Let R = {(a, b), (b, c), (c, a), (d, b)} and S = {(a, a), (b, b), (c, c), (d, a)} be relations on A = {a, b, c, d}. Find S R .

o {(a, a), (b, b), (c, c), (d, a)}

o {(a, a), (b, a), (c, a), (c, b), (d, b), (d, c)}

o {(a, a), (a, b), (b, b), (b, c), (c, a), (c, c), (d, a), (d, b)}

o {(b, a), (c, b), (a, c), (b, d), (a, d)}

109. Represent the relation R = {(1, 1), (1, 2), (2, 1), (2, 3), (3, 2)} on {1, 2, 3} with a matrix (with the elements of this set listed in increasing order).

order).

o {(1, 2), (1, 3), (2, 1), (2, 3), (3, 2), (3, 3)} o {(1, 2), (2, 1), (3, 3)}

 {(1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2)} o {(1, 1), (2, 2), (3, 1), (3, 2), (1, 2), (1, 3)} o {(1, 1), (1, 3), (3, 1), (3, 3)}

111. List the triples in the relation {(a, b, c) | a, b and c are positive integers with 1 < a + b

< c ≤ 4}

o {(0, 2, 3), (0, 2, 4), (2, 0, 3), (2, 0 , 4), (1, 1, 3), (1, 1, 4), (0, 3, 4), (3, 0, 4)} o {(1, 2, 4), (0, 1, 3), (0, 2, 4), (0, 3, 4)}

o {(1, 2, 1), (0, 1, 3), (1, 1, 2), (2, 1, 1), (1, 0, 3), (3, 0, 1)}

112. A relation S on a set B is reflexive if

o (b, c)  S whenever (c, b)  S for all b, c  B

o it is not antisymmetric

o whenever (b, c)  S and (c, a)  S then (b, a)  S for all a, b, c  B o it is both symmetric and antisymmetric

113. A relation S on a set B is called antisymmetric if

o (b, c)  S whenever (c, b)  S for all b, c  B o (b, b)  S for every element b  B

o whenever (b, c)  S and (c, a)  S then (b, a)  S for all a, b, c  B o it is not symmetric

114. Let R = {(1, 1), (2, 1), (2, 3), (3, 1), (4, 2), (4, 3)}. Find R 2 .

o {(1, 1), (2, 1), (2, 3), (3, 1), (4, 2), (4, 3)}

 {(1, 1), (2, 1), (3, 1), (4, 1), (4, 3)} o {(1, 1), (2, 1), (3, 1), (4, 1)}

o {(2, 1), (4, 1), (3, 1), (2, 3)}

o {(1, 1), (1, 2), (1, 3), (2, 4), (3, 2), (3, 4)}

115. Let R = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (4, 4)} be a relation on {1, 2, 3, 4}. The relation R is

 Symmetric

o Reflexive

o antisymmetric o transitive

o reflexive and transitive

116. Let R = {(a, b) | a ≤ b} be a relation on the set of integers. The relation R is

o reflexive, symmetric and transitive o antisymmetric and symmetric

 reflexive, antisymmetric and transitive o non-reflexive and non-transitive

o non-antisymmetric and non-symmetric

117. Let R = {(1, 2), (2, 3), (3, 4), (4, 1), (4, 2)}. Find R3 .

o {(1, 4), (2, 3), (3, 3), (4, 3)}

 {(1, 4), (2, 1), (2, 2), (3, 2), (3, 3), (4, 3), (4, 4)} o {(1, 3), (2, 4), (3, 1), (3, 2), (4, 2), (4, 3)}

o {(1, 2), (2, 3), (3, 4), (4, 1), (4, 2)} o {(1, 1), (2, 2), (3, 3), (4, 4)}

Find R1  R2 .

o {(1, 0), (2, 1)}

o {(0, 0), (0, 2), (1, 2), (2, 0), (3, 0)} o {(1, 1), (2, 0)}

o {(2, 1)}

119. Represent the relation R= {(0, 1), (0, 3), (1, 2), (1, 3), (2, 0), (2, 1), (2, 3), (3, 2), (3, 3)} on {0, 1, 2, 3} with a matrix (with the elements of this set listed in increasing order).

120. List the ordered pairs in the relation on {1, 2, 3, 4} corresponding to the matrix

increasing order).

o {(1, 2), (1, 3), (1, 4), (2, 2), (3, 1), (3, 3), (4, 1)} o {(0, 2), (0, 3), (1, 0), (1, 2), (2, 0), (2, 2), (3, 0)}

 {(1, 3), (1, 4), (2, 1), (2, 2), (3, 1), (3, 3), (4, 1)} o {(0, 1), (0, 2), (0, 3), (1, 1), (2, 0), (2, 2), (3, 0)}

o {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (2, 4), (3, 1), (3, 2), (4, 2)}

121. Which of the following relations on {0, 1, 2, 3, 4} is an equivalence relation?

o {(0, 0), (0, 1), (1, 0), (2, 2), (2, 4), (3, 3), (4, 2)} o {(1, 2), (2, 3), (1, 3), (3, 4), (1, 4), (4, 4)}

o {(0, 0), (1, 1), (1, 3), (2, 2), (3, 2), (3, 3), (3, 4), (4, 4)}

 {(0, 0), (0, 3), (1, 1), (2, 2), (2, 4), (3, 0), (3, 3), (4, 2), (4, 4)} o {(0, 0), (0, 1), (1, 2), (0, 2), (2, 1), (3, 4), (4, 1), (3, 1)}

122. Which of the following are posets?

o (Z+, >) o (Z, >)

 (Z, ≥) o (Z, ≠) o (Z, <)

123. Find two incomparable elements in the poset (P({0, 1}), ).

o  and {0, 1} o  and {1}

o {0} and {0, 1} o {1} and {0, 1}

124. Let S = {0, 1, 2, 3}. With respect to the lexicographic order based on the usual “less than” relation find all pairs in S  S less than (1, 3).

o (0, 0), (1, 1), (1, 2), (2, 0), (2, 1), (0, 1), (0, 2), (0, 3)

o (2, 0), (2, 1), (2, 2), (3, 0), (1, 0), (1, 1), (1, 2), (0, 0), (0, 3) o (1, 0), (1, 1), (1, 2)

 (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2) o (0, 0), (1, 1), (2, 2), (3, 3)

125. Find maximal elements of the poset ({1, 2, 3, 5, 6, 15, 30, 45}, |).

126. Find minimal elements of the poset ({2, 3, 5, 6, 9, 30, 45}, |).

o 30, 45

 2, 3, 5 o 2, 3

o 5, 6

o 2

127. Find the lexicographic ordering of the following strings of lowercase English letters: computer, computing, comma, competent, computable.

o computer, computable, computing, comma, competent o comma, computable, computer, computing, competent

 comma, competent, computable, computer, computing o computer, competent, comma, computing, computable o computable, computer, computing, competent, comma

128. Which of the following sets is th

e equivalence class of 1 for congruence modulo 3?

o {…, –6, –3, 0, 3, 6, …} o {…, –4, –1, 2, 5, 8, …}

o {…, –7, –4, –1, 1, 4, 7, …}

 {…, –5, –2, 1, 4, 7, …} o {…, –9, –5, 1, 5, 9, …}

129. Let S = {1, 2, 3, 4, 5, 6, 7, 8}. Which of the following collections of sets forms a partition of S?

o {1, 2, 3, 4}, {5, 6, 7}, {7, 8}

 {1, 4, 8}, {3, 5, 7}, {2, 6} o {1, 2} {3, 4, 5}, {4, 6, 7, 8}

o {1, 2, 3}, {2, 4, 6}, {5, 7, 8} o {1, 2, 3, 7}, {3, 4, 5, 6, 8}

130. Find the greatest element of the poset ({2, 4, 5, 6, 10, 24, 50}, |).

131. Find the least element of the poset ({2, 3, 4, 6, 18, 36}, |).

132. Find the lexicographic ordering of the following 5-tuples: (1, 0, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (1, 1, 0, 0, 0).

o (0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (0, 1, 1, 1, 0), (1, 1, 0, 0, 0), (1, 0, 1, 0, 1). o (1, 1, 0, 0, 0), (1, 0, 1, 0, 1), (0, 1, 0, 1, 0), (0, 1, 1, 1, 0), (0, 1, 0, 0, 1).

 (0, 1, 0, 0, 1), (0, 1, 0, 1, 0), (0, 1, 1, 1, 0), (1, 0, 1, 0, 1), (1, 1, 0, 0, 0). o (1, 0, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (1, 1, 0, 0, 0). o (0, 1, 0, 1, 0), (0, 1, 0, 0, 1), (1, 1, 0, 0, 0), (0, 1, 1, 1, 0), (1, 0, 1, 0, 1).

133. Find maximal elements of the poset ({2, 4, 6, 7, 8, 14, 20, 21, 42}, |).

134. Find minimal elements of the poset ({3, 4, 7, 8, 9, 21, 36, 72}, |).

135. Find the greatest element of the poset ({1, 2, 3, 6, 7, 42, 126}, |). o 1

o there is no greatest element

o 42, 126 o 3, 6, 7

136. Find the least element of the poset ({5, 10, 25, 55, 70, 110}, |).

137. Find two incomparable elements in the poset (P({a, b}), ).

o  and {a, b} o  and {a}

o {a} and {a, b}

 {a} and {b}

o {b} and {a, b}

138. Which of the following relations on the set of all people is an equivalence relation?

o {(a, b) | a and b share a common grandmother} o {(a, b) | a and b speak a common language}

o {(a, b) | a and b don’t understand each other} o {(a, b) | a and b have a common friend}

139. Which of the following sets is the equivalence class of 3 for congruence modulo 5?

o {…, –8, –3, 3, 9, 15, …} o {…, –5, –1, 3, 7, 11, …}

o {…, –8, –3, 2, 7, 12, …} o {…, –10, –5, 0, 5, 10, …}

140. An element a of a poset (S, ≤) is called maximal if

o there is no b  S such that b < a o b ≤ a for all b  S

o a ≤ b for all b  S

o a is not a greatest element of (S, ≤).

141. How many edges are there in an undirected graph with 7 vertices each of degree 4?

142. How many edges are there in an undirected graph having 3 vertices each of degree 3 and 5 vertices each of degree 5?

o 34  17

o 8

o 16 o 25

143. Which of the following simple graphs does exist?

o a simple graph with seven vertices of degrees 0, 1, 1, 2, 3, 4, 6. o a simple graph with four vertices of degrees 0, 1, 1, 4.

o a simple graph with six vertices of degrees 1, 2, 3, 4, 5, 6.

 a simple graph with five vertices of degrees 1, 2, 2, 2, 3. o a simple graph with three vertices of degrees 0, 1, 2.

144. A simple graph differs from a multigraph since

o every multigraph has loops

o every multigraph has multiple edges or loops o every simple graph has loops

o every simple has loops or multiple edges

145. A pseudograph differs from a multigraph since

o every pseudograph has multiple edges and has no loops o every multigraph has loops and has no multiple edges

o every multigraph has no multiple edges and loops

o every pseudograph has no multiple edges and loops.

146. A directed graph differs from a directed multigraph since

o every directed multigraph has multiple edges and has no loops

o every directed graph has multiple edges and has no loops. o every directed graph has loops and multiple edges

o every directed multigraph has loops and has no multiple edges.