Truth Table Method and Propositional ProofsDeductionLogical EntailmentTruth Table MethodExampleSlide 6Slide 7ProblemPatternsRules of InferenceRule InstancesSound Rules of InferenceProof (Version 1)Slide 14ErrorSlide 16Axiom SchemataRules and SchemataValid Axiom SchemataStandard Axiom SchemataSample ProofProof (Official Version)ProvabilitySoundness and CompletenessTruth Tables and ProofsMetatheoremsProof Without Deduction TheoremProof Using Deduction TheoremTA Appeasement RulesTruth Table MethodandPropositional ProofsComputational Logic Lecture 3Michael Genesereth Spring 20052DeductionIn deduction, the conclusion is true whenever the premises are true.Premise: pConclusion: (p q)Premise: p Non-Conclusion: (p q)Premises: p, qConclusion: (p q)3Logical EntailmentA set of premises logically entails a conclusion (written as |= ) if and only if every interpretation that satisfies the premises also satisfies the conclusion.{p} |= (p q){p} |# (p q){p,q} |= (p q)4Truth Table MethodWe can check for logical entailment by comparing tables of all possible interpretations.In the first table, eliminate all rows that do not satisfy premises.In the second table, eliminate all rows that do not satisfy the conclusion.If the remaining rows in the first table are a subset of the remaining rows in the second table, then the premises logically entail the conclusion.5ExampleDoes p logically entail (p q)?p q1 11 00 10 0p q1 11 00 10 06ExampleDoes p logically entail (p q)?p q1 11 00 10 0p q1 11 00 10 0Does {p,q} logically entail (p q)?7ExampleIf Mary loves Pat, then Mary loves Quincy.If it is Monday, then Mary loves Pat or Quincy.If it is Monday, does Mary love Pat?m p q1 1 1 1 0 1 0 1 1 0 0 10 0 0m p q1 1 1 1 0 1 0 1 10 1 00 0 10 0 08ProblemThere can be many, many interpretations for a Propositional Language.Remember that, for a language with n constants, there are 2n possible interpretations.Sometimes there are many constants among premises that are irrelevant to the conclusion. Much wasted work.Answer: Proofs9PatternsA pattern is a parameterized expression, i.e. an expression satisfying the grammatical rules of our language except for the occurrence of meta-variables (Greek letters) in place of various subparts of the expression.Sample Pattern: ( )Instance:p (q p)Instance:(p r) ((pq) (p r))10Rules of InferenceA rule of inference is a rule of reasoning consisting of one set of sentence patterns, called premises, and a second set of sentence patterns, called conclusions.ϕ ⇒ ψϕψ11Rule InstancesAn instance of a rule of inference is a rule in which all meta-variables have been consistently replaced by expressions in such a way that all premises and conclusions are syntactically legal sentences.wet⇒ slipperywetslippery(p⇒ q) ⇒ rp⇒ qrraining⇒ wetrainingwetp⇒ (q⇒ r)pq⇒ r12Sound Rules of InferenceA rule of inference is sound if and only if the premises in any instance of the rule logically entail the conclusions.Modus Ponens (MP) Modus Tolens (MT)Equivalence Elimination (EE) Double Negation (DN)ϕ ⇒ ψϕψϕ ⇒ ψ¬ψ¬ϕ¬¬ϕϕϕ ⇔ ψϕ ⇒ ψψ ⇒ ϕ13Proof (Version 1)A proof of a conclusion from a set of premises is a sequence of sentences terminating in the conclusion in which each item is either:1. a premise2. the result of applying a rule of inference to earlier items in sequence.14ExampleWhen it is raining, the ground is wet. When the ground is wet, it is slippery. It is raining. Prove that it is slippery.1. raining⇒ wet Premise2. wet⇒ slippery Premise3. raining Premise4. wet MP :1,35. slippery MP : 2,415ErrorNote: Rules of inference apply only to top-level sentences in a proof. Sometimes works but sometimes fails. No! No!1. raining⇒ cloudy Premise2. raining⇒ wet Premise3. cloudy⇒ wet MP : 1,216ExampleHeads you win. Tails I lose. Suppose the coin comes up tails. Show that you win.1. h⇒ y Premise2. t⇒ ¬m Premise3. h⇔ ¬t Premise4. y⇔ ¬m Premise5. t Premise6. ¬m MP :2,57. y⇒ ¬m EE : 48. ¬m⇒ y EE : 49. y MP :8,617Axiom SchemataFact: If a sentence is valid, then it is true under all interpretations. Consequently, there should be a proof without making any assumptions at all.Fact: (p (q p)) is a valid sentence.Problem: Prove (p (q p)).Solution: We need some rules of inference without premises to get started.An axiom schema is sentence pattern construed as a rule of inference without premises.18Rules and SchemataAxiom Schemata as Rules of Inference ( )Rules of Inference as Axiom Schemata ( ) ( )Note: Of course, we must keep a least one rule of inference to use the schemata. By convention, we retain Modus Ponens.ϕ ⇒ (ψ ⇒ ϕ)ϕ ⇒ ψ¬ψ¬ϕ19Valid Axiom SchemataA valid axiom schema is a sentence pattern denoting an infinite set of sentences, all of which are valid. ( )20Standard Axiom SchemataII: ( )ID: ( ( )) (( ) ( ))CR: ( ) (( ) )( ) (( ) )EQ: ( ) ( )( ) ( )( ) (( ) ( ))OQ: ( ) ( )( ) ( )( ) ( )21Sample ProofWhenever p is true, q is true. Whenever q is true, r is true. Prove that, whenever p is true, r is true.1. p⇒ q Premise2. q ⇒ r Premise3. (q⇒ r)⇒ (p⇒ (q⇒ r)) II4. p⇒ (q⇒ r) MP : 3,25. (p ⇒ (q⇒ r))⇒ ((p⇒ q) ⇒ (p⇒ r)) ID6. (p ⇒ q)⇒ (p⇒ r) MP : 5,47. p⇒ r MP : 6,122Proof (Official Version)A proof of a conclusion from a set of premises is a sequence of sentences terminating in the conclusion in which each item is either:1. a premise2. An instance of an axiom schema3. the result of applying a rule of inference to earlier items in sequence.23ProvabilityA conclusion is said to be provable from a set of premises (written |- ) if and only if there is a finite proof of the conclusion from the premises using only Modus Ponens and the Standard Axiom Schemata.24Soundness and CompletenessSoundness: Our proof system is sound, i.e. if the conclusion is provable from the premises, then the premises propositionally entail the conclusion.( |- ) ( |= )
View Full Document
Unlocking...