CSC165H1, Winter 2022 CSC165H1: Worksheet 5—Proofs II (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Prove and disprove statements about numbers and functions.
Copyright By PowCoder代写 加微信 powcoder
• Use mathematical definitions of predicates to simplify or expand formulas. • Identify errors in an incorrect proof.
1. A direct proof. Let n ∈ Z. Recall that we say n is odd when ∃k ∈ Z, n = 2k − 1. Prove the following statement: For every pair of odd integers, their product is odd.
Be sure to first translate the statement into predicate logic. You can use the predicate Odd(n) in your formula without expanding the definition, but you’ll need to use the definition in your proof.
Translation:
Discussion. Like the proof we saw in lecture, we’ll need to use the definition of odd to introduce new variables
∀m,n∈Z, Odd(m)∧Odd(n)⇒Odd(mn).
to write m = 2k1 − 1 and n = 2k2 − 1; the rest should be straightforward algebra.
Proof. Let m,n ∈ Z, and assume they are both odd. That is, we assume there exist k1,k2 ∈ Z such that m=2k1−1andn=2k2−1.Weneedtoprovethatmnisodd,i.e.,thereexistsk3 suchthatmn=2k3−1. Let k3 = 2k1k2 − k1 − k2 + 1.∗
Then we can calculate:
2k3 −1=2(2k1k2 −k1 −k2 +1)−1 = 4k1k2 −2k1 −2k2 +1
= (2k1 − 1)(2k2 − 1) = mn
∗We actually did the calculation in reverse to find the value of k3; this was our rough work!
2. An incorrect proof. Consider the following claim: Foreveryevenintegermandoddintegern,m2−n2 =m+n.
(a) Using the predicates Even(n) and Odd(n) (which return whether an integer n is even or odd, respectively), express the above statement in predicate logic.
(b) The following was submitted as a proof of the statement:
Proof. Let m and n be arbitrary integers, and assume m is even and n is odd. By the definition of even,
∃k ∈ Z, m = 2k; by the definition of odd, ∃k ∈ Z, n = 2k − 1. We can then perform the following algebraic Page 1/4
∀m,n∈Z, Even(m)∧Odd(n)⇒m2 −n2 =m+n.
CSC165H1, Winter 2022 CSC165H1: Worksheet 5—Proofs II (Partial Solutions)
manipulations:
m2 −n2 =(2k)2 −(2k−1)2 =4k2 −4k2 +4k−1
= 2k + (2k − 1) =m+n
The given argument is not a correct proof. What is the flaw?1
3. Comparing functions. Consider the following definition:2
Definition 1. Let f, g : N → R≥0. We say that g is dominated by f (or f dominates g) when for every natural
number n, g(n) ≤ f(n).
(a) Express this definition symbolically by defining the following predicate:
Dom(f,g) : , where f,g : N → R≥0.
(b) Let f(n) = 3n and g(n) = n. Prove that g is dominated by f.
The author has assumed that m = 2k and that n = 2k − 1, using the same variable k to express both m and n. In this way, the author has unwittingly assumed that m and n are consecutive integers. But the statement is about an arbitrary m and an arbitrary n, and so it is wrong to assume that they are consecutive numbers. The author should have let m = 2k1 and n = 2k2 − 1, for some integers k1 and k2. And of course, k1 is not necessarily equal to k2!
Dom(f,g) : ∀n ∈ N, g(n) ≤ f(n).
We want to prove the following statement:
Proof. Let n ∈ N.
∀n∈N, n≤3n
We start with the inequality 1 ≤ 3. Since n ≥ 0, we can multiply both sides by n to obtain the desired inequality, n ≤ 3n.
(c) Let f(n) = n2 and g(n) = n + 165. Prove that g is not dominated by f. Make sure to write the statement you’ll prove in predicate logic, in fully simplified form (negations moved all the way inside).
(d) Now let’s generalize the previous statement. Translate the following statement into predicate logic (expanding the definition of Dom) and then prove it!
For every positive real number x, g(n) = n + x is not dominated by f(n) = n2.
1For extra practice, determine whether the given statement is actually True or False, and write a correct proof or disproof. 2RecallthatR≥0 ={x|x∈R∧x≥0}.
The statement we want to prove is the negation of Dom(f,g): ∃n∈N, n+165>n2.
We leave the proof as an exercise.
CSC165H1, Winter 2022 CSC165H1: Worksheet 5—Proofs II (Partial Solutions)
Translation:
We leave the proof as an exercise.
∀x∈R, x>0⇒∃n∈N, n+x>n2
CSC165H1, Winter 2022 CSC165H1: Worksheet 5—Proofs II (Partial Solutions)
4. More with floor. Recall that the floor of a number x, denoted ⌊x⌋, is the largest integer less than or equal to x. Hereisafactyoumayuseaboutfloor: foreveryx∈R,0≤x−⌊x⌋<1.
Prove the following statement:3
∀ x ∈ R ≥ 0 , x ≥ 4 ⇒ ( ⌊ x ⌋ ) 2 ≥ 21 x 2
Hints: First introduce a variable ε = x − ⌊x⌋ and rewrite ⌊x⌋ as x − ε. What can you conclude about ε given the
above fact? Then, prove the following simpler statement, and use it in your proof: ∀x ∈ R≥0, x ≥ 4 ⇒ 21x2 ≥ 2x.
Proof. Let x ∈ R≥0, and assume that x ≥ 4. As noted in the question, we let ε = x−⌊x⌋, and so we know that 0 ≤ ε < 1. Then we can calculate:
(⌊x⌋)2 = (x − ε)2
=x2 −2xε+ε2 (1)
We now want to show that 2xε < 21x2, which we can do using our assumption x ≥ 4: 4≤x
2 x ≤ 12 x 2
2xε ≤ 12x2
So then we can use this inequality in equation (1) to get:
(⌊x⌋)2 =x2 −2xε+ε2
≥ x2 − 21x2 + ε2 = 12 x 2 + ε 2
(multiplying both sides by x)
(since ε < 1)
(since 2xε ≤ 21x2) (since ε2 ≥ 0)
3For extra practice, try proving the following generalization of this statement: ∀k ∈ R≥0, k < 1 ⇒ ∃x0 ∈ R≥0, ∀x ∈ R≥0, x ≥ x0 ⇒ (⌊x⌋)2 ≥ kx2.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com