Def. An integer n > 1 is composit if and only if there exist positive integers r and s such that n = rs and r != 1 and s != 1.
Def. An integer n > 1 is prime if and only if for all positive integers r and s, if n = rs, then r = 1 or s = 1.
Prove or Disprove:
- For every positive integer n, the integer 3n is composit.
False (universally quantified –> disprove)
Counter example: Let n = 1. Then 3n = 3 * 1 = 3, which is prime.
- There exists an integer m such that m^2 - 1 is prime.
True (existentially quantified –> proove)
Proof: Let m = 2. Then m^2 - 1 = 2^2 -1 = 3, which is prime
- For all positive integers n, 2n^2 + 4 is composite. Factor: 2n^2 + 4 = 2(n^2 + 2) True (universlly quantified), this expression can be factored into two statements, neither of which are composit. Proof: Let n be any positive integer. Then 2n^2 + 4 = 2(n^2 + 2). So 2 and n^2 + 2 are both integers. And 2 != 1, also n^2 + 2 >= 1^2 + 2 = 3. Thus n^2 + 2 != 1. Therefore 2n^2 + 4 is composite.
- There exists a positive integer n such that n^2 + 3n + 2 is prime. False (existentialy quantified) we know this is false because n^2 + 3n + 2 = (n + 2)(n + 1) <– that factors to two expressions where neither is equal to 1 Prove: For all positive integers n, n^2 + 3n + 2 is composite. Disproof: Let n be a positive integer. Then n^2 + 2n + 2 = (n + 1)(n + 2). Observe n+ 1 and n+ 2are positive integers and n + 2 != 1 since n + 2 >= 3. Therefore n^3 + 3n + 2 is composite.
Proove P => Q Direct proof: Assume P. Proove Q. Proof by contrapositive: Assume ~Q. Proove ~P.
Universal for all x, P(x) proof: Let x be arbitrary
True: (don’t argue from an example)
False: counter example let x = _____ Show ~P(x)
Existential there exists x such that
True: proof: Let x = _____ (okey to argue from an example)
False Disproof: For all x, ~P(x) Let x be arbitrary Proove ~P(x)