Propositional LogicAmbiguitySlide 3Slide 4ComplexityMisleading RepresentationPropositional ConstantsCompound SentencesCompound Sentences (concluded)Parenthesis RemovalPrecedenceExampleSlide 13Propositional InterpretationSentential InterpretationOperator SemanticsOperator Semantics (continued)Slide 18Operator Semantics (concluded)EvaluationSlide 21Multiple InterpretationsTruth TablesProperties of SentencesSlide 25Example of ValidityMore ValiditiesEvaluation Versus SatisfactionSlide 29SatisfactionSatisfaction ExampleSatisfaction Example (continued)Satisfaction Example (concluded)The Big GameBasic IdeaThe Big Game SolvedPropositional LogicComputational Logic Lecture 2Michael Genesereth Autumn 200801/14/19 2AmbiguityLeland Stanford Junior University Leland-Stanford Junior-University? Leland-Stanford-Junior University?01/14/19 3AmbiguityThere’s a girl in the room with a telescope.01/14/19 4AmbiguityLettuce won’t turn brown if you put your headin a plastic bag before placing it in the refrigerator.Hershey bars protest.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 Shaefer01/14/19 5ComplexityThe cherry blossoms in the spring … sank.01/14/19 6Misleading RepresentationChampagne is better than soda.Soda is better than swill. Therefore, champagne is better than swill.Bad sex is better than nothing.Nothing is better than good sex. Therefore, bad sex is better than good sex.01/14/19 7Propositional ConstantsExamples:rainingr32ainingrAiNiNgrainingorsnowingNon-Examples:324567raining.or.snowing01/14/19 8Compound SentencesNegations:raining The 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.01/14/19 9Compound Sentences (concluded)Implications:(raining cloudy) The left argument of an implication is the antecedent. The right argument 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)01/14/19 10Parenthesis RemovalDropping Parentheses is good:(p q) p qBut it can lead to ambiguities:((p q) r) p q r(p (q r)) p q r01/14/19 11PrecedenceParentheses can be dropped when the structure of an expression can be determined by precedence. NB: An operand associates with operator of higher precedence. If surrounded by operators of equal precedence, the operand associates with the operator to the right.p q r p q r p qp q r p q r01/14/19 12Exampleo (p q) (p q) a r ob p qs (o r) (o r) c a bpqrscoab01/14/19 13Example(r ((p q) (p q))) (p q)pqr01/14/19 14Propositional InterpretationA propositional interpretation is an association between the propositional constants in a propositional language and the truth values T or F.pi ⏐ → ⏐ T pi=Tqi ⏐ → ⏐ F qi=Fri ⏐ → ⏐ T ri=T01/14/19 15Sentential InterpretationA sentential interpretation is an association between the sentences in a propositional language and the truth values T or F.pi = T (p q)i = Tqi = F (q r)i = Tri = T ((p q) (q r))i = TA propositional interpretation defines a sentential interpretation by application of operator semantics.01/14/19 16Operator SemanticsNegation:For example, if the interpretation of p is F, then the interpretation of p is T.For example, if the interpretation of (pq) is T, then the interpretation of (pq) is F.φ ¬φT FF T01/14/19 17Operator Semantics (continued)Conjunction: Disjunction:NB: The type of disjunction here is called inclusive or, which says that a disjunction is true if and only if at least one of its disjuncts is true. This contrasts with exclusive or, which says that a disjunction is true if and only if an odd number of its disjuncts is true.φ ψ φ∧ψT T TT F FF T FF F Fφ ψ φ∨ψT T TT F TF T TF F F01/14/19 18Operator Semantics (continued)Implication: Reduction:NB: The semantics of implication here is called material implication. Any implication is true if the antecedent is false, whether or not there is a connection to the consequent.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 T01/14/19 19Operator Semantics (concluded)Equivalence:φ ψ φ ⇔ ψT T TT F FF T FF F T01/14/19 20EvaluationInterpretation i:Compound Sentence(p q) (q r)pi= Tqi= Fri= T01/14/19 21Examplepi = Tqi = Tri = T(r ((p q) (p q))) (p q)pqr01/14/19 22Multiple InterpretationsLogic does not prescribe which interpretation is “correct”. In the absence of additional information, one interpretation is as good as another.Interpretation i Interpretation jExamples: Different days of the week Different locations Beliefs of different peoplepi= Tqi= Fri= Tpj= Fqj= Frj= T01/14/19 23Truth Tables€ p q rT T TT T FT F TT F FF T TF T FF F TF F FA truth table is a table of all possible interpretationsfor the propositional constants in a language.One column per constant.One row per interpretation.For a language with n constants,there are 2n interpretations.01/14/19 24Properties 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 andonly if no interpretation satisfies it.ValidContingentUnsatisfiable01/14/19 25Properties of SentencesA sentences is satisfiable if and onlyif it is either valid or contingent.A sentences is falsifiable if and onlyif it is contingent or unsatisfiable.ValidContingentUnsatisfiable01/14/19 26Example 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 001/14/19 27More ValiditiesDouble Negation:p pdeMorgan's Laws:(pq) (pq)(pq) (pq)Implication Introduction:p (q p)Implication Distribution(p (q r)) ((p q) (p r))01/14/19 28Evaluation Versus SatisfactionEvaluation:Satisfaction:pi= Tqi= F(p∨q)i= T(¬q)i= T(p∨q)i=
View Full Document
Unlocking...