1. Which of the following sentences is a proposition?
o Can you help me?
o Take this pencil.
Ox + 2 = 6
3 + 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
p
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
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
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
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
p q
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
p q
o p q
o p q
8. Find the converse of p q .
o
q p
o
q p
o
q p
q p
o
p q
9. Find the contrapositive of p q . o q
p
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
1000 1000
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
13. Construct the truth table for the proposition
(pq)(pq)
.
o
p
q
(pq)(pq)
T
T
T
T
F
T
F
T
F
F
F
T
O
p
q
(pq)(pq)
T
T
T
T
F
F
F
T
T
F
F
F
p
q
(pq)(pq)
T
T
T
T
F
T
F
T
T
F
F
T
O
p
q
(pq)(pq)
T
T
F
T
F
F
F
T
T
F
F
F
o
p
q
(pq)(pq)
T
T
F
T
F
T
F
T
T
F
F
F
14. Construct the truth table for the proposition p(qr).
p
q
r
p(qr)
T
T
T
F
T
T
F
F
T
F
T
F
T
F
F
T
F
T
T
T
F
T
F
T
F
F
T
T
F
F
F
F
o
p
q
r
p(qr)
T
T
T
T
T
T
F
T
T
F
T
T
T
F
F
F
F
T
T
T
F
T
F
T
F
F
T
T
F
F
F
T
O
p
q
r
p(qr)
T
T
T
T
T
T
F
F
T
F
T
T
T
F
F
F
F
T
T
T
F
T
F
F
F
F
T
T
F
F
F
F
O
p
q
r
p(qr)
T
T
T
T
T
T
F
T
T
F
T
T
T
F
F
T
F
T
T
T
F
T
F
T
F
F
T
T
F
F
F
F
o
p
q
r
p(qr)
T
T
T
F
T
T
F
F
T
F
T
T
T
F
F
T
F
T
T
F
F
T
F
T
F
F
T
F
F
F
F
T
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(pq) o
(pq)r o
(pq)r
(pq)r
o r(pq)
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
p q
o p q
O
p q
17. Evaluate the expression
(1011010)1110110
.
o
11 0100
11 0000
o
00 0110
o
11 1111
o
01 0101
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.
If 2 + 3 = 5, then pigs can fly.
19. Let p and q be the propositions “It is below freezing” and “It is snowing” respectively.
Express the proposition (pq)(pq)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.
it is always true, no matter what the truth values of the propositions that occur in it.
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 (pq)(qp)is a tautology.
p q is a tautology.
o
p q is a contradiction.
o
( p q) is a contradiction.
23. Find the proposition that is a
tautology.
o (pq)(qp)
o (pq)(pq)
o (pq)(qp)
o (pq)(qp)
(pq)(pq)
24. Which of the following logical equivalences is a distributive
law?
o p(qr)(pq)r
p(qr)(pq)(pr)
o pqqp
o p(qr)p(qr)
o pqqp
25. Find the proposition that is logically equivalent to p q .
o
q p
o
p q
o
(pq)
p q
o
( p q)
26. Find the proposition that is logically equivalent to p q .
o ( p q)
o (pq)(qp)
( p q)
o (pq) 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 (pq)r o
(pq)r o
(pq)r
pqr
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.
pqr
o pqr o
pqr
o p(qr) o
pqr
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 (pr)(qr) o
(pq)r
pqr
o r(pq) o
(pq)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
“ xP(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 yxP(x,y) in English.
o There is a student at your class who has taken all computer courses at your school.
There is a computer course at your school taken by all students in your class.
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).
o For each of the computer courses at your school there is a student at your class who has
taken it.
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?
xyS(x,y)
o xyS(x,y) o
xyS(x,y) o
yxS(x,y) o
yxS(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 xyS(x,y)
o xyS(x,y)
yxS(x,y)
o xyS(x,y)
o yxS(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 yxP(x,y) o
yxP(x,y) o
xyP(x,y)
yxP(x,y)
o xyP(x,y)
y(P(y)xS(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)xS(x,y)) o
y(P(y)xS(x,y)) o
x(S(x,y)yP(y))
y(P(y)xS(x,y)) o
y(P(y)xS(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(xP(x,y)xR(,y))
y(xP(x,y)xR(x,y))
o x(yP(x,y)yR(x,y)) o
y(xP(x,y)xR(x,y)) o
y(xP(x,y)xR(x,y))
y(xzP(x,y,z)xzS(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(xzP(x,y,z)xzS(x,y,z)) o
y(xzPyx(,,)xzS(x,y,z))
o x(yzP(x,y,z)yzS(x,y,z))
y(xzPyx(,,)xzS(x,y,z)) o
xz(yP(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)
nm(n21m1)
o n(n2 1)
o nm(nm3)
o nm(nmn2m2)
41. Which of the following statements is true if the universe of discourse of each
variable is the set of real numbers?
o xy(xy2)
o xy(xy4)
x(x2 8)
o xy(xyyx)
o yx(x3 y)
42. When the statement yxP(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 yxP(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.
There is a y for which P(x, y) is true for every x.
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
xyz((xy)(W(x,z)W(y,z)))
sites. Express the statement by a simple English sentence.
o For every student in your school there exists another student who has visited only Web
sites visited by the first student.
There are two students in your school who have visited the same Web sites.
o There are two students in your school such that if a Web site has been visited by the
first student then this site has also been visited by the second student.
o For every Web site there exist two students who have visited it.
o For every Web site visited by a student in your school there exists another student who has
also 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.
xy(xyQ(x,WheelofFortuneofWheelyQ)(,))
o x(Qx,WheelzQxzxofF)Q(x,Fort)rtunz(f(,
121 2 12
xy(Q(x,WheelofFortune)xyQ(y,WheelofFortun))
o yxx((Qx,y)Q(x,y))Q(x,WheelofFortune))
12 1 2 1
o x(Q(x,WheelofFortun)z(xQ(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 ABC
ABC
o ACB
o BCA
o BAC
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 (AC)B.
o {b, m, n, o, p, r, d , f}
o {a, b, c, d, e, f}
{b, d, f, g, h, s}
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 CBC.
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}
the set of all subsets of 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)|(aAbB)(aAbB)}
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
o the set of all ordered n-tuples
(a,a ,...a, )
where
a AB
for all i = 1, 2, …, n.
1 2n
i
57. Let A and B be sets. The union of A and B
is o {x|(xAxB)(xAxB)}
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|(xA)(xB)}
the set containing those elements that are in both A and 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.
o
{1, 3, 6}
o
{4, 5, 8}
{2, 6, 7}
o
{6}
o
{1, 2, 3, 4, 5, 7, 8}
5
A{3,4,5,...i,2}
A
60. Let i
for i = 1, 2, 3, … Find
i
i
1
o
{3}
o
{5, 6, 7}
o {1, 2, 3, 4, 5}
{3, 4, 5, 6, 7}
o
{3, 4, 5}
4
A{i3,i4,i5,...}
A
61. Let i
for i = 1, 2, 3, … Find
i
i1
o {4, 5, 6, …}
o {1, 2, 3, …}
o {4, 5, 6, 7}
o {1, 2, 3, 4}
{7, 8, 9,…}
62. Let f be a function from A to B. Then the codomain of f is
o the set A
the set B
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.
iff f(x) = f(y) implies that x = y for all x and y 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.
it is both one-to-one and onto.
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 {xZ|x0}
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.
o
2
o
1,98
1
o
0
o
1,99
71. Find 1,01.
2
o 1
o 1,01
o 0
o 1, 02
72. Find –
2,34. o – 2
o –2,34
o 0
– 3
o
– 1
73. Find –2,34.
o
– 3
o
–2,34
o
0
– 2
o
– 1
74. Find 1/10 + 9/10.
o 9/10
1
o 0
o 2
o 1/10
75. Find 1/10 +9/10.
o
2
o
9/10
o
1/10
1
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
f(a) = d, f(b) = c, f(c) = b, f(d) = a
78. Which of the following functions from R to R is a bijection?
f(x)6x5 o
f(x)4x29
o f(x)x2 1 x4
1
o f(x) 1 x6 1
o f(x) x5 x10
79. Let S = {–3, 0, 3, 7}. Find f(S) if f(x) = ( x 2 + 2)/3.
2
2
;3
;17
o
3
3
o {0, 3, 17}
{1, 4, 17}
o {–2, 0, 3, 16}
o {–3, 0, 3, 7}
3
2 and g(x)5x3 are functions from R to R.
80. Find f g if f(x)x
o
5x3
7
o
x3 5x1
o
3
2)(5x3)
(x
(5x3)3 2
o x3 2
5x 3
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?
264
o
25
24
23
22
o
26
25
24
23
o
26
5
o
26
25
24
23
22
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?
o
360
o
60
o
30
15
o
120
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 (3x5y)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?
o
10!
o
C(10, 3)
o
720
50400
o
100800
100. How many solutions are there to the equation
xxxx10x , x , x
1234
where 1 2 3 and
x
4
are nonnegative integers such that
x 2, x 3?
1
3
o
252
56
o
84
o
5
o
112
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!
9
o C(100, 8) + C(80, 8)
103. How many different strings can be made from the letters in ORONO, using all
the letters?
o
10
o
120
o
6
o
12
20
104. Find P(8, 5).
o 336
o 56
6720
o 28
o 72
105. Find C(8, 4).
o
1680
o
35
o
140
70
o
840
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)}
{(1, 2), (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)}
{(a, b), (b, c), (c, a), (d, b)}
R1 R2 .
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).
1
1
0
1
1
1
o
0
0
1
1
1
0
1
0
1
0
1
0
0
1
1
1
0
0
o
1
1
0
1
0
1
0
0
0
o
1
0
1
1
1
1
1
0
1
o
0
0
0
110. List the ordered pairs in the relation on {1, 2, 3} corresponding to the matrix
1
0
1
0
1
1
(where the rows and columns correspond to the integers listed in increasing
1
1
0
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 {(0, 1, 2), (0,1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4), (1, 0, 2), (1, 0, 3), (1, 0, 4), (2, 0, 3), (2,
0, 4)}
{(1, 1, 3), (1, 1, 4), (1, 2, 4), (2, 1, 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
(b, b) S for every element b B
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
both (a, b) and (b, a) belong to S only if a = b for all a, 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)}
1. 118. Let R1 = {(a, b) | a = b + 1} and R2 = {(a, b) | a + b ≤ 3} be relations on {0, 1, 2, 3}.
Find R1 R2 .
{(3, 2)}
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).
0
0
1
0
1
0
1
0
o
0
1
0
1
1
1
1
1
0
1
0
1
0
0
1
1
1
1
0
1
0
0
1
1
1
0
1
0
0
1
1
0
o
1
1
0
1
0
1
1
0
0
0
0
0
1
1
1
1
o
0
0
0
0
1
1
1
1
1
0
1
0
0
1
0
1
o
1
0
1
0
0
1
1
1
120. List the ordered pairs in the relation on {1, 2, 3, 4} corresponding to the matrix
0
0
1
1
1
1
0
0
(where the rows and columns correspond to the integers listed in
1
0
1
0
1
0
0
0
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}
{0} and {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}, |).
o
15, 30, 45
30, 45
o
45
o
1
o
2, 3, 5
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}, |).
o
50
o
24, 50
o
4, 6, 10
o
2
there is no greatest element
131. Find the least element of the poset ({2, 3, 4, 6, 18, 36}, |).
o
2
o
2, 3
o
4, 6, 18
there is no least element
o
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}, |).
o
42
o
8, 14, 20
o
7, 21, 42
8, 20, 42
o
2, 7
134. Find minimal elements of the poset ({3, 4, 7, 8, 9, 21, 36, 72}, |).
o
8, 9, 21
3, 4, 7
o
3
o
21, 72
o
3, 7, 8
135. Find the greatest element of the poset ({1, 2, 3, 6, 7, 42, 126},
|). o 1
o there is no greatest element
126
o 42, 126
o 3, 6, 7
136. Find the least element of the poset ({5, 10, 25, 55, 70, 110}, |).
O
there is no least element
5
O
110
O
25, 70, 110
O
5, 10
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}
{(a, b) | a and b like the same films}
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, …}
{…, –7, –2, 3, 8, 13, …}
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
there is no b S such that a < b
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?
O
7
O
12
14
O
28
O
20
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
every multigraph has 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
every multigraph has multiple edges and has no loops
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
every directed multigraph has multiple edges
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.
147. The union of two simple graphs
G (V,E)
G (V,E)
1
11 and
2
2
2 is
O
the undirected graph with vertex set V1 V2
and edge set E1
E
2
such that
|EE||E||E|.
1
2
1
2
O
the undirected graph with vertex set
V V
2
such that
|VV||V||V|
1
1
2
1
2 and edge set
E1 E2 .
O
V V
2
E E
2
such that
|EE||E||E|.
the multigraph with vertex set 1
and edge set 1
1212
the simple graph with vertex set
V
1
V
2
and edge set E1
E2 .
O
the simple graph with vertex set
V
1
V
2
and edge set E1
E2 .
148. A subgraph of a graph G = (V, E) is
o a graph H = (W, F) where WV and FE.
a graph H = (W, F) where W V and F E.
o a graph H = (W, F) where V W and E F.
o a graph H = (W, F) where W V and F E.
o a graph H = (W, F) where WV and FE.
149. A vertex of a graph is called isolated if
o its degree equals 1
o its degree equals 2
o it is not pendant
its degree equals 0
o there is no true answer
150. A vertex of a graph is called pendant if
o its degree equals 0
o its degree equals 2
its degree equals 1
o it is not isolated
o there is no true answer
o
