CSE 321 Sample Questions from Old Midterms Instructions: Closed books, closed notes, no calculators, work all problems. In 50 minutes there would be 5-7 of these questions: 1. Let T(n) be defined by: T(0) = 1, T(n)=2*n*T(n-1). Prove that for all n>=0 , T(n) = 2^n n!. 2. Let x_1, x_2, ... , x_n be odd integers. Prove that x_1 x_2 ... x_n is also an odd integer. 3. Determine whether the following compound proposition is a tautology, a contradiction, or a contingency: ((s v p) /\ (s v ~p)) -> ((p -> q)-> r) 4. Find predicates P(x) and Q(x) such that FORALL x (P(x) (+) Q(x)) is true, but FORALL x P(x) (+) FORALL x Q(x) is false. (`(+)' denotes the exclusive-or). 5. Show that the following is a tautology: (((~p v q) ^ (p v r)) -> (q v r)) 6. Let T(n) be defined by: T(0) = 1, T(1) = 2, and T(n) = T(n-1) + 2T(n-2) for n>= 2. Prove that for all n>= 0, T(n) = 2^n. 7. Prove that the sum of an odd number and an even number is an odd number. 8. Use mathematical induction to show that 3 divides n^3 - n whenever n is a non-negative integer. 9. Show that the following compound proposition is a contingency (i.e., neither a tautology nor a contradiction): (p-> (q-> r)) -> (~p -> (~q -> ~r)) 10. Find predicates P(x) and Q(x) such that FORALL x (P(x) -> Q(x)) is false, but FORALL x P(x) -> FORALL x Q(x) is true. 11. Let the predicates D(x,y) mean ``team x defeated team y'' and P(x,y) mean ``team x has played team y.'' Give quantified formulas with the following meanings: a) Every team has lost at least one game. b) There is a team that has beaten every team it has played. 12. Prove that there exists an n>= 0 such that 2^n +1 is not prime. 13. Let g_n be defined by: g_0=1, and g_{n+1}= sum from i=0 to n of g_i for n >= 0. Prove that for n>= 1, g_n= 2^{n-1}. 14. Let T be defined by T(1)=1 and T(n+1)= 2 T(n) + 2^n for n>= 1. Prove that for all n>= 1, T(n)<= n 2^{n-1}. 15. Define each of the following 6 properties in English AND then express each in predicate logic being as detailed as you can. You may use the predicates defined for earlier answers in solving later questions. Make sure you describe the universe of each quantifier and say what each predicate means: a) a divides b b) p is a prime number c) g is the greatest common divisor of a and b d) f is a 1-1 function from A to B e) f is an onto function from A to B 16. Prove the following for all natural numbers n by induction, The sum from i=0 to n of i/(2^i) = 2 - (n+2)/(2^n). 17. (a) Explain why or prove: for any predicates P and Q, if EXISTS x (P(x) ^ Q(x)) is true then (EXISTS x P(x)) ^ (EXISTS y Q(y)) must be true. (b) Give an example of a universe and meaning for predicates P and Q such that (EXISTS x P(x)) ^ (EXISTS y Q(y)) is true but EXISTS x (P(x) ^ Q(x)) is false (and therefore that they are not equivalent to each other.) 18. Let P(x,y) be the predicate "x< y" and let the universe for all variables be the real numbers. Express each of the following statements as predicate logic formulas using P: (a) For every number there is a smaller one. (b) 7 is smaller than any other number. (c) 7 is between a and b. (Don't forget to handle both the possibility that b is smaller than a as well as the possibility that a is smaller than b.) (d) Between any two different numbers there is another number. (e) For any two numbers, if they are different then one is less than the other. 21. Show that the following is a tautology: ((r -> (p v q)) -> (~p -> (r -> q))) 22. The amount of memory that an algorithm needs to solve a problem of size n is given by the function S where S(1)=2 and S(n+1)= 3 S(n) + 2 for n>= 1. Prove that for all n>= 1, S(n)= 3^n -1. 23. (a) Explain why or prove: for any predicate P, if Exists x Forall y P(x,y) is true then Forall y Exists x P(x,y) must be true. (b) Give an example of a universe and meaning for predicate P defined on that universe such that Forall y Exists x P(x,y) is true but Exists x Forall y P(x,y) is false. 24. Let V(x,y) be the predicate "x voted for y", let M(x,y) be the predicate "x received more votes than y", and let the universe for all variables be the set of all people. Express each of the following statements as predicate logic formulas using V and M: (a) Everybody received at least one vote. (b) Jane and John voted for the same person. (c) Ross won the election. (The winner is the person who received the most votes.) (d) Nobody who votes for him/herself can win the election. (e) Everybody can vote for at most one person. 25. True or false: (a) a congruent to b mod m, and b congruent to c mod m implies that a^2 is congruent to bc mod m. (b) If a and b are positive even integers with a >= b > 0, then gcd(a,b) = 2 gcd(a/2,b/2). (c) If a and b are positive integers with a >= b > 0, then gcd(a,b) = gcd(a-b,b). 26. Let P(m,n) be the statement "m divides n", where the universe of discourse for both variables is the set of positive integers. Determine the truth values of each of these propositions. (a) P(6,7) (b) for all m, for all n P(m,n) (c) exists m, for all n P(m,n) (d) P(m,n) -> for all r P(m,nr)