**Mail folder:**Interlingua Mail**Next message:**sowa@watson.ibm.com: "Some thoughts on K.I.F."**Previous message:**Matthew L. Ginsberg: "MVL theorem proving system available via anonymous ftp"

Full-Name: Richard Fikes Date: Thu, 21 Mar 1991 14:02:10 PST From: Richard Fikes <fikes@sumex-aim.stanford.edu> Subject: Interlingua Nonmon Proposal and Meeting Agenda Items To: interlingua-admin@vaxa.isi.edu, kr-advisory@isi.edu, grosof@ibm.com, nado@tc.pw.com Cc: fikes@sumex-aim.stanford.edu Message-id: <MacMS.28002.31327.fikes@sumex-aim.stanford.edu>

Folks, Our meeting next Thursday will be focused on four items as follows: Presentation and review of a proposal by Vladimir Lifschitz for language extensions to support representation of nonmonotonic knowledge. Presentation of a proposal by Mike Genesereth and Reed Letsinger for extending the interlingua to nth order. Report by Ramesh Patil and myself on the status and plans for building translators into and out of the interlingua. Discussion of next steps for the working group. Benjamin Grosof from IBM Watson Research and Bob Nado from Price Waterhouse will be joining us and providing initial reviews of the nonmon proposal. The proposal itself is appended to this message as a Tex file. I encourage you to read and think about it before the meeting (its short). The following is my current attendees status list: Richard Fikes (yes) Mike Genesereth (yes) Danny Bobrow (yes) Piero Bonissone (?) Ron Brachman (no) Ramanathan Guha (yes) Reed Letsinger (yes) Vladimir Lifschitz (yes) Bob MacGregor (yes) John McCarthy (?) Peter Norvig (yes) Ramesh Patil (yes) Len Schubert (yes) Benjamin Grosof (yes) Bob Nado (yes) Bob Neches (?) Peter Patel-Schneider (yes) Bill Swartout (?) Gio Wiederhold (no) Tim Finin (?) Tom Gruber (yes) Marty Tenenbaum (?) Mike and I look forward to seeing you all next Thursday at 4:00 and to having a productive meeting. Location information for the meeting to follow. Richard P.S. Vladimir's nonmon proposal: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %%% Macros %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \font\eightrm=cmr10 scaled 800 \font\twelverm=cmr10 scaled \magstep1 \font\twelvebf=cmbx10 scaled \magstep1 \font\fourteenrm=cmr10 scaled \magstep2 \font\fourteenbf=cmbx10 scaled \magstep2 \countdef\sectioncount=11 \countdef\subsectioncount=13 \countdef\subsubsectioncount=15 \sectioncount=0 \subsectioncount=0 \subsubsectioncount=0 \def\sect#1{\advance\sectioncount by1\subsectioncount=0 \nobreak\bigskip\noindent{\bf\the\sectioncount. #1}\par\medskip} \def\subsect#1{\advance\subsectioncount by 1\subsubsectioncount=0 \bigskip\noindent{\bf\the\sectioncount.\the\subsectioncount\ #1}\par \nobreak\medskip} \def\subsubsect#1{\advance\subsubsectioncount by 1 \bigskip\noindent {\bf\the\sectioncount.\the\subsectioncount.\the\subsubsectioncount\ #1}\par \nobreak\medskip} \def\nosect#1{\bigskip\noindent{\bf#1}\par\nobreak\medskip} \def\uncatcodespecials{\def\do##1{\catcode`##1=12}\dospecials} \def\setupverbatim{\tt\def\par{\leavevmode\endgraf}\catcode`\`=\active \obeylines\uncatcodespecials\obeyspaces} {\catcode`\`=\active \gdef`{\relax\lq}} {\obeyspaces\global\let =\ }{\obeylines\global\let^^M=\par} \def\beginverbatim{\par\begingroup\setupverbatim\doverbatim} {\catcode`|=0 \catcode`\\=12 |obeylines|gdef|doverbatim^^M#1\endverbatim{#1|endgroup}} \def\bibitem#1#2{\medskip\noindent} \def\cite#1{[#1]} \def\begconcept{\bigskip\hrule\par\nobreak \noindent\vrule height3pt\hfill\vrule height3pt\par\nobreak} \def\midconcept{\nobreak\medskip\hrule\medskip\par} \def\defconcept#1#2{\noindent{\tt #1}\hfill{\it #2}\par\nobreak} \def\difconcept#1#2{\noindent{\tt #1}\hfill{\it #2}\par\medskip} \def\endconcept{\nobreak\noindent\vrule height3pt\hfill\vrule height3pt\par \nobreak\hrule\bigskip} \countdef\eqcount=17 \eqcount=1 \def\eqn{\the\eqcount\advance\eqcount by1} \sect{Nonmonotonicity} Many knowlege representation and reasoning systems are capable of drawing conclusions based on the absence of knowedge from a database. This is nonmonotonic reasoning. The addition of new sentences to the database may be cause for the system to retract earlier conclusions. In some systems, the exact policy for deriving nonmonotonic conclusions is built into the system. In other systems, the policy can be modified by its user, though rarely within the system's knowledge representation language (e.g. by selecting which predicates to circumscribe). Since KIF is a knowledge representation language and not a system, it is necessary to provide means for its user to express his nomonotonic reasoning policy within the language itself. To this end, we define a new type of legal list expressions---{\it default rules}. The syntax of defaults rules is described by the following modified BNF: \medskip \beginverbatim <defrule> ::= <sentence> | (<<= <sentence> <premise>*) <premise> ::= <sentence> | (consis <sentence>) \endverbatim \medskip The sentence that follows {\tt <<=} is the {\it consequent} of the rule; the premises that are sentences are its {\sl prerequisites}, and the premises that have the form {\tt (consis $\phi$)} are its {\it justifications}. Notice that every sentence $\phi$ is also a default rule. The consequent of this default is $\phi$ itself. For instance, the default rule \medskip \beginverbatim (<<= (flies $x) (bird $x) (consis (flies $x))) \endverbatim \medskip \noindent expresses that an object can be assumed to fly if this object is known to be a bird and it is consistent to assume that it flies. A {\it nonmonotonic database} is a set of default rules. Since every sentence is a default rule, every database (i.e. set of sentences) is a nonmonotonic database. The semantics of default rules described at the end of this section extends the notion of a model to nonmonotonic databases. We say that a nonmonotonic database $\Delta$ {\it (nonmonotonically) entails} a sentence $\phi$ if every model of $\Delta$ is also a model of $\phi$. We will see that the definition of a model for nonmonotonic databases is ``nonlocal'': One cannot check whether an interpretation $i$ is a model by looking at each default rule in isolation. This feature of the definition is responsible for the nonmonotonic character of the new notion of entailment. The use of {\tt consis} is the only source of nonmonotonicity in KIF. Accordingly, a rule without justifications will be called {\it monotonic}. This particularly simple case will be discussed first. \subsect{Monotonic Rules} It is clear that a monotonic rule is either a sentence or an expression of the form $$(\hbox{\tt <<= $\phi$ $\phi_1$ $\dots$ $\phi_n$}),$$ where $\phi$, $\phi_1,\dots,\phi_n$ are sentences. Such an expression should be distinguished from the implication $$(\hbox{\tt <= $\phi$ $\phi_1$ $\dots$ $\phi_n$}).$$ Monotonic rules are not sentences; they are similar to {\it inference rules}, familiar from elementary logic. If, for instance, $\Delta$ consists of some sentences $\Delta_0$ and one rule ({\tt <<=} $\psi$ $\phi$), where $\phi$ and $\psi$ are sentences without free variables, then the set of sentences entailed by $\Delta$ is the smallest set of sentences which (i) contains $\Delta_0$, (ii) is closed under logical entailment, and (iii) contains $\psi$ provided that it contains $\phi$. It is not generally true that this set contains the implication ({\tt <=} $\psi$ $\phi$). The rationale for using monotonic rules in knowledge representation, instead of implications, is twofold. On the one hand, the ``directed'' character of rules can simplify the task of developing efficient inference procedures. On the other hand, in some cases, replacing {\tt <==} by {\tt <=} would be semantically unacceptable. For instance, the rules \medskip \beginverbatim (<<= (status-known $x) (citizen $x)) (<<= (status-known $x) (not (citizen $x))) \endverbatim \medskip \noindent allow us to infer {\tt (status-known Joe)} only if one of the sentences \medskip \beginverbatim (citizen Joe), (not (citizen Joe)) \endverbatim \medskip \noindent can be inferred. Replacing the rules by implications would make {\tt (citizen \$x)} identically true. \subsect{Logic Programs} A pure Prolog rule $$\phi\hbox{\tt :-}\phi_1,\dots,\phi_n$$ where $\phi,\phi_1,\dots,\phi_n$ are atoms, can be viewed as a syntactic variant of the monotonic rule $$(\hbox{\tt <<= $\phi$ $\phi_1$ $\dots$ $\phi_n$})$$ except for two important details. First, the declarative semantics of Prolog applies the {\it unique names assumption} to its ground terms. If, for example, the program contains no function constants, then this assumption can be expressed by the sentences $$(\hbox{\tt not ($=$ $\sigma_1$ $\sigma_2$))}$$ for all distinct object constants $\sigma_1$, $\sigma_2$ in the language of the program. Second, this semantics applies the {\it closed world assumption} to each relation. For a relation constant $\sigma$, this assumption can be expressed by the rule $$(\hbox{\tt <<= (not ($\sigma$ $\nu$)) (consis (not ($\sigma$ $\nu$)))}),$$ where $\nu$ is a sequence variable. A pure Prolog program can be translated into KIF by appending to it (i) the sentences expressing the unique names assumption, and (ii) the default rules expressing the closed world assumption. This method can be easily extended to programs with negation as failure. A negative subgoal {\tt not}$\,\phi$ is represented in KIF by the premise {\tt (consis (not $\phi$))}. (Adding {\tt consis} is necessary because, in KIF, {\tt not} represents classical negation, rather than negation as failure.) \subsect{Circumscribing Abnormality} Extending a set of sentences by the closed world assumption for some relation constant $\sigma$, expressed by a default rule as shown above, has the same effect as circumscribing $\sigma$ (with all object, function and relation constants varied). In particular, circumscribing abnormality can be expressed by the default rule $$\hbox{\tt (<<= (not (ab }\nu\hbox{\tt )) (consis (not (ab }\nu\hbox{))))}.$$ Consider, for instance, the nonmonotonic database that contains, in addition to this standard default, two facts: {\tt (bird tweety)} and \medskip \beginverbatim (<= (flies $x) (bird $x) (not (ab aspect1 $x))) \endverbatim \medskip \noindent (birds fly unless they are abnormal in {\tt aspect1}). This database nonmonotonically entails the conclusion that everything is {\it not} abnormal, including {\tt tweety}: \medskip \beginverbatim (not (ab $x)) \endverbatim \medskip >From this, we can conclude that {\tt tweety} flies. Suppose, on the other hand, that our database includes also the fact that {\tt tweety} is abnormal in {\tt aspect1}: \medskip \beginverbatim (ab aspect1 Tweety) \endverbatim \medskip In this case, we can no longer infer that {\tt tweety} is not abnormal, and, therefore, we cannot conclude that {\tt tweety} is a flier. Note, however, that we have {\it not} asserted that {\tt tweety} cannot fly; we have only prevented the default rule from taking effect in this case. \subsect{Semantics of Default Rules} Recall that the truth value of a sentence is defined relative to an interpretation $i$ and a variable assignment $v$. To define the truth value of a premise in a default rule, we need to select, instead of a single interpretation $i$, a {\it set} of interpretations---the interpretations that are considered ``possible.'' In the following definition, $I$ is a set of interpretations which all have the same universe of discourse $O$, and $v$ is a variable assignment with this universe. We consider prerequisites and justifications separately. \begconcept \defconcept{\tt $\phi$}{premise} The truth value of a prerequisite is {\it true} if and only if it is true for at every ``possible'' intepretation. $$t_{Iv}(\phi)=\cases{ true&$\forall i\in I\;t_{iv}(\phi)=true$\cr false&otherwise\cr}$$ \midconcept \defconcept{\tt (consis $\phi$)}{premise} The truth value of a justification is {\it true} if and only if its second term is true for at least one ``possible'' intepretation. $$t_{Iv}(\hbox{\tt (consis $\phi_i$)})=\cases{ true&$\exists i\in I\;t_{iv}(\phi)=true$\cr false&otherwise\cr}$$ \endconcept Let $\Delta$ be a nonmonotonic database. We define when a set $I$ of interpretations is ``a set of possible worlds'' for $\Delta$, by means of the following fixpont construction. Consider a universe of discourse $O$; by a {\it world} we understand an interpretation with the universe $O$. Let $I$ be a set of worlds. Consider the largest set $I'$ of worlds such that, for each default $\delta\in\Delta$ and each variable assignment $v$ with the universe $O$, the following condition holds: If the truth value of every prerequisite of $\delta$ for $I'$ and $v$ is $true$, and the truth value of every justification of $\delta$ for $I$ and $v$ is true, then the truth value of the consequent of $\delta$ for $I'$ and $v$ is $true$. (This $I'$ always exists.) If $I'=I$, then we say that $I$ is {\it a set of possible worlds} for $\Delta$. Typically, a nonmonotonic database has many sets of possible worlds; it is clear, for instance, that any two interpretations with different universes cannot belong to the same set of possible worlds. An interpretation $i$ is a {\it model} of $\Delta$ if it belongs to some set of possible worlds for $\Delta$. -------