Truth Table MethodandPropositional ProofsComputational LogicLecture 3Michael GeneserethSpring 20022DeductionIn deduction, the conclusion is true whenever the premises aretrue.Premise: pConclusion: (p ∨ q)Premise: pNon-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 thepremises 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 allpossible interpretations.In the first table, eliminate all rows that do not satisfypremises.In the second table, eliminate all rows that do not satisfy theconclusion.If the remaining rows in the first table are a subset of theremaining rows in the second table, then the premises logicallyentail 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)?7ProblemThere can be many, many interpretations for a PropositionalLanguage.Remember that, for a language with n constants, there are 2npossible interpretations.Sometimes there are many constants among premises that areirrelevant to the conclusion. Much wasted work.Answer: Proofs8PatternsA pattern is a parameterized expression, i.e. an expressionsatisfying the grammatical rules of our language except forthe occurrence of meta-variables (Greek letters) in place ofvarious subparts of the expression.Sample Pattern:ϕ ⇒ (ψ ⇒ ϕ)Instance:p ⇒ (q ⇒ p)Instance:(p ⇒ r) ⇒ ((p⇒q) ⇒ (p ⇒ r))9Rules of InferenceA rule of inference is a rule of reasoning consisting of oneset of sentence patterns, called premises, and a second setof sentence patterns, called conclusions.ϕ ⇒ψϕψ10Rule InstancesAn instance of a rule of inference is a rule in which all meta-variables have been consistently replaced by expressions insuch a way that all premises and conclusions are syntacticallylegal sentences.wet ⇒ slipperywetslippery(p ⇒ q) ⇒ rp ⇒ qrraining ⇒ wetrainingwetp ⇒ (q ⇒ r)pq ⇒ r11Sound Rules of InferenceA rule of inference is sound if and only if the premises in anyinstance of the rule logically entail the conclusions.Modus Ponens (MP)Modus Tolens (MT)Equivalence Elimination (EE)Double Negation (DN)ϕ ⇒ψϕψϕ ⇒ψ¬ψ¬ϕ¬¬ϕϕϕ ⇔ψϕ ⇒ψψ ⇒ϕ12Proof (Version 1)A proof of a conclusion from a set of premises is a sequenceof sentences terminating in the conclusion in which eachitem is either:1. a premise2. the result of applying a rule of inference to earlier items insequence.13ExampleWhen 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 ⇒ wetPremise2. wet ⇒ slipperyPremise3. rainingPremise4. wet MP :1,35. slippery MP : 2,414ErrorNote: Rules of inference apply only to top-level sentences in aproof. Sometimes works but sometimes fails.No! No!1. raining ⇒cloudyPremise2. raining ⇒ wetPremise3.cloudy⇒ wet MP : 1,215ExampleHeads you win. Tails I lose. Suppose the coin comes uptails. Show that you win.1. h ⇒ yPremise2. t ⇒ ¬mPremise3. h ⇔ ¬tPremise4. y ⇔ ¬mPremise5. tPremise6. ¬m MP : 2,57. y ⇒ ¬m EE : 48. ¬m ⇒ y EE : 49. y MP :8,616Axiom SchemataFact: If a sentence is valid, then it is true under allinterpretations. Consequently, there should be a proof withoutmaking 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 toget started.An axiom schema is sentence pattern construed as a rule ofinference without premises.17Rules 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 touse the schemata. By convention, we retain Modus Ponens.ϕ ⇒ (ψ ⇒ϕ)ϕ ⇒ψ¬ψ¬ϕ18Valid Axiom SchemataA valid axiom schema is a sentence pattern denoting an infiniteset of sentences, all of which are valid.ϕ ⇒ (ψ ⇒ ϕ)19Standard Axiom SchemataII: ϕ ⇒ (ψ ⇒ ϕ)ID:(ϕ ⇒ (ψ ⇒ χ)) ⇒ ((ϕ ⇒ ψ) ⇒ (ϕ ⇒ χ))CR: (¬ψ ⇒ ϕ) ⇒ ((¬ψ ⇒ ¬ϕ) ⇒ ψ)(ψ ⇒ ϕ) ⇒ ((ψ ⇒ ¬ϕ) ⇒ ¬ψ)EQ: (ϕ ⇔ ψ) ⇒ (ϕ ⇒ ψ)(ϕ ⇔ ψ) ⇒ (ψ ⇒ ϕ)(ϕ ⇒ ψ) ⇒ ((ψ ⇒ ϕ) ⇒ (ϕ ⇔ ψ))OQ: (ϕ ⇐ ψ) ⇔ (ψ ⇒ ϕ)(ϕ ∨ ψ) ⇔ (¬ϕ ⇒ ψ)(ϕ ∧ ψ) ⇔ ¬(¬ϕ ∨ ¬ψ)20Sample 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 ⇒ qPremise2. q ⇒ rPremise3. (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,121Proof (Official Version)A proof of a conclusion from a set of premises is a sequenceof sentences terminating in the conclusion in which eachitem is either:1. a premise2. An instance of an axiom schema3. the result of applying a rule of inference to earlier items insequence.22ProvabilityA conclusion is said to be provable from a set of premises(written ∆ |- ϕ) if and only if there is a finite proof of theconclusion from the premises using only Modus Ponens and theStandard Axiom Schemata.23Soundness and CompletenessSoundness: Our proof system is sound, i.e. if the conclusion isprovable from the premises, then the premises propositionallyentail the conclusion.(∆ |- ϕ) ⇒ (∆ |= ϕ)Completeness: Our proof system is complete, i.e. if the premisespropositionally entail the conclusion, then the conclusion isprovable from the premises.(∆ |= ϕ) ⇒ (∆ |- ϕ)24Truth Tables and ProofsThe truth table method and the proof method succeed in exactlythe same cases.On large problems, the proof method often takes fewer stepsthan the truth table method. However, in the worst case, theproof method may take just as many or more steps to find ananswer as the truth table method.Usually, proofs are much smaller than the corresponding truthtables. So writing an argument to convince others does not takeas much space.25MetatheoremsDeduction Theorem: ∆ |- (ϕ ⇒ ψ) if and only if ∆∪{ϕ} |- ψ.Equivalence Theorem: ∆ |- (ϕ ⇔ ψ) and ∆ |- χ, then it is thecase that ∆ |- χϕ←ψ.26Proof Without Deduction
View Full Document
Unlocking...