# Unit III AIR- Logic and Reasoning

Views:

Category: Education

## Presentation Description

Knowledge Based Reasoning: Agents, Facets of Knowledge. Logic and Inferences: Formal Logic, Propositional and First Order Logic, Resolution in Propositional and First Order Logic, Deductive Retrieval, Backward Chaining, Second order Logic. Knowledge Representation: Conceptual Dependency, Frames, Semantic nets.

## Presentation Transcript

### slide 1:

Unit III: Logic and Reasoning Reference: Artificial Intelligence by Stuart Russell and Peter Norvig

### slide 2:

7/31/2018 KNOWLEDGE REASONING AND PLANNING 2  Knowledge Based Reasoning:  Logic and Inferences:  Knowledge Representation Index

### slide 3:

Knowledge Representation and Reasoning Intelligent agents should have capacity for:  Perceiving: that is acquiring information from environment  Knowledge Representation: that is representing its understanding of the world  Reasoning: that is inferring the implications of what it knows and of the choices it has and  Acting: that is choosing what it want to do and carry it out. 3 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 4:

Knowledge bases  The central component of a knowledge-based agent is its knowledge base or KB.  Informally a knowledge base is a set of sentences.  Here "sentence" is used as a technical term. It is related but is not identical to the sentences of English and other natural languages.  Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world. 5 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 5:

Knowledge bases  The agent maintains a knowledge base KB  KNOWLEDGE which may initially contain some background knowledge.  Each time the agent program is called it does three things.  First it TELLS the knowledge base what it perceives.  Second it ASKS the knowledge base what action it should perform.  Third the agent records its choice with TELL and executes the action.  The second TELL is necessary to let the knowledge base know that the hypothetical action has actually been executed. 6 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 6:

A simple knowledge-based agent  The agent must be able to:  Percept  Represent  Reasoning  Action. 7 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 7:

Wumpus World  Performance Measure • Gold +1000 Death – 1000 • Step -1 Use arrow -10  Environment • Square adjacent to the Wumpus are smelly • Squares adjacent to the pit are breezy • Glitter iff gold is in the same square • Shooting kills Wumpus if you are facing it • Shooting uses up the only arrow • Grabbing picks up the gold if in the same square  Actuators • Left turn right turn forward grab release shoot  Sensors • Breeze glitter and smell 9 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 8:

Wumpus World Characterization of Wumpus World  Observable • partial only local perception  Deterministic • Yes outcomes are specified  Episodic • No sequential at the level of actions  Static • Yes Wumpus and pits do not move  Discrete • Yes  Single Agent • Yes 10 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 9:

Logic in general  Logics are formal languages for representing information such that conclusions can be drawn  Syntax defines the sentences in the language  Semantics define the "meaning" of sentences  i.e. define truth of a sentence in a world  E.g. the language of arithmetic  x+2 ≥ y is a sentence x2+y is not a sentence  x+2 ≥ y is true iff the number x+2 is no less than the number y  x+2 ≥ y is true in a world where x 7 y 1  x+2 ≥ y is false in a world where x 0 y 6 20 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 10:

Reasoning  process of constructing new configurations sentences from old ones  proper reasoning ensures that the new configurations represent facts that actually follow from the facts that the old configurations represent  this relationship is called entailment and can be expressed as KB | alpha  knowledge base KB entails the sentence alpha 21 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 11:

Inference Methods  an inference procedure can do one of two things:  given a knowledge base KB it can derive new sentences  that are supposedly entailed by KB KB |-  KB |   given a knowledge base KB and another sentence alpha it can report whether or not alpha is entailed by KB KB   KB |   an inference procedure that generates only entailed sentences is called sound or truth-preserving  the record of operation of a sound inference procedure is called a proof  an inference procedure is complete if it can find a proof for any sentence that is entailed 22 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 12:

Big Ideas  Logic is a great knowledge representation language for many AI problems  Propositional logic is the simple foundation and fine for some AI problems  First order logic FOL is much more expressive as a KR language and more commonly used in AI 23 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 13:

Propositional logic  Logical constants: true false  Propositional symbols: P Q... atomic sentences  Wrapping parentheses: …  Sentences are combined by connectives:  and conjunction  or disjunction  implies implication / conditional  is equivalent biconditional  not negation  Literal: atomic sentence or negated atomic sentence P  P 24 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 14:

Propositional logic: Syntax  Propositional logic is the simplest logic – illustrates basic ideas  The proposition symbols P 1 P 2 etc are sentences  If S is a sentence S is a sentence negation  If S 1 and S 2 are sentences S 1  S 2 is a sentence conjunction  If S 1 and S 2 are sentences S 1  S 2 is a sentence disjunction  If S 1 and S 2 are sentences S 1  S 2 is a sentence implication  If S 1 and S 2 are sentences S 1  S 2 is a sentence biconditional 25 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 15:

Propositional logic: Semantics Each model specifies true/false for each proposition symbol E.g. P 12 P 22 P 31 false true false With these symbols 8 possible models can be enumerated automatically. S is true iff S is false S 1  S 2 is true iff S 1 is true and S 2 is true S 1  S 2 is true iff S 1 is true or S 2 is true S 1  S 2 is true iff S 1 is false or S 2 is true i.e. is false iff S 1 is true and S 2 is false S 1  S 2 is true iff S 1 S 2 is true andS 2 S 1 is true Simple recursive process evaluates an arbitrary sentence e.g. P 12  P 22  P 31 true  true  false true  true true Rules for evaluating truth with respect to a model m: 26 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 16:

On the implies connective: P  Q  Note that  is a logical connective  So P Q is a logical sentence and has a truth value i.e. is either true or false  If we add this sentence to the KB it can be used by an inference rule Modes Ponens to derive/infer/prove Q if P is also in the KB  Given a KB where PTrue and QTrue we can also derive/infer/prove that P Q is True 27 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 17:

P  Q  When is P Q true Check all that apply  PQtrue  PQfalse  Ptrue Qfalse  Pfalse Qtrue 28 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 18:

P  Q  When is P Q true Check all that apply  PQtrue  PQfalse  Ptrue Qfalse  Pfalse Qtrue  We can get this from the truth table for   Note: in FOL it’s much harder to prove that a conditional true. ✔ ✔ ✔ 29 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 19:

Truth tables  Truth tables are used to define logical connectives and to determine when a complex sentence is true given the values of the symbols in it Truth tables for the five logical connectives 30 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 20:

31 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 21:

Examples of PL sentences  P  Q  R “If it is hot and humid then it is raining”  Q  P “If it is humid then it is hot”  Q “It is humid.”  We’re free to choose better symbols btw: Ho “It is hot” Hu “It is humid” R “It is raining” 33 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 22:

Model for a KB  Let the KB be P Q R Q  P Q  What are the possible models Consider all possible assignments of T|F to P Q and R and check truth tables  FFF: OK  FFT: OK  FTF: NO  FTT: NO  TFF: OK  TFT: OK  TTF: NO  TTT: OK  If KB is P Q R Q  P Q then the only model is TTT P: it’s hot Q: it’s humid R: it’s raining 34 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 23:

35 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 24:

Inference  KB ├ i α sentence α can be derived from KB by procedure i  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. 36 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 25:

Inference rules  Logical inference creates new sentences that logically follow from a set of sentences KB  An inference rule is sound if every sentence X it produces when operating on a KB logically follows from the KB  i.e. inference rule creates no contradictions  An inference rule is complete if it can produce every expression that logically follows from is entailed by the KB. 37 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 26:

Resolution  A KB is actually a set of sentences all of which are true i.e. a conjunction of sentences.  To use resolution put KB into conjunctive normal form CNF  A sentence expressed as a conjunction of disjunctions of literals is said to be in conjunctive normal form.  Convertion to CNF by using the following equivalences 1. A ↔ B A-B ∧ B-A 2. A →B ￢A ∨ B 3. ￢A ∧ B ￢A ∨ ￢B 4. ￢A ∨ B ￢A ∧ ￢B 5. ￢￢A A 6. A ∨ B ∧ C A ∨ B ∧ A ∨ C 40 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 27:

A→B→C ￢A→B ∨ C 2 ￢ ￢A ∨ B ∨ C 3 A ∧ ￢B ∨ C 4 A ∨ C ∧ ￢B ∨ C 6 A→B ∧ C ∧ B ∧ C→A 1 ￢A ∨ B ∧ C ∧ ￢B ∧ C ∨ A 2 ￢A ∨ B ∧ C ∧ ￢B ∨ ￢C ∨ A 3 ￢A ∨ B ∧ ￢A ∨ C ∧ ￢B ∨ ￢C ∨ A 6 A further example follows: A↔ B ∧ C For example we will convert A →B→C to CNF: 44 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 28:

Horn sentences  A Horn sentence or Horn clause has the form: P1  P2  P3 ...  Pn  Qm where n0 m in01  Note: a conjunction of 0 or more symbols to left of  and 0-1 symbols to right  A Horn clause or Horn sentence is a clause that has at most one positive literal. Hence the following Horn clause takes the following form: • A ∨ ￢B ∨ ￢C ∨ ￢D ∨ ￢E • can be written as: B ∧ C ∧ D ∧ E→A • In Prolog: can be written as A :− B C D E 45 KNOWLEDGE REASONING AND PLANNING 7/31/2018 P  Q P  Q

### slide 29:

Horn sentences • Horn clauses can take three forms: • Clause with one positive literal and one or more negative literals is called a rule relation. A ∨ ￢B ∨ ￢C ∨ ￢D ∨ ￢E • A clause with no negative literals is called a fact: A : − • Finally a clause with no positive literal is called a goal or a headless clause: : − B C D E 46 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 30:

Artificial Intelligence: First-Order Logic 47 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 31:

Contents • More on Representation • Syntax and Semantics of First-Order Logic • Using First Order Logic • Knowledge Engineering in First-Order Logic 48 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 32:

First-Order Logic • AKA First-Order Predicate Logic • AKA First-Order Predicate Calculus • Much more powerful than propositional logic • Greater expressive power than propositional logic • Allows for facts objects and relations • In programming terms allows classes functions and variables 49 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 33:

Truth in First-Order Logic • Sentences are true with respect to a model and an interpretation • Model contains 1 object domain elements and relations among them • Interpretation specifies referents for – constant symbols - objects – predicate symbols - relations – function symbols - functional relations • An atomic sentence predicate term 1 …term n is true iff the objects referred to by term 1 …term n are in the relation referred to by predicate 50 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 34:

Syntax of First-Order Logic • Constants KingJohn KingRamA … • Predicates Brother … • Functions Sqrt LeftArmOf … • Variables x y a b … • Connectives   ¬   • Equality • Quantifiers  51 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 35:

Components of First-Order Logic • Term – Constant e.g. Red – Function of constant e.g. ColorBlock1 • Atomic Sentence – Predicate relating objects no variable • Brother John Richard • Married MotherJohn FatherJohn • Complex Sentences – Atomic sentences + logical connectives • Brother John Richard Brother John FatherJohn • BrotherLeftLegRichard J ohn • BrotherRichard John A Brother John Richard • King Richard V King John • King Richard  King John • 52 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 36:

Components of First-Order Logic • Quantifiers – Each quantifier defines a variable for the duration of the following expression and indicates the truth of the expression… • Universal quantifier “for all”  – The expression is true for every possible value of the variable • Existential quantifier “there exists”  – The expression is true for at least one value of the variable 53 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 37:

First-Order Logic Example 54 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 38:

Universal Quantification •  variables sentence • x P is true in a model m iff P with x being each possible object in the model • x Kingx  Personx is true iff Kingx  Personx 55 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 39:

A Common Mistake to Avoid •  variables sentence • Typically  is the main connective with  • Common mistake: using  as the main connective with  • x Kingx  Personx • x Kingx  Personx 56 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 40:

Existential Quantification •  variables sentence •  x P is true in a model m iff P with x being at least one possible object in the model •  x Crownx A OnHead x John – Richard the Lionheart is a crown  Richard the Lionheart on Johns head – King John is a crown  King John is on Johns head – Richards left leg is a crown  Richards left leg is on Johns head – Johns left leg is a crown  Johns left leg is on Johns head – The crown is a crown  the crown is on Johns head. 57 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 41:

Another Common Mistake to Avoid • Typically  is the main connective with  • Common mistake: using  as the main connective with   x Crownx A OnHead x John  x Crownx  OnHead x John 58 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 42:

Examples • Everyone likes McDonalds – x likesx McDonalds • Someone likes McDonalds – x likesx McDonalds • All children like McDonalds – x childx  likesx McDonalds • Everyone likes McDonalds unless they are allergic to it – x likesx McDonalds  allergicx McDonalds – x allergic x McDonalds  likesx McDonalds 59 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 43:

Properties of Quantifiers • x y is the same as y x – x y Brotherx y  Siblingx y. – x y Siblingx y  Sibling yx. • x y is the same as y x • x y is not the same as y x – x y Lovesx y • “There is a person who loves everyone in the world” – y x Lovesx y • “Everyone in the world is loved by at least one person” 60 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 44:

Nesting Quantifiers • Everyone likes some kind of food y x foodx  likesy x • There is a kind of food that everyone likes x y foodx  likesy x • Someone likes all kinds of food y x foodx  likesy x • Every food has someone who likes it x y foodx  likesy x 61 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 45:

Fun with Sentences • One’s mother is one’s female parent xy Motherxy  Femalex  Parentxy • A first cousin is a child of a parent’s sibling xy FirstCousinxy  pps Parentpx  Siblingpsp  Parentpsy 62 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 46:

Equality • We allow the usual infix operator – FatherJohn Henry – x siblingx y  xy • Example: –  x y Brotherx R ichard A Brothery Richard  ¬ xy 63 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 47:

Interacting with FOL KBs • Tell the system assertions – Facts : • Tell KB person John – Rules: • Tell KB x personx  likesx McDonalds • Ask questions – Ask KB personJohn – Ask KB likesJohn McDonalds – Ask KB likesx McDonalds 64 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 48:

Unification 66 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 49:

Unification • We can get the inference immediately if we can find a substitution θ such that Kingx and Greedyx match KingJohn and Greedyy θ x/Johny/John works Unifyαβ θ if αθ βθ p q θ KnowsJohnx KnowsJohnJane KnowsJohnx KnowsyOJ KnowsJohnx KnowsyMothery KnowsJohnx KnowsxOJ Standardizing apart eliminates overlap of variables e.g. Knowsz 17 OJ 67 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 50:

Unification • We can get the inference immediately if we can find a substitution θ such that Kingx and Greedyx match KingJohn and Greedyy θ x/Johny/John works Unifyαβ θ if αθ βθ p q θ KnowsJohnx KnowsJohnJane x/Jane KnowsJohnx KnowsyOJ KnowsJohnx KnowsyMothery KnowsJohnx KnowsxOJ • Standardizing apart eliminates overlap of variables e.g. Knowsz 17 OJ 68 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 51:

Unification • We can get the inference immediately if we can find a substitution θ such that Kingx and Greedyx match KingJohn and Greedyy θ x/Johny/John works Unifyαβ θ if αθ βθ p q θ KnowsJohnx KnowsJohnJane x/Jane KnowsJohnx KnowsyOJ x/OJy/John KnowsJohnx KnowsyMothery KnowsJohnx KnowsxOJ • Standardizing apart eliminates overlap of variables e.g. Knowsz 17 OJ 69 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 52:

Unification • finding substitutions that make different logical expressions look identical Unifyαβ θ if αθ βθ p q θ KnowsJohnx KnowsJohnJane x/Jane KnowsJohnx KnowsyOJ x/OJy/John KnowsJohnx KnowsyMothery y/Johnx/MotherJohn KnowsJohnx KnowsxOJ • Standardizing apart eliminates overlap of variables e.g. Knowsz 17 OJ 70 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 53:

Unification • We can get the inference immediately if we can find a substitution θ such that Kingx and Greedyx match KingJohn and Greedyy θ x/Johny/John works Unifyαβ θ if αθ βθ p q θ KnowsJohnx KnowsJohnJane x/Jane KnowsJohnx KnowsyOJ x/OJy/John KnowsJohnx KnowsyMothery y/Johnx/MotherJohn KnowsJohnx KnowsxOJ fail • Standardizing apart eliminates overlap of variables e.g. Knowsz 17 OJ 71 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 54:

Unification • To unify KnowsJohnx and Knowsyz θ y/John x/z or θ y/John x/John z/John • The first unifier is more general than the second. • There is a single most general unifier MGU that is unique up to renaming of variables. MGU y/John x/z 72 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 55:

Forward Chaining Forward Chaining • Start with atomic sentences in the KB and apply Modus Ponens in the forward direction adding new atomic sentences until no further inferences can be made. 75 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 56:

FC: Example Knowledge Base • The law says that it is a crime for an American to sell weapons to hostile nations. The country Nono an enemy America has some missiles and all of its missiles were sold to it by Col. West who is an American. • Prove that Col. West is a criminal. 77 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 57:

FC: Example Knowledge Base …it is a crime for an American to sell weapons to hostile nations Americanx Weapony Sellsxyz Hostilez  Criminalx Nono…has some missiles x OwnsNono x  Missilesx OwnsNono M 1 and MissleM 1 …all of its missiles were sold to it by Col. West x Misslex  OwnsNono x  Sells West x Nono Missiles are weapons Misslex  Weaponx 78 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 58:

FC: Example Knowledge Base An enemy of America counts as “hostile” Enemy x America  Hostilex Col. West who is an American American Col. West The country Nono an enemy of America EnemyNono America 79 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 59:

FC: Example Knowledge Base 80 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 60:

FC: Example Knowledge Base 81 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 61:

FC: Example Knowledge Base 82 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 62:

Efficient Forward Chaining Order conjuncts appropriately ◦ E.g. most constrained variable Don’t generate redundant facts each new fact should depend on at least one newly generated fact. ◦ Production systems ◦ RETE matching ◦ CLIPS 83 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 63:

Forward Chaining Algorithm 84 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 64:

Backward chaining Idea: work backwards from the query q:  Idea: Check whether a particular fact q is true. Backward Chaining  Given a fact q to be “proven” 1. See if q is already in the KB. If so return TRUE. 2. Find all implications I whose conclusion “matches” q. 3. Recursively establish the premises of all I in I via backward chaining.  Avoids inferring unrelated facts. 85 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 65:

Forward and backward chaining  Horn Form restricted KB conjunction of Horn clauses  Horn clause  proposition symbol or  conjunction of symbols  symbol  E.g. C  B  A  C  D  B  Modus Ponens for Horn Form: complete for Horn KBs α 1 … α n α 1  …  α n  β β  Can be used with forward chaining or backward chaining.  These algorithms are very natural and run in linear time. 86 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 66:

Forward vs. backward chaining  FC is data-driven automatic unconscious processing  e.g. object recognition routine decisions  May do lots of work that is irrelevant to the goal  BC is goal-driven appropriate for problem-solving  e.g. Where are my keys  Complexity of BC can be much less than linear in size of KB 87 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 67:

Logic Programming Basis: • Prolog programs are sets of definite clauses written in a notation some what different from standard first-order logic. • Prolog uses uppercase letters for variables and lowercase for constants. • Clauses are written with the head preceding the body " : -" is used for left implication commas separate literals in the body and a period marks the end of a sentence: Programming set of clauses head :- literal1 … literaln criminalX :- americanX weaponY sellsX Y Z hostileZ 88 KNOWLEDGE REASONING AND PLANNING 7/31/2018

### slide 68:

Semantic Nets Frames

### slide 69:

Knowledge Representation as a medium for human expression An intelligent system must have KRs that can be interpreted by humans. – We need to be able to encode information in the knowledge base without significant effort. – We need to be able to understand what the system knows and how it draws its conclusions.

### slide 70:

Knowledge Representation Logic prepositional predicate Network representation ◦ Semantic nets Structured representation ◦ Frames

### slide 71:

Semantic Networks First introduced by Quillian back in the late-60s M. Ross Quillian. "Semantic Memories" In M. M. Minsky editor Semantic Information Processing pages 216-270. Cambridge MA: MIT Press 1968 Semantic network is simple representation scheme which uses a graph of labeled nodes and labeled directed arcs to encode knowledge ◦ Nodes – objects concepts events ◦ Arcs – relationships between nodes Graphical depiction associated with semantic networks is a big reason for their popularity

### slide 72:

Inheritance Inheritance is one of the main kind of reasoning done in semantic nets The ISA is a relation is often used to link a class and its superclass. Some links e.g. haspart are inherited along ISA paths The semantics of a semantic net can be relatively informal or very formal ◦ Often defined at the implementation level

### slide 73:

Advantages of Semantic nets Easy to visualize Formal definitions of semantic networks have been developed. Related knowledge is easily clustered. Efficient in space requirements ◦ Objects represented only once ◦ Relationships handled by pointers

### slide 74:

Frames Frames – semantic net with properties A frame represents an entity as a set of slots attributes and associated values A frame can represent a specific entry or a general concept Frames are implicitly associated with one another because the value of a slot can be another frame Book Frame Slot  Filler •Title  AI. A modern Approach •Author  Russell Norvig •Year  2003 3 components of a frame • frame name • attributes slots • values fillers: list of values range string etc.

### slide 75:

Inheritance Similar to Object-Oriented programming paradigm Hotel Room •what  room •where hotel •contains  –hotel chair –hotel phone –hotel bed Hotel Chair •what  chair •height 20-40cm •legs  4 Hotel Phone •what  phone •billing  guest Hotel Bed •what  bed •size king •part  mattress Mattress •price  100