The Rationality and Decidability of Fuzzy Implications

1 Introduction

Implication is the heart of logic. The truth value of the material implication A-.B in classical logic is determined by the truth values of the antecedent A and the consequent B, i.e. A-B is true iff A is false or B is true. The truth value of the implication should be determined by the conditional relation between the antecedent and the consequent. Because the truth values of the antecedent A and the consequent B cannot determine the causal link between A and B, there are implicational paradoxes in classical logic, i.e. if one regards the material implication as the entailment and each logical theorem in the logic as a valid reasoning for~ then some logical axioms or theorems in the logic, such as A-.(~BVB), (~A!\A)-.B, A-.(B-.A), ~A-.(A-.B), (A-.B) V (B-. A) , (A-.B) V (~A-. B) , (A-.B) V (A-.~ B) and so on, present some paradoxical properties and therefore they have been referred to as 'implicational paradoxes' [Anderson & Belnap, 1975] . For example,' (~AI\ A) -.B' means 'a contradiction implies anything', 'A-. (~BVB)' means 'a tautology is implied by anything'. In 1912, Lewis established modal logic in order to avoid implicational paradoxes. In 1955, Sugihara pointed out that a logic system is paradoxical if it has either a weakest formula ( WF for short) or a strongest formula (SF for short). Where A is a WF iff B entails A for any formula B. Where A is a SF iff A entails B for any formula B. We call a logic system general-implicational- paradox-free (GIPF for short) if it contains neither WF nor SF. In 1956, Ackermann pointed out: ' Rigorous implication, which we write as A-.B, should express the fact that a logical connection holds between A and B, that the content of B is part of that of A ... That has nothing to do with the truth or falsity of A or B.' During the period from the 1950s to the 1970s,Anderson and Belnap[1975] extended the work of Ackermann and proposed variable-sharing as a necessary but not sufficient formal conditon for the relevance between the antecedent and consequent of a valid entailment, i.e. if A entails B then A and B share a variable. They introduced the concept of generic implication ( GI for short) which can be looked as the inference rule of the logic system while the material imp I ication can be looked as a logical connective. Their relevant logic has neither WF nor SF, but its semantic model is not clear and the definition of GI in it needs sever a I axioms.

Let f=L represent the GI in logic L and W stand for the set of all well formed formulas, the belief set of a formula setS is defined by ThdS) = {GI (GEW)!\ ~S f=LG) }. Call a formula setS meaningless under~ tff ThL(S) =W. Call a formula setS contradictory under f=L iff there exists a formula A such that S f=~ and s rL ~A. Call logic L or the GI rL paraconsistent iff there exists a formula set,which is contradictory, but not meaningless under rL· For example, the paraconsistent logic LP proposed by Priest [1979] has no SF, thus the paradoxical implication ~A!\A rLPB does not hold true for arbitrary B in it. The paraconsistent logic can reason rationally when the premise of a theory is contradictory.

Logic L or the GI f=L is monotonic iff VA, B, CE W, if A r=Lc, then A!\B r=Lc. rL is reflexive iff VAE W,Af=~. ~is transitive iff VA,B,CEW, if A rLB and B r=Lc, then A r& We say that rL has WF (or SF) iff L has WF (or SF). ~L is GIPF iff L is GIPF.

The extensions of classical logic into nonclassical logics can be classified into the following two types: one extends the truth value set or the logical connectives; the other modifies the GI. The former improves the expressive power of the logic, the latter modifies the reasoning ability of the logic. For exam­ ple, fuzzy logic [Lee, 1972] extends classical logic's truth value set {0, 1} to [0, 1] so as to reason with uncertain knowledge. The entailments of preferential logics [ Shoham, 1987; Jiang, 1990; Benferhat, 1993] are preferential implications, which are nonmonotonic.

In section 2 of this paper , we will analyse the rationality of some existing fuzzy implications. Section 3 presents two new fuzzy preferential implications and section 4 discusses the decision procedures for these implications.

For convenience, the formulas discussed here wi II be restricted within the propositional version of Lee's system[1972]. Let 1'1 (G) represent the truth value of a formula G under an interpretation I, then VG, HEW, T1 (G) E [0, 1], T1 (-G) =1-TI (G), T. (G/\H) =min <T1 (G), T1 (H)}, T z (GVH) =max {T · (G), T 1 (H) }, T · (Q-+H) =T 1 (-GVH) .

2 Fuzzy Generic Implications

Mukai dono [1982] has argued that:' In researching fuzzy reasoning, the following two pionts should be made clear: (1) What form is adopted as a inference rule for deriving a logical consequence from the premise and how the fuzzy implication is defined ? ( 2) What significance is postulated to fuzzy inference?'.

There have been only a few attempts [Liu and Xiao, 1985; Liu, 1990; Liu eta!, 1991; Lee, 1972;Mukaidono, 1982; Yager, 1985] to extend fuzzy logic to automated reasoning. The Gis of these systems are of the following four types:

• (j) G l=cH iff VI. T1 (G) <T1 (H)
• ® G=>H iff VI, T. (-GVH) >O. 5
• @ G==>H iff VI, if T1 (G) >O. 5, then T1 (H) >O. 5
• @ G==>' H iff VI, if T. (G) >0. 5, then T. (H) >0. 5

Where G and H are formulas . The antecedents of above implications can be formula sets also. A formula set S is regarded as a conjunction of all formulas inS. The truth value of a formula set S is defined by the smallest one of the truth values of formulas inS.

The significance standard of fuzzy implication should be changed when we need the fuzzy inference engine capable of dealing with the incomplete or inconsistent information just like human being. We think that the GI with fewer paradoxes is more significant. We will discuss the properties of the above Gis in this section.

Let I be an interpretation of a formula (seU ~ we say that I satisfies G or I is a model of G iff T1 (G)> 0. 5; if T. (G) <O. 5, then I is said to falsify G. G is said to be valid . iff any interpretation I satisfies Q G is unsatisfiable iff any interpretation I falsifies Q Obvious!~ I satisfies a formula set iff I satisfies every formula in it.

From above definitions,we can prove the following properties:

~ 1 Suppose the formulas G and H share no atom, if G l=cH then G is unsatisfiable, H is valid; if G==>H then H is valid; if G==>' H then G is unsatis­ fiable; if G=>H then G is unsatisfiable or H is valid.

If His valid i.e. Vl,TI(H)>0.5 then VGEW,G==>H holds true, i.e. = > has WF; if G is unsatisfiable i.e. VI, T 1 (G) )>0. 5 then VHE W, G==>' H holds true, i. e. = >' has SF; but the logic system adopting l=c has neither WF nor SF, i. e. I= c is GIPF.

~ 2. => and = >' are not paraconsistent; l=c and = > are paraconsistent.

~ 3.VG, HEW, G=>H holds true in Lee's fuzzy logic iff G-+H is valid in classical logic.

So => has the implicational paradoxes just like the material implication in classical logic and the resolution system in Lee's fuzzy logic [1972] has no formal difference from that of classical logic. The difference between fuzzy proposition and classical proposition exists only in the truth values of atoms.

~ 4.=>, =>' , l=c and -> are all reflexive, transitive and monotonic.

As a result of the monotonic property, even if we have obtained new evidence, we cannot change the conclusions that were derived from the initial belief set, so the logics lack the cognitive or adaptive capabilities.The preferential entailment [Jiang, 1990;Shoham, 1987] is important in the research of nonmonotonic reasoning. We will present two nonmonotonic, paraconsistent fuzzy implications in the following section.

3 Fuzzy Preferential Implications

Deimition l.Vv" VzE [0, 1J. if I v1-0. 51 > I Vz-0. 51, then we say that v 2 is not more exact than v 11 denoted by V1 !»z; if I v1-0. 51 >I vz-0. 51, V1 is said to be more exact than v2, denoted by V1~2·

Deimition 2. Let M1 and M2 be two models of the formula (set) S,M1~ M2 iff for any atom P occurring in S, TMl(P)~Mz(P);M~~Mz iff for any atom P occurring inS, TM1 (P)~M2 (P), and there exists at least one atom Q occurring in S such that TM1 (Q)0Mz (Q) .

Deimition 3. A model M1 of S is called a preferential model iff there exists no model M2 of S satisfying M2 ~ M1.

It merits attention that there are no constraints on the atoms that do not occur in S for the preferential models of S.

Deimition 4. If every preferential model of S is a model of G,we say that the formula(set)S preferentially entails the formula G, denoted by S =>PG; otherwise, we say that ~>p�.

For example: (j) {P,P-+Q} =>pQ, i.e. modus ponens holds true in the inference system using =>p.

@{P, P-+Q, -R/\R}=>pQ, i.e. = >p can work reasonably well while the inference is not affected by the contradictions of the premise.

® {P, P-+Q, ""P}~>pQ, i. e. if a new evidence ""P con­ tradicts the initial supposition {P, P-+Q}, under =>p, we can withdraw the conclusion Q that is derived from the outdated or incomplete premise {P, P-+Q} . This example illustrates the cognitive process.

@ {P, P-+Q, ""Q} ~>p Q, i. e. under =>P , we can withdraw the conclusion Q that contradicts a new evidence ""Q. So, ->p can limit the propagation of contradictions.

~ 5. - >p is reflexive and paraconsistent. Proof:For any formula G, the preferential model of G is obviously a model of G, so G=>P G, i.e. = >P is reflexive.

Since {P, P-+Q, ""P}=>pP, {P, P-+Q, ""P}=>p"" P; {P, P-+Q, "-'P} is contradictory under ->p. {P,P-+Q, "-'P}~>pR referring to the following preferential model of S: l={P=O. 5, Q=I, R=O}, so {P, P-+Q, ""P} is not meaningless under = >p. Thus, = >p is paraconsistent. (Q. E.D.)

For ->Pis reflexive,PA (P-Q} A (""P)->pPA (P-Q) ; from example (j), PA (P-Ql = >p Q; but from example @, PA (P-Q} A (""P) ~>P Q, so = >P is neither transitive nor monotonic.

Let lltonnset(S) denotes the set of atoms occurring in a formula setS; Lit(S)={P, "-'PIPE Atomset(S) } represent the literal set concerning S.

~uoitkn1 5.Let M be a model of formula (set) S, the inconsistent set of M is defined by M!:

M! ={PIPE Atomset (S) and TM(""PAP) =0. 5}.

~ 6.A formula set S is contradictory under = >p iff the inconsistent set of any model of S is not empty.

~ 7.Let M1 and M2 be two models of formula set S, if M,~ M2, then M,! cM2!.

Because any interpretation is a model of a valid formula, S==>p""QVQ for any formula set S, i.e. =>p has WF, so - >p is not GIPF.

l=r is GIPF, but it lacks some reasonable composition. For example, modus ponens does not hold true under I= Ct i. e. { P, P-+Q } II: c Q because under I= {P=O. 5, Q=O}, T1 ( {P, P-+Q}) =min {TI (P), T1 (P-Qj }= 0. 5 ~O=T1 (Q) .

~uoitkn1 6.Let S be a formula set and H be a formula. If T1 (H) > T1 (S) under any preferential model I of S, we say that S l=rPH; otherwise, we say that S II: cpH.

For example: CD {P, P-+Q} I= rP Q, because under the unique preferential model I={P=I, Q=I} of {P, P-+Q}, Td{P,P-+Q}) =I < TdQ)=I, i.e. l=rP can accomplish the rational inference that can not be accomplished by l=r.

® { P, P-+Q } II: rP ""RVR , because under the preferential model I={ P=I,Q=I,R=0.5} of { P,P-+Q }, Td"-'RVR)=0.5;ii=min{TI(P), T1(P-Q)}. i.e. l=rP can avoid the paradox that cannot be avoided by = >p. Similarly, @{ P,P-+Q, ""RAR} l=rp Q; @ { P, P-+Q, ""P} II: CP Q; { P, P-+Q, "" Q} II: CP Q.

It can be proved that for any formulas G and H, if G l=rp H holds true and G and H have no sharing atom, then G is unsatisfiable and H is valid, so l=rP has neither WF nor SF, i. e. I= rP is GIPF.

~ 8. The preferential implication l=rP is reflexive, paraconsistent and GIPF.

Similar to =>p, l=rP is neither transitive nor monotonic.

The comparision among the above fuzzy implications is listed in Table 1:

4 Decision Tableaux

The resolution procedure can be used as a decision procedure for => in Lee's system[I972]: suppose S is a set of clauses, H is a clause, S=>H iff there is a resolution deduction of the empty clause from SU{"-'H}.

Both Mukaidono[I982] and Yager[I985] think that l=r is meaningful. Lee [1972] has proved that, if both the truth values of the parent clauses C, and C2 are greater than 0. 5 under an interpretation I, a resolvent clause R(C1 , C2) derived by the resolution principle is significant, i.e. T1 (C1AC2) <T1 (R(Cl, C2)) . Mukaidono showed an interpretation that, even if the truth value of one parent clause is not greater than 0. 5, a resolvent clause is meaningful in the sense of reducing ambiguity, i.e. T1 (C1AC2AR (C11 C2) )~\ (C1AC2) under any interpretation I. Yager also found that in fuzzy logic the resolution law does not hold true in its usual form and presented some modified inference laws, but didn't prove the completeness of these laws. Liu and Xiao [1985] proposed Operator Fuzzy Logic (OFL) which can represent vague knowledge by fuzzy operators explicitly and without resorting to the use of intermediate truth values at the semantic level. In order to prove that A-resolution is a sound decision procedure for inconsistent clause set in OF4 Liu[I990] introduced the Gl that is = >' when the threshold is 0. 5. [Liu etal, 1991] chose the inference rule that is => when the threshold is 0. 5, but in order to keep the significance of A. -resolution in OFL, they need the A. -pseudoreduction that cannot apply to Lee's fuzzy logic which has no fuzzy operator . Ti II now, nobody has discussed the proof theory of = > or = >' . In brief, the resolution procedure may not be suitable for deciding whether l=c. = > or = >' holds true, and the decision problems of l=c, => and =>' are s t iII open.

Semantic tableaux [Smullyan, 1968] , which are dual forms of Gentzen' s sequent calculi, are widely used in the field of automatic theorem proving. Using the unified notation, we can classify the non- literal propositional formulas of Lee's system[1972] into the following two types:

Type a: AAB,,..., (A VB),,..., (A-+B),,..., -A

Type ~ :

,..., (AAB),AVB,A-+B

We define the direct descendents of them in Table 2 and Table 3 respectively:

Dermition 7.Let S be a set of formulas, the tableau of S, which is denoted by Tbl (S), is a binary tree with formula sets as nodes constructed by the following rules: 1) The root of Tb l (S) is S.

2)For any nodes, of Tbl(S),we generate its direct descendent node (s) by the following rules:

• (j) a rule: If S,={a}U Sj , then S, has one direct descendent node: S,' = {au a 2} U SJ . In this case, S, is called a type a node.

® ~rule: If S,={~}U SJ,then s, has two direct descendent nodes: S,'={~t}U SJ and S,"={~2}USJ . In this case , S, is called a type ~ node.

Obviously, any terminal node of Tbl (S) contains literals only.

~ 1. Suppose all of the terminal nodes of Tbl ({A}) are au .. . , an, the literals in a, are a, u ... , B1m1 for i=1, .. ·, n,thenA=(a11A .. ·Aa1m1) V .. ·V (an 1 /\ "' 1\ Bn mn} ·

DeimoitM>n 8. A terminal node is called closed if it contains some complementary literal pair. A type a node is called closed if its direct descendent node is closed. A type ~ node is called closed if both its direct descendent nodes are closed.A tableau is called closed iff its root is closet

By lemma 1,we. can derive the following conclusion:

Table 3.

PropositM>n 1. Let A be a formula, A is unsatisfiable iff Tbl ( {A}) is closed.

Theorem 1. VA, BE W, A=>B iff Tbl ({A, -B}) is closed. In order to analyse the causal link between the premise and the conclusion, we' II construct tableaux for the premise and the negation of the conclusion respectively to decide whether a implication holds true.

DeimoitM>n 9.Suppose S is a set of formulas, A is a formula, the terminal nodes of Tbl (S) are Su ... , Sn, the terminal nodes of Tbl ({-A}) are au ... , am. If for any iE {1, ·"n}, j E {1, ... m}, there exists some complementary literal pair in S,LJaJ and the complementary literals belong to s, and aJ respectively or both belong to aJ , then we say that the dual tableaux of S and A are closed for = >.

~ 2.Let S be a formula set,A be a formula, S -->A iff the dual tableaux of S and A are closed for=>. Proof:Let the terminal nodes of Tbl (S) be Su ... , Sn; the terminal nodes of Tbl ({-A}) be a 1, ... , am and the literals in aJ be SJ u ... , aJ kJ for j=1, ... ,m.

Suppose the dual tableaux of S and A are closed for = >. By lemma 1, any model I of S satisfies at least one terminal node S10 of Tbl (S) where ioE { 1, ... n} . Since the dual tableaux of S and A are closed for = >, for any j E {1, '"m} there exists some complementary literal pair in S,oLJaJ and the complementary literals belong to S, 0 and aJ respectively or both belong to aJ .

If the complementary literals belong to S,o and aJ respectively, without losing generality, we can suppose LsE S,o, LAE aJ, Ls=- LA. Because I satisfies S,o,Tt!Ls) > 0.5, i.e. T.(-LJ > 0. 5.

If both the complementary literals belong to aJ, we can suppose LA E aJ and "'LAE aJ . Because any interpretation satisfies at least one of LA and -L"' without losing generality, we suppose T, (-LJ > O. 5.

By the arbitrariness of aJ, for every terminal node aJ of Tbl({-A}), I satisfies the conjugate of some literal aJ ·J in aJ where IJ E {l. "'· kJ},j E {l , .. ·,m}.

Thus I satisfies "'81 u /\'"1\"'SJ IJ /\"'1\"'am Jm where l1E {1, ... , k1}, ... , lJ E {1, .. . , kJ}, ... , lmE {1, ... , k.,}. By lemma 1, "'A= (a1 1/\ ... Aa1 kl) V ... V (am 1/\ ... A am -l A=- (-Al=- ((a1 1/\'"Aa1 k1) V·"V (am 1/\'"/\Bm -l) (by the De. Morgan's Law in fuzzy logic) =(-a1 1V'"V"'a1 k1) /\'" /\ ("-' Bm 1V .. ·V-am -l (by the Complete Distributive Law in fuzzy logic) =(-al tA '"/\"'Bm 1) V·"V (- a1 u /\ '"1\"'am · .,) V '"V(-al kl /\'"/\"'Bm -l . So, I satisfies A. By the arbitrariness of I, S==>A holds true.

Suppose S==>A holds true, from the above analysis, we can see that any model I of S satisfies at least one conjunction (-a1 uA'"/\"'SJo IJo /\'"/\"'am · .,) where l1E {1, ... , k1}, ... , IJoE {1, '"kJo}, ... , lmE {1, ... , k.,}. If the dual tableaux of S and A are not closed for = >, there is at least one pair of nodes S,o and aJo (ioE {1, ... , n}, j 0 E {1, ... , m}) that includes no complementary literal pair satisfying the condition that at least one of the complementary literals belongs to ftJo· Suppose LA is a literal of ftJoo LA' is the conjugate of LAJ thus either LAE S, 0 and LA' r{S,o or LA({S,o and LA' r{S,o, i.e. the conjugate of any literal of ftJo doesn't belong to S,o.

We can construct the following interpretation M of S. For any PE Atomset (S):

if PE S,o, -PE S10, then let T .. (P) =0. 6;

if PE S,o, -Pr{S,o, then let T .. (P) =1;

if Pr{S,o, -PE S10, then let T .. (P) =0;

if Pr{S,oo -Pr{S,oo then let T .. (P) =0.

Obviously,M satisfies S,o, by lemma 1, M satisfies S. Since the conjugate of any literal of flJo doesn't belong to S,o, the conjugate of any literal of ftJo is assigned the truth value 0 under lot Specially, T .. (-aJo IJo)=O, this contradicts the assumption that M satisfies (-a. 11;\'" /\"'aJo ·Jo/\'"1\"'a... ,...). Thus we can see, if S==>A, then the dual tableau of S and A are closed for =>. (Q. E. D.)

If every terminal node of Tbl ({-A}) is closed, the dual tableaux of S and A are closed for => for any formula setS. By proposition 1, any valid formula A is a WF of =>,so => is not GIPF.

Corresponding to the preferential implications, we must distinguish the nodes that determine the preferential models.

Let BA (S) = {P I "'P, PE S} for any I iter a I set S. Suppose PS={S1 , ... , S .. }, S, is a literal set for any iE {1, '"n}, s, is called minimum contradictory in PS if there is no SJ (jE {1, ... , n}) satisfying BA(SJ) CBA(S,).

SupposeS is a set of formulas,PS is the set of the terminal nodes of Tbl (S), the mtnlmum contradictory element in PS are called the minimum contradictory terminal nodes of Tbl (S).

~uiHion 10. SupposeS is a set of formulas,A is a formula; the minimum contradictory terminal nodes of Tbl (S) are S1 , ... , S,.; the terminal nodes of Tbl ({-A}) are flto ... , flm. If for any iE {1, ... , n}, jE {1, ... , m}, there exists some complementary literal pair in S,UftJ and the complementary literals belong to S, and flJ respectively or both belong to ftJo then we say that the dual tableaux of S and A are closed for =>p.

~ 2. Suppose S is a formula set, CD any preferential model M of S satisfies at l~ast one of the minimum contradictory terminal nodes of Tbl (S) ; ® any minimum contradictory terminal node of Tbl (S) is satisfied by some preferential model of S.

Proof:Let the terminal nodes of Tbl (S) be S1 , ... , S,.; So. s.oo ... , S .. o be the conjunctions of the formulas in S, s., ... , S., respectively, by lemma 1, So=S10V···VS ..o.

Q)Suppose M1 is a preferential model of S, by lemma 1, M1 satisfies a terminal node S,(iE {l, .. ·,n}) of Tbl(S). If M1 satisfies no minimum contradictory terminal node of Tbi(S), there must exist SJ (jE {1, .. ·, n}) satisfying BA (SJ) C BA (S,), thus there exists Q E Atomset (S) satisfiying QE BA(S,) and Qr{BA(SJ) .

We can construct the following interpretation M2 of S.

For any PE Atomset (S):

if PE SJ, "'PE SJ, then let TM2 (P) =0. 6;

if PE SJ, -Pr{SJ, then let T .. 2 (P) =1;

if P(l'SJ, -PE SJ, then let TM2 (P) =0;

if Pr{SJ, -Pr{SJ, then let T .. 2 (P) =0.

Obviously,M2 satisfies SJ, by lemma 1, Mll satisfies S. For any P E Atomset (S), T .. 2 (P) =0. 6 means PE BA (SJ); because BA (SJ) CBA (S,), this means PE BA (S,); since M. is a model of s,, T ... (P) =0. 6. Qr{BA(SJ) means T .. ll (Q) "0. 6; since M. satisfies S" QE BA(S,) means T .. 1 (Q) =0. 6; thus Mll [8 M ·. This result contradicts the assumption that M1 is a preferential model of S.

Thus we have shown, any preferential model M of S satisfies at least one of the minimum contradictory terminal nodes of Tbi(S). ·

®Suppose SJ (jE {1, ... , n}) is a minimum contradictory terminal node of Tbl (S), we can construct the following interpretation M. of S. For any PE Atomset(S):

if PE SJ, -PE SJ, then let T .. 1 (P) =0. 6;

if PE SJ, -Pr{SJ, then let T ... (P) =1;

if Pr{SJ, -PE SJ, then let T .. 1 (P) =0;

if Pr{SJ, -Pr{SJ, then let Tlo4t (P) =0.

Obviously,M1 satisfies SJ, by lemma 1,M1 satisfies S. If M1 is not a preferential model of S, there must exist a preferential model M2 of S satisfying M~ M11 by property 7 of section a,M2! C M.!. The truth values of the atoms under M. can only be 0, 0. 6, 1 and no truth values can be more exact than 0 or 1, so M2! C M.! . By lemma 1, M2 must satisfies some terminal node S, (iE {l, .. ·,n}) ofTbi(S). BA(S,)cMll! eM.! =BA(SJ). This contradicts the assumption that SJ is a minimum contradictory terminal node of Tbl (S). Thus we can see, any minimum contradictory terminal node of Tbl (S) ia satisfied by some preferential model of S. (Q.E.D.)

By lemma 2,we can prove the following theorem

~ 3. LetS be a formula set, A be a formal~ S =>p A iff the dual tableaux of S and A ate closed for ==>p.

Similarly, we can solve the decision problem of l=rP· ~uiHion ll.Suppose S ia a formula set, A is a formula; the minimum contradictory terminal nodes of Tbl (S) are S1 , ... , S,.; the terminal nodes of Tbl ({-A} ) are fl11 ... , ft..,. If for any iE {1, ... , n}, j E {1, ... , m}, there exists some complementary literal pair in S,UftJ and the complementary literals belong to S, and ftJ

respectively or both belong to ftJ and the complementary literals belong to Lit (S) or s, is closed and ftJ is closed, then we say that the dual tableaux of S and A are closed for l=rP·

~ 3.Suppose S is a set of formulas; the minimum contradictory terminal nodes of Tbl (S) are Su ... , S .. ; So, S101 ... , S .. o are the conjunctions of the formulas inS, S1 , ... , s .. respectively; then under any preferential model I of S, T, (So) =T, (S.oV"·VS,.o).

Proof:Suppose PS is the terminal node set of Tbl (S) . If PS={Su ... , S,.}, by lemma 1, T, (So) =T, (S.oV"·VS,.o). Otherwise, we can derive the conclusion as follows:

Firstly, the truth values of the atoms occurring inS under a preferential model I of S can only be 0, 0. 5, 1.

Secondly, by lemma 2, any preferential model I of S satisfies at least one minimum contradictory terminal node S1 of Tbl (S) (i E {1, ... , n}), i.e. T. (S10l > O. 5; and for any SLE PS- {S1 , ... , Sn } , SL contains some complementary literal pairs, so T. (SLO) <O. 5. By lemma 1, T. (So) =max{T. (SLO) ISLE PS} =max{T. (SLO) I LE {1, ... , n} } =T. (S10 V ... VSnol. (Q.E.D.)

By lemma 3,we can prove the following thoerem: Theorem 4.Let S be a formula set, A be a formula, S l=cPA iff the dual tableaux of S and A are closed for l=cp.

Similar to the decision procedures given by theorem 2, 3 or 4, we have the following decision methods for l=r and=>' respectively:

S l=rA iff for any terminal node S1 of Tbl (S) and any terminal node aJ of Tbl ({~A}), there exists some complementary literal pair in S1U aJ and the complementary literals belong to sl and aJ respectively or S1 is closed and aJ is closed.

S==>' A iff for any terminal node S1 of Tbl (S) and any terminal node aJ of Tbi({~A}), there exists some complementary literal pair in sl u aJ and the complementary literals belong to sl and aJ respectively or both belong to S1.

As space is limited, the proofs will be omitted here.

By the different conditions required in theorem 2, 3

or 4,we can see that the above fuzzy implications have different paradoxes.

5 Applications and Conclusions

The dual tableaux method presented in this paper is important in the research of the model semantics of the generic implications. It is easy to adapt it for other logic systems, such as [Liu, 1990; Shoham, 1987; Priest, 1979] .

Our treatment of inconsistency gives a robust semantics for logic programs and the decision tableaux for l=cP can be used as a framework for the nonmonotonic, paraconsistent fuzzy Prolog [ISHIZUKA and KANA I, 1985]. The dua I tableaux method, as compared with resolution deduction, has more potential parallelism to exploit. While querying a given large database S many times, the minimun contradictory terminal nodes of Tbl (S) can be stored beforehand; for any simple query A, the decision problem whether S l=rPA holds true can be solved quickly.

l=rP is nonmonotonic, paraconsistent and GIPF, so is more reasonable. It is capable of reasoning by the inconsistent, incomplete or imprecise knowledge without taking away any piece of knowledge [Benfer hat eta!, 1993]. Thus it applies to the design of adaptive expert systems or very large knowledge bases where inconsistent information is often present.

Acknowledgements

This work was supported by National Natural Science Foundation and National High-tech Program of P.R. China. We are indebted to the referees for suggested revisions.