Today’s topicsProof TerminologyMore Proof TerminologyInference Rules - General FormInference Rules & ImplicationsSome Inference RulesModus Ponens & TollensSyllogism Inference RulesFormal ProofsFormal Proof ExampleProof Example cont.Slide 12Inference Rules for QuantifiersCommon FallaciesCircular ReasoningA Correct ProofA More Verbose VersionProof Methods for ImplicationsDirect Proof ExampleIndirect Proof ExampleVacuous Proof ExampleTrivial Proof ExampleProof by ContradictionProof by Contradiction ExampleReview: Proof Methods So FarProving ExistentialsConstructive Existence ProofAnother Constructive Existence ProofThe proof...Nonconstructive Existence ProofThe proof, using proof by cases...The Halting Problem (Turing‘36)The halting problem: writing doesHaltConsider the class Confuse.javaLimits on ProofsMore Proof ExamplesAnswerAnswer cont…The Proof in Gory DetailAnother exampleSlide 41Another ExampleSlide 43What you might writeWhat next?More writing…Finishing the proof.Example wrong answerCompSci 102 © Michael Frank 3.1Today’s topics•Proof techniquesProof techniques–Indirect, by cases, and direct–Rules of logical inference–Correct & fallacious proofs•Reading: Section 1.5Reading: Section 1.5•UpcomingUpcoming–Sets and FunctionsSets and FunctionsCompSci 102 © Michael Frank 3.2Proof Terminology•TheoremTheorem–A statement that has been proven to be true.A statement that has been proven to be true.•AxiomsAxioms, , postulatespostulates, , hypotheseshypotheses,, premises premises–Assumptions (often unproven) defining the Assumptions (often unproven) defining the structures about which we are reasoning.structures about which we are reasoning.•Rules of inferenceRules of inference–Patterns of logically valid deductions from Patterns of logically valid deductions from hypotheses to conclusions. hypotheses to conclusions.CompSci 102 © Michael Frank 3.3More Proof Terminology•LemmaLemma - - A minor theorem used as a stepping-A minor theorem used as a stepping-stone to proving a major theorem.stone to proving a major theorem.•CorollaryCorollary - - A minor theorem proved as an easy A minor theorem proved as an easy consequence of a major theorem.consequence of a major theorem.•ConjectureConjecture - - A statement whose truth value has A statement whose truth value has not been proven.not been proven. (A conjecture may be widely (A conjecture may be widely believed to be true, regardless.)believed to be true, regardless.)•TheoryTheory – – The set of all theorems that can be The set of all theorems that can be proven from a given set of axioms.proven from a given set of axioms.CompSci 102 © Michael Frank 3.4Inference Rules - General Form•An An Inference RuleInference Rule is is –A pattern establishing that if we know that a set A pattern establishing that if we know that a set of of antecedentantecedent statements of certain forms are all statements of certain forms are all true, then we can validly deduce that a certain true, then we can validly deduce that a certain related related consequentconsequent statement is true. statement is true. • antecedent 1antecedent 1 antecedent 2 … antecedent 2 … consequent consequent ““” means “therefore”” means “therefore”CompSci 102 © Michael Frank 3.5Inference Rules & Implications•Each valid logical inference rule Each valid logical inference rule corresponds to an implication that is a corresponds to an implication that is a tautology.tautology.• antecedent 1 antecedent 1 Inference ruleInference rule antecedent 2 … antecedent 2 … consequentconsequent•Corresponding tautology: Corresponding tautology: ((((ante. 1ante. 1) ) ( (ante. 2ante. 2) ) …) …) consequentconsequentCompSci 102 © Michael Frank 3.6Some Inference Rules• ppRule of AdditionRule of Addition ppqq• ppqqRule of SimplificationRule of Simplification pp• ppRule of ConjunctionRule of Conjunction qq ppqqCompSci 102 © Michael Frank 3.7Modus Ponens & Tollens• ppRule of Rule of modus ponensmodus ponensppqq (a.k.a. (a.k.a. law of detachmentlaw of detachment))qq• qqppqq Rule of Rule of modus tollensmodus tollens pp“the mode of affirming”“the mode of denying”CompSci 102 © Michael Frank 3.8Syllogism Inference Rules• ppqqRule of hypotheticalRule of hypothetical qqrrsyllogismsyllogismpprr•p p qqRule of disjunctiveRule of disjunctive ppsyllogismsyllogism qqAristotle(ca. 384-322 B.C.)CompSci 102 © Michael Frank 3.9Formal Proofs•A formal proof of a conclusion A formal proof of a conclusion CC, given , given premises premises pp11, , pp22,…,…,,ppnn consists of a sequence consists of a sequence of of stepssteps, each of which applies some , each of which applies some inference rule to premises or previously-inference rule to premises or previously-proven statements (proven statements (antecedentsantecedents) to yield a ) to yield a new true statement (the new true statement (the consequentconsequent).).•A proof demonstrates that A proof demonstrates that ifif the premises are the premises are true, true, thenthen the conclusion is true. the conclusion is true.CompSci 102 © Michael Frank 3.10Formal Proof Example•Suppose we have the following premises:Suppose we have the following premises:“It is not sunny and it is cold.”“It is not sunny and it is cold.”“We will swim only if it is sunny.”“We will swim only if it is sunny.”“If we do not swim, then we will canoe.”“If we do not swim, then we will canoe.”“If we canoe, then we will be home early.”“If we canoe, then we will be home early.”•Given these premises, prove the theoremGiven these premises, prove the theorem“We will be home early”“We will be home early” using inference rules. using inference rules.CompSci 102 © Michael Frank 3.11Proof Example cont.•Let us adopt the following abbreviations:Let us adopt the following abbreviations:–sunny sunny = = “It is sunny”“It is sunny”; ; cold cold = = “It is cold”“It is cold”; ; swim swim = = “We will swim”“We will swim”; ; canoe canoe = = “We will “We will canoe”canoe”; ; early early = = “We will be home early”“We will be home early”..•Then, the premises can be written as:Then, the
View Full Document
Unlocking...