A Fuzzy Logic Based Resolution Principal for Approximate Reasoning ()
1. Introduction
This study is a continuation of a research, which is based on a proposed t-norm fuzzy logic, presented in [1] . Here we also use an automated theorem proving, where a resolution principal is a rule of an inference, leading to a refutation theorem-proving technique. Applying the resolution rule in a suitable way, it is possible to check whether a propositional formula is Universally Valid (UV) and construct a proof of a fact that relative consequent’s first-order formula is UV or non UV. In 1965, J. A. Robinson [2] introduced the resolution principle for first-order logic. A fuzzy resolution principal, in its part, was introduced by M. Mukaidono [3] .
Taking into account the above mentioned, we present the following.
Definition 1 [3] .
A fuzzy resolvent of two fuzzy clauses
and
, containing the complementary literals
and
respectively, is defined as
(1.1)
where
and
.
,
are fuzzy clauses, which don’t contain
and
respectively. The operator
is understood as the disjunction of the literals present in them. It is also a logical consequence of
. A resolution deduction of a clause
from a set
of clauses is a finite sequence of clauses
such that each
is either a member of or is a resolvent of two clauses taken from the resolution principle in propositional logic we deduce that, if
is true under some truth valuation
, then
for all
, and in particular,
[2] .
Example 1: Here is a derivation of a clause from a set of clauses presented by means of a resolution Tree in Figure 1.
In first order logic, resolution condenses the traditional syllogism of logical inference down to single rule.
A simple resolution scheme is:
Antecedent 1:
Antecedent 2:
(1.2)
Consequent:
The entire historical analysis of this approach toward applying of a resolution principal to a logical inference is presented in [4] .
2. Basic Theoretical Aspects
First, Let us consider that A, A', B and B' are fuzzy concepts represented by fuzzy sets in universe of discourse U, U, V and V, respectively and correspondent fuzzy sets be represented as such
,
, where
(2.1)
Given (2.1) let us formulate the argument form of simple Fuzzy Resolution as follows.
---------- (2.2)
Given (2.2) the scheme for Generalized Fuzzy Resolution looks like that
Antecedent 1: If x is A OR y is B Antecedent 2: y is B'
---------------------------------- (2.3)
Consequent: x is A'.
In case (2.3), we can say that the Disjunctive Syllogism holds if B' is close to not B, whereas A' is close to A. The second approach is called Inverse Approximate Reasoning. Its scheme looks like that:
Antecedent 1: If x is A, then y is B Antecedent 2: y is B'
---------------------------------- (2.4)
Consequent: x is A'.
We shall transform the disjunction form of rule into fuzzy implication from fuzzy logic, introduced in [1] , or fuzzy relation and apply the method of inverse approximate reasoning to get the required resolvent. However, in the case of complex set of clauses the method is not suitable. Hence, we investigate for another method of approximate reasoning based on similarity to get the fuzzy resolvent.
Let us consider Generalized Fuzzy Resolution first. The key operation used in this method is disjunction. The disjunction operation
is presented in Table S1 and, being applied to above introduced fuzzy sets A and B, looks like that [1]
(2.5)
Whereas correspondent conjunction operation
is also presented in Table S1 and looks like that [1]
(2.6)
Taking into account (2.5) and (2.6) and the fact that
, let us formulate the following
Lemma 1.
If there are two fuzzy clauses
and
is a fuzzy resolvent of them with keyword
, then the following inequality holds
(2.7)
where T(x) is a truth value of an x.
Proof: Since
and
, where
, then
(2.8)
whereas from (1.1)
. From (2.8) let define the following values of truth:
(2.9)
Since
, then from (2.9) we are getting that
(2.10)
In a meantime from the same (2.8) we have
(2.11)
From (2.11) let’s take a note that
(2.12)
Also from (2.11) let
(2.13)
Continuing from (2.11) let
(2.14)
And finally from (1.1) we have
(2.15)
Let’s rewrite (2.8) in the following way
(2.16)
From (2.16) given both (2.10) and (2.12) we have
(2.17)
Taking into account (2.12) finally we are getting
(2.18)
Furthermore from the same (2.16) let
(2.19)
Note that from (2.18)
, which means that from (2.13)
, therefore from (2.19) we have
(2.20)
But from (2.14) and (2.20)
, when
or equally
(2.21)
Finally from (2.16), given (2.18) and (2.20), we are getting the following
(2.22)
Taking into account (2.21) from (2.15) and (1.1)
(2.23)
From (2.22) and (2.23) we are getting
(Q. E. D.).
Corollary 1
Let
are two fuzzy clauses. If
, then the following is true:
(2.24)
Proof: First note that for
(2.25)
From (1.1) and (2.15), given (2.25) we are getting the following
(2.26)
First from (2.14) we have the following
(2.27)
But from (2.13) we have the following
, but
, therefore
, in other words the following is true.
(Q. E. D.).
Corollary 2
Let
are two fuzzy clauses. If
, then the following is true:
(2.28)
Proof:
From (2.22) we have
, which means that
. From (2.14), (2.17) and (2.19) we are getting
, but from (2.26)
, which means that
(Q. E. D.).
Based on above presented results let formulate the following
Theorem 1 (Deduction):
Let
and
are fuzzy concepts. A fuzzy concept
is a logical consequent of
if and only if the following inequality holds
. (2.29)
Or equally
(2.30)
Which means a fuzzy formula (2.30) is UV. Note, that a fuzzy formula
is called UV, if
. Before providing a proof of this theorem let us give the following
Definition 2
A fuzzy concept
is a logical consequent of
, i.e.
, if and only when UV of
has caused UV of a fuzzy concept
, in other words the following is true.
, where
Proof: Let fuzzy concept
is a logical consequent of fuzzy concepts
.
If fuzzy concepts
are UV, i.e.
, then in accordance with Definition 2 a fuzzy concept
is also UV, i.e.
. An implication operator in a fuzzy logic, used in this article is defined as the following (see Table S1 and Table S2)
(2.31)
Let us consider a set of cases.
・ If
, then
, therefore UV of a fuzzy formula (2.30) is apparent.
・ If
, then
, but since
and
, then
and
. Therefore it is obvious then
, i.e. a fuzzy formula (2.30) is not UV, a logical contradiction takes place.
・ If
, then
a fuzzy sub formula (antecedent) from (2.30)
is not UV, i.e. contradictive, but in a meantime
, therefore
, i.e. a fuzzy formula (2.30) is UV.
・ If
(2.32)
and if
, therefore formula (2.30) is UV, whereas if
, then again
and given conditions (2.32) we have
, which means that a fuzzy formula (2.30) is not UV or is contradictive.
At last let a fuzzy formula (2.30) be UV and also let
. Then if a fuzzy sub formula (antecedent) from (2.30)
is also UV, i.e.
, then from (2.31) we have
. In other words a fuzzy concept
is UV. Therefore from Definition 2 a fuzzy concept
is a logical consequent of fuzzy concepts
(Q. E. D.).
Based on these results we formulate the following
Theorem 2
If there are two fuzzy clauses
and
is a fuzzy resolvent of them with keyword
, then
is logical consequent of both
and
i.e.
(2.33)
Proof:
Let
and
, where
, whereas
. By Definition 1 and in accordance with (2.5)
(2.34)
(2.35)
(2.36)
Let
are both UV, i.e.
and
. Since from (2.35) and (2.36) the following is taking place
and
then UV of
is in reality means that
(2.37)
Taking into account that
let sum both inequalities (2.37) together and get the following
. From (2.34)
i.e.
is UV. Therefore by Definition 2 we are getting a fact that if
are both UV, and then
is also UV. (Q. E. D.).
Let us present some considerations about using a notion of similarity, which plays a fundamental role in theories of knowledge and behavior and has been dealt with extensively in psychology and philosophy. A careful analysis of the different similarity measures reveals that it is impossible to single out one particular similarity measure that works well for all purposes. We will utilize a consistent approach toward definition of a similarity measure, based on the same fuzzy logic we used above [1] . But this time we will use the operation Equivalence (see Table S1).
Suppose
be an arbitrary finite set, and
be the collection of all fuzzy subsets of
. For
, a similarity index between the pair
is denoted as
or simply
which can also be considered as a function
. In order to provide a definition for similarity index, a number of factors must be considered.
Definition 3
A function
defines a similarity between fuzzy concepts
if it satisfies the following axioms:
P1.
, where
,
P2.
,
P3.
,
P4. For two fuzzy concepts
,
, i.e.
,
P5.
.
Lemma 2
If a function
is defined as operation equivalence from Table S1, then it could be considered as a similarity measure.
Proof:
From Table S1 we have
(2.38)
P1. From (2.38)
(2.39)
whereas
(2.40)
Axioms P2 and P3 are trivially satisfied by (2.38).
P4. From (2.38)
(2.41)
P5. From (2.38)
(2.42)
Case:
From (2.38) and (2.42) we have
(2.43)
From (2.43)
, whereas
. Since
and
, then the following is also true:
(2.44)
Case:
From (2.38) and (2.42) we have
(2.45)
From (2.45)
, whereas
. Since
and
, then the following is also true:
(Q. E. D.).
To illustrate our further research before giving the definition of similarity index, we will present couple examples.
Let
and
be two normal fuzzy sets defined over the same universe of discourse
and presented by unimodal linear monotonic membership functions and
;
. Correspondent linguistic scale could consist of the terms like {“SMALL”…, “MEDIUM”…, “LARGE”}. Let us consider the following cases.
1)
labeled “SMALLER THAN LARGE”
Whereas
labeled “LARGE”
From (2.38) the similarity matrix
would look like that
2)
labeled “MEDIUM”
And
labeled “LARGE”
From (2.38) the similarity matrix
would look like that (for simplicity sake we show elements of a matrix with singles only)
3)
labeled “MEDIUM”
And
labeled “SMALL”
From (2.38) the similarity matrix
would look like that
4)
labeled “LARGE”
And
labeled “SMALL”
From (2.38) the similarity matrix
would look like that
5)
labeled “MEDIUM”
And
labeled “MEDIUM”
From (2.38) the similarity matrix
would look like that
Let consider similarity measure as a matrix
. We are presenting the following
Proposition 1
Since
and
are two normal fuzzy sets, then
. Then the following function could be considered as a similarity index
(2.46)
In Table 1 there are three sets of pairs of indices
.
1) For
2) For
3) For
.
From (2.46) we are getting
. This value perfectly matches our intuition and perception of a closeness of terms “SMALLER THAN LARGE” and “LARGE” and membership functions of correspondent fuzzy sets.
In Table 2 there are six sets of pairs of indices
1) For
2) For
3) For
4) For
5) For
6) For
Table 1. “Smaller Than Large”
“Large”.
From (2.46)
. This value is in a middle of a scale [0, 1] and also perfectly matches our intuition and perception of an average closeness of terms “LARGE” and “MEDIUM” and membership functions of correspondent fuzzy sets.
Similarly in Table 3 there are six sets of pairs of indices
.
1) For
2) For
3) For
4) For
5) For
6) For
.
From (2.46) we are getting
. This value is also in a middle of a scale
and also perfectly matches our intuition and perception of an average closeness of terms “SMALL” and “MEDIUM” and membership functions of correspondent fuzzy sets.
In Table 4 there are eleven sets of pairs of indices
1) For
2)
3)
4)
5)
6)
7) For
8) For
9) For
10) For
11) For
.
From (2.46) we are getting
. This value also perfectly matches our intuition and perception of a fact that terms “SMALL” and “LARGE” has nothing in common.
In Table 5 there are twelve sets of pairs of indices
1) For
2)
3)
4)
5)
6)
7) For
8) For
9) For
10) For
11) For
.
12) For
.
From (2.46) we are getting
. This value is a confirmation of a fact that both fuzzy sets are identical.
3. Generalized Fuzzy Resolution Based Approximate Reasoning
Let us remind that the scheme for Generalized Fuzzy Resolution (2.3) looks like that
Antecedent1: If x is A OR y is B Antecedent2: y is B’
---------------------------------- (3.1)
Consequent: x is A’.
First consider the following classical logic equivalence
(3.2)
The classical logic equivalence (3.2) can be extended in fuzzy logic with implication and negation functions. We use the same fuzzy logic, which operations are presented in Table S1. Let us first proof that (3.2) holds.
Since
(3.3)
And because
therefore
(3.4)
Both (3.3) and (3.4) proofs that classical logic equivalence (3.2) holds. It is very important to show that we transform Generalized Fuzzy Resolution rule (3.1) into its equivalent form
Antecedent1: If y is ØB then x is A Antecedent2: y is B'
---------------------------------- (3.5)
Consequent: x is A'.
Let us formulize an inference method for a rule (3.5). Following a well-known pattern, established a couple of decades ago and the standard approaches toward such formalization, presented and extensively used in [5] [6] [7] [8] [9] , let
and
be two universes of discourses and correspondent fuzzy sets be represented as such
,
, where
(3.6)
Whereas given (3.6) a binary relationship for the fuzzy conditional proposition of the type: “If y is
then x is A” for a fuzzy logic is defined as
(3.7)
Given an implication operator from Table S1 expression (3.7) looks like
(3.8)
It is well known that given a unary relationship
one can obtain the consequence
by applying compositional rule of inference (CRI) to
and
of type (3.7):
(3.9)
In order that Criterion I (see Appendix) is satisfied, that is
from (3.9) the equality
(3.10)
must be satisfied for arbitrary
and in order that the equality (3.10) is satisfied, it is necessary that the inequality
(3.11)
holds for arbitrary
and
. Let us define new methods of fuzzy conditional inference of the type (3.5), which requires the satisfaction of Criteria I-IV from Appendix.
Theorem 3
If fuzzy sets
,
are defined as (3.6) and
is defined by (3.7), where
(3.12)
then Criteria I, II, III and IV-1 are satisfied.
Proof:
For Criteria I-III let
then
(3.13)
(3.14)
From (3.13) and given subsets from (3.14) we have
. (3.15)
Let us introduce the following function (as a part of implication operation)
. (3.16)
Then the following is taking place:
(3.17)
Since from (3.16)
, but
, therefore from (3.17) we have
(3.18)
(3.19)
From (3.16)-(3.19) we have
. (Q. E. D.).
For Criteria IV-2 let
then
(3.20)
From (3.20) and given subsets from (3.14) we have
(Q. E. D.) (3.21)
To illustrate these results we will present couple examples.
Example 1
Let
and
be two universes of discourses and correspondent fuzzy sets are represented as in (3.6)
,
; related linguistic scale could consist of the terms like {“SMALL”…, “MEDIUM”…, “LARGE”}. Let us consider the following cases.
labeled “LARGE”
And
labeled “SMALL”
The negation of a fuzzy set
would look like
The binary relationship matrix
of a type (3.7) would look like
Let
labeled “very SMALL”
Applying (3.13)
Example 2
labeled “LARGE”
And
also labeled “LARGE”
The negation of a fuzzy set
would look like
The binary relationship matrix
of a type (3.7) would look like
Applying (3.13)
Let us revisit the fuzzy conditional inference rule (3.5). It will be shown that when the membership function of the observation
is continuous, then the conclusion
depends continuously on the observation; and when the membership function of the relation
is continuous then the observation
has a continuous membership function. We start with some definitions. A fuzzy set
with membership function
, is called a fuzzy number if
is normal, continuous, and convex. The fuzzy numbers represent the continuous possibility distributions of fuzzy terms of the following type
Let
be a fuzzy number, then for any
we define
the modulus of continuity of
by
. (3.22)
An α-level set of a fuzzy interval
is a non-fuzzy set denoted by
and is defined by
for
and
for
. Here we use a metric of the following type
, (3.23)
where
denotes the classical Hausdorff metric expressed in the family of compact subsets of
, i.e.
.
whereas
,
when the fuzzy sets
and
both have finite support
then their Hamming distance is defined as
.
In the sequel we will use the following lemma.
Lemma 3 [10]
Let
be a real number and let
,
be fuzzy intervals. If
, then
.
Consider the fuzzy conditional inference rule (3.5) with different observations
and
:
Antecedent 1: If y is ØB then x is A Antecedent 2: y is B
----------------------------------
Consequent: x is ØA
Antecedent 1: If y is ØB then x is A Antecedent 2: y is B1
----------------------------------
Consequent: x is ØA1
According to the fuzzy conditional inference rule (3.5), the membership functions of the conclusions are computed as
;
Or
;
, (3.24)
The following theorem shows the fact that when the observations are closed to each other in the metric
of (3.23) type, then there can be only a small deviation in the membership functions of the conclusions.
Theorem 4 (Stability theorem)
Let
and let
,
be fuzzy intervals and an implication operation in the fuzzy conditional inference rule (3.5) is from Table S1. If
then
Proof:
Given an implication operation in the fuzzy conditional inference rule (3.5) is from Table S1, for the observation
we have
(3.25)
From (3.13) and given subsets from (3.14) we have
. (3.26)
Then from (3.16) the following is taking place:
(3.27)
Since from (3.16)
, but
, therefore from (3.17) we have
(3.28)
(3.29)
From (3.27)-(3.29) we have
From (3.28) and (3.29), we see that the difference of the values of conclusions for both
and
observations for arbitrary fixed
is defined as follows
Therefore from Lemma 1 we have
(Q. E. D.)
Theorem 5 (Continuity theorem)
Let binary relationship
be continuous. Then
is continuous and
for each
.
Proof:
Let
be a real number and let
such that
. From (3.22) we have
. Then
(Q. E. D.).
Results from Theorem 4 and Theorem 5 could be used for formulating another similarity measure, based on Hamming distance between two fuzzy sets
Figure 2. Terms “very” and “more or less”.
and
, which presented by non-linear membership functions, i.e.
(3.30)
For instance let us apply (3.29) to fuzzy sets from Example 1 (see Figure 2):
Let
labeled “SMALL”
And
labeled “very SMALL”
. It is important to pay attention to a fact that
from the same Example 1, which confirms results of both Theorem 4 and Theorem 5.
4. Generalized Modus Tollens Based Inverse Approximate Reasoning
Let us remind that the scheme for Generalized Modus Tollens (2.3) looks like that
Antecedent 1: If x is A, then y is B Antecedent 2: y is B1
---------------------------------- (4.1)
Consequent: x is A1.
First consider classical logic equivalence
(4.2)
The classical logic equivalence (4.2) can be extended in fuzzy logic with implication and negation functions. We use the same fuzzy logic, which operations are presented in Table S1. Let us first proof that (4.2) holds.
Since
(4.3)
And because
(4.4)
Both (4.3) and (4.4) proofs that classical logic equivalence (4.2) holds. It is very important to show that we transform Generalized Modus Tollens rule (4.1) into its equivalent form
Antecedent1: If y is ØB then x is ØA Antecedent2: y is B1
---------------------------------- (4.5)
Consequent: x is A1.
Let us formulize an inference method for a rule (4.5). Following a standard approaches toward such formalization, let
and
be two universes of discourses and correspondent fuzzy sets be represented as such
,
.
Whereas given (3.6) a binary relationship for the fuzzy conditional proposition of the type: “If y is ØB then x is ØA” for a fuzzy logic is defined as
(4.6)
Given an implication operator from Table S1 expression (4.6) looks like
And again given a unary relationship
one can obtain the consequence
by applying compositional rule of inference (CRI) to
and
of type (4.6):
(4.7)
In order that Criterion V (see Appendix) is satisfied, that is
from (3.9) the equality
(4.8)
must be satisfied for arbitrary
and in order that the equality (3.10) is satisfied, it is necessary that the inequality
(4.9)
holds for arbitrary
and
. Let us define new methods of fuzzy conditional inference of the type (4.6), which requires the satisfaction of Criteria V-VIII from Appendix.
Theorem 6
If fuzzy sets
,
are defined as (3.6) and
is defined by (4.6), where
(4.10)
then Criteria V,VI,VII and VIII-2 are satisfied.
Proof:
For Criteria V-VII let
then
(4.11)
(4.12)
From (4.11) and given subsets from (4.12) we have
. (4.13)
Let us introduce the following function (as a part of implication operation)
. (4.14)
Then the following is taking place:
(4.15)
(4.16)
From (4.15), (4.16) we have
. (Q. E. D.).
For Criteria VIII-2 let
then
(4.17)
From (4.17) and given subsets from (4.15) and (4.16) we have
. Since the following is taking place
.
Therefore
. (Q. E. D.)
To illustrate these results we will present couple examples. We use similar fuzzy sets as in Examples 1 and 2.
Example 3
Let
and
be two universes of discourses and correspondent fuzzy sets are represented as in (3.6)
,
; related linguistic scale could consist of the terms like {“SMALL”…, “MEDIUM”…, “LARGE”}. Let us consider the following cases.
labeled “LARGE”
And
labeled “SMALL”
The negations of fuzzy sets
would look like
The binary relationship matrix
of a type (4.6) would look like
Let
labeled “very SMALL”
Applying (4.7)
(“very LARGE”).
Example 4
labeled “LARGE”
And
also labeled “LARGE”
The negations of fuzzy sets
would look like
The binary relationship matrix
of a type (4.6) would look like
Applying (4.7)
5. Concluding Remarks
In this article, we presented a systemic approach toward a fuzzy logic based formalization of an approximate reasoning methodology in a fuzzy resolution. We derived a truth value of A from both values of B → A and B by some mechanism. We used a t-norm fuzzy logic, in which an implication operator is a root of both graduated conjunction and disjunction operators. We investigated features of correspondent fuzzy resolvent, which was based on introduced operators. We proposed two types of Similarity Measures for both linear and non-linear membership functions. We applied this approach to both generalized modus-ponens/modus-tollens syllogisms, for which we formulated a set of Criterion. The content of this investigation is well-illustrated with artificial examples.
Appendix
Table S2. A Fuzzy Logic Implication Operation.
Criterion I
Antecedent 1: If y is ØB then x is A Antecedent 2: y is B
----------------------------------
Consequent: x is ØA.
Criterion II
Antecedent 1: If y is ØB then x is A Antecedent 2: y is very B
----------------------------------
Consequent: x is Ø(very A).
Criterion III
Antecedent 1: If y is ØB then x is A Antecedent 2: y is more or less B
----------------------------------
Consequent: x is Ø(more or less A).
Criterion IV-1
Antecedent 1: If y is ØB then x is A Antecedent 2: y is ØB
----------------------------------
Consequent: x is unknown
Criterion IV-2
Antecedent 1: If y is ØB then x is A Antecedent 2: y is ØB
----------------------------------
Consequent: x is A.
Criterion V
Antecedent 1: If y is ØB then x is ØA Antecedent 2: y is B
----------------------------------
Consequent: x is A.
Criterion VI
Antecedent 1: If y is ØB then x is ØA Antecedent 2: y is very B
----------------------------------
Consequent: x is very A
Criterion VII
Antecedent 1: If y is ØB then x is ØA Antecedent 2: y is more or less B
----------------------------------
Consequent: x is more or less A
Criterion VIII-1
Antecedent 1: If y is ØB then x is ØA Antecedent 2: y is ØB
----------------------------------
Consequent: x is unknown
Criterion VIII-2
Antecedent 1: If y is ØB then x is ØA Antecedent 2: y is ØB
----------------------------------
Consequent: x is ØA.