Ex-Con logic

fritz@rodin.wustl.edu (Fritz Lehmann)
Date: Wed, 16 Feb 94 10:52:37 CST
From: fritz@rodin.wustl.edu (Fritz Lehmann)
Message-id: <9402161652.AA09596@rodin.wustl.edu>
To: boley@dfki.uni-kl.de, cg@cs.umn.edu, interlingua@ISI.EDU
Subject: Ex-Con logic


          "Russell for instance imagines every fact as
           a spatial complex."
                                   Ludwig Wittgenstein

          "All necessary thought is diagrammatic."
                                   Charles S. Peirce

      Len Schubert, John Sowa and Pat Hayes discussed that part of
logic without nested negations (which Sowa called existential-
conjunctive logic), and the problems of variable renaming and
conjunct-order within that part.

      First: how nice semantic networks are.  Bound variables are an
abomination; they are no part of logic at all -- they are artifacts
of the unhappy attempt to force a (combinatorial) network into a
string.  Tedious and inelegant phrases like "not occurring freely in
the scope of the quantifier" or "up to renaming of variables" have
needlessly taxed the patience of generations of students.  In Sowa's
"Principles of Semantic Networks", Schubert challenged us net-nuts to
justify the graph-formalism with actual graph-theoretic merits.  One
such merit is that there is no theoretical notion of "up to
renaming."  A semantic network floats in abstract space and there is
no need to maintain multiple versions of the same graph in different
variable permutations and hundreds of different arbitrary order-
embeddings.  [If you elect to represent the graph as a string in a
conventional computer, as in linear CGs, KIF/FOL, or Boley's RELFUN
version of his DRLH's, these emerge as implementation problems, but
they are _not_ logic problems.]  Similarly, if semantic networks
include nested negation loops (Sowa's "contexts") as in Peirce's
Existential Graphs, the canonical form emerges immediately:
  '~p->q', '~q->p', '~(~p ^ ~q)', and 'p v q' all have the same
simple shape (a region with two holes) and this spare lack of
notational excess is multiplied many times over when relational
structures interact with the loops.  Len's two examples with permuted
variables and conjuncts have the same existential graph.  Particular
embodiments of abstract semantic networks may have their own
notational artifacts, of course, like the shapes of drawn graphs; I
prefer these artifacts to the mess of bound variables.

     Second: What Sowa calls existential-conjunctive logic is what
some others call 'vivid" knowledge representation (although there are
variants), directed hypergraphs (Boley), models (Tarski), or
relational structures (in Universal Algebra).  Hayes calls this a
trivial part of logic but I hope not, since I am studying it
intently.  I have found a rich world of hierarchic structures,
especially when the ex-con logic is typed with ordered sorts.  Every
descriptive graph is subsumed by its subgraphs, and the remarkable
poset of connected hypergraph inclusion is a quotient-structure in
the induced algebra of typed relational structures ordered by
subsumption.  Group-theoretic graph symmetries abound (unlike the
case of functional "feature structures") and defeat efforts to make
everything into nice distributive lattices with unique greatest lower
bounds handy for theory-resolution and unification.  Further
quotients are determined by inter-cycle (matroid) inclusion
relations.  Most of KL-ONE hierarchies reside within this structure,
and it is only beginning to be studied for Conceptual Graphs (by
Gerard Ellis, Bob Levinson, Michel Chein, Marie-L. Mugnier and
sometimes me).  Determining the congruences and quotients should
allow very fast inference (divide & conquer).  Also, the conceptual
lexicon interacts via graph-grammar definitional expansions of types. 
The theory of this structure is necessarily intensely graph-
theoretic, dealing with subgraph iso- and homo-morphisms and
symmetries and cycles of graphs, which I feel answers Len's challenge
re semantic nets.  (In Episodic Logic's notation, he is apostate.)

      If anyone can steer me to any prior work on this kind of thing,
I would be most grateful.  (I think maybe Alex Borgida is looking
into the "rooted" subset.)  A very important question is:  how much
of real-world reasoning takes place within this "ex-con" hierarchy
(without reasoning about arbitrarily nestable negations)?  Hayes
suggested that most inference takes place outside it, but is that
really true?  (Walther's and Cohn's results on using a hierarchy to
speed the solution of "Schubert's Steamroller" suggests that it is
worthwhile to study even if the answer to that question is "somewhat
true").

                          Yours truly,   Fritz Lehmann
4282 Sandburg, Irvine, CA 92715  714-733-0566  fritz@rodin.wustl.edu
====================================================================
P.S. Hayes suggested "positive logic" (ex-con plus disjunction and
universal quantification) as a potential "intermediate logic" in
Sowa's sense.  This is the first I've heard of it.  What is gained? 
Universal quantifications with arbitrarily nestable scopes seem at
first glance to be as bad as arbitrarily nestable negations, since
every nontrivial u.q. makes a claim about what does _not_ exist. 
(All men are bald = there is no man with hair on his head.)  Is this
right?