Comments from Vladimir Lifschitz on the Nonmonotonic Proposal

Richard Fikes <pwtc!>
Date: Sun, 29 Jul 90 00:06 PDT
From: Richard Fikes <pwtc!>
Subject: Comments from Vladimir Lifschitz on the Nonmonotonic Proposal
Cc: pwtc!
Included-Msgs: <9007271825.AA25426@Gang-of-Four.Stanford.EDU>,
               The message of 27 Jul 90 11:25 PDT from labrea!val@Gang-of-Four.Stanford.EDU,
               The message of 27 Jul 90 11:25 PDT from Vladimir Lifschitz
Included-References: <>,
                     The message of 17 Jul 90 09:53 PDT from Richard Fikes
Message-id: <>
I ask Vladimir to evaluate the new proposal for expressing nonmonotonic
knowledge in KIF.  He will not be at AAAI, but sent the following


    Date: Fri, 27 Jul 90 11:25 PDT
    From: Vladimir Lifschitz <labrea!val@Gang-of-Four.Stanford.EDU>
    To: pwtc!
    To: genesereth@cs.Stanford.EDU
    In-Reply-To: Richard Fikes's message of Tue, 17 Jul 90 09:53 PDT <>
    Subject: KIF

	   Notes on the Nonmonotonicity Section of the KIF Manual

			     July 27, 1990

    1. In connection with the closed world assumption (CWA), we need to
    distinguish between the ground atoms of the internal language of the
    system and the larger class of the baselevel ground atoms of KIF.
    The designer of the system perhaps knew nothing about KIF, and his
    understanding of the CWA had nothing to do with this larger class.
    For this reason, it seems that (baselevel $p) in the formula on
    p. 27 should be replaced by something like (internal-language $p).

    The semantics of "internal-language" is not completely clear to me. It
    probably applies only to the internal languages that are "logic-based"
    in some sense. If a ground atom of KIF contains any of the constants
    listed in Appendix A (A.1-A.4) then apparently it is not an internal-
    language atom. Are there any other exceptions? Can it happen that, in
    the process of translating the internal knowledge base into KIF, some
    defined relations are introduced, such as "bachelor" in Sec. 8.4? If
    yes, then such relations should not be allowed in internal-language
    formulas either. Or is it forbidden to add new definitions in the
    process of translating knowledge into KIF? (Will there be any
    specifications--formal or informal--for the translation process?)

    A similar problem arises in connection with the unique names assumption
    (UNA), because there are more ground terms in KIF than in the internal

    2. How will we define "derivable" for KIF (which is used in the CWA and
    UNA)? This isn't obvious, because KIF is not a first-order language.
    Are there any postulates for the constants from A.1-A.4, including
    "true"? For "database"? For "defrelation"? For "derivable" itself?
    Perhaps the notion of derivability should be applied to the "internal-
    language component" of KIF only; then we won't have to address these

    When this is settled, it would be a good idea to prove that the
    definitions of the CWA and UNA in KIF are satisfactory in the sense
    that, for some specific method of translating first-order formulas
    into KIF, they are equivalent to the usual definitions of the CWA
    and UNA for first-order theories. This should be easy if all the
    definitions are reasonable.

    3. Do we want to include predicate completion as a separate construct?
    It is restricted here to the solitary case, when it is equivalent to
    circumscription anyway. Predicate completion was originally proposed
    as a semantics for logic programs, but now many people favor the
    stratification-based semantics (which can be easily expressed in
    terms of circumscription--see my paper in Ginsberg's collection,
    p. 337). Besides, the solitary case is inadequate for logic programs
    anyway, because it is not applicable when the program is recursive.

    4. About including second-order logic in KIF: I would support this
    solution to the problem of expressing circumscription. True, there
    will be no complete inference procedure then, but for languages as
    expressive as KIF such procedures would be of no use anyway. KIF
    includes all first-order number theory; you can write Fermat's last
    theorem as a sentence in KIF!

    Circumscription wouldn't be the only opportunity to use second-order
    quantifiers in KIF. Recursive definition can be reformulated as
    explicit second-order definitions; we'll be able, for instance, to
    define transitive closure using the defrelation construct.

    5. It will be necessary to include some notation for circumscription
    policies, including priorities. I gave Mike a draft of the chapter for
    the Handbook of Logic in AI that I'm writing now, which can be useful.

    6. Brewka's IJCAI-87 paper "The Logic of Inheritance in Frame Systems"
    describes a translation from a frame language into circumscription.
    It would be useful to include an example based on that paper.