-
Recursion example in Prolog
on_route(rome).
- on_route(Place):-
- move(Place,Method,NewPlace),
- on_route(NewPlace).
- move(home,taxi,halifax).
- move(halifax,train,gatwick).
- move(gatwick,plane,rome).
-
Cut ! in prolog. Explain the purpose of cut and how it works
The cut mechanism allows for optimizing the efficiency of programs by pruning the search-tree. For example a clause a:-b,c,!,d,e.: when ! is encountered the solutions to the previous goals, a and b, are ‘frozen’, i.e. the remaining computation, and success of the rule, is committed to the choices made prior to the !.
-
Clause form
∀x.∀y.(P(x,y) ∨ ∃z.Q(x,y,z))
- Skolemize:
- for all x and all y there exists a z, call z f(x,y)
- (P(x,y) ∨ Q(x,y,(f(x,y))))
- Convert to Clause Form:
- { [P(x,y), Q(x,y,(f(x,y)))] }
-
Unifiability
P(f(x, g(y)), y)
P(f(g(a), z), b)
- 1. f(x, g(y)) = f(g(a), z)
- x = g(a)
- {g(a) → x}
- unifies term g(a) with x
- P(f(g(a), g(y)), y)
- P(f(g(a), z), b)
- 2. g(y) = z
- {z → g(y)}
- unifies z with term g(y)
- P(f(g(a), g(y)), y)
- P(f(g(a), g(y)), b)
- 3. y = b
- {b → y}
- b is unified with the variable y
- P(f(g(a), g(y)), y)
- P(f(g(a), g(y)), y)
Thus, it is unifiable
-
Unifiability
P(x, f(y,a), y)
P(f(a,b), b, z)
- 1. x = f(a,b)
- {f(a,b) → x}
- unifies x with f(a,b)
- x becomes f(a,b)
- f(a,b) is really just one thing, when the function is used then it becomes a value which is one thing, and x which is one thing can be replaced with its «one» value.
- P(f(a,b), f(y,a), y)
- P(f(a,b), b, z)
2. f(y,a) = b fails
- 3. y = z
- {z → y}
- z is unified with the variable y, they are aliased
not unifiable
-
prolog program to find siblings to GOT arya and robb with father ned
- father(ned,arya). father(ned,robb).
- sibling(Sibling1,Sibling2) :-
- father(CommonFather,Sibling1),
- father(CommonFather,Sibling2).
- ?- (sibling(arya, robb)).
- true
-
How to find parents of royal family in Prolog given:
olav and martha are the parents of harald and astrid and ragnhild
- parents(olav, martha , harald).
- parents(olav, martha , astrid).
- parents(olav, martha , ragnhild).
- father(X, F):- parents(F,_,X).
- mother(X, M):- parents(_,M,X).
- parent(X,Z) :- parents(X,_,Z).
- parent(X,Z) :- parents(_,X,Z).
- ?- parent(X,harald).
- would find X for father and X for mother
-
Russian dolls
irina is inside of natash inside of olga inside of katarina.
Find container of inner doll, see if container of inner doll is inside outer doll.
- directlyIn(irina,natasha).
- directlyIn(natasha,olga).
- directlyIn(olga,katarina).
x= inner, y=outer, z=InnerContainer
- in(x, y) :- directlyIn(x, y).
- % Basecase
- in(x, y) :- directlyIn(x, z), in(z, y).
- % y is inside of X
- % if Z is inside of X, Z is also inside of Y
-
progamming constructs of prolog.
fact male(arne) is he a man?
-
The clock says tick, tock or, when it dies, nothing. It never says two ticks in a row, or two tocks in a row and at the end it always makes the nothing sound.
tick(nothing) is a legitimate sequence.
tick(tock(nothing)) , or even tick(tock(tick(nothing))), are also legitimate sequences.
tick(tick(nothing)) is not.
Define a recursive predicate clockSequence(S), with helper predicates tick/1 and tock/1, which only holds if S is a legitimate sequence of ticks and tocks.
- clockSequence(tick(nothing)).
- % Basecase
- clockSequence(tock(nothing)).
- % Basecase
- clockSequence(tick(tock(X))) :- clockSequence(tock(X)).
- % Recurse by removing outer layer
- clockSequence(tock(tick(X))) :- clockSequence(tick(X)).
- % Recurse by removing outer layer
-
We have the following knowledge base:
directTrain(saarbruecken,dudweiler). directTrain(forbach,saarbruecken). directTrain(freyming,forbach). directTrain(stAvold,freyming). directTrain(fahlquemont,stAvold). directTrain(metz,fahlquemont). directTrain(nancy,metz).
That is, this knowledge base holds facts about towns it is possible to travel between by taking a direct train. But of course, we can travel further by chaining together direct train journeys.
Write a recursive predicate travelFromTo/2 that tells us when we can travel by train between two towns.
For example, when given the query
travelFromTo(nancy,saarbruecken).
it should reply yes.
x=From, y=To, z=NextCity
- travelFromTo(x, y) :- directTrain(x, y).
- % Basecase
- travelFromTo(x, y) :- directTrain(x, z), travelFromTo(z, y).
- % NextCity matches with locations reachable directly from origin. Recursion sees if the destination is reachable from NextCity
-
john is beautiful and rich horn clause and prolog example
- (beautiful(john)) ∧ (rich(john))
- beautiful(john).
- rich(john).
- beautiful:- beautiful(X).
- rich:- rich(X).
- beautiful(X),rich(X).
-
PROLOG
john likes X if X is a car.
X and Y are friends if X likes Y and Y likes X. OR Two people are friends if they like each other.
- likes(john, X) :- car(X).
- friends(X, Y) :- likes(X, Y), likes(Y, X).
-
Make a KB using Horn-clauses
Diseases like Flu, mumps and the common cold are contagious and can transfer between humans. Situations in which there is a risk for transfer are, for instance, when shaking hands, kissing or when coughing in the direction of another person. Individuals are exposed to a disease when they are in such a risk-situation together with
a) someone who has the disease, in which case we say that the exposure is direct, or
b) someone who has been exposed to the disease, directly or indirectly
John and Liz are sick with the flu whereas Mary has the mumps.
John and Tom have shaken hands and so have Tom and Mary.
Mary has coughed on Pete.
Given the KB it should be possible to query who has been exposed to a given disease. For instance, it should entail that Pete has been exposed to the flu, i.e. KB=exposed(pete, flu). (Since he was coughed on by Mary who shook the hand of Tom who shook the hand of John who has the flu.) Alternatively that Prolog answers Yes on the query ?-exposed(pete, flu).
- contagious(flu).
- contagious(mumps).
- contagious(cold).
- sick(john, flu).
- sick(liz, flu).
- sick(mary, mumps).
- handshake(john, tom).
- handshake(tom, mary).
- coughOn(mary, pete).
- %Situation with risk of spreading from Person1 to Person2
- spreadRisk(Person1, Person2):-handshake(Person1, Person2).
- spreadRisk(Person1, Person2):-coughOn(Person1, Person2).
- spreadRisk(Person1, Person2):-kissed(Person1, Person2).
- exposed(Person, Disease):- spreadRisk(X,Person), sick(X,Disease).
- exposed(Person, Disease):- spreadRisk(X, Person), exposed(X, Disease).
-
Extend the KB such that queries can be used to derive exposure-chains, i.e. terms which traces an exposure back to its source by listing the people involved. For instance: Pete, Mary, Tom, John.
For example, using an answer predicate a derivation of KB=exposureChain(x, flu) should extract an answer such as x\chain(pete, chain(mary, chain(tom, chain(john, unknownSource)))). Alternatively [pete, mary, tom, john] if you use the list-format of Prolog.
- %non-list
- exposureChain(chain(X, Disease-source), Disease):-sick(X, Disease).
- exposureChain(chain(X, from(Y,Chain)), Disease):- spreadRisk(Y,X),
- exposureChain(chain(Y,Chain), Disease).
- % list-representation
- %exposureChain([X], Disease):-sick(X, Disease).
- %exposureChain([X, Y|Chain], Disease):- spreadRisk(Y,X),
- % exposureChain([Y|Chain]), Disease).
-
Given a Prolog-program containing cuts (!). Consider the program obtained by replacing every
occurrence of ‘!’ with ‘cut’ and adding the clause: cut:-!.
Will the new program necessarily have the same results as the original? Explain carefully.
No, the modification may affect the result, because the parent-node of the cut will then be one level deeper in the tree so that alternatives from the previous parent-node will no longer be blocked from backtracking and may yield new results.
-
Is olav royal?
parents(haakon, maud, olav)
royal(haakon)
- royal(X):- father(X,Y), royal(Y).
- royal(X):- mother(X,Y), royal(Y).
-
prolog atoms vs variables, how to spell, and or implication
- atoms start with a lowercase letter, pam, haakon
- variables start with an uppercase letter X, LeastNumber, _leastnumber
- in between answers in query if multiple results ;
- No means the query is finished and has not found anymore X
- , resembles and
- ; resembles or
- :- resembles implication
- \+ resembles negation
-
how to write does not equal in prolog
X \= Y.
-
find pams birthday
birthday(pam, date(4, sept, 1997)).
- ?-birthday(pam, date(_, _, Year)).
- Year = 1997
-
What is this in prolog?
¬a∨¬b∨c
- 1. ¬a ∨ ¬b ∨ c ≡ PL
- 2. [¬a,¬b,c] ≡ horn clause
- 3. ¬(a∧b) ∨ c ≡ PL and De Morgan
- 4. (a∧b) ⊃ c ≡ pl, De Morgan, implication rule
- 5. c():- a,b. ≡ PROLOG
-
use SLD derivation. let KB|=
∀x.(B(x) ⊃ A(x))
∀x.(E(x) ⊃ B(x))
∀x.(A(x) ⊃ Loves(erik, x))
¬B(frank)
E(hannah)
erik, frank, hannah = constants
A,B,E,Loves = predicates
Does Erik love Hannah?
- 1. [¬B(x),A(x)]
- 2. [¬E(x),B(x)]
- 3. [¬A(x),Loves(erik, x)]
- 4. [E(hannah)]
- From 1 and 2, take away Bs
- From 1 and 3, take away As
- From 2 and 4, take away Es
- we now know that x=hannah, since E(x) and E(hannah)
- so we are left with
- Loves(erik, hannah)
-
Variable Function Constant
Unification explanation
x,y,z are used as variables, f,g as function symbols, and a,b as constants.
A variable which is uninstantiated—i.e. no previous unifications were performed on it—can be unified with an atom, a term, or another uninstantiated variable, thus effectively becoming its alias. In many modern Prolog dialects and in first-order logic, a variable cannot be unified with a term that contains it; this is the so-called occurs check.
Two atoms can only be unified if they are identical.
A term can be unified with another term if the top function symbols and arities of the terms are identical and if the parameters can be unified simultaneously. Note that this is a recursive behavior.
-
Unification
Prolog/Mathematical Notation
Unifying Substitution
Explanation
a=a
a=b
X=X
a=X
X=Y
f(a,X) = f(a,b)
f(a) = g(a)
f(X) = f(Y)
f(X) = g(Y)
f(X) = f(Y,Z)
f(g(X)) = f(Y)
f(g(X),X) = f(Y,a)
X = f(X)
X=Y, Y=a
a=Y, X=Y
X=a, b=X
- a=a ;yes
- a=b ;no, a and b do not match
- X=X ;yes
- a=X ;yes, {x→a}, x is unified with constant a
- X=Y ;yes, {x→y}, x and y are aliased
- f(a,X) = f(a,b) ;yes, {x→b}, function and constant symbols match, x is unified with constant b
- f(a) = g(a) ;no, f and g do not match
- f(X) = f(Y) ;yes, {x→y}
- f(X) = g(Y) ;no, f and g do not match
- f(X) = f(Y,Z) ;fails, functions with different arities
- f(g(X)) = f(Y) ;yes, {y→g(x)}, unifies y with term g(X)
- f(g(X),X) = f(Y,a) ;yes, {x→a, y→g(x)}, unifies x with constant a, and y with the term g(a)
- X = f(X) ;yes in prolog as x=f(f(f(f...), but should be no
- X=Y, Y=a ;yes, {x→a, y→a}, both x and y are unified with constant a
- a=Y, X=Y ;yes, same as above
- X=a, b=X ;fails, a and b do not match, X cannot be unified with both
-
∃x∀y∃z.P(x,y,z)
get rid of Es to be ready for unification.
- an x exists, rename it a
- for all y, there exists a Z, so call z function of y or f(y)
- ∀y.P(a,Y,f(Y))
-
Prolog KB school courses example from oblig 2
- teacher(t1).
- department(sv).
- teachesIn(sv, t1).
- teachesTopic(t1, programming).
- course(sv100).
- course(sv101).
- topic(programming).
- courseHasTopic(sv100, programming).
- courseHasTopic(sv101, programming).
- courseOfferedAt(sv, sv100).
- courseOfferedAt(sv, sv101).
- background(sv101, sv100).
- background(sv200, sv101).
- background(sv201, sv200).
- in(X,Y):-
- background(X,Y).
- in(X,Y):-
- background(X,Z),
- in(Z,Y).
- externalTeacher(Teacher, Department) :-
- teacher(Teacher), department(Department),
- teachesTopic(Teacher, Topic),
- courseOfferedAt(Department, Course),
- courseHasTopic(Course, Topic),
- \+teachesIn(Department, Teacher).
- courseCompetance(Course,Teacher) :-
- course(Course), teacher(Teacher),
- courseHasTopic(Course, Topic),
- \+teachesTopic(Teacher, Topic).
- solo(Course, Teacher):-
- course(Course), teacher(Teacher),
- \+courseCompetance(Course, Teacher).
-
\+ means
\+ just means: fail, if the goal is provable at this point in time quantifying all variables existentially.
-
Consider the following definite program that describes a world where “parents of newborn children are proud”, “Adam is the father of Mary” and “Mary is newborn”:
refutation of <- proud(Z)
-
Logical equivalent
proud(X) <- parent(X,Y),newborn(Y)
∀(¬proud(X) ⊃ ¬(parent(X,Y) ∧ newborn(Y)))
-
- ←grandfather(a,X).
- |
- father(X0,Y0), parent(Y0,Z0)→ grandfather(X0,Z0).
- |
- ←father(a,Y0), parent(Y0,X).
- |
- father(a,b).
- |
- ←parent(b,X).
- |
- mother(X2,Y2)→ parent(X2,Y2).
- |
- ←mother(b,X).
- |
- mother(b,c).
- |
- [ ]
-
Forward Chaining mother and parent example
Parent(x, y) ⇐ Mother(x, y):
- works from the facts in the KB
- toward the goals. The idea is to mark atoms as “solved” as soon as we have determined that they are entailed by the KB.
if added: when a fact matching mother(x,y) is added to the DB, also add parent(x,y). Connection between mother and parent made as soon as we learn about a new mother relationship.
-
Backward Chaining mother and parent example
Parent(x, y) ⇐ Mother(x, y):
works backward from goals to facts in the KB
if-needed: whenever we have a goal matching parent(X,Y) we can solve it by solving mother(X,Y). Wait to make a connection between mother and parent until we need to prove something about parents.
-
Explain cut. Logical equivalence.
G:- P, !, R.
G:- S.
- if P holds then R implies G
- if notP holds than S implies G (only considers the P once)
-
P ⊃ Q sanctions two directions of reasoning
Data-directed and Goal-directed
- Data-directed: Assertion of P, allows assertion of Q
- Forward Chaining
- Goal-directed: A goal Q can be reduced to a goal P
- Backward Chaining
-
The following KB represents a fight between some animals. The predicate Bite(x,y) represents the fact that x bites y during the fight. Snake(x), Venomous(x), Die(x) represents the properties of being a snake, venomous and being killed in the fight, respectively. Note that death is not necessarily instant, i.e. an animal may remain capable of biting for some time after having received a deadly bite. For instance, snakes will always bite back when bitten.
KB
Determine if KB entails the following:
The cheetah survived
notDie(cheetah)
- No: Counterexample C=<{co, vi, li, ch}, I> where
- I[cobra]=co and so on…
- I[Snake]={co, vi}
- I[Bite]={ (li,co), (co,li,), (li,vi), (vi,li) , (co,vi),(vi,co),(vi,ch) }
- I[Venomous]={co, vi} ! nothing prohibits the viper from being venomous
- I[Die]={vi, co, li, ch} ! so cheeta dies
-
Backward chaining IDEA
- Idea: work backwards from the query q:
- to prove q by BC,
- check if q is known already, or
- prove by BC all premises of some rule concluding q
Avoid loops: check if new subgoal is already on the goal stack
- Avoid repeated work: check if new subgoal
- 1. has already been proved true, or
- 2. has already failed
|
|
