Discrete Structures

(BIT 152)

Unit 1: Logic and Proof Methods (6 Hrs)

Unit 1.2: Proof Methods

Prepared By: Manila Tiwari

Discrete Structures: BIT 2nd Sem
 • Basic Terminologies of
Proof Methods
Unit 1.2 • Proof Methods (Direct
Proof, Indirect Proof,
Contents Proof by Contradiction,
Proof By Contraposition,
Exhaustive Proofs and
Proof by Cases),
• Mistakes in Proof

Prepared By: Manila Tiwari

Discrete Structures: BIT 2nd Sem 2
Introduction to Proofs

3
Section Summary
• Mathematical Proofs
• Forms of Theorems
• Direct Proofs
• Indirect Proofs
• Proof of the Contrapositive
• Proof by Contradiction

Prepared By: Manila Tiwari

Discrete Structures: BIT 2nd Sem 4
Proofs of Mathematical Statements
Before learning proof techniques, it is important to understand some basic terms.
Proof
• A proof is a logical argument that demonstrates a statement is always true using
accepted facts, definitions, axioms, and previously proven theorems.
• Example: Prove that the sum of two even integers is even.
Theorem
• A theorem is a mathematical statement that has been proven to be true.
• Example: If a and b are even integers, then a+b is even.

Proposition
• A proposition is a declarative statement that is either true or false.
• Examples:
• 5 is an odd number. (True)
• 8 is a prime number. (False)
Prepared By: Manila Tiwari 5
Discrete Structures: BIT 2nd Sem
 Proofs of Mathematical Statements
• A proof is a valid argument that establishes the truth of a statement.
• In math, CS, and other disciplines, informal proofs which are generally
shorter, are generally used.
• More than one rule of inference are often used in a step.
• Steps may be skipped.
• The rules of inference used are not explicitly stated.
• Easier for to understand and to explain to people.
• But it is also easier to introduce errors.
• Proofs have many practical applications:
• verification that computer programs are correct
• establishing that operating systems are secure
• enabling programs to make inferences in artificial intelligence
• showing that system specifications are consistent

Prepared By: Manila Tiwari 6

Discrete Structures: BIT 2nd Sem
Definitions
• A theorem is a statement that can be shown to be true using:
• definitions
• other theorems
• axioms (statements which are given as true)
• rules of inference
1. Theorem
A theorem is a statement that can be proved true using definitions, axioms, rules of
inference, and previously proved theorems.
Example: The sum of two even integers is even.
2. Lemma
A lemma is a helping theorem used to prove another theorem.
Example: If a and b are even integers, then a+b is even.
(This lemma can be used to prove more complex theorems about even numbers.)
Prepared By: Manila Tiwari 7
Discrete Structures: BIT 2nd Sem
Definitions
3. Corollary
A corollary is a result that follows directly from a theorem.
Example:
Theorem: The sum of two even integers is even.
Corollary: The sum of four even integers is also even.
4. Proposition
A proposition is a theorem that is considered less important.
Example: The square of an odd integer is odd.
5. Conjecture
A conjecture is a statement believed to be true but not yet proved.
Example:
Goldbach's Conjecture: Every even integer greater than 2 can be expressed as the
sum of two prime numbers.
(This has not yet been proved for all even integers.)
Prepared By: Manila Tiwari 8
Discrete Structures: BIT 2nd Sem
Definitions
6. Axiom (Postulate)
An axiom is a statement accepted as true without proof.
Example:
For any real number a,
• a+0=a + 0 =a

Another example:
• a=a (Every object is equal to itself.)

Prepared By: Manila Tiwari 9

Discrete Structures: BIT 2nd Sem
Proving Theorems
• Many theorems have the form:

• To prove them, we show that where c is an arbitrary element of the

domain,
• By universal generalization the truth of the original formula follows.
• So, we must prove something of the form:

Prepared By: Manila Tiwari 10

Discrete Structures: BIT 2nd Sem
Even and Odd Integers
Definition: The integer n is even if there exists an integer k such that
n = 2k, and n is odd if there exists an integer k, such that n = 2k + 1.
Note that every integer is either even or odd and no integer is both
even and odd.

Prepared By: Manila Tiwari 11

Discrete Structures: BIT 2nd Sem
Proof Methods
• A mathematical proof can be constructed using different methods.

A. Direct Proof
• A direct proof begins with the given assumptions and logically derives the
conclusion.
• Assume that p is true. Use rules of inference, axioms, and logical equivalences to
show that q must also be true.
• Used mainly for proving statements of the form
P→Q
Steps
• Assume P is true.
• Use definitions and known facts.
• Show that Q must be true. Prepared By: Manila Tiwari
nd
Discrete Structures: BIT 2 Sem
12
Example
Prove: If n is even, then n2 is even.
Proof
• Assume n is even.
• Then
n=2k for some integer k.
• Now,
n2 = (2k)2 =4 k2 =2(2 k2)
• Since 2k2 is an integer,
• n2 is divisible by 2.
Therefore, n2 is even.
Hence proved.
Prepared By: Manila Tiwari 13
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 14
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 15
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 16
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 17
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 18
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 19
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 20
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 21
Discrete Structures: BIT 2nd Sem
Exercise: Give a direct proof of the theorem “If n is an odd
integer, then n2 is odd.”
Solution: Assume that n is odd. Then n = 2k + 1 for an
integer k. Squaring both sides of the equation, we get:
n2 = (2k + 1)2 = 4k2 + 4k +1 = 2(2k2 + 2k) + 1= 2r +
1,
where r = 2k2 + 2k , an integer.
We have proved that if n is an odd integer, then n2 is an
odd integer.

Prepared By: Manila Tiwari 22

Discrete Structures: BIT 2nd Sem
 Definition: The real number r is rational if there exist integers
p and q where q≠0 such that r = p/q
Exercise: Prove that the sum of two rational numbers is
rational.
Solution: Assume r and s are two rational numbers. Then there
must be integers p, q and also t, u such that

where v = pu + qt
w = qu ≠ 0

Thus the sum is rational.

Prepared By: Manila Tiwari 23
Discrete Structures: BIT 2nd Sem
Proof Methods
B. Indirect Proof
• Direct proof begin with the premises, continue with a sequence
of deductions and end with the conclusion.
• Indirect proof proves a statement without proving it directly.
• Proofs that do not start with the premises and end with the
conclusion are called indirect proofs.
• There are two major types:
1. Proof by Contraposition
2. Proof by Contradiction
Prepared By: Manila Tiwari 24
Discrete Structures: BIT 2nd Sem
1. Proof by Contraposition
• A proof by contraposition is based on the logical equivalences between a
statement and its contrapositive. Therefore, the implication P→Q can be
proved by showing that its contrapositive ¬Q→¬P is true. The
contrapositive is usually proved directly.
The methods of proof by contrapositive may be summarized as:
1. Express the statement in the form if p then q.
2. Rewrite this statement in the contrapositive form if not q then not
p.
3. Prove the contrapositive by a direct proof.

Prepared By: Manila Tiwari 25

Discrete Structures: BIT 2nd Sem
Prove:
If n2 is even, then n is even.
Solution: Instead prove the contrapositive: If n is odd, then n2 is odd.
Assume
n=2k+1 for some integer k
Then
n2 = (2k+1)2 =4 k2 +4k+1 =2(2k2 +2k) +1 which is odd.
Therefore,
If n is odd, n2 is odd.
• Hence,
If n2 is even, then n is even.

Prepared By: Manila Tiwari 26

Discrete Structures: BIT 2nd Sem
• Proof by Contraposition: Assume ¬q and show ¬p is true also. This is sometimes
called an indirect proof method. If we give a direct proof of ¬q → ¬p then we have a
proof of p → q.
Why does this work?
Example: Prove that if n is an integer and 3n + 2 is odd, then n is odd.
Solution: Assume n is even.
So, n = 2k for some integer k.
Thus
3n + 2 = 3(2k) + 2
=6k +2
=2(3k + 1)
= 2j for j = 3k +1
Therefore 3n + 2 is even. Since we have shown ¬q → ¬p , p → q must
hold as well. If n is an integer and 3nBy:+Manila
Prepared 2 Tiwari
is odd, then n is odd . 27
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 28
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 29
Discrete Structures: BIT 2nd Sem
 Example: Prove that for an integer n, if n2 is odd, then n is
odd.
Solution: Use proof by contraposition. Assume n is even (i.e.,
not odd).
Therefore, there exists an integer k such that n = 2k. Hence,
n2 = 4k2 = 2 (2k2)
and n2 is even(i.e., not odd).
We have shown that if n is an even integer, then n2 is even.

Therefore by contraposition, for an integer n, if n2 is odd, then n

is odd.
Prepared By: Manila Tiwari 30
Discrete Structures: BIT 2nd Sem
2. Proof by Contradiction

Prepared By: Manila Tiwari 31

Discrete Structures: BIT 2nd Sem
Proof by Contradiction(contd…..)
• To prove statement P:
• Assume P is false.
• Show this assumption leads to a contradiction.
• Therefore, the original statement must be true.
General Form
• To prove P:
• Assume
¬P
• Obtain contradiction
False
• Hence, P is true. Prepared By: Manila Tiwari 32
Discrete Structures: BIT 2nd Sem
2. Proof by Contradiction (contd…..)

Prepared By: Manila Tiwari

Prepared
Discrete By: Manila
Structures: [Link] 2nd Sem
Tiwari 33
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari
Prepared
Discrete By: Manila
Structures: [Link] 2nd Sem
Tiwari 34
Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 35
Discrete Structures: BIT 2nd Sem
 PreparedBy:
Prepared By:Manila
ManilaTiwari
Tiwari
36
Discrete Structures: [Link] 2nd Sem
Discrete Structures: BIT 2nd Sem
To prove p, assume ¬p and derive a contradiction such as p ∧ ¬p. (an
indirect form of proof).
Since we have shown that ¬p →F is true , it follows that the contrapositive
T→p also holds.

Example: Prove that if you pick 22 days from the calendar, at least 4 must
fall on the same day of the week.

Solution: Assume that no more than 3 of the 22 days fall on the same day
of the week. Because there are 7 days of the week, we could only have
picked 21 days. This contradicts the assumption that we have picked 22
days.

Prepared By: Manila Tiwari 37

Discrete Structures: BIT 2nd Sem
Example: Use a proof by contradiction to give a proof that √2 is irrational.
Solution: Suppose √2 is rational. Then there exists integers a and b with √2 = a/b,
where b≠ 0 and a and b have no common factors .
Then

Therefore a2 must be even. If a2 is even then a must be even. Since a is even, a = 2c

for some integer c. Thus,

Therefore b2 is even. Again then b must be even as well.

But then 2 must divide both a and b. This contradicts our assumption that a and b have
no common factors. We have proved by contradiction that our initial assumption must
be false and therefore √2 is irrational .

Prepared By: Manila Tiwari 38

Discrete Structures: BIT 2nd Sem
Proof by Counter Example

Disprove the statement by giving a counter example. For all

real numbers a and b, if a<b then a2 < b2 .
Solution:
Suppose a= -5 and b =-2
Then clearly -5 < -2
But a2 = (-5)2 = 25 and b2 = (-2)2 = 4
But 25 > 4
This disproves the given Discrete
statement.
Prepared By: Manila Tiwari
nd
Structures: BIT 2 Sem
39
 Prepared By: Manila Tiwari 40
Discrete Structures: BIT 2nd Sem
Mistakes in Proof

“Proof” that 1 = 2

Solution: Step 5. a - b = 0 by the premise and division

Prepared byTiwari
By: Manila 0 is undefined.
41
Every step is valid except step 5, where we divided
Discrete both
Structures: BIT sides
2nd Sem by a-b . The error is that it equals to zero.
Mistakes in Proof

Prepared By: Manila Tiwari

Discrete Structures: BIT 2nd Sem 42
Proof Methods and Strategy

43
Proof by Cases
• Divide the problem into several cases.
• If the conclusion is true in every case, then the statement is
true.

Steps
• Divide into cases.
• Prove each case separately.
• Conclude the theorem.
Prepared By: Manila Tiwari
Discrete Structures: BIT 2nd Sem
Proof by Cases
• To prove a conditional statement of the form:

• Use the tautology

• Each of the implications is a case.

Prepared By: Manila Tiwari 45

Discrete Structures: BIT 2nd Sem
Proof that if n is an integer, then n2 ≥ n .
Case 1: n = -1
-12 ≥ -1
1 ≥ -1
Case 2: n = 0
02 ≥ 0
0≥0
Case 3: n = 1
12 ≥ 1
1≥1

Prepared By: Manila Tiwari 46

Discrete Structures: BIT 2nd Sem
Proof that if n is an integer, then n2 +3n+4 is even .
Case 1: n is odd, i.e. n = 2k+1
Given, n2 +3n+4
= (2k+1)2 +3(2k+1)+4
= 4k2+10k+12
= 2(2k2+5k+6)
= 2m (even)
Case 2: n is odd, i.e. n = 2k
Given, n2 +3n+4
= (2k)2 +3(2k)+4
= 4k2+6k+4
= 2(2k2+3k+2)
= 2m (even)
Prepared By: Manila Tiwari 47
Hence, Proved. Discrete Structures: BIT 2nd Sem
Exhaustive Proof (Proof by Exhaustion)

If there are only a finite number of possible cases, check every case
individually.
1. Proof that (n+1) 3 ≥ 3n if n is a positive integer with n 4.
Case 1: n = 1 Case 3: n = 3
(1+1)3 ≥ 31 (3+1)3 ≥ 33
(2)3 ≥ 3 (4)3 ≥ 33
Case 2: n = 2
(2+1)3 ≥ 32 Prepared By: Manila Tiwari
(3)3 ≥ 32 Discrete Structures: BIT 2nd Sem
48
Example
Prove that n2 ≥n for n=0,1,2
Check each value.
• For n=0
0 2 =0 True
• For n=1
12 =1 True
• For n=2
2 2 =4≥2 True

Since all cases are true, the statement is true.

Prepared By: Manila Tiwari 49
Discrete Structures: BIT 2nd Sem
Without Loss of Generality
• Sometimes two or more cases are symmetric or arbitrary naming of
variables, meaning they are essentially the same.
• Instead of proving every symmetric case separately, we prove one case
and say:
• Without loss of generality (WLOG); This means the omitted cases
can be proved in exactly the same way.

Show that for integers a and b of opposite parity then a+b is odd.
(one is even and one is odd) Show for all x, y R
Case 1:
a is even and b is odd.
Case 2:
Prepared By: Manila Tiwari 50
b is even and a is odd. Discrete Structures: BIT 2nd Sem
Without Loss of Generality
Example: Show that if x and y are integers and both x∙y and x+y are even, then
both x and y are even.
Proof: Use a proof by contraposition. Suppose x and y are not both even. Then,
one or both are odd. Without loss of generality, assume that x is odd. Then x = 2m
+ 1 for some integer m.
Case 1: y is even. Then y = 2n for some integer n, so
x + y = (2m + 1) + 2n = 2(m + n) + 1 is odd.
Case 2: y is odd. Then y = 2n + 1 for some integer n, so
x ∙ y = (2m + 1) (2n + 1) = 2(2m ∙ n +m + n) + 1 is odd.

We only cover the case where x is odd because the case where y is odd is similar.
The use phrase without loss of generality (WLOG) indicates this.
Prepared By: Manila Tiwari 51
Discrete Structures: BIT 2nd Sem
Existence Proofs
Srinivasa Ramanujan
(1887-1920)
• Proof of theorems of the form .
• Constructive existence proof:
• Find an explicit value of c, for which P(c) is true.
• Then is true by Existential Generalization (EG).
Example: Show that there is a positive integer that can be written as the sum of
cubes of positive integers in two different ways:
Proof: 1729 is such a number since
1729 = 103 + 93 = 123 + 13

Godfrey Harold Hardy

(1877-1947)
Prepared By: Manila Tiwari 52
Discrete Structures: BIT 2nd Sem
Constructive Existence proof
• To prove
∃xP(x)
find an explicit example satisfying the property.
• This is called a constructive existence proof.

Steps
• Find a specific object.
• Verify it satisfies the required property.
• Therefore the object exists.
Prepared By: Manila Tiwari
Discrete Structures: BIT 2nd Sem
Nonconstructive Existence Proofs
• Instead of giving an explicit example, prove that an object must exist,
usually by contradiction or logical reasoning.
• In a nonconstructive existence proof, we assume no c exists which makes
P(c) true and derive a contradiction.
Example: Show that there exist irrational numbers x and y such that xy is
rational.
Proof: We know that √2 is irrational. Consider the number √2 √2 .
If it is rational, we have two irrational numbers x and y with xy rational,
namely x=√2 and y=√2.
But if √2 √2 is irrational, then we can let x = √2 √2 and y = √2
so that xy = (√2 √2 )√2
= √2 (√2 √2) = √2 2 = 2.
Prepared By: Manila Tiwari 54
Discrete Structures: BIT 2nd Sem
 Counter examples
Falsity of Universal Quantification
• A counter example is a single example that proves a universal
statement is false.
• To disprove ∀x P(x), it is enough to find one value ccc for which P(c) is
false.

• Recall .
• To establish that is true (or is false) find a c
such that P(c) is true or P(c) is false.
• In this case c is called a counterexample to the assertion .
Example: “Every positive integer is the sum of the squares of 3
integers.” The integer 7 is a counterexample.
Prepared By: Manila Tiwari
So the claim is false. 55
Discrete Structures: BIT 2nd Sem
Uniqueness Proofs
• Some theorems state that exactly one object exists.
• This is written as
∃!x P(x)
(read: "There exists a unique x such that P(x).
• A uniqueness proof has two parts:
• Existence: We show that an element x with the property exists.
• Uniqueness: We show that if y≠x, then y does not have the property.

Prepared By: Manila Tiwari 56

Discrete Structures: BIT 2nd Sem
Uniqueness Proofs
• Example: Show that if a and b are real numbers and a ≠0, then there
is a unique real number r such that ar + b = 0.
Solution:
• Existence: The real number r = −b/a is a solution of ar + b = 0
because a(−b/a) + b = −b + b =0.
• Uniqueness: Suppose that s is a real number such that as + b = 0.
Then ar + b = as + b, where r = −b/a. Subtracting b from both
sides and dividing by a shows that r = s.

Prepared By: Manila Tiwari 57

Discrete Structures: BIT 2nd Sem
Universally Quantified Assertions
• To prove theorems of the form ,assume x is an arbitrary
member of the domain and show that P(x) must be true. Using UG it
follows that .
Example: An integer x is even if and only if x2 is even.
Solution: The quantified assertion is
x [x is even  x2 is even]
We assume x is arbitrary.
Recall that is equivalent to
So, we have two cases to consider. These are considered in turn.
Continued on next slide 
Prepared By: Manila Tiwari 58
Discrete Structures: BIT 2nd Sem
Universally Quantified Assertions
Case 1. We show that if x is even then x2 is even using a direct proof
(the only if part or necessity).
If x is even then x = 2k for some integer k.
Hence x2 = 4k2 = 2(2k2 ) which is even since it is an integer divisible
by 2.
This completes the proof of case 1.

Case 2 on next slide 

Prepared By: Manila Tiwari 59
Discrete Structures: BIT 2nd Sem
Universally Quantified Assertions
Case 2. We show that if x2 is even then x must be even (the if part or
sufficiency). We use a proof by contraposition.
Assume x is not even and then show that x2 is not even.
If x is not even then it must be odd. So, x = 2k + 1 for some k. Then x2
= (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1
which is odd and hence not even. This completes the proof of case 2.
Since x was arbitrary, the result follows by UG.
Therefore we have shown that x is even if and only if x2 is even.

Prepared By: Manila Tiwari 60

Discrete Structures: BIT 2nd Sem
 Prepared By: Manila Tiwari 61
Discrete Structures: BIT 2nd Sem