Proof Strategies

Question 1

How do you prove P → Q?

Answer 1

Assume P is true and then prove Q

or

Assume Q is false and prove that P is false

Question 2

How would you go about solving ¬P?

Answer 2

If possible, reexpress the goal in some other form and then use one of the
proof strategies for this other goal form

or

If you’re doing a proof by contradiction, try making P your goal. If
you can prove P, then the proof will be complete, because P contradicts the
given ¬P

Question 3

What does modus ponens state?

Answer 3

p→q
p
∴ q

Question 4

What does modus tollens state?

Answer 4

¬q
p→q
∴ ¬p

Question 5

How would you prove ∀xP(x)?

Answer 5

Let x stand for an arbitrary object and prove P(x). The letter x must be a
new variable in the proof. If x is already being used in the proof to stand for
something, then you must choose an unused variable, say y, to stand for the
arbitrary object, and prove P(y).