CSE 321 Sample Questions from Old Midterms Winter 2009
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. 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.
6. Prove that the sum of an odd number and an even number is an odd
number.
7. Use mathematical induction to show that 3 divides n^3 - n whenever n is
a non-negative integer.
8. 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.
9. Prove that there exists an n>= 0 such that 2^n +1 is not prime.
10. 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}.
11. 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}.
12. 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
13. 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).
14. (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.)
15. 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.
16. (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.
17. 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.
18. 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).
19. 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)