Introduction to Prolog

Copyright © 2018 by . All Rights Reserved.

Learning Outcomes

Copyright By cscodehelp代写 加微信 cscodehelp

by the End of the Lecture, Students that Complete

the Recommended Exercises should be Able to:

Review Logical Inference and Describe the Structure of a Prolog Program Implement simple Rules, Facts, and Queries in Prolog Describe the Processes of Derivation and Unification

Copyright © 2018 by . All Rights Reserved.

Optional Reading Assignment

Copyright © 2018 by . All Rights Reserved.

Read the following Chapter(s): 1

Logical Programming Basics

Logical Programming is programming that Uses Relations and Inference

Inference is the Derivation of Logical Conclusions from Premises that are Assumed to be True

Copyright © 2018 by . All Rights Reserved.

Given a Rule… …and a Fact… …Conclude:

Given a Rule… …and a Fact: …Conclude:

“The Way that Affirms by Affirming”

If A is True, Then B is True A is True

“The Way that Denies by Denying”

If A is True, Then B is True B is False

A is False

Copyright © 2018 by . All Rights Reserved.

“If something is a car, then it has wheels. The vehicle outside is a car. Therefore, it has wheels.”

“Agelasts never fleer. Xanthippes are agelasts. Therefore Xanthippes never fleer.”

these are Correct applications of Copyright © 2018 by . All Rights Reserved.

“For something to be an insect, it must have six legs. This table has six legs. Therefore it is an insect.”

“If something is made of wood then it burns. Witches burn. Theferfore witches are made of wood.”

these are Incorrect applications of (a common Fallacy known as Affirming the Consequent)

Copyright © 2018 by . All Rights Reserved.

Logical Programming Logical Programming is Based on Tuples

consider that the Function for Squaring (which is also a Relation) is also an Infinite Set of Tuples

square = { (0,0), (1,1), (2, 4), (3,9), … }

through Abstraction it can be Written… square = (x, x2)

… and Using an Alias… square = (x, y) where y = x2

Copyright © 2018 by . All Rights Reserved.

Logical Programming

What is the Meaning of the statement “Xavier is Zeke’s Uncle”?

i.e., Under What Conditions is X an Uncle of Z?

Copyright © 2018 by . All Rights Reserved.

Logical Programming X is Z’s Uncle

(is logically equivalent to)

X is Y’s Brother Y is Z’s Parent

(is logically equivalent to)

(X is Y’s Sibling X is Male) Y is Z’s Parent

Copyright © 2018 by . All Rights Reserved.

Logical Programming

Equivalence is Not the Same as Implication, but the Biconditional Equivalence means that when A is Equivalent to B, B Implies A (and Vice Versa)

X is Y’s Sibling X is Male Y is Z’s Parent Then

X is Z’s Uncle

Copyright © 2018 by . All Rights Reserved.

Logical Programming

uncleOf(X, Z) :- male(X), siblingOf(X,Y),

parentOf(Y,Z).

this is Prolog Syntax

it is an Implication Statement written with

Antecedent on the Right and Consequent on the Left

Copyright © 2018 by . All Rights Reserved.

PROgramming in LO Programs are Solutions to Problems that Involve Entities and Relationships

Programmer makes Logical Assertions*

* Assertions are Statements that a Fact or Rule is True

Programmer or User Asks a Query

Prolog Engine Attempts to Determine Values that Satisfy*

Introduction to Prolog

* Satisfaction means Cause to Evaluate to True Copyright © 2018 by . All Rights Reserved.

Programming Paradigms

with the Imperative* Programming Paradigm, the Fundamental Operation is Assignment

* (and Procedural, and Object-Oriented)

with the Functional Programming Paradigm, the Fundamental Operation is Reduction

with the Logical Programming Paradigm, the the Fundamental Operation is Satisfaction

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

Rules are Assertions that are Conditionally True Facts are Assertions that are Unconditionally True

Queries are Questions Answered through Inference Using the Facts and Rules

Collections of Facts and Rules are Known as Knowledge Bases

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

a Collection of Facts Written in Natural Language

John is a beatle.

Paul is a beatle. George is a beatle. Ringo is a beatle. John sings. John plays guitar. Paul sings. Paul plays base. George sings. George plays guitar. Ringo drums.

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog a Collection of Facts Written in Prolog

beatle(john).

beatle(paul). beatle(george). beatle(ringo). sings(john). sings(paul). sings(george). playsGuitar(john). playsGuitar(george). playsBase(paul). playsDrums(ringo).

Copyright © 2018 by . All Rights Reserved.

beatle(john).

beatle(paul). beatle(george). beatle(ringo). sings(john). sings(paul). sings(george). playsGuitar(john). playsGuitar(george). playsBase(paul). playsDrums(ringo).

| ?- playsGuitar(john). true.

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

beatle(john).

beatle(paul). beatle(george). beatle(ringo). sings(john). sings(paul). sings(george). plays(john, guitar). plays(george, guitar). plays(paul, base). plays(ringo, drums).

| ?- plays(ringo, drums). true.

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

beatle(john).

beatle(paul). beatle(george). beatle(ringo). sings(john). sings(paul). sings(george). plays(john, guitar). plays(george, guitar). plays(paul, base). plays(ringo, drums).

| ?- plays(ringo, ukelele). false.

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

beatle(john).

beatle(paul). beatle(george). beatle(ringo). sings(john). sings(paul). sings(george). plays(john, guitar). plays(george, guitar). plays(paul, base). plays(ringo, drums).

| ?- dances(ringo).

ERROR: … Undefined Procedure: dances/1

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

beatle(john).

beatle(paul). beatle(george). beatle(ringo). sings(john). sings(paul). sings(george). plays(john, guitar). plays(george, guitar). plays(paul, base). plays(ringo, drums).

| ?- eats(paul, meat).

ERROR: … Undefined Procedure: eats/2

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

beatle(john).

beatle(paul). beatle(george). beatle(ringo). sings(john). sings(paul). sings(george). likesMusic(john) :- sings(john). likesMusic(paul) :- sings(paul). likesMusic(ringo) :- sings(ringo).

| ?- likesMusic(john). true.

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

Introduction to Prolog

beatle(john).

beatle(paul).

beatle(george).

beatle(ringo).

sings(john).

plays(john, guitar).

plays(ringo, drums). reallyLikesMusic(john) :- sings(john), plays(john, guitar). kindaLikesMusic(ringo) :- sings(ringo); plays(ringo, drums).

| ?- reallyLikesMusic(john). true.

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

beatle(john).

beatle(paul).

beatle(george).

beatle(ringo).

sings(john).

plays(john, guitar).

plays(ringo, drums). reallyLikesMusic(john) :- sings(john), plays(john, guitar). kindaLikesMusic(ringo) :- sings(ringo); plays(ringo, drums).

| ?- kindaLikesMusic(ringo). true.

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

beatle(john).

beatle(paul).

beatle(george).

beatle(ringo).

sings(john).

plays(john, guitar).

plays(ringo, drums). reallyLikesMusic(john) :- sings(john), plays(john, guitar). kindaLikesMusic(ringo) :- sings(ringo). kindaLikesMusic(ringo) :- plays(ringo, drums).

| ?- kindaLikesMusic(ringo). true.

Copyright © 2018 by . All Rights Reserved.

| ?- sings(john). true.

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

beatle(john).

beatle(paul). beatle(george). beatle(ringo). sings(john). sings(paul). sings(george). plays(john, guitar). plays(george, guitar). plays(paul, base). plays(ringo, drums).

beatle(john).

beatle(paul). beatle(george). beatle(ringo). sings(john). sings(paul). sings(george). plays(john, guitar). plays(george, guitar). plays(paul, base). plays(ringo, drums).

| ?- sings(X).

X = john ; X = paul ; X = george.

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

beatle(john).

beatle(paul). beatle(george). beatle(ringo). sings(john). sings(paul). sings(george). plays(john, guitar). plays(george, guitar). plays(paul, base). plays(ringo, drums).

| ?- plays(X, Y).

X = john , Y = guitar ; …

Copyright © 2018 by . All Rights Reserved.

Introduction to Prolog

Graph Representation and Pathfinding

What is the Formal Representation of this Graph? a Graph is Formally Represented as a Tuple

(i.e., an Ordered Pair) of a Vertex Set and an Edge Set Copyright © 2018 by . All Rights Reserved.

Graph Representation and Pathfinding

vertex(1). vertex(2). vertex(3). vertex(4). vertex(5). vertex(6). edge(1,2). edge(2,4). edge(1,3). edge(3,5). edge(5,6). edge(3,6).

if you are Concerned only with Paths (i.e., Sequences of Edges), then the Prolog Facts for the Vertices are Unimportant

What is the Recursive Definition of a Path? as a Prolog Rule?

Copyright © 2018 by . All Rights Reserved.

Graph Representation and Pathfinding

edge(1,2).

edge(2,4).

edge(1,3).

edge(3,5).

edge(5,6).

edge(3,6).

path(X, Y) :- edge(X, Y).

path(X, Y) :- edge(X, Z), path(Z, Y).

How could we Adapt this for an Undirected Graph?

Copyright © 2018 by . All Rights Reserved.

Graph Representation and Pathfinding

edge(1,2).

edge(2,4).

edge(1,3).

edge(3,5).

edge(5,6).

edge(3,6).

path(X, Y) :- edge(X, Y).

path(X, Y) :- edge(X, Z), path(Z, Y). edge(X, Y) :- edge(Y, X).

Why would this Introduce a Problem? Copyright © 2018 by . All Rights Reserved.

Graph Representation and Pathfinding

edge(1,2).

edge(2,4).

edge(1,3).

edge(3,5).

edge(5,6).

edge(3,6).

path(X, Y) :- edge1(X, Y).

path(X, Y) :- edge1(X, Z), path(Z, Y). edge1(X, Y) :- edge(X, Y).

edge1(X, Y) :- edge(Y, X).

What happens with Graphs that contain Cycles? Copyright © 2018 by . All Rights Reserved.

Graph Representation and Pathfinding

2. p(X) :- q(X), r(X).

3. p(X) :- u(X).

4. q(X) :- s(X).

What is the Response to the Following Query? | ?- p(X).

Copyright © 2018 by . All Rights Reserved.

Graph Representation and Pathfinding

2. p(X) :- q(X), r(X).

3. p(X) :- u(X).

4. q(X) :- s(X).

What is the Response to the Following Query? | ?- p(X).

X = a; X = a; X = b; X = d.

Copyright © 2018 by . All Rights Reserved.

1. p(a). 4. q(X) :- s(X). 2. p(X) :- q(X), r(X). 5. r(a).

7. s(a). 8. s(b). 9. u(d).

3. p(X) :- u(X).

6. r(b). p(X)

Derivation Trees

Xa 1? true

Copyright © 2018 by . All Rights Reserved.

1. p(a). 4. q(X) :- s(X). 2. p(X) :- q(X), r(X). 5. r(a).

7. s(a). 8. s(b). 9. u(d).

3. p(X) :- u(X).

p(X) q(X), r(X) s(X), r(X)

Derivation Trees

Copyright © 2018 by . All Rights Reserved.

1. p(a). 4. q(X) :- s(X). 2. p(X) :- q(X), r(X). 5. r(a).

7. s(a). 8. s(b). 9. u(d).

3. p(X) :- u(X).

p(X) q(X), r(X) s(X), r(X)

Derivation Trees

Copyright © 2018 by . All Rights Reserved.

1. p(a). 4. q(X) :- s(X). 2. p(X) :- q(X), r(X). 5. r(a).

7. s(a). 8. s(b). 9. u(d).

3. p(X) :- u(X).

p(X) q(X), r(X) s(X), r(X) Xb r(b)

Derivation Trees

Copyright © 2018 by . All Rights Reserved.

1. p(a). 4. q(X) :- s(X). 2. p(X) :- q(X), r(X). 5. r(a).

7. s(a). 8. s(b). 9. u(d).

3. p(X) :- u(X).

p(X) q(X), r(X) s(X), r(X) Xb r(b)

Derivation Trees

Copyright © 2018 by . All Rights Reserved.

1. p(a). 4. q(X) :- s(X). 2. p(X) :- q(X), r(X). 5. r(a).

7. s(a). 8. s(b). 9. u(d).

3. p(X) :- u(X).

p(X) q(X), r(X) s(X), r(X)

Derivation Trees

Xb … r(b)

Copyright © 2018 by . All Rights Reserved.

Derivation Trees are Traversed Depth-First

this Entails that Alternate Choices are Attempted when the Search Returns to the Branch where the Alternative was Available

this is known as Backtracking Copyright © 2018 by . All Rights Reserved.

Derivation Trees

Unification and Matching

Unification Matches a Pair of Terms by Finding a Substitution of Variables (denoted S)

if S is Applied to Both Terms then the Results are Equal

Copyright © 2018 by . All Rights Reserved.

Unification and Matching there are Three Types of Term in Prolog

(e.g., robert, 31, etc.) Variables

(e.g., X, Y, VariableName, etc.) Complex Terms

(i.e.,functor (term1, term2, …, termn))

How does Prolog Match Terms? Copyright © 2018 by . All Rights Reserved.

Unification and Matching

Conditions for Match between T1 and T2

T1 and T2 Match If and Only If:

T1 and T2 are the Same Atom or Number

Nonvariable

T1 and T2 Match

T1 is then Instantiated to T2

T1 and T2 Match

T1 and T2 are now “Co-References”

T1 and T2 Match If and Only If:

T1 and T2 have the Same Functor Name T1 and T2 have the Same Functor Arity Corresponding Arguments Match Variable Instantiations are Compatible

Copyright © 2018 by . All Rights Reserved.

Unification and Matching Which of the following will Match?

reads(robert, scifi) eats(robert, What) book(1, herbert, dune) foo(X, a) teaches(robert, X) foo(X, Y) foo(bar, X)

reads(Who, What)

eats(Who, pizza) book(A, B, ringworld) foo(a, X) teaches(X, comp3007) foo(Z, Z)

Copyright © 2018 by . All Rights Reserved.

Unification and Matching Which of the following will Match?

reads(robert, scifi) eats(robert, What) book(1, herbert, dune) foo(X, a) teaches(robert, X) foo(X, Y) foo(bar, X)

match match

reads(Who, What)

eats(Who, pizza) book(A, B, ringworld) foo(a, X) teaches(X, comp3007) foo(Z, Z)

Copyright © 2018 by . All Rights Reserved.

程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com