# CS代考程序代写 CS 561a: Introduction to Artificial Intelligence

CS 561a: Introduction to Artificial Intelligence

CS 561, Sessions 11-12

1

Last time: Logic and Reasoning

Knowledge Base (KB): contains a set of sentences expressed using a knowledge representation language

TELL: operator to add a sentence to the KB

ASK: to query the KB

Logics are KRLs where conclusions can be drawn

Syntax

Semantics

Entailment: KB |= a iff a is true in all worlds where KB is true

Inference: KB |–i a = sentence a can be derived from KB using procedure i

Sound: whenever KB |–i a then KB |= a is true

Complete: whenever KB |= a then KB |–i a

CS 561, Sessions 11-12

2

Last Time: Syntax of propositional logic

CS 561, Sessions 11-12

3

Last Time: Semantics of Propositional logic

CS 561, Sessions 11-12

4

Last Time: Inference rules

for propositional logic

CS 561, Sessions 11-12

5

This time

First-order logic

Syntax

Semantics

Wumpus world example

Ontology (ont = ‘to be’; logica = ‘word’): kinds of things one can talk about in the language

CS 561, Sessions 11-12

6

Why first-order logic?

We saw that propositional logic is limited because it only makes the ontological commitment that the world consists of facts.

Difficult to represent even simple worlds like the Wumpus world;

e.g.,

“don’t go forward if the Wumpus is in front of you” takes 64 rules

CS 561, Sessions 11-12

7

First-order logic (FOL)

Ontological commitments:

Objects: wheel, door, body, engine, seat, car, passenger, driver

Relations: Inside(car, passenger), Beside(driver, passenger)

Functions: ColorOf(car)

Properties: Color(car), IsOpen(door), IsOn(engine)

Functions are relations with single value for each object

CS 561, Sessions 11-12

8

Semantics

there is a correspondence between

functions, which return values

predicates, which are true or false

Function: father_of(Mary) = Bill

Predicate: father_of(Mary, Bill) [true or false]

8

more formally, this is how build interpretation of whole from interpretation of parts.

predicate and relation used interchangeably; here predicate is the formal symbol and relation the real world relation

give example of tuples for functions and relations (e.g. son-of, son)

CS 561, Sessions 11-12

9

Examples:

“One plus two equals three”

Objects:

Relations:

Properties:

Functions:

“Squares neighboring the Wumpus are smelly”

Objects:

Relations:

Properties:

Functions:

CS 561, Sessions 11-12

10

Examples:

“One plus two equals three”

Objects: one, two, three, one plus two

Relations: equals

Properties: —

Functions: plus (“one plus two” is the name of the object obtained by applying function plus to one and two;

three is another name for this object)

“Squares neighboring the Wumpus are smelly”

Objects: Wumpus, square

Relations: neighboring

Properties: smelly

Functions: —

CS 561, Sessions 11-12

11

FOL: Syntax of basic elements

Constant symbols: 1, 5, A, B, USC, JPL, Alex, Manos, …

Predicate symbols: >, Friend, Student, Colleague, …

Function symbols: +, sqrt, SchoolOf, TeacherOf, ClassOf, …

Variables: x, y, z, next, first, last, …

Connectives: , , ,

Quantifiers: ,

Equality: =

CS 561, Sessions 11-12

12

FOL: Atomic sentences

AtomicSentence Predicate(Term, …) | Term = Term

Term Function(Term, …) | Constant | Variable

Examples:

SchoolOf(Manos)

Colleague(TeacherOf(Alex), TeacherOf(Manos))

>((+ x y), x)

CS 561, Sessions 11-12

13

FOL: Complex sentences

Sentence AtomicSentence

| Sentence Connective Sentence

| Quantifier Variable, … Sentence

| Sentence

| (Sentence)

Examples:

S1 S2, S1 S2, (S1 S2) S3, S1 S2, S1 S3

Colleague(Paolo, Maja) Colleague(Maja, Paolo)

Student(Alex, Paolo) Teacher(Paolo, Alex)

CS 561, Sessions 11-12

14

Semantics of atomic sentences

Sentences in FOL are interpreted with respect to a model

Model contains objects and relations among them

Terms: refer to objects (e.g., Door, Alex, StudentOf(Paolo))

Constant symbols: refer to objects

Predicate symbols: refer to relations

Function symbols: refer to functional Relations

An atomic sentence predicate(term1, …, termn) is true iff the relation referred to by predicate holds between the objects referred to by term1, …, termn

CS 561, Sessions 11-12

15

Example model

Objects: John, James, Marry, Alex, Dan, Joe, Anne, Rich

Relation: sets of tuples of objects

{

{

E.g.:

Parent relation — {

then Parent(John, James) is true

Parent(John, Marry) is false

CS 561, Sessions 11-12

16

Quantifiers

Expressing sentences about collections of objects without enumeration (naming individuals)

E.g., All Trojans are clever

Someone in the class is sleeping

Universal quantification (for all):

Existential quantification (there exists):

CS 561, Sessions 11-12

17

Universal quantification (for all):

“Every one in the cs561 class is smart”:

x In(cs561, x) Smart(x)

P corresponds to the conjunction of instantiations of P

(In(cs561, Manos) Smart(Manos))

(In(cs561, Dan) Smart(Dan))

…

(In(cs561, Bush) Smart(Bush))

CS 561, Sessions 11-12

18

Universal quantification (for all):

is a natural connective to use with

Common mistake: to use in conjunction with

e.g: x In(cs561, x) Smart(x)

means “every one is in cs561 and everyone is smart”

CS 561, Sessions 11-12

19

Existential quantification (there exists):

“Someone in the cs561 class is smart”:

x In(cs561, x) Smart(x)

P corresponds to the disjunction of instantiations of P

In(cs561, Manos) Smart(Manos)

In(cs561, Dan) Smart(Dan)

…

In(cs561, Bush) Smart(Bush)

CS 561, Sessions 11-12

20

Existential quantification (there exists):

is a natural connective to use with

Common mistake: to use in conjunction with

e.g: x In(cs561, x) Smart(x)

is true if there is anyone that is not in cs561!

(remember, false true is valid).

CS 561, Sessions 11-12

21

Properties of quantifiers

Proof?

Not all by one person but each one at least by one

CS 561, Sessions 11-12

22

Proof

In general we want to prove:

x P(x) <=> ¬ x ¬ P(x)

x P(x) = ¬(¬( x P(x))) = ¬(¬(P(x1) ^ P(x2) ^ … ^ P(xn)) ) = ¬(¬P(x1) v ¬P(x2) v … v ¬P(xn)) )

x ¬P(x) = ¬P(x1) v ¬P(x2) v … v ¬P(xn)

¬ x ¬P(x) = ¬(¬P(x1) v ¬P(x2) v … v ¬P(xn))

CS 561, Sessions 11-12

23

Example sentences

Brothers are siblings

.

Sibling is transitive

.

One’s mother is one’s sibling’s mother

.

A first cousin is a child of a parent’s sibling

.

CS 561, Sessions 11-12

24

Example sentences

Brothers are siblings

x, y Brother(x, y) Sibling(x, y)

Sibling is transitive

x, y, z Sibling(x, y) Sibling(y, z) Sibling(x, z)

One’s mother is one’s sibling’s mother

m, c, d Mother(m, c) Sibling(c, d) Mother(m, d)

A first cousin is a child of a parent’s sibling

c, d FirstCousin(c, d)

p, ps Parent(p, d) Sibling(p, ps) Child(c, ps)

CS 561, Sessions 11-12

25

Example sentences

One’s mother is one’s sibling’s mother

m, c, d Mother(m, c) Sibling(c, d) Mother(m, d)

c, d m Mother(m, c) Sibling(c, d) Mother(m, d)

c

d

m

Mother of

sibling

CS 561, Sessions 11-12

26

Translating English to FOL

Every gardener likes the sun.

x gardener(x) => likes(x,Sun)

You can fool some of the people all of the time.

x t (person(x) ^ time(t)) => can-fool(x,t)

CS 561, Sessions 11-12

27

Translating English to FOL

You can fool all of the people some of the time.

x person(x) => t time(t) ^

can-fool(x,t)

All purple mushrooms are poisonous.

x (mushroom(x) ^ purple(x)) => poisonous(x)

Caution with nested quantifiers

x y P(x,y) is the same as x ( y P(x,y)) which means “for every x, it is true that there exists y such that P(x,y)”

y x P(x,y) is the same as y ( x P(x,y)) which means “there exists a y, such that it is true that for every x P(x,y)”

CS 561, Sessions 11-12

28

CS 561, Sessions 11-12

29

Translating English to FOL…

No purple mushroom is poisonous.

¬( x) purple(x) ^ mushroom(x) ^ poisonous(x)

or, equivalently,

( x) (mushroom(x) ^ purple(x)) => ¬poisonous(x)

CS 561, Sessions 11-12

30

Translating English to FOL…

There are exactly two purple mushrooms.

( x)( y) mushroom(x) ^ purple(x) ^ mushroom(y) ^ purple(y) ^ ¬(x=y) ^ ( z) (mushroom(z) ^ purple(z)) => ((x=z) v (y=z))

Deb is not tall.

¬tall(Deb)

CS 561, Sessions 11-12

31

Translating English to FOL…

X is above Y iff X is directly on top of Y or else there is a pile of one or more other objects directly on top of one another starting with X and ending with Y.

( x)( y) above(x,y) <=> (on(x,y) v ( z) (on(x,z) ^ above(z,y)))

CS 561, Sessions 11-12

32

Equality

CS 561, Sessions 11-12

33

Higher-order logic?

First-order logic allows us to quantify over objects (= the first-order entities that exist in the world).

Higher-order logic also allows quantification over relations and functions.

e.g., “two objects are equal iff all properties applied to them are equivalent”:

x,y (x=y) ( p, p(x) p(y))

Higher-order logics are more expressive than first-order; however, so far we have little understanding on how to effectively reason with sentences in higher-order logic.

CS 561, Sessions 11-12

34

Logical agents for the Wumpus world

TELL KB what was perceived

Uses a KRL to insert new sentences, representations of facts, into KB

ASK KB what to do.

Uses logical reasoning to examine actions and select best.

Remember: generic knowledge-based agent:

CS 561, Sessions 11-12

35

Using the FOL Knowledge Base

Set of solutions

CS 561, Sessions 11-12

36

Wumpus world, FOL Knowledge Base

CS 561, Sessions 11-12

37

Deducing hidden properties

CS 561, Sessions 11-12

38

Situation calculus

CS 561, Sessions 11-12

39

Describing actions

May result in too many frame axioms

CS 561, Sessions 11-12

40

Describing actions (cont’d)

CS 561, Sessions 11-12

41

Planning

CS 561, Sessions 11-12

42

Generating action sequences

[ ] = empty plan

Recursively continue until it gets to empty plan [ ]

CS 561, Sessions 11-12

43

Summary

/docProps/thumbnail.jpeg