Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSC165H1S Midterm 1, Version 1
No Aids Allowed
Name:
Student Number:
• This examination has 4 questions. There are a total of 7 pages, DOUBLE-SIDED.
• Final expressions in predicate logic must have negation symbols (¬) applied only to predicates or proposi-
tional variables, e.g., ¬p or ¬Prime(x).
• You may not define your own propositional operators, predicates, or sets unless asked for in the question.
• In your proofs, you may always use definitions we have covered in this course. However, you may not use
any external facts about these definitions unless they are given in the question.
• You may not use proofs by induction or contradiction on this midterm.
Take a deep breath.
This is your chance to show us
how much you’ve learned.
We WANT to give you the credit
that you’ve earned.
A number does not define you.
Good luck!
Question Grade Out of
Q1 7
Q2 8
Q3 5
Q4 5
Total 25
CSC165H1S , Winter 2020 Midterm 1, Version 1
1. [7 marks] Short answer questions. No justification is required for any parts of this question.
(a) [1 mark] Let S = {1, 3, 5, 7, 9}. Find a set S1 ⊆ N such that the following properties all hold:
|S1| = |S|+ 1 and ∀x ∈ S, ∃y ∈ S1, x− 1 = y
Solution
S1 = {0, 2, 4, 6, 8, 10} (10 could be replaced by any other natural number)
(b) [2 marks] Let T = {1, 3, 5, 7, 9}. Find sets T1 ⊆ T and T2 ⊆ T such that the following properties all hold:
T1 ⊆ T2 and |T1| > 1 and |T2 × T2| = |T1 × T | − 1
Solution
T1 is any two numbers from T2, and T2 is any three numbers from T , e.g., T1 = {1, 3} and T2 = {1, 3, 5}.
(c) [2 marks] Write down the truth table for the following expression in propositional logic. Intermediate
columns of the truth table are not required, but may be included.
(p⇒ ¬q)⇔ r
Solution
p q r (p⇒ ¬q)⇔ r
False False False False
False False True True
False True False False
False True True True
True False False False
True False True True
True True False True
True True True False
(d) [2 marks] Suppose we want to prove the following statement:
∀x ∈ N, (∃y ∈ N, P (x, y))⇒ (∃z ∈ N, Q(x, z))
Write the complete proof header for a proof, introducing all variables and assumptions. You may write
statements like “Let d = ” without filling in the blank. The last statement of your proof header should
be “We will prove that. . . ” where you clearly state what’s left to prove.
Please do not write below this line. There is extra space at the back of the test paper. Page 2/7
CSC165H1S , Winter 2020 Midterm 1, Version 1
Solution
Let x ∈ N.
Assume that there exists a y such that P (x, y) is true. Let z = .
We will prove that Q(x, z) is true.
Please do not write below this line. There is extra space at the back of the test paper. Page 3/7
CSC165H1S , Winter 2020 Midterm 1, Version 1
2. [8 marks] Translations. Let P be the set of all people, and suppose we define the following predicates:
• Doctor(x): “x is a doctor”, where x ∈ P
• Loves(x, y): “x loves y”, where x, y ∈ P
(Loves(x, y) does not mean the same thing as Loves(y, x))
Translate each of the following statements into predicate logic. No explanation is necessary. Do not define any of
your own predicates or sets. You may use the = and 6= symbols to compare whether two people are the same.
(a) [2 marks] Every doctor loves everyone.
Solution
∀p1 ∈ P, Doctor(p1)⇒
(∀p2 ∈ P, Loves(p1, p2))
(b) [2 marks] There is exactly one person loved by everyone.
Solution
∃p ∈ P, (∀p1 ∈ P, Loves(p1, p)) ∧ (∀q ∈ P, (∀p2 ∈ P, Loves(p2, q))⇒ p = q)
Or, ∃p ∈ P, ∀q ∈ P, (∀p2 ∈ P, Loves(p2, q))⇔ q = p
The following is tempting, but incorrect: ∃p ∈ P, ∀p1 ∈ P, Loves(p1, p)∧
(∀q ∈ P, Loves(p1, q)⇒ p = q).
By using the p1 in the last part, this says that q must equal p if any one person p1 loves q (rather than
all people), since the implication Loves(p1, q)⇒ p = q must be true for all p1 and q.
(c) [2 marks] If every person loves at least one doctor, then no one is a doctor.
Solution(∀p1 ∈ P, ∃p2 ∈ P, Loves(p1, p2) ∧Doctor(p2))⇒ (∀p3 ∈ P, ¬Doctor(p3))
(d) [2 marks] There exists a person who is not a doctor, who loves himself/herself, and only loves himself/herself.
Solution
∃p1 ∈ P, ¬Doctor(p1) ∧
(∀p2 ∈ P, Loves(p1, p2)⇔ p1 = p2)
Or, ∃p1 ∈ P, ¬Doctor(p1) ∧ Loves(p1, p1) ∧
(∀p2 ∈ P, p1 6= p2 ⇒ ¬Loves(p1, p2))
Please do not write below this line. There is extra space at the back of the test paper. Page 4/7
CSC165H1S , Winter 2020 Midterm 1, Version 1
3. [5 marks] A proof about numbers.
(a) [1 mark] Translate the following statement into predicate logic: “For every positive integer n, the sum of
the first (n2 − 1) positive integers is divisible by 2.”
Do not use the predicate |, but instead expand its definition in your statement. You may use summation
notation in your translation.
Solution
∀n ∈ Z+, ∃k ∈ Z,
n2−1∑
i=1
i = 2k
(b) [4 marks] Prove the statement from part (a) in the space below (you may also continue onto the next page).
Use a proof by cases based on whether n can be written as n = 2k or n = 2k + 1 for some integer k.
You may find the following formula helpful:
∀m ∈ N,
m∑
i=1
i =
m(m + 1)
2
Solution
Proof. Let n ∈ Z+. We’ll divide our proof into two cases.
Case 1: assume there exists a k1 ∈ Z such that n = 2k1.
Let k2 = k
2
1(n
2 − 1). We’ll prove that
n2−1∑
i=1
i = 2k2. We can calculate:
n2−1∑
i=1
i =
(n2 − 1)n2
2
(using the given formula)
=
(n2 − 1)(4k21)
2
(substituting n = 2k1)
= 2k21(n
2 − 1)
= 2k2 (by our choice of k2)
Case 2: assume there exists a k1 ∈ Z such that n = 2k1 + 1.
Please do not write below this line. There is extra space at the back of the test paper. Page 5/7
CSC165H1S , Winter 2020 Midterm 1, Version 1
Let k2 = (k
2
1 + k1)n
2. We’ll prove that
n2−1∑
i=1
i = 2k2. We can calculate:
n2−1∑
i=1
i =
(n2 − 1)n2
2
(using the given formula)
=
(4k21 + 4k1 + 1− 1)n2
2
(substituting n = 2k1)
= (2k21 + 2k1)n
2
= 2k2 (by our choice of k2)
Please do not write below this line. There is extra space at the back of the test paper. Page 6/7
4. [5 marks] Floors and disproofs.
Recall that the floor of a number x ∈ R, denoted bxc, is defined as the greatest integer that is less than or equal
to x. Consider the following statement:
There exists a k ∈ Z+ where every x ∈ Z+ satisfies x− (⌊√x⌋)2 ≤ k.
(a) [1 mark] Write the negation of this statement in predicate logic.
Solution
∀k ∈ Z+, ∃x ∈ Z+, x− (⌊√x⌋)2 > k
(b) [4 marks] Disprove the original statement by proving its negation in the space below.
Hint: for all positive integers a and b, if b2 ≤ a < (b + 1)2 then ⌊√a⌋ = b.
Solution
Proof. Let k ∈ Z+. Let x = k2 + 2k. We’ll prove that x− (⌊√x⌋)2 > k.
First, since k ≥ 1, we know that k2 + 2k > k2. Also, k2 + 2k < k2 + 2k + 1 = (k + 1)2, and so we can
conclude k2 ≤ x < (k + 1)2. The hint then tells us that ⌊√x⌋ = k.
So then we can calculate:
x− (⌊√x⌋)2 = x− k2 (since ⌊√x⌋ = k)
= k2 + 2k − k2 (since x = k2 + 2k)
= 2k
> k (since k ≥ 1)
Total Pages = 7. Total Marks = 25. Page 7/7