CPSC 121 Study Guide - Midterm Guide: First-Order Logic, Contraposition, Natural Number

• School: UBC
• Department: Computer Science
• Course: CPSC 121
• Professor: All

Document Summary

For any integer n, if 2n 1 is a prime, then n is also prime. Prime(x) which is true when x is a prime. Solution : n z, prime(2n 1) prime(n). Suppose that you decide to prove this theorem using a direct proof. Solution : you would consider an unspeci ed integer n, and assume that 2n 1 is prime. You would need to prove that n is prime. [4] c. suppose that you decide to prove this theorem using a proof by contrapositive. Solution : you would consider an unspeci ed integer n, and assume that n is not prime. You would need to prove that 2n 1 is not prime. [4] d. suppose that you decide to prove this theorem using a proof by contradiction. Write down what you would assume and what you would need to show. Solution : you would assume that some integer n is not prime, but that 2n 1 is prime.