Discrete Mathematics - Lecture 1.7 Introduction to Proofs PDF

Preview

Summary

Discrete Mathematics - Lecture 1.7 Introduction to Proofs...

Description

Math 3336 Section 1.7 Introduction to Proofs Topics:    

Mathematical Proofs Forms of Theorems Direct Proofs Indirect Proofs  Proof of the Contrapositive  Proof by Contradiction  Mistakes in Proofs

Definition: A

is a statement that can be shown to be true.

We demonstrate that a theorem is true with a proof (valid argument) using: • Definitions • Other theorems • Rules of Inference • Axioms •

A

a ‘helping theorem’ or a result which is needed to prove a theorem.

•

A

•

Less important theorems are sometimes

.

•

A

e. Once a proof of a conjecture

y is a result which follows directly from a theorem.

is a statement that is being

is found, it becomes a theorem. It may turn out to be false.

Forms of Theorems • Many theorems assert that a property holds for all elements in a 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. Example: then ฀฀ 2 > ฀฀ 2 ”

“If ฀฀ > ฀฀, where ฀฀ and ฀฀ are means

Page 1 of 6

Methods of Proving Theorems 1. Direct Proofs In direct proof we show that conditional that ฀฀ must be

is true. We a

that

and show

Definition: The integer ฀฀ is if there exists an integer ฀฀ such that and if there exists an integer ฀฀, such that . Note that every integer is either even or odd and no integer is both even and odd. Questions: 1. 0:

odd, or neither?

2. -21: even, odd, or neither? Example: Give a

of the theorem “If

Example: Give a direct proof of the theorem “If ”

Page 2 of 6

r, then

e, then

”

Example: Use a direct proof to show that “The product of two odd numbers is odd.”

We know that This means that the conditional statement ฀฀ → ฀฀ can be proven by showing that its contrapositive, ¬฀฀ → ¬฀฀ , is true.We that is true and show that

Page 3 of 6

.

4. Proofs by Contradiction Suppose we want to prove that a statement ฀฀ is true. We assume this leads to a Example: Prove that if ฀฀ is an integer and a. a proof by contraposition b. a proof by contradiction

d, then

C

C

Page 4 of 6

then show that

using

M •

: If we know ฀฀ is true, then ฀฀ →

is true as well.

Example: “If it is raining then 1=1.” then

•

→ ฀฀ is true as well.

r then 2 + 2 = 5.” Even though these examples seem silly, both trivial and vacuous proofs are often used in later. e a theorem that is biconditional statement, that is are BOTH true. ieve a statement of the form

) to be

,

we look

for a counterexample. Example: Show that the statement “ two integers” is .

positive integer is the sum of the squares of

Page 5 of 6

What is wrong with this proof? “Proof” that

Page 6 of 6...