CS3710

Assignment #6

Due Date: Nov.4, 2011

1. Suppose we have Prolog facts about named events in terms of the follwing three predicates:

start(<\event>, <\time>), an event started at a particular time
end(<\event>, <\time>), an event ended at a particular time
duration(<\event>, <\length>), an event lasted for a particular length of time

we may have one, two, or all three of these facts about some event, and we can't know in advance which we will have if we have one or two.

(a) Write Prolog rules to infer an end time for some event when there is no end(Event, Time) fact for it, and to infer a start time when there is no start(Event, Time) fact for it.

(b) Define a new Prolog predicate after(Event1, Event2) which is true when its first argument Event1 definitely happened after its second argument Event2 .

(c) Define a new Prolog predicate during(Event1, Event2) which is true when its first argument Event1 definitely happened after its second argument Event2 was happening.

(d) Explain where in a Prolog database of facts these rules should go for things to work right.

2. (a) Suppose that Prolog predicate mystery is queried with its first argument a bound (input) list and its second argument unbound (an output). Describe what the predicate mystery does.

mystery([],[]).
mystery([X],[X]).
mystery([X,Y|L],[X,censored|M]):- mystery(L,M).

(b) Most recursive list-processing definitions have only one basis condition. Why does the preceding definition need two?

3. Use the state-transition framework for solving the classic search problem from recreational mathematics -- the water jugs problem. Write a prolog program to it and show the solution. There are two jugs of capacity 8 and 5 liters with no markings, and the problem is to measure out exactly 4 liters from a vat containing 20 liters (or some other large number). The possible operations are filling up a jug from the vat, emptying a jug into the vat, and transferring the contents of one jug to another until either the pouring jug is emptied completely, or the other jug is filled to capacity. (hint: assume two facts in the database, capacity and natural representation for the volumes of liquid currently in the two jags. specify actions: fills, emptyings, transferings and define movements from a state to another state.)