# Interlingua Nonmon Proposal and Meeting Agenda Items

Richard Fikes <fikes@sumex-aim.stanford.edu>
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
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

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)
Bob MacGregor (yes)
John McCarthy (?)
Peter Norvig (yes)
Ramesh Patil (yes)
Len Schubert (yes)

Benjamin Grosof (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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%%% 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

\nobreak\bigskip\noindent{\bf\the\sectioncount. #1}\par\medskip}

\bigskip\noindent{\bf\the\sectioncount.\the\subsectioncount\ #1}\par
\nobreak\medskip}

\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

\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$.

-------