CS311 -- Discrete Structures ----Spring 2002

Final Exam Practice Questions AND REALLY ANSWERS

DISCLAIMER: THESE QUESTIONS DO NOT NECESSARILY REPRESENT WHAT WILL BE ON THE MIDTERM.

  1. Each of the following are proposed as rules of inference. Prove or disprove their validity. 
        (a)  p V q      (b)  (p & q) -> r
         not p            not r
        ------           ------------
         q               not p
    SOLUTION: The first is valid and the 2nd is invalid.
    (a) This is valid. There are two main ways to show this is valid. You can look at the truth table and show that whenever p V q is true and "not p" is also true, then q must be true. Or you can show that the following is a tautology: ((p V q) & (not p) ) -> q. You can show this either by a truth table or by simplifying the expression using rules of logic.
    Truth Table Method:
    pqp V qnot p
    0001
    0111
    1010
    1110
    You can see that p v q is true in lines 2,3, and 4. "not p" is true in lines 1 and 2. So both hypotheses are true in line 2 only. In line 2, q is true. Therefore if p V q is true and not p is true then q must be true so this is a valid rule of inference.
    Showing ((p V q) & (not p)) -> q is a tautology using rules of logic: 
        ((p V q) & (not p)) -> q    	given
    not ((p V q) & not p) V q   	p-> q <=> not p V q
    (not (p V q) V not not p ) V q	DeMorgan's Law
     ((not p & not q) V p) V q)		DeMorgan's Law
     ((not p V p) & (not q V p)) V q)    Distribution Law
      (T_0 & (not q V p)) V q           Inverse Law
       (not q V p) V q                  Identity Law
       (p V not q ) V q   		Commutative Law
        p V (not q V q)			Associative Law
        p V T_0				Inverse Law
        T_0				Domination Law
    (b) This is not a valid rule of inference. It should be intuitively clear. Modus Tollens would say that if r is false, then (p & q) has to be false. But by DeMorgan's Law this would give "not p V not q" , not necessarily "not p". Maybe p could be true and q could be false. Try substituting p = 1, q = 0 and r = 0. You will see that this is a contradiction.
    A rule of inference is valid if whenever the hypotheses (the things above the line) are true, then the conclusion is always true. We can show this invalid by assuming the hypotheses are true and showing the conclusion can be false. All we need is values for p, q, and r that makes (p & q) -> r true and not r true and not p false. You can figure out the right values by reasoning or using a truth table. Let's try the values we figured out above: p = 1, q = 0, and r = 0.
    Then (p & q) -> r = (1 & 0) -> 0 = 0 -> 0 = 1, as desired.
    Then not r = not 0 = 1, as desired. Then no p = not 1 = 0, which makes the conclusion false. Thus this is not a valid rule of inference.
  2. Write the following in English and state our opinion as to whether they are true or false (showing that you understand what they mean). N(x) = "x is a nerd" C(x) = "x works with computers" M(x) = "x is a man" F(x) = "x is friendly"
    Universe = people
    1. for-all x [N(x)-> ¬ F(x)]
      SOLUTION: "All nerds are unfriendly." This is not true in my opinion.
    2. there-exists x [C(x) & ¬ M(x)]
      SOLUTION: "There are some people who work with computers and are not men." Obviously true.
    3. ¬ there-exists x [C(x) & ¬ N(x)]
      SOLUTION: "There are not any people who work with computers and are not nerds" OR "All people who work with computers are nerds." I don't think so, not that there is anything wrong with being a nerd.
    4. ¬ for-all x [N(x) -> C(x)]
      SOLUTION: "Not all nerds are computer people." OR "There are some nerds who are not computer people." Could be true.
  3. Prove using the rules of inference or disprove. If proving, label each step. 
    (a)  Duke is a labrador retriever.
     All labrador retrievers like to swim.
     Therefore Duke likes to swim.
UNIVERSE = dogs

    
SOLUTION: Let L(x) = "x is a labrador retriever"; S(x) = "x likes to swim".
Given: L(Duke)
       for-all x [L(x) -> S(x)]
       Therefore S(Duke)
Proof:  1) for-all x [L(x) -> S(x)]	given
	2) L(Duke) -> S(Duke)		1 and universal specification
	3) L(Duke)			given
	4) S(Duke)			2 and 3 and Modus Ponens
This is too easy. I couldn't think of any better ones this afternoon.
(b)  All even numbers that are also greater than 2 are not prime.
     2 is an even number.
     2 is prime.
     Therefore some even numbers are prime.
UNIVERSE = numbers

    
SOLUTION: Let E(x) = "x is even"  and G(x) = "x is greater than 2" and P(x) = "x is prime".
Given: 	for-all x[(E(x) & G(x)) -> not P(x)]
	E(2)
	P(2)
	Therefore there-exists x [E(x) & P(x)]
Notice the first statement is irrelevant.  This was an exercise in not letting irrelevant
facts confuse matters.
Proof:
	1) E(2)		given
     	2) P(2)		given
	3) E(2) & P(2)	1 and 2 and conjunction
	4) there-exitsts x [E(x) & P(x)]	3 and existential generalization
(c)  If it is hot today or raining today then it is no fun to snow ski today.
     It is no fun to snow ski today.
     Therefore it is hot today.
UNIVERSE = days.
Let H(x) = "day x is hot"; R(x) = "on day x is raining";  and 
F(x) = "on day x it is fun to snow ski".

Given: 	for-all x [(H(x) V R(x)) -> not F(x)]
	not F(today)
	Therefore H(today)

This is an invalid argument. We need to show a counterexample.  In this case, since
the first statement is a for-all, if we can find can imagine any x (day) that makes
the hypotheses true and the conclusion false, then we have a counter-example.  

For example, imagine a day c when  H(c) = 0
				   R(c) = 1
				   F(c) = 0
Then the first and 2nd lines are true and the third, the conclusion is false.  This
is a counter-example.  Intuitively, there are lots of other reasons skiing is not
fun besides heat and rain.

(d) It is not fun to snow ski today if it is too warm or raining today.
    It is too warm today.
    Therefore it is not fun to snow ski today.
UNIVERSE = days.
Use the same predicates as for part (c).
Given:
  	for-all x [(H(x) V R(x)) -> not F(x)]  (notice this was stated as  "q if p")
        H(today)
        therefore not F(today)
This is a valid argument.
Proof:	1) for-all x [H(x) V R(x)) -> not F(x)	given
	2) H(today)				given
	3) (H(today) V R(today)) -> not F(today) 1 and universal specification
   	4) H(today) V R(today)			2 and conjunctive amplification
 	5) not F(today)				3 and 4 and Modus Ponens
  4. Answer the following counting questions.
    1. How many possible assignments are there for the logical expression (p V q) & (¬ p V r)?
      SOLUTION: there are 3 variables, 2 possible values each (0, 1) so 23 = 8
    2. You have 3 textbooks worth $100 and 3 textbooks worth $50. How many ways can you sell enough textbooks to make $200 exactly? (Hint: consider the possible cases)
      SOLUTION: There are 2 ways to do this. Either pick 1 $100 textbook and 2 $50 textbooks or 2 $100 textbooks. Since this is an "or" we will add the number of ways to do each case.
      Case 1: pick 1 $100 textbook and 2 $50 textbooks.
      Out of 3 $100 textbooks there are 3 ways to pick 1.
      Out of 3 $50 textbooks there are 3-choose-2 = 3 ways to pick 2.
      Therefore there are 3*3 = 9 ways to do both.
      Case 2: pick 2 $100 textbooks. There are 3-choose-2 ways to do this = 3.
      So the answer is #ways to do case1 + #ways to do case 2 = 9 + 3 = 12.
    3. You are planning a dinner party. There are 6 possible appetizers, 5 possible main courses, and 4 possible desserts. How many ways can you choose 3 appetizers, 2 main courses, and 3 desserts?
      SOLUTION: (6-choose-3)*(5-choose-2)*(4-choose-3) = (6!/3!3!)*(5!/2!3!)*((4!/3!1!)= (6*5*4/3*2)*(5*4/2)*(4) = 20*10*4= 800. See the "and" in the problem statement and think multiply.
    4. Same setup as above, how many ways can you choose 6 things total (any combination of appetizers, main courses, desserts that adds up to 6).
      SOLUTION: If you don't assume that you must choose at least one from each category (since the problem doesn't say this), then the answer is (6+5+4)-choose-6 = 15-choose-6 = 15!/6!9! = 15*14*13*12*11*10/6*5*4*3*2 = 15*(7*2)*13*12*11*(2*5)/15*12*4 = 7*13*11*5 = 5005. If you had to pick at least one from each category (appetizer, main dish, dessert) then the problem would be much harder. I don't know how to do it other than by analyzing cases, but there is a better way.
    5. How many binary strings of length n contain exactly 3 ones (assume n >= 3)?
      SOLUTION: n-choose-3
    6. How many license plates of 3 letters and 3 numbers contain the letters "c" and "s"? Assume no letters or numbers are repeated.
      SOLUTION: There are 24 possibilities for the third letter; 3! ways to arrange the three letters, and 10*9*8 possibilities for the numbers, giving: 24*6*10*9*8 =103680.
    7. Given 10 2-digit numbers,what is the probability that no 2 are the same? I.e., figure how many ways can you pick 10 that are all different and then divide by the total number of possible 2 digit numbers.
      SOLUTION: The number of ways to pick 10 2-digit numbers such that no 2 are the same: There are 100 ways to pick the first number; 99 to pick the second one different, 98 to pick the third one still different, etc, down to 91, giving: 100*99*98*97*96*95*94*93*92*91. There are 10010 ways to pick 10 2-digit numbers. So the probability of picking 10 such that no 2 are the same is: 100*99*98*97*96*95*94*93*92*92/10010. When you multiply this out on your calculator you better do it this way to avoid overflow: (100/100)*(99/100)*(98/100)...(91/100) = 0.628. So the probability is better than 50% that the numbers will all be different.
      ASIDE: This is the principle behind the birthday "paradox". If you have x people in a room, what is the probability that 2 will have the same birthday? When this probability is higher than 0.5, it is more likely that 2 people will have the same birthday than not. You would think it would take a high number of people to get a high probability of a duplicate, but the answer is 23. The probability of n people having different birthdays is: 365*364*363*....*(365-n+1)/365n. You can write a program to increment n until this value goes below 0.5. When n = 23, this value is 0.49 which means the probability of everyone having a distinct birthday is lower then the probability of two people having the same. I have tried this out in many classes and it always has worked out.
  5. True or False. Explain.
    1. Any relation is also a function.
      SOLUTION: False. Consider: {(1, 2), (1, 3)}. This is not a function.
    2. Any function is also a relation.
      SOLUTION: True. If you write the values of the function as {(x, f(x))|x in domain} then this is a relation.
    3. All functions have inverses.
      SOLUTION: Obviously false. E.g. f:R->R such that f(x) = x2. What is the inverse of -1? It is not in R.
    4. f(x):Z^+ -> positive-evens ; f(x) = 2x ; is bijective.
      SOLUTION: This is bijective for the given range and domain. It is 1-1 because if f(x = f(y) then 2x = 2y -> x = y.
      It is onto because for any positive even y, y is even, so y = 2k where k is an integer (and positive) so f(k) = y. Therefore it is bijective (since bijective means 1-1 and onto)..
  6. Give an example of an equivalence relation. SOLUTION: U = {1, 2, 3, ..., 10} a R b if a = b mod 2.
  7. Consider the following recurrence relation: 
       t(n) = t(n-1) + 2n-1
   t(1) = 1
    1. Guess a closed form formula by looking at small values.
      SOLUTION: 
          n   t(n)
    1    1
    2    4	t(2) = t(1)  + 2*2 - 1 = 1 + 4 - 1 = 4
    3    9      t(3) = t(2) + 2*3-1 = 4 + 6 - 1 = 9
GUESS:  t(n) = n2

    2.  Here is a wrong formula: t(n) = n^2 - n . Try to prove it by induction 
and show the proof fails.

      
Basis: for n = 1, the formula gives t(1) = 1*1 - 1 = 0, which is false. Therefore
the proof fails. 
This is too easy; not what I intended.  Try 2*n^2 - n instead.:
Claim: t(n) as defined above = 2*n2 - n.

      
Basis: By the definition, t(1) = 1.   By the formula, t(1) = 2*1*1 - 1 = 1.
The claim is true for the basis case.

      
I.H. Assume that t(n) = 2*n2 - n for some n > 1.

      
Induction step: Will show that t(n+1)  2*(n+1)2 - (n+1).
      
By the recursive definition we have:

        t(n+1) = t(n) + 2(n+1) - 1
       =   2*n^2 - n + 2(n+1) - 1  by I.H.
        = 2*n^2 - n +2n + 2 - 1
        = 2*n^2 + n + 1
This doesn't match the claim and there is no way to fix it.  Therefore the claim
appears to be false.

      

    3.  Prove your guessed formula by induction.

      
SOLUTION: Claim: for t(n) as defined above, t(n) = n2.

      Proof (by induction):
Basis: For n = 1, by the recursive definition t(1) = 1.  By the formula t(1) = 1*1  = 1.
Therefore the claim is true for the basis case.

      
I.H. Assume t(n) = n^2 for some n > 1.
Induction Step: Will show that t(n+1) = (n+1)^2.
    By the recursive definition, t(n+1) = t(n) + 2(n+1) - 1
					 = n^2 + 2n + 2 - 1   by I.H.
					= n^2 + 2n + 1
					= (n+1)^2.
Therefore the claim is true.
  8. Using the fact: "if c|a then there exists integer k such that c*k = a" Prove:
    1. If 2|n then 2|n-2.
      PROOF (direct): Assume 2 divides some integer n. Then by definition, there exists an integer k such that n = 2*k. Then n-2 = 2k - 2 = 2*(k-1). K-1 is also an integer therefore by the definition of "divides", 2 divides n-2. QED
    2. If c|a and c|b then c|(a-b).
      PROOF: Let a, b, and c be integers such that c|a and c|b. Then by the definition of "divides", there exist integers k and j such that a = c*k and b = c*j. Then a-b can be written as c*k - c*j = c*(k - j). Since (k-j) is an integer, we have a-b = c*an integer. Therefore a-b is divisible by c. QED
    3. If c|a and c|b then c|a mod b. Use this fact too: a = (a div b)*b + (a mod b). This is extra credit.
      PROOF: Let a, b, and c be three integers such that c|a and c|b. Then by def of "divides" there exist integers k and j such that c*k = a and c*j = b. We know that we can write: a = (a div b)*b + (a mod b). let q = a div b and r = a mod b. Then we can write: a = qb + r. Therefore r = a - qb = c*k .-q*c*j = c(k - q*j). Since k, j, and q are integers, this says r is divisible by c. Since r = a mod b, this proves the claim. QED.
  9. Prove or disprove. State whay type of proof used.
    1. If 9 is prime then 9 is not divisible by 3.
      SOLUTION: 9 is not prime therefore the claim is vacuously true.
    2. If any integer x is prime then x^2 is positive. SOLUTION: x^2 is positive for any integer x so therefore the claim is trivially true.
    3. For all integers a and b, if a divides b*p, where p is a prime, then a divides b. SOLUTION: This is false. Consider a = 6, b = 2, p = 3. a divides 2*3 but not b = 2.
  10. Determine tightest possible bound for each function. Prove that the function is O(bound), Omega(bound), and theta(bound).
    1. f(n) = 1 + 2 + ... + n
      SOLUTION: This is theta(n2). 
      Big-O: We know that this sum is n(n+1)/2 so f(n)  = (n^2)/2 + 1/2. 
       We know n^2/2 < n^2/2 and 1/2 < n^2/2.  thereofre f(n)  < 2*(n^2)/2  = n^2.
       Therefore f(n)  is O(n^2) for c = 1 and n_0 = 0.
Omega: We know that f(n) = 1/2(n^2 + 1) > 1/2(n^2) so f(n) is Omega(n^2)
Theta: Since f(n) is O(n^2) and Omega(n^2) it is theta(n^2).
    2. f(n) = 2*log_2{n/2} + 2 SOLUTION: f(n) is Theta(log_2 n). 
      Simplify: f(n) = 2*(log n) - 1) + 2 - 2 log n - 2 + 2 = 2 log n.
Big-O : Clearly f(n) = 2 log n is O(log n) for c = 2.  
Omega: Clearly f(n) = 2 log n >= 2 log n so is Omega(log n ) for c = 2.
Theta: Since f(n) is O(log n) and Omega(log n) it is also Theta(log n).
    3. f(n) = 3n^2 + 4n - 5
      SOLUTION: This is Theta(n^2). 
      Big-O: f(n) <= 3n^2 + 4n^2  for n >= 1.
       since 4n <= 4n^2 for n >= 1
       and   -5 <= 0
      Therefore f(n) is O(n^2) for c = 7 and n_0 = 1.
Omega: f(n) >= 3n^2?  Solve: 3n^2 + 4n - 5 >= 3n^2  
				    4n - 5 >= 0
				    4n >= 5
				     n >= 5/4
     So f(n) >= 3n^2 for n >= 5/4
     So f(n) is Omega(n^2) or c = 3, n_0 = 5/4
Theta: Since it is O and Omega(n^2), f(n) is theta(n^2).
    4. f(n) = n!/(n-2)! SOLUTION: This is n*(n-1) = n^2 - n which is theta(n^2). 
      Big-O: f(n) = n^2 - n <= n^2    whenever n >= 0.  Therefer f(n) is O(n^2) for c = 1, n_0 = 0.
Omega: f(n) = n^2 - n >= 1/2 n^2?  Notice we can't pick c >= 1.  It won't work.  It is
					ok to pick c a positive fraction.  The only restriction
					is c has to be positive.
     Solve:   1/2 n^2 >= n
		1/2 n >= 1
		n >= 2.
     So f(n) >= 1/2 n^2 for n >= 2
     So f(n) is Omega(n^2) for c = 1/2,  n_0 = 2.
Theta: since ...... same as above
    5. f(n) = 3n log n - 2n - 3log n.
      SOLUTION: f(n) is Theta(n log n). 
      Big-O: f(n) = 2 n log n - 2n - 3 log n <= 3n log n since 2n + 3 log n >= 0 for n >= 1.
       Therefore f(n) is O(n log n) for c = 3, n_0 = 1.
Omega: f(n) >= 2n log n?  Solve:
       3n log n - 2n - 3 log n >= 2n log n
       n log n >= 2n + 3 log n
       log n >= 2 + 3logn/n  (Equation *)
       Now, this is tricky. You can't solve it exactly.  You have to replace 3 logn/n by
         an upper bound.  We know that logn < n for n >= 1.  When n = 2 logn/n = 1/2.
         When n = 4, logn/n = 1/2.  When n = 8, logn/n = 3/8.  So for any intger 
	 n >= 1 we are pretty sure that logn/n <= 1/2.  Therefore 3logn/n <= 3/2 for
         n >= 1.
       So Equation * becomes:
         logn >= 2 + 3/2 >= 2 + 3logn/n  Sine if logn >= 2 +3/2 then  since 2 + 3/2 is
		greater than 2 + 3logn/n, log n > = 2 + 3logn/n as desired.
       So now we want to know for what n is log n >= 7/2?
       Well certainly if logn >= 4 then logn >= 7/2 since 4 > 7/2.
       So figure out when logn >= 4.  This is easy, when n >= 16.
       Therefore, when n >= 16 we have logn >= 2 + 3logn/n and, going back,
            f(n) >= 2nlogn.
       Therefore f(n) is Omega(n log n) for c = 2, n_0 = 16.
Note: This was very involed.  I would like you to be able to do this, but do not expect it.
Theta: same as always.