Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 13 views

    09 Proof

    Uploaded by

    Shadmaan Sabit
    This document discusses different proof techniques in mathematics including direct proof, proof by contradiction, and proof by contraposition. It provides examples of proving statements using each technique and discusses concepts like vacuous proofs, trivial proofs, and disproving universally quantified statements by counterexample. The document is intended to teach students in a discrete mathematics course how to structure and write mathematical proofs.

    Copyright:

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

    09 Proof

    Uploaded by

    Shadmaan Sabit
    13 views19 pages
    This document discusses different proof techniques in mathematics including direct proof, proof by contradiction, and proof by contraposition. It provides examples of proving statements using each technique and discusses concepts like vacuous proofs, trivial proofs, and disproving universally quantified statements by counterexample. The document is intended to teach students in a discrete mathematics course how to structure and write mathematical proofs.

    Original Description:

    Original Title

    09-proof

    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 discusses different proof techniques in mathematics including direct proof, proof by contradiction, and proof by contraposition. It provides examples of proving statements using each technique and discusses concepts like vacuous proofs, trivial proofs, and disproving universally quantified statements by counterexample. The document is intended to teach students in a discrete mathematics course how to structure and write mathematical proofs.

    Copyright:

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

    09 Proof

    Uploaded by

    Shadmaan Sabit
    This document discusses different proof techniques in mathematics including direct proof, proof by contradiction, and proof by contraposition. It provides examples of proving statements using each technique and discusses concepts like vacuous proofs, trivial proofs, and disproving universally quantified statements by counterexample. The document is intended to teach students in a discrete mathematics course how to structure and write mathematical proofs.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 19

    PROOF TECHNIQUES

    CSE 2213 – Discrete Mathematics


    Course teacher: Minhajul Bashir

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD
    WHAT TO PROVE? HOW TO
    PROVE?
    Prove that, if an integer is even, then is also even.

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 2
    CAN WE PROVE THE
    REVERSE?
    Prove that, if is an integer, and is even, then is also even.

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 3
    PROOF TECHNIQUES
    Three basic techniques –
     Direct proof
     Proof by contradiction
     Proof by contraposition

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 4
    DIRECT PROOF
    To prove , we first assume that is true, and hence prove that is true
     We reach the conclusion directly from our assumption

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 5
    PROOF BY CONTRADICTION
    To prove , we first assume that , and start logical arguments to reach a conclusion
    that contradicts our assumption, or any real life scenario

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 6
    PROOF BY CONTRAPOSITION
    To prove , we first assume that is true, and hence prove that is true
     We actually prove the contrapositive of the actual sentence, i.e.

    What is the difference between proof by contraposition and proof by contradiction?

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 7
    EXAMPLE
    Use direct proof to prove that the product of two rational numbers is rational

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 8
    EXAMPLE
    Prove by contradiction that is an irrational number.

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 9
    EXAMPLE
    Prove by contraposition that if is an integer and is odd,
    then is even.

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 10
    STANDARD FORMS OF
    DIFFERENT NUMBERS
    Type Standard form
    Even number , where is an integer
    Odd number or , where k is an integer
    Multiple of , where is an integer
    Division by gives remainder , where is an integer
    Perfect square , where is an integer
    , where are integers and
    Rational number (Sometimes also assume do not have any common factors other
    than 1)

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 11
    VACUOUS AND TRIVIAL
    PROOFS
    If we prove a conditional statement by disproving its hypothesis, then the proof
    technique is called vacuous proof
    If we prove a conditional statement by proving its conclusion, then the proof
    technique is called trivial proof

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 12
    QUICK EXERCISE
    Is true, where ?
     Vacuous proof

    Is true, where ?
     Trivial proof

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 13
    PROVING EQUIVALENCES
    Prove that “For every positive integer , is odd if and only if is odd”
     First prove “if is odd then is odd”
     Then prove “if is odd then is odd”

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 14
    DISPROVING UNIVERSALLY
    QUANTIFIED PROPOSITIONS
    Prove that “Every positive integer is the sum of the squares of two integers” is false.
     We just find a counterexample, that invalidates the use of “every” in the sentence
     Here, a counterexample is 3 (because 3 = 1 + 2 = 0 + 3, and 2 and 3 are not squares of any integer)

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 15
    EXAMPLE
    Prove that, if and are even integers, then is also even

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 16
    EXAMPLE
    Prove that, if is irrational, then is also irrational

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 17
    EXAMPLE
    Prove that the sum of an irrational and a rational number is irrational

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 18
    QUICK EXERCISE
    Prove or disprove that the product of two irrational numbers is irrational

    12/15/2022 MINHAJUL@CSE.UIU.AC.BD 19

    You might also like