338 Chapter 9. Inference in First-Order Logic function FOL-BC-Asx(KB, query) returns a generator of substitutions return FOL-B C-OR ( KB, query, F) generator FOL - 13C - Ort(KB, goal, 0) yields a substitution for each rule (//is rhs) in FETCH-RULES-FOR-GoAL(KB, goal) do (lhs, rise) A— STANDARDIZE VARIABLES((lhw, rhe)) for each 0' in FOL-BC-AND(KB, the, UNIFY(rhs, goad, 0)) do yield 9' generator FOL - BC- AND(KB, goals, 9) yields a substitution if 0 = failure then return else if LENGTH(goals) = 0 then yield 0 else do FIRST(goaLs). REST(goals) for each 0' in FOL-BC-OR(KB, ScasT(0, first), 0) do fur each 0" in FOL-BC-AND(KB, rest, 0') do yield 8" first,rest Figure 9.6 A simple backward-chaining algorithm for first order knowledge bases, •riminal(Wect) Ad■ American(West)1 Weaporay) { Selis(West 1 ,z) Hostile(Nong)I AZ/Nano} Missilery) Missile (M1) ir y/Mj} 1. 1 Owns(Nono 1) Enemy(Nona America) () Proof tree constructed by backward chaining to prove that West is a criminal. The tree should be read depth first, left to right. To prove Cr-writ/a/ ( West), we have to prove the four conjuncts below it. Some of these are in the knowledge base, and others require further backward chaining. Bindings for each successful unification are shown next to the corresponding subgoal. Note that once one subgoal in a conjunction succeeds, its substitution is applied to subsequent subgoals. Thus, by the time FOL- BC- ASK gets to the last conjunct, originally Hostile(z), z is already bound to Nano. Figure 9.7 Section 9.4. Backward Chaining 339 9.4.2 Logic programming Logic programming is a technology that comes fairly close to embodying the declarative ideal described in Chapter 7: that systems should be constructed by expressing knowledge in a formal language and that problems should be solved by running inference processes on that knowledge. The ideal is summed up in Robert Kowalski's equation, Algorithm = Logic ± Control . PROLOG Prolog is the most widely used logic programming language. It is used primarily as a rapidprototyping language and for symbol - manipulation tasks such as writing compilers (Van Roy, 1990) and parsing natural language (Pereira and Warren, 1980). Many expert systems have been written in Prolog for legal, medical, financial, and other domains. Prolog programs are sets of definite clauses written in a notation somewhat different from standard first-order logic. Prolog uses uppercase letters for variables and lowercase for constants—the opposite of our convention for logic. Commas separate conjuncts in a clause, and the clause is written "backwards" from what we are used to; instead of A AB = C in Prolog we have C : A, B. Here is a typical example: - criminal(X) american0q, weapon(Y), sells(X,Y,Z), hostile(Z). IL] denotes a list whose first element is E and whose rest is L. Here is a Prolog program for append ( X, Y, Z ) , which succeeds if list Z is the result of appending lists X and Y: The notation [E append([1,Y,Y). append([AIX],Y,[20]) append(X,Y,Z). In English, we can read these clauses as (1) appending an empty list with a list Y produces the same list Y and (2) [A I Z ] is the result of appending [A X] onto Y, provided that Z is the result of appending X onto Y. In most high-level languages we can write a similar recursive function that describes how to append two lists. The Prolog definition is actually much more powerful, however, because it describes a relation that holds among three arguments, rather than a junction computed from two arguments. For example, we can ask the query append ( X , Y , [ 1 , 2 ] ): what two lists can be appended to give [ 1, 2 ]? We get back the solutions X-[] Y-[1,2]; X=[1] Y=[2]; X=[1,2] Y=[] The execution of Prolog programs is done through depth-first backward chaining, where clauses are tried in the order in which they are written in the knowledge base. Some aspects of Prolog fall outside standard logical inference; • Prolog uses the database semantics of Section 8.2.8 rather than first-order semantics, and this is apparent in its treatment of equality and negation (see Section 9.4.5). • There is a set of built-in functions for arithmetic. Literals using these finiction symbols are "proved" by executing code rather than doing further inference. For example, the

© Copyright 2017 ExploreDoc