Search the whole station

# 离散数学及其应用代写 Proofs代写 Numbers代写

126

## HW7 Proofs, Numbers, and Cardinality

In this assignment,

You will practice determining and justifying whether statements are true in multiple contexts.

For all HW assignments:

Please see the instructions and policies for assignments on the class website and on the writeup for HW1.

• Collaboration policy

• Where to get help

• Expectations for full credit

### Resources离散数学及其应用代写

To review the topics you are working with for this assignment, see the class material from Weeks 7, 8 and 91.

Relevant examples in the textbook (all numbers and pages refer to the 7th edition) include: Example 2 on page 258, Example 10 on page 265, Example 14 on page 266. Section 4.3 exercises 3, 5 Examples 7-14

on pages 85-88. Section 1.7 exercises 3, 7, 9, 11, 16, 25. Examples 8-17 on pages 142-144. Section 2.3 exercises 15, 21. Examples 1,4,5 on pages 171-173. Section 2.5 exercises 1, 11, 15, 17. Example 7 on page 576, Example 9 on page 576. Section 9.1 exercises 1, 5. Example 3 on page 609, Example 5 on page 609, Example 10 on page 611, Example 15 on page 614. Section 9.5 exercises 3, 7, 25, 29, 43, 45, 57. Example 12 on page 254. Section 4.2 exercise 25. Key exchange on page 302. Section 4.6 exercise 29. Example 1-3 on pages 618-619. Examples 12-13 on pages 623-624. Section 9.6 exercises 1, 5, 9, 21, 23.

We will post frequently asked questions and our answers to them in a shared FAQ doc linked below2.

In your proofs and disproofs of statements below, justify each step by reference to the proof strategies we have discussed so far, and/or to relevant definitions and calculations.

1 Week 7 material Google Drive folder and Week 8 material Google Drive folder and Week 9 material Google Drive folder

### Assigned questions离散数学及其应用代写

#### 1. (Graded for correctness3 )

Recall the definition of the set of rational numbers,

#### 2. (Each part graded for correctness in evaluating statement and for fair effort completeness in the justification)

Consider the set U = P(R). Prove or disprove each of the following claims. In your justifications, you may refer to any of the facts about cardinality we mentioned in class or that appear in the relevant sections in the textbook. Include the specific slide number for specific day, location on specific worksheet, or page number to help the person reading your proof find the claims you use.

(a) ∀A ∈ U ∀B ∈ U ( (A ⊆ B → |A| ≤ |B| )

(b) ∀X ∈ U ∀Y ∈ U ( Z ⊆ X ∧ Z ⊆ Y → |X| = |Y | )

#### 3. (Graded for fair effort completeness4 ) 离散数学及其应用代写

In the Week 1 Notes, we have the definition of the set of binary strings:

The set of binary strings, denoted {0, 1}which we read as “zero one star”, is defined (recursively) by:

Basis Step:    λ ∈ {0, 1}

Recursive Step: If s ∈ {0, 1} then s0 ∈ {0, 1} and s1 ∈ {0, 1}

where s0 and s1 are the results of string concatenation. The symbol λ, pronounced “lambda” is used to denote the empty string and has the property that λx = xλ = x for each string x.

4 This means you will get full credit so long as your submission demonstrates honest effort to answer the question. You will not be penalized for incorrect answers.

Recall (from Week 4 Notes) the function redun3 : {0, 1} → {0, 1} where the output of the function is computed by the algorithm below.

(a) Determine and briefly justify whether redun3 is one-to-one.

(b) Determine and briefly justify whether redun3 is onto.

(c) Determine and briefly justify whether {0, 1} is finite, countably infinite, or uncountable.

#### 4. (Graded for fair effort completeness)

The diagonalization argument constructs, for each function f : N → P(N), a set Df  defined as

Df = {x ∈ N | x /∈ f(x)}

(a) Define a function g such that Dg = , or explain why no such function exists.

(b) Define a function h such that Dh = N, or explain why no such function exists.

#### 5. 离散数学及其应用代写

Imagine you are playing the role of Alice in the Diffie Hellman key agreement (exchange) protocol (page 302). You and Bob have agreed to use the prime p = 7 and its primitive root a = 3. Your secret integer is k1 = 9.

(a) (Graded for correctness) Calculate the number you send to Bob, ak1 mod p. Use Algorithm 5 on page 254 for the calculation of modular exponentiation. Include a trace of the algorithm in your solution.

(b) (Graded for correctness) Bob sends you the number 5. Compute your shared key, (ak2 )k1 mod p.  Hint: ak2 mod p is what Bob sent you. Include all relevant calculations, annotated with explanations, for full credit.

(c) (Graded for fair effort completeness) What are some possible values for Bob’s secret integer? What algorithm are you using to compute them?

#### 6. (Graded for correctness) 离散数学及其应用代写

Consider the following binary relations. For each one (i) determine if it is an equivalence relation, a partial order, or neither. (This part is graded for correctness in evaluating the statement and for fair effort completeness in the justification) (ii) If it is an equivalence relation give an example of an equivalence class by writing out its definition in set builder notation and giving at least two elements in the class; if it is a partial order, draw its Hasse diagram; if it is neither, explain which properties (reflexivity, symmetry, transitivity, antisymmetry) it fails to have. (This part is graded for correctness; you should include justifications.)

(a) Recall that in a movie recommendation system, each user’s ratings of movies is represented as a n-tuple (with the positive integer n being the number of movies in the database), and each component of the n-tuple is an element of the collection {−1, 0, 1}. Assume there are five movies in the database, so that each user’s ratings can be represented as a 5-tuple. Consider the binary relation on the set of all 5-tuples where each component of the 5-tuple is an element of the collection {−1, 0, 1}:

G1 = {(u, v) | the ratings of users u and v agree about the first movie in the database}

(b) Define U3 = P({1, 2, 3}). Consider the binary relation on U3:

Sub = {(X, Y ) | X ⊆ Y }

(c) Define N5 = {0, 1, 2, 3, 4}. Consider the binary relation on N5:

P = {(a, b) | (a · b) mod 5 = 1}

(d) Define N5 = {0, 1, 2, 3, 4}. Consider the binary relation on N5:

F = {(a, b) | ∃c ∈ Z ( b = (a · c) mod 5 )}

### Related recommendations

• #### R代码代写 Jupyter notebook代写 R code代写 assessment代写

21

R代码代写 isease X is a newly-discovered infectious disease of humans. It is directly transmitted (i.e. without need for vectors).

View details
• #### 设计管理代写 Design Management代写 LICA242代写

26

设计管理代写 Introduction To allow you to demonstrate the Learning Outcomes, you are asked to complete two assignments worth 100% of the module. As...

View details
• #### 战略品牌管理代写 Strategic Brand Management代写

26

战略品牌管理代写 Assignment Task This assignment is an individual presentation. You are to record a video or PowerPoint with audio voice-over using...

View details
• #### 国际商业计划书代写 International Entrepreneurship代写 IE770代写

45

国际商业计划书代写 If you are resitting this assignment please take note of the feedback on your original submission and make the necessary improve...

View details
1