CSE 321 Sample Questions from Old Midterms (version: 2/8/2007) 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!. Sol: Base Case: T(1) = 2*1*T(0) = 2 = 2^1 1!. Assume IH(k), therefore T(k) = 2^k k!. Now T(k+1) = 2*(k+1)*T(k) = 2 * (k+1) * 2^k * k! = [2 * 2^k] * [(k+1) * k!] = 2^(k+1) * (k+1)! Therefore IH(k) => IH(k+1), hence proved 2. Let x_1, x_2, ... , x_n be odd integers. Prove that x_1 x_2 ... x_n is also an odd integer. Sol: Base Case: If x_1, x_2 are odd so is x_1 x_2 Assume IH(k), therefore if x_1, x_2, ... , x_k are odd integers then x_1 x_2 ... x_k is an odd integer Now let x_1, x_2, ... , x_(k+1) be odd integers, Let us define the number a_1 = x_1 x_2 ... x_k By IH(k) a_1 is odd, thus a_1 x_(k+1) is also odd Therefore IH(k) => IH(k+1), hence proved 3. Determine whether the following compound proposition is a tautology, a contradiction, or a contingency: ((s v p) /\ (s v ~p)) -> ((p -> q)-> r) Sol: If s=T, p=T, q=F the above formula is F but when s=F, the above formula is T Therefore its a contingency 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). Sol: P(x) : x is odd Q(x) : x is even 5. Show that the following is a tautology: (((~p v q) ^ (p v r)) -> (q v r)) Sol: ((~p v q) ^ (p v r)) -> (q v r) = ~((~p v q) ^ (p v r)) v (q v r) = ( ~(~p v q) v ~(p v r) ) v (q v r) {DeMorgan's law} = (p ^ ~q) v (~p ^ ~r) v q v r {Associative Law} = ((p ^ ~q) v q) v ((~p ^ ~r) v r) {Commutative Law} = ((p v q) ^ (q v ~q)) v ((~p v r) ^ (r v ~r)) {Distibutive Law} = (p v q) v (~p v r) {(~a v a) = T} = p v ~p v q v r {Associative law} = T v q v r {(p v ~p) = T} = T {Domination} 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. Sol: Base Case: T(0) = 2^0, T(1) = 2^1. Assume IH(k) & IH(k-1), therefore T(k) = 2^k and T(k-1) = 2^(k-1) Now T(k+1) = T(k) + 2*T(k-1) = 2^k + 2*2^(k-1) = 2^k + 2^k = 2^(k+1) Therefore (IH(k-1) ^ IH(k)) => IH(k+1), hence proved 7. Prove that the sum of an odd number and an even number is an odd number. Sol: Let O be any odd number, therefore by definition 2 does not divide O Let E be any even number, therefore by definition 2 divides E Assume O+E is even, thus 2 | (O+E) and 2 | E => 2 | ((O+E) - E) => 2 | O Thus we get a contradicition, hence O+E is odd. 8. Use mathematical induction to show that 3 divides n^3 - n whenever n is a non-negative integer. Sol: Base Case: 3 | (0^3 - 0) Assume IH(k), therefore 3 | k^3 - k Now (k+1)^3 - (k+1) = (k^3 - k) + 3(k^2 + k) Hence 3 | ((k+1)^3 - (k+1)) Thus IH(k) => IH(k+1), which completes the proof 9. Show that the following compound proposition is a contingency (i.e., neither a tautology nor a contradiction): (p-> (q-> r)) -> (~p -> (~q -> ~r)) Sol: if p=F, q=F, r=T the above formula is False if p=T, q=T, r=F the above formula is True Hence it is a contingency. 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. Sol: P(x) = x is 5 Q(x) = x is even 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. Sol: Let V stand for forall and E stand for there exists a) Vx Ey D(y,x) b) Ex Vy (P(x,y) => D(x,y)) 12. Prove that there exists an n>= 0 such that 2^n +1 is not prime. Sol: Proof by construction- For n=3, we see that 9 is not a 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}. Sol: Base Case: g_1 = g_0 = 1 = 2^(1-1) Assume IH(i) for all i such that 1<= i <= k, therfore g_i = 2^(i-1) for all i, 1<= i <= k To prove IH(k+1), note that g_(k+1) = sum from i=0 to k of 2^i = 2^k Hence proved. 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}. Sol: Base Case: T(1) = 1 = 1 * 2^0 Assume IH(k), therefore T(k) <= k 2^(k-1) Now T(k+1) = 2T(k) + 2^k <= 2k*2^(k-1) + 2^k = k 2^k + 2^k = (k+1)2^k Therefore T(k+1) <= (k+1)2^k Hence T(k) => T(k+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 Sol: a) English version: There exists an integer x such that ax = b divides(a,b):= Ex (ax = b) here domain of x is all integers b) English version: If a number divides p then the number is either 1 or p. prime(p):= Vx [divides(x,p) => (x=1) v (x=p)] here domain of x is all positive integers c) English version: g divides a and b, also if g1 divides a and g1 divides b then g1 <= g gcd(a,b,g):= divides(g,a) ^ divides(g,b) ^ Vx [ (divides(x,a)^divides(x,b)) => x <= g ] here domain of x is all positive integers d) English version: If x and y are two elements in A such that f(x)=f(y) then x=y one-one(f):= Vx Vy [ (f(x) = f(y)) => x=y ] here domain of x,y is A e) English version: For all elements y in B, there exists x in A such tha f(x)=y onto(f):= Vy Ex f(x) = y here domain of x is A and domain of y is 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). Sol: Base case: For n=0, we see that LHS=RHS=0 Assume IH(k), therefore sum from i=0 to k of i/(2^i) = 2 - (k+2)/(2^k). Now, sum from i=0 to (k+1) of i/(2^i) = 2 - (k+2)/{2^k} + (k+1)/{2^(k+1)} = 2 - 2(k+2)/{2^(k+1)} + (k+1)/{2^(k+1)} = 2 - 2(k+1)/{2^(k+1)} - 2/{2^(k+1)} + (k+1)/{2^(k+1)} = 2 - 2(k+1)/{2^(k+1)} + (k+1)/{2^(k+1)} - 2/{2^(k+1)} = 2 - (k+1)/{2^(k+1)} - 2/{2^(k+1)} = 2 - {(k+1)+2}/{2^(k+1)} Thus IH(k) => IH(k+1), Hence proved. 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.) Sol: (a) Assume that Exists x (P(x) ^ Q(x)) is true. Thus there is a c such that P(c) ^ Q(c) is true {Instantiation} Now P(c) => (Exists x P(x)) and Q(c) => (Exists x Q(x)) Thus ( P(c) ^ Q(c) ) => ( (Exists x P(x)) ^ (Exists x P(x)) ) Hence proved (b) Consider the following example- P(x) = x is even Q(x) = x is odd Thus, (Exists x P(x)) ^ (Exists y Q(y)) is true over the domain of number However, EXISTS x (P(x) ^ Q(x)) is false as no number is both odd as well as even 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. Sol: Let Ex stand for 'there exists x' and Vx stand 'for all x' (a) Vx Ey P(y,x) (b) Vx P(7,x) (c) { P(7,a) ^ P(b,7) } v { P(a,7) ^ P(7,b) } (d) Vx Vy Ez ((P(x,z) ^ P(z,y) V (P(y,z) ^ P(z,x)) (e) Vx Vy [ (x!=y) => {P(x,y) v P(y,x)} ] 21. Show that the following is a tautology: ((r -> (p v q)) -> (~p -> (r -> q))) Sol: (r -> (p v q)) -> (~p -> (r -> q)) = (~r v (p v q)) -> (~p -> (r -> q)) = (~r v (p v q)) -> (p v (r -> q)) = (~r v (p v q)) -> (p v ~r v q) = (~r v (p v q)) -> (~r v (p v q)) = T 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. Sol: Base case: For n=1, we see that S(1)=3^1 -1=2 Assume IH(k), therefore S(k) = 3^k -1 Now, S(k+1) = 3 S(k) + 2 = 3*(3^k - 1) + 2 = 3^{k+1) - 3 + 2 = 3^{k+1} - 1 Thus IH(k) => IH(k+1), Hence proved. 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. Sol: (a) Ex Vy P(x,y) means that there is a c such that Vy P(c,y) Thus for all y we have a x such that P(x,y) is true hence Vy Ex P(x,y) is true. Essentially, Ex Vy P(x,y) => Vy P(c,y) => Vy Ex P(x,y) (b) Let the universe be the set of natural numbers Let P(x,y) = x is greater than y Thus Vy Ex P(x,y) means that for every number y there is a number x greater than it. Hence Vy Ex P(x,y) is true. However the statement Ex Vy P(x,y) is not true as there is no number x which is greater than all other numbers. 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. Sol: (a) Vx Ey Voted(y,x) (b) [Vx (Voted(Jane,x) <=> Voted(John,x))] (c) Vx M(Ross,x) (d) Vx ( Voted(x,x) => (Ey M(y,x)) ) (e) Vx Vy Vz [ (Voted(x,y) ^ Voted(x,z)) => (y=z) ] 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 integers with a >= b > 0, then gcd(a,b) = 2 gcd(a/2,b/2) iff a and b are both even. (c) If a and b are positive integers with a >= b > 0, then gcd(a,b) = gcd(a-b,b). Sol: (a) True (b) True (c) True 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) Sol: (a) False (b) False (c) True (d) True