( )1. the Procedural Meaning Specifies How Prolog Answers Questions

第1頁共6頁

邏輯語言程式設計(B版)

系級： 座號： 姓名： 97/11

一、是非題(20%)

( )1. The procedural meaning specifies how Prolog answers questions.

( )2. If several answers satisfy the question then Prolog can find only one of them.

( )3. A procedure is a set of clauses about the different relations.

( )4. Atoms and numbers are constants.Variables belong to simple objects.

( )5. If not is defined as fx then not not p is legal.

( )6. In Prolog, matching, if it succeeds, results in the most general instantiation of variables.

( )7. A database can be naturally represented as a set of Prolog rules.

( )8. The lexical scope of variable names is one clause. Thus the same variable name in two clauses means two different variables.

( )9. The list is a frequently used structure. It is either empty or consists of a head and a tail which is a list as well.

( )10.A automation is said to accept the input string if there is a transition path in the graph such that it ends with one of its states.

二、選擇題(12%)

( )1. Which one is not an atom?

(A) x_35AB(B)‘Tom’(C)<--->(D)_x23

( )2. Which list can not be accepted by Prolog?

(A)[Item1, Item2, Item3 | Other](B) [Head | [Tail]]

(C) [Item1 | Item2, Item3, Item4](D) [[Item1]| Other]

( )3. If the ‘+’ and ‘–‘ operators are defined as follows:

:- op( 500, xfy, [+,–]).

Which result of these equations is different to others?

(A)a +b – c– d(B) a +b –(c– d)(C) (a +b )– c– d(D) a +(b – c) – d

( )4. Which one of the answers is ‘no’ in Prolog?

(A)1+2 = 2+1(B) 1+2 =:=2+1(C)3=2+1(D)3 is2+1

三、簡答題

1. (6%) Deleting an item X form a list L can be programmed as a relation:

del( X, L, L1) where L1 is equal to the list L with the item X removed.

Given the delrelation as follows:

del( X, [X| Tail], Tail).

del( X, [Y| Tail], [Y|Tail1]) :- del( X, Tail, Tail1).

Please use the delrelation to define the insertandmember relations.

(1)Inserting X at any place in some list List giving BiggerList can be defined:

insert( X, List, BiggerList) :-

(2)Use del to test for membership:

member( X, List) :-

ANS:

1. (8%) Here is a program to solve the monkey and banana problem. Please define the canget relation to finish the following program:

move( state( middle, onbox, middle, hasnot), grasp, state( middle, onbox, middle, has) ).

move( state( P, onfloor, P, H),climb, state( P, onbox, P, H) ).

move( state( P1, onfloor, P1, H),push( P1, P2),state( P2, onfloor, P2, H) ).

move( state( P1, onfloor, B, H), walk( P1, P2), state( P2, onfloor, B, H) ).

PS. The initial state is state( atdoor, onfloor, atwindow, hasnot). It means

(1)Monkey is at door.

(2)Monkey is on floor.

(3)Box is at window.

(4)Monkey does not have banana.

ANS:

1. (6%) Given the facts as follows:

parent( pam, bob).

parent( tom, bob).

parent( tom, liz).

parent( bob, ann).

parent( bob, pat).

parent( pat, jim).

predecessor( X, Z) :- parent( X, Z).

predecessor( X, Z) :- parent( X, Y),predecessor( Y, Z).

(1) Please show the answer of the following questions.

?- predecessor( pam, jim).

(2) Please show the second answer of the following question.

?- predecessor( X, pat).

ANS:

1. (6%) Please show the output of the following question.

abc( [], L, L).

abc( [X| L1], L2, [X| L3]) :- abc( L1, L2, L3).

(1) |?- abc([[a, b]], [a, b, b, c ], X).

(2) | ?- abc ( _, [Month1,may, Month2|_], [jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec]).

ANS:

1. (3%) Please show the output of the following questions.

f( 1, one).f( s(1), two).f( s(s(1)), three).

f( s(s(s(X))), N) :- f( X, N).

| ?- f( s(s(s(s(s(s(s(1))))))), C).

ANS:

1. (6%) Please show the output of the following questions.

point(1,1).point(1,2).point(2,4).

seg(point(1,1), point(1,2)).

seg(point(1,1), point(2,4)).

seg(point(1,2), point(2,4)).

vertical( seg( point( X, Y), point( X, Y1))).

horizontal( seg( point( X, Y), point( X1, Y))).

(1) | ?- vertical( seg( point(1,1), P)).

ANS:

(2) | ?- vertical( S), horizontal( S).

ANS:

1. (3%) Please show the output of the following question.

abc( [], 0).

abc( [_ | Tail], N) :- abc( Tail, N1), N is 1 + N1.

| ?- abc( [a, b, [b, [c], c, [f] ]], X).

ANS:

1. (6%) Please show the output of the following questions.

(1) | ?- [a|Z] = .(X, .(Y, [])).

ANS:

(2) | ?- date( D, M, 2001) = date(D1, may, Y1), date( D, M, 2001) = date( 15, M, Y).

ANS:

1. (12%)If a familysturcture of a database defined as follows:

(1) Each family has three components:husband, wife, and children.

(2) The children are represented by a list.

(3) Each person represented by a structure of four components: name, surname, date of birth, and job.

(4) The job information is ‘unemployed’, or it specifies the working organization and salary.

An example of a family structure of a database is shown as follows:

family(

person( tom, fox, date(7,may,1960), works( bbc, 15200)),

person( ann, fox, date(9,may,1961), unemployed),

[ person( pat, fox, date(5,may,1983), unemployed),

person( jim, fox, date(5,may,1983), unemployed) ] ).

If some useful utility procedure for the database are defined:

husband( X) :- family( X, _, _).

wife( X) :- family( _, X, _).

child( X) :- family( _, _, Children), member( X, Children).

exists( Persons) :- husband( Persons); wife( Persons); child( Persons).

dateofbirth( person(_, _, Date, _), Date).

salary( person(_, _, _, works(_, S)), S).

salary( person(_, _, _, unemployed), 0).

(1) (4%) Please show the meaning of the following queries.

(A)family( person( _, Name, _, _), _, [_, _, _| _]).

(B)exists( person( Name, Surname, date(_, _, Year), unemployed)), Year < 1973.

ANS:

(2) (2%) If we write a quary to find people born before 1960 whose salary is less than 8000 as follows:

| ?- dateofbirth( Person, date(_, _, Year)), Year < 1960,

salary( Person, Salary), Salary < 8000.

Is it a correct quary? If not, please correct this quary.

ANS:

(3) (6%) Please use these utilities in the following queries to the database:

(A) Find names of families without children.

(B)Find all employed wives.

ANS:

1. (12%) Given afinite atuomaton as follows:

(1) (2%) A unary relation final which defines the final states of the automaton. Please show one of the final facts.

ANS:

(2) (2%) A three-argument relation trans which defines the state transitions so that
trans( S1, X, S2) means that a transition from a state S1 to S2 is possible when the current input symbol X is read. Please show one of the trans facts.

ANS:

(3) (2%) A binary relation silent( S1, S2)meanings that a silent moveis possible from S1 to S2.Please show one of the silent facts.

ANS:

(4) (6%) Please define the acceptance of a string from a given state:accepts( State, String)

(A) The empty string, [], is accepted from a state State if State is a final state.

accepts( State, []):-

(B) A non-empty string is accepted from State if reading the first symbol in the string can bring the automaton into some state State1, and the rest of the string is accepted from State1.

accepts( State, [ X| Rest]):-

(C) A string is accepted from State if the automaton can make a silent move from State to State1 and then accept the (whole) input string from State1.

accepts( State, String):-

1