Analog tests for the course “Discrete mathematics”

Analog tests for the course “Discrete mathematics”

Which of the following sentences is a proposition?

A proposition is a statement that is either true or false, but not both.

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

Ø p

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

(conjunction)

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

(disjunction)

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

(exclusive or)

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

(implication)

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

(biconditional)

8. Find the converse of.

9. Find the contrapositive of .

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

1111 0110

11. Find the bitwise AND of the bit strings 1010 1010 and 1100 0001.

1000 0000

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

1000 1010

13. Construct the truth table for the proposition .

F F T F

14. Construct the truth table for the proposition .

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.

() r

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.

17. Evaluate the expression .

18. Find the implication that is false.

p) T q) F

19. Let p and q be the propositions “It is below freezing” and “It is snowing” respectively. Express the proposition as an English sentence.

It’s below freezing or snowing, and it’s freezing, if it’s snowing

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

You don’t miss the exam if and only if you pass the course

21. A compound proposition is a tautology if

A compound proposition that is always true

22. The propositions p and q are logically equivalent if

have the same truth values in all possible cases

23. Find the proposition that is a tautology.

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

25. Find the proposition that is logically equivalent to .

26. Find the proposition that is logically equivalent to .

27. A proposition is a contingency if

proposition that is neither a tautology nor a contradiction

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.

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.

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.

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 “ ” in English.

There is a student, who doesn’t spend less than three hours

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 in English.

There is a computer, that has been taken by all students

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.

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?

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?

36) 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).

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).

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).

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).

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

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

42) When the statement is false?

43) When the statement is true?

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 sites. Express the statement by a simple English sentence.

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.

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

. {-4, -3, -2, -1}

47) List the members of the set {x | x is an integer such that x² = 155}.

{}

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

{}, {0} {0,1} {0,2} {1,2} {0, 1, 2}

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

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

{b,c,d,e,f,g,h,s}

51) Let A = {0, 1, 2, 3}, B = {x, y, z} and C = {a, b, c}. Find

{a,a,x}{a,a,y}{a,a,z}{a,b,x}{a,b,y}{a,b,z}{a,c,x}{a,c,y}{a,c,z}{b,a,x}{b,a,y}{b,a,z}….

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

{0}

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

{0,1,3,4,5,7,8}

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

set A is a subset of the set B but that

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

the power set of A is the set of all subsets of the set A

56) Let A and B be sets. The Cartesian product of A and B is

57) Let A and B be sets. The union of A and B is

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

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

{3,7}

60) Let for i = 1, 2, 3, … Find

61) Let for i = 1, 2, 3, … Find

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

A-domain, B-codomain

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

8 codomain

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, h}.

F(s)={4,0,5,1,3}

65) A function f is said to be injective …

One-to-one, f(x) = f(y)

66) A function f is said to be surjective …

ONTO, for all y exist from codomain exist x from domain, f(x) = y

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

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) = 5x – 6 and g(x) = 2x + 3. Find the composition of g and f.

GoF = g(f(x)) = 2(5x – 6) +3 = 10x-9

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

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

70) Find ë2,97û.

71) Find é2,02ù.

72) Find ë–3,43û.

-4

73) Find é–3,43ù.

-3

74) Find ë2/30 + é7/30ùû.

75. Find é2/30 +ë7/30ûù.

76) Find éë1/4û+ é1/4ù+1/4ù.

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

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

79) Let S = {–2, 1, 2, 5}. Find f(S) if f(x) = é(x ² + 2)/3ù.

{2,1,9}

80) Find if and are functions from R to R.

. (15x-7)^3+12

81) Find é3/4 × ë4/9ûù.

82) There are 25 mathematics majors and 44 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?

25+44 = 69

83) There are 25 mathematics majors and 44 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?

25*44 = 1100

84) How many bit strings of length 6 begin and end with a 0?

2^4=16

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

26^5

86) A drawer contains a dozen brown socks and two 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 four socks of the same color?

87) A drawer contains two 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 four brown socks?

88) A bowl contains 9 red balls and 9 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 five balls of the same color?

89) A bowl contains 9 red balls and 9 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 five red balls?

9+5=14

90) How many bit strings of length 6 begin with a 0?

2^5 = 32

91) How many bit strings are there of length five or less?

2^5+2^4+2^3+2^2+2^1+2^0

92) Find a decreasing subsequence of maximal length in the sequence 13, 14, 10, 6, 15, 26, 12, 4, 25, 2.

{14,16,6,4,2}{13,10,6,4,2}

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

5!

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

6!/(6!-4!)=360

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

(5/3) = 10

96) Sixty tickets, numbered 1, 2, 3, …, 60, are sold to 60 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 25 wins the grand prize?

59!/54!

97) Find the coefficient of x⁷y⁶ in (x + y)¹³.

(13!/6!*7!)*1^7*1^6

98) Find the coefficient of x⁴y³ in (3x – 4y)⁷.

(7!/3!*4!) * 3^4 *(-4)^3

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

11!/2!2!2!

100) How many solutions are there to the equation where x₁, x₂, x₃ and x₄ are nonnegative integers such that

C(7,4) =7!/(4!*3!)=35

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

Answer is (12+(7-1))!/12!(7-1)!

102) How many ways are there to choose seven coins from a piggy bank containing 150 identical pennies and 90 identical nickels?

C(8,7)=8

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

6!/(2!*1!*1!*1!*1!)=3*4*5*6

104) Find P(9, 5).

P(9,5)= 9!/(9-5)!

105) Find C(7, 4).

C(7,4)=7!/((7-4)!*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 = 4.

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

107) Let R₁ = {(1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3, 4)} and R₂ = {(1, 2), (1, 3), (2, 4), (3, 1), (3, 2), (3, 3)} be relations from {1, 2, 3} to {1, 2, 3, 4}. Find .

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

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

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

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

110) List the ordered pairs in the relation on {1, 2, 3} corresponding to the matrix (where the rows and columns correspond to the integers listed in increasing order).

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

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

{(1,1,3)}

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

if (b, b) ϵ S for every element b ϵ B

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

if a, b ϵ B, if (a, b) ϵ S and (b, a) ϵ S, then a = b

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

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

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

non-reflex,sym,non-antisym,non-tran;

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

partical ordering

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

R^2={(1,2),(2,3),(3,1),(4,2),(4,3)}, R^3={(1,1),(2,2),(3,3),(4,1),(4,2)}

118) Let R₁ = {(a, b) | a = b + 2} and R₂ = {(a, b) | a + b ≤ 3} be relations on {0, 1, 2, 3}. Find R₁ – R₂.

{(3,1)}

119) Represent the relation R= {(0, 0), (0, 2), (1, 1), (1, 3), (2, 0), (2, 2), (2, 3), (3, 0), (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 (where the rows and columns correspond to the integers listed in increasing order).

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

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

(ref,sym,tran)

122) Which of the following are posets?

123) Find two incomparable elements in the poset (P({1, 2, 3}), Í).

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 (2, 1).

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

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

13,45,60

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

2,3,5,7

127) Find the lexicographic ordering of the following strings of lowercase English letters: compute, computable, commandos, competition.

commandos, competition, computable, compute

128) Which of the following sets is the equivalence class of 2 for congruence modulo 3?

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

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

24,100

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

Кажется 2, 5, 6 (no least elements)

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

(0,1,0,1,0)(0,1,1,0,1)(1,1,0,0,0),(1,1,1,0,1),(1,1,1,1,0)

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

20,42,72

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

2,3,7

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

136) Find the least element of the poset ({1, 5, 10, 11, 25, 55, 77, 111}, |).

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

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

139) Which of the following sets is the equivalence class of 4 for congruence modulo 5?

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

Reflexive, antisym, trans, partial ordering

141) How many edges are there in an undirected graph with 6 vertices each of degree 5?

(6*5)/2= 15 edges

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

((5*5)/2)+(7*5)/2=25 edges

143) Which of the following simple graphs does exist?

144) A simple graph differs from a multigraph since 145) A pseudograph differs from a multigraph since

146) A directed graph differs from a directed multigraph since

147) The union of two simple graphs and is

simple graph with vertex se V1 U V2 and edge set E1 U E2

148) A subgraph of a graph G = (V, E) is …

149) A vertex of a graph is called isolated if

it has degree 0

150) A vertex of a graph is called pendant if

it has degree 1

151) Find the degree of the vertex b in the graph K:

Deg(b) = 1

152) Find the degree of the vertex a in the graph K:

Deg(a) = 3

153) Find the degree of the vertex c in the graph K:

Deg(c) = 4

154) The following graph is called …

Simple graph

155) Which of the vertices of the following graph is isolated?

Non of them

156) Which of the vertices of the following graph is pendant?

Deg(d) = 1

157) Find the in-degree of the vertex c in the following graph with directed edges.

Indeg(c) = 3

158) Find the out-degree of the vertex c in the following graph with directed edges.

Outdeg(c) = 3

159) Find the in-degree of the vertex d in the following graph with directed edges.

Indeg (d) = 3

160) Find the out-degree of the vertex d in the following graph with directed edges.

Outdeg(d) = 0

161) How many subgraphs with at least one vertex does C₃ have?

17 subgraphs

162) How many subgraphs with at least one vertex does C₄ have?

163) A simple graph G is called bipartite if …

its vertex set v can ba partitioned into two disjoint nonempty set V1, V2, suc tat every edge in the graph connects a vertex in V1 and V2

164. Let G = (V, E) be a graph with directed edges. Then …

165. Which of the following statements is true?

An undirected graph has an even number of vertices of odd degree….

166. The complete graph on n vertices is called

Kn if simple graph that contains exactly one edge between each pair of distinct vertices

167. Find the coefficient of the term in the expansion of .

C(5,j3*x^5-3y³=5!/3!2!*x²y³

168. Which is the correct expansion of ?

C(4,j)*x^100-jy^j

169. What is the sum of the coefficients in the expansion of ?

E⁵_j=0=C(5,j)*x^5-jy^j

170. What is the sum of the coefficients in the expansion of ?

E⁵_j=0=C(5,j)*x^5-jy^j

171. Consider the complete graph on 4 vertices. Which of the following statements is true?

…It has 30 edges and each of its vertices has degree 6 …

172. Consider the complete graph on 5 vertices. Which of the following statements is true?

…It has 42 edges and each of its vertices has degree 7 …

173. Try to draw a graph with the following degrees for its five vertices: 1, 1, 1, 2, 3? Which statement is true?

..Such a graph has five edges…

174. Try to draw a graph with the following degrees for its four vertices: 2, 2, 2, 2? Which statement is true?

175. Try to draw a graph with the following degrees for its five vertices: 3, 3, 3, 3, 3? Which statement is true?

176. How many permutations of {1, 2, 3, 4, 5} start with 1?

4!

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

P=5!/(3-2)! = 60

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

P = 6!/2!4!=15

179. Let for i = 1, 2, 3, … Find

A₁ =2; A₂=3; A₃=4; = {2,3,4,5,6,7}

180. Let for i = 1, 2, 3, … Find

A₁=3,4,5,6,7,8,9…; A₂=4,5,6,7,8,9…; A₃=5,6,7,8,9…; ={5,6,7,8…}

181. What rule of inference is used in the following argument: Alice is a runner. Therefore, Alice is either a runner or a cyclist.

Addition

182. What rule of inference is used in the following argument: If Alex sleeps all day, he does not do his homework. If he does not do his homework, he will receive F at the school. Therefore, if he sleeps all day, he will receive F at the school.

Hypothetical syllogism

183. What rule of inference is used in the following argument: It is either rainy today or I play football. It is sunny today. Therefore, I play football.

Disjunctive syllogism

184. For the following set of premises, what relevant conclusion or conclusions can be drawn?

Every student of this group does not a personal computer. Mary has a personal computer. Ivan does not have a personal computer.

185. For the following set of premises, what relevant conclusion or conclusions can be drawn?

He is either a skier or a runner. He is not a runner. If he is a runner, he will take part at a competition on running.

186. For the following set of premises, what relevant conclusion or conclusions can be drawn?

All students of your group like to prepare a dinner. Alice is a student of your group. David is not student of your group. Mary and Ivan do not like to prepare a dinner.

187. Mathematical induction is a technique for proving that P(n) is true for every positive integer n as follows:

188. How many strings of seven English letters are there those start with X and contain at least two vowels, if letters can be repeated?

189. How many solutions are there to the equation where and are nonnegative integers such that , and ?

190. How many solutions are there to the equation where is a nonnegative integer such that , , , , and ?

191. How many solutions are there to the equation where and are nonnegative integers such that and ?

n = 4, r= 0. C(3, 0) 3!/0!3! = 1

192. A bagel shop has onion bagels, poppy seed bagels, egg bagels, pumpernickel bagels, sesame seed bagels, raisin bagels, and plain bagels. How many ways are there to choose a dozen bagels with at least two of each kind?

193. Find all upper bounds of {4, 18} in the poset ({1, 2, 3, 4, 6, 9, 12, 18, 24, 36, 48, 60}, |).

(36)

194. Find the least upper bound of {4, 18}, if it exists, in the poset ({1, 2, 4, 6, 9, 18, 27, 36, 48, 60}, |).

(36)

195. Find all lower bounds of {36, 64} in the poset ({4, 6, 9, 16, 24, 36, 48, 64, 76}, |)

.(4)

196. Find the greatest lower bound of {36, 64}, if it exists, in the poset ({2, 4, 6, 9, 16, 18, 27, 36, 54, 64, 80}, |).

(4)

197. Find the greatest lower bound of {18, 48}, if it exists, in the poset ({1, 2, 4, 5, 9, 12, 18, 24, 40, 48, 100}, |).

(4)

198. Find the least upper bound of {9, 24}, if it exists, in the poset ({1, 3, 6, 9, 10, 18, 24, 36, 40, 66, 98}, |).

(no)

199. Determine which of the following posets is a lattice:

({1, 4, 6, 12, 20}, |)(lattice) … ({3, 5, 10, 50, 150, 300}, |) (lattice)…

200. Determine which of the following posets is a lattice:

({1, 3, 6, 9, 18, 36}, |) (lattice)… ({2, 4, 6, 8, 12, 16, 24, 36, 44, 124}, |) (not lattice)

Дата добавления: 2015-11-04