CSC165H1, Winter 2022 CSC165H1: Worksheet 1—Mathematical Preliminaries (Partial Solutions)

Learning objectives

By the end of this worksheet, you will:

• Understand and apply definitions about sets, strings, and common mathematical functions.

Copyright By cscodehelp代写 加微信 cscodehelp

• Simplify summation and product expressions.

1. Set complement. Let A and U be sets, and assume that A ⊆ U. The complement of A in U, denoted Ac, is

defined to be set of elements that are in U but not A. Ac depends on the choice of both U and A!

(a) Let U be the set of natural numbers between 1 and 6, inclusive. Let A = {2, 5}. What is Ac?

(b) Given an arbitrary A and U, write an expression for Ac in terms of A, U, and the set difference operator .

(c) Let U = R, A = {x | x ∈ U and 0 < x ≤ 2}, and B = {x | x ∈ U and 1 ≤ x < 4}. Find each of the following: Ac ∩ Bc, Ac ∪ Bc, (A ∩ B)c and (A ∪ B)c. Drawing number lines may be helpful. What relationships do you notice between these sets?
Ac = {1,3,4,6}.
Ac = U A.
Ac ∩ Bc = {x | x ∈ U and x ≤ 0 or x ≥ 4}
Ac ∪ Bc = {x | x ∈ U and x < 1 or x > 2} (A∩B)c ={x|x∈U andx<1orx>2} (A∪B)c ={x|x∈U andx≤0orx≥4}

There are two equalities we observe: Ac ∩ Bc = (A ∪ B)c and Ac ∪ Bc = (A ∩ B)c (de Morgan’s laws for sets).

partitions. Let A be a set. A (finite or infinite) collection of nonempty sets {A1, A2, A3, . . . } is called a

partition of A when (1) A is the union of all of the Ai,1 and (2) the sets A1, A2, A3, . . . do not have any element in common.2

(a) Recall that Z+ is the set of all positive integers. Let

T0 ={n|n∈Z+ andn=3k, forsomeintegerk},

T1 ={n|n∈Z+ andn=3k+1, forsomeintegerk}, T2 ={n|n∈Z+ andn=3k+2, forsomeintegerk}, T3 ={n|n∈Z+ andn=6k, forsomeintegerk}.

Write the smallest three elements of T0, of T1, of T2, and of T3.

1We say the Ai are exhaustive.

2We say the Ai are mutually disjoint (or pairwise disjoint or non-overlapping) when no two distinct sets Ai and Aj have any element in common.

CSC165H1, Winter 2022 CSC165H1: Worksheet 1—Mathematical Preliminaries (Partial Solutions)

T0 = {3,6,9,…}, T1 = {1,4,7,…}, T2 = {2,5,8,…}, T3 = {6,12,18,…}.

(b) Write down a partition of Z+ using T0, T1, T2, and/or T3. Why can’t you use all four sets?

The set {T0,T1,T2} is a partition of Z+, since, when any positive integer is divided by 3, the possible integer remainders are 0, 1, and 2. The sets T0, T1, T2 list the numbers whose remainder when divided by 3 are 0, 1, or 2, respectively.

T3 ⊆ T0, so we can’t use both T0 and T3 in our partition (they have elements in common).

CSC165H1, Winter 2022 CSC165H1: Worksheet 1—Mathematical Preliminaries (Partial Solutions)

3. Strings. An alphabet A is a set of symbols like {0,1} or {a,b,c}. We define a string over alphabet A as an ordered sequence of elements from A; the length of a finite string is its number of elements.

For example, 011 is a string over {0, 1} of length three, and abbbacc is a string over {a, b, c} of length seven.

(a) Write down all strings over the alphabet {0, 1} of length three (you should have eight in total).

(b) Let S1 be the set of all strings over {a, b, c} that have length two, and S2 be the set of all strings over {a, b, c} that start and end with the same letter. Find S1 ∩ S2 and S1 S2.

(c) What is the relationship between S1, S1 ∩ S2, and S1 S2?

4. The floor and ceiling functions. Let x ∈ R. We define the floor of x, denoted ⌊x⌋, to be the largest integer that is less than or equal to x. Similarly, we define the ceiling of x, denoted ⌈x⌉, to be the smallest integer that is greater than or equal to x.

(a) Compute ⌊x⌋ and ⌈x⌉ for each of the following values of x: x = 25 , x = 0.999, and x = −2.01. 4

(b) What is the domain and codomain of the floor and ceiling functions?

(c) Consider the following statement: For all real numbers x and y, ⌊x + y⌋ = ⌊x⌋ + ⌊y⌋. Is this statement is True or False? Why?

{000, 001, 010, 011, 100, 101, 110, 111}

S1 ∩ S2 = {aa, bb, cc}.

S1 S2 ={ab,ac,ba,bc,ca,cb}.

Note that S2 is actually an infinite set, but both S1 ∩ S2 and S1 S2 are finite.

Hint: look at (S1 ∩ S2) ∪ (S1 S2).

4 =⌊6.25⌋=6, 4 =⌈6.25⌉=7,⌊0.999⌋=0,⌈0.999⌉=1,⌊−2.01⌋=−3,⌈−2.01⌉=−2.

The domain is R and the codomain is Z.

1 2 7 1 2 ThestatementisFalse,since,forexample, 2+3 = 6 =1,while 2 + 3 =0+0=0.

CSC165H1, Winter 2022 CSC165H1: Worksheet 1—Mathematical Preliminaries (Partial Solutions)

5. Sumandproductnotation. Recallthatthenotationf(i)givesusashortformforf(j)+f(j+1)+···+ i=j

f(k − 1) + f(k), and that f(i) gives us a short form for f(j) × f(j + 1) × · · · × f(k − 1) × f(k). i=j

(a) Expand the following expressions into their long sum/product form. Do not evaluate the resulting expressions.

3 1111 (k + 1) = (1 + 1) + (2 + 1) + (3 + 1) = +

(k2 +3)=(1+3)+(0+3)+(1+3)+(4+3) k=−1

(2k) = 2 + 4 + 6 + 8 + 10 k=1

(−1)j =0− + − + j=0 j+1 2345

4 i(i+2) 2·4 3·5 4·6 = · ·

(i−1)(i+1) 1·3 2·4 3·5

(b) Rewrite each of the following expressions by using sum or product notation.

3+6+12+24+48+96=3·2i i=0

1+4+ 9 +16+ 25 + 36 =j2

0+1−2+3−4+5=

(−1)j+1 ·j

3 9 27 81 243 729 1 2 3

k k j

1·2 2·3 3·4 3·4×4·5×5·6

= 3 j · (j + 1)

(j +2)·(j +3) j=1

CSC165H1, Winter 2022 CSC165H1: Worksheet 1—Mathematical Preliminaries (Partial Solutions)

6. Sum and product laws. It is possible to prove properties that help us manipulate sums and products. Let m,n ∈ Z, and let am,am+1,am+2,… and bm,bm+1,bm+2,… be sequences of real numbers, and let c ∈ R. Then the following equations hold:3

n i n i+1

i+1 i+2 i=1 i=1

n nn (ai + bi) = ai + bi

i=m i=m i=m

(ai·bi)= ai · bi i=m i=m i=m

nn c·ai =c· ai i=m i=m

ai = ai′+m i=m i′ =0

ai = ai′+m

(separating sums) (separatingproducts) (pullingoutconstant) (changing index) (changing index)

Using these laws, rewrite each of the following as a single sum or product, but do not evaluate your final sum/product.4 nn

3·(2i−3)+(4−5i) i=1 i=1

3 · (2i − 3) + (4 − 5i) = (6i − 9) + (4 − 5i)

= (6i − 9) + (4 − 5i) i=1

= (i − 5) i=1

n i n i+1 n i i+1 =·

i+1 i+2 =n i

2i + (i − 1) (change the indexes to match) i=10 i=101

3Because of how we’ve defined the empty sum and empty product, these equations hold even when n < m! 4We’ll cover some formulas for evaluating common sums and products throughout this course.
CSC165H1, Winter 2022 CSC165H1: Worksheet 1—Mathematical Preliminaries (Partial Solutions)
15 106 5 5
2i+ (i−1)=2(i+10)+(i+101−1)
i=10 i=101
i=0 i=0 55
= 2(i + 10) + (i + 101 − 1) i=0 i=0
= 2(i + 10) + (i + 101 − 1) i=0
= (3i + 120) i=0
Note: it is also possible to change the first summation to go from i = 101 to 106, or the second summation to go from i = 10 to 15.
程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com