Unformatted text preview:

1Logical EntailmentComputational Logic Lecture 3Michael Genesereth Autumn 20102Logical ReasoningLogical Reasoning relates premises and conclusion does not say whether conclusion is true in general says conclusion true whenever premises are trueLeibnitz: The intellect is freed of all conception ofthe objects involved, and yet the computation yieldsthe correct result.Russell: Math may be defined as the subject inwhich we never know what we are talking about norwhether what we are saying is true.23Logical EntailmentA set of premises Δ logically entails a conclusion ϕ(written as Δ |= ϕ) if and only if every interpretationthat satisfies the premises also satisfies theconclusion.{p} |= (p ∨ q){p} |# (p ∧ q){p, q} |= (p ∧ q)4Logical Entailment ≠ Logical Equivalence{p} |= (p ∨ q){p ∨ q)} |# pAnalogy in arithmetic: inequalities rather than equations35Truth Table MethodWe can check for logical entailment by comparingtables of all possible interpretations.In the first table, eliminate all rows that do not satisfypremises.In the second table, eliminate all rows that do notsatisfy the conclusion.If the remaining rows in the first table are a subset ofthe remaining rows in the second table, then thepremises logically entail the conclusion.6ExampleDoes p logically entail (p ∨ q)?€ p qT TT FF TF F€ p qT TT FF TF F47ExampleDoes p logically entail (p ∧ q)?Does {p,q!} logically entail (p ∧ q)?€ p qT TT FF TF F€ p qT TT FF TF F8ExampleIf Mary loves Pat, then Mary loves Quincy.If it is Monday, then Mary loves Pat or Quincy.If it is Monday, does Mary love Quincy?FFFTFF×××TTF×××TFT×××TTTqpmFFFTFFFTFTTF×××TFT×××TTTqpm59Logical Entailment and SatisfiabilityTheorem: Δ |= ϕ if and only if Δ ∪ {¬ϕ} isunsatisfiable.Suppose that Δ|= ϕ. If an interpretation satisfies Δ,then it must also satisfy ϕ. But then it cannot satisfy¬ϕ. Therefore, Δ ∪ {¬ϕ} is unsatisfiable.Suppose that Δ ∪ {¬ϕ} is unsatisfiable. Then everyinterpretation that satisfies Δ must fail to satisfy ¬ϕ,i.e. it must satisfy ϕ. Therefore, Δ |= ϕ.Upshot: We can determine logical entailment bydetermining unsatisfiability.10ExampleProblem: {(p⇒q), (m ⇒ p∨q)} |= (m⇒q)?Or: Is {(p⇒q), (m ⇒ p∨q),¬(m⇒q)} unsatisfiable?FFFTFFFTFTTFFFTTFTFTTTTTqpm611ProblemThere can be many, many interpretations for aPropositional Language.Remember that, for a language with n constants, thereare! 2n possible interpretations.Sometimes there are many constants among premisesthat are irrelevant to the conclusion. Much wastedwork.Answer: Proofs12PatternsA pattern is a parameterized expression, i.e. anexpression satisfying the grammatical rules of ourlanguage except for the use of meta-variables(Greek letters) in place of various subparts of theexpression.Sample Pattern:ϕ ⇒ (ψ ⇒ ϕ)Instance:p ⇒ (q ⇒ p)Instance:(p ⇒ r) ⇒ ((p⇒q) ⇒ (p ⇒ r))713Rules of InferenceA rule of inference is a rule of reasoningconsisting of one set of sentence patterns, calledpremises, and a second set of sentence patterns,called conclusions.ϕ⇒ψϕψ14Rule InstancesAn instance of a rule of inference is a rule in whichall meta-variables have been consistently replaced byexpressions in such a way that all premises andconclusions are syntactically legal sentences.wet ⇒ slipperywetslippery( p ⇒ q) ⇒ rp ⇒ qrraining ⇒ wetrainingwetp ⇒ (q ⇒ r)pq ⇒ r815Sound Rules of InferenceA rule of inference is sound if and only if the premisesin any instance of the rule logically entail theconclusions.Modus Ponens (MP) Modus Tolens (MT)Equivalence Elimination (EE) Double Negation (DN)ϕ⇒ψϕψϕ⇒ψ¬ψ¬ϕ¬¬ϕϕϕ⇔ψϕ⇒ψψ⇒ϕ16Proof (Version 1)A proof of a conclusion from a set of premises is asequence of sentences terminating in the conclusionin which each item is either:1. a premise2. the result of applying a rule of inference to earlieritems in sequence.917ExampleWhen it is raining, the ground is wet. When theground is wet, it is slippery. It is raining. Prove thatit is slippery.1. raining ⇒ wet Premise2. wet ⇒ slippery Premise3. raining Premise4. wet MP : 1, 35. slippery MP : 2, 418ErrorNote: Rules of inference apply only to top-levelsentences in a proof. Sometimes works butsometimes fails.No! No!1. raining ⇒ cloudy Premise2. raining ⇒ wet Premise3. cloudy ⇒ wet MP : 1, 21019ExampleHeads you win. Tails I lose. Suppose the coincomes 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, 620Axiom SchemataFact: If a sentence is valid, then it is true under allinterpretations. Consequently, there should be a proofwithout 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 withoutpremises to get started.An axiom schema is sentence pattern construed as arule of inference without premises.1121Rules and SchemataAxiom Schemata as Rules of Inference ϕ ⇒ (ψ ⇒ ϕ)Rules of Inference as Axiom Schemata (ϕ ⇒ ψ) ⇒ (¬ψ ⇒ ¬ϕ)Note: Of course, we must keep a least one rule ofinference to use the schemata. By convention, weretain Modus Ponens.ϕ⇒ (ψ⇒ϕ)ϕ⇒ψ¬ψ¬ϕ22Valid Axiom SchemataA valid axiom schema is a sentence pattern denotingan infinite set of sentences, all of which are valid.Implication Introduction (II):ϕ⇒ (ψ ⇒ ϕ)ImplicationDistribution (ID):(ϕ ⇒ (ψ ⇒ χ)) ⇒ ((ϕ ⇒ ψ) ⇒ (ϕ ⇒ χ))1223Proof (Official Version)A proof of a conclusion from a set of premises is asequence of sentences terminating in the conclusionin which each item is either:1. a premise2. An instance of an axiom schema3. the result of applying a rule of inference to earlieritems in sequence.24Sample ProofWhenever p is true, q is true. Whenever q is true, r istrue. 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,11325Mendelson AxiomatizationII: ϕ ⇒ (ψ ⇒ ϕ)ID: (ϕ ⇒ (ψ ⇒ χ)) ⇒ ((ϕ ⇒ ψ) ⇒ (ϕ ⇒ χ))CR: (¬ψ ⇒ ϕ) ⇒ ((¬ψ ⇒ ¬ϕ) ⇒ ψ)Note: Mendelson’s system assumes there are only twooperators, viz. ¬ and ⇒. Fortunately, all sentences inPropositional


View Full Document

Stanford CS 157 - Logical Entailment

Documents in this Course
Lecture 1

Lecture 1

15 pages

Equality

Equality

32 pages

Lecture 19

Lecture 19

100 pages

Epilog

Epilog

29 pages

Equality

Equality

34 pages

Load more
Download Logical Entailment
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Logical Entailment and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Logical Entailment 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?