Math 3200 - Exam #1

Intro to Proofs exam 1 Paul Pollack

Statement

Statement

A declarative sentence that is true or false (not both).

Compound Statements

A statement built out of simpler statements, using ∧, ∨, ⇒, ~.

Logically Equivalent Statements

Statements that always have the same truth value, no matter what the truth values of the initial components are.

Implication

A statement of the form P ⇒ Q

Q ⇒ P

Converse of an implication

~P ⇒ ~Q

Inverse of an implication

~Q ⇒ ~P

Contrapositive of an implication

Direct Proof

Proof technique to show P ⇒ Q: Assume P is true, conclude that Q is true.

Proof by Contrapositive

Proof technique to show P ⇒ Q: Assume ~Q, conclude ~P

Proof by Contradiction

Proof technique to show P ⇒ Q: Rule out that P is true & Q is false: reach an absurdity

Even integer

An integer that can be written as n=2k for some integer k.

Odd integer

An integer that can be written as n=2k+1 for some integer k.

Parity Proof

A proof dealing with even or odd integers

A divides B

A | B if and only if there exists an integer k such that b = a * k

Induction

Let P(1), P(2), P(3), … be an infinite list of statements. Suppose that:
1. P(1) is true.
2. For each natural number n, if P(n) is true, then so is P(n+1).
Then P(n) is true for every natural number n.

Complete Induction

Let P(1), P(2), P(3), … be an infinite list of statements. Suppose that:
1. P(1) is true.
2. For each natural number n, if all of P(1), P(2), …, P(n) are true, then so is P(n+1).
Then P(n) is true for every natural number n.