Assigned: Apr. 16

Due: Apr. 23

Note: I will be grading this, rather than the grader, so if you submit this by email, send it to davise@cs.nyu.edu.

The forward chaining algorithm involves the repeated application of the two inference subroutines, "fc-infer-fact", and "fc-infer-rule", defined below, which it runs until no new conclusions can be drawn.

fc-infer-fact(in F : fact; R : rule with one literal in the conditions; out G : fact) Let R have the form "A => C" If R uses some of the same variables names as F, then rename the variables; if F matches A under variable binding B then G := the application of B to C end fc-infer1 fc-infer-rule(in F : fact; R : rule with more than one literal in the conditions; out Q : rule) Let R have the form "A1 & A2 ... & Ak => C" If R uses some of the same variables names as F, then rename the variables; If F matches A1 under variable binding B then Q := the application of B to "A2 & ... & Ak => C" end

For instance if you start with

Fact F1: man(socrates) Rule R2: man(X) => mortal(X)fc-infer-fact will match the tail of R2 to F1 under the variable binding X -> socrates, and infer the new fact "mortal(socrates)".

If you start with

Fact F3: parent(elizabeth,charles) Fact F4: female(elizabeth) Rule R5: female(X) & parent(X,Y) => mother(X,Y)first, fc-infer-rule applies to F4 and R5 under X -> elizabeth to infer the new rule

Rule R6: parent(elizabeth,Y) => mother(elizabeth,Y)Second, fc-infer-fact applies to rule F3 and R6 under the binding Y -> charles to infer the new fact

Fact F7: mother(elizabeth,charles).

The entire forward chaining algorithm can be described as follows:

forward-chain(in out FF : set of facts; RR : set of rules) NEW := FF union RR; loop until NEW is empty { pop Z from NEW; if Z is a fact then loop for R in RR if R has form "A => C" and Z matches A then { fc-infer-fact(Z,R,G); if G is not in FF then { add G to FF; add G to NEW} endif } else if R has form "A1, A2 ... Ak => C" and Z matches A1 then { fc-infer-rule(Z,R,Q); if Q is not in RR then { add Q to RR; add Q to NEW} endif } endif endloop elseif Z is a rule of the form "A => C" then loop for F in FF if F matches A then { fc-infer-fact(F,Z,G); if G is not in FF then { add G to FF; add G to NEW} endif } endif endloop elseif Z is a rule of the form "A1 ... Ak => C" then loop for F in FF if F matches A1 then { fc-infer-rule(F,Z,Q); if Q is not in FF then { add Q to RR; add Q to NEW} endif } endif endloop endif } endloop end forward-chain

A. Trace what happens when the forward chaining algorithm is applied to the following knowledge base:

Facts: F1: parent(elizabeth,charles). F2: parent(philip,charles). F3: parent(elizabeth,anne). F4: parent(philip,anne). F5: parent(charles,william). F6: parent(charles,harry). F7: female(elizabeth). F8: male(philip). F9: male(charles). F10: female(anne). F11: anc(X,X). Rules: R1: parent(X,Y) => child(Y,X). R2: child(X,Y) => parent(Y,X) R3: child(X,Y) & female(X) => daughter(X,Y). R4: parent(X,Y) & anc(Y,Z) => anc(X,Z).Your trace should show every call to "fc-infer-fact" and "fc-infer-rule" that generates a new fact or rule.

B. It is possible to prove that, for a Datalog knowledge base, the algorithm
"forward-chain" is *
complete* with respect to the inference of facts. That is, if F is
a fact that is a logical consequence of FF and RR, then F will be returned
in the set of facts returned by forward-chain(FF,RR). Give an example
to show that "forward-chain" is not complete with respect to the inference
of *rules*; that is, an example of a set of facts FF, a set of rules
RR and a conclusion Q such that Q is a logical consequence of FF and RR,
but Q is not in the set of rules returned by forward-chain(FF,RR).

A. As far as is possible, write down the contents of the text in a set of formulas of the form "holds(S,F)" where S is a situation and F is a fluent (in an English language description); "occurs(S1,S2,E)" where S1 and S2 are situations and E is an event (in an English language description); and purely temporal relations between situations (e.g. "S5 occured before S4"; "S6 was less than an hour after S7" etc.)

B. Give three examples of queries that could be answered from your representation.

C. Is there any significant temporal information in this narrative that you have not been able to express in this notation?