1 2 3 4 .... 1 1 1 1 1 ......... ?
1 2 3 4 ....
Discrete mathematics
The
Foundations:
x y ( x y )
Logic and
x( | x )
1
Proofs
x 1 ?
x
x 1 x ?
RIZOAN TOUFIQ
ASSISTANT PROFESSOR
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJSHAHI UNIVERSITY OF ENGINEERING & TECHNOLOGY
Introduction to Proofs
Section 1.7
Section Summary
Mathematical Proofs
Forms of Theorems
Direct Proofs
Indirect Proofs
– Proof of the Contrapositive
– Proof by Contradiction
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
Some Terminology
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
A lemma is a „helping theorem‟ or a result which is needed to
prove a theorem.
A corollary is a result which follows directly from a theorem.
Less important theorems are sometimes called propositions.
A conjecture is a statement that is being proposed to be true.
Once a proof of a conjecture is found, it becomes a theorem. It
may turn out to be false.
Understanding How Theorems
Are Stated
Many theorems assert that a property holds for all elements
in a domain, such as the integers, the real numbers, or some
of the discrete structures that we will study in this class.
Often the universal quantifier (needed for a precise
statement of a theorem) is omitted by standard mathematical
convention.
For example, the statement:
“If x > y, where x and y are positive real numbers, then x2 > y2 ”
really means
“For all positive real numbers x and y, if x > y, then x2 > y2 .”
Methods of 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:
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.
Direct Proof
(Proving Conditional Statements: p → q)
Direct Proof: Assume that p is true. Use rules of
inference, axioms, and logical equivalences to show
that q must also be true.
Example: 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.
( marks the end of the proof. Sometimes QED is used instead. )
Direct Proof
(Proving Conditional Statements: p → q)
Definition: The real number r is rational if there exist
integers p and q where q≠0 such that r = p/q
Example: 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
Thus the sum is rational.
where v = pu + qt
w = qu ≠ 0
Direct Proof
(Proving Conditional Statements: p → q)
Example: Give a direct proof that if m and n are both
perfect squares, then nm is also a perfect square.
(An integer a is a perfect square if there is an integer b such that a = b2.)
Solution:
Home Task
Proof by Contraposition
(Proving Conditional Statements: p → q)
– 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.
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 3n + 2 is odd (not
even) , then n is odd (not even).
Proof by Contraposition
(Proving Conditional Statements: p → q)
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.
Vacuous And Trivial Proofs
Proving Conditional Statements: p → q
Trivial Proof: If we know q is true, the p → q is true as well.
“If it is raining then 1=1.”
Vacuous Proof: If we know p is false then p → q is true as
well.
“If I am both rich and poor then 2 + 2 = 5.”
[Even though these examples seem silly, both trivial and vacuous proofs are often
used in mathematical induction, as we will see in Chapter 5) ]
Proof by Contradiction
(Proving Conditional Statements: p → q)
Proof by Contradiction:
To prove p
Assume ¬p
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.
Proof by Contradiction
(Proving Conditional Statements: p → q)
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 (see
Chapter 4). Then
Therefore a2 must be even. If a2 is even then a must be even (an
exercise). 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 .
Proofs Of Equivalence
To prove a theorem that is a biconditional statement,
that is, a statement of the form p ↔ q, we show that p →
q and q →p are both true.
Example: Prove the theorem: “If n is an integer, then n is odd if
and only if n2 is odd.”
Solution: We have already shown (previous slides) that both
p →q and q →p. Therefore we can conclude p ↔ q.
Sometimes iff is used as an abbreviation for “if an only if,” as in
“If n is an integer, then n is odd iif n2 is odd.”
Counterexamples
∀xP(x) is false, we need only find a counterexample.
Example: x for which P(x) is false
Example: Show that the statement “Every positive integer is
the sum of the squares of two integers” is false.
Solution: there is no way to get 3 as the sum of two terms each
of which is 0 or 1.
2
2 4
{ 0 , 1 },
0 1 1 3
Mistakes in Proofs
“Proof” that 1 = 2
Solution: Step 5. a - b = 0 by the premise and division by 0 is undefined.
Query???
1 2 3 4 ....
x y ( x y ) ?
1
x 1 x ?
x 1 ?
x
x( | x ) ? x y ( x y ) ?
1
1 2 3 4 .... ?
x 1 ?
1 1 1 1 1 ......... ? x