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

Discrete Mathematics and Its Applications

HW7 Proofs, Numbers, and Cardinality

离散数学及其应用代写 In this assignment, You will practice determining and justifying whether statements are true in multiple contexts.

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.

In particular, these policies address

• Collaboration policy

• Where to get help

• Typing your solutions

• 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 9¹.

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 below².

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.

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

² FAQ Google doc

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

1. (Graded for correctness³ )

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 completeness⁴ ) 离散数学及其应用代写

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.

³ This means your solution will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should explain how you arrived at your conclusions, using mathematically sound reasoning.  Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.

⁴ 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 D_f  defined as

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

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

(b) Define a function h such that D_h = 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 k₁ = 9.

(a) (Graded for correctness) Calculate the number you send to Bob, a^k1 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, (a^k2 )^k1 mod p.  Hint: a^k2 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}:

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

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

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

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

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

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

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

更多代写：Java课业作业代写  GMAT代考  英国计量经济学网课代刷  加拿大Essay代写多少钱  加拿大高中论文代写范文 留学essay写作代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写