CSE 321 Sample Questions from Old Midterms Fall 2004 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 predicated 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. Define set S of character strings over alphabet {a,b} by a) a is in S, ab is in S, b) If x is in S and y is in S then axb is in S and xy is in S. c) Nothing else is in S. Prove by induction that every string in \$S\$ has at least as many a's as b's. 18. Define a set S of numbers by: 4 and 12 are in S; If x is in S and y is in S then x+y is in S and x-y is in S; Nothing else is in S. Prove by induction that every number in S is divisible by 4. 19. (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.) 20. 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. Define a set S of strings over {a,b,c} by (a) lambda is in S, aba is in S, (b) If x is in S and y is in S then xcy is in S and xa is in S. (c) Nothing else is in S. Prove by induction that every string x in S has at least twice as many a's as b's. 24. (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. 25. 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.