Inference Rules and Proof Methods - Engineering

1 IntroRules of InferenceProof MethodsInference Rules and Proof MethodsLucia MouraWinter 2010 CSI2101 Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsIntroductionRules of Inference and Formal ProofsProofs in mathematics are valid arguments that establish the truth ofmathematical a sequence of statements that end with a argument isvalidif the conclusion (final statement) follows fromthe truth of the preceding statements (premises). Rules of Inference are templates for building valid will study Rules of inferences for compound propositions, for quantifiedstatements, and then see how to combine will be the main ingredients needed informal Discrete Structures Winter 2010.

2 Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsIntroductionProof Methods and Informal ProofsAfter studying how to writeformal proofsusing Rules of Inference forpredicate logic and quantified statements, we will move useful theorems usingformal proofswould result in long andtedious proofs, where every single logical step must be used for human consumption (rather than for automated derivationsby the computer) are usuallyinformal proofs, where steps are combinedor skipped, axioms or Rules of Inference are not explicitly second part of these slides will cover Methods for writing Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicValid Arguments using Propositional LogicConsider the following argument (sequence of propositions):If the prof offers chocolate for an answer, you answer the prof prof offers chocolate for an , you answer the prof s the prof offers chocolate for an answer andqbe you answer the prof s question.

3 Theformof the above argument is:p qp qThe argument is valid since((p q) p) qis a Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicArguments, argument forms and their validityDefinitionAnargumentin propositional logic is sequence of propositions. All but thefinal proposition are calledpremisesand the final proposition is called theconclusion. An argument isvalidif the truth of all its premises impliesthat the conclusion is formin propositional logic is a sequence of compoundpropositions involving propositional variables. An argument form isvalidifno matter which propositions are substituted for the propositional variablesin its premises, if the premises are all true, then the conclusion is other words, an argument form with premisesp1, p2.

4 , pnandconclusionqis valid if and only if(p1 p2 pn) qis a Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicRules of Inference for Propositional Logic Iinference ruletautologynamepp q q(p (p q)) qModus ponens(mode that affirms) qp q p( q (p q)) pModus tollens(mode that denies)p qq r p r((p q) (q r)) (p r)hypothetical syllogismp q p q((p q) ( p)) qdisjunctive syllogismCSI2101 Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicRules of Inference for Propositional Logic IIp p qp (p q)additionp q p(p q) psimplificationpq p q((p) (q)) (p q)conjunctionp q p r q r((p q) ( p r)) (q r)resolutionCSI2101 Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicWhich rule of Inference is used in each argument below?

5 Alice is a Math major. Therefore, Alice is either a Math major or aCSI is a Math major and a CSI major. Therefore, Jerry is a it is rainy, then the pool will be closed. It is rainy. Therefore, thepool is it snows today, the university will close. The university is not closedtoday. Therefore, it did not snow I go swimming, then I will stay in the sun too long. If I stay in thesun too long, then I will sunburn. Therefore, if I go swimming, then Iwill go swimming or eat an ice cream. I did not go , I eat an ice Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicDetermine whether the argument is valid and whether theconclusion must be trueIf 2>32then( 2)2>(32)2.

6 We know that 2>32. Therefore,( 2)2= 2>(32)2= the argument valid?Does the conclusion must be true?What is wrong?The argument is valid: modus ponens Inference cannot conclude that the conclusion is true, since one of itspremises, 2>32, is , in this case the conclusion is false, since26>94= Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicDetermine whether the argument is valid and whether theconclusion must be trueIf 2>32then( 2)2>(32)2. We know that 2>32. Therefore,( 2)2= 2>(32)2= the argument valid?Does the conclusion must be true?What is wrong?The argument is valid: modus ponens Inference cannot conclude that the conclusion is true, since one of itspremises, 2>32, is , in this case the conclusion is false, since26>94= Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicDetermine whether the argument is valid and whether theconclusion must be trueIf 2>32then( 2)2>(32)2.

7 We know that 2>32. Therefore,( 2)2= 2>(32)2= the argument valid?Does the conclusion must be true?What is wrong?The argument is valid: modus ponens Inference cannot conclude that the conclusion is true, since one of itspremises, 2>32, is , in this case the conclusion is false, since26>94= Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicDetermine whether the argument is valid and whether theconclusion must be trueIf 2>32then( 2)2>(32)2. We know that 2>32. Therefore,( 2)2= 2>(32)2= the argument valid?Does the conclusion must be true?What is wrong?The argument is valid: modus ponens Inference cannot conclude that the conclusion is true, since one of itspremises, 2>32, is , in this case the conclusion is false, since26>94= Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicDetermine whether the argument is valid and whether theconclusion must be trueIf 2>32then( 2)2>(32)2.

8 We know that 2>32. Therefore,( 2)2= 2>(32)2= the argument valid?Does the conclusion must be true?What is wrong?The argument is valid: modus ponens Inference cannot conclude that the conclusion is true, since one of itspremises, 2>32, is , in this case the conclusion is false, since26>94= Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicDetermine whether the argument is valid and whether theconclusion must be trueIf 2>32then( 2)2>(32)2. We know that 2>32. Therefore,( 2)2= 2>(32)2= the argument valid?Does the conclusion must be true?What is wrong?The argument is valid: modus ponens Inference cannot conclude that the conclusion is true, since one of itspremises, 2>32, is , in this case the conclusion is false, since26>94= Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicDetermine whether the argument is valid and whether theconclusion must be trueIf 2>32then( 2)2>(32)2.

9 We know that 2>32. Therefore,( 2)2= 2>(32)2= the argument valid?Does the conclusion must be true?What is wrong?The argument is valid: modus ponens Inference cannot conclude that the conclusion is true, since one of itspremises, 2>32, is , in this case the conclusion is false, since26>94= Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicFormal Proofs: using Rules of Inference to build argumentsDefinitionAformal proofof a conclusionqgiven hypothesesp1, p2, .. , pnis asequence of steps, each of which applies some Inference rule to hypothesesor previously proven statements (antecedents) to yield a new truestatement (the consequent).

10 A formal Proof demonstrates that if the premises are true, then theconclusion is that the wordformalhere is not a synomym of formal Proof is based simply on symbol manipulation (no need ofthinking, just apply Rules ).A formal Proof is rigorous but so can be a Proof that does not rely onsymbols!CSI2101 Discrete Structures Winter 2010: Rules of Inferences and Proof MethodsLucia MouraIntroRules of InferenceProof MethodsRules of Inference for Propositional LogicFormal Proof exampleShow that the hypotheses:It is not sunny this afternoon and it is colder than will go swimming only if it is we do not go swimming, then we will take a canoe we take a canoe trip, then we will be home by to the conclusion:We will be home by the steps:1 Translate the statements into proposional a formal Proof , a sequence of steps that state hypotheses orapply Inference Rules to previous Discrete Structures Winter 2010.