Study Guides (248,402)
CSC165H1 (27)

# Summer.2012.e3_solutions.pdf

2 Pages
119 Views

Department
Computer Science
Course
CSC165H1
Professor
Nathalie Fournier
Semester
Fall

Description
CSC165H1Y Homework Exercise # 3 Summer 2012 1. (a) 9x 2 N;8y 2 N;yx = y This is true. Let x = 1 0 Then, x 2 N Assume y 2 N 0 Then, yx = 1y = y # Math Then, 8y 2 N;yx = y # Universal Introduction Then, 9x 2 N;8y 2 N;yx = y # Existential Introduction (b) 9x 2 N;8y 2 N;4y = x This is false. In order to disprove the statement, we need to prove the negation. :9x 2 N;8y 2 N;4y = x () 8x 2 N;9y 2 N;4y 6= x Assume x 2 N Let y = x 0 Then, y 2 N # Since x 2 N Then, 4y = 4x 6= x # Math; x > 0, since we assumed N start with 1 Then, 9y 2 N;4y 6= x # Existential Introduction Then, 8x 2 N;9y 2 N;4y 6= x # Universal Introduction Note: the above proof uses the assumption that Natural Numbers do not include 0. In the future, we will be using the de▯nitions of Natural Numbers which do include 0. This does not change the value of the statement. The proof, however, would be a bit longer. We could use proof by cases, specifying a di▯erent value for y when x = 0 (try to work through this!). Alternatively, consider the following proof: Assume x 2 N 0 Let y = x + 1 Then, y 2 N # Natural numbers are closed under addition 0 Assume 4y = x Then, x = 4y = 4(x + 1) = 4x + 4 # Math Then, 0 = 3x + 4 # subtract x from both sides Then, x = ▯4=3
More Less

Related notes for CSC165H1
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.