Scribd Logo
Upload

Welcome to Scribd!

  • 37 views

    Discrete Mathematic LEC-02:: Method of Proofs

    Uploaded by

    Quang Chien Pham
    This document summarizes different proof techniques: direct proof, proof by contraposition, proof by contradiction, and proof by cases. It provides examples of using each technique to prove theorems about integers, primes, and rational/irrational numbers. Students are given practice problems to prove statements about even/odd integers using different proof styles. The key proof techniques and examples are intended to help students understand how to structure mathematical proofs.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Discrete Mathematic LEC-02:: Method of Proofs

    Uploaded by

    Quang Chien Pham
    37 views27 pages
    This document summarizes different proof techniques: direct proof, proof by contraposition, proof by contradiction, and proof by cases. It provides examples of using each technique to prove theorems about integers, primes, and rational/irrational numbers. Students are given practice problems to prove statements about even/odd integers using different proof styles. The key proof techniques and examples are intended to help students understand how to structure mathematical proofs.

    Original Title

    Proofs.pptx

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document summarizes different proof techniques: direct proof, proof by contraposition, proof by contradiction, and proof by cases. It provides examples of using each technique to prove theorems about integers, primes, and rational/irrational numbers. Students are given practice problems to prove statements about even/odd integers using different proof styles. The key proof techniques and examples are intended to help students understand how to structure mathematical proofs.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    37 views27 pages

    Discrete Mathematic LEC-02:: Method of Proofs

    Uploaded by

    Quang Chien Pham
    This document summarizes different proof techniques: direct proof, proof by contraposition, proof by contradiction, and proof by cases. It provides examples of using each technique to prove theorems about integers, primes, and rational/irrational numbers. Students are given practice problems to prove statements about even/odd integers using different proof styles. The key proof techniques and examples are intended to help students understand how to structure mathematical proofs.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 27

    Fall, 2018

    DISCRETE MATHEMATIC
    LEC-02:
    Method of Proofs
    Lecture 2

    Direct Proof
    Proof by Contraposition
    Proof by Contradiction
    Proof by Cases.
    Definitions

    • Why proof?
    • Proof: A sequence of statements, ending with the
    proposition being proved; each statement is either an axiom
    or can be deduced easily from the previous statements.
    • In proving theorems or solving problems, creativity and insight
    are needed, which cannot be taught.
    Definitions

    • Theorem: a true proposition that is guaranteed by a


    proof.
    • Axiom: an assertion we accept without proof.
    Example 1
    • Theorem:

    If n2 is odd, then n is odd.

    • Axiom:

    If equals are added to equals, the wholes are equal.


    Types of Proof
    Direct Proof
    Direct proof of P=>Q
    Assume P
    =>A
    =>B
    …
    Therefore Q
    Example 2
    • Theorem: If x is odd, then x + 1 is even.
    • Proof
    Assume x is odd
    => x = 2k + 1
    => x + 1 = 2(k + 1)
    Therefore, x + 1 is even
    Example 3
    • Theorem: Let n be a positive integer less than 1000. If
    the sum of the digits of n is divisible by 9, then n is
    divisible by 9.
    • Proof
    Let n be abc. Assume (a + b + c) is divisible by 9.
    n = abc
    => n = 100a + 10b + c
    => n = 99a + 9b + (a + b + c)
    since a + b + c is divisible by 9
    Therefore, n is divisible by 9
    Example 4
    • Theorem: n is divisible by 9 iff the sum of digits is divisible by 9.
    • Proof:
    Example 5

    • Proof:
    Indirect Proofs
    Proof by Contraposition
    Proof by contraposition of P=>Q
    Assume ¬Q.

    Therefore ¬P.

    So ¬Q=>¬P ≡ P=>Q
    Example 6
    • Theorem: If n2 is even, then n is even
    • Proof:
    Assume n is odd
    => n = 2k + 1
    => n2 = 2(2k2 + 2k) + 1
    Therefore n2 is odd
    So if n is odd then n2 is odd. This is equivalent to if n2 is even
    then n is even.
    Example 7

    • Prove that if and is odd, then is


    odd.
    • Proof:
    Assume the ¬(conclusion): n is even
    => n = 2k
    => 3n+2 = 3(2k) + 2 = 2(3k+1)
    Therefore 3n+2 is odd: ¬(hypothesis)
    So if n is odd then 3n+2 is odd. This is
    equivalent to if n is even then 3n+2 is even.
    Open Question
    • Show a direct proof of the following theorem.
    • Theorem: if n2 is odd, then n is odd.
    Proof by Contradiction

    Proof by contradiction of P
    Assume ¬P
    …
    R
    …
    ¬R
    Contradiction
    Therefore P
    Example 8
    • Theorem: There are infinitely many primes.
    • Proof:
    Assume there are only finitely many primes.
    => Q = p1, p2, .., pk are all primes.
    => Q = p1p2…pk + 1 is not a prime.
    => Q = p1p2…pk + 1 has a prime divisor p > 1.
    Q = p * R1.

    p is a prime => p must be one of p1,p2,…,pk


    => Q = p * R2 + 1.

    => Contradiction.
    Therefore there are infinitely many primes.
    Example 9

    • Theorem: 2 is irrational
    • Proof:
    Open Question
    • Show a proof by contradiction of the following theorem.
    • Theorem: if n2 is odd, then n is odd.
    Proof by Cases

    Sometimes we don’t know which of a set of possible cases is


    true, but we know that at least one of the cases is true. If we
    can prove at least one of possible cases is true then we have a
    proof.
    Example 10

    • Theorem: For some irrational number x and y, xy is


    rational.
    • Proof:
    Case 1: is rational (done.)

    Case 2: is irrational.

    is rational (done.)
    Test 1

     Show that the square of an even number is an even number using


    direct proof.
    Test 2

     Show that if is an integer and is odd,


    then is even using:
    • A proof by contraposition.
    • A proof by contradiction.
    Test 3

    Proof by contraposition:
    Test 4

    Proof by contradiction:
    Test 5
     Show that if is an integer and is
    odd, then is even by using direct
    proof?

     Is odd  n is even
    Summary
    • Direct proofs
    • Proofs by contraposition
    • Proofs by contradiction
    • Proofs by cases
    • Homework: Problem Set 2

    You might also like