Class Notes (835,342)
CSC165H1 (167)
Lecture

# tut04solution.pdf

2 Pages
118 Views

Department
Computer Science
Course
CSC165H1
Professor
Nathalie Fournier
Semester
Fall

Description
CSC165H1F Tutorial # 4 | Sample Solutions Fall 2011 1. Write detailed proof structures for each of the following statements. Don’t write complete proofs|for now, focus on the proof structure only and leave out all of the actual \content". (a) 8x 2 Z;8y 2 Z;x 6 y ) 9z 2 Z;x 6 z 6 y Assume x 2 Z and y 2 Z. # domain assumption. Assume x 6 y. # antecedent. 0 Let z = ::: # pick a value that depends on x and y. [...proof...] Then, z 2 Z. [...proof...] Then, x 6 z 6 y. Then, 9z 2 Z;x 6 z 6 y. # introduce 9 Then, x 6 y ) 9z 2 Z;x 6 z 6 y. # introduce ) Then, 8x 2 Z;8y 2 Z;x 6 y ) 9z 2 Z;x 6 z 6 y. # introduce 8 2 (b) 8x 2 Z;(9y 2 Z;x = 3y + 1) ) (9y 2 Z;x = 3y + 1) Assume x 2 Z. # domain assumption. Assume 9y 2 Z;x = 3y + 1. # antecedent. Let y0be such that x = 3y + 10 # by assumption 0 Let y = ::: # pick a value that depends on x and y . 0 [...proof...] 0 Then, y 2 Z [...proof...] 2 0 Then, x = 3y + 1 Then, 9y 2 Z;x = 3y + 1. # introduce 9 2 Then, (9y 2 Z;x = 3y + 1) ) (9y 2 Z;x = 3y + 1) # introduce ) Then, 8x 2 Z;(9y 2 Z;x = 3y + 1) ) (9y 2 Z;x = 3y + 1) # introduce 8 (c) :8x 2 N;9y 2 N;y > x ^ a > a y x First, we work the negation into the statement. :8x 2 N;9y 2 N;y > x ^ a > a () 9x 2 N;:9y 2 N;y > x ^ a > a y x y x () 9x 2 N;8y 2 N;:(y > x ^ a > a ) y x () 9x 2 N;8y 2 N;y > x ) :(a > a ) y x () 9x 2 N;8y 2 N;y > x ) a 6 a y x Then, we can write down the proof structure. Let x = :::. [...proof...] Then, x 2 N. Assume y 2 N. # domain assumption. Assume y > x . 0 # antecedent. [...proof...]
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.