Scribd Logo
Upload

Welcome to Scribd!

  • 383 views

    Chapter 3 - Proofs

    Uploaded by

    trevorsum123
    This document introduces three methods for proving theorems: direct proofs, contraposition, and contradiction. Direct proofs assume the hypothesis is true and prove the conclusion is true. Contraposition assumes the conclusion is false and proves the hypothesis is false. Contradiction assumes the hypothesis is true and conclusion is false, then derives a contradiction. Examples of each method are provided to prove statements about odd and even integers, along with exercises for the reader to practice the three proof techniques.

    Copyright:

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

    Chapter 3 - Proofs

    Uploaded by

    trevorsum123
    383 views4 pages
    This document introduces three methods for proving theorems: direct proofs, contraposition, and contradiction. Direct proofs assume the hypothesis is true and prove the conclusion is true. Contraposition assumes the conclusion is false and proves the hypothesis is false. Contradiction assumes the hypothesis is true and conclusion is false, then derives a contradiction. Examples of each method are provided to prove statements about odd and even integers, along with exercises for the reader to practice the three proof techniques.

    Original Description:

    tttttttttttttt

    Copyright

    © © All Rights Reserved

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document introduces three methods for proving theorems: direct proofs, contraposition, and contradiction. Direct proofs assume the hypothesis is true and prove the conclusion is true. Contraposition assumes the conclusion is false and proves the hypothesis is false. Contradiction assumes the hypothesis is true and conclusion is false, then derives a contradiction. Examples of each method are provided to prove statements about odd and even integers, along with exercises for the reader to practice the three proof techniques.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    383 views4 pages

    Chapter 3 - Proofs

    Uploaded by

    trevorsum123
    This document introduces three methods for proving theorems: direct proofs, contraposition, and contradiction. Direct proofs assume the hypothesis is true and prove the conclusion is true. Contraposition assumes the conclusion is false and proves the hypothesis is false. Contradiction assumes the hypothesis is true and conclusion is false, then derives a contradiction. Examples of each method are provided to prove statements about odd and even integers, along with exercises for the reader to practice the three proof techniques.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    You are on page 1of 4
    At a glance
    Powered by AI
    The text introduces three methods of proving theorems: direct proofs, proofs by contraposition, and proofs by contradiction. It also defines even and odd integers.

    The three methods of proving a theorem discussed are: direct proofs, proofs by contraposition, and proofs by contradiction.

    For a direct proof, the assumption is that the hypothesis is true. The goal is to show that the conclusion is true. The steps are to assume the hypothesis is true and then show that the conclusion is true.

    Introduction to Proof

    A theorem is a statement that can be shown to be true. Normally, a theorem consists


    of hypothesis and conclusion. If we are given a theorem in the form of p q , then
    p is the hypothesis and q is the conclusion. We demonstrate that a theorem is true
    with a proof. We will introduce three methods of proving theorem:
    i)

    Direct Proofs.

    ii)

    Contraposition.

    iii)

    Contradiction.
    Table 1.7: Summary of Proof Techniques

    Direct Proofs
    Assumption Hypothesis is true
    ( p is true).

    Contraposition
    Conclusion is false
    ( q is false @ q is

    Goal

    true).
    false.
    Hypothesis is false
    A contradiction.
    ( p is false @ p is

    Conclusion is true
    ( q is true).

    Contradiction
    Hypothesis is true
    and conclusion is

    true).

    Direct Proofs

    Assume hypothesis (p) is true, and then show conclusion (q) is true.
    Example 1.15
    Give a direct proof of the following theorem: If x is an odd integer and y is an even
    integer, then x y is odd.

    Definition 1.6: Even and odd integer


    The integer n is even if there exists an integer k such that n 2k . The integer n
    is odd if there exists an integer k such that n 2k 1 .

    Solution:

    Proof by Contraposition

    Assume conclusion (q) is false [or q is true], and then show hypothesis (p) is
    false [or p is true].
    Example 1.16
    Prove that if n is an integer and 3n 2 is odd, then n is odd.
    Solution:

    Proof by Contradiction
    Assume hypothesis (p) is true and conclusion (q) is false [or q is true], and then
    show a contradiction.
    Example 1.17
    Give a proof by contradiction of the theorem If 3n 2 is odd, then

    n is odd.

    Solution:

    Exercises

    1. Give a direct proof of the following: If x is an odd integer and y is an even


    integer, then x y is odd.
    2. Give a proof by contradiction of the following: If n is an odd integer, then n2
    is odd.
    3. Consider the following theorem: if x and y are odd integers, then x y is
    even. Give a direct proof of this theorem.
    4. Consider the following theorem: if x and y are odd integers, then x y is
    even. Give a proof by contradiction of this theorem.
    5. Give a proof by contradiction of the following: If x and y are even integers,
    then xy is even.
    6. Consider the following theorem: If x is an odd integer, then x 2 is odd.
    Give a direct proof of this theorem
    7. Consider the following theorem: If x is an odd integer, then x 2 is odd.
    Give a proof by contraposition of this theorem.
    8. Consider the following theorem: If x is an odd integer, then x 2 is odd.
    Give a proof by contradiction of this theorem.
    9. Consider the following theorem: If n is an even integer, then n 1 is odd.
    Give a direct proof of this theorem.
    10. Consider the following theorem: If n is an even integer, then n 1 is odd.
    Give a proof by contraposition of this theorem.
    11. Consider the following theorem: If n is an even integer, then n 1 is odd.
    Give a proof by contradiction of this theorem.

    You might also like