CSCI 2500 – Assignment 2
1. For each of the following arguments, identify the rule of inference being used.
(1 point each)
a. If I had a hammer I would hammer in the morning. I will not hammer in the
morning. Therefore, I do not have a hammer.
b. If you leave then I won’t cry. If I won’t cry then I won’t waste one single day.
Therefore, If you leave then I won’t waste one single day.
c. You can get with this. Therefore, you can get with this or you can get with
that.
d. Jeremiah was a bullfrog. If Jeremiah was a bullfrog then he was a good friend
of mine. Therefore, he was a good friend of mine.
e. There is a light and it never goes out. Therefore, there is a light.
f. You are either with us or you are against us. You are not with us. Therefore,
you are against us.
2. Given the domain {1,2,3,4}, determine if each of the following propositions are true
or false and give a brief explanation of why that is the case.
(2 points each)
a. ∀𝑥(𝑥 2 < 5)
b. ∃𝑥(𝑥 2 < 5)
c. ∀𝑥(𝑥 2 > 0)
d. ∃𝑥(𝑥 2 = 5)
3. Translate the following sentences to logical expressions where the domain each of
the following predicates is Hobbits. Let 𝐸(𝑥) be “𝑥 likes to eat,” 𝐺(𝑥) be “𝑥 goes on
an adventure,” 𝑅(𝑥) be “𝑥 returns home” and 𝑆(𝑥) be “𝑥 will be the same.”
(2 points each)
a. “All Hobbits like to eat.”
b. “Some Hobbits will go on an adventure.”
c. “Not all hobbits go on an adventure and return home.”
d. “If any hobbit goes on an adventure and returns home, they will not be the
same.”
4. For each of the following arguments, identify the rule of inference being used.
(1 point each)
a. Everything is beautiful. Therefore, Ray Stevens is beautiful.
b. Rockwell is watching me. Therefore, somebody’s watching me.
c. Given an arbitrary real number 𝑥, we have 𝑥 2 ≥ 0. Therefore, ∀𝑥(𝑥 2 ≥ 0).
d. There is a prime number between 30 and 40. Therefore, let p be such a
number.
5. For each statement either give a proof that the statement is true or a
counterexample showing that the statement is false.
(3 points each)
a. The sum of two even integers is even.
b. Every square number is a multiple of 3.
c. The product of two odd numbers is odd.
d. If an even number is divided by 2, the result is an odd number.
6. For each of the following proof outlines, identify the type of proof being used and
give a proof that follows the outline. You may choose from the following options:
• Proof by contradiction.
• Proof by contrapositive.
• Equivalence proof.
• Constructive existence proof.
(3 points each)
a. Theorem: there are positive integers 𝑥, 𝑦, and 𝑧 that satisfy 𝑥 2 + 𝑦 2 = 𝑧 2.
Proof outline: pick specific value for 𝑥, 𝑦, and 𝑧 that satisfy the equation.
b. Theorem: if integers 𝑥 and 𝑦 are odd, then 𝑥 + 𝑦 is even.
Proof outline: Assume 𝑥 + 𝑦 is odd, and show that 𝑥 and 𝑦 are not both odd.
c. A prime number is an integer greater than one that is only divisible by one
and itself. That is, if 𝑝 is prime and 𝑝 = 𝑚 ⋅ 𝑛, then one of 𝑚 and 𝑛 is one and
the other is 𝑝.
Theorem: Every prime number greater than two is odd.
Proof outline: assume there is an even prime number greater than 2 and
show that it leads to a contradiction.
d. Theorem: The integer 𝑛 is odd if and only if 𝑛 + 1 is even.
Proof outline:
• Show that if 𝑛 is odd, then 𝑛 + 1 is even.
• Show that if 𝑛 + 1 is even, then 𝑛 is odd.