Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 2080 Winter 2022 Homework Assignment 1

SOLUTIONS



Useful definitions and results for this assignment:

| An integer x divides an integer y means: there exists an integer k such that y = x | k. We use the notation x | y to denote "x divides y"

| A number p is prime means: p is a positive integer, and, there are exactly two different positive integers that divide p (and they are 1 and p).

| The predicate isPrime(z) evaluates to true when z is prime, and evaluates to false when z is not prime.

| Every positive integer has a unique prime factorization.   One particularly useful fact you can conclude from this: if you write a positive integer x as some specific product of prime numbers, then no other prime numbers divide x .


Assignment questions start here:


(2 pts)    1.  Translate the following English sentence into a logical statement:

"Every even integer greater than 2 is the sum of two prime numbers".

Your solution may only use the following: ( ) v # | Z > 2 | + = , x y z k isPrime


Solution:

x | Z, [((x > 2)(k | Z, x = 2 |k)) # (y | Z, z | Z, isPrime(y)isPrime(z)(x = y +z))]


2.  Consider the following logical statement S : 扌w | R, (w2 这 2w 这1) # (w 1) Define P(w) to be the predicate (w2 这 2w 这1) # (w 1).

(1 pt)          (a) Write the converse of the predicate P(w).


Solution

(w 1) # (w2 2w 1)

(2 pts)          (b) Write the contrapositive of the predicate P(w).

Simplify (showing each step of your work) so that your final answer does not contain a negation symbol (+)


Solution

(w 1) #+(w2 2w 这1)

(w = 1) # (w2 2w = 1)

(2 pts)          (c) Write the inverse of the predicate P(w).

Simplify (showing each step of your work) so that your final answer does not contain a negation symbol (+)


Solution

(w2 2w 这1) #+(w 1)

(w2 2w = 1) # (w = 1)

(3 pts)          (d) Write the negation of S .

Simplify (showing each step of your work) so that your final answer does not contain a negation symbol (+)


Solution

+(扌w | R, (w2 2w 这1) # (w 1))

w | R,+((w2 这 2w 这1) # (w 1))

w | R, (w2 2w 这1) 入+(w 1)

w | R, (w2 2w 这1) (w = 1)

(4 pts)          (e) Write an indirect proof that S is true.


Solution

(1)  Let w be an arbitrary real number.

(2) We prove (w2 这 2w 这1) # (w 1) using an indirect proof, i.e., we prove its contrapositive is true:

(3)  Suppose w = 1.

(4)  Then w2 2w = (1)2 2(1) = 1 2 = 这1. This proves that w2 2w = 这1.


(5)  The two previous steps prove (w = 1) # (w2 2w = 1), as required.


(4 pts)           (f) Write a proof by contradiction that S is true.


Solution

(1)  To obtain a contradiction, assume+S is true, i.e., we assume 甘w | R, (w2 2w 这1) (w = 1)

(2)  Let w be a real number that satisfies (w2 2w 这1) (w = 1), i.e., both w2 2w 这1 and w = 1 are true.

(3)  Since w = 1, the expression w2 2w evaluates to (1)2 这 2(1) = 这1. So we have shown that w2 这 2w = 这1.

(4) We get a contradiction: from the previous two lines, we see that w2 这 2w 这1 and w2 这 2w = 这1 are both true, which is impossible.

(5)  Since we reached a contradiction, our assumption "+S is true" must have been incorrect. In particular, this means+S is false, so S is true.


(4 pts)    3.  Prove or disprove the following logical statement: t | R, x | R, x | (t 1) < 1


Solution

We prove that the statement is true:

(1)  Let t = 1

(2)  Let x be an arbitrary real number.

(3)  From the fact that t = 1, subtracting 1 from both sides gives t 这 1 = 0.

(4)  Since t 这 1 = 0, the expression x(t 这 1) evaluates to 0, which is less than 1. Therefore, x(t 这 1) < 1, as required.


(4 pts)   4.  Prove or disprove the following logical statement:

z | Z, isPrime(z) # ((2 | z3 z2 + z) v (3 | z3 z2 + z))


Solution 1: Prof. Miller overcomplicates things

We disprove the statement by proving that its negation is true:

z | Z, isPrime(z) (2 | z3 z2 + z) (3 | z3 z2 + z)

(1)  Let z = 7

(2) z is prime since the only positive integers that divide 7 are 1 and 7. Therefore, isPrime(z) evaluates to true.

(3)  The value of z3 z2 + z is 73 72 + 7 = 7(72 7 + 1) = 7 | 43

(4)  Since 7 and 43 are both prime, we have written z3 这 z2 + z as a product of primes 7 and 43, which means that no other primes divide z3 z2 + z .

(5)  Since 2 and 3 are both prime, the previous line tells us that 2 does not divide z3 这 z2 + z, and

3 does not divide z3 z2 + z .

(6)  Therefore, by lines (2) and (5), we have shown that                   isPrime(z) 入+(2 | z3 z2 + z) 入+(3 | z3 z2 + z), as required.


Solution 2: Easier Proof

We disprove the statement by proving that its negation is true:

z | Z, isPrime(z) (2 | z3 z2 + z) (3 | z3 z2 + z)

(1)  Let z = 7

(2) z is prime since the only positive integers that divide 7 are 1 and 7. Therefore, isPrime(z) evaluates to true.

(3)  The value of z3 z2 + z is 73 72 + 7 = 7(72 7 + 1) = 7 | 43 = 301

(4)  Since 301/2 = 150.5 is not an integer, this means 2 does not divide 301.       Since 301/3 = 100.333... is not an integer, this means 3 does not divide 301.

(5)  Therefore, by lines (2) and (4), we have shown that                   isPrime(z) 入+(2 | z3 z2 + z) 入+(3 | z3 z2 + z), as required.


5.  Our goal in this question is to prove the following identity: for all even integers q | 4,

匕(q)匕(y) ↓ ( = (q 2)(2q2(2)4+ 7q + 12)

To make your life easier, we’ve broken up the task into separate steps.



(8 pts)







(a)  Prove the following using strong induction:

For all integers y | 0:

↓   ( = , 41




if y is even

if y is odd



Solution 1 (one induction proof for both even and odd cases)

Define P(y) to be predicate '  ' = , 4

We prove, by induction on y, that P (y) is true for all y | 0.

0

Base Case: Suppose y = 0. The expression! ''evaluates to '' = |0I = 0. The expression

=0

evaluates to = 0. Since y is even and we showed that ! '' = , the base case holds.

=0

Induction Hypothesis: For a y | 1, assume that P(0) | | | 入 P(y 1) is true. Inductive Step: We prove that P(y) is true. We separately consider the following two subcases:

(i) y is even

(ii) y is odd

These two subcases cover all possibilities, since each integer y is either even or odd.


Proof of Case (i):

(1)  Suppose that y is even. By the definition of even, there exists an integer j such that y = 2j .

(2)  Split the summation range:

↓   ( = 1 ↓   ( + 1 ↓   (

= 1 ↓   ( + ↓(

= 1 ↓   ( + | |     (since y = 2j)

= 1 ↓   ( + |jI     (arithmetic)


= 1 ↓   ( + j (since j is an integer) = 1 ↓   ( + (since y = 2j)

(3)  Note that y 这 1 is odd, since y is even. By the induction hypothesis, we assumed that

1

=0


↓   ( = 1 ↓   ( +

= (y 2 1 + (from Induction Hypothesis) = y2 2y4+ 1 1 + (arithmetic)

= y2 2y + 1 1 + 2y (arithmetic)

4

= (arithmetic)

Since y is even and we showed that ! '' = , this concludes the inductive step in

=0

Case (i).


Proof of Case (ii):

(1)  Suppose that y is odd. By the definition of odd, there exists an integer j such that y = 2j + 1.

(2)  Split the summation range:

↓   ( = 1 ↓   ( + 1 ↓   (

= 1 ↓   ( + ↓(

= 1 ↓   ( + | |     (since y = 2j + 1)

= 1 ↓   ( + | (slide 8 of Math Review 5: | | = | ) = 1 ↓   ( + 1j]     (arithmetic)

= 1 ↓   ( + j (since j is an integer)


= 1 ↓   ( + y 2(这) 1



(since y = 2j + 1)


(3)  Note that y 这 1 is even, since y is odd. By the induction hypothesis, we know that

1

=0


↓   ( = 1 ↓   ( + y 2(这) 1

= (y 4(这) 1)2 + y 2(这) 1 (from Induction Hypothesis) = y2 4(2)y + 1 + y 2(这) 1 (arithmetic)

= y2 2y + 1 + 2y 2 (arithmetic)

4

= y24 1 (arithmetic)

Since y is odd and we showed that ! '' = y 241 , this concludes the inductive step in

=0

Case (ii).


Solution 2 (two induction proofs: one for even, one for odd)

We separately consider the following two subcases:

(i) y is even

(ii) y is odd

These two cases cover all possibilities, since each integer y is either even or odd.

Proof of Case (i): Define P(y) to be predicate ! ' ' = .

=0

We prove, by induction on y, that P (y) is true for all even integers y | 0.

0

Base Case: Suppose y = 0. The expression! ''evaluates to '' = |0I = 0. The expression

=0

evaluates to = 0. Therefore, the base case holds.

Induction Hypothesis: For an even y | 2, assume that P(0) | | | 入 P(y 2) is true. Inductive Step: We prove that P(y) is true.

(1)  By the definition of even, there exists an integer j such that y = 2j .

(2)  Split the summation range:

↓   ( = 1 ↓   ( +'(.)u1 ↓   (   +!(┐) 1 ↓   (

= 1 ↓   ( + | y 2(这) 1 | + ↓(

= 1 ↓   ( + | 2j 2 1 | + | |     (since y = 2j)

= 1 ↓   ( + | (2j 2(2)) + 1 | + | |     (since 2j 1 = 2j 2 + 1)

= 1 ↓   ( + | 2j 2 2 + | |     (slide 8 of Math Review 5: | | = | ) = 1 ↓   ( + 1j 1] + |jI     (arithmetic)

= 1 ↓   ( + j 1 + j (since j 1 and j are integers)

= 1 ↓   ( + y 1     (since y = 2j)

(3)  By the induction hypothesis, we know that P(y 2) is true, so we know that

! ' ' = (y 4(这)2)2 . Substituting this into the result from the previous line, we get:

=0

↓   ( = 1 ↓   ( + y 1



= (y 4(这)2)2 + y 1     (from Induction Hypothesis) = y2 4(4)y + 4 + y 1     (arithmetic)

= y2 4y + 4 + 4y 4 (arithmetic)

4

= (arithmetic)



We showed that ! '' = , which concludes the inductive step in Case (i).

=0

Proof of Case (ii): Define P(y) to be predicate ! ' ' = y 241 .

=0

We prove, by induction on y, that P (y) is true for all odd integers y | 0.

1

Base Case: Suppose y = 1.  The expression  ! ''evaluates to ''+'' = 0 + 0 = 0.  The

=0

expression y241 evaluates to 1241 = 0. Therefore, the base case holds.

Induction Hypothesis: For an odd y | 3, assume that P(1) | | | P(y 这 2) is true. Inductive Step: We prove that P(y) is true.