Summer.2012.e3_solutions.pdf

2 Pages
119 Views
Unlock Document

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

Log In


OR

Join OneClass

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

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit