Proof

Question 1

NOT P

Answer 1

¬ P

Question 2

P AND Q

Answer 2

P ∧ Q

Question 3

If P then Q

Answer 3

P ⟹ Q

Question 4

P if and only if Q

Answer 4

P ⟺ Q

Question 5

NOT (P AND Q)

Answer 5

¬ P ∨ ¬Q
(NOT P) OR (NOT Q)

Question 6

Direct proof steps

Answer 6

1. Write down assumptions and known facts
2. Create a logical chain of argument
3. Deduce the statement to be proven

Question 7

Proof by cases

Answer 7

Breaking down the statement into cases and proving them each on their own

Question 8

Proof by contradiction steps

Answer 8

1. Assume the negation of the statement (¬P) is true
2. Use logical deductions to show it leads to a contradiction and conclude that the original statement (P) is true

Question 9

Proof by induction steps

Answer 9

1. Base case - irst check the base case: P(n) is true
   The smallest possible n is usually 0 or 1 unless stated otherwise
2. Inductive Hypothesis - assume P(k) is true for some k such that k ∈ N
3. Inductive Step - show if the statement is true for n = k then it must be true for n = k + 1
4. Conclusion - conclude the statement holds for all n (since base case and inductive step work)

Question 10

Proof by construction

Answer 10

1. Create an object or example that satisfies the given statement
2. Show that the object or example meets the required conditions
3. Conclude that the statement is true by virtue of the constructed object or example

Question 11

When to use direct proof

Answer 11

Claims in the form “if (some claim A is true), then (some other claim B is true)”.

Question 12

When to use case proof

Answer 12

Claims with modular arithmetic, even versus odd numbers, claims about “is a multiple of”, or absolute values.

Question 13

When to use construction

Answer 13

Claims in the form “Show that blah exists?”

Question 14

When to use induction

Answer 14

Claims where it seems like your previous results stick together to give you a later result.

Question 15

When to use contradiction

Answer 15

Anything else :’)