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.