Transcript m5zn_b5de286616a4fe3

Chapter 7
Instructor : Miss Mahreen Nasir
Outline
Knowledge-based agents
Logic in general
Propositional (Boolean) logic
Equivalence, validity, satisfiability
Predicate Logic
Sememtic Networks
Frames
Logical Agents
Knowledge-based agents – agents that have
an explicit representation of knowledge that
can be reasoned with.
 These agents can manipulate this knowledge
to infer new things at the “knowledge level”
Knowledge Based Agent
 The central component a knowledge-based agent is
its Knowledge base (KB) : set of sentences in a
formal language (i.e. a list of facts that are known
to the agent).

Each sentence is expressed in a language called a
knowledge representation language, and represent
some assertion about the world
Knowledge Bases
 Knowledge base = set of sentences in a formal language
 Declarative approach to building an agent (or other system):
 Tell it what it needs to know
 Then it can Ask itself what to do - answers should follow from
the KB
 Agents can be viewed at :
 Knowledge level - i.e., what they know, what its goals are, in
order to fix its behavior, regardless of how implemented
 Implementation level
 i.e., data structures in KB and algorithms that manipulate
them
 Each time the agent program is called:
1.It TELLs the KB what it perceive.
2.It ASKs the KB what action it should perform (query).
3.The agent program TELLs the knowledge base which action
was chosen and the agent executes the action.
A Simple knowledge based Agent
 The agent must be able to:
 Represent states, actions, etc.
 Incorporate new percepts
 Update internal representations of the world
 Deduce hidden properties of the world
 Deduce appropriate actions
What is a Logic?
Logics are formal languages for representing information
such that conclusions can be drawn.
Have a syntax and semantics
Syntax
How
to make sentences, valid strings of sentences
Rules
for constructing legal sentences in the logic
Semantics
Define
How
the meaning of the sentences
we interpret sentences in the logic
Logic-Syntax & Semantics
Example: Arithmatic language
Syntax: x+y=4 a well formed sentence
X2y+= not a well formed sentence
x + 2 >= y is true if and only if the number of x + 2 is no less than
the number y
 x +2 >= y is true in a world (or model) where x = 7, y = 1
 x +2 >= y is false in a world (or model) where x = 0, y = 6
Propositional Logic
Propositions: assertions about an aspect of a world
that can be assigned either a true or false value.
 e.g. Sky is cloudy, Sarah is happy, Is morning, P1, ..
 True, False are propositions meaning true and false
 Atoms/atomic sentences:
 composed of a single propositional symbol
e.g. Sky is cloudy
Propositional Logic
Complex Sentences:
constructed
of
simpler
sentences
using
logical
connectives (disjunction, implication, equivalence,
negation),
 e.g. Sky is cloudy ∧ Sarah is happy.
 Sentences Literals:
Either an atomic sentence (P1, positive literal) or a
negated atomic sentence (¬P1, negative literal)
Propositional Logic -Syntax
The proposition symbols P1, P2 etc are (atomic)
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)
Propositional Logic -Sementics
Each model specifies true/false for each proposition symbol
E.g.
P1,2
P2,2
P3,1
false
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
S1is 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  (true  false) = true  true = true
Truth Table for Connectives
English to Propositional Formulae
Example 1 :
“It is not the case that the Sky is Blue ” :¬ B
( alternatively teh sky is not blue )
“The Sky is Blue and the Grass is Green ” :B ∧ G
“ Either teh sky is Blue or the Grass is Green ” :B ∨ G
“ If the Sky is Blue, then the Grass is not Green” :B→ ¬ G
“ The Sky is Blue if anf only if the Grass is Green ” :B↔ G
“ If the sky is blue,then if the Grass is not Green,the Plants
will not Grow ” :B→ ( ¬ G→ ¬ P )
English to Propositional Formulae
p = “It is below freezing”
q = “It is snowing”
It is below freezing and it is snowing
It is below freezing but not snowing
It is not below freezing and it is not snowing
It is either snowing or below freezing (or both)
If it is below freezing, it is also snowing
It is either below freezing or it is snowing,
pq
p¬q
¬p¬q
pq
p→q
((pq)¬(pq))
but it is not snowing if it is below freezing
That it is below freezing is necessary and
sufficient for it to be snowing
p↔q
Truth Table
•Truth tables can be used to test sentences for validity
• One row for each possible combination of truth values
symbols in the sentence
•Given n symbols,2^n possible
combinations of truth value assignments.
•Here each row is an interpretation
for the
Truth Tables-Implications
•Does A⇒B is equivalent to ¬A ∨ B?
•A⇒B is true iff A is false or B is true
•is false iff A is true and B is false
•Implication is used in propositional logic and predicate
logic to describe a relationship between two propositions
or sentences.
Truth Tables-Validity
Truth Tables -Satisfiability
Truth Tables-Unsatisfiability
Predicate Logic
Propositional logic combines atoms
An atom contains no propositional connectives
Have no structure (today_is_wet, john_likes_apples)
Predicates allow us to talk about objects
Properties:
is_wet(today),is _a_bird(x)
Relations:
likes(john, apples)
True or false
In predicate logic each atom is a predicate
e.g. first order logic, higher-order logic
First Order Logic
More expressive logic than propositional
Constants are objects: john, apples
Predicates are properties and relations:
likes(john, apples)
Functions transform objects:
likes(john,
Variables represenfruit_of(apple_tree))t any object:
likes(X,
apples)
Quantifiers qualify values of variables
True for all objects (Universal):
X. likes(X, apples)
Exists at least one object (Existential):
X. likes(X, apples)
Example: FOL Sentence
“Every rose has a thorn”
For all X
if
(X is a rose)
then
there exists Y
(X
has Y) and (Y is a thorn)
Example: FOL Sentence
“On Mondays and Wednesdays I go to
John’s house for dinner”

Note the change from “and” to “or”
–
Translating is problematic
Non-Logical Representations
Production rules
Semantic networks
Conceptual graphs
Frames
Logic representations have restricitions and
can be hard to work with
Production Rules
Rule set of <condition,action> pairs
“if condition then action”
Match-resolve-act cycle
Match: Agent checks if each rule’s condition holds
Resolve:
Multiple
Agent
production rules may fire at once (conflict set)
must choose rule from set (conflict resolution)
Act: If so, rule “fires” and the action is carried out
Working memory:
rule can write knowledge to working memory
knowledge may match and fire other rules
< ‫قاعدة تعيين من أزواج‬condition،action>
""‫اذا كان الشرط ثم العمل‬
-‫مباريات لحل‬ACT ‫دورة‬
Production Rules Example
IF (at bus stop AND bus arrives) THEN action(get
on the bus)
IF (on bus AND not paid AND have oyster card)
THEN action(pay with oyster) AND add(paid)
IF (on bus AND paid AND empty seat) THEN sit
down
conditions and actions must be clearly defined
can easily be expressed in first order logic!
Graphical Representation
Graphs easy to store in a computer
To be of any use must impose a formalism
Jason is 15, Bryan is 40, Arthur is 70, Jim is 74
 How old is Julia?
Semantic Networks
Because the syntax is the same
We can guess that Julia’s age is similar to
Bryan’s
Semantic Networks
 Used as an alternative to predicate logic for
knowledge representation
Knowledge is stored in the form of Graph
Nodes represent objects in the world
Arcs represent relationships between the objects
Semantic Networks
Conceptual Graphs
Semantic network where each graph represents a single proposition
Concept nodes can be
Concrete (visualisable) such as restaurant, my dog Spot
Abstract (not easily visualisable) such as anger
Edges do not have labels
Instead, conceptual relation nodes
Easy to represent relations between multiple objects
Frame Representations
Semantic networks where nodes have structure
Frame with a number of slots (age, height, ...)
Each slot stores specific item of information
When agent faces a new situation
Slots can be filled in (value may be another frame)
Filling in may trigger actions
May trigger retrieval of other frames
Inheritance of properties between frames
Very similar to objects in OOP
Example: Frame Representation