Re: Ex-Con logic

schubert@cs.rochester.edu
Date: Mon, 21 Feb 1994 18:22:28 -0500
From: schubert@cs.rochester.edu
Message-id: <199402212322.SAA07435@cherry.cs.rochester.edu>
To: boley@dfki.uni-kl.de, cg@cs.umn.edu, fritz@rodin.wustl.edu,
        interlingua@ISI.EDU
Subject: Re:  Ex-Con logic
Cc: schubert@cs.rochester.edu

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

As a reminder, my example was 

   (E x)(E z)~((E v)(E w)~((~(P(x)&P(v)) & ~(P(z)&P(x))) & R(v,w,x))
   (E v)(E w)~((E x)(E y)~((~(P(v)&P(w)) & ~(P(y)&P(w))) & R(y,x,w))
(the second is obtained from the first by variable renaming x z v w
                                                            w v y x
and permutation of conjuncts).

The observation that the 2 wffs have the "same" existential graph
seems to me unhelpful, since all we can ever display, or compute with,
are their tokens (embodiments, as you say). Those tokens stubbornly
insist on having the properties -- like node identities, locations, 
relative configuration of parts in the physical medium, etc. -- that 
you have abstracted away. The problem is to match the tokens, not the 
abstract structures they are tokens OF. My challenge was to show this 
is easy for propositions in John's sense, and this remains unanswered.

Look, one can play the abstract identity game without graphs: 
I will define a "conceptual formula" as one in which a subexpression
written like (P1 & P2 & ... & Pn) is viewed as a notation for a SET
of formulas, to be conjunctively interpreted. For instance, (P1 & P2)
and (P2 & P1) are the SAME conceptual formula. (We could write 
AND{P1, ..., Pn}, but why bother?) Similarly (P1 V P2 V ...V Pn) is
a SET of formulas, to be disjunctively interpreted. (Again, we could
use brace notation -- as is often done in defining "clauses" in
resolution theorem proving, but...) And similarly sequences of
existential quantifiers (or sequences of universal quantifiers) are
viewed as sets, e.g., (E x)(E y)P(x,y) is the same conceptual formula
as (E y)(E x)P(x,y). For a sequence of negations, all that matters is
the parity, i.e., ~~~ is indistinguishable from ~, etc. Finally, bound
variable names don't matter, i.e., a conceptual formula (E v)phi remains
the same conceptual formula when we rename v to w in the quantifier and
for all free occurrences of v in phi. (And let me emphasize: whether
you make a set of argument occurrences coreferential by using a common
distinctive name in all those occurrences or by drawing pointers to
a common, distinctive node surely matters little from a technical
perspective, whatever your cognitive preferences may be.)

So now I can say that if only we were to change those ugly standard
logical formulas above to conceptual formulas, they'd be the same!

> 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.)

My point, in my position paper in John's book, was that if you view
expressions of a (standard) logical syntax as "vertices", and the
relation between an expression and its immediate ordered constituents
as labeled edges, then sets of logical formulas ARE graphs (DAGs),
mathematically speaking. So to say "I'm using graphs rather than 
formulas" is rather meaningless. Yet this is roughly the slogan by
which net adherents have often distinguished themselves, as a group,
>From logic adherents. Thus whatever you say concerning the significance
of homomorphisms and cycles and so on in networks also carries over to 
formulas, since they ARE graphs. (Note that this is also the view taken 
in modern feature logics, whose expressions are sometimes written in a
kind of matrix notation and sometimes as node-link diagrams.)

Len
expressions are sometimes