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 allpositive 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)