Language American English 1

FUZZY METALOGIC FOR CRISP LOGICS

Giangiacomo Gerla

D.I.I.M.A., Università di Salerno, Via S. Allende 84100 Baronissi, Italy. gerla@matna2.dma.unina.it

Keywords: Approximate reasoning, fuzzy sets, closure operators.

Abstract

I consider examples of fuzzy logic borning from a fuzzyfication of the main metamatematical notions of a crisp logic (in particular, the one of hypothesis, deduction relation, matching, inference rule, and so on). The necessity logic, similarity logic, the theory of graded consequences, are examples of such an approach. Also, I show that these logics are strictly connected.

1 Introduction.

In my opinion, two possible approaches to fuzzy logic are possible. In the first one the semantics is based on (vague) predicates arising from a fuzzy world. To represent the vagueness of such predicates we have to refer to an algebra U of truth values that is larger than the usual Boolean algebra {0, 1}; so, a model is a map m : 𝔽 →U from the set 𝔽 of formulas of a given language into the set U of truth values. This is in accordance with the tradition of the multivalued logics, obviously. Nevertheless, the ideas of fuzzy logic are completely new with respect to the role of the deduction apparatus. Indeed, while the students on multivalued logic aim (only) to find a deduction apparatus able to produce the set of tautologies, fuzzy logics is interested to find tools to deduce new, more complete, information from the available partial information on the fuzzy world under consideration. The partial information is represented by a fuzzy subset v : 𝔽 →U expressing lower constraints on the actual truth values of the formulas. This means that the information carried on by v is that the actual truth value of any formula α is greather or equal to v(α). The deduction operator D associates the fuzzy subset of hypothesis v with the fuzzy subset of logical consequence D(v), one defines in a suitable way. In this case usually fuzzy logic is related with Lukasiewictz logic (see, for example, Pavelka [1979]c, Novak [1987]). Nevertheless, a similar approach is useful also for an intervalbased probability logic (Gerla [1994]b, Biacino [1991]).

In order to extend such an approach, in Gerla [1998]a and Gerla [1998]b we propose the following definitions. We call constraint any subset X of U and we fix a class ℭ of possible constraints. It is useful to assume that ℭ is a closure system and therefore a complete lattice. Moreover, we say that a constraint Y improves a constraint X if Y ⊆ X and that a truth value λ satisfies X provided that λ ∈ X. As an example we can set ℭ equal to the class of interval constraints

ℭ = {[a, b] | a ≤ b, a ∈ U, b ∈ U}.

Then, the pieces of information we have to elaborate are maps V : 𝔽 → ℭ from the set of formulas 𝔽 into the lattice ℭ of possible constraints, we call ℭsubsets. The information carried on by V is that, for any formula α, the actual truth value of α satisfies V(α). In other words m is a model of V provided that m(α) ∈ V(α) for every formula α. Also, the deduction operator D have to be a tool to improve these constraints, i.e., D have to transform the ℭ-subset of hypothesis V into a new ℭ-subset D(V) : 𝔽 → ℭ in such a way that:

- D(V) has the same models than V,

- for every formula α, V(α) ⊇ D(V)(α)

- there is some formulas α,such that V(α) ⊃ D(V)(α).

Such an approach extends the usual one considered in fuzzy logic. Indeed, if v is a fuzzy subset of hypothesis then for each formula α, v(α) represents the constraint [v(α), 1] on the actual truth value of α and D(v)(α) the improved constraint [D(v)(α), 1] ⊆ [v(α), 1]. In other words, in literature one refers to the class ℭ = {[a, 1] | a ∈ U} of constraints.

The second point of view, we consider in this paper, is rather different. Indeed, one starts from a ”crisp” logic (for instance the usual classical propositional calculus) and one ”fuzzyfies” some metamatematical notions such as the one of hypothesis, deduction relation, matching, inference rule, and so on. In this case no semantics exists and therefore no completeness theorem is possible. As an example, the meaning of a fuzzy subset of axioms v is not that any formula α is true at degree v(α) and neither that α is true at least at degree v(α). Its meaning is that we accept α as a (classical) axiom only at degree v(α). The necessity logic, similarity logic, the theory of graded consequences, are examples of such an approach (see Biacino and Gerla [1984], Biacino and Gerla [1992]a, Biacino and Gerla [1993], Chakraborty [1988], Chakraborty [1998], Gerla [1994]a, Gerla [1997], Ying [1994]).

In this paper I confine myself only to examine such a point of view and, in particular, to establish some connections among necessity logic, similarity logic, fuzzy sequent calculus, graded consequence theory, and an extension principle proposed in Ramik [1983], Ramik [1986], Biacino and Gerla [1996] and Gerla [1994]a.

At first, we propose a very general definition of abstract fuzzy logic that is in accordance with Tarski’s point of view.

2 Abstract fuzzy deduction systems.

Let U be the interval [0, 1] and set, for every λ and λ′ in U, λ ∨ λ′ = max{λ, λ′} and λ ∧ λ′ = min{λ, λ′}. Then, (U, ∨, ∧) is a complete, completely distributive lattice whose minimum is 0 and maximum 1. Let S be a set, then a fuzzy subset is any map from S in U. We denote by 𝔉(S) the class of the fuzzy subsets of S. The basic notions of set theory are extended to the fuzzy subsets as follows. The inclusion relation is defined by setting, for every pair s and s′ of fuzzy subsets s ⊆ s′ provided that s(x) ≤ s′(x) for every x ∈ S. The union s ∪ s′ and the intersection s ∩ s′ of two fuzzy subsets s and s′ are defined by setting (s ∪ s′)(x) = s(x) ∨ s′(x) and (s ∩ s′)(x) = s(x) ∧ s′(x), respectively. More generally, given a family (s_{i})_{i∈I} of fuzzy subsets of S, the union and the intersection are defined by

(⋃_{i∈I} s_{i})(x) = Sup{s_{i}(x) | i ∈ I} and (⋂_{i∈I} s_{i})(x) = Inf{s_{i}(x) | i ∈ I}.

In this way 𝔉(S) becomes a complete, completely distributive, lattice, i.e., the direct power with index set S of (U, ∨, ∧). Such a lattice extends the lattice (𝔓(S), ∪, ∩) of the subsets of S. Indeed, if we call crisp a fuzzy subset s such that s(x) ∈ {0, 1} for every x ∈ S, then we can identify the classical subsets of S with the crisp fuzzy subsets of S via the characteristic functions. As an example, we identify the empty set with the map constantly equal to 0 and S with the map constantly equal to 1. Recall that a closure operator in S is any map J : 𝔓(S) → 𝔓(S) such that, for every X and Y in 𝔓(S),

X ⊆ Y ⇒ J(X) ⊆ J(Y) ; X ⊆ J(X) ; J(J(X)) = J(X).

J is called compact provided that

J(X) = ⋃{J(X_{f}) | X_{f} ⊆ X, X_{f}finite}.

Let 𝔽 be a set and D a compact closure operator in 𝔽. Then, in accordance with Tarski point of view, we say that (𝔽, D) is an abstract deduction system.

Likewise, a fuzzy closure operator in S is any operator J : 𝔉(S) → 𝔉(S) satisfying

(i) s_{1} ≤ s_{2} ⇒ J(s_{1}) ≤ J(s_{2}) (monotony)

(ii) s ≤ J(s) (inclusion)

(iii) J(J(s)) = J(s) (idempotence).

If (iii) is skipped, then we say that J is an almost closure operator. In order to give a natural counterpart of the notion of compactness we need the following definitions. A nonempty class C of fuzzy subsets is directed if

x_{1} ∈ C and x_{2} ∈ C ⇒ ∃z ∈ C, x_{1} ≤ z and x_{2} ≤ z.

In this case we call limit the union s = ⋃(C) and we write s = limC. The chains are typical examples of directed classes. If J is an order-preserving operator and C is directed, then the image J(C) = {J(s) | s ∈ C} is also directed, obviously. This enables us to give the following definition.

An order-preserving operator J is called continuous if, for every directed class C,

J(limC) = limJ(C).  (1)

The following general definition is in accordance with Tarski point of view. Let 𝔽 be a set whose elements we call formulas and D a continuous fuzzy

closure operator in 𝔽. Then the pair (D, 𝔽) is called an abstract fuzzy deduction system and D is called a deduction operator. A theory is defined as a fixed point of D.

So, τ is a theory iff τ ≥ D(τ), i.e., τ is a fuzzy set of formulas closed under deductions. In particular, the whole set of formulas 𝔽 is a theory, we call the inconsistent theory. If τ is a theory and v a fuzzy set of formulas such that D(v)=τ, then we say that v is a system of axioms for τ. A fuzzy set v of formulas is consistent provided that D(v) ≠ 𝔽.

Notice that usually in a crisp logic we can obtain a deduction operator D by starting from an immediate consequence operator H. More precisely, given a set X of formulas, let H(X) be the set of formulas that are either logical axioms, or elements in X or are obtained by one application of an inference rule to formulas in X. Then D(X) = ⋃ H^{n}(X). To extend such an approach to fuzzy logic recall the following theorem whose proof is immediate.

Let H be a continuous fuzzy almost closure operator and set, for every subset X of 𝔽,

D(X) = ⋃_{n∈N} H^{n}(X).

Then D is a continuous closure operator, we call the closure operator generated by H.

We say that (𝔽, D) is a step-by-step deduction system if an almost closure operator H exists such that D is generated by H.

3 Fuzzy deduction systems in Hilbert style.

In its papers J. Pavelka proposed a very general notion of fuzzy logic in Hilbert style. Namely, let 𝔽 be a set whose elements we call formulas, then a fuzzy deduction system on 𝔽 is a pair S = (a, ℝ) where a is a fuzzy subset of 𝔽, the fuzzy subset of logical axioms, and ℝ is a set of fuzzy rules of inference. In turn, a fuzzy rule of inference is a pair r = (r′, r′′), where

- r′ is a partial n-ary operation on 𝔽

- r′′ is an n-ary operation on U such that

r′′(x_{1}, ..., Sup_{i∈I} y_{i}, ..., x_{n}) = Sup_{i∈I}r′′(x_{1}, ..., y_{i}, ..., x_{n})  (2)

So an inference rule r consists of a syntactical component r′ that operates on formulas (in fact, it is a rule of inference in the usual sense) and an evaluation component r′′ that operates on truth values to calculate how the truth value of the conclusion r′(α_{1}, ..., α_{n}) depends on the truth values of the premises α_{1}, ..., α_{n}. A proof π of a formula α is a sequence α_{1}, ..., α_{m} of formulas such that α_{m} = α, together with a sequence of related ”justifications”. This means that, for every formula α_{i}, we have to specify whether

(i) α_{i} is assumed as a logical axiom or; (ii) α_{i} is assumed as a proper axiom or; (iii) α_{i} is obtained by a rule (in this case we have to indicate also the rule

and the formulas from α_{1}, ..., α_{i−1} used to obtain α_{i}).

The justifications are necessary to evaluate the proofs. Let v : 𝔽 → U be any fuzzy set of formulas that we call initial valuation or fuzzy set of proper axioms. The meaning of v is that for every α we belief that α is true at least at degree v(α). Moreover, for every i ≤ m denote by π(i) the proof α_{1}, ..., α_{i}. Then the valuation V al(π, v) of π with respect to v is defined by induction on m by

V al(π, v) = a(α_{m}) if α_{m} is assumed as a logical axiom

V al(π, v) = v(α_{m}) if α_{m} is assumed as a proper axiom

V al(π, v) = r′′(V al(π(i_{1}), v), ..., V al(π(i_{n}), v))

if α_{m} = r′(α_{i1}, ..., α_{in}) with i_{1} < m, ..., i_{n} < m.

Now, unlike the crisp deduction systems, in a fuzzy deduction system different proofs of a same formula α may give different contributions to the degree of validity of α. This suggests setting

D(v)(α) = Sup{V al(π, v) | π is a proof of α}.  (3)

This formula defines, for every initial valuation v, a fuzzy subset D(v) we call the fuzzy set of formulas deduced from v. Also, we call deduction operator the function D : 𝔉(𝔽) → 𝔉(𝔽) so defined, i.e., the operator associating any fuzzy subset v of hypotheses with the fuzzy subset D(v) of its consequences. The following proposition was proven in Pavelka [1979]a.

Let S = (a, ℝ) be a fuzzy deduction system and D the related deduction operator. Then D is a continuous fuzzy closure operator and therefore (D, 𝔽) is an abstract deduction system.

Notice also that, by extending in a suitable way recursiveness theory to fuzzy subsets, it is possible to prove that if v is decidable, then D(v) is recursively enumerable and that if D(v) is complete, then it is decidable (see Biacino and Gerla [1989], Biacino and Gerla [1992]b).

The notion of crisp deduction system, in Hilbert style, can be obtained by some obvious modifications of the notion of fuzzy deduction system. Namely, a crisp rule of inference is any partial operation in 𝔽, a crisp deduction system is a pair S = (𝔸, ℝ) such that 𝔸 is a subset of 𝔽, we interpret as the set of logical axioms, and ℝ a set of crisp inference rules. The notion of a proof π under the set X of hypothesis is immediate and we call deduction operator the operator D defined by

D(X) = {α ∈ 𝔽 | aproofofα existswhosehypothesisarein X}.  (4)

Sometimes we write X ⊢ α to denote that α ∈ D(X), α_{1}, ..., α_{n} ⊢ α to denote that α ∈ D({α_{1}, ..., α_{n}}) and ⊢ α to denote that α ∈ D(∅).

4 An extension principle for necessities and fuzzy Herbrand models.

In Gerla [1998] a way to extend any crisp deduction system S into a fuzzy deduction system S^{∗} is proposed and examined. This way is related with a more general extension principle for closure operators (see Ramik [1983], Ramik [1986], Gerla [1994]a, Biacino and Gerla [1996]). Indeed, given an n−ary crisp rule of inference r, we say that the fuzzy rule r^{∗} = (r′, r′′) is the canonical extension of r if r′ = r and r′′(x_{1}, ..., x_{n}) = x_{1} ∧ ...∧x_{n}. Given a crisp deduction system S = (𝔸, ℝ) we call canonical extension of S the fuzzy deduction system S^{∗} = (a^{∗}, ℝ^{∗}) where

- a^{∗} is the characteristic function of 𝔸

- ℝ^{∗} = {r^{∗} | r ∈ ℝ}.

Note that we can consider any continuous T-norm instead of the minimum ∧ in defining such an extension. It is rather immediate to prove the following proposition.

Let S be a crisp deduction system. Then the deduction operator D^{∗} of the canonical extension S^{∗} can be obtained by the formula

D^{∗}(v)(α) = \{ \begin{matrix}1 & if α ∈ T au \\ Sup\{v(γ_{1}) ∧ ... ∧ v(γ_{m}) | γ_{1}, ..., γ_{m} ⊢ α\} & otherwise \end{matrix}  (5)

where T au is the set {α ∈ 𝔽 | ⊢ α} of the tautologies.

In accordance with the point of view considered in this paper, (5) is a multivalued interpretation of the (metalogical) claim

”γ_{1}, ..., γ_{m} exist belonging to v such that γ_{1}, ..., γ_{m} ⊢ α”.

Indeed, in a multivalued setting the claim ”γ_{1}, ..., γ_{n} belong to v” is evaluated by the number v(γ_{1}) ∧ ... ∧ v(γ_{m}) and the quantifier ∃ is interpreted by the supremum operator.

Example. Let us assume that S is a classical first order logic in a language for set theory, denote by CA the choice axiom and by T a system of axioms for set theory containing CA. We can consider the fuzzy subset v of axioms such that:

v(α) = 0.8 if α in CA

v(α) = 1 if α ∈ T −{CA}

v(α) = 0 otherwise.

Then it is immediate that

D^{∗}(v)(α) = 1 if we can prove α without CA

D(v)(α) = 0.8 if we need CA to prove α

D(v)(α) = 0 otherwise.

This simple example enables us to emphasize that the fuzzyness we consider is not semantical in nature. Indeed v(α) is neither a truth degree nor a constraint on the actual truth degree of α. Rather, v(α), in a sense, represents the degrees of acceptability for α as an axiom. In this sense, by recalling the Euclidean distinction between axioms and postulate, perhaps should be better to say that v is the fuzzy subset of acceptable postulates. Thus, in spite of the fact that no vague predicate is considered in classical set theory, in the metalanguage it is reasonable to consider the vague predicate ”acceptable” and represent it by the fuzzy subset v.

It is also interesting to observe that we can use the notion of a canonical extension of the classical propositional calculus to justify the notion of generalized necessity. Recall that if B is a Boolean algebra then a generalized necessity is any map n : B → U such that

n(1) = 1 ; n(x ∧ y) = n(x) ∧ n(y)

for every x, y ∈ B (Biacino and Gerla [1992]a). A generalized necessity n such that n(0) = 0 is called a necessity (see Dubois and Prade [1988], Dubois and Prade [1990]). The proof of the following proposition is matter of routine.

Let S be the deduction system of the classical propositional calculus and B the related Lindenbaum algebra. Also, define, for every theory τ in the canonical extension S^{∗}, the map τ̂ : B → U by setting, for every [α] ∈ B, τ̂([α]) = τ(α). Then τ̂ is a generalized necessity. Conversely, let n : B → U be a generalized necessity. Then the fuzzy subset τ of 𝔽 defined by setting τ(α) = n([α]) for every formula α, is a theory of S^{∗}.

Also, we can use the canonical extension S^{∗} of a first order logic to extend some basic notion of programming logic. Indeed, let L be a first order language and denote by B_{L} the related Herbrand base. We call fuzzy Herbrand interpretation for L any fuzzy subset m of B_{L}. The name is justified by the fact that m defines a multivalued interpretation of L in which, as in the classical case, the domain is the Herbrand universe U(L), the constants in L are assigned themselves and any n-ary function symbol f in L is interpreted as the map associating t_{1}, ..., t_{n} with the term f(t_{1}, ..., t_{n}). The only difference with the classical case is that any n-ary predicate symbol p is interpreted by the fuzzy n-ary relation p′ of B_{L} defined by setting

p′(t_{1}, ..., t_{n}) = m(p(t_{1}, ..., t_{n})).

Let P C_{L} denote the set of definite program clauses and define a fuzzy program as any fuzzy subset p : P C_{L} → [0, 1] of P C_{L}. Then it is natural to associate any fuzzy program p with the fuzzy closure operator J_{p} : 𝔉(B_{L}) → 𝔉(B_{L}) defined by setting, for every v ∈ 𝔉(B_{L}) and α ∈B_{L}

J_{p}(v)(α) = D^{∗}(p ∪ v)(α).

We call a fuzzy Herbrand model for p every fixed point of J_{p}. Then, a fuzzy Herbrand model for p is a fuzzy subset m of B_{L} such that D^{∗}(p∪m)(α) = m(α) for every α ∈ B_{L}. J_{p}(v) is the minimal fuzzy Herbrand model containing v and, in particular, we call the least fuzzy Herbrand model m_{p} of p the fuzzy subset J_{p}(∅).

5 Abstract similarity logic.

We can consider reasonings that may be approximate by allowing the antecedent clauses of a rule to match its premises only approximately. An example is an inference like

A. x is a thriller ⇒ x good for me +

B. b is detective story +

C. the predicate ”detective story” is similar to the predicate ”thriller” =

b is good for me.

Notice that while A and B are formulas in the language under consideration, C expresses a metalogical claim about the connection between two predicate constants ”detective story” and ”thriller”. Also, similarity is a fuzzy notion, in general, so the degree at which we can admit the conclusion ”b is good for me” depends on the degree of similarity between ”detective story” and ”thriller” (see Ying [1994]). Such an approach, syntactical in nature, is rather different from the one proposed in Ruspini [1991], semantical in nature. Indeed in the latter the similarity is defined on the set of worlds and not in the set of formulas (see also Dubois, Esteva, Garcia, Godo Prade [1996]). In this section we will give an abstract approach to similarity logic. Recall that, given two sets S and T, a fuzzy relation between S and T is a fuzzy subset R of S × T, i.e., a map R : S × T → U. A fuzzy relation R in a set S is called a similarity if, for every x, y, z ∈ S, we have that

a) R(x, x) = 1 (reflexivity)

b) R(x, y) ≥ R(x, z) ∧ R(z, y) (transitivity)

c) R(x, y) = R(y, x) (symmetry).

Every similarity R defines a fuzzy operator SIM : F(𝔽) → F(𝔽), we call the fuzzy operator associated with R. Such an operator is defined by setting, for any s ∈ F(𝔽) and x ∈ 𝔽,

SIM (s)(x) = Sup{R(x′, x) ∧ s(x′) | x′ ∈ 𝔽}.  (6)

We can interpret SIM (s) as the fuzzy subset of formulas that are similar to some formula in s. Let R be the identity relation, i.e., assume that R(x, y) = 1 if x = y and R(x, y) = 0 otherwise. Then SIM is the identity map. If R is the equivalence relation ≡, then SIM (X) = {x ∈ S | ∃x′ ∈ X, x ≡ x′}.

SIM is a continuous closure operator.

ProofSince R(x, x) = 1, we have that SIM (s)(x) ≤ s(x), and this prove the inclusion property. It is immediate that SIM is order preserving. In order to prove that SIM ( SIM (s))(x) ≤ SIM (s)(x) observe that by the transitivity

SIM (SIM (s))(x) = Sup_{x′∈𝔽}R(x′, x) ∧ SIM (s)(x′)

= Sup_{x′∈𝔽}R(x′, x) ∧ (Sup_{z∈𝔽}R(z, x′) ∧ s(z)) = Sup_{x′∈𝔽}Sup_{z∈𝔽}R(x′, x) ∧ R(z, x′) ∧ s(z)

= Sup_{x′∈𝔽}Sup_{z∈𝔽}R(z, x′)∧R(x′, x)∧s(z) ≤ Sup_{z∈𝔽}R(z, x)∧s(z) = SIM (s)(x). The continuity is immediate.End Proof

We say that a fuzzy subset s is closed with respect to R if s is a fixed point for SIM . The proof of the following proposition is immediate.

A fuzzy subset s is closed with respect to R if and only if

s(x) ≥ s(x′) ∧ R(x′, x)  (7)

for every x, x’ in 𝔽. In particular, since SIM (s) is a fixed point for SIM ,

SIM (s)(x) ≥ SIM (s)(x′) ∧ R(x′, x).  (8)

Let (D, 𝔽) be any fuzzy deduction system. Then we can consider the operator

K = D ∘ SIM .  (9)

Given an initial valuation v, K(v) is the fuzzy subset of formulas that can be deduced by D from formulas that are either in v or are similar to formulas in v. Unfortunately, K is not a closure operator, in general, and this since D ∘ SIM (v) is not closed with respect to the similarity relation. Nevertheless, since it is immediate that K is a continuous almost closure operator, we can define a similarity-based deduction system as the step-by-step system generated by K.

An abstract similarity deduction system is a fuzzy deduction system whose deduction operator D_{R} is the fuzzy closure operator generated by the operator K defined in (9) where D is the deduction operator of a fuzzy deduction system and SIM the closure operator associated with a similarity R.

Since K is continuous, we have that, for every initial valuation v,

D_{R}(v) = ⋃ K^{n}(v).  (10)

In other words, we obtain the fuzzy set of logical consequence of v by an alternate application of the operators D and SIM ,

v ⊆ SIM (v) ⊆ D(SIM (v)) ⊆ SIM (D(SIM (v))) ⊆ … ⟶ D_{R}(v).

The proof of the following theorem is matter of routine.

The theories of the abstract similarity logic are the theories of D that are closed with respect to the similarity relation R. In accordance, given an initial valuation v, D_{R}(v) is the least fuzzy subset of formulas containing v closed both with respect to the similarity relation R and the deduction operator D.

6 Similarity logic associated with a crisp logic.

Let 𝔽 be the set of formulas of a crisp deduction system S = (𝔸, ℝ) and R a similarity on 𝔽. Then we define the relation R̂ : F(𝔽) × 𝔓(𝔽) → U by setting

R̂(v, Y) = Inf_{y∈Y} Sup_{x∈𝔽}R(x, y) ∧ s(x),  (11)

i.e.,

R̂(v, Y) = Inf_{y∈Y} SIM (v)(y).  (12)

The number R̂(v, Y) gives the extent at which each formula of Y is similar to a formula of v.

The fuzzy consequence relation Con : F(𝔽)×𝔽 → U associated with a fuzzy deduction system S = (𝔸, ℝ) and a similarity R is defined by

Con(v, α) = Sup{R̂(v ∪ 𝔸, Y) | Y ⊆ 𝔽, Y ⊢ α}  (13)

where v is an initial valuation, α a formula and ⊢ the deduction relation associated with S.

Obviously, due to the compactness of the relation ⊢, the set Y in (13) can be assumed to be finite. The meaning of Con(v, α) is immediate, it represents the degree at which we can prove α by using formulas that are similar to formulas in v or in 𝔸. Note that if R is the identity relation, then R̂ coincides with the (characteristic function of the) inclusion relation and

Con(v, α) = D^{∗}(v)(α)  (14)

where D^{∗} is the deduction operator of the canonical extension of S. Consequently, Definition 11 extends the notion of canonical extension of a crisp deduction system.

The relation R̂ represents a graded inclusion, in a sense. This suggests to extend the definition of the relation Con my substituting R̂ with any reasonable definition of graded inclusion.

Set, for every initial valuation v,

H(v) = SIM (v ∪ 𝔸).  (15)

We interpret H(v) as the fuzzy subset of formulas that are similar either to a formula of v or to a logical axiom. In Biacino and Gerla [1998] one proves the following theorem.

H is a continuous closure operator such that

Con(v, ) = (D^{∗} ∘ H)(v).  (16)

From (16) it follows that

CON(v, α) = \{ \begin{matrix}1 & if∅ ⊢ α \\ Sup\{H(v)(α_{1}) ∧ ... ∧ H(v)(α_{m}) | α_{1}, ..., α_{m} ⊢ α\} & otherwise. \end{matrix}

(17)

Then CON(v, α) is the multivalued valuation of the (metalogical) claim ”α is a consequence of v provided that α is a tautology or α_{1}, ..., α_{n} exist

able to prove α such that each α_{i} either is similar to a formula of v or to a logical axiom ”.

Such an interpretation is not different from the one leading to formula (5). The only difference is that the equality is interpreted by a similarity and not by the identity.

Ying considers a particular case of similarity logic in which 𝔽 is the set of formulas of the classical propositional whose connectives are ⇒ (implication) and f (a constant to denote false). Also only the natural similarities are considered, i.e., similarities R : 𝔽 × 𝔽 → [0, 1] obtained from a similarity R_{v} : V AR → [0, 1] on the set V AR of propositional variables by

(1) R(x, y) = R_{v}(x, y) for every x, y ∈ V AR;

(2) R(f, x) = R(x, f) = 1 if x = f

(3) R(x ⇒ y, x′ ⇒ y′) = R(x, x′) ∧ R(y, y′),

(4) R(x, y) = 0 otherwise.

Also, the fuzzy consequence relation is defined as a relation between crisp subsets and formulas, i.e.,

Con(X, α) = Sup{R̂(X ∪ T au, Y) | Y ⊢ α}  (18)

where T au is the set of tautologies and ⊢ is the deduction relation in the classical propositional calculus.

Confining ourselves to the similarity relations considered by Ying, we can prove that the composition D^{∗} ∘ H is a closure operator (see Biacino, Gerla, Ying [1997]).

Under Ying’s hypothesis D^{∗} ∘ H is a continuous closure operator. Consequently, Ying’s logic is an abstract similarity logic.

7 Similarity based Prolog.

In programming logic a mismatch either among constants or among names of relations causes a failure of the unification process. Now, it is rather natural to admit a more flexible unification in which the syntactical identity is substituted by a similarity. In Ferrante, Gerla, Sessa [1998] such a possibility is considered and an unification algorithm to compute a relaxed most general unifier is proposed following the lines of Martelli-Montanari algorithm. Since we are interested in Deductive Data-base, the languages under consideration are function-free.

To give an idea of the proposed theory, consider a first order language whose constants are a, a′, b, b′ and whose relational constants are r, r′, s, s′. Then, given the program:

r′(X) : − s(X), t(X, a).

s′(b).

t(b′, a′).

we can consider the goal r(Z). It is immediate that no (classical) unification is possible and therefore that no answer exists. Nevertheless, assume that r similar to r′. Then, we can consider the equation r(Z) = r′(X) and to obtain the substitution Z → X. Moreover, given the equation s(X) = s′(b), we can go on by obtaining the substitution θ = {Z → X, X → b} provided that s is similar to s′. By substituting and by considering the equation t(b, a) = t(b′, a′), we can conclude in a positive way the resolution process provided that b is similar to b′ and a is similar to a′. In other words, θ is a correct answer provided that the conditions

r = r′, s = s′, b = b′, a = a′

are (approximately) satisfied. If we assume that the different degree of similarity are represented by the fuzzy relation R, the conjunction of these formulas is satisfied at degree R(r, r′)∧R(s, s′)∧R(b, b′)∧R(a, a′) and therefore θ is correct to such a degree. A further consideration is suggested by the fact that the equality b = b′ was admitted. Indeed, since no reason we have to distinguish b and b′, it is more correct to consider the answer θ = {Z → X, X → {b, b′}}. This means that in our approach the substitutions can associate to the variables clouds of constants. The intended meaning is that the constants in a cloud are pairwise similar and therefore we cannot distinguish them. Finally, in accordance with the required flexibility,

- any set S of equations can be unified at a suitable degree (different from 1, in general)

- any substitution is an unifier at a suitable degree (different from 1, in general).

8 Sequent calculus and graded consequence relations.

As it is well know, the calculi of sequents can be understood as a meta-calculi for the deducibility relation. Then, in accordance with the point of view assumed in this chapter, we will consider a fuzzyfication of such a calculi. We start from a ”minimal” sequent calculus corresponding to the notion of crisp abstract logic. Let 𝔓_{f}(𝔽) denote the class of finite subsets of formulas. Then we call sequent any pair (X, α) ∈ 𝔓_{f}(𝔽)×𝔽 and we denote by SEQ the class of sequents. Also, we consider the crisp deduction system S = (𝔸, ℝ) such that

- the set of formulas is SEQ

- the set 𝔸 of logical axioms is {({x}, x) | x ∈ 𝔽}

- ℝ contains the rules

(i) \frac{(X, α)}{(X ∪ Y, α)} ; (ii) \frac{(X, β), (X ∪ \{β\}, α)}{(X, α)}.

We call sequent-system such a system. Obviously, a set T of sequents is a theory in such a system iff

(j) ({α}, α) ∈ T for every α ∈ 𝔽,

(jj) (X, α) ∈ T , Y ⊇ X ⇒ (Y, α) ∈ T

(jjj) (X, y_{1}) ∈ T, ..., (X, y_{n}) ∈ T, (X ∪ {y_{1}, ..., y_{n}}, α) ∈ T ⇒ (X, α) ∈ T. The following proposition shows that there is an one-one correspondence

between the theories in the sequent-system and the compact closure operators, i.e., the crisp abstract logics.

Let T be a theory of the sequent deduction system and set, for every subset X of 𝔽

H(X) = {x ∈ 𝔽 | thereexistsY ⊆ X suchthat(Y, x) ∈ T }.

Then H is a compact closure operator. Conversely, let H be a compact closure operator and set

T = {(X, x) ∈ SEQ | x ∈ H(X)}.

Then T is a theory in the sequent-system.

ProofLe T be a theory of the sequent-system. Then it is immediate that H satisfies the inclusion property and the monotony. To prove the idempotence, observe that if x ∈ H(H(X)) then there exists Y ⊆ H(X) such that (Y, x) ∈ T. Assume that Y = {y_{1}, ..., y_{n}} and let Y_{1}, ..., Y_{n} finite subsets of X such that (Y_{i}, y_{i}) ∈ T. Then, Y′ = Y_{1}∪...∪Y_{n}, is a finite subset of X such that (Y′, y_{i}) ∈ T for every index i = 1, ..., n. Since (Y, x) ∈ T entails (Y′ ∪ {y_{1}, ..., y_{n}}, x) ∈ T , by (jjj) we can conclude that (Y′, x) ∈ T. This proves that x ∈ H(X) and therefore that H(H(X)) ⊆ H(X).

Conversely, let H be a compact closure operator, then it is immediate that T contains the set of logical axioms and is closed with respect to the rule (ii). Assume that (X, β) ∈ T and (X ∪ {β}, α) ∈ T ,i.e.,. β ∈ H(X) and α ∈ H(X ∪ {β}). Then, since from H(X) ⊇ X ∪ {β} it follows that H(X) = H(H(X)) ⊇ H(X ∪ {β}), we have that α ∈ H(X) and therefore (X, α) ∈ T.

End Proof

We are interested to the canonical extension S^{∗} of S that we consider as a fuzzy metalogic for the crisp deduction systems. We call fuzzy sequent-system such an extension. By definition, the fuzzy sequent-system, is characterized by the set 𝔸 = {({x}, x) | x ∈ 𝔽} of logical axioms and the fuzzy inference rules

(i^{∗}) \frac{(X, α)}{(X ∪ Y, α)} ^{,} \frac{λ}{λ} ; (ii^{∗}) \frac{(X, β) , (X ∪ \{β\}, α)}{(X, α)} ^{,} \frac{λ , μ}{λ ∧ μ}.

The following proposition is immediate.

A fuzzy set τ : SEQ → U of sequents is a theory of the fuzzy sequent-system iff satisfies

(j^{∗}) τ(X, α) = 1 for every α ∈ X

(jj^{∗}) τ(X ∪ Y, α) ≥ τ(X, α)

(jjj^{∗}) τ(X, α) ≥ τ(X, β) ∧ v(X ∪ {β}, α).

Now we will relate the fuzzy sequent-system with the interesting notion of graded consequence proposed in Chakraborty [1988]. Such a notion consists in a fuzzyfied version of the metalogic deduction relation ⊢ .

A fuzzy relation g : 𝔓(𝔽)×𝔽 → 𝕌 is called a graded consequence if, for every X, Y, Z ∈ 𝔓(𝔽) and α ∈ 𝔽

(j) g(X, α) = 1 for every α ∈ X

(jj) X ⊇ Y ⇒ g(X, α) ≥ g(Y, α)

(jjj) g(X, α) ≥ (Inf{g(X, z) | z ∈ Z} ∧ g(X ∪ Z, α). Moreover, g is compact if (jv) g(X, α) = Sup{g(X_{f}, α) | X_{f} ∈ 𝔓_{f}(X)}. It is easy to prove that Ying’s similarity logic defines a compact graded

consequence. For the compact fuzzy relations condition (jjj) can be weakened as follows.

A fuzzy relation g is a compact graded consequence iff satisfies (j), (jj), (jv) and

(jjj^{∗}) g(X, α) ≥ g(X, z) ∧ g(X ∪ {z}, α).

ProofAssume that (j), (jj), (jv) and (jjj^{∗}) are satisfied. Then, at first we will prove, by induction on n, that (jjj) holds for every finite set Z_{f}. Indeed, assume that Z_{f} = {z_{1}, ..., z_{n}}. Then, for n = 1, (jjj) coincides with (jjj^{∗}). Moreover, by induction hypothesis, (jjj^{∗}) and by (jj),

g(X, α) ≥ (Inf{g(X, z_{i}) | i = 1, ..., n − 1}) ∧ g(X ∪ {z_{1}, ..., z_{n−1}}, α)
≥ (Inf{g(X, z_{i}) | i = 1, ..., n − 1}) ∧ g(X ∪ {z_{1}, ..., z_{n−1}}, z_{n}) ∧ g(X ∪ {z_{1}, ..., z_{n}}, α))
≥ (Inf{g(X, z_{i}) | i = 1, ..., n − 1}) ∧ g(X, z_{n}) ∧ g(X ∪ Z_{f}, α))
= (Inf{g(X, z) | z ∈ Z_{f}}) ∧ g(X ∪ Z_{f}, α)).

Let Z be any set, then, by (jv)

(Inf{g(X, z) | z ∈ Z}) ∧ g(X ∪ Z, α)
= (Inf{g(X, z) | z ∈ Z}) ∧ (Sup{g(X ∪ Z_{f}, α) | Z_{f} ∈ 𝔓_{f}(Z)})
= Sup{(Inf{g(X, z) | z ∈ Z}) ∧ g(X ∪ Z_{f}, α) | Z_{f} ∈ 𝔓_{f}(Z)})
≤ Sup{(Inf{g(X, z) | z ∈ Z_{f}}) ∧ g(X ∪ Z_{f}, α) | Z_{f} ∈ 𝔓_{f}(Z)})
≤ g(X, α).EndP roof

If h is a fuzzy subset of 𝔓_{f}(𝔽) × 𝔽 and we set

g(X, α) = Sup{h(X_{f}, α) | X_{f} is a finite subsetof X},  (19)

then it is immediate that g is a compact fuzzy relation. In this case we say that g is the compact extension of h. The proof of the following proposition is immediate.

A fuzzy relation g is a compact graded consequence iff is the compact extension of a theory of the fuzzy sequent-calculus.

References

- Biacino L. [1991], Generated envelopes, J. Math. Anal. Appl., 172, 179-90.

- Biacino L., Gerla G. [1984], Closure systems and L-subalgebras, Inform. Sci., 32 , 181-195.

- Biacino, L., Gerla, G. [1989], Decidability, recursive enumerability and Kleene hierarchy for L-subsets, Z. Math. Logik Grundlag. Math., 35, 49-62.

- Biacino L., Gerla G. [1992]a, Generated necessities and possibilities, International Journal of Intelligent Systems, 7, 445-454.

- Biacino L., Gerla G. [1992]b, Fuzzy subsets: A constructive approach, Fuzzy Sets and Systems 45, 161-168.

- Biacino L, Gerla G. [1993], Closure operators for fuzzy subsets, EUFIT ’93, First European Congress on Fuzzy and Intelligent Technologies, Aachen, 1441-447.

- Biacino L., Gerla G. [1996], An extension principle for closure operators, J. of Math. Anal. Appl. 74, 432-440.

- Biacino L., Gerla G. [1998], Logics with approximate premises, Int. Journal of Intelligent Systems, 13, 1-10.

- Biacino L., Gerla G., Ying M. [1998], Approximate reasoning based on similarity: Propositional calculi, unpublished paper.

- Chakraborty M.K. [1988], Use of fuzzy set theory in introducing graded consequence in multiple valued logic, in Fuzzy Logic in Knowledge-Based Systems, Decision and Control, M.M. Gupta and T.Yamakawa (eds), North-Holland, Amsterdam, 247-257.

- Chakraborty M.K. [1998], Graded consequence: further studies, to appear in Journal of Applied non-classical Logic.

- Dubois D., Lang J., Prade H. [1994], Possibilistic logic, In: D.Gabbay, C.Hogger and J.Robinson (eds.) Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3. Clarendon Press.

- Dubois D., Prade H. [1988], Possibility Theory, Plenum Press, New York and London.

- Dubois D., Prade H. [1990], Resolution principles in possibilistic logic, Inter. J. of Approximate Reasoning, 4, 1-21.

- Hajek P. [1993], On logics of approximate reasoning, Neural Network Word 6/1993, 733-744.

– Formato F., Gerla G., Sessa M. [1998], Similarity-based Unification, unpublished paper.

- Gerla G. [1994]a, An extension principle for fuzzy logic, Math. Log. Quart., 40, 357-380.

- Gerla, G. [1994]b, Inferences in probability logic, Artificial Intelligence, 70, 33-52.

- Gerla G. [1997], Graded consequence relations and closure operators, Journal of Applied non-classical Logic, 6, 369-379.

- Gerla G. [1998]a, Closure operators, fuzzy logic and constraints, to appear in Dubois and Prade (eds), Fuzzy Sets, Logics, and Knowledge-Based Reasoning (1996 Linz seminar), Kluwer.

- Gerla G. [1998]b, Multivalued logic as a logic of constraints, unpublished paper.

- Novak V. [1987], First-Order fuzzy logic, Studia Logica, 46, 87-109.

- Pavelka J. [1979]a, On fuzzy logic I: Many valued rules of inference, Zeitschr. f. Math.Logik und Grundlagen Math., 25, 45-52.

- Pavelka J. [1979]b, On fuzzy logic II: Enriched residuated lattices and semantics of propositional calculi, Z. Math. Logik Grundlag. Math., 25, 119-134.

- Pavelka J. [1979]c, On fuzzy logic III: Semantical completeness of some many-valued propositional calculi, Z. Math. Logik Grundlag. Math., 25, 447-464.

- Ramik J.[1983], Extension principle and fuzzy-mathematical programming, Kybernetika, 19, 513-25.

- Ramik J. [1986], Extension principle in fuzzy optimization, Fuzzy Sets and Systems, 19, 29-35.

- Ruspini E. [1991], On the semantics of fuzzy logic, Int. J. of Approximate Reasoning, 5, 45-88.

- Zadeh, L.A. [1975], Fuzzy logic and approximate reasoning, Synthese, 30, 407-428.

- M. Ying [1994], A logic for approximate reasoning, The Journal of Symbolic Logic, 59, 830-837.