SHARE

TWEET

# Untitled

a guest
Feb 17th, 2020
137
Never

**Not a member of Pastebin yet?**

**, it unlocks many cool features!**

__Sign Up__- Computer Science Department - Rutgers University Spring 2020
- CS 205: Homework Set 2 16:198:205
- Complete each of the following problems to the best of your ability. Remember, you can’t be graded on what you
- don’t write down so (unless you are just making stuff up) something is better than nothing. Discussing problems
- between each other is fine, but your final writeup and work must be your own.
- • Inference
- 1) The Resolution Inference Rule states that if (P ∨ Q) and (¬P ∨ R), we may conclude (Q ∨ R). Show
- that
- (P ∨ Q) ∧ (¬P ∨ R) → (Q ∨ R) (1)
- is a tautology, i.e., always true. Try to do it without a truth table - could you use any other rules of
- inference?
- 2) Modus Ponens is the rule that if P and P → Q, we may conclude Q. Show that this is really a simple
- version of the resolution inference rule. Hint: Consider a very specific R.
- 3) It can be shown that the resolution inference rule is ‘complete’ in the sense that it is all that is needed
- in order to conclude or infer everything that can be concluded or inferred. Why might other rules of
- inference still be interesting or useful?
- 4) (1.6.20 in the book) Determine whether these are valid arguments. Abstract the statements as much as
- possible to be able to analyze the logical structure / errors.
- ∗ If x is a positive real number, then x
- 2
- is a positive real number. Therefore, if a
- 2
- is positive, where a
- is a real number, then a is a positive real number.
- ∗ If x
- 2 6= 0 where x is a real number, then x 6= 0. Let a be a real number with a
- 2 6= 0; then a 6= 0.
- 5) (1.6.26) Justify the rule of universal transitivity, which states that if ∀x : P(x) → Q(x) and ∀x :
- Q(x) → R(x) are true, then ∀x : P(x) → R(x).
- 6) Someone shows you four cards, each with a letter on one side and a number on the other, and says the
- following: “Any card with a vowel on one side has an even number on the other side.” The four cards you
- are shown reveal the following: A, 7, B, 4. If you wanted to verify their claim, which cards would you
- flip over, and why?
- • Proofs
- 1) (1.7.16) Prove that if m and n are integers and nm is even, then m is even or n is even.
- ∗ What is the best approach here, direct proof, proof by contraposition, or proof by contradiction -
- why?
- ∗ Complete the proof.
- 2) Prove that for any integer n, n is divisible by 3 iff n
- 2
- is divisible by 3. Does your proof work for divisibility
- by 4 - why or why not? Identify the kind of proof steps you used, and why.
- 3) Prove that √
- 3 is irrational. What is the best proof approach to take, and why?
- 4) Prove that if you take 101 pigeons, and try to force them into 100 pigeonholes, there is some hole that
- has two pigeons. What is the best proof approach to take, and why?
- 5) Generalize the result of the previous problem: that if you take N pigeons and try to force them into
- 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.