Artificial Intelligence: Solution Set 7

Assigned: Apr. 16
Due: Apr. 23

A. Forward chain infers the following facts and rules:

 
fc_infer_fact(F1,R1,F12) returns F12="child(charles,elizabeth)".
fc_infer_rule(F1,R4,R5) returns R5="anc(charles,Z1) => anc(elizabeth,Z1)".
fc_infer_fact(F2,R1,F13) returns F13="child(charles,philip)".
fc_infer_rule(F2,R4,R6) returns R6="anc(charles,Z1) => anc(philip,Z1)".
fc_infer_fact(F3,R1,F14) returns F14="child(anne,elizabeth)".
fc_infer_rule(F3,R4,R7) returns R7="anc(anne,Z1) => anc(elizabeth,Z1)".
fc_infer_fact(F4,R1,F15) returns F15="child(anne,philip)".
fc_infer_rule(F4,R4,R8) returns R8="anc(anne,Z1) => anc(philip,Z1)".
fc_infer_fact(F5,R1,F16) returns F16="child(william,charles)".
fc_infer_rule(F4,R4,R9) returns R9="anc(william,Z1) => anc(charles,Z1)".
fc_infer_fact(F5,R1,F17) returns F17="child(harry,charles)".
fc_infer_rule(F4,R4,R10) returns R10="anc(harry,Z1) => anc(charles,Z1)".
fc_infer_fact(F11,R5,F18) returns F18="anc(elizabeth,charles)"
fc_infer_fact(F11,R6,F19) returns F19="anc(philip,charles)"
fc_infer_fact(F11,R7,F20) returns F20="anc(elizabeth,charles)"
fc_infer_fact(F11,R8,F21) returns F21="anc(philip,charles)"
fc_infer_fact(F11,R9,F22) returns F22="anc(charles,william)"
fc_infer_fact(F11,R10,F23) returns F23="anc(charles,harry)"
fc_infer_rule(F12,R3,R11) returns R11="female(charles) => daughter(charles,elizabeth)"
fc_infer_rule(F13,R3,R12) returns R12="female(charles) => daughter(charles,philip)"
fc_infer_rule(F14,R3,R13) returns R13="female(anne) => daughter(anne,elizabeth)"
fc_infer_rule(F15,R3,R14) returns R14="female(anne) => daughter(anne,philip)"
fc_infer_rule(F16,R3,R15) returns R15="female(williams) => daughter(william,charles)"
fc_infer_rule(F17,R3,R16) returns R16="female(harry) => daughter(harry,charles)"
fc_infer_fact(F22,R5,F24) returns F24="anc(elizabeth,william)".
fc_infer_fact(F22,R6,F25) returns F25="anc(philip,william)".
fc_infer_fact(F23,R5,F26) returns F26="anc(elizabeth,harry)".
fc_infer_fact(F23,R6,F25) returns F25="anc(philip,harry)".
fc_infer_fact(F10,R13,F26) returns F26="daughter(anne,elizabeth)".
fc_infer_fact(F10,R14,F27) returns F26="daughter(anne,philip)".

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).

Answer: There are many such. E.g. "parent(Y,X) & female(X) => daughter(X,Y)" is a necessary consequence of R1 and R3, but cannot be found by this inference process.