CSE 321      Sample Questions from Old Midterms     Fall 1997

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 \/ p) /\ (s \/ ~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. Suppose that a department offers 6 courses, and every student is required to 
   take exactly 3 of the courses.  Prove that if there are 25 students, then
   at least one pair of students takes exactly the same set of courses.

   If the requirement is changed so that students take at least 3
   courses, is there necessarily a pair of students taking the same set
   of courses?  (Justify your answer).


7. 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.


8. Prove that the sum of an odd number and an even number is an odd 
    number. 

9.  Use mathematical induction to show that 3 divides n^3 - n whenever n is 
     a non-negative integer.

10.  Show that the following compound proposition is a
     contingency (i.e., neither a tautology nor a contradiction):
     (p-> (q-> r)) -> (~p -> (~q -> ~r))

11.  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.


12.  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.

13.  Prove that there exists an n>= 0 such that 2^n +1 is not prime.

14.  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}.

15.  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}.

16.  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

17.   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).

18.  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.


19.  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.

20.  (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.)  


21.   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.


22. Show that the following is a tautology:
((r -> (p \/ q)) -> (~p -> (r -> q)))

23. 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.

24. 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.

26.  (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.

27. 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.