辅导CSE20W21编程、讲解data留学生编程、辅导Java，Python程序
- 首页 >> Java编程 HW5 Proofs and sets
CSE20W21
Due: Tuesday, February 16, 2021 at 11:00PM on Gradescope
In this assignment,
You will analyze statements and determine if they are true or false using valid proof strategies. You will
also 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 credit
You will submit this assignment via Gradescope (https://www.gradescope.com) in the assignment called
“HW5-proofs-and-sets”.
Resources
To 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.5
exercises 17, 45. Examples 1 and 3 on page 83 (note typo in parentheses in theorem statement for Example
1), 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, Example
3 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 folder
2FAQ Google doc
1
In your proofs and disproofs of statements below, justify each step by reference to a component of the
following 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 element
e from the domain and show that P(e) is true, without making any assumptions about e other than
that it comes from the domain.
• To prove that ∃xP(x) is false, write the universal statement that is logically equivalent to its negation
and then prove it true using universal generalization.
• Strategies for conjunction: To prove that p ∧ q is true, have two subgoals: subgoal (1) prove p is
true; and, subgoal (2) prove q is true. To prove that p ∧ q is false, it’s enough to prove that p is false.
To prove that p ∧ q is false, it’s enough to prove that q is false.
• Proof of Conditional by Direct Proof: To prove that the implication p → q is true, we can
assume 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, we
can 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 questions
1. Consider the predicate F(a, b) = “a is a factor of b” over the domain Z
6=0 ×Z. Consider the following
quantified statements
(i) ∀x ∈ Z (F(1, x))
(ii) ∀x ∈ Z
6=0 (F(x, 1))
(iii) ∃x ∈ Z (F(1, x))
(iv) ∃x ∈ Z
6=0 (F(x, 1))
(v) ∀x ∈ Z
6=0 ∃y ∈ Z (F(x, y))
(vi) ∃x ∈ Z
6=0 ∀y ∈ Z (F(x, y))
(vii) ∀y ∈ Z ∃x ∈ Z
6=0 (F(x, y))
(viii) ∃y ∈ Z ∀x ∈ Z
6=0 (F(x, y))
(a) (Graded for correctness of choice and fair effort completeness in justification) Which of the
statements (i) - (viii) is being proved by the following proof:
By universal generalization, choose e to be an arbitrary integer. We need to show that
F(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,
c·1 = e·1 = e, as required. Since the predicate F(1, e) evaluates to true for the arbitrary
integer 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 the
statements (i) - (viii) is being disproved by the following proof:
To disprove the statement, we need to find a counterexample. We choose 2, a nonzero
integer so in the domain. We need to show that ¬F(2, 1). By definition of the predicate
F, we can rewrite this goal as 1 mod 2 6= 0. By definition of integer division, since
1 = 0 · 2 + 1 (and 0 ≤ 1 < 2), 1 mod 2 = 1 which is nonzero so the counterexample
works 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 completeness
of the translation and proof) Translate the statement to English and then prove or disprove
it
∀x ∈ Z
6=0 ∀y ∈ Z
6=0 ( F(x, y) → F(y, x) )
(d) (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completeness
of the translation and of the proof) Translate the statement to English and then prove or
disprove it
∀x ∈ Z
6=0 ∀y ∈ Z
6=0 ( F(x, y) → ¬F(y, x) )
(e) (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completeness
of the translation and of the proof) Translate the statement to English and then prove or
disprove it
∃x ∈ Z
6=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 completeness
of the translation and of the proof) Translate the statement to English and then prove or
disprove it
∃x ∈ Z
6=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 prove
that 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 have
1 as an element. By definition of power set, elements of W are subsets of {1, 2, 3, 4, 5}. Since
each 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 hence
is an element of W. Also, by roster method, 1 ∈ {1, 2}. Thus, {1, 2} satisfies the conditions for
membership in {X ∈ W | 1 ∈ X}.
• Similarly, by set builder notation, elements in {X ∈ W | 2 ∈ X} have to be elements of W which
have 2 as an element. By definition of power set, elements of W are subsets of {1, 2, 3, 4, 5}. Since
each 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 hence
is an element of W. Also, by roster method, 2 ∈ {1, 2}. Thus, {1, 2} satisfies the conditions for
membership in {X ∈ W | 2 ∈ X}.
3
(a) (Graded for correctness3
) Give two example elements in
W × W
Justify your examples by explanations that include references to the relevant definitions.
(b) (Graded for correctness) Give one example element in
P(W)
that is not equal to ∅ or to W. Justify your examples by explanations that include references to
the 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 we
need 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 that
x ∈ 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 ∈ A∧x ∈ B.
(8) By the definition of conjunction, x ∈ A, which is what we needed to show. QED
Demonstrate 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 invalid
by identifying in which step a definition or proof strategy is used incorrectly, and describing how
the 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 is
defined (recursively) by:
Basis Step: A ∈ S, C ∈ S, U ∈ S, G ∈ S
Recursive Step: If s ∈ S and b ∈ B, then sb ∈ S
where sb is string concatenation. The function rnalen that computes the length of RNA strands in S
is defined recursively by rnalen : S → Z
+
Basis step: If b ∈ B then rnalen(b) = 1
Recursive 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 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.
4
The function basecount that computes the number of a given base b appearing in a RNA strand s is
defined recursively by basecount : S × B → N
Basis step: If b1 ∈ B, b2 ∈ B, basecount(b1, b2) = (
1 when b1 = b2
0 when b1 6= b2
Recursive Step: If s ∈ S, b1 ∈ B, b2 ∈ B, basecount(sb1, b2) = (
1 + basecount(s, b2) when b1 = b2
basecount(s, b2) when b1 6= b2
Prove 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) referring
back to the recursive function definitions.
5
CSE20W21
Due: Tuesday, February 16, 2021 at 11:00PM on Gradescope
In this assignment,
You will analyze statements and determine if they are true or false using valid proof strategies. You will
also 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 credit
You will submit this assignment via Gradescope (https://www.gradescope.com) in the assignment called
“HW5-proofs-and-sets”.
Resources
To 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.5
exercises 17, 45. Examples 1 and 3 on page 83 (note typo in parentheses in theorem statement for Example
1), 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, Example
3 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 folder
2FAQ Google doc
1
In your proofs and disproofs of statements below, justify each step by reference to a component of the
following 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 element
e from the domain and show that P(e) is true, without making any assumptions about e other than
that it comes from the domain.
• To prove that ∃xP(x) is false, write the universal statement that is logically equivalent to its negation
and then prove it true using universal generalization.
• Strategies for conjunction: To prove that p ∧ q is true, have two subgoals: subgoal (1) prove p is
true; and, subgoal (2) prove q is true. To prove that p ∧ q is false, it’s enough to prove that p is false.
To prove that p ∧ q is false, it’s enough to prove that q is false.
• Proof of Conditional by Direct Proof: To prove that the implication p → q is true, we can
assume 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, we
can 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 questions
1. Consider the predicate F(a, b) = “a is a factor of b” over the domain Z
6=0 ×Z. Consider the following
quantified statements
(i) ∀x ∈ Z (F(1, x))
(ii) ∀x ∈ Z
6=0 (F(x, 1))
(iii) ∃x ∈ Z (F(1, x))
(iv) ∃x ∈ Z
6=0 (F(x, 1))
(v) ∀x ∈ Z
6=0 ∃y ∈ Z (F(x, y))
(vi) ∃x ∈ Z
6=0 ∀y ∈ Z (F(x, y))
(vii) ∀y ∈ Z ∃x ∈ Z
6=0 (F(x, y))
(viii) ∃y ∈ Z ∀x ∈ Z
6=0 (F(x, y))
(a) (Graded for correctness of choice and fair effort completeness in justification) Which of the
statements (i) - (viii) is being proved by the following proof:
By universal generalization, choose e to be an arbitrary integer. We need to show that
F(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,
c·1 = e·1 = e, as required. Since the predicate F(1, e) evaluates to true for the arbitrary
integer 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 the
statements (i) - (viii) is being disproved by the following proof:
To disprove the statement, we need to find a counterexample. We choose 2, a nonzero
integer so in the domain. We need to show that ¬F(2, 1). By definition of the predicate
F, we can rewrite this goal as 1 mod 2 6= 0. By definition of integer division, since
1 = 0 · 2 + 1 (and 0 ≤ 1 < 2), 1 mod 2 = 1 which is nonzero so the counterexample
works 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 completeness
of the translation and proof) Translate the statement to English and then prove or disprove
it
∀x ∈ Z
6=0 ∀y ∈ Z
6=0 ( F(x, y) → F(y, x) )
(d) (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completeness
of the translation and of the proof) Translate the statement to English and then prove or
disprove it
∀x ∈ Z
6=0 ∀y ∈ Z
6=0 ( F(x, y) → ¬F(y, x) )
(e) (Graded for correctness of evaluation of statement (is it true or false?) and fair effort completeness
of the translation and of the proof) Translate the statement to English and then prove or
disprove it
∃x ∈ Z
6=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 completeness
of the translation and of the proof) Translate the statement to English and then prove or
disprove it
∃x ∈ Z
6=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 prove
that 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 have
1 as an element. By definition of power set, elements of W are subsets of {1, 2, 3, 4, 5}. Since
each 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 hence
is an element of W. Also, by roster method, 1 ∈ {1, 2}. Thus, {1, 2} satisfies the conditions for
membership in {X ∈ W | 1 ∈ X}.
• Similarly, by set builder notation, elements in {X ∈ W | 2 ∈ X} have to be elements of W which
have 2 as an element. By definition of power set, elements of W are subsets of {1, 2, 3, 4, 5}. Since
each 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 hence
is an element of W. Also, by roster method, 2 ∈ {1, 2}. Thus, {1, 2} satisfies the conditions for
membership in {X ∈ W | 2 ∈ X}.
3
(a) (Graded for correctness3
) Give two example elements in
W × W
Justify your examples by explanations that include references to the relevant definitions.
(b) (Graded for correctness) Give one example element in
P(W)
that is not equal to ∅ or to W. Justify your examples by explanations that include references to
the 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 we
need 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 that
x ∈ 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 ∈ A∧x ∈ B.
(8) By the definition of conjunction, x ∈ A, which is what we needed to show. QED
Demonstrate 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 invalid
by identifying in which step a definition or proof strategy is used incorrectly, and describing how
the 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 is
defined (recursively) by:
Basis Step: A ∈ S, C ∈ S, U ∈ S, G ∈ S
Recursive Step: If s ∈ S and b ∈ B, then sb ∈ S
where sb is string concatenation. The function rnalen that computes the length of RNA strands in S
is defined recursively by rnalen : S → Z
+
Basis step: If b ∈ B then rnalen(b) = 1
Recursive 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 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.
4
The function basecount that computes the number of a given base b appearing in a RNA strand s is
defined recursively by basecount : S × B → N
Basis step: If b1 ∈ B, b2 ∈ B, basecount(b1, b2) = (
1 when b1 = b2
0 when b1 6= b2
Recursive Step: If s ∈ S, b1 ∈ B, b2 ∈ B, basecount(sb1, b2) = (
1 + basecount(s, b2) when b1 = b2
basecount(s, b2) when b1 6= b2
Prove 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) referring
back to the recursive function definitions.
5