Notes from “How to Prove it: A Structured Approach” by

Daniel J. Velleman

§ DeMorgan’s laws:

? ¬(P ∧ Q) is equivalent to ¬P ∨ ¬Q)

? ¬(P ∨ Q) is equivalent to ¬P ∧ ¬Q)

§ Commutative laws:

? (P ∧ Q) is equivalent to (Q ∧ P )
? (P ∨ Q) is equivalent to (Q ∨ P )

§ Associative laws:

? P ∧ (Q ∧ R) is equivalent to (P ∧ Q) ∧ R
? P ∨ (Q ∨ R) is equivalent to (P ∨ Q) ∨ R

§ Idempotent laws:

? (P ∧ P ) is equivalent to P
? (P ∨ P ) is equivalent to P

§ Distributive laws:

? P ∨ (Q ∧ R) is equivalent to (P ∨ Q) ∧ (P ∨ R)
? P ∧ (Q ∨ R) is equivalent to (P ∧ Q) ∨ (P ∧ R)

§ Absorption laws:

? P ∨ (P ∧ Q) is equivalent to P
? P ∧ (P ∨ Q) is equivalent to P

1
§ Double Negation law: ¬¬P is equivalent to P

§ Conditional laws:

? P ⇒ Q and ¬P ∨ Q are equivalent

? P ⇒ Q and ¬(P ∧ ¬Q) are equivalent

§ Quantifier Negation Laws:

? ¬∀xP (x) is equivalent to ∃x¬P (x)

? ¬∃xP (x) is equivalent to ∀x¬P (x)

§ Contrapositive Law: P ⇒ Q is equivlaent to ¬Q ⇒ ¬P

§ Here are a few other ways of expressing the idea P ⇒ Q that are used often in mathematics:
P implies Q. Q, if P . P only if Q. P is a sufficient condition for Q. Q is a necessary
condition for P

§ You can think of P ⇐⇒ Q as just an abbreviation for the formula (P ⇒ Q) ∧ (Q ⇒ P )

A statement of the form P ⇐⇒ Q is called a biconditional statement, because it represents
two conditional statements. P ⇐⇒ Q is usually written “P iff Q.” Another statement
that means P ⇐⇒ Q is “P is a necessary and sufficient condition for Q.”

§ A variable that is bound by a quantifier can always be replaced with a new variable without
changing the meaning of the statement, and it is often possible to paraphrase the statement
without mentioning the bound variable at all. For example, the statement ∀xL(x, y) is
equivalent to ∀wL(w, y), because both mean the same thing as “Everyone likes y.”

§ We will write ∃!xP (x) to represent the statement “There is exactly one value of x such
that P (x) is true.”

§ We can look at ∃!xP (x) as an abbreviation for the formula ∃x(P (x) ∧ ¬∃y(P (y) ∧ y 6= x)).

§ ∀x ∈ AP (x) is always true if A = φ. Mathematicians sometimes say that such a statement

is vacuously true.

§ ∀x(E(x) ∧ T (x)) is equivalent to ∀xE(x) ∧ ∀xT (x). In other words, we could say that the
universal quantifier distributes over conjunction. However, the corresponding distributive
law doesn’t work for the existential quantifier. The expressions ∃x(E(x) ∧ T (x)) and
∃xE(x) ∧ ∃xT (x) are not equivalent.

2
§ Suppose A is a set. The power set of A, denoted ℘(A), is the set whose elements are all
the subsets of A. In other words, for any sets A and B, ℘(A ∩ B) = ℘(A) ∩ ℘(B)

§ To prove a conclusion of the form P ⇒ Q: Assume P is true and then prove Q.

Form of final proof
Suppose P .
[Proof of Q goes here.]
Therefore P ⇒ Q.

This technique says that if the conclusion of the theorem you are trying to prove has the
form P ⇒ Q, then you can transform the problem by adding P to your list of hypotheses
and changing your conclusion from P ⇒ Q to Q. This gives you a new, perhaps easier
proof problem to work on. If you can solve the new problem, then you will have shown
that if P is true then Q is also true, thus solving the original problem of proving P ⇒ Q.

§ There is a second method that is sometimes used for proving goals of the form P ⇒ Q.
Because any conditional statement P ⇒ Q is equivalent to its contrapositive ¬Q ⇒ ¬P ,
you can prove P ⇒ Q by proving ¬Q ⇒ ¬P instead, using the strategy discussed earlier.

To prove a goal of the form P ⇒ Q: Assume Q is false and prove that P is false.
Form of final proof
Suppose Q is false.
[Proof of ¬P goes here.]
Therefore P ⇒ Q

§ Usually it’s easier to prove a positive than a negative statement, so it is often helpful to
re-express a goal of the form ¬P before proving it. Instead of using a goal that says what
shouldn’t be true, see if you can rephrase it as a goal that says what should be true.
To prove a goal of the form ¬P : If possible, re-express the goal in some other form
and then use one of the proof strategies for this other goal form.

§ Sometimes a goal of the form ¬P cannot be re-expressed as a positive statement, and

therefore this strategy cannot be used.
To prove a goal of the form ¬P : Assume P is true and try to reach a contradic-
tion. Once you have reached a contradiction, you can conclude that P must be false
Form of final proof
Suppose P is true.

3
 [Proof of contradiction goes here.]
Thus, P is false.

§ To use a given of the form ¬P : 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 .

§ To use a given of the form P ⇒ Q: If you are also given P , or if you can prove that
P is true, then you can use this given to conclude that Q is true. Since it is equivalent to
¬Q ⇒ ¬P , if you can prove that Q is false, you can use this given to conclude that P is
false. The first of these rules of inference says that if you know that both P and P ⇒ Q
are true, you can conclude that Q must also be true. Logicians call this rule modus ponens.
The second rule, called modus tollens, says that if you know that P ⇒ Q is true and Q is
false, you can conclude that P must also be false.

§ To prove a goal of the form ∀xP (x): 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).
Form of final proof
Let x be arbitrary.
[Proof of P(x) goes here.]
Since x was arbitrary, we can conclude that ∀xP (x).

§ To prove a goal of the form ∃xP (x): Try to find a value of x for which you think P (x)
will be true. Then start your proof with “Let x = (the value you decided on)” and proceed
to prove P (x) for this value of x. Once again, x should be a new variable. If the letter x is
already being used in the proof for some other purpose, then you should choose an unused
variable, say y, and rewrite the goal in the equivalent form ∃yP (y). Now proceed as before
by starting your proof with “Let y = (the value you decided on)” and prove P (y).
Form of final proof
Let x = (the value you decided on).
[Proof of P (x) goes here.]
Thus, ∃xP (x)

§ To use a given of the form ∃xP (x): Introduce a new variable x0 into the proof to stand
for an object for which P (x0 ) is true. This means that you can now assume that P (x0 ) is
true. Logicians call this rule of inference existential instantiation.

4
§ To use a given of the form ∀xP (x): You can plug in any value, say a, for x and use
this given to conclude that P (a) is true. This rule is called universal instantiation.

§ To prove a goal of the form P ∧ Q: Prove P and Q separately. In other words, a goal
of the form P ∧ Q is treated as two separate goals: P , and Q.

§ To use a given of the form P ∧ Q: Treat this given as two separate givens: P , and Q.

§ To prove a goal of the form P ⇐⇒ Q: Prove P ⇒ Q and Q ⇒ P separately.

§ To use a given of the form P ⇐⇒ Q: Treat this as two separate givens: P ⇒ Q, and
Q ⇒ P.

§ Any proof can be broken into two or more cases at any time, as long as the cases are
exhaustive. Note that cases need not be exclusive. The cases in a proof by cases must
cover all possibilities, but there is no harm in covering some possibilities more than once.
In other words, the cases must be exhaustive, but they need not be exclusive.
To use a given of the form P ∨ Q: Break your proof into cases. For case 1, assume
that P is true and use this assumption to prove the goal. For case 2, assume Q is true and
give another proof of the goal.
Form of final proof
Case 1. P is true.
[Proof of goal goes here.]
Case 2. Q is true.
[Proof of goal goes here.]
Since we know P ∨ Q, these cases cover all the possibilities. Therefore
the goal must be true.

§ To prove a goal of the form P ∨ Q: If P is true, then clearly the goal P ∨ Q is true,
so you only need to worry about the case in which P is false. You can complete the proof
in this case by proving that Q is true.
Form of final proof
If P is true, then of course P ∨ Q is true. Now suppose P is false.
[Proof of Q goes here.]
Thus, P ∨ Q is true.
Thus, this strategy for proving P ∨ Q suggests that you transform the problem by adding
¬P as a new given and changing the goal to Q. It is interesting to note that this is exactly
the same as the transformation you would use if you were proving the goal ¬P ⇒ Q! This

5
 is not really surprising, because we already know that the statements P ∨ Q and ¬P ⇒ Q
are equivalent. Of course, the roles of P and Q could be reversed in using this strategy.
Thus, you can also prove P ∨ Q by assuming that Q is false and proving P .

§ To use a given of the form P ∨ Q: If you are also given ¬P , or you can prove that P
is false, then you can use this given to conclude that Q is true. Similarly, if you are given
¬Q or can prove that Q is false, then you can conclude that P is true.

§ In this section we consider proofs in which the goal has the form ∃!xP (x). ∃!xP (x) could
also be written as ∃x(P (x) ∧ ∀y(P (y) ⇒ y = x)).
To prove a goal of the form ∃!xP (x): Prove ∃xP (x) and ∀y∀z((P (y)∧P (z)) ⇒ y = z).
The first of these goals shows that there exists an x such that P (x) is true, and the second
shows that it is unique. The two parts of the proof are therefore sometimes labeled existence
and uniqueness. Each part is proven using strategies discussed earlier.
Form of final proof :
Existence:
[Proof of ∃xP (x) goes here.]
Uniqueness:
[Proof of ∀y∀z((P (y) ∧ P (z)) ⇒ y = z) goes here.]

§ To use a given of the form ∃!xP (x): Treat this as two given statements, ∃xP (x) and
∀y∀z((P (y) ∧ P (z)) ⇒ y = z). To use the first statement you should probably choose a
name, say x0 , to stand for some object such that P (x0 ) is true. The second tells you that
if you ever come across two objects y and z such that P (y) and P (z) are both true, you
can conclude that y = z.

§ To prove a goal of the form ∀nP (n): First prove P (0), and then prove ∀n(P (n) ⇒
P (n + 1)). The first of these proofs is sometimes called the base case and the second the
induction step.
Form of the final proof
Base case:
[Proof of P (0) goes here.]
Induction step:
[Proof of ∀n(P (n) ⇒ P (n + 1)) goes here.]
The assumption that P (n) is true is sometimes called the inductive hypothesis, and the
key to the proof is usually to work out some relationship between the inductive hypothesis
P (n) and the goal P (n + 1)

6
§ In the induction step of a proof by mathematical induction, we prove that a natural
number has some property based on the assumption that the previous number has the
same property. In some cases this assumption isn’t strong enough to make the proof work,
and we need to assume that all smaller natural numbers have the property. This is the
idea behind a variant of mathematical induction sometimes called strong induction
To prove a goal of the form ∀nP (n): Prove that ∀n[(∀k < nP (k)) ⇒ P (n)], where
both n and k range over the natural numbers in this statement. Of course, the most direct
way to prove this is to let n be an arbitrary natural number, assume that ∀k < nP (k),
and then prove P (n).

§ Note that no base case is necessary in a proof by strong induction. All that is needed is a
modified form of the induction step in which we prove that if every natural number smaller
than n has the property P , then n has the property P . In a proof by strong induction, we
refer to the assumption that every natural number smaller than n has the property P as
the inductive hypothesis.
Suppose that we’ve followed the strong induction proof strategy and proven the statement
∀n[(∀k < nP (k)) ⇒ P (n)]. Then, plugging in 0 for n, we can conclude that (∀k <
0P (k)) ⇒ P (0). But because there are no natural numbers smaller than 0, the statement
∀k < 0P (k) is vacuously true. Therefore, by modus ponens, P (0) is true. (This explains
why the base case doesn’t have to be checked separately in a proof by strong induction;
the base case P (0) actually follows from the modified form of the induction step used in
strong induction.)
For example when we are solving the Fibonacci sequence problem using induction, we need
to know that the formula works for two previous cases, we must use strong induction rather
than ordinary induction.