Question 1 (8 points) Which of the following describes the proposition (q v -(q / (p A -p)))? O It is a contradiction O It is neither a tautology nor a contradiction It is both a tautology and a contradiction O It is a tautologyQuestion 2 (8 points) Which of the following describes modus tollens? O p - q, q . . p O - p - q, p:. q Op - q, p. . q Op - q, -q. . -p\fQuestion 4 (8 points) Which of the following is a synonym for a bijection? O an onto function a one-to-one correspondence an algebraic function O a one-to-one functionQuestion 5 (8 points) Which is the following sets is has the greatest cardinality? () Natural Numbers Q Integers () Rational Numbers () Real Numbers Question 6 (8 points) Which of the following functions is a one-to-one function? O f: R R, where f(x) = 5x* + 3 O f: Z Z, where f(n) = |n| - 1 O f: R R, where f(x) = 4x? Q f:Z - 7, where f(n) =n*+ 6 Question 7 (8 points) Assuming U represents the universal set and S represents any set, which of the following is a correct set property? Osno = 0 OSUU =S OSnu = UQuestion 8 (8 points) Given an alphabet E = {a, b, c} and a language L consisting of all strings of length s 3 that begin with a and end with an a, which of the following is the set of all strings in L? {a, aa, aaa, aba, aca} Ofa, aa, aba, aca} O {aaa, aba, aca} Ofa, aa, aaa}Question 2 (8 points) A B Which of the following describes (A U B) - (A N B) in the Venn diagram shown above? O The dark blue portion O The light blue portion on the left side Q The light blue portion on both sides O The light blue portion on the right side Question 10 (8 points) In the predicate calculus statement "dx R, x 2 y", which of the following correctly describes the variables x and y? O x is a free variable and y is a bound variable Q Both x and y are free variables O X is a bound variable and y is a free variable O Both x and y are bound variables Question 11 (8 points) Which of the following is the correct English translation of the predicate calculus statement "If any real number is positive, then its reciprocal is also positive"? VXER, x > 0 - 1/x > 0 XER, X > 0A 1 / X > 0 V X ER, X > 0 A 1/ X > 0 O 3 x ER, x > 0 - 1/ x > 0Question 12 (8 points) Assuming P is the set of professors and S is the set of students, which of the following is the correct predicate calculus translation of the sentence "At least one professor teaches some student"? 3p EP, As E S, p teaches s s saypeat d's = SA 'd = dA O 3p EP, Vs ES, p teaches s Vp EP, As ES, p teaches sQuestion 13 (8 points) a b Which of the following is true about spanning trees of the above graph? O It has many possible spanning trees O It has only one possible spanning tree O It has no possible spanning tree because it is disconnected O It has no possible spanning tree because it contains an isolated vertex Question 14 (8 points) a b Which of the following is true about the above graph? Q Every vertex has an odd degree Q Exactly one vertex has an odd degree Q Exactly one vertex has an even degree Q Every vertex has an even degree Question 15 (8 points) a b Which of the following best explains whether the above graph has a Hamiltonian circuit? O It does not have a Hamiltonian circuit because it has an isolated vertex O It does have a Hamiltonian circuit O It does not have a Hamiltonian circuit because it contains parallel edges It does not have a Hamiltonian circuit because every circuit would visit vertex d twice Question 16 (8 points) a b Which of the following is true about the above graph? O The graph is not connected O The graph has two parallel edges Q The graph has one isolated vertex O The graph contains circuits Question 17 (8 points) Which of the following is the proper way to begin a proof by contradiction of the theorem"Vp Vq,pe QAqeQ -p+ge Q" Q Suppose there exist two rational numbers whose sum is irrational Q Suppose there exist two irrational numbers whose sum is rational O Suppose the sum of every two rational numbers is irrational Q Suppose the sum of every two irrational numbers is rational Question 18 (8 points) In the proof by induction of the theorem Vne N,n>1-4+8+ ... +4n = 2(n*+n), which of the following would be the proper way to state the base case? O When n = 1, the sum consists of the first term 4 and the formula shows (1% + 1)? =4 O When n = 0, the sum consists of the first term O and the formula shows 0% + 0 = 0 O When n = 1, the sum consists of the first term 1 and the formula shows 1* =1 O When n = 1, the sum consists of the first term 4 and the formula shows 2(1% + 1) =4 Question 19 (8 points) When we prove the statement "All real numbers whose square is negative are irrational numbers, we are using which of the following kinds of proofs? Q Trivial proof Q Vacuous proof () Direct proof Q Proof by contradiction Question 20 (8 points) Assume A is the set of positive integers less than 10 and B is the set of positive integers less than or equal to 20, and R is a relation from A to B defined as follows: R ={(a,b) | a A, b B, ais divisible by 4 A b = 2a}. Which of the following ordered pairs belongs to that relation? () (6,12) () (12, 6) () (8,16) () (16,32) Question 21 (8 points) Given the relation R = {(n, m) | n, m Z, n