# 代写代考 Introduction to Prolog – cscodehelp代写

Introduction to Prolog

Learning Outcomes

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

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

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

“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.”

“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)

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

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?

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

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

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

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

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

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

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.

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).

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.
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.
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.
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
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
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.
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.

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.

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.

| ?- sings(john). true.
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.
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 ; …
Introduction to Prolog

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

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?

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?

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).

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).

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).

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.

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
Xa 1? true

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

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

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) Xb r(b)
Derivation Trees

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) Xb r(b)
Derivation Trees

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
Xb … r(b)

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
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

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))

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

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)