Introduction to Artificial Intelligence

If the hypotheses become empty, then we conclude that the initial hypothesis is true under the substitution θ.

The following is the back-inference procedure. In this procedure, Hyp and θ are local variables in the procedure. The initial value of Hyp is the initial list of hypotheses (representing the question being asked), and the initial value of θ is the empty substitution.

Input: Knowledge base (FB, RB), Hypothesis Hyp.

Output: Conclude that Hyp is true and give the argument θ or Hyp is not true.

Procedure Backward_Chaining (Hyp, θ) Begin

H ← first hypothesis in the Hyp list; for each rule R = (Conds, Q) do

Begin

if H is united with Q by substitution θ 1 then

1. Remove H from the Hyp list;

2. Add Conds rule conditions to Hyp list;

3. Apply the substitution θ 1 to the hypotheses in the Hyp list;

4. Take the composition of the substitutions θ and θ 1 to obtain a new substitution θ, i.e. θ ← θθ 1 ;

if Hyp = [ ] then give θ

else Backward_Chaining (Hyp, θ); End;

End;

In the backward reasoning procedure, each θ produced is a substitution that makes the initial hypothesis true, i.e. (Hyp) θ = H 1 θ  ...  H m θ is true (which is a logical consequence of the CSTT). Therefore each substitution θ produced by the procedure is an answer to the question posed.

Example 5.11:

Given the events: A (1)

B (2)

and the laws:

R 1 : A  C (3)

R 2 : B  D (4)

R 3 : C  E (5) R 4 : A  D  E (6) R 5 : B  C  F (7) R 6 : E  F  G (8)

Prove G.

Consider the hypothesis Hyp={G} (9) From (8), (9) we deduce Hyp={E, F} (10)

From (7), (10) we deduce Hyp={E, B, C} (11)

From (11), (5) we deduce Hyp={B, C} (12)

From (12), (2) we deduce Hyp={C} (13)

From (13), (3) we deduce Hyp={A} (14)

From (14), (1) we deduce that Hyp=[] So G is proven.

Example 5.12: Given the following logical expressions: A  C (1)

A  B  F (2)

(D  B)  F  I (3)

 H  A  F (4)

F  G  H  I (5)

 A  D  C (6)

A  D  G  H (7)

Prove I by backward reasoning on Horn's rules.

Prize:

- Step 1: Convert the rules into Horn sentence form

+ Considering (1) we deduce A, C

+ Consider (2) which has Horn form

+ Consider (3)  (D  F)  (B  F)  I

 ((D  F)  (B  F))  I

 (  (D  F)  (B  F))  I

 (  (D  F)  I)  (  (B  F)  I)

 ((D  F)  I)  ((B  F)  I) implies D  F  I, B  F  I

+ Consider (4):  H  A  F

 (H  A)  F

 H  A  F

+Consider (5) which has Horn form

+Consider (6): Similar to (4), we have (6)  (A  C  D)

+ Consider (7) we have A  D  G  H, which implies A  D  G and A  D  H (exclusion rule). So we have:

(8)
C	(9)
A  B  F	(10)
D  F  I	(11)
B  F  I	(12)
H  A  F	(13)
F  G  H  I	(14)
A  C  D	(15)
A  D  G	(16)
A  D  H	(17)

Maybe you are interested!

Step 2: Use backward reasoning with Hyp=[I] (18)

- Consider (18), (11)  Hyp={D, F} (19)

- Consider (19), (15)  Hyp={A, C, F} (20)

- Consider (20), (13)  Hyp={A, C, H} (21)

- Consider (21), (17)  Hyp={A, C, D} (22)

- Consider (22), (15)  Hyp={A, C} (23)

- Consider (23), (8), (9)  Hyp=[]

Conclusion: I is proven.

Example 5.13. Consider the zoo rule (mentioned in section 5.3.1) Rule 1: longmao(x)  covu(x) (1)

Rule 2: longvu(x)  chim(x) (2)

Rule 3: know(x)  detrung(x)  chim(x) (3)

Rule 4: covu(x)  anthit(x)  thuanthit(x) (4)

Law 5: covu(x)  rangnhon(x)  mongvuot(x)  thuanthit(x) (5) Law 6: thuanthit(x)  vanghung(x)  domsam(x)  baochauphi(x) (6) Law 7: thuanthit(x)  vanghung(x)  vanden(x)  ho(x) (7) Law 8: chim(x)  bietbay(x)  chandai(x)  codai(x)  dadieu(x) (8)

Law 9: bird(x)  bietbay(x)  bietboi(x)  dentrang(x)  canhcut(x) (9) Suppose there is the following event basis:

longvu(BiBi)

(10)
Chandai(BiBi)	(11)
code(BiBi)	(12)
 know(BiBi)	(13)

Consider the hypothesis Hyp={dadieu(BiBi) } (14)

(14) can be unified with dadieu(x) in (8) by the substitution [x/BiBi], so: Hyp={  bietbay(BiBi), chandai(BiBi), codai(BiBi), chim(BiBi) } (15)

Consider (15) matches (13)  Hyp={chandai(BiBi), codai(BiBi), chim(BiBi) } (16) Consider (16) matches (11)  Hyp={codai(BiBi), chim(BiBi) } (17)

Consider (17) matching with (12)  Hyp={chim(BiBi) } (18)

Consider (18) matching with (2) by substitution [x/BiBi]  Hyp={longvu(BiBi) } (19) Consider (19) matching with (10)  Hyp=[]

Conclusion: The hypothesis "BiBi is an ostrich" is correct.

Example 5.14. Suppose the CSTT includes:

- The legal basis includes the following two laws:

If (x is a horse) and (x is y's mother) and (y runs fast) then x is worth If z wins then z runs fast.

- The event base includes the following events: Tom is a horse

Ken is a horse Kit is a horse Bin is a horse

Tom is Bin's mother Tom is Ken's mother Bin is Kit's mother. Kit runs fast.

Bin won.

Question: Which horse is valuable? Answer:

Define the following predicates:

- Horse(x) (x is horse),

- Mother(x, y) (x is the mother of y),

- Fast(y) (y runs fast),

- Winner(x) (x wins). The CSTT is described as follows: Horse(Tom) (1)

Horse(Ken) (2)

Horse(Kit) (3)

Horse(Bin) (4)

Mother(Tom, Bin) (5)

Mother(Tom, Ken) (6)

Mother(Bin, Kit) (7)

Fast(Kit) (8)

Winner(Bin) (9)

Horse(x)  Mother(x, y)  Fast(y) ⇒ Valuable(x) (10) Winner(z) ⇒ Fast(z) (11)

Note that the events (1) to (9) can be considered as special rules with condition=  .

The initial hypothesis Hyp = [Valuable(w)] and θ = []. The hypothesis Valuable(w) is unified with the conclusion of rule (10) by the substitution θ 1 = [w/x], thus we get a list of new hypotheses

Hyp = [House(x), Mother(x, y), Fast(y)] and θ = θθ 1 = [w/x]

a) Case 1:

The hypothesis House(x) is unified with the event (1) by the substitution θ 1 = [x/Tom], we get a list of new hypotheses

Hyp = [Mother(Tom, y), Fast(y) ] and θ = [w/x][x/Tom] = [w/Tom]

The hypothesis Mother(Tom, y) is unified with the event (5) by the substitution θ 1 = [y/Bin], we get the list of hypotheses Hyp = [Fast(Bin) ]

and θ = [w/Tom][y/Bin] = [w/Tom, y/Bin]

The Fast(Bin) hypothesis is unified with the conclusion of rule (11) by the substitution [z/Bin], so we have Hyp = [Winner(Bin) ]

and θ = [w/Tom, y/Bin, z/Bin]

The hypothesis Winner(Bin) coincides with event (9) (which is unified by the substitution θ 1 = []). Therefore the list of hypotheses becomes empty with the substitution θ = [w/Tom, y/Bin, z/Bin].

So with this substitution, the hypothesis Valuable(w) becomes true, or in other words, Tom is a valuable horse.

b) Case 2:

The hypothesis House(x) is unified with the event (4) by the substitution θ 1 = [x/Bin], we get a list of new hypotheses

Hyp = [Mother(Bin, y), Fast(y) ] and θ = [w/x][x/Bin] = [w/Bin]

The hypothesis Mother(Bin, y) is unified with the event (7) by the substitution θ 1 = [y/Kit], we get the list of hypotheses Hyp = [Fast(Kit) ]

and θ = [w/Bin][y/Kit] = [w/Bin, y/Kit].

The hypothesis Fast(Kit) coincides with event (8) (unified by the substitution θ 1 = []). Therefore the list of hypotheses becomes empty. So Bin is a valuable horse.

c) The remaining cases: doing the same when merging House(x) with the substitution [x/Ken] or [x/Kit] does not result in the list of hypotheses becoming empty.

Conclusion: Tom and Bin are two valuable horses.

5.4. Prolog Programming

5.4.1. Introduction to Prolog language

Prolog is a logic programming language. The Prolog language was first proposed by French professor Alain Colmerauer and his research group at the University of Marseille in the early 1970s. By 1980, Prolog was quickly widely used in Europe and was chosen by the Japanese as the language for developing the 5th generation of computers. Prolog has been installed on Apple II, IBM-PC, and Macintosh computers.

Prolog is also known as symbolic programming language similar to functional programming languages, or non-numerical programming. Prolog is very suitable for solving problems related to objects and the relationships between them.

Prolog is widely used in the field of artificial intelligence. The principle of logic programming is based on Horn propositions (Horn logic). A Horn proposition represents an event or a thing as true or false, occurring or not occurring.

Example 5.15: Here are some Horn clauses:

1. If an old man is wise, he is happy.

2. Jim is a happy man.

3. If X is the parent of Y and Y is the parent of Z then X is the grandfather of Z.

4. Tom is Sue's grandfather.

5. All men are mortal (or If anyone is a man, someone must die).

6. Socrates is a man.

In the Horn clauses above, clauses 1, 3, 5 are called rules, the remaining clauses are called facts. A logic program can be viewed as a database of Horn clauses, either rules or facts, such as all the facts and rules from 1 to 6 above. The user (NSD) calls a logic program by asking a query/question on this database, such as the question:

Is Socrates dead?

(equivalent to affirming that Socrates died true or false?)

A logical system will execute the program in a "deductive" way - searching based on the existing "knowledge" of the program - database, to prove that the question is an assertion, true (Yes) or false (No). With the above question, the system searches in the database to affirm that Socrates died and "finds" the satisfied law 5. Applying law 5, the system receives that Socrates is the person who is event 5. From there, the answer will be: Yes, meaning that the event that Socrates died is true.

5.4.2. Prolog syntax

a) Terms

A Prolog program is a database of clauses. Each clause is built from predicates. A predicate is a statement about objects that has the truth value true or false. A predicate can have logical atoms as arguments.

Each atom (in short) represents a relation between terms. Thus, terms and relations between terms form propositions.

Classes are considered as "data" objects in a Prolog program. Classes can be elementary terms (constants), variables (variables) and compound terms (compound terms).

Complex terms represent complex objects of the problem to be solved in the domain under consideration. A complex term is a functor containing arguments, of the form:

Function_name(Argument_1,..., Argument_n)

A function name is a string of letters and/or numbers starting with a lowercase letter. Arguments can be variables, elementary classes, or compound classes. In Prolog, the special function name "." (dot) represents a list structure. The function data type is similar to the record type and the list is similar to the array type in imperative programming languages (C, Pascal...).

Example 5.16 : f(5, a, b).

student(robert, 1975, info, 2, address(6, 'mal juin', 'Caen')). [a, b, c]

A clause can be a fact, a rule, or a question. Prolog uses a period after each clause to end it, as follows:

• Event: <... >.

(corresponding to the rule <... >:- true.)

• Law: <... >:- <... >.

• Question?- <... >.

(in interactive mode with command prompt)

b) Prolog data types

Prolog has elementary data types and structured data types. This classification identifies the type of an object by its syntactic appearance.

Prolog syntax specifies that each type of object has a different form. Prolog does not need to provide any other information to identify the type of an object. In Prolog, users do not need to declare data types.