Class Notes
(807,344)

Canada
(492,711)

University of Toronto St. George
(42,781)

Computer Science
(737)

CSC165H1
(160)

Nathalie Fournier
(31)

Lecture

# handout7.pdf

Unlock Document

University of Toronto St. George

Computer Science

CSC165H1

Nathalie Fournier

Fall

Description

CSC165H1F Homework Assignment # 2 Fall 2011
Worth: 8% Due: By 10pm on Friday 4 November.
Remember to write the full name, student number, and CDF/UTOR email address of each group
member prominently on your submission.
Please read and understand the policy on Collaboration given on the Course Information Sheet. Then, to protect
yourself, list on the front of your submission every source of information you used to complete this homework
(other than your own lecture and tutorial notes, and materials available directly on the course webpage). For
example, indicate clearly the name of every student with whom you had discussions (other than group members),
the title of every additional textbook you consulted, the source of every additional web document you used, etc.
For each question, please write up detailed answers carefully. Make sure that you use notation and terminology
correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous
use of notation and terminology, and for making incorrect, unjusti▯ed, ambiguous, or vague claims in your solutions.
[40] 1. In this question, you are to consider four propositions and their (incorrect) proofs. For each part, translate
the given proof into a detailed structured proof, using the style presented in class and in the lecture notes.
Then explain why the proof is not correct (i.e., clearly state what error(s) was(were) made). And, ▯nally,
provide a counter-example that shows that the proposition is not correct.
(a) Proposition. Suppose that x and y are real numbers and x 6= 3: If x y = 9y then y = 0:
Proof. Suppose that x y = 9y. Then (x ▯ 9)y = 0: Since x 6= 3; x 6= 9; so x ▯ 9 6= 0: Therefore we
can divide both sides of the equation (x ▯9)y = 0 by x ▯9, which leads to the conclusion that y = 0:
2
Thus, if x y = 9y then y = 0:
(b) Proposition. Suppose that A ▯ C; B ▯ C; and x 2 A: Then x 2 B:
Proof. Suppose that x 2 = B: Since x 2 A and A ▯ C, x 2 C: Since x 2 = B and B ▯ C; x 2 = C: But now
we have proven both x 2 C and x 2 = C; so we have reached a contradiction. Therefore x 2 B:
(c) Proposition. If (8x 2 A;x 6= 0) and A ▯ B then (8x 2 B;x 6= 0):

More
Less
Related notes for CSC165H1