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