1CS 1571 Intro to AIM. HauskrechtCS 1571 Introduction to AILecture 14Milos [email protected] Sennott SquarePropositional logic II CS 1571 Intro to AIM. HauskrechtAnnouncements• Homework assignment 5 is out– Deadline extended till Monday, October 23– Tree.cpp now implements ‘stochastic’ minimax• No new homework assignment• Midterm exam:– Wednesday, October 25, 2006Course web page:http://www.cs.pitt.edu/~milos/courses/cs1571/2CS 1571 Intro to AIM. HauskrechtKnowledge-based agent• Knowledge base (KB):– A set of sentences that describe facts about the world in some formal (representational) language – Domain specific• Inference engine:– A set of procedures that use the representational language to infer new facts from known ones or answer a variety of KB queries. Inferences typically require search. – Domain independentKnowledge baseInference engineCS 1571 Intro to AIM. HauskrechtKnowledge representation• The objective of knowledge representation is to express the knowledge about the world in a computer-tractable form• Key aspects of knowledge representation languages:– Syntax: describes how sentences are formed in the language– Semantics: describes the meaning of sentences, what is it the sentence refers to in the real world– Computational aspect: describes how sentences and objects are manipulated in concordance with semanticalconventionsMany KB systems rely on some variant of logic3CS 1571 Intro to AIM. HauskrechtLogicA formal language for expressing knowledge and ways of reasoning.Logic is defined by:• A set of sentences– A sentence is constructed from a set of primitives according to syntax rules.• A set of interpretations– An interpretation gives a semantic to primitives. It associates primitives with values. • The valuation (meaning) function V– Assigns a value (typically the truth value) to a given sentence under some interpretationinterpretasentence:×V },{tion FalseTrue→CS 1571 Intro to AIM. HauskrechtPropositional logic. Syntax• Formally propositional logic P:– Is defined by Syntax+interpretation+semantics of PSyntax:• Symbols (alphabet) in P:– Constants: True, False– Propositional symbolsExamples: • P• Pitt is located in the Oakland section of Pittsburgh.,• It rains outside, etc.– A set of connectives:⇔⇒∨∧¬ ,,,,4CS 1571 Intro to AIM. HauskrechtPropositional logic. SyntaxSentences in the propositional logic:• Atomic sentences:– Constructed from constants and propositional symbols– True, False are (atomic) sentences–or Light in the room is on, It rains outside are (atomic) sentences • Composite sentences:– Constructed from valid sentences via connectives– If are sentences then orare sentences QP ,BA ,)( BA ∧ )( BA ∨A¬ )( BA⇔)( BA ⇒)()( BABA¬∨∧∨CS 1571 Intro to AIM. HauskrechtPropositional logic. Semantics.The semantic gives the meaning to sentences.the semantics in the propositional logic is defined by:1. Interpretation of propositional symbols and constants– Semantics of atomic sentences2. Through the meaning of connectives– Meaning (semantics) of composite sentences5CS 1571 Intro to AIM. HauskrechtSemantic: propositional symbolsA propositional symbol• a statement about the world that is either true or falseExamples: – Pitt is located in the Oakland section of Pittsburgh– It rains outside– Light in the room is on•An interpretation maps symbols to one of the two values: True (T), or False (F), depending on whether the symbol is satisfied in the worldI: Light in the room is on -> True, It rains outside -> FalseI’: Light in the room is on -> False, It rains outside -> FalseCS 1571 Intro to AIM. HauskrechtSemantic: propositional symbolsThe meaning (value) of the propositional symbol for a specific interpretation is given by its interpretation I: Light in the room is on -> True, It rains outside -> FalseV(Light in the room is on, I) = TrueI’: Light in the room is on -> False, It rains outside -> FalseV(Light in the room is on, I’) = FalseV( It rains outside, I) = False6CS 1571 Intro to AIM. HauskrechtSemantics: constants• The meaning (truth) of constants:– True and False constants are always (under any interpretation) assigned the corresponding True,False valueV(True, I) = TrueV(False, I) = FalseFor any interpretation ICS 1571 Intro to AIM. HauskrechtSemantics: composite sentences.• The meaning (truth value) of complex propositional sentences.– Determined using the standard rules of logic:QP∧P QP¬ QP ∨ QP ⇒ QP ⇔TrueTrue True True True TrueTrue FalseFalseFalse FalseFalse FalseFalseFalse False False FalseFalse FalseTrueTrueTrueTrue TrueTrueTrueTrue7CS 1571 Intro to AIM. HauskrechtModel, validity and satisfiability•A model (in logic): An interpretation is a model for a set of sentences if it assigns true to each sentence in the set.• A sentence is satisfiable if it has a model;– There is at least one interpretation under which the sentence can evaluate to True.• A sentence is valid if it is True in all interpretations– i.e., if its negation is not satisfiable (leads to contradiction)PQQP ∨QQP¬∧∨ )(TrueTrue True TrueTrueTrue FalseFalseFalse False FalseTrueTrueTrueTrueTruePQQP ⇒¬∧∨ ))((TrueFalseFalseFalseCS 1571 Intro to AIM. HauskrechtEntailment• Entailment reflects the relation of one fact in the world following from the others• Entailment• Knowledge base KB entails sentence if and only ifis true in all worlds where KB is trueα=|KBαα8CS 1571 Intro to AIM. HauskrechtInference.Inference is a process by which conclusions are reached. • We want to implement the inference process on a computer !!Assume an inference procedure i that • derives a sentence from the KB :Properties of the inference procedure in terms of entailment• Soundness: An inference procedure is sound• Completeness: An inference procedure is completeαiKBαα=|KBαiKBIf then it is true thatIf then it is true thatα=|KBαiKBCS 1571 Intro to AIM. HauskrechtLogical inference problemLogical inference problem:• Given:– a knowledge base KB (a set of sentences) and – a sentence (called a theorem), • Does a KB semantically entail ?In other words: In all interpretations in which sentences in the KB are true, is also true?Question: Is there a procedure (program) that can decide this problem in a finite number of