1Lecture 3 • 16.825 Techniques in Artificial IntelligenceLogic• When we have too many states, we want a convenient way of dealing with sets of states.• The sentence “It’s raining” stands for all the states of the world in which it is raining.• Logic provides a way of manipulating big collections of sets by manipulating short descriptions instead.• Instead of thinking about all the ways a world could be, we’re going to work in the a language of expressions that describe those sets.Lecture 3 • 2What is a logic?• A formal language• Syntax – what expressions are legal• Semantics – what legal expressions mean• Proof system – a way of manipulating syntactic expressions to get other syntactic expressions (which will tell us something new)• Why proofs? Two kinds of inferences an agent might want to make:• Multiple percepts => conclusions about the world• Current state & operator => properties of next stateLecture 3 • 3Propositional Logic SyntaxSyntax: what you’re allowed to write• for (thing t = fizz; t == fuzz; t++){ … }• Colorless green ideas sleep furiously.Sentences (wffs: well formed formulas)•trueand false are sentences• Propositional variables are sentences: P,Q,R,Z•If φ and ψ are sentences, then so are (φ), ¬φ, φ ∧ ψ, φ ∨ ψ, φ→ψ, φ↔ψ• Nothing else is a sentenceLecture 3 • 4Precedence↔→∨∧¬highestlowest(A → (B ∨ C)) ↔ DA → B ∨ C ↔ D(A ∧ B) → (C ∨ D)A ∧ B → C ∨ DA ∨ (B ∧ C)A ∨ B ∧ C• Precedence rules enable “shorthand” form of sentences, but formally only the fully parenthesized form is legal.• Syntactically ambiguous forms allowed in shorthand only when semantically equivalent: A ∧ B ∧ C is equivalent to (A ∧ B) ∧ C and A ∧ (B ∧ C) Lecture 3 • 5Recitation Exercises: Part 1Which of these are legal sentences?Give fully parenthesized expressions for the legal sentences. (If there is more than one solution, just pick any one).Lecture 3 • 6Semantics• Meaning of a sentence is truth value {t, f}• Interpretation is an assignment of truth values to the propositional variables• riφ [Sentence φ is t in interpretation i ]• iφ[Sentence φ is f in interpretation i ]Semantic Rules• ritrue for all i• ifalse for all i [the sentence false has truth value f in all interpret.]• ri¬φ if and only if iφ• riφ ∧ ψ if and only if riφ and riψ [conjunction]• riφ ∨ ψ if and only if riφ or riψ [disjunction]• ri P iff i(P) = t2Lecture 3 • 7Some important shorthandLecture 3 • 8Some important shorthand• φ → ψ ≡ ¬ φ ∨ ψ [conditional, implication]• φ ↔ ψ ≡ (φ → ψ) ∧ (ψ → φ) [biconditional, equivalence]antecedent →→→→ consequentTruth TablesttftQ → PtfftP ↔ QtttfttftffftttfttftfftffP → QP ∨ QP ∧ Q¬ PQPNote that implication is not “causality”, if P is f then P → Q is tLecture 3 • 9Terminology• A sentence is valid iff its truth value is t in all interpretations (r φ)Valid sentences: true, ¬ false, P ∨ ¬ P• A sentence is satisfiable iff its truth value is t in at least one interpretationSatisfiable sentences: P, true, ¬ P• A sentence is unsatisfiable iff its truth value is f in all interpretationsUnsatisfiable sentences: P ∧ ¬ P, false, ¬ trueAll are finitely decidable.Lecture 3 • 10Models and Entailment• An interpretation i is a modelof a sentence φ iff riφ• A set of sentences KB entails φiff every model of KB is also a model of φSentences SentencesInterpretations InterpretationssemanticssemanticsentailssubsetKB = A ∧ Bφ = BUBA ∧ BKB r φ iff r KB → φKB entails φ if and only if (KB → φ) is validA ∧∧∧∧ B rrrr BLecture 3 • 11Examplessmoke → smokesmoke ∨¬smokevalidsmoke → firesatisfiable, not valid(s → f) → (¬ s → ¬ f)satisfiable, not validsmoke = t, fire = fInterpretation that make sentence’s truth value = fSentence Valid?s = f, f = ts → f = t, ¬ s → ¬ f = f(s → f) → (¬ f → ¬ s)validcontrapositiveb ∨ d ∨ (b → d)validb ∨ d ∨ ¬ b ∨ dLecture 3 • 12Recitation Exercises: Part IIFor each of the following sentences, say whether it is valid, unsatisfiable, or satisfiable but not valid. If it is neither valid nor unsatisfiable, provide an interpretation in which it is true and another in which it is