CS Toolkit Problem Set Problem Set # 3

Bireswar Das (Aug 2025)

Most likely, you will find solutions to all these problems on the internet. However, the
best way not to learn the subject is to simply look at the solutions. You are strongly
encouraged to spend time on each problem before referring to the solution. It is expected
that you may sometimes spend multiple days on a single problem set.
While this set may appear lengthy, most of the questions are easy and short answer type.
The problems marked * may take more time to solve.

1 Logic
Problem 1.1. Let p and q be the propositions:
p : The election is decided.
q : The votes have been counted.
Express each of the following compound propositions as an English sentence:

(a) ¬p (d) q → p (g) p ↔ q

(b) p ∨ q (e) ¬q → ¬p
(c) ¬p ∧ q (f ) ¬p → ¬q (h) ¬q ∨ (¬p ∧ q)

Problem 1.2. For each of these sentences, state what the sentence means if the logical
connective or is interpreted as an inclusive or (that is, a disjunction) versus an exclusive or
(i.e., xor). Which of these meanings of or do you think is intended?

(a) To take discrete mathematics, you must have taken calculus or a course in computer
science.

(b) When you buy a new car from Acme Motor Company, you get $2000 back in cash or
a 2% car loan.

(c) Dinner for two includes two items from column A or three items from column B.

(d) School is closed if more than 2 feet of snow falls or if the wind chill is below −100.

Problem 1.3. Construct a truth table for each of these compound propositions.

(a) p ∧ ¬p (d) (p ∨ q) → (p ∧ q)

(b) p ∨ ¬p (e) (p → q) ↔ (¬q → ¬p)

(c) (p ∨ ¬q) → q (f ) (p → q) → (q → p)

Problem 1.4 (*). Each inhabitant of a remote village always tells the truth or always lies.
A villager will give only a “Yes” or a “No” response to a question a tourist asks. Suppose

1
you are a tourist visiting this area and come to a fork in the road. One branch leads to the
ruins you want to visit; the other branch leads deep into the jungle. A villager is standing at
the fork in the road.
What one question can you ask the villager to determine which branch to take?

Problem 1.5 (*). When three professors are seated in a restaurant, the hostess asks them:
“Does everyone want coffee?” The first professor says: “I do not know.” The second profes-
sor then says: “I do not know.” Finally, the third professor says: “No, not everyone wants
coffee.” The hostess comes back and gives coffee to the professors who want it.
How did she figure out who wanted coffee?

Problem 1.6. Four friends have been identified as suspects for an unauthorized access into
a computer system. They have made statements to the investigating authorities. Alice said,
“Carlos did it.” John said, “I did not do it.” Carlos said, “Diana did it.” Diana said,
“Carlos lied when he said that I did it.”

(a) If the authorities also know that exactly one of the four suspects is telling the truth,
who did it? Explain your reasoning.

(b) If the authorities also know that exactly one is lying, who did it? Explain your reason-
ing.

Problem 1.7. Show that (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) is a tautology.

Problem 1.8. Let C(x) be the statement “x has a cat”, let D(x) be the statement “x has
a dog”, and let F (x) be the statement “x has a ferret”. Express each of these statements in
terms of C(x), D(x), F (x), quantifiers, and logical connectives. Let the domain consist of
all students in your class.

(a) A student in your class has a cat, a dog, and a ferret.

(b) All students in your class have a cat, a dog, or a ferret.

(c) Some student in your class has a cat and a ferret, but not a dog.

(d) No student in your class has a cat, a dog, and a ferret.

(e) For each of the three animals, cats, dogs, and ferrets, there is a student in your class
who has this animal as a pet.

Problem 1.9. Suppose that the domain of the propositional function P (x) consists of the
integers 1, 2, 3, 4, 5. Express these statements without using quantifiers, instead using only
negations, disjunctions, and conjunctions.

(a) ∃xP (x) (c) ¬∃xP (x)

(b) ∀xP (x) (d) ¬∀xP (x)

2


(e) ∀x (x ̸= 3) → P (x) ∨ ∃x¬P (x)

Problem 1.10. Suppose that the domain of the propositional function P (x) consists of
−5, −3, −1, 1, 3, and 5. Express these statements without using quantifiers, instead using
only negations, disjunctions, and conjunctions.


(a) ∃xP (x) (d) ∃x (x ≥ 0) ∧ P (x)
(b) ∀xP (x)



(c) ∀x (x ̸= 1) → P (x) (e) ∃x(¬P (x)) ∧ ∀x (x < 0) → P (x)

Problem 1.11. Establish these logical equivalences, where x does not occur as a free variable
in A. Assume that the domain is nonempty.

(a) (∀x P (x)) ∨ A ≡ ∀x (P (x) ∨ A)

(b) (∃x P (x)) ∨ A ≡ ∃x (P (x) ∨ A)

Problem 1.12. The notation ∃!x P (x) denotes “There exists a unique x such that P (x) is
true”. If the domain consists of all integers, what are the truth values of these statements?

(a) ∃!x (x > 1) (c) ∃!x (x + 3 = 2x)

(b) ∃!x (x2 = 1) (d) ∃!x (x = x + 1)

Problem 1.13. Translate these statements into English, where the domain for each variable
consists of all real numbers.

(a) ∃x ∀y (xy = y)

(b) ∀x ∀y (((x ≥ 0) ∧ (y < 0)) → (x − y > 0))

(c) ∀x ∀y ∃z (x = y + z)

Problem 1.14. Express each of these statements using predicates, quantifiers, logical con-
nectives, and mathematical operators where the domain consists of all integers.

(a) The product of two negative integers is (c) The difference of two negative integers
positive. is not necessarily negative.

(d) The absolute value of the sum of two

(b) The average of two positive integers is integers does not exceed the sum of the
positive. absolute values of these integers.

Problem 1.15. Express the negations of each of these statements so that all negation symbols
immediately precede predicates.

(a) ∃z∀y∀x T (x, y, z)

3
 (b) ∃x∃y P (x, y) ∧ ∀x∀y Q(x, y)

(c) ∃x∃y (Q(x, y) ↔ Q(y, x))

(d) ∀y∃x∃z (T (x, y, z) ∨ Q(x, y))

Problem 1.16. Find a counterexample, if possible, to each of these universally quantified

statements, where the domain for all variables consists of all integers.



(a) ∀x ∃y x = 1/y (c) ∀x ∀y x2 ̸= y 3


(b) ∀x ∃y y 2 − x < 100

Problem 1.17. Determine the truth value of the statement

∃x∀y (x ≤ y 2 )

if the domain for the variables consists of:

(a) the positive real numbers.

(b) the integers.

(c) the nonzero real numbers.

Problem 1.18. Find a counterexample, if possible, to each of these universally quantified

statements, where the domain for all variables consists of all integers.

(a) ∀x∀y (x2 = y 2 → x = y) (c) ∀x∀y (xy ≥ x)

(b) ∀x∃y (y 2 = x)

Problem 1.19. What is the most counterintuitive rule of inference given in the book by
Rosen?

Problem 1.20 (Important). Determine whether each of these arguments is valid. If an

argument is correct, identify the rule of inference being used (Check Rosen). If it is not,
state the logical error.

(a) If n is a real number such that n > 1, then n2 > 1. Suppose that n2 > 1. Then n > 1.

(b) If n is a real number with n > 3, then n2 > 9. Suppose that n2 ≤ 9. Then n ≤ 3.

(c) If n is a real number with n > 2, then n2 > 4. Suppose that n ≤ 2. Then n2 ≤ 4.

Problem 1.21. Determine whether these are valid arguments.

(a) If x is a positive real number, then x2 is a positive real number. Therefore, if a2 is

positive, where a is a real number, then a is a positive real number.

4
 (b) If x2 ̸= 0, where x is a real number, then x ̸= 0. Let a be a real number with a2 ̸= 0;
then a ̸= 0.
Problem 1.22. Prove that if x is rational and x ̸= 0, then 1/x is rational. What kind of
proof did you use?
Problem 1.23. Show that if n is an integer and n3 + 5 is odd, then n is even using
(a) a proof by contraposition.
(b) a proof by contradiction.
Problem 1.24 (*). Use a proof by contradiction to show that there is no rational number r
for which
r3 + r + 1 = 0.
a
Hint: Assume r = is a root, where a and b are integers with gcd(a, b) = 1. Multiply
b
the equation by b3 to obtain an equation in integers, and then consider the parity (odd/even)
of a and b.
Problem 1.25. Find a counterexample to the statement that every positive integer can be
written as the sum of the squares of three integers.
Problem 1.26. Prove that at least one of the real numbers a1 , a2 , . . . , an is greater than or
equal to the average of these numbers. What kind of proof did you use?
Problem 1.27. Prove that there are no positive perfect cubes less than 1000 that are the
sum of the cubes of two positive integers.
Problem 1.28 (*). Prove the triangle inequality: if x and y are real numbers, then
|x| + |y| ≥ |x + y|,
where |x| denotes the absolute value of x (that is, |x| = x if x ≥ 0 and |x| = −x if x < 0).
Problem 1.29. Prove that there are 100 consecutive positive integers that are not perfect
squares. Is your proof constructive or nonconstructive?
Problem 1.30 (*). Write the numbers 1, 2, . . . , 2n on a blackboard, where n is an odd
integer. Repeatedly pick any two of the numbers, j and k, write |j − k| on the board, and
erase j and k. Continue this process until only one integer remains on the board. Prove that
this final integer must be odd.
Problem 1.31 (*). Prove that there are no integer solutions (x, y) to the equation
2x2 + 5y 2 = 14.
Problem 1.32 (*). Prove that when a white square and a black square are removed from an
8 × 8 checkerboard you can tile the remaining squares of the checkerboard using dominoes.
Hint: Show that when one black and one white square are removed, each part of the
partition of the remaining cells formed by inserting the barriers shown in the figure can be
covered by dominoes.

5
6