##
This **preview** shows page *1-2-16-17-18-34-35*
out of 35 **pages**.

*View Full Document*

End of preview. Want to read all 35 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

1CS 2710 Foundations of AICS 2710 Foundations of AILecture 8Milos [email protected] Sennott SquarePropositional logicCS 2710 Foundations of AIKnowledge representation2CS 2710 Foundations of AIKnowledge-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 2710 Foundations of AIExample: MYCIN• MYCIN: an expert system for diagnosis of bacterial infections• Knowledge base represents– Facts about a specific patient case – Rules describing relations between entities in the bacterial infection domain• Inference engine:– manipulates the facts and known relations to answer diagnostic queries (consistent with findings and rules)1. The stain of the organism is gram-positive, and2. The morphology of the organism is coccus, and3. The growth conformation of the organism is chainsthe identity of the organism is streptococcusIfThen3CS 2710 Foundations of AIKnowledge 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 logicCS 2710 Foundations of AILogicA 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→4CS 2710 Foundations of AIExample of logicLanguage of numerical constraints:• A sentence:• An interpretation:• Valuation (meaning) function V:zx ≤+ 3zx,- variable symbols (primitives in the language)2,5 == zxVariables mapped to specific real numbers ),3( IzxV ≤+is False for I:2,5==zx10,5==zxis True for I: I:CS 2710 Foundations of AITypes of logic• Different types of logics possible:– Propositional logic– First-order logic– Temporal logic– Numerical constraints logic– Map-coloring logicIn the following: • Propositional logic.– Formal language for making logical inferences– Foundations of propositional logic: George Boole (1854)5CS 2710 Foundations of AIPropositional logic. Syntax• Propositional logic P:– defines a language for symbolic reasoning• Proposition: a statement that is either true or false• Examples of propositions: – Pitt is located in the Oakland section of Pittsburgh.– France is in Europe.– It rains outside.– 2 is a prime number and 6 is a prime– How are you? Not a proposition. CS 2710 Foundations of AIPropositional 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:⇔⇒∨∧¬ ,,,,6CS 2710 Foundations of AIPropositional 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 2710 Foundations of AIPropositional 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 sentences7CS 2710 Foundations of AISemantic: 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 2710 Foundations of AISemantic: 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) = False8CS 2710 Foundations of AISemantics: 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 2710 Foundations of AISemantics: 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 TrueTrueTrueTrue9CS 2710 Foundations of AITranslation Assume the following sentences:• It is not sunny this afternoon and it is colder than yesterday.• We will go swimming only if it is sunny.• If we do not go swimming then we will take a canoe trip. • If we take a canoe trip, then we will be home by sunset.Denote:• p = It is sunny this afternoon• q = it is colder than yesterday• r = We will go swimming • s= we will take a canoe trip• t= We will be

View Full Document