Discrete Mathematics for CS

Informal proofs

[Link] Rahmani
cenghabib@[Link]
Kandahar University

Discrete mathematics for CS [Link]

Proofs
• The truth value of some statements about the world are obvious
and easy to assess
• The truth of other statements may not be obvious, …
…. But it may still follow (be derived) from known facts about
the world

Proof: shows that the truth value of such a statement follows from
(or can be inferred) from the truth value of other statements

Important questions:
– When is the argument correct?
– How to construct a correct argument, what method to use?

Discrete mathematics for CS [Link]

1
 Theorems
• Theorem: a statement that can be shown to be true.
– Typically the theorem looks like this:
(p1  p2  p3  … pn )  q

Premises conclusion

• Example:
Premises (hypotheses)
Fermat’s Little theorem:
– If p is a prime and a is an integer not divisible by p,
then: a p1 1mod p
conclusion

Discrete mathematics for CS [Link]

Formal proofs
Allow us to infer from new True statements from known True
statements

premises
conclusion
+
axioms
+
proved
theorems

True ?
True
Discrete mathematics for CS [Link]

2
 Formal proofs

premises
conclusion
+
axioms
+
proved
theorems
True ?
True
Steps of the proof for statements in the propositional logic are
argued using:
• Equivalence rules
• Rules of inference (e.g. modus ponens)
Discrete mathematics for CS [Link]

Proofs using rules of inference

Translations:
• Assumptions: ¬ p  q, r  p, ¬ r  s, s t
• We want to show: t
Proof:
• 1. ¬ p  q Hypothesis
• 2. ¬ p Simplification
• 3. r  p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r  s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
Discrete mathematics for CS [Link]

3
 Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question

• We use (informal) proofs to illustrate different methods of

proving theorems

Discrete mathematics for CS [Link]

Methods of proving theorems

Basic methods to prove the theorems:
• Direct proof
– p  q is proved by showing that if p is true then q follows
• Indirect proof
– Show the contrapositive ¬q  ¬p. If ¬q holds then ¬p follows
• Proof by contradiction
– Show that (p  ¬ q) contradicts the assumptions
• Proof by cases
• Proofs of equivalence
– p  q is replaced with (p  q)  (q  p)

Sometimes one method of proof does not go through as nicely as the

other method. You may need to try more than one approach.
[Link]
Discrete mathematics for CS

4
 Direct proof
• p  q is proved by showing that if p is true then q follows

• Example: Prove that “If n is odd, then n2 is odd.”

Proof:
• Assume the hypothesis is true, i.e. suppose n is odd.
• Then n = 2k + 1, where k is an integer.
n2 = (2k + 1)2
= 4k2 + 4k + 1
= 2(2k2 + 2k) + 1
• Therefore, n2 is odd.

Discrete mathematics for CS [Link]

Indirect proof
• To show p  q prove its contrapositive ¬q  ¬p
• Why? p  q and ¬q  ¬p are equivalent !!!
• Assume ¬q is true, show that ¬p is true.

Example: Prove If 3n + 2 is odd then n is odd.

Proof:
• Assume n is even, that is n = 2k, where k is an integer.
• Then: 3n + 2 = 3(2k) + 2
= 6k + 2
= 2(3k+1)
• Therefore 3n + 2 is even.
• We proved ¬ “n is odd”  ¬ “3n + 2 is odd”. This is
equivalent to “3n + 2 is odd”  “n is odd”.

Discrete mathematics for CS [Link]

5
 Proof by contradiction
• We want to prove p  q
• The only way to reject (or disprove) p  q is to show that (p 
¬q ) can be true

• However, if we manage to prove that either q or ¬ p is True

then we contradict (p  ¬q )
– and subsequently p  q must be true

• Proof by contradiction. Show that the assumption (p  ¬q )

leads either to q or ¬ p which generates a contradiction.

Discrete mathematics for CS [Link]

Proof by contradiction
• We want to prove p  q
• To reject p  q show that (p  ¬q ) can be true
• To reject (p  ¬q ) show that either q or ¬ p is True

Example: Prove If 3n + 2 is odd then n is odd.

Proof:
• Assume 3n + 2 is odd and n is even, that is n = 2k, where k an
integer.

Discrete mathematics for CS [Link]

6
 Proof by contradiction
• We want to prove p  q
• To reject p  q show that (p  ¬q ) can be true
• To reject (p  ¬q ) show that either q or ¬ p is True

Example: Prove If 3n + 2 is odd then n is odd.

Proof:
• Assume 3n + 2 is odd and n is even, that is n = 2k, where k an
integer.
• Then: 3n + 2 = 3(2k) + 2
= 6k + 2
= 2(3k + 1)
• Thus 3n + 2 is even. This is a contradiction with the assumption
that 3n + 2 is odd. Therefore n is odd.

Discrete mathematics for CS [Link]

Vacuous proof
We want to show p  q
• Suppose p (the hypothesis) is always false
• Then p  q is always true.
Reason:
• F  q is always T, whether q is True or False

Example:
• Let P(n) denotes “if n > 1 then n2> n” is TRUE.
• Show that P(0).
Proof:
• For n=0 the premise is False. Thus P(0) is always true.

[Link]
Discrete mathematics for CS

7
 Trivial proofs
We want to show p  q
• Suppose the conclusion q is always true
• Then the implication p  q is trivially true.
• Reason:
• p T is always T, whether p is True or False

Example:
• Let P(n) is “if a >=b then an >= bn”
• Show that P(0)
Proof:
a0 >=b0 is 1=1 trivially true.

[Link]
Discrete mathematics for CS

Proof by cases
• We want to show p1  p2  …  pn  q
• Note that this is equivalent to
– (p1  q)  (p2  q)  …  (pn  q)
• Why?
• p1  p2  …  pn  q <=> (useful)
• ¬ (p1  p2  …  pn)  q <=> (De Morgan)
• (¬p1  ¬p2  …  ¬pn)  q <=> (distributive)
• (¬p1  q)  (¬p2  q)  … (¬pn  q) <=> (useful)
• (p1  q)  (p2  q)  …  (pn  q)

Discrete mathematics for CS [Link]

8
 Proof by cases
We want to show p1  p2  …  pn  q
• Equivalent to (p1  q)  (p2  q)  …  (pn  q)
Prove individual cases as before. All of them must be true.

Example: Show that |x||y|=|xy|.

Proof:
• 4 cases:
• x >=0, y>=0
• x>= 0, y <0
• x<0, y>=0 |
• x<0, , y <0 |

Discrete mathematics for CS [Link]

Proof by cases
We want to show p1  p2  …  pn  q
• Equivalent to (p1  q)  (p2  q)  …  (pn  q)
Prove individual cases as before. All of them must be true.

Example: Show that |x||y|=|xy|.

Proof:
• 4 cases:
• x >=0, y>=0 xy >0 and |xy|=xy=|x||y|
• x>= 0, y <0 xy < 0 and |xy|=-xy =x (-y)=|x||y|
• x<0, y>=0 xy < 0 and |xy|=-xy =(-x) y=|x||y|
• x<0, , y <0 xy >0 and |xy|= (-x)(-y) =|x||y|
• All cases proved.
Discrete mathematics for CS [Link]

9
 Proof of equivalences
We want to prove p  q
• Statements: p if and only if q.
• Note that p  q is equivalent to [ (p  q )  (q  p) ]
• Both implications must hold.

Example:
• Integer is odd if and only if n^2 is odd.
Proof of (p  q ) :
• (p  q ) If n is odd then n^2 is odd
• we use a direct proof
• Suppose n is odd. Then n = 2k + 1,where k is an integer.
• n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1
• Therefore, n^2 is odd.

Discrete mathematics for CS [Link]

Proof of equivalences
We want to prove p  q
• Note that p  q is equivalent to [ (p  q )  (q  p) ]
• Both implications must hold.

• Integer is odd if and only if n^2 is odd.

Proof of (q  p):
• (q  p): if n^2 is odd then n is odd
• we use an indirect proof (¬p  ¬q) is a contrapositive
• n is even that is n = 2k,
• then n^2 = 4k^2= 2(2k^2)
• Therefore n^2 is even. Done proving the contrapositive.
Since both (p  q) and (q  p) are true the equivalence is true
Discrete mathematics for CS [Link]

10
 Proofs with quantifiers
• Existence proof – sentences expressed with an existential
quantifiers

– Constructive
• Find an example (through search) that shows the
statement holds.
– Nonconstructive
• Show the statement holds for one example but we do not
have the witness example. Typically relies on the proof by
contradiction – negate the existentially quantified
statement and show that it implies a contradiction.

Discrete mathematics for CS [Link]

Proofs with quantifiers

• Universally quantified statements

– Prove the property holds for all examples

– can be tricky
– proof by cases to divides the proof to the different
subgroups may help

– Counterexamples:
• use to disprove universal statements
• Similar to constructive proofs for existentially

[Link]
Discrete mathematics for CS

11