Prolog-ELF Incorporating Fuzzy Logic

1 · INI'RODUcriON

As a basic language for building knowledge systems, Prolog has many preferable features, such as pattern matehing (unification ), automatic backtracking and relatinal database . It has been chosen as the kerne! language of Japanese fifth generation computer . Many Prolog- based knowledge systems have become to appear recently .

. Prolog, which is based on first-order predicate log1c (more precisely, Horn logic ) , deals with only a two-valued log1c. Knowledge sometimes manifests uncertainty in real-world problems . Uncertain knowledge has pl~yed important role in many expert systems , such as Myc1n [t ] , P~ospector[2] , Casnet [3] , Speril[4,5], etc . . Wh~n deal1ng with uncertain knowledge in Prolog, some spec1al prog~amming techniques are required [6] , wh1ch are annoy1ng for us to build a large system. Therefore , ther~ exi~ts a need for a basic language capable of deal1ng w1th uncertain knowledge .

~n fuzzy logic , the uncertainty of a fact or a rule 1s expressed with a truth-value between t and 0. There. are of . course several other methods , such as Myc1n s certa1nty factor [l], subjective Bayesian method [2] , and Dempster-Shafer theory [5] . However : unl1ke these methods, the fuzzy logic has a certain kind of logical feature . This logical feature can be extend~ to a fis~-order predicate logic, which provids

us a nch express1 ve power .

This paper presents a language called Prolog-ELF [7] I.ncorporatl.Ilg fuzzy logic into Prolog . The Prolog-ELF is different from existing fuzzy languages such as described in [8,9] , because the Prolog-ElF is a general -purpose language which inherits all the preferable basic features of Prolog . Moreover . several useful pr~icates are imbedded in the Prolog-ELF. Using these pred1cates , we can manipulate fuzzy sets very

eas1ly to a certain extent .

The Prolog-ELF is implemented on Pascal and completely operational on VAX-tl. Thi s paper describes ~ome f~tur~ and considerations on the Prolog-ELF and 1ts appl1cat1on to a fuzzy logical database.

2. TOWARD FUZZY PROLOO

Although fuzzy sets are considered in general fuzzy logic [10], . we will at first consider logical formu~ae expressed w1 th symbols in ordinaly sense . The certa1nty of the logical formula is expressed with a t~uth-val ue ~, where 1 ~ ~ 0, in the fuzzy logic . (A d1fferent k1nd of fuzzy logic in which linguistic truth-values are used is presented in [11] . )

Let T(P) be the truth-value of a logical formula P. The following treatments of the truth-value are foundamental. c~ denotes NOT.)

lf P=A and A is an atomic formula: T(P)=T(A)

If P=~ : T(P)=l-T (Q)

If P=Q AND R : T(P )=min(T (Q),T(R))

lf P=Q 00 R : T(P)=max(T (Q),T(R)).

For example, if

T(P)=0 .6, T(Q)=0.9, T(R)=0 .8 and S= (P 00 Q) AND ~R

then, T(S)=min (max(T (P) , T (Q)) , 1-T(R)) =min (max (0.6,0.9), 1-0.8) =0 .2 .

Most of logical laws, such as commutative , associative, distributive and DeMorgan's laws, are hold in fuzzy logic, except excluded-middle law; that is . T(P AND ~p ) and T (P OR ~p ) are not al ways 0 and 1 , respecti vely.

Lee[12] and Mukaidono[13] considered the resolution principle as a mechanical inference of fuzzy logic . lf we interprete P->Q as c~p OR Q) in f.uzzy logic, the well-known inference rules, i.e., Modus ponens, Modus tollens and syllogism, become the special cases of the resolution principle. ßy introducing arguments attached to the logical symbol (predicate ) and unification. the fuzzy logic can be extended to fuzzy first-order predicate logic .

Lee[12] has proved that, if all the truth-values of parent clauses are greater than 0.5, then a resolvent clause derived by the resolution principle is always meaningful and has a truth-value between the maximum and minimum of those of the parent clauses. Mukaidono[t3] showed an interpretation that, even if a truth-value of the parent clause is less than 0.5. a resolvent clause is meaningful in the sense of reducing ambiguity .

Expressions in Prolog are restricted to Horn clauses which have at most one positive literal, so that the efficient linear input resolution can work as a complete resolution. If we define a Horn clause witrh a truth-value less than 0.5 in fuzzy Horn logic , it is equivalent to the negation of the clause which goes beyond the scope of Horn clause. Therefore , in order to realize a fuzzy-Prolog, we basically restriet our logical expression to the Horn clause with a truth-value greater than 0.5. The result of the resolution in this case is guaranteed to be meaningful based on the Lee's paper(t2].

lt is a problern if the truth-value of a clause including variables changes when the variables are instantiated by the unification . We take bowever a position that the truth-value of the clause will not change due to the unification.

One major difference in the inference process of fuzzy-Prolog from that of ordinary Prolog is that exhaustive search is often required at an OR-branch, since the maximum truth-value of a literal is looked

for at this branch .

3. PIU.OO-ElF

Prolog-ELF has been implemented based on the above-mentioned principle and by adding some useful functions for a basic language of knowledge systems .

The clauses in Prolog-ELF are expressed in the following forms .

Definition clause : +P-Q···-R. or +P.

Goal clause : -Q· · ·-R.

The truth-value of the clause can be assigned as ;

0.7:+P-Q. or -assert(0 .7:+P-Q. ).

When the definition of the truth-value is omitted, then the default truth-value is 1. If all the clauses have the truth-value 1 , the behavier of the Prolog-ELF is essentially the same as that of ordinary Prolog.

The reason why we have adopted above notation for a clause , i .e . , +P-Q-R. , instead of a popular notation such as P: -Q,R . · is to avoid a question regarding the interpretation of implication. In fuzzy logic, ~PVQ is not only the interpretation of P->Q; there are several other interpretations [10,14] . Using our notation , we can make i t clear that our Prolog-ELF works starting from axioms defined in clause forms, some of which can be interpreted , if appropriate, into implication forms .

A variable in Prolog-ELF is denoted as a character string headed by *· (Single* can be also a variale.) The result of the execution of a goal clause, if its truth-value is larger than a predetermined threshold (described later), is displayed in the form of , for example;

0.75:-P (apple ).

Same of the system predicates characterizing Prolog-ELF are as follows .

(1 )llfRESH : This predicate sets a value given as its argument to a threshold. The clause with a truth-value less than this threshold is ignored or regarded as false . which initiates the ba.cktracking during the execution process . The default of this threshold is 0.5. A threshold below 0.5 is permitted only for exceptional cases , which suffer a risk of going out of the scope of Horn logic . (See a comment regarding a predicate oor. )

(2 )Hode · setting predicates There are three operational modes in Prolog-ELF. The following predicates perform as a switch to change the mode .

(2-1 )~ : The system searches and displays a first-encountered answer regardless of its truth-value . This is the default mode and the behavior is equivalent to that of ordinary Prolog .

(2-2)QI)Em" All the answers are searched and displayed .

(2-3)BEST(n) The system displays top n answers according to their . truth-values . In order to improve search efficiency, a dynamic thresholding strategy is adopted in this mode . The threshold is set dynamically to the value of the n-th truth-value from the top of already obtained answers .

(3)0SEVALUE This pridicate assigns a truth-value given as its argument to the associated clause. Using this predicate , we can represent fuzzy sets very easily as exemplified in Fig . 1 .

(4)VALUE : This is a deterministic predicate which returns a truth-value of a clause given as its first argument to its second argument . For example, suppose that

O.B:+P(a ).

0.6: +P(b).

have been defined. Then , when

-value(-P(+x) ., *Val) .

is executed, +x and +val are at first unified to a and 0. 8, respecti vely. Once the backtrack occurs , +x and *Val are then unified tob and 0.6, respectively. Fig .2 shows an interaction exemplifying a usage of the predicate VALUE.

(5)0iVALIJE : This predicate updates the truth-value of an associated clause to a new value .

(6)MAXC.. , IltAXCL : An exhaustive search for the goal clause with the maximum truth-value is ·essential at OR- branch in fuzzy logic . In general , this is achieved in the BEST (1 ) mode in Prolog-ELF . The use of pr~icates MAXQ and ~a... is another way to specify th1s search. They are also used in sub-goal node for the following reason . For example, if

0.9 :+R(*X)-P(+x )-Q(+X).

0.9:+P(a ).

0.7 :+P (b).

0.6:+Q(a ).

O.B:+Q(b).

are defined. then

T(R(a ))=min (0.9 . min (0.9 ,0.6 ))=0 .6

T(R(b))=min (0.9 , min (0.7 ,0 .8 ))=0 .7.

This means that, if we take an instance of R(*X) with the maximum truth-value, i .e . , R(b) in this case , this instantiation does not necessarily correspond to that of P(+x ) with the maximum truth-value . There exists a case where we want to fix a sub-goal literal to the unification yielding its maximum truth- value . For example, if we add the following clause to the above definition ,

0.9: +S(+x)-maxcl (P(+x) . )-Q(+x) .

then the system operates as follows.

>-maxcl (S (+X). ) .

.

0.6 :maxcl (S(a ). ).

MAXCL is a non-deterministic predicate, whereas DMAXa... is a deterministic predicate. That is , if more than one answers with the same maximum truth-value are obtained , an alternative answer is used upon the backtracking in the case of MAXQ, whereas the search fails upon the ba.cktracking in the case of DMAXCEL.

+Old(*age)-gt(*age,70)-/-usevalue(1) .

+Old(*age)-gt(*age,50)-/-minus(*age,50,*x)

-times(*x,0.015,*y)-plus(*y,0.7,*z)-usevalue(*z).

+Old(*age)-gt(*age,30)-/-minus(*age,30,*x)

-times(*x,0.01,*y)-plus(*y,0.5,*z)-usevalue(*z) .

>-load( demo ) .

>+very(*cl)=value(*cl,*x)-sqr(*x,*y)-usevalue(*y).

success

>-old(60).

0.8500:-old(60).

>-very(-old(60).).

0.7225:-very(-old(60).).

Fig.2 An example of the usage of VALUE. ( > is a system prompt.) The definition of Fig.l is assumed.

(7)NOT : As in ordinary Prolog, NOT fails in the normal threshold setting of Prolog-ELF if there exists at least one answer . However, if the threshold setting is less than 0.5. the result of unification during the execution of NOT may remain in Prolog-ELF. For example, suppose that the threshold is 0.2 and the answer of dmaxcl (P (>t<x ). ) is 0. 7:dmaxcl (P(a).), then not (PC·x ).) will succeed with the truth-value of 0.3 (=1-0.7) and with the unification that >t<X is a .

4. APPLICATICII TO A FtJZZY LOOICAL DATABASE

As an application of Prolog-ELF, a fuzzy logical database including fuzzy rules and fuzzy set concepts is illustrated in Fig.3, where a person who may possibly have a second house is retrieved from stored facts and heuristic rules . Several other applications including a production system have been written by the authors .

5. aH:lliDIN::: HEMARKS

Prolog-ELF incorporating fuzzy logic and related some useful functions has been implemented as a basic language of knowledge systems with uncertainty or fuzziness.

One problern of the Prolog-ELF is its slow speed , since the exhaustive search is often required at the OR node. One way to avoide this problern is to set the threshold to an appropriatly high value. Some mechanisms to improve search efficiency are planned to implement in a future version; but it seems that ultimate solution may be a parallel processors l1ke Japanese fifth-generation computer. A knowledge management mechanism using meta-predicates is scheduled to be added to Prolog-ELF.

AOOIOWI..EIX::MEJ:-IT: The Prolog-ELF has been implemented with reference to the program of Dr. H.Nakashima at Electrotechnical Lab., who is the author of Prolog/KR. The authors are grateful to him.

This work was supported by Grant-i.n-aid tor Special Project Research, Ministry of Education, Japan.

; Have a seoond house ;

+have a second house(Kato).

0.9:+bave a second house(*who)-rich(*who).

0.7:+have:a:second:house(*who)-president(*who).

; Rieb;

+rich(*who)-1ncome(*who,*yen)-rich2(*yen).

+rich2(*yen)-gt(*yen,30000000)-/.

+rich2(*yen)-gt(*yen,15000000)-/

-minus(*yen,1.5e7,*x)-rdiv(*x,1e8,*y)

-times(3,*y,*z)-plus(0.5,*z,*w)

-usevalue(*w).

; Inoome ;

+income(Yamada,20000000).

+income(Sato,25000000).

+income(Nomura,8000000).

• +income(Kobayash1,40000000).

; President ;

+president(Suzuki).

+president(Kobayashi).

(a) database