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 [1].
    ----------------------------------------------------------------------

    ----------------------------------------------------------------------
    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 [2].
    ----------------------------------------------------------------------

    ----------------------------------------------------------------------
    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 [3].
    ----------------------------------------------------------------------

    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 [4], 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 [5].

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

    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 [6]; `truth value
    restrictions' in [7]), 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 [2]). Other mentions for instance in [8] 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?

    With many thanks in advance for any comments, references or pointers
    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.

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

    [1]
    @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"}

    [2]
    @INCOLLECTION{Dubois/Lang/Prade94,
            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",
            address = "Oxford",
            volume = 3,
            year = 1994,
            author = "Didier Dubois and J{\'e}r{\^o}me Lang and Henri Prade",
            title = {Possibilistic Logic},
            pages = "439-513"}

    [3]
    @INCOLLECTION{Esteva/Garcia/Godo99,
            language = "USenglish",
            editor = "Didier Dubois and Erich Peter Klement and Henri Prade",
            booktitle = "Fuzzy Sets, Logics and Reasoning about Knowledge",
            publisher = "Kluwer Academic Publishers",
            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"
    }

    [4]
    @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"}

    [5]
    @INCOLLECTION{Lehmke99a,
            language = "USenglish",
            editor = "Vil\'em Nov\'ak and Irina Perfilieva",
            booktitle = "Discovering the World with Fuzzy Logic",
            publisher = "Physica-Verlag",
            address = "Heidelberg",
            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"
    }

    [6]
    @ARTICLE{Zadeh78,
            language = "USenglish",
            author = "Lotfi A. Zadeh",
            title = "{PRUF} --- A Meaning Representation Language for Natural Languages",
            journal = {International Journal of Man Machine Studies},
            year = 1978,
            volume = 10,
            pages = "395-460",
            note = "Reprinted in \cite{ZadehSelectedPapers}."}

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

    [8]
    @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