Propositional LogicComputational LogicLecture 2Michael Genesereth Autumn 200210/10/02 2Grammatical ComplexityThe dog chased the cat.The dog that ate the rat chased the cat.The cherry blossoms in the spring … sank.10/10/02 3AmbiguityLeland Stanford Junior University Leland-Stanford Junior-University? Leland-Stanford-Junior University?There’s a girl in the room with a telescope.10/10/02 4AmbiguityLettuce won’t turn brown if you put your headIn a plastic bag before placing it in therefrigerator.The manager of a nudist colony complains thata hole was cut in the wall surrounding the camp.Police are looking into it.from Misteaks in Printedited by Kermit Shaefer10/10/02 5Propositional ConstantsExamples:rainingr32ainingrAiNiNgrainingorsnowingNon-Examples:324567raining.or.snowing10/10/02 6Compound SentencesNegations:¬rainingThe argument of a negation is called the target.Conjunctions:(raining∧snowing)The arguments of a conjunction are called conjuncts.Disjunctions:(raining∨snowing)The arguments of a disjunction are called disjuncts.10/10/02 7Compound Sentences (concluded)Implications:(raining ⇒ cloudy)The left argument of an implication is the antecedent.The right argument of an implication is the consequent.Reductions:(cloudy ⇐ raining)The left argument of a reduction is the consequent.The right argument of a reduction is the antecedent.Equivalences:(cloudy ⇔ raining)10/10/02 8Parenthesis RemovalDropping Parentheses is good:(p ∧ q) → p ∧ qBut it can lead to ambiguities:((p ∨ q) ∧ r) → p ∧ q ∨ r(p ∨ (q ∧ r)) → p ∧ q ∨ r10/10/02 9PrecedenceParentheses can be dropped when the structure of anexpression can be determined on the basis of precedence.¬∧∨⇒ ⇐ ⇔NB: An operand associates with operator of higher precedence.If surrounded by operators of equal precedence, the operandassociates with the operator to the right.p ∧ q ∨ r p ⇒ q ⇒ r ¬p ∧ qp ∨ q ∧ r p ⇒ q ⇐ r10/10/02 10Propositional Logic InterpretationA propositional logic interpretation is an association betweenthe propositional constants in a propositional language and thetruth values T or F.The notion of interpretation can be extended to all sentences byapplication of operator semantics.pi → T pi= Tqi → F qi= Fri → T ri= T10/10/02 11Operator SemanticsNegation:For example, if the interpretation of p is F, then theinterpretation of ¬p is T.For example, if the interpretation of ¬p is T, then theinterpretation of ¬¬p is F.φ ¬φT FF T10/10/02 12Operator Semantics (continued)Conjunction:Disjunction:NB: The semantics of disjunction here is often called inclusiveor, which says that a disjunction is true if and only if at leastone of its disjuncts is true. This is in contrast with exclusiveor, according to which a disjunction is true if and only if anodd number of its disjuncts is true. What is the truth table forexclusive or?φ ψ φ ∧ψT T TT F FF T FF F Fφ ψ φ ∨ψT T TT F TF T TF F F10/10/02 13Operator Semantics (continued)Implication:Reduction:NB: The semantics of implication here is called materialimplication. It has the peculiar characteristic that anyimplication is true if the antecedent is false, whether or notthere is a connection to the consequent. For example, thefollowing is a true sentence.If George Washington is alive, I am a billionaire.φ ψ φ ⇒ψT T TT F FF T TF F Tφ ψ φ ⇐ψT T TT F TF T FF F T10/10/02 14Operator Semantics (concluded)Equivalence:φ ψ φ ⇔ ψT T TT F FF T FF F T10/10/02 15EvaluationInterpretation i:Compound Sentence(p ∨ q) ∧ (¬q ∨ r)pi= Tqi= Fri= T10/10/02 16Multiple InterpretationsLogic does not prescribe which interpretation is “correct”. Inthe absence of additional information, one interpretation is asgood as another.Interpretation i Interpretation jExamples: Different days of the week Different locations Beliefs of different peoplepi= Tqi= Fri= Tpj= Fqj= Frj= T10/10/02 17Truth Tablesp q r1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0A truth table is a table of all possible interpretations for thepropositional constants in a language.One column per constant.One row per interpretation.For a language with n constants,there are 2n interpretations.10/10/02 18Evaluation and DisambiguationEvaluation:Disambiguation:pi= Tqi= F(p∨ q)i= T(¬q)i= T(p∨ q)i= T(¬q)i= Tpi= Tqi= F10/10/02 19Disambiguationp q r1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0By crossing out rows, it is possible to find interpretationsimplicit in a set of sentences.10/10/02 20Disambiguationp q r1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0××By crossing out rows, it is possible to find interpretationsimplicit in a set of sentences.q⇒r10/10/02 21Disambiguationp q r1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0××××By crossing out rows, it is possible to find interpretationsimplicit in a set of sentences.q⇒rp ⇒q∧r10/10/02 22Disambiguationp q r1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 0×××××××By crossing out rows, it is possible to find interpretationsimplicit in a set of sentences.q⇒rp ⇒q∧r¬r10/10/02 23Properties of SentencesA sentence is valid if and only ifevery interpretation satisfies it.A sentence is contingent if and only ifsome interpretation satisfies it andsome interpretation falsifies it.A sentence is unsatisfiable if and only ifno interpretation satisfies it.ValidContingentUnsatisfiable10/10/02 24Example of Validityp q r ( p ⇒ q) (q⇒ r) ( p⇒ q) ∨ (q ⇒ r)1 1 11 1 01 0 11 0 00 1 10 1 00 0 10 0 010/10/02 25More ValiditiesDouble Negation:p ⇔ ¬¬pdeMorgan's Laws:¬(p∧q) ⇔ (¬p∨¬q)¬(p∨q) ⇔ (¬p∧¬q)Implication Introduction:p ⇒ (q ⇒ p)Implication Distribution(p ⇒ (q ⇒ r)) ⇒ ((p ⇒ q) ⇒ (p ⇒ r))10/10/02 26The Big GameStanford people always tell the truth, and Berkeley peoplealways lie. Unfortunately, by looking at a person, you cannottell whether he is from Stanford or Berkeley.You come to a fork in the road and want to get to the footballstadium down one fork. However, you do not know which totake. There is a person standing there. What single questioncan you ask him to help you decide which fork to take?10/10/02 27Basic Idealeftsu Question ResponseT TT FF TF F10/10/02 28The Big Game SolvedQuestion: The left road the way to the stadium if and only ifyou from Stanford. Is that correct?left⇔
View Full Document
Unlocking...