Fuzzy Logic and the Resolution Principle

1. Introduction

In recent years, we have witnessed great progress in techniques of designing problem­ solving and question-answering systems (9, 23, 25, 19) . The new approach may be called an axiomatic approach, where facts and information are stored as axioms and the original problem to be solved, or the original question to be answered, is stated as a theorem to be proved.

This axiomatic approach suffers from one drawback. That is, since we store information as axioms, we are assuming that the information is absolutely correct and no uncertainty is involved. But, everyone knows that the real world is full of uncertainty and any machine that is going to work in this real world, such as a robot designed for exploring the surface of the moon, should be able to make intelligent decisions in a "fuzzy" environment.

Obviously, it would be nice if one could combine probability theory with symbolic logic. But we do not s~em to know how to do this. (This was pointed out in (17)). In this paper, we propose that instead of two-valued logic, one may use fuzzy logic (26, 27) which is a special kind of many-valued logic. The proposal to use many-valued logic in problem-solving systems i s nothing new, Green proposed this in 1969 (9). It should be emphasized that the author by no means claims that the problem of uncertainty is well taken care of if fuzzy logic is used. In fact, the main contribution of tnis paper is to show many interesting properties of fuzzy logic which make it suitable for incor­ poration into problem-solving systems .

Despite the author's effort to make this paper self-contained, it may still be too difficult for many naive readers. The reader at least has to have some background in elementary symbolic logic and is encouraged to read (20), (23), and (19) for an introduction to mechanical theorem-proving and its applica­ tions to problem-solving systems.

2. Fuzzy Logic

Fuzzy logic is based on the concepts of fuzzy sets (3, 5, 6, 15, 26, 27) and symbolic logic. In (15) and (13), the discussion of fuzzy logic was limited to propositional

calculus.

We may view fuzzy logic as a special kind of many-valued logic (21, 1, 2) . In fuzzy logi c, the truth-value of a formula, instead of assuming two values, (0 and 1), can assume any value in the interval [0,1] and is used to indicate the degree of truth represented by the formula.

For example, let P(x) represent "x is a 6 large number." Then the truth-value of P(lO ) and P(l0- 6 ) are certainly 1 and 0 respectively. As for P(l25), the truth-value of it may be some value between 0 and 1, say 0.25.

We shall assume that well formed formulas (formulas for short) are defined to be exactly the same as those in two-valued logic. Letting T(S) denote the truth-value of a formulaS, the evaluation procedure for a formula in fuzzy logic can be described as follows:

1. T(S)=T(A) if S=A and A is a ground atomic formula.
2. T(S)=l-T(R) if S=-R . (3) T(S)=min[T(S 1 ),T(S 2 )] if S=S 1 &s 2 .

1. T(S)=inf[T(B(x))jx£0] if S=(x)B and D is the domain of x.
2. T(S)=sup[T(B(x)) jx£0] if S=(Ex)B and D is the domain of x.

Note that if D is a finite set, then (5) and (6) become

The reader should note that two-valued logic is a special case of fuzzy logic; all the rules stated above are applicable in two-valued logic.

Example 1

Consider S=(PvQ)&-R.

Assume T(P)=O. 1, T(Q)=0.7 and T(R)=0.6.

Example 2

Consider S=(x)P(x).

Assume the domain of x is {a 1 ,a 2 ,a 3 } and T(P(a 1 ) )=0.1, T(P(a 2 ) )=0. 7 and T(P(a 3 ) )=0.5.

Example 3

Consider S=(x)(Ey)P(x,y).

Note that T( (Ey)P(x,y) )=T(P(x,a 1 )vP(x,a 2 )).

Therefore, T((x)(Ey)P(x,y))

= T( (P(a 1 ,a 1 )vP(a 1 ,a 2 ) )&(P(a 2 ,a 1 ) vP(a 2 ,a 2 )))

= min[max[P(a 1 ,a 1 ) ,P(a 1 ,a 2 )],

= min[max[O.l,0.3], max[0.2,0.7]]

max[P(a 2 ,a 1 ) ,P(a 2 ,a 2 )]]

min[0.3,0.7]

= 0 .3.

If two-valued logic is used in a problen,­ solving system, one stores a statement if and only if the truth-value of it is 1. (If the truth-value of a statement A is 0, one simply stores -A). In fuzzy logic, obviously we should store a statement A, instead of -A, iff the truth-value of A is greater than or equal to that of -A. That is, we store A iff

In this case, T(A)~0.5.

We can use this concept to define "satis­ fiability" in fuzzy logic. An interpretation I is said to satisy a formula S if T(S)>0.5 under I. An interpretation I is said to falsify S if T(S)<0.5 under I. (According to this definition, 1f T(S)=0.5 under I, then I both satisfies and falsifies S.) A formula is said to be unsatisfiable if it is falsified by every interpretation of it. Again, it should be easy to note that these definitions are com­ patible with those in two-valued loqic . However, in fuzzy logic, "not satisfying" is different from "falsifying" and "not falsifying" is different from "satisfying."

In applying logic to problem-solving systems, we often have to prove the unsatis­ fiability of a formula (lg). We shall devote the next section to this subject.

3. Satisfiability in Fuzzy Logic

In (13), the following theorem was proved.

Theorem

A ground formula S is unsatisfiable in fuzzy logic if and only if it is unsatifiable in two-valued logic.

Regretfully, the above theorem has only been proved for the ground case. In this section, we shall prove a theorem similar to the above one except that the formula does not have to be

a ground formula.

We shall assume that formulas contain no existential quantifiers. Variables that are existentially quantified are all replaced by Skolem functions (7). Due to the existence of distributive and De Morgan's laws, we can also assume that the formula is in the form of a conjunction of clauses where every variable is universally quantified.

Since an interpretation can be defined over any domain,- it seems that we would have to con­ sider an infinite number of domains. For­ tunately, so far as unsatisfiability is con­ cerned, we only have to consider one particular domain, namely, the Herbrand universe (10, 17).

It is assumed here that the reader is familiar with the definition of Herbrand universe.

Given an interpretation I of a setS of clauses over an arbitrary domain D, we can always construct an interpretation I' of S over the Herbrand universe of S that preserves some interesting properties of I. We shall call this interpretation I' the H-interpretation of S with respect to I (over domain D).

Before giving the definition of the H­ interpretation, note that the interpretation I maps every constant occurring in S to some element in D. In case no constant occurs in S, then the basic element a which initiates the construction of the Herbrand universe is assumed to be mapped to any element in D. Thus, every element in the Herbrand universe of S is assumed to be mapped by I to some element in the domain D.

Let I be an interpretation of a set S of clauses over a domain D. Let H denote the Herbrand universe of S. The H-interpretation I' of S (over the Herbrand universe of S) with respect to I is defined as follows:

1. I' maps all constants occurring inS to themselves.
2. let h 1 ,h 2 , ... hn be elements of H. Let f be an n-place function symbol (n>O) occurring inS . In I', f is assigned to be a function which maps {hl'h 2 , ... ,h } (an element in n n H ) to f(h 1 ,h 2 , ... ,hn) (an element in H).
3. Let h 1 , ... ,hn be elements of H. Let P be an n-place (n~O) predicate symbol occurring in S. Let every element hi be mapped to some di in D. If P(d 1 ·. .. ,dn} is assigned a truth­ value t by I, then P(h 1 , ... ,hn) is also assigned the truth-value t.

Example 4

Consider the following clause:

P(a,f(x)).

The interpretation is defined as follows:

D = {1,2}.

Assignment of constants :

Assignment of functions:

a -+ l

f(l) -+ 2

f(2) -+

Assignment of predicates:

T(P(l,l))=0.57

T(P(2 ,l) )=0.47

T(P(l,2))=0.7

T(P(2,2))=0.36

The Herbrand universe of S is H={a,f(a), 2 f (a) .... }.

The H-interpretation I' of S is constructed as follows:

Assignment of constants:

Assignment of functions :

a -. a

f(a) -. f(a)

f 2 (a) -. f 2 (a)

Assignment of predicates:

In this example, it is easy to see that I satisfies S. It is interesting to note that tne H-interpretation I' (over the Herbrand universe of S) with respect to I also satisfies S. In fact, we can prove the following lemma.

Lemma

fuzzy logic, if an interpretation I of of clauses over a domain D does not falsif S, then the H-inter retation I' of S over the Herbrand universe of S does not fa sify S either.

Proof: Assume I' does falsify S. Then there must exist at least one clause C in S such that T(C)<0.5 under I'. let x 1 , ... ,x be the - n

variables occurring in C. Then there exist h 1 , ... hn in the Herbrand universe of S such that

T(C')<O.S where C' is the ground clause obtained from C by replacing every x 1 with hi. Let every

hi be mapped to some di in D by the interpre­

tation I. According to the definition of the H-interpretation of S, if C'' is the ground clause obtained from C by replacing every x 1 with di then T(C' ')~0.5 also. This means that I falsifies S which is impossible. Q.E . D.

Using the above lemma, we can prove the following important theorem.

Theorem 2

A set of clauses is unsatisfiable in fuzzy logic if and only if it is falsified by every interpretation I over the Herbrand universe of S.

Proof :

This part of the proof is trivial. By definition, S is unsatisfiable if and only if S is falsified by all interpretations over any domain, including the Herbrand universe of S.

(b) ( ... )

Assume S is not falsified by an interpre­ tation I over some domain D. According to Lemma l, there exists an interpretation I' over the Herbrand universe of S such that I' does not falsify Seither. This contradicts the assumption. Q.E.D.

It can be easily seen that so far as sat­ isfiability is concerned, the only relevant information is whether a ground atom is assigned a truth-value greater than, equal to or smaller than 0.5 . For example, a ground clause is satisfied by an interpretation if the truth­ value of at least one literal of the clause is greater than or equal to 0.5. Therefore, in the sequel, instead of giving the exact truth-value of a ground atom in an interpretation, we shall merely compare it with 0.5.

Furthermore, since the domain is fixed to be the Herbrand universe, we only have to con­ sider the truth-value of. those ground atoms whose arguments are elements of the Herbrand universe. Let A be the set of ground atomic formulas of the form P(h 1 , ... ,hn) for all n-place predicate

symbols occurring inS, where every h. is an 1 element of the Herbrand universe of S. The set A is called the atom set of S.

We still have not discussed how to determine whether a set S of clauses is unsatisfiable or not . Obviously, we can exhaustively construct all possible interpretations. If a partial interpretation is found to falsify a clause, we may stop constructing that particular interpre­ tation. Let us enumerate atomic formulas in the atom set of S by

Note that each different assignment of truth­ value {with respect to 0. 5) to each A; corresponds to a ·distinct branch of the infinite binary tree shown in Fig . l. Since the path from the root of the tree T to every node N of the tree represents a partial interpretation I of S, we can terminate the tree at node N if I falsifies a clause . In such a case, N is called a failure node. If S is unsatisfiable, then every branch of the semantic tree in Fig . l is terminated by a failure node and vice versa. We shall call the semantic tree T in Fig. l a closed semantic tree if every branch of T is terminated by a failure node.

Although corresponding to every ordering of the elements in the atom set of S, there is a closed semantic tree for S if and only if S is unsatisfiable, we still cannot use this approach until we know that the closed semantic tree is also a finite one. The following theorem essentially shows us that it is indeed the case.

Theorem 3

A set S of clauses is unsatisfiable in fuzz loaic if and on y if corresponding to every or er1ng of the elements of the atom set of S, the semantic tree of S is a finite closed semantic tree.

Proof:

(a) (-+)

Suppose S is unsatisfiable. Then no inter­ pretation over the Herbrand universe of S satisfies S. Therefore every possible assignment of truth-values to A 1 ,A 2 , ... , will falsify at

least one clause of S. Hence every branch of the semantic tree is terminated by ·a failure none. Assume there are infinitely many nodes in the tree, then the initial node would be a node with infinitely many descendants. Moreover, if any node has infinitely many descendants, then at least one of its descendants has infinitely many descendants. Therefore there is a non­ terminating branch in the semantic tree which is impossible . Thus the closed semantic tree must be finite.

This part of the proof is trivial and will be omit ted.

From Theorem 3, we can easily obtain Theorem 4 as follows:

Theorem 4

Since two-valued logic is a special case of fuzzy logic, the above theorem is true for two­ valued logic. A proof of the foregoing theorem in two-valued logic can be found in (4).

Using Theorems 1 and 4, we can now prove the following theorem which is the main contri­ bution of this section.

Tneorem 5

A set S of clauses is unsatisfiable in fuzzy logic if and only if it is unsatisfiable in two-valued logic.

Proof :

(a) ( .. )

Since S is unsatisfiable in fuzzy logic, S must be falsified by every interpretation of S. In particular, S must be falsified by all the interpretations in which the truth-value is either 1 or 0. Thus S must be unsatisfiable in two-valued logic .

(b) H

Since S is unsatisfiable in two-valued logic, there must exist a finite unsatisfiable ( in two­ valued logic) setS' of ground instances in S over the Herbrand universe of S. According to Theorem 1, S' must be also unsatisfiable in fuzzy logic . From Theorem 4, we conclude that S is unsatisfiable in fuzzy logic.

4. The Concept of Logical Consequence in Fuzzy Logic

Given a formula F, we shall define a formula G to be a logical consequence of F if and only if F&-G is unsatisfiable. If F&-G is unsatisfiable, then T(F&-G) <0.5 under all interpretations. If we further require that T(F) >0.5, then T(-G) must not be larger than 0.5. But T(-G)=l-T(G).

Therefore T(G)>0.5 in all interpretations in which T(F) > 0 . 5~ This means that if the degree of truth of F exceeds 0.5, the degree of truth of all logical consequences of F is never smaller than 0.5. Note that our definition of logical consequence in fuzzy logic is compatible with that in two-valued logic. In two-valued logic, T(G)=l whenever T(F)=l.

Using the above definition and Theorem 5, we can establish the following lemma.

Lerrrna 2

A formula G is a logical consequence of a formula F in fuzzy logic if and only if G is a logical consequence of G in two-valued logic.

The proof of this lemma is omitted.

In two-valued logic, tnere is a very good inference rule, called the resolution principle (20), which has been proved complete for deducing logical consequences (12,24,22). In the following , we shall show that the resolution principle is also complete in fuzzy logic . It is assumed nere that the reader is familiar with the resolution principle .

Let S be a set of clauses. The resolution of S, denoted R(S), is the set consisting of members of S together with all the resolvents of the pairs of members of S. The n-th resolution of S, denoted by Rn(s), is defined for n>O as follows:

The completeness theorem in (12) can now be stated as follows :

Theorem 6

Given a setS of clauses, let us define a logical consequence C (C is assumed to be a clause) to be a prime logical consequence of S if there exists no other logical consequence C' of S (C' is also a clause) such that C is also a logical consequence of C'. Theorem 6 can now be stated as Theorem 7.

Theorem 7

if a clause C is a of a setS of clauses,

A similar theorem in the context of fuzzy logic will now be proved. This is accomplished by first proving the following lemma.

Lemma 3

Proof:

Since C is a logical consequence of S in fuzzy logic, by Lemma 2, C is a logical conse­ quence of S in two-valued logic . Assume C is not a "prime" logical consequence of S. Then there is a logical consequence C' of S such that C is a logical consequence of C' in two-valued logic. Applying Lemma 2 again, we will be able to conclude that the relationship governing C, C' and S also holds in fuzzy logic. Thus C is not a "prime " logical consequence of S in fuzzy logic, which contradicts the assumption . Hence C must be a prime logical consequence of S in two-valued logic.

Th is part of the proof is similar to the proof of part (a) above.

Using Theorem 7 and Lemma 3, we can deduce the completeness theorem of the resolution principle in fuzzy logic.

Theorem 8

A fundamental property of probability theory is that "if G is a consequence of F, then P(G)>P(F) ." Beautiful dis cussions on this property can be found in (8) and (14) . We have a s imil ar relationship in two -valued logic . That is, in two-valued logic, if G is a logical con­ sequence ofF, then T(G) >T(F). However, we cannot establish this in-fuzzy logic . Consider the following example .

Example 5

Q is a resolvent (thereby a logical consequence) of cl and c2.

min[max[T( -P) ,T(Q)] ,T(P)]

min[max[0.7,0.2],0 .3]

min[0.7,0.3]

The above example shows that the truth-value of c 1 &c 2 is not necessarily smaller than or equal to that of a logical consequence of cl and c2. But, if T(C 1 &c 2 )>0 .5, we have a different situation .

Lemma 4

Let c 1 ~ 2 be two clauses . Let R(C 1 ~ 2 l denote any resolvent of c 1 ~ 2 _. _If_ ffi 1 &c 2 )>0.5, then T(R(C 1 ~ 2 .2.l..iU.f 1 &c 2 L

Proof:

Without losing generality, we can represent cl and c2 as follows :

where L 1 and L 2 are two disjunctions of literals. R(C 1 ,c 2 )=L 1 vL 2 .

Again, without losing generality, we can assume that

From (l), we conclude that T(L 1 ) can be either equal to or smaller than a.

But T(C 1 &c 2 )=a. Therefore, T(R(C 1 ,c 2 )).:_T(C 1 &c 2 ).

Case 2: Assume T(L 1 )<a.

Consequently, from (2), T(L 2 )~ T(R(C 1 ,c 2 ))

• = T(L 1 vL 2 )
• = max[T(L 1 ),T(L 2 )J~a.

Therefore T(R(C 1 ,c 2 ))~T(C 1 &c 2 ). Q.E.D.

Using the definition of Rn(S), we can extend the result of Lemma 4 to the following

theorem.

Theorem 9

Let S be a set of clauses and T(S)>0.5. Let Cn denote any clause in the set Rn(S). Then for all n>O, T(Cn)>T(S).

Theorem 9 is an interesting theorem. It shows that if every clause in S is something more than a "half-truth" and the most un­ reliable clause has truth-value a, then we are guaranteed that all the logical consequences obtained by repeatedly applying the resolution principle will have truth-value at least equal. to a. We shall discuss the significance of th1s

theorem in the next section.

5. Conclusions

Many readers may find the "min-max" principle in fuzzy logic disturbing. That is, they may find it hard to accept

T(A&B)=min(T(A) ,T(B)]

and T(AvB)=max[T(A),T(B)].

To answer this criticism, we would like to point out that two-valued logic uses ~xac~ly the same evaluation procedure. By reJeCtlng the evaluation procedure of fuzzy logic, one would simultaneously reject that of two-valued logic. We do not believe that fuzzy logic is adequate to describe the complex wor~d we are . living in (it would be simply too na1ve to th1nk that the world can be described by a set of mathematical rules). However, it would not be difficult to see that it is an improvement of two-valued logic; at least it gives us a way to

handle fuzzy information.

The estimation of the truth-value of a statement might be a serious problem to many readers . It was pointed out by Zadeh (26,27) that this has to be subjective. In fact, many readers will find it difficult to believe that "no objective definition of probabilities in terms of actual or possible observations, or possible properties of this world, is adm~ssible" (a famous quote from Sir Harold Jeffreys 1n (11)). Thus if the information is supplied by a human being, he might as well supply the truth-value of it also. If the information is supplied by another machine, say a pa~tern_ recognizer, then a measure of uncerta1nty 1s often associated with it. For example, a pattern recognizer may decid~ that an ~ncoming object is a meteor, not an a1rplane, w1th pro­ bability 0.9. Then this information may be assigned a truth-value of 0.9 since probability often reflects the degree of truth.

Perhaps the most useful theorem proved in this paper is Theorem 9. Suppose we ~ave two sets of clauses, s 1 and s 2 , represent1ng two

sets of information. From s 1 , we can deduce a logical consequence which suggests us to use Highway 70S. From s 2 , we can deduce a logical

consequence which suggests to use Highway 495. We might not know the exact degrees of correct­ ness of these suggestions. But we st1ll can make intelligent decisions based on Theorem 9. For example, let T(S 1 )=0.6 and T(S 2 )=0.9.

According to Theorem 9, we know that the correctness of the second suggestion is at least 0.9 while that of the first one is only guaran­ teed to be not less than 0.6. This further . tells us that the risk of taking the f1rst act1on may be as high as 0.4 while the other ri~k cannot be higher than 0.1. To minimize the max1mum pos­ sible risk, we should take the second suggest1on, i.e., use Highway 495.

In fact, no one in this world uses two­ valued logic to solve problems such as baking a cake, buying a used car or hiring an employee . After all, every competent housewife knows what it means to "generously grease the pan" or "vigorously beat the mixture." If we really want to build a machine with common sense (16), is it not a must that some kind of many-valued logic be used?