1Propositional LogicComputational Logic Lecture 2Michael Genesereth Autumn 20089/25/08 2AmbiguityThere’s a girl in the room with a telescope.29/25/08 3Compound 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/25/08 4Compound 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)39/25/08 5Parenthesis 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/25/08 6PrecedenceParentheses 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 ⇐ r49/25/08 7Exampleo ⇔ (p ∧ ¬q) ∨ (¬p ∧ q)a ⇔ r ∧ ob ⇔ p ∧ qs ⇔ (o ∧ ¬r) ∨ (¬o ∧ r)c ⇔ a ∨ bpqrscoab9/25/08 8Example(r ∧ ((p ∧ ¬q) ∨ (¬p ∧ q))) ∨ (p ∧ q)pqr59/25/08 9Propositional 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/25/08 10Sentential 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.69/25/08 11Operator 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/25/08 12Operator 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 F79/25/08 13Operator 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/25/08 14Operator Semantics (concluded)Equivalence:φ ψ φ⇔ψT T TT F FF T FF F T89/25/08 15EvaluationInterpretation i:Compound Sentence(p ∨ q) ∧ (¬q ∨ r)pi= Tqi= Fri= T9/25/08 16Examplepi = Tqi = Tri = T(r ∧ ((p ∧ ¬ q) ∨ (¬p ∧ q))) ∨ (p ∧ q)pqr99/25/08 17Multiple 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/25/08 18Truth 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.109/25/08 19Properties 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/25/08 20Properties 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}}119/25/08 21Example 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/25/08 22More 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))129/25/08 23Evaluation Versus SatisfactionEvaluation:Satisfaction:pi= Tqi= F( p ∨ q)i= T(¬q)i= T( p ∨ q)i= T(¬q)i= Tpi= Tqi= F9/25/08 24Examplepi = ?qi = ?ri = ?((r ∧ ((p ∧ ¬q) ∨ (¬p ∧ q))) ∨ (p ∧ q))i = Tpqr139/25/08 25SatisfactionMethod 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/25/08 26Satisfaction Example€ p q rT T TT T FT F TT F FF T TF T FF F TF F F××q⇒r149/25/08 27Satisfaction Example (continued)€ p q rT T TT T FT F TT F FF T TF T FF F TF F F××××q⇒rp ⇒q∧r9/25/08 28Satisfaction Example (concluded)€ p q rT T TT T FT F TT F FF T TF T FF F TF F F×××××××q⇒rp ⇒q∧r¬r159/25/08 29The Big GameStanford people always tell the truth, and Berkeleypeople always lie. Unfortunately, by looking at aperson, you cannot tell whether he is from Stanford orBerkeley.You come to a fork in the road and want to get to thefootball stadium down one fork. However, you do notknow which to take. There is a person standing there.What single question can you ask him to help youdecide which fork to take?9/25/08 30Basic Idealeft su Question ResponseT TT FF TF F169/25/08 31The Big Game SolvedQuestion: The left road the way to the stadium if andonly if you are from Stanford. Is that correct?left ⇔
View Full Document
Unlocking...