Transcript Logic and Proofs 093 ICS 253: Discrete Structures I

King Fahd University of Petroleum & Minerals
Information & Computer Science Department
ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
093 ICS 253: Discrete Structures I
2
The Foundations: Logic and Proofs
Section 1.7: Proof Methods and Strategy
• In Section 1.6 we briefly discussed the
strategy behind constructing proofs.
• In this section, we will study some additional
aspects of the art and science of proofs.
• Give advice on how to find a proof of a theorem.
• Describe some tricks of the trade, including how
proofs can be found by working backward and by
adapting existing proofs.
093 ICS 253: Discrete Structures I
3
The Foundations: Logic and Proofs
Exhaustive Proofs and Proof By Cases
• Exhaustive Proof: Some theorems can be proved
by examining a relatively small number of
examples.
• These proofs proceed by exhausting all possibilities.
• An exhaustive proof is a special type of proof by cases
where each case involves checking a single example.
• Proof by Cases
• Prove that (p1  p2  …  pn)  q
using the tautology
[(p1 p2… pn)q]  [(p1q)(p2q)…(pnq)]
093 ICS 253: Discrete Structures I
4
The Foundations: Logic and Proofs
Examples
• Prove that (n + 1)3 > 3n if n is a positive
integer with n  4.
• Q4 pp. 102: Use a proof by cases to show that
min( a, min( b, c)) = min(min(a, b), c)
whenever a, b, and c are real numbers.
• Show that there are no solutions in integers x
and y of x2 + 3y2 = 8.
093 ICS 253: Discrete Structures I
5
The Foundations: Logic and Proofs
Without Loss of Generality
• When the phrase "without loss of generality"
is used in a proof (abbreviated as WLOG), we
assert that by proving one case of a theorem,
no additional argument is required to prove
other specified cases.
• That is, other cases follow by making
straightforward changes to the argument, or by
filling in some straightforward initial step.
• Use a proof by cases to show that |xy| = |x||y|,
where x and y are real numbers.
093 ICS 253: Discrete Structures I
6
The Foundations: Logic and Proofs
Existence Proofs
• Usually applied to theorems of the form
xP(x).
• We usually prove them by
• Finding a particular element c such that P(c)
holds, which is a form of constructive proof.
• Some other way, like proof by contradiction,
which is a form of nonconstructive proof.
093 ICS 253: Discrete Structures I
7
The Foundations: Logic and Proofs
Examples
• Q6 pp 102: Prove that there is a positive
integer that equals the sum of the positive
integers not exceeding it. Is your proof
constructive or nonconstructive?
• Q8 pp 102: Prove that either 2.10500 +15 or
2. 10500 +16 is not a perfect square. Is your
proof constructive or nonconstructive?
8
093 ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
Uniqueness Proofs
• To prove statements concerning the existence
of a unique element, we show
• Existence:
• Uniqueness:
• Q17 pp 103: Show that if n is an odd integer,
then there is a unique integer k such that n is
the sum of k - 2 and k + 3.
093 ICS 253: Discrete Structures I
9
The Foundations: Logic and Proofs
Forward and Backward Reasoning
• Direct proofs are examples of forward reasoning.
• Unfortunately, forward reasoning is often
difficult to use to prove more complicated
results.
• Reasoning needed to reach the desired conclusion
may be far from obvious.
• In such cases, it may be helpful to use backward
reasoning.
• To reason backward to prove a statement q, we
find a statement p that we can prove with the
property that p  q.
093 ICS 253: Discrete Structures I
10
The Foundations: Logic and Proofs
Example
• Given two distinct positive real numbers x
and y, their arithmetic mean is (x + y) /2 and
their geometric mean is xy . Prove that the
arithmetic mean is always greater than the
geometric mean.
Proof:
093 ICS 253: Discrete Structures I
11
The Foundations: Logic and Proofs
Adapting Existing Proofs
• An excellent way to look for possible approaches
that can be used to prove a statement is to take
advantage of existing proofs.
• An existing proof can be adapted to prove a new
result.
• Some of the ideas used in existing proofs may be
helpful.
• Because existing proofs provide clues for new
proofs, you should read and understand the
proofs you encounter in your studies.
• Check the example on proving 3 is irrational!
12
093 ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
The 3x+1 Conjecture
• Let T be the transformation that sends an even integer x to x/2 and
an odd integer x to 3x + 1.
• Conjecture: For all positive integers x, when transformation T is
applied repeatedly, we will eventually reach the integer 1.
• For example, starting with x = 13, we find
•
•
•
•
•
•
•
•
•
T(13) = 3 .13 + 1 = 40,
T(40) = 40/2 = 20,
T(20) = 20/2 = 10,
T(10) = 10/2 = 5,
T(5) = 3 · 5 + 1 = 16,
T(16) = 8,
T(8) = 4,
T(4) = 2, and
T(2) = 1.
• The 3x + 1 conjecture has been verified for all integers x up to
5.6  1013.