a guest Feb 17th, 2020 137 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Computer Science Department - Rutgers University Spring 2020
  2. CS 205: Homework Set 2 16:198:205
  3. Complete each of the following problems to the best of your ability. Remember, you can’t be graded on what you
  4. don’t write down so (unless you are just making stuff up) something is better than nothing. Discussing problems
  5. between each other is fine, but your final writeup and work must be your own.
  6. • Inference
  7. 1) The Resolution Inference Rule states that if (P ∨ Q) and (¬P ∨ R), we may conclude (Q ∨ R). Show
  8. that
  9. (P ∨ Q) ∧ (¬P ∨ R) → (Q ∨ R) (1)
  10. is a tautology, i.e., always true. Try to do it without a truth table - could you use any other rules of
  11. inference?
  12. 2) Modus Ponens is the rule that if P and P → Q, we may conclude Q. Show that this is really a simple
  13. version of the resolution inference rule. Hint: Consider a very specific R.
  14. 3) It can be shown that the resolution inference rule is ‘complete’ in the sense that it is all that is needed
  15. in order to conclude or infer everything that can be concluded or inferred. Why might other rules of
  16. inference still be interesting or useful?
  17. 4) (1.6.20 in the book) Determine whether these are valid arguments. Abstract the statements as much as
  18. possible to be able to analyze the logical structure / errors.
  19. ∗ If x is a positive real number, then x
  20. 2
  21. is a positive real number. Therefore, if a
  22. 2
  23. is positive, where a
  24. is a real number, then a is a positive real number.
  25. ∗ If x
  26. 2 6= 0 where x is a real number, then x 6= 0. Let a be a real number with a
  27. 2 6= 0; then a 6= 0.
  28. 5) (1.6.26) Justify the rule of universal transitivity, which states that if ∀x : P(x) → Q(x) and ∀x :
  29. Q(x) → R(x) are true, then ∀x : P(x) → R(x).
  30. 6) Someone shows you four cards, each with a letter on one side and a number on the other, and says the
  31. following: “Any card with a vowel on one side has an even number on the other side.” The four cards you
  32. are shown reveal the following: A, 7, B, 4. If you wanted to verify their claim, which cards would you
  33. flip over, and why?
  34. • Proofs
  35. 1) (1.7.16) Prove that if m and n are integers and nm is even, then m is even or n is even.
  36. ∗ What is the best approach here, direct proof, proof by contraposition, or proof by contradiction -
  37. why?
  38. ∗ Complete the proof.
  39. 2) Prove that for any integer n, n is divisible by 3 iff n
  40. 2
  41. is divisible by 3. Does your proof work for divisibility
  42. by 4 - why or why not? Identify the kind of proof steps you used, and why.
  43. 3) Prove that √
  44. 3 is irrational. What is the best proof approach to take, and why?
  45. 4) Prove that if you take 101 pigeons, and try to force them into 100 pigeonholes, there is some hole that
  46. has two pigeons. What is the best proof approach to take, and why?
  47. 5) Generalize the result of the previous problem: that if you take N pigeons and try to force them into
  48. M < N pigeonholes, some hole must have at least N/M many pigeons.
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand