程序代写代做代考 prolog Prolog 3

Prolog 3

1

Prolog

Negation, Cut

Fariba Sadri

(Acknowledgement to Keith Clark for

use of some slides)

2

Negation in Prolog \+

In Prolog negation is allowed only in queries and

in the bodies of rules – not in the heads of

rules.

E.g.

✔ ?- student(X), \+ gets_scholarship(X).

✔ happy(X):- owns_a_house(X),

\+ has_mortgage(X).

✘ \+ has_mortgage(X) :- child(X).

✘ \+ has_scholarship(john).

3

4

Negation in Logic

In logic we can write both negative and positive
statements.

E.g.

T: student(john)

student(mary)

gets_scholarship(john)

¬ gets_scholarship(mary)

we can show:

From T we can prove:

student(mary) ¬gets_scholarship(mary)

So how can Prolog show

student(mary) , \+ gets_scholarship(mary)?

It will use

the Closed world assumption.

5

6

Closed world assumption

In Prolog:

• Programs contain only positive statements (i.e.

rules and facts with positive heads).

• Negative conditions are evaluated using:

The closed world assumption: i.e.

Any fact that cannot be inferred is false.

• Negative information is inferred by default,

using the Negation as failure (Naf) rule.

7

E.g. In Prolog we would write:

student(john).

student(mary).

gets_scholarship(john).

?- student(X), \+ gets_scholarship(X).

X = mary

Because Mary is a student that Prolog cannot prove gets a
scholarship.

8

The Negation as Failure (Naf) Rule

• \+ Q is proved if all evaluation paths for the

query Q end in failure.

• Proof of \+Q will not generate any bindings

for variables in Q.

• If Q contains variables X1,..,Xk, it effectively

establishes:

¬X1 … Xk Q

9

• \+ Q fails to be proved if there is some proof

of Q.

Be careful with the order of

subgoals
E.g. In Prolog we would write:

student(john).

student(mary).

gets_scholarship(john).

?- \+ gets_scholarship(X), student(X).

no

10

Justification of the NAF Rule

Naf rule is valid providing we assume clauses

constitute complete definitions of the relations

they describe, and that different terms denote

different individuals (e.g. paul≠peter).

11

Justification of the NAF Rule cntd.

Program P:

student(john).

student(mary).

gets_scholarship(john).

Completion of P:

student(X)  X=john  X= mary

gets_scholarship(X)  X=john

john ≠ mary

12

13

Example use of \+

dragon(puff).

dragon(macy).

dragon(timothy).

dragon(spyro).

magical(puff).

lives_by_the_sea(spyro).

vegetarian(macy).

fights(spyro).

lives_forever(X):- magical(X).

lives_forever(X):- vegetarian(X).

lives_forever(X):- lives_by_the_sea(X), \+ fights(X).

?- dragon(X), \+ lives_forever(X).

Construct the Prolog evaluation to see how it
finds the answers.

14

15

Negated conditions with unbound

variables

Be careful with variables in negative conditions:

?- \+ lives_forever(X), dragon(X).

will have no answers. Why?

Apply the Naf inference rule to first condition –

what is the result?

More on Prolog Negation

\+ can be applied to conjunctions.

Example:

Assuming a set of male/1 and parent/2 facts:

we can define dragons with no sons:

no_sons(D):-

dragon(D),

\+(parent(D,C), male(C)).

16

\+ can be nested.

Example:

Dragons with no daughters:

no_daughters(D):-

dragon(D),

\+(parent(D, C),\+male(C)).

17

18

\+ can be applied to disjunctions.

Example:

damaged(D) :-

dragon(D),

\+ ( breathes_fire(D) ; has_wings(D)).

19

Prolog definition of \+

\+(P) :- P, !, fail.

\+(_).

20

Evaluation control : !

• Cut, denoted by “!”, is a Prolog query evaluation
control primitive.

• It is “extra-logical” and it is used to control the search
for solutions and prune the search space.

• In logical reading it is ignored.

• The cut can only be understood procedurally, in
contrast to the declarative style that logic
programming encourages.

• But used wisely, it can significantly improve
efficiency without compromising clarity too much.

21

Example program with needless

search
send(Cust, Balance, Mess):-

Balance =< 0, warning(Cust, Mess). send(Cust, Balance, Mess):- Balance > 0,

Balance=< 50000, credit_card_info(Cust, Mess). send(Cust, Balance, Mess):- Balance > 50000

investment_offer(Cust, Mess).

22

For a condition:

send(bill, -10, Message)

in a query for which all solutions are being

sought, Prolog will try to use second and third

clause after an answer has been found using

the first clause.

Clearly this search is pointless.

23

Using !

send(Cust, Balance, Mess):-

Balance =< 0, !, warning(Cust,Mess). send(Cust,Balance, Mess):- Balance > 0,

Balance=< 50000, !, credit_card_info(Cust,Mess). send(Cust,Balance, Mess):- Balance > 50000

investment_offer(Cust,Mess).

send(Cust, Balance, Mess):-

Balance =< 0, !, warning(Cust,Mess). send(Cust,Balance, Mess):- delete Balance > 0,

Balance=< 50000, !, credit_card_info(Cust,Mess). send(Cust,Balance, Mess):- delete Balance > 50000

investment_offer(Cust,Mess).

24

25

The Effect of !

Program:

p(…):- T1,. . . , Tk, !, B1 . . . , Bn.

p(…):- …

p(…):- …

In trying to solve a call:
p(…)

if first clause is applicable, and

T1,. . . , Tk

is provable, then on backtracking:

• do not try to find an alternative solution for T1,. . . , Tk and

• do not try to use a later applicable clause for the call p(…).

Backtacking will happen as normal on B1 . . . , Bn.

Cut Practice

Place a cut in different positions in the following

program and test your understanding of its

effects.

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

p(X,Y) :- s(X,Y).

q(1). q(2).

r(1). r(2). r(3).

s(10, 10). s(20, 10).

26

Be careful with the cut!

max(X,Y,Y) :- Y>X, !.

max(X,Y, X).

?- max(1, 2, Z).

Z=2

?- max(1, 2, 1).

yes

27

An alternative definition of max

max(X,Y, Z) :- Y>X, !, Z=Y.

max(X,Y, Z):- Z=X.

?- max(1,2,Z).

Z = 2

?- max(1,2,1).

no

28