Transcript Discrete Mathematics I Lectures Chapter 4

DISCRETE MATHEMATICS I
LECTURES CHAPTER 4
Some material adapted from
lecture notes provided by Dr.
Chungsim Han and Dr. Sam
Lomonaco
Dr. Adam Anthony
Spring 2011
Section 4.1


Elementary Number Theory
Basic Proof Technique: Direct Proof
Tying It All Together: Self-Quiz



What is a valid argument?
When is a valid argument correct? When is it
wrong?
How could you PROVE that a valid argument is
correct?
What is a Proof?



A mathematical proof is a valid argument for which
all premises are formally guaranteed (proven) to be
true.
Different argument forms lead to different proof
types
Sometimes guaranteeing a premise results in having
to stop and prove the premise first!
Proof Terminology
An axiom is a basic assumption about mathematical
structures that needs no proof.

We can use a proof to demonstrate that a particular
statement is true. A proof consists of a sequence of
statements that form an argument.

The steps that connect the statements in such a
sequence are the rules of inference.
Cases of incorrect reasoning are called fallacies.


A theorem is a statement that can be shown to be true.
Proof Terminology
A lemma is a simple theorem used as an intermediate
result in the proof of another theorem.

Lemmas
prove premises to be true!
A corollary is a proposition that follows directly from
a theorem that has been proved.

A conjecture is a statement whose truth value is
unknown. Once it is proven, it becomes a theorem.

Elementary Number Theory

Some knowledge we’ll assume:
Properties of Real Numbers in Appendix A (‘basic algebra’)
 All logic material from Chapters 2,3
 Properties of equality:

A = A (reflexive)
 If A = B, then B = A (symmetric)
 If A = B and B = C then A = C (transitive)

The Integers include …-2, -1, 0, 1, 2, … (No Fractions)
 Integers are closed under +, -, *



Sum/Difference/Product of any two integers is also an integer
Integers are not generally closed under /

3/2 is not an integer
Properties of Integers





An integer n is even  n = 2k for some integer k
An integer n is odd  n = 2k + 1 for some integer
k
An integer n is prime   positive integers a and b,
if n = ab, then a = 1 or b = 1
An integer n is composite   positive integers a
and b for which n = ab, and a 1 and b  1
Using the symbol  means we can use these
properties in either direction!
Exercises 1, 2

If r is any integer (even or odd!), is (2r -1) odd?

If s is any integer, is 2s2 + 6s – even?

Which of the following are prime?
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12


Can an even number >2 be prime?
Is every integer > 1 either prime or composite?
Simplest Proof Type: Constructive Proof
of Existence


You know this one already!
How do we prove:

1.
2.
x in D, Q(x)?
Give a straight example
Prove that  even integer n such that n can be
written in 2 ways as a sum of prime numbers
Give a set of instructions to find an example:
Prove that  integer k, 22r + 18s = 2k
Simple ‘Proof’: Disproof by Counter
Example


We know this one too!
How do we disprove
 x

in D, P(x)?
2 identical approaches:
1.
2.
Directly find a single item in D for which P(x) is false
Negate the phrase and prove the negation (this one is
a constructive proof!)
Disproof of a Conditional



A special case of disproof comes up again and
again:
How do we disprove;
How do we disprove
 x

in D, P(x)  Q(x)?
In general, we can skip the above and just move to
find an example where P(x) is true, but Q(x) is
false.
Exercise 3

1.
2.
3.
4.
Disprove the following statements:
 integers n, n2 – n + 11 is prime
 real numbers a and b, if a < b, then a2 < b2
All primes are odd
For any integer n, if n2 = 4 then n = 2
Proving Universal Statements


We’ve discussed this before: disproving universal
statements is easy, but proving them true is difficult!
In general, how do we prove


Exhaustive search: try everything in D!


x in D, P(x)?
What if D is infinite???
Use a Generic Particular
Pick a variable x that has a particular but arbitrarily chosen
value from the set D
 Show that P(x) is true, without ever knowing what number
was picked, based on the known axioms for items in D.

Disproving Existential Statements

How do we disprove:


x in D, Q(x)?
2 identical approaches:
Show that there isn’t a single item in D for which P(x)
is false.
Negate the phrase and prove the negation using the
previous slide:
1.
2.

 x in D, Q(x)  x in D, P(x)
Exercise 4


True or False?
There is an even integer n > 2 such that n is prime.
Perhaps the negation is easier to prove:


For any even integer n, if n > 2, then n is not prime
Proof:
1.
2.
3.
4.
5.
6.
7.
Pick any even integer at all, we’ll call it x, and suppose that x > 2
By definition of an even integer: x = 2m for some integer m
m must be greater than 1 since x > 2
By definition of a prime integer, if x = a*b then either a or b must be
equal to 1
But x = 2m and 2  1 and m  1
Therefore x is not prime (no matter what even integer you pick!)
If the negation is TRUE, then the original statement must be FALSE!!!
Proofs Using Universal Modus Ponens


x in D, P(x)  Q(x)
P(c) for a particular c in D
Q(c)
Proof: MUST SHOW THAT ALL PREMISES ARE
GUARANTEED TO BE TRUE!
 Then,


the conclusion follows as a proof
Proving P(c): easy—it’s either true or false for that
one thing
How do we prove x in D, P(x)  Q(x) is true?
Direct Proof

Many proofs start with or otherwise use a
universally quantified conditional statement:
 x

in D, P(x)  Q(x)
One way to show this is true is using a Direct Proof:
1.
2.
Suppose P(x) is true for some particular but
arbitrarily chosen element in D.
Show that Q(x) must be true by using definitions,
previously established results, and rules for logical
inference.
Tips on Getting Started with a Proof
that P(x)  Q(x)
1.
2.
3.
4.
5.
Read and re-read the question until you clearly
understand what is being asked:
Write down the starting point, adapted from the lefthand side of the implication—“Suppose there exists a
particular but arbitrarily chosen m for which P(m) is
true.”
Write down a clear statement for what you need to
prove: “Therefore, Q(m) is true”
On the side, write down every definition and axiom
that you know which you think might be relevant
From the starting point, use the definitions and axioms
to build up toward the conclusion
Exercise 5


Prove that, for all Integers n, if n is even, then n2 is
even.
Starting Point: Suppose n is a [particular but
arbitrarily chosen] integer such that n is even.
 By
definition, n = 2k for some integer k
 Then n2 = (2k)2 = 4k2 = 2(2k2) using basic algebra.
 Then n2 = 2m where m = 2k2, and 2k2 is an integer.

[Conclusion to be shown: ] Therefore, by definition n2
is even
Exercise 6

Prove that for all integers m and n, if m is even and
n is odd, then m + n is odd
General Guidelines for Proof Writing
1.
2.
3.
Copy the statement of the theorem to be proved
onto the paper
Clearly mark the beginning of the proof with the
word ‘Proof’.
Make your proof self-Contained

4.
Explain the meaning of each variable you use
Write your proof in complete, grammatically
correct sentences, mathematical notation excepted.

“Then M + N = 2r + 2s.”
General Guidelines for Proof Writing
5.
6.
7.
8.
Be clear about assumptions or things that haven’t
been
proved
yet.
PROOFS IN YOUR JOURNAL DO NOT
Give
a reason
for each
statement
HAVE
TO FOLLOW
THESE
GUIDELINES!
•Journal
workbymay
be as messy
as youtheorem, etc.
 By
definition,
hypothesis,
by previous
like!
Use
good connecting words to guide logic
•You don’t have to use complete
 Then, thus, so, hence, It follows that, therefore, etc.
sentences, give reasons, or even be clear
DISPLAY
equations
and
inequalities
about assumptions and such
 Put them on a SEPARATE line, centered.
•It’s the copying phase—where you re White
space
your friend,
improves
write for
theishomework
where
you readability
apply
these 8 guidelines!
Common Proof Mistake: Arguing from
examples

“Proof” that  integers n, n2 – n + 11 is prime
n = 6, then 62 – 6 + 11 = 41 which is prime so this
must work
 If


Using examples is useful when you are thinking
through the problem (esp. in your journal) to
visualize structure
But in general, proofs must work for ALL items in the
domain, so picking 1 or 2 is not satisfactory proof.
Common Proof Mistake: Using the same
letter for two different values


“Suppose m and n are any odd integers. Then by
definition of odd, m = 2k + 1 and n = 2k + 1 for
some integer k.”
Why is this wrong?
Common Proof Mistake: Jumping to a
Conclusion and Circular Reasoning

“Proof” that the sum of two even integers is even:
 Suppose
m and n are any even integers. By definition
of even, m = 2r and n = 2s for some integers r and s.
Then m + n = 2r + 2s. So m + n is even.
 Jumping
to a conclusion: the last line does not fit any
definition!

“Proof” that the product of two odd integers is odd:
 Suppose
m and n are any odd integers. When any
odd integers are multiplied, their product is odd.
Hence mn is odd.
 See
the circular reasoning here?
Section 4.3: Divisibility



Definition: If n and d are integers and d  0 then
n is divisible by d if, and only if, n
equals d times some integer
Identical phrases: n is a multiple of d, d is a factor of n,
d is a divisor of n, d divides n
Notation:

d | n is read as ‘d divides n’ and means:
 integer k, n = dk
 OR, n/k is an integer


d ∤ n is read as ‘d does not divide n’ and means:
integer k, n  dk
 OR, n/k is not an integer

Exercise 1






Is 18 divisible by 6?
Does 3 divide 12?
Does 5 | 25?
If d is a nonzero integer, does d divide 0?
If m and n are integers is 10m + 15n divisible by 5?
Does 6 | 3?
Exercise 2

Prove that for all integers a, b and c, if a|b and b|c
then a|c. [This is the transitive property of divisibility]
Exercise 3

Prove that for all integers a and b if a|b then
a2|b2.
Exercise 4

Disprove the following: For all integers a and b if
a|b and b|a then a = b.
Section 4.4: The Quotient-Remainder
Theorem

Think of an integer as a set of whole items:


12 = xxxxxxxxxxxx
Then saying 12  3 is the same as dividing the set into
groups of size 3:

12  3 = xxx xxx xxx xxx,



4 groups of 3
12 = 4*3
What about 13  3?

13  3 = xxx xxx xxx xxx x,


4 groups of 3, with one left over
13 = 4*3 + 1
The Quotient Remainder Theorem

For any integer n and a positive integer d, there
exist unique integers q and r such that:
n = dq + r and 0 r<d

Find values for q and r for the given n and d:
n
= 26, d = 7
 n = -26 and d = 7
 n = 27 and d = 30
 n = -34 and d = 11
Definitions, notation



n div d: the value of q (aka the quotient) when n is
divided by d
n mod d: the value of r (aka the remainder) when n is
divided by d
Find:
 29
div 8
 29 mod 8
 -29 div 8
 -29 mod 8
Applying The Quotient-Remainder
Theorem


Apply the QR theorem to any integer n with d = 2
Just fill in the blanks with what we know, leaving the
rest:
 For
any integer n and the positive integer 2, there exist
unique integers q and r such that:
n


= 2q + r and 0 r<2
What can we conclude???
The parity property refers to the fact that any given
integer is either even or odd, and not both.
Dealing With Uncertainty



Up to now, if we didn’t know something for sure then
we ignored it
But we don’t have to!
Take any integer n:
 Is
it even or odd?
 If
it is even, then we know
certain facts about n
 If it is odd, then we know
a different set of facts
These two ‘possible scenarios’
are referred to as cases
Division into Cases—Argument Form
pr
qr
sr
…
zr
(p  q  s  …  z)
r
Cases where r must be true
Assertion that at least one of
the cases MUST have occurred.
Division into Cases—Proof Form
Given an item r to prove in which some item can fall
into several categories (e.g., odd/even):

Assert that there exist a fixed number of potential cases in
the world that can be true: (Case1  Case2 …)
Set up the following arguments:
1.
2.
1.
2.
3.
3.
4.
Case1  r
Case2  r
…
Perform a direct proof for each case above
If you succeed for all cases, then by valid argument, r must
always be true.
Proof Example 1





Prove that the product of any two consecutive
integers is even.
Starting Point: Select any integer n.
Need to prove: the product of n and the next
consecutive integer (n + 1) is even.
What do we know for sure about n?
What don’t we know for sure?
Proof Example 1

Prove that the product of any two consecutive
integers is even.
Select any integer n.
Case 1: n is even.

Case 2: n is odd.


Proof Example 2


Prove that if n is an integer, then n2  n
Common set of cases: n = 0, n < 0, n > 0
 ‘Divide
and conquer’ approach: break a big problem into
2 or more smaller problems.
Proof Example 3


Show that |xy| = |x||y| where x Absolute Value:
|x| = x when x  0
and y are real numbers.
|x| = -x when x < 0
With two numbers, what are all the
possible scenarios (cases)?
Proof Example 4: Triangle Inequality

Show that for all real numbers x
and y, |x + y|  |x| + |y|
Absolute Value:
|x| = x when x  0
|x| = -x when x < 0
Section 4.6: Indirect Proof Techniques


Proof by contraposition
Proof by contradiction
First attempt


Let’s try to use a direct proof for the following:
Prove for all integers n, if n2 is even, then n is even
The Contrapositive Trick

Remember that an implication’s contrapositive is
equivalent to the original statement:
p


 q  q  p
So for any proof statement, we can replace an
implication with its contrapositive and prove that
instead!
The proof of the new statement is a necessary and
sufficient proof of the original
Second Attempt



Use contraposition this time:
Prove for all integers n, if n2 is even, then n is even
Contrapositive version: for all integers n, if n is not
even, then n2 is not even
 If
n is odd, then n2 is odd
Prove this!
Contraposition Example 1

Prove that for all integers n, if 3n+2 is odd, then n is
odd.
Contraposition Example 2

For all integers n, if 5 ∤ n2 then 5 ∤ n
Proof by Contradiction

An inference rule:
p
(p  c)
 What

is the intuition here?
To use this to our advantage, we use the ‘causeeffect’ interpretation of :
 If
p were true, then it MUST follow that some
contradiction arises
 If we can show that, then (p  c) is true, which means
p is true
Another Attempt

Prove by Contradiction that for all integers, n, if n2
is even, then n is even
1.
2.
3.
Negate the claim:  integer n, n2 is even  n is odd
Work toward a contradiction
If/when you find one, proof completed.
Contradiction Example 1

Prove that there is no greatest real number.
Contradiction Example 2

For all prime numbers a, b and c, a2 + b2  c2
Proof Techniques Summary




The only real “technique” we learned is the direct
proof: apply logic to reach a formal conclusion
Division into cases: break large problem up into
smaller, manageable pieces
Proof by contraposition: sometimes it is easier to
“flip” the problem first.
Proof by contradiction: intuitively the most versatile,
but still results in a special kind of direct proof
Proof Practice 1

Prove that if you pick three socks from a drawer
containing just blue socks and black socks, you must
get either a pair of blue socks or a pair of black
socks.
Proof Practice 2

Prove that if n = ab, where a and b are positive
integers, then a  n or b   n
Proof Practice 3

Show that at least four of any 22 days must fall on
the same day of the week.
Proof Practice 4

For all integers m and n, if m+ n is even then m and
n are both even or m and n are both odd.