1Propositional LogicComputational Logic Lecture 2Michael Genesereth Autumn 20099/22/09 2AmbiguityThere’s a girl in the room with a telescope.29/22/09 3ComplexityThe cherry blossoms in the spring … sank.9/22/09 4Misleading 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.39/22/09 5Propositional LanguagesThe signature of a propositional language is a set ofprimitive objects, called propositional constants.The sentences in a propositional language consist of(1) the propositional constants in the language’ssignature together with (2) compound sentencescomposed of simpler sentences. (Details to follow.)9/22/09 6Proposition ConstantsProposition constants are written as strings ofalphnumeric characters beginning with a lower caseletter.Examples:rainingr32ainingrAiNiNgrainingorsnowingNon-Examples:324567raining.or.snowing49/22/09 7Compound 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.9/22/09 8Compound 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)59/22/09 9Parenthesis RemovalDropping Parentheses is good:(p ∧ q) → p ∧ qBut it can lead to ambiguities:((p ∨ q) ∧ r) → p ∧ q ∨ r(p ∨ (q ∧ r)) → p ∧ q ∨ r9/22/09 10PrecedenceParentheses can be dropped when the structure of anexpression can be determined by precedence.¬∧∨⇒ ⇐ ⇔NB: An operand associates with operator of higherprecedence. If surrounded by operators of equalprecedence, the operand associates with the operatorto the right.p ∧ q ∨ r p ⇒ q ⇒ r ¬p ∧ qp ∨ q ∧ r p ⇒ q ⇐ r69/22/09 11Exampleo ⇔ (p ∧ ¬q) ∨ (¬p ∧ q)a ⇔ r ∧ ob ⇔ p ∧ qs ⇔ (o ∧ ¬r) ∨ (¬o ∧ r)c ⇔ a ∨ bpqrscoab9/22/09 12Example(r ∧ ((p ∧ ¬q) ∨ (¬p ∧ q))) ∨ (p ∧ q)pqr79/22/09 13Propositional InterpretationA propositional interpretation is an associationbetween the propositional constants in a propositionallanguage and the truth values T or F.pi → T pi= Tqi → F qi= Fri → T ri= T9/22/09 14Sentential InterpretationA sentential interpretation is an association betweenthe sentences in a propositional language and the truthvalues 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 sententialinterpretation by application of operator semantics.89/22/09 15Operator SemanticsNegation:For example, if the interpretation of p is F, then theinterpretation of ¬p is T.For example, if the interpretation of (p∧q) is T, thenthe interpretation of ¬(p∧q) is F.φ¬φT FF T9/22/09 16Operator Semantics (continued)Conjunction: Disjunction:NB: The type of disjunction here is called inclusiveor, which says that a disjunction is true if and only ifat least one of its disjuncts is true. This contrasts withexclusive or, which says that a disjunction is true ifand 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 F99/22/09 17Operator Semantics (continued)Implication: Reduction:NB: The semantics of implication here is calledmaterial implication. Any implication is true if theantecedent is false, whether or not there is aconnection 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 T9/22/09 18Operator Semantics (concluded)Equivalence:φ ψ φ⇔ψT T TT F FF T FF F T109/22/09 19EvaluationInterpretation i:Compound Sentence(p ∨ q) ∧ (¬q ∨ r)pi= Tqi= Fri= T9/22/09 20Examplepi = Tqi = Tri = T(r ∧ ((p ∧ ¬q) ∨ (¬p ∧ q))) ∨ (p ∧ q)pqr119/22/09 21Multiple 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= T9/22/09 22Truth 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.129/22/09 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 andonly if no interpretation satisfies it.ValidContingentUnsatisfiable9/22/09 24Properties 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.ValidContingentUnsatisfiable}}139/22/09 25Example 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 09/22/09 26More 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))149/22/09 27Evaluation Versus SatisfactionEvaluation:Satisfaction:pi= Tqi= F( p ∨ q)i= T(¬q)i= T( p ∨ q)i= T(¬q)i= Tpi= Tqi= F9/22/09 28Examplepi = ?qi = ?ri = ?((r ∧ ((p ∧ ¬q) ∨ (¬p ∧ q))) ∨ (p ∧ q))i = Tpqr159/22/09 29SatisfactionMethod to find all propositional interpretations thatsatisfy a given set of sentences:(1) Form a truth table for the propositional constants.(2) For each sentence in the set and each row in thetruth table, check whether the row satisfies thesentence. If not, cross out the row.(3) Any row remaining satisfies all sentences in theset. (Note that there might be more than one.)9/22/09 30Satisfaction Example€ p q rT T TT T FT F TT F FF T TF T FF F TF F F××q⇒r169/22/09 31Satisfaction Example (continued)€ p q rT T TT T FT F TT F
View Full Document
Unlocking...