**Mail folder:**Interlingua Mail**Next message:**Tom Gruber: "announcing the Knowledge Sharing library on the WWWeb"**Previous message:**Fritz Lehmann: ""Close enough""**Reply:**schubert@cs.rochester.edu: "Re: Ex-Con logic"

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?