” 辅导CSE20W21编程、 写作data留学生编程HW5 Proofs and setsCSE20W21Due: Tuesday, February 16, 2021 at 11:00PM on GradescopeIn this assignment,You will analyze statements and determine if they are true or false using valid proof strategies. You willalso determine if candidate arguments are valid.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 creditYou will submit this assignment via Gradescope ( httpss://www.gradescope.com) in the assignment calledHW5-proofs-and-sets.ResourcesTo review the topics you are Working with for this assignment, see the class material from Weeks 4 and 51.Relevant examples in the textbook (all numbers and pages refer to the 7th edition) include: Section 1.5exercises 17, 45. Examples 1 and 3 on page 83 (note typo in parentheses in theorem statement for Example1), Examples 7-8 on page 85, Example 15 on page 89. Section 1.7 exercises 5, 7. Examples 1-3 on page 93.Section 1.7 exercise 3. Examples 8-9 on page 119, Theorem 1 on page 120, Examples 14-15 on page 122,Examples 17-18 on page 123. Section 2.1 exercises 1, 5, 7, 9, 11, 17, 23. Example 1 on page 172, Example3 on page 128. Section 2.2. exercise 3.We will post frequently asked questions and our answers to them in a shared FAQ doc linked below2.1Week 4 material Google Drive folder and Week 5 material Google Drive folder2FAQ Google doc1In your proofs and disproofs of statements below, justify each step by reference to a component of thefollowing proof strategies We have discussed so far, and/or to relevant definitions and calculations. A counterexample can be used to prove that xP(x) is false. A witness can be used to prove that xP(x) is true. Proof of universal by exhaustion: To prove that x P(x) is true when P has a finite domain,evaluate the predicate at each domain element to confirm that it is always T. Proof by universal generalization: To prove that x P(x) is true, we can take an arbitrary elemente from the domain and show that P(e) is true, without making any assumptions about e other thanthat it comes from the domain. To prove that xP(x) is false, write the universal statement that is logically equivalent to its negationand then prove it true using universal generalization. Strategies for conjunction: To prove that p q is true, have two subgoals: subgoal (1) prove p istrue; and, subgoal (2) prove q is true. To prove that p q is false, its enough to prove that p is false.To prove that p q is false, its enough to prove that q is false. Proof of Conditional by Direct Proof: To prove that the implication p q is true, we canassume p is true and use that Assumption to show q is true. Proof of Conditional by Contrapositive Proof: To prove that the implication p q is true, wecan assume q is true and use that assumption to show p is true. Proof by Cases: To prove q when we know p1 p2, show that p1 q and p2 q.Assigned questions1. Consider the predicate F(a, b) = a is a factor of b over the domain Z6=0 Z. Consider the followingquantified statements(i) x Z (F(1, x))(ii) x Z6=0 (F(x, 1))(iii) x Z (F(1, x))(iv) x Z6=0 (F(x, 1))(v) x Z6=0 y Z (F(x, y))(vi) x Z6=0 y Z (F(x, y))(vii) y Z x Z6=0 (F(x, y))(viii) y Z x Z6=0 (F(x, y))(a) (Graded for correctness of choice and fair effort completeness in justification) Which of thestatements (i) – (viii) is being proved by the following proof:By universal generalization, choose e to be an arbitrary integer. We need to show thatF(1, e). By definition of the predicate F, we can rewrite this goal as c Z (e = c 1).We pick the witness c = e, which is an integer and therefore in the domain. Calculating,c1 = e1 = e, as required. Since the predicate F(1, e) evaluates to true for the arbitraryinteger e, the claim has been proved.Hint: it may be useful to identify the key words in the proof that indicate proof strategies.2(b) (Graded for Correctness of choice and fair effort completeness in justification) Which of thestatements (i) – (viii) is being disproved by the following proof:To disprove the statement, we need to find a counterexample. We choose 2, a nonzerointeger so in the domain. We need to show that F(2, 1). By definition of the predicateF, we can rewrite this goal as 1 mod 2 6= 0. By definition of integer division, since1 = 0 2 + 1 (and 0 1 2), 1 mod 2 = 1 which is nonzero so the counterexampleworks to disprove the original statement.Hint: it may be useful to identify the key words in the proof that indicate proof strategies.(c) (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completenessof the translation and proof) Translate the statement to English and then prove or disproveitx Z6=0 y Z6=0 ( F(x, y) F(y, x) )(d) (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completenessof the translation and of the proof) Translate the statement to English and then prove ordisprove itx Z6=0 y Z6=0 ( F(x, y) F(y, x) )(e) (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completenessof the translation And of the proof) Translate the statement to English and then prove ordisprove itx Z6=0 y Z ( F(x, y) F(x + 1, y) F(x + 2, y) )(f) (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completenessof the translation and of the proof) Translate the statement to English and then prove ordisprove itx Z6=0 y Z ( F(x, y + 3) F(x + 4, y) )2. Let W = P({1, 2, 3, 4, 5}).Sample response that can be used as reference for the detail expected in your answer for parts (a) and(b) below:To give an example element in the set {X W | 1 X}{X W | 2 X}, consider {1, 2}. To provethat this is in the set, by definition of intersection, we need to show that {1, 2} {X W | 1 X}and that {1, 2} {X W | 2 X}. By set builder notation, elements in {X W | 1 X} have to be elements of W which have1 as an element. By definition of power set, elements of W are subsets of {1, 2, 3, 4, 5}. Sinceeach element in {1, 2} is an element of {1, 2, 3, 4, 5}, {1, 2} is a subset of {1, 2, 3, 4, 5} and henceis an element of W. Also, by roster method, 1 {1, 2}. Thus, {1, 2} satisfies the conditions formembership in {X W | 1 X}. Similarly, by set builder notation, elements in {X W | 2 X} have to be elements of W whichhave 2 as an element. By definition of power set, elements of W are subsets of {1, 2, 3, 4, 5}. Sinceeach element in {1, 2} is an element of {1, 2, 3, 4, 5}, {1, 2} is a subset of {1, 2, 3, 4, 5} and henceis an element of W. Also, by roster method, 2 {1, 2}. Thus, {1, 2} satisfies the conditions formembership in {X W | 2 X}.3(a) (Graded for correctness3) Give two Example elements inW WJustify your examples by explanations that include references to the relevant definitions.(b) (Graded for correctness) Give one example element inP(W)that is not equal to or to W. Justify your examples by explanations that include references tothe relevant definitions.(c) (Graded for correctness) Consider the following statement and attempted proof:A W B W ( ((A B) A) (A B) )(1) Towards a universal generalization argument, choose arbitrary A W, B W .(2) We need to show ((A B) A) (A B).(3) Towards a proof of the conditional by the contrapositive, assume A B, and weneed to show that (A B) A.(4) By definition of subset inclusion, this means we need to show x (x A B x A ).(5) Towards a universal generalization, choose arbitrary x; we need to show thatx A B x A.(6) Towards a direct proof, assume x A B, and we need to show x A.(7) By definition of set intersection and set builder notation, we have that x Ax B.(8) By the definition of conjunction, x A, which is what we needed to show. QEDDemonstrate that this attempted proof is invalid by providing and justifying a counterexample(disproving the statement).(d) (Graded for fair effort completeness) Explain why the attempted proof from part (c) is invalidby identifying in which step a definition or proof strategy is used incorrectly, and describing howthe definition or proof strategy was misused.3. (Graded for correctness) We define the set of bases as B = {A, C, U, G}. The set of RNA strands S isdefined (recursively) by:Basis Step: A S, C S, U S, G SRecursive Step: If s S and b B, then sb Swhere sb is string concatenation. The function rnalen that computes the length of RNA strands in Sis defined recursively by rnalen : S Z+Basis step: If b B then rnalen(b) = 1Recursive step: If s S and b B, then rnalen(sb) = 1 + rnalen(s)3This means your solution will be evaluated not only on the correctness of your answers, but on your ability to present yourideas 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 shouldalways be well-supported. Your goal should be to convince the reader that your results and methods are sound.4The function Basecount that computes the number of a given base b appearing in a RNA strand s isdefined recursively by basecount : S B NBasis step: If b1 B, b2 B, basecount(b1, b2) = (1 when b1 = b20 when b1 6= b2Recursive Step: If s S, b1 B, b2 B, basecount(sb1, b2) = (1 + basecount(s, b2) when b1 = b2basecount(s, b2) when b1 6= b2Prove or disprove:b B s S ( rnalen(s) = basecount(s, b) )In your justification, justify the Value of each function application you use by (repeatedly) referringback to the recursive function definitions.如有需要，请加QQ：99515681 或WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
