is true and Propositional logic:Semantics If 5 andS are sentences.sntence (implication) sentences,(disjunction) If s is a sentence,is a sntence (negation) The propoition etc are sentences Propositional logic:Syntax sentence o can be derived fromB by procedure Inference .. Wumpus world sentences Wumpus world sentences Truth tables for connectives .Inference KB `i α = sentence α can be derived from KB by procedure i Consequences of KB are a haystack; α is a needle. Entailment = needle in haystack; inference = finding it Soundness: i is sound if whenever KB `i α, it is also true that KB |= α Completeness: i is complete if whenever KB |= α, it is also true that KB `i α Preview: we will define a logic (first-order logic) which is expressive enough to say almost anything of interest, and for which there exists a sound and complete inference procedure. That is, the procedure will answer any question whose answer follows from what is known by the KB. Chapter 7 31 Propositional logic: Syntax Propositional logic is the simplest logic—illustrates basic ideas The proposition symbols P1, P2 etc are sentences If S is a sentence, ¬S is a sentence (negation) If S1 and S2 are sentences, S1 ∧ S2 is a sentence (conjunction) If S1 and S2 are sentences, S1 ∨ S2 is a sentence (disjunction) If S1 and S2 are sentences, S1 ⇒ S2 is a sentence (implication) If S1 and S2 are sentences, S1 ⇔ S2 is a sentence (biconditional) Chapter 7 32 Propositional logic: Semantics Each model specifies true/false for each proposition symbol E.g. P1,2 P2,2 P3,1 true true false (With these symbols, 8 possible models, can be enumerated automatically.) Rules for evaluating truth with respect to a model m: ¬S is true iff S is false S1 ∧ S2 is true iff S1 is true and S2 is true S1 ∨ S2 is true iff S1 is true or S2 is true S1 ⇒ S2 is true iff S1 is false or S2 is true i.e., is false iff S1 is true and S2 is false S1 ⇔ S2 is true iff S1 ⇒ S2 is true and S2 ⇒ S1 is true Simple recursive process evaluates an arbitrary sentence, e.g., ¬P1,2 ∧ (P2,2 ∨ P3,1) = true ∧ (false ∨ true) = true ∧ true = true Chapter 7 33 Truth tables for connectives P Q ¬P P ∧ Q P ∨ Q P⇒Q P⇔Q false false true false false true true false true true false true true false true false false false true false false true true false true true true Chapter true 7 34 Wumpus world sentences Let Pi,j be true if there is a pit in [i, j]. Let Bi,j be true if there is a breeze in [i, j]. ¬P1,1 ¬B1,1 B2,1 “Pits cause breezes in adjacent squares” Chapter 7 35 Wumpus world sentences Let Pi,j be true if there is a pit in [i, j]. Let Bi,j be true if there is a breeze in [i, j]. ¬P1,1 ¬B1,1 B2,1 “Pits cause breezes in adjacent squares” B1,1 ⇔ (P1,2 ∨ P2,1) B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1) “A square is breezy if and only if there is an adjacent pit” Chapter 7 36