Prolog terms
Author Message Prolog terms

Can anybody give me answer to the following Prolog terms
terms match, give the substitutions that make the terms equivalent.

a)        A(X,[Y,Z]) and a(x,y,z)

b)        A([],X) and a([Y,Z], d)

c)        A(A,[a, b]) and a([b,a], B)

Btw  Which is best site to study about prolog

Sun, 26 Jun 2005 17:24:54 GMT  Prolog terms

<snip request for doing homework>

Quote:
> Btw  Which is best site to study about prolog

Right between your ears, with a good book in front of your nose.

--
Nasrudin walked into a teahouse and declaimed, "The moon is more useful
than the sun."  "Why?", he was asked.  "Because at night we need the
light more."

Mon, 27 Jun 2005 01:46:10 GMT  Prolog terms

Quote:
>Can anybody give me answer to the following Prolog terms
>terms match, give the substitutions that make the terms equivalent.

>a)        A(X,[Y,Z]) and a(x,y,z)

>b)        A([],X) and a([Y,Z], d)

>c)        A(A,[a, b]) and a([b,a], B)

No.  Half of them aren't valid Prolog terms, so the question is
meaningless.

Nick
--

Tue, 28 Jun 2005 00:23:55 GMT  Prolog terms

Quote:

> Can anybody give me answer to the following Prolog terms
> determine whether the terms match. Justify your answers and, where the
> terms match, give the substitutions that make the terms equivalent.

> a)        A(X,[Y,Z]) and a(x,y,z)

> b)        A([],X) and a([Y,Z], d)

> c)        A(A,[a, b]) and a([b,a], B)

I will assume that the version of Prolog you are using allows
variables to have arguments.

definition of what it means to unify Prolog terms.

Here is such a definition [taken from Chin-Lin Chang and Richard
Char-Tung Lee, /Symbolic Logic and Mechanical Theorem-Proving/, Academic
Press, 1973, and modified for the purposes of this discussion]:

Definition 1. The /disagreement set/ of a nonempty finite set W of
Prolog terms is obtained by locating the first symbol (counting from the
left) at which not all terms in W have exactly the same symbol, and then
extracting from each term in W the constituent term that begins with the
symbol occupying that position. The set of these respective constituent
terms is the disagreement set of W.

Example:

W = { p(X,f(Y,Z)), p(X,a), p(X,g(h(k(X))) }
^^^^         ^^^^    ^^^^

The disagreement set of W is

D = { f(Y,Z) , a , g(h(k(X))) }

Definition 2. Unification Algorithm

Let W be a set of Prolog terms.

Step 0. If the members of W are identical, stop; W is unified.

Otherwise, go to Step 1.

Step 1. Find the difference set D for W.

Step 2. If there exist elements v and t in D such that v
is a variable that does not occur in t, go to Step 3.

Otherwise, stop; W is not unifiable.

Step 3. Replace every occurrence of v in W by t
and go to Step 0.

Example 1.

 W = { p(a,X,f(g(Y))), p(Z,f(Z),f(U)) }
^^              ^^

 D = { a , Z }

 v = Z , t = a

 W = { p(a,X,f(g(Y))), p(a,f(a),f(U)) }
^^^^            ^^^^

 D = { X , f(a) }

 v = X , t = f(a)

 W = { p(a,f(a),f(g(Y))) , p(a,f(a),f(U)) }
^^^^^^^^^^^         ^^^^^^^^^^^

 D = { g(Y) , U }

 v = U , t = g(Y)

 W = { p(a,f(a),f(g(Y))) , p(a,f(a),f(g(Y)) }

 Done.

Example 2.

 W = { [a,X,Y] , [a,Y,c] }
^^^       ^^^

 D = { X , Y }

 v = X , t = Y

 W = { [a,Y,Y] , [a,Y,c] }
^^^^^     ^^^^^

 D = { Y , c }

 v = Y , t = c

 W = { [a,c,c] , [a,c,c] }

 Done.

Example 3.

 W = { A(A,[a, b]) , a([b,a], B) }
^             ^

 D = { A , a }

 v = A , t = a

 W = { a(a,[a, b]) , a([b,a], B) }
^^            ^^

 D = { a , [b,a] }

 Fail.

Theorem [stated without proof]: The Unification Algorithm  given above
will terminate at Step 0 if and only if the set W is unifiable, and it
will terminate at Step 2 if and only if the set W is not unifiable.

Quote:

> Btw  Which is best site to study about prolog

If you want to develop any meaningful degree of skill at using Prolog,
you have to be willing to spend at least 120 solid hours writing Prolog
programs and debugging them on a computer -- and that's just for starters.

I do not recommend using any of the so-called standard versions of
Prolog for that purpose. I do recommend using Turbo Prolog 2.0 or PDC
Prolog 3.21 on MS-DOS -- if you can still find copies anywhere -- or PDC
Visual Prolog 5.2 for Windows. A "nagged" version of 5.2 can be freely
recommend grabbing a copy while it is still available if you are
that interested. (PDC Visual Prolog 6.0 is in early alpha stage.)

Bill
--
http://www.sonic.net/~sequitur

Tue, 28 Jun 2005 11:50:09 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages