COT3100 Practice Problems for Exam 1

These problems are only meant to help you prepare the first exam. It is not guaranteed
that the exam questions will be similar to these problems.
There will be five problems on the exam:

1. Propositional logic and equivalences (1.1 and 1.2)

2. Predicates and Quantifiers (1.3)

3. Rules of Inference and Proofs (1.5)

4. Set Operations (2.1 and 2.2)

5. Functions and sequences (2.3 and 2.4)

The (brief) solutions will be available only after 9pm on Thursday night. However,
instead of memorizing the solutions, you should attempt to solve all problems by
yourself first.

1. What is the truth value of (p q) → (p q), when both p and q are false?
Solution: You should work out this problem and convince yourself that
your answer is correct.

2. State the converse and contrapositive of, "If I answer this question, then I
will get 4 points".
Solution: You just need to know the definitions of converse and contrapositive.
Check out the textbook or lecture slides.

3. Which rule of inference allows you to conclude, "Mark has stripes" from
the statements, "Every zebra has stripes" and "Mark is a zebra"?
Solution: Same as above.

4. Construct the truth table for the proposition .
Solution: Clock yourself to make sure that you don't take more than three
minutes on this problem.

5. Prove that there is a positive integer that equals the sum of positive integers
not exceeding it.
Solution: 3 is one such number.

6. Prove that the product of a rational number and an irrational number is irrational.
Solution: We know that the product and quotient of two rational numbers
are also ration. Therefore, we can prove this by contradiction. Let p, q be
the two numbers with p rational and q irrational. Assume that r = pq is rational.
Then, this implies that q = r/p is also rational, which is the desired
contradiction.

7. Prove that the proposition is a tautology.
Solution: Compute the truth table and show that it is always true.

8. We briefly discussed the uniqueness quantifier, . The notation
meant "There is a unique x, such that P(x) is true." Express this uniqueness
quantification in terms of universal quantifiers, existential quantifiers
and logical operators. (Hint: You might need to use nested quantifiers).
Solution: Here is a partial solution:



You have to figure out what to put for A and B.

9. Prove that at least one of the real numbers is greater than or
equal to their average.
Solution: Proof by contradiction. If all are smaller than their average,
then you can show that this average is smaller than itself, which is the contradiction.

10. For the following argument, explain which rules of inference are used in
each step to lead from the premises to the conclusion:
"There is someone in this class who has been to France. Everyone who
visits France visits the Louvre. Therefore, someone in this class has visited
the Louvre".
Solution: Again, the answer can be found in the textbook (Section 1.5).

11. Give one example of a trivial proof and one example of a vacuous proof.
Solution: A vacuous proof is a proof that shows the hypothesis is false.
Here is an example: Suppose x is a real number . Show that if x² < 0, then
x² + x⁶ = 2. The (vacuous) proof is to show that x² < 0 is false if x is real
number. Then, because the hypothesis is false, the implication is always
true.

12. Use the rules of inference to prove that if



are true, then is also true.
Solution: Work out this problem yourself. Make sure that you know how to
solve this problem. There are similar examples in the textbook and lecture
slides.

13. Prove that there cannot exist any real number x such that x² + 1/x² = π/2.
Solution: We did this in class.

14. If x is an integer, prove that x = floor(x/2) + ceil(x/2).
Solution: There are two cases: (1) x = 2k+1 is odd. Then floor(x/2) = k
and ceil(x/2) = k + 1. Therefore, x = floor(x/2) + ceil(x/2). Similarly,
if x is even, we can show that x = floor(x/2) + ceil(x/2).

15. Prove that

Solution: We went over this problem in class. You need to use the formula


16. Give an example each of a function from the set of natural numbers to the
set of natural numbers which is (a) one-to-one but not onto, (b) onto but
not one-to-one, and (c) neither one-to-one nor onto. Prove your example in
each case.
Solution: .

17. Let be a countable collection of countable sets. Show that
their union and intersection are also countable..
Solution: The intersection will be a subset of say . Because is countable,
the intersection (which is a subset) is also countable. To show that
their union is also countable, you can do the following. First, show that
the set is countable, i.e., the set of cartesian product of positive
integers is countable. The required bijection is constructed exactly as in the
proof that shows the set of rational numbers is countable. Once you have
shown that is countable, you can define an onto function from
to showing that the latter set is indeed
countable.

18. Determine whether each of these sets is countable. For those that are countable,
exhibit an one-to-one correspondence between the set of natural numbers
and that set.

(a) integers not divisible by 3.

(b) integers divisible by 5 but not by 7.

(c) the real numbers with decimal representations consisting of all 1s.

(d) the real numbers with representation of all 1s or 9s.

(e) the real numbers not containing 0 in their decimal representation.

(f) the real numbers containing only a finite number of 1s in their decimal
representation.

Solution: (a) and (b) are both countable because they are subsets of the integers.
(c) is also countable. (d) will depend on how you read the problem. If
the number can contain 1s or 9s but not both, then, it will be countable (it is
just a union of two countable sets). However, if the number can contain both
1 and 9 in its decimal representation, then, the set is uncountable. Cantor's
diagonal argument can be used here to show that this set is uncountable. (e)
and (f) are both uncountable.

19. Let f be a function from the set A to the set b. Let S and T be subsets of A.
Show that



Solution: Here we show how to solve (a). Let x ∈ f(S ∪ T). This means
that there exists an y ∈ S ∪ T such that f(y) = x. If y ∈ S, then x ∈ f(S).
Else, y ∈ T, then x ∈ f(T). This shows that x ∈ f(S) ∪ f(T). Conversely,
if x ∈ f(S) ∪ f(T). If x ∈ f(T), there exists y ∈ T such that f(y) = x.
This shows that x ∈ f(S ∪ T).

20. Compute the sum .
Solution:
This telescoping sum is simply .