# Validity degrees anyone? [long]

From: Stephan Lehmke (Stephan.Lehmke@cs.uni-dortmund.de)
Date: Sat Mar 31 2001 - 14:47:08 MET DST

• Next message: Umesh Harigopal: "CFP: IEEE SMC Conf Session on Knowledge Management"

Dear colleagues,

in my PhD thesis I'm using the concept of "validity degree" which
seems to be strange or even outright revolting to logicians ;-)

Let me try to explain:

Classically, in many-valued logics, validity is two-valued. The model
relation is usually defined using a set of designated truth values,
calling an interpretation a model of a formula iff the truth value of
the formula under the interpretation falls into the set of designated
truth values.

Obviously, for a non-graded model relation, validity is two-valued: a
formula is said to be valid iff all interpretations are models for it.

It can be argued that for knowledge modelling purposes, a yes-or-no
definition of validity is less than satisfying. Truth values are not
really looked at in mathematical logic, but quantified over when
defining validity, semantic consequence or semantic
equivalence. Without a graded model relation, all other logical
concepts stay a little too `crisp' for the resulting logic to be
called `fuzzy'.

As soon as the model relation becomes graded, however, the validity of
a formula naturally becomes graded too: It is the infimum(*) of the
`modelness degrees' of all interpretations for this formula.

How to define a graded model relation?

Some approaches known from the literature:

----------------------------------------------------------------------
a) [does this approach have a name to it?]
In a many-valued logic, just define the `degree of modelness' to be
the truth value of a formula under the given interpretation.

This approach is problematic in two ways.
First, it doesn't really allow to distinguish between truth values and
validity degrees, so it can't be used for analysing the relationship
between these concepts.
Secondly, it doesn't lead to a logic of very high expressive
power. I'm not aware of a lot of literature where this approach is
used (though I'd be interested to hear of others), one of the earlier
references seems to be .
----------------------------------------------------------------------

----------------------------------------------------------------------
b) Possibilistic logic.
In the simplest variant, formulae of two-valued logic are labelled
with elements from the real unit interval called "neccessity
degrees". The label of a formula represents the "trust" in the
information represented by the formula. The higher the value of the
label, the more trust is placed in the source of the information.

The `degree of modelness' of a two-valued interpretation I for a
labelled formula <F,d> is defined as follows:

. If I is a (classical) model for F, the degree is 1.
. If I is no (classical) model for F, the degree is 1-d.

The interpretation of this definition is as follows: If I is no model
of F, but the information represented by F is not fully trusted (d<1),
then <F,d> is given the `benefit of the doubt', i.e. it is accepted
that <F,d> could still be valid up to the degree 1-d.

This definition is especially interesting when drawing semantic
consequences from a set of labelled formulae. In classical logic, when
trying to establish that a formula F follows from a set X of formulae,
the set X acts as a `constraint' on the set of interpretations to be
considered. All interpretations in the constrained set have to be
models of F for F to be a consequence of X. The larger X becomes, the
smaller the set of interpretations, and the easier it becomes for F to
be a consequence of X.

In possibilistic logic, this constraint becomes a fuzzy one and the
set of interpretations to be considered is a fuzzy set. Using the
canonical definition of semantic consequence in this case, it turns
out that the label d of a labelled formula <F,d> acts as a threshold
value for the trust in the information to be considered in deriving F:
<F,d> follows from a set X of labelled formulae iff (essentially) F
follows classically from all formulae labelled in X with a degree at
least as high as d.

Possibilistic logic has been studied intensively in the literature;
compare .
----------------------------------------------------------------------

----------------------------------------------------------------------
c) Similarity-based logic.
This approach is also based on two-valued logic. The set of all
interpretations of some given two-valued logic is equipped with a
"similarity relation", i.e. a binary fuzzy relation (mapping pairs of
interpretations to elements of the real unit interval) satisfying the
`canonically fuzzified' properties of a classical equivalence relation
(relexivity, symmetry, transitivity).

The `degree of modelness' of a two-valued interpretation I for a
Formula F is then the infimum of the degrees of similarity of I with
all classical models of F, i.e. the `degree of existence' of a
classical model of F similar with I.

I won't discuss this approach any further here, see for instance .
----------------------------------------------------------------------

I've put a relevant section of my thesis at
http://lrb.cs.uni-dortmund.de/~lehmke/pub/sec34.pdf

Now for my first question: Are there any fundamentally different ways
of defining a graded model relation? As far as I know, probabilistic
logic and `uncertainty logics' (based on Dempster-Shafer theory) are
similar to possibilistic logic, only the way of calculating with
labels is different.

Are there any references which absolutely have to be part of a survery
on this subject?

----------------------------------------------------------------------

Next, some words on the approach taken in my thesis:

How can `uncertainty' expressed by truth values (i.e. vagueness) be
combined with `uncertainty' expressed by validity degrees (i.e. graded
illknowledge)?

The approach a described above doesn't offer a lot of possibilities,
because, as already remarked, it mixes truth values and validity
degrees in an unfortunate way.

For similarity-based logic (approach c), several open questions
remain. First of all, what exactly is the semantical meaning of the
degrees of modelness in the current version of this approach?
Secondly, how should the graded model relation be defined when the
underlying logic is many-valued? The definition of the graded model
relation is based on the classical non-graded model relation, so
either the classical definition of a model in many-valued logic is
used (using a set of designated truth values), or the similarity
relation used for defining the graded model relation is modified to
incorporate the truth value of a formula under a given interpretation
(i.e. the similarity relation maps a 4-tuple of two interpretations
and two truth values to a validity degree).

While it would be interesting to develop this further and compare it
to my approach sketched below, it won't be pursued any further here.

Possibilistic logic (approach b) offers a very straightforward
extension to many-valued logic, to be described in the following.

First, a little excurse: What happens if we use a _fuzzy_set_ of
designated truth values in many-valued logic? The degree of modelness
of an interpretation for a formula could be defined to be the degree
of membership of its truth value in the fuzzy set of designated truth
values.

This approach has the great advantage that it's immediately obvious
that the domain and range of the fuzzy set of designated truth values
do not need to be the same.

In fact, by choosing two arbitrary lattices (**) T, D of truth values
and validity degrees, respectively, and defining the fuzzy set of
designated truth values to be a D-fuzzy set on T(***), it is made
absolutely sure from the outset that no confusion between truth values
and validity degrees can arise.

Interestingly, choosing D to be two-valued yields classical
many-valued logic as a special case, and choosing T=D and the fuzzy
set of designated truth values to be identity yields approach a) as a
special case.

Another interesting special case is to choose T to be two valued,
yielding a logic where only validity degrees are many-valued.
Unfortunately, this doesn't make much sense when only one fuzzy set of
designated truth values is considered.

The obvious solution to this dilemma is the way taken in Pavelka's
logic. In Pavelka's logic , the set of designated truth values is
_localized_ to formulae by effectively labelling formulae with sets of
truth values (which are restricted to principal filters of the truth
value lattice).

Now, finally, coming to the approach taken in my PhD thesis: Label
formulae with D-fuzzy sets(***) on T, and define the degree of
modelness of a many-valued interpretation I for a labelled formula
<F,L> as L(I(F)) (where I(F) denotes the truth value of F under the
interpretation I).

Obviously, all examples so far (including Pavelka's logic) apart from
approach c) are special cases of this approach. Furthermore, choosing
both T and D to be many-valued yields a straightforward generalization
of possibilistic logic to the case of an underlying many-valued logic.

The main advantage I see in this approach is that it makes absolutely
clear that truth values and validity degrees are distinct and
independent concepts, yet defines a simple, understandable and
straightforward way for getting from the truth value of a formula to a
validity degree.

In my PhD thesis, I'm studying the semantics of logics of this type in
depth. Special cases (taking T to be two-valued leads to possibilistic
logic, taking D to be two-valued leads to [a generalization of]
Pavelka-type logic) are discussed and compared. Part of this is
already published, see for instance .

----------------------------------------------------------------------

Now for my second questions: Are there any other studies of logics of
this kind from a mathematical logic point of view?

I know that fuzzy sets of truth values are mentioned at several places
under different names (`truth qualifications' in ; `truth value
restrictions' in ), but I haven't seen a study in the context of
mathematical logic yet.

Furthermore, the term "fuzzy possibilistic logic" is well-known, but
it is only mentioned, not yet formally studied by Dubois and Prade
(compare ). Other mentions for instance in  are in a completely
different setting (fuzzy modal logic).

Lastly: Does this lengthy explanation establish a notion of "validity
degree" acceptable to logicians?

Is this kind of logic interesting as a formal tool for reasoning?

Can anyone (but me) see any merit/potential in it?

Stephan

----------------------------------------------------------------------

(*) When truth values are used to model vagueness, the most sensible
choice of truth value structure is a complete lattice, the unit
element of which means "total truth" and the zero element of which
means "total falsity". This choice will be implicitly assumed in the
following. The most popular particular lattice used is the real unit
interval [0,1] with the usual order of real numbers.

(**) Concerning the choice of a lattice structure for truth values,
see footnote (*). In fact, a lattice is probably the most general
sensible structure for truth values as well as degrees of validity,
when the intention is to model uncertainty.

(***) In my thesis, I'm making the additional assumption that the
fuzzy set is a _D-fuzzy_filter_ of T, in particular, it's monotone and
maps 1 to 1. The same assumption is made in this posting.
There's a lot of justification for this choice, but it'd lead too far
to expand on this here.

----------------------------------------------------------------------


@ARTICLE{Lee/Chang71,
language = "USenglish",
author = "Richard C. T. Lee and Chin-Liang Chang",
title = "Some Properties of Fuzzy Logic",
journal = {Information and Control},
year = 1971,
volume = 19,
number = 1,
pages = "417-431"}


language = "USenglish",
editor = "Dov M. Gabbay and C. J. Hogger and J. A. Robinson",
series = {Handbook of Logic in Artificial Intelligence and Logic Programming},
booktitle = {Nonmonotonic Reasoning and Uncertain Reasoning},
publisher = "Claredon Press",
volume = 3,
year = 1994,
author = "Didier Dubois and J{\'e}r{\^o}me Lang and Henri Prade",
title = {Possibilistic Logic},
pages = "439-513"}


@INCOLLECTION{Esteva/Garcia/Godo99,
language = "USenglish",
editor = "Didier Dubois and Erich Peter Klement and Henri Prade",
booktitle = "Fuzzy Sets, Logics and Reasoning about Knowledge",
series = {Applied Logic},
volume = 15,
year = "1999",
author = {Francesco Esteva and Pere Garcia and Llu{\'\i}s Godo},
title = "About Similarity-Based Logical Systems",
pages = "269-287"
}


@ARTICLE{Pavelka79I,
language = "USenglish",
author = "Jan Pavelka",
title = "On Fuzzy Logic {I} --- {M}any-valued rules of inference",
journal = {Zeitschrift f\"ur Mathematische Logik und Grundlagen der Mathematik},
year = 1979,
volume = 25,
pages = "45-52"}


@INCOLLECTION{Lehmke99a,
language = "USenglish",
editor = "Vil\'em Nov\'ak and Irina Perfilieva",
booktitle = "Discovering the World with Fuzzy Logic",
publisher = "Physica-Verlag",
series = "Studies in Fuzziness and Soft Computing",
volume = 57,
year = "2000",
author = {Stephan Lehmke},
title = "Degrees of Truth and Degrees of Validity --- Two Orthogonal Dimensions of Representing Fuzziness in Logical Systems",
pages = "192-236"
}


language = "USenglish",
title = "{PRUF} --- A Meaning Representation Language for Natural Languages",
journal = {International Journal of Man Machine Studies},
year = 1978,
volume = 10,
pages = "395-460",


@INCOLLECTION{Baldwin81,
language = "USenglish",
editor = "E. H. Mamdani and B. R. Gaines",
booktitle = "Fuzzy Reasoning and its Applications",
year = 1981,
author = "J. F. Baldwin",
title = {Fuzzy logic and fuzzy reasoning},
pages = "133-148"}


@ARTICLE{Hajek/Harmancova/Verbrugge94,
language = "USenglish",
author = {Petr H{\'a}jek and Dagmar Harmancov\'a and Rineke Verbrugge},
title = "A Qualitative Fuzzy Possibilistic Logic",
journal = {International Journal of Approximate Reasoning},
year = 1995,
volume = 12,
pages = "1-9"}

```--
Stephan Lehmke     		 Stephan.Lehmke@cs.uni-dortmund.de
Fachbereich Informatik, LS I	 Tel. +49 231 755 6434
Universitaet Dortmund		 FAX 		  6555
D-44221 Dortmund, Germany
############################################################################
This message was posted through the fuzzy mailing list.
(1)  To subscribe to this mailing list, send a message body of
"SUB FUZZY-MAIL myFirstName mySurname" to listproc@dbai.tuwien.ac.at
(2)  To unsubscribe from this mailing list, send a message body of
"UNSUB FUZZY-MAIL" or "UNSUB FUZZY-MAIL yoursubscription@email.address.com"
to listproc@dbai.tuwien.ac.at
(3)  To reach the human who maintains the list, send mail to
fuzzy-owner@dbai.tuwien.ac.at
(4)  WWW access and other information on Fuzzy Sets and Logic see
http://www.dbai.tuwien.ac.at/ftp/mlowner/fuzzy-mail.info
(5) WWW archive: http://www.dbai.tuwien.ac.at/marchives/fuzzy-mail/index.html
```

This archive was generated by hypermail 2b30 : Sat Mar 31 2001 - 14:50:34 MET DST