Propositions

• Mail folder: Interlingua Mail
• Next message: sowa: "Re: Propositions"
• Previous message: phayes@cs.uiuc.edu: "Re: Intensions/Sinn"
• Maybe in reply to: macgregor@ISI.EDU: "Propositions"
• Reply: sowa: "Re: Propositions"

Date: Tue, 15 Feb 94 06:21:18 EST
From: sowa <sowa@turing.pacss.binghamton.edu>
Message-id: <9402151121.AA14149@turing.pacss.binghamton.edu>
To: cg@cs.umn.edu, interlingua@ISI.EDU
Subject: Propositions
Cc: sowa@turing.pacss.binghamton.edu

Pat and Bob,

There are two extreme cases in the definition of propositions.
One extreme is the identification of propositions with sets of possible
worlds (or possible models).  This leads to the absurd result that
all theorems are equivalent to T.  Therefore, if you believe
2+2=4, then you must also believe every theorem of mathematics.

The other extreme is the identification of propositions with
sentences in some language.  This means that P&Q is a different
proposition from Q&P.

We would like to have some definition that is somewhere between
the two extremes, that is relatively language-independent, and
that makes a reasonable match with plausible intuitions.  I will
tell you my preferred definition, which I am strongly leaning towards,
but which I am willing to modify if someone can give me good reasons
to do so.

First, I begin with a very nice subset of logic, which I call
existential-conjunctive logic.  It is simply first-order predicate
calculus with only one quantifier -- the existential -- and only
one Boolean operator -- conjunction.   No universals, negations,
disjunctions, or implications.

This subset is nice for several reasons:

 1. Existential quantification and conjunction are the two
    least problematical operators of logic.  You can find puzzles,
    paradoxes, and philosophical controversies about every one
    of the others:  universal quantification, implication,
    disjunction, and negation.

 2. Every database system, frame system, and even good old-fashioned
    file system can represent existential-conjunctive logic.

 3. It is capable of describing anything that exists, although it
    cannot state any generalizations or deny that something exists.
    For example, I can describe the complete contents of the room
    I am now sitting in using only existential-conjunctive logic.
    But I can't tell you that there is no hippopotamus in it.
    (Actually, the room next to it does have a hippopotamus -- a
    replica of a blue hippopotamus from the Metropolitan Museum.)

 4. It is an easily decidable subset of logic, and there exists a
    normal form for every proposition that is easily computable
    in (N log N) time.

Normal form:  Simply convert a formula to prenex normal form,
sort all the conjuncts in alphabetical order, delete duplicates, 
and replace the variable names by the standard names x1, x2, x3, ...

For this subset of logic, I define two formulas to be expressions of
the same proposition iff they can be reduced to the same normal form.

This definition has all the nice properties you may like -- and it
happens to coincide with the definition of proposition as a class
of possible worlds or possible models.

Now I would like to extend this definition to all of first-order logic.
I begin by adding just one more operator -- negation.  Then given any
formula in FOL, I make the usual conversions:

 (Ax) -> ~(Ex)~

 (p or q) -> ~(~p & ~q)

 (p implies q) -> ~(p & ~q)

The only simplifications I'll allow are to delete redundant
parentheses and to delete two adjacent negations with nothing
between them; i.e. ~~ becomes blank.

Normal form:  This leads to a normal form for FOL that is as easy
to compute as the normal form for existential-conjunctive logic:
Starting with the innermost parentheses, sort the conjuncts and
delete duplicates; then work your way out of the nested parentheses
doing the sorting and deleting.

Now I will define two formulas to be expressions of the same
proposition iff they reduce to the same normal form by this procedure.

I claim that this definition has lots of nice properties:
easily computable; trivial variations collapse to the same
normal form; most obvious variations collapse to the same form;
but nonobvious variations do not collapse to the same form.

Furthermore, given the same predicate names and alphabetical
sort order, you can define equivalent procedures for languages
as syntactically different as KIF, CGs, vanilla-flavored predicate
calculus, etc.

If you want more than FOL, this procedure can be extended
by allowing the quantifiers to range over whatever you like.

John Sowa