FOL and Prolog

Information about FOL and Prolog

Published on June 15, 2007

Author: Haggrid

Source: authorstream.com

Content

First Order Logicand Prolog:  First Order Logic and Prolog Introduction to Artificial Intelligence Henry Kautz Spring 2007 First Order Logic:  First Order Logic Sentence ::= Atom | (Sentence Connective Sentence) |  Variable . Sentence |   Variable . Sentence |  Sentence Atom ::= Proposition | Predicate(Term, ...) Term ::= Constant | Variable | Function(Term, ...) First-Order Logic:  First-Order Logic All men are mortal.  x . (man(x)  mortal(x)) No man is not mortal.   x . (man(x)   mortal(x) ) Everybody has somebody they lean on.  x . (person(x)   y . (person(y)  leans_on(x,y)) A number is less than it’s successor.  n . (number(x)  less_than(x, successor(x)) ) Nothing is less than zero.   x . less_than(x, ZERO) First-Order Clausal Form:  First-Order Clausal Form Begin with universal quantifiers (implicit) Rest is a clause No , use function symbols instead Variables in each clause are unique to that clause 'x' in clause 1 is not the same 'x' as in clause 2  x . (man(x)  mortal(x)) man(x)  mortal(x) Skolem Functions:  Skolem Functions Begin with universal quantifiers (implicit) Rest is a clause No , use function symbols instead Variables in each clause are unique to that clause 'x' in clause 1 is not the same 'x' as in clause 2  x . (person(x)   y . (person(y)  leans_on(x,y))  x .  y . (person(x)  (person(y)  leans_on(x,y))  x . (person(x)  (person(f(x))  leans_on(x,f(x)))  x .  person(x)  (person(f(x))  leans_on(x,f(x))  x . ( person(x)person(f(x)))  (person(x)leans_on(x,f(x)))  x . person(x)  person(f(x))  x . person(x)  leans_on(x,f(x)) Unification:  Unification Can resolve clauses if can unify one pair of literals Same predicate, one positive, one negative Match variable(s) to other variables, constants, or complex terms (function symbols) Carry bindings on variables through to all the other literals in the result (Mortal(HENRY)) (Mortal(y)Fallible(y)) (Fallible(HENRY)) Unification with Multiple Variables:  Unification with Multiple Variables You always hurt the ones you love. Politicians love themselves. Therefore, politicians hurt themselves.  love(x,y)  hurt(x,y) politician(z)  love(z,z) politician(z)  hurt(z,z) Unification with Multiple Variables:  Unification with Multiple Variables You always hurt the ones you love. Politicians love themselves. Therefore, politicians hurt themselves.  love(x,y)  hurt(x,y) politician(z)  love(z,z) politician(w)  hurt(w,w) rename 'z' as 'w' so that no clauses have variables with the same name Why Keep Distinct Variables in Each Clause?:  Why Keep Distinct Variables in Each Clause? If you hit someone, then you hurt them. If you hurt someone, then you are bad. Therefore: If you hit someone, then you are bad.  hit(x,y)  hurt(x,y)  hurt(y,x)  bad(y) hit(x,x)  bad(x) if you hit yourself then you are bad?! Why Keep Distinct Variables in Each Clause?:  Why Keep Distinct Variables in Each Clause? If you hit someone, then you hurt them. If you hurt someone, then you are bad. Therefore: If you hit someone, then you are bad.  hit(x,y)  hurt(x,y)  hurt(w,z)  bad(w) hit(x,z)  bad(x) Unification with Function Symbols:  Unification with Function Symbols (Less(a,suc(a))) (Less(b,c) Less(c,d) Less(b,d)) (Less(b,a) Less(b,suc(a))) rename variables: (Less(e,f) Less(e,suc(f))) Less(a,suc(suc(a))) A number is less than its successor 'Less than' is transitive A number is less than the successor of its successor {c/a, d/suc(a)} {e/a,f/suc(a)} Making FOL Practical:  Making FOL Practical Barriers to using FOL: Choice of clauses to resolve Huge amount of memory to store DAG Getting useful answers to queries (not just 'yes' or 'no') PROLOG’s answers: Simple backward-chaining resolution strategy – left/right, first to last clause Tree-shaped proofs – no need to store entire proof in memory at one time Extract answers to queries by returning variable bindings happy.pl:  happy.pl happy(X) :- rich(X). happy(X) :- loves(X,Y),happy(Y). loves(X,Y) :- spouse(X,Y). loves(X,Y) :- mother(X,Y). rich(bill). spouse(melinda,bill). mother(elaine,melinda). mother(mary,bill). rich(paul). mother(barbara,henry). QUERIES: ?- happy(bill). YES ?- happy(henry). NO ?- happy(Z). Prolog Interpreter:  Prolog Interpreter binding_list disprove(literal neglit){ choose (clause c) such that (binding = unify(head(c),neglit)) if (no choice possible){ backtrack to last choice;} for (each lit in body(c)){ binding = binding U disprove(substitute(lit,binding)); } return binding; } Exercise: The Mini Zebra Puzzle:  Exercise: The Mini Zebra Puzzle There are three houses in a row on street. Each house is inhabited by a man of a different nationality, who has a different pet, and drinks a different beverage. The Spaniard own a dog. The Ukranian drinks tea. The man in the third house drinks milk. The Norwegian lives next to the tea drinker. The juice drinker owns a fox. The fox is next door to the dog. Question: Who owns the zebra? Prolog Limitations:  Prolog Limitations Only handles definite clauses (exactly one positive literal per clause) Cannot express e.g. happy(bill) v happy(henry) Tree-shaped proofs means some sub-steps may be repeatedly derived DATALOG: does forward-chaining inference and caches derived unit clauses Interpreter can get into an infinite loop if care is not taken in form andamp; order of clauses

Related presentations


Other presentations created by Haggrid

makyaj
18. 06. 2007
0 views

makyaj

2407224601
22. 04. 2008
0 views

2407224601

0616PVR76491
17. 04. 2008
0 views

0616PVR76491

DART Slideshow
17. 04. 2008
0 views

DART Slideshow

AdvFin 2008 01 Introduction
10. 04. 2008
0 views

AdvFin 2008 01 Introduction

dept revenue presentation
09. 04. 2008
0 views

dept revenue presentation

het607 m06a01
07. 04. 2008
0 views

het607 m06a01

20061116 intl ops
30. 03. 2008
0 views

20061116 intl ops

2004 AMCHAM Doorknock
27. 03. 2008
0 views

2004 AMCHAM Doorknock

pdhpe moderate
18. 06. 2007
0 views

pdhpe moderate

Where the Red Fern Grows
03. 10. 2007
0 views

Where the Red Fern Grows

tutorial 1
19. 09. 2007
0 views

tutorial 1

Future Law Enforcement ppt
19. 09. 2007
0 views

Future Law Enforcement ppt

231B 2006 Suetterlin Lec1
12. 10. 2007
0 views

231B 2006 Suetterlin Lec1

Crocodile
12. 10. 2007
0 views

Crocodile

VLSI Symp 2 10 2007
09. 10. 2007
0 views

VLSI Symp 2 10 2007

2003 08 27 Schelle Wolff Carola
24. 10. 2007
0 views

2003 08 27 Schelle Wolff Carola

875 PERL 06 mini
02. 11. 2007
0 views

875 PERL 06 mini

Where the Sidewalk Ends
26. 10. 2007
0 views

Where the Sidewalk Ends

CNV
22. 10. 2007
0 views

CNV

pfit
07. 11. 2007
0 views

pfit

scholz
16. 11. 2007
0 views

scholz

DDR Frog Licking
17. 11. 2007
0 views

DDR Frog Licking

The Suffering of Jesus
17. 08. 2007
0 views

The Suffering of Jesus

lecture5
28. 11. 2007
0 views

lecture5

ontology
11. 12. 2007
0 views

ontology

predationmurray
01. 01. 2008
0 views

predationmurray

academy mission vision
03. 01. 2008
0 views

academy mission vision

Maldives presentation
07. 08. 2007
0 views

Maldives presentation

mood disorders
07. 08. 2007
0 views

mood disorders

Loh Verma Michalowski CPS04
07. 08. 2007
0 views

Loh Verma Michalowski CPS04

Karen Middleton
07. 08. 2007
0 views

Karen Middleton

Linkage ordinal data hm
07. 08. 2007
0 views

Linkage ordinal data hm

modern Day Slavery
07. 08. 2007
0 views

modern Day Slavery

MOA Presentation Mandsager final
07. 08. 2007
0 views

MOA Presentation Mandsager final

oct15 insurance reinsurance RGA
07. 08. 2007
0 views

oct15 insurance reinsurance RGA

maldives khaleel
07. 08. 2007
0 views

maldives khaleel

peters HTC BlueGene CondorWeek
19. 09. 2007
0 views

peters HTC BlueGene CondorWeek

mostly oopsla03
19. 09. 2007
0 views

mostly oopsla03

2005 Loftus Introduced Fish
19. 11. 2007
0 views

2005 Loftus Introduced Fish

UNTITLED
07. 08. 2007
0 views

UNTITLED

knoblock
23. 10. 2007
0 views

knoblock

India US Dual Use Goldman
17. 08. 2007
0 views

India US Dual Use Goldman

RedSquare Bike Ride Eng
27. 09. 2007
0 views

RedSquare Bike Ride Eng

Financing EFA Maldives
07. 08. 2007
0 views

Financing EFA Maldives

Languages Models Factories
14. 11. 2007
0 views

Languages Models Factories

Ge11cDIfferentiation
20. 02. 2008
0 views

Ge11cDIfferentiation

1950s
24. 02. 2008
0 views

1950s

Dual Language Posterboard 2
24. 02. 2008
0 views

Dual Language Posterboard 2

200792013611855
10. 10. 2007
0 views

200792013611855

as2007 aviation careers brief
28. 02. 2008
0 views

as2007 aviation careers brief

BiodieselFuelQuality pt1
29. 02. 2008
0 views

BiodieselFuelQuality pt1

2005 Inflammation
04. 03. 2008
0 views

2005 Inflammation

MI 2006 final 11 9
07. 08. 2007
0 views

MI 2006 final 11 9

figuerola lucifer
15. 10. 2007
0 views

figuerola lucifer

TOXICVB
05. 01. 2008
0 views

TOXICVB

GENIe ISA
10. 03. 2008
0 views

GENIe ISA

Pretty Blue Planet
19. 09. 2007
0 views

Pretty Blue Planet

AM1 DTV China EN
11. 10. 2007
0 views

AM1 DTV China EN

2007RoyalEurope consumer
01. 11. 2007
0 views

2007RoyalEurope consumer

YTBv4
12. 03. 2008
0 views

YTBv4

SevenBrochure
26. 03. 2008
0 views

SevenBrochure

babar
15. 10. 2007
0 views

babar

memphis
23. 10. 2007
0 views

memphis

NASBE Asthma Policies
07. 08. 2007
0 views

NASBE Asthma Policies

Apache Harmony Short Talk
19. 09. 2007
0 views

Apache Harmony Short Talk

DSF
07. 01. 2008
0 views

DSF

Module 10 C Older Adults
07. 08. 2007
0 views

Module 10 C Older Adults

CEC 999 2006 018
11. 10. 2007
0 views

CEC 999 2006 018

NNER MAGAZIN neu
18. 06. 2007
0 views

NNER MAGAZIN neu

kids slide show
18. 06. 2007
0 views

kids slide show

Inco Present1
18. 06. 2007
0 views

Inco Present1

nifty fifty thrifty 2
18. 06. 2007
0 views

nifty fifty thrifty 2

Navigator
18. 06. 2007
0 views

Navigator

mudancas internas2 lila
18. 06. 2007
0 views

mudancas internas2 lila

MMC Selection271006
18. 06. 2007
0 views

MMC Selection271006

MD Rhythm Software
18. 06. 2007
0 views

MD Rhythm Software

Experian
19. 09. 2007
0 views

Experian

urb1
27. 11. 2007
0 views

urb1

presentation reunion cnds clubs
18. 06. 2007
0 views

presentation reunion cnds clubs

PMA Veri Sign Hot Trends
18. 06. 2007
0 views

PMA Veri Sign Hot Trends

Phys Act2 Ron Johnston
18. 06. 2007
0 views

Phys Act2 Ron Johnston

cdp 8 12 06
19. 09. 2007
0 views

cdp 8 12 06

cdp 12 06
19. 09. 2007
0 views

cdp 12 06

061101 Panofsky
17. 08. 2007
0 views

061101 Panofsky

Saints or Sinners
17. 08. 2007
0 views

Saints or Sinners

memoria
18. 06. 2007
0 views

memoria

00021386
19. 09. 2007
0 views

00021386

peso fall protection w
04. 01. 2008
0 views

peso fall protection w

irony
15. 06. 2007
0 views

irony

HOUSE HOLDER
15. 06. 2007
0 views

HOUSE HOLDER

god you are looking for
15. 06. 2007
0 views

god you are looking for

generadio7
15. 06. 2007
0 views

generadio7

friendship cinquain
15. 06. 2007
0 views

friendship cinquain

foreign words in english
15. 06. 2007
0 views

foreign words in english

FME UC 2006 Opening Session
15. 06. 2007
0 views

FME UC 2006 Opening Session

First fun in the afternoon
15. 06. 2007
0 views

First fun in the afternoon

feml fool 2006
15. 06. 2007
0 views

feml fool 2006

FATE AND CHANCE WEEK I 2006
15. 06. 2007
0 views

FATE AND CHANCE WEEK I 2006

FATE AND CHANCE WEEK 2 2006
15. 06. 2007
0 views

FATE AND CHANCE WEEK 2 2006

faq remarriage
15. 06. 2007
0 views

faq remarriage

faq commitment
15. 06. 2007
0 views

faq commitment

Fabulously Funny Facts
15. 06. 2007
0 views

Fabulously Funny Facts

NEW MEMBERS
18. 06. 2007
0 views

NEW MEMBERS

mouton
18. 06. 2007
0 views

mouton

NPR
18. 06. 2007
0 views

NPR

NOWARonIran
16. 10. 2007
0 views

NOWARonIran

maendsregler
18. 06. 2007
0 views

maendsregler

Les arts figuratives al s XIX
01. 10. 2007
0 views

Les arts figuratives al s XIX

Kirkpatrick
07. 08. 2007
0 views

Kirkpatrick

texas emission
26. 02. 2008
0 views

texas emission

NFI Pact presentation copy 2
07. 08. 2007
0 views

NFI Pact presentation copy 2

casestudy
22. 10. 2007
0 views

casestudy

Thankyou Lord
17. 08. 2007
0 views

Thankyou Lord

megagreen
18. 06. 2007
0 views

megagreen

SRaha
17. 08. 2007
0 views

SRaha

Glasgow Anand
15. 11. 2007
0 views

Glasgow Anand

2 day training slideshow
07. 08. 2007
0 views

2 day training slideshow

Finch
15. 11. 2007
0 views

Finch