- To: cg@cs.uah.edu
- Subject: Extensions of Logical Graphs
- From: Jon Awbrey <jawbrey@oakland.edu>
- Date: Fri, 04 Aug 2000 23:23:02 -0400
- References: <LYRIS-3322-2847-2000.03.15-03.11.51--jawbrey#oakland.edu@lyris.acs.ttu.edu>
#%%%%%%%%%#%%%%%%%%%#%%%%%%%%%#%%%%%%%%%#%%%%%%%%%#%%%%%%%%%#
It occurs to me that a few members of this group might be interested
in several extensions of Peirce's Logical Graphs that I have been
developing over the past twenty years. By way of introduction,
of myself and my subject, I will give some personal history,
as it relates to these topics.
But first, for those who want the short version, I will try
to present the main ideas of these extensions as succinctly
as possible.
I should explain that I learned my graph theory in the
"midwestern graph theory" (MiGhTy) school, mostly from
Frank Harary at Michigan and Ed Palmer at Michigan State,
and so my terminology may be slightly different from that
which is used in other places.
For example, I always think of rooted trees as rooted in the
ground and growing upward, "toward the light", in other words,
in the "botanical" or the "phyllogenic" orientation rather than
the "genealogical" or the "phylogenic" format. So, my use of terms
like the subtree "above" a node or the path "below" a node needs to
be understood in this sense.
For now, I limit myself to the alpha level (propositional calculus
or sentential logic), since that has been my focus for several years.
Even though I do most of my thinking in the existential interpretation,
I will continue to speak of these forms as "logical graphs", because
I think it is an important fact about them that the formal validity
of the axioms and theorems is not dependent on the choice between
the entitative and the existential interpretations.
The first extension is the "reflective extension of logical graphs" (RefLog).
It is obtained by generalizing the negation operator "()" in a certain way,
calling "()" the "controlled", "moderated", or "reflective" negation operator
of order 1, and adding another such operator for each finite k = 2, 3, ... .
In sum, these operators are symbolized by bracketed argument lists as follows:
"(_)", "(_,_)", "(_,_,_)", ..., where the number of slots is the order of the
reflective negation operator in question.
The formal rule of evaluation for a k-operator is:
"(a, b, c, ...) = blank <=> Just one of the arguments a, b, c, ... = ()."
The interpretation of these operators, read as assertions about
the values of their arguments, is as follows:
Existential Interpretation: "Just one of the k argument is false."
Entitative Interpretation: "Not just one of the k arguments is true."
I am running out of time for today, so I will append a previous account
of these ideas, in hopes that it will serve as a sufficient introduction.
I'll be using "propositional calculus" as a symbolic notation for
talking about points of Bk and functions Bk->B, where B = {0, 1}.
These types of functions will often be spoken of as "propositions".
In effect, I'll be looking for analogies in the realm {Bk, Bk->B}
with all the sorts of things we would usually do with {Rk, Rk->R},
eventually asking what the "differential extension of prop calc"
ought to look like, for instance, what the logical analogues of
derivatives, differentials, Taylor series, (co)tangent spaces,
and so on, ought to be.
#Begin Citation#====#====#====#====#====#====#====#====#====#
Differential Logic & Dynamic Systems
Author: Jon Awbrey
Created: Dec 16, 1993
Revised: Oct 31, 1994
Revised: Mar 6, 2000
Project: Engineering 690
Advisor: M.A. Zohdy
Setting: Oakland University
Excerpt: Pages 1-3, 12-13.
Stand and unfold yourself. [Hamlet: Francisco -- 1.1.2]
Purpose
This series of reports develops a differential extension
of propositional calculus and applies it to a context of
problems arising in dynamic systems. The work pursued
here is coordinated with a parallel application that
focuses on neural network systems, but the dependencies
are arranged to make the present series the main and more
self-contained work, to serve as a conceptual frame and a
technical background for the network project.
Review & Transition
This note continues a previous discussion on the problem
of dealing with change and diversity in logic-based
intelligent systems. For ease of reference, we begin by
summarizing essential material from previous reports.
Table 1 outlines the notation we use for propositional
calculus. Explained as briefly as possible, we employ
only two basic kinds of truth-functional connectives,
both of variable k-ary scope. For the first, we use
concatenation as a connective for logical conjunctions of
k arguments. For the other, we use a bracket of the form
( , , , ) as a connective which says that exactly one of
its k arguments is false. All other truth-functional
connectives can be obtained in a very efficient style of
representation through combinations of these two forms.
Our treatment of propositional logic is derived from
the work of C.S. Peirce [P1, P2], who gave this approach
an extensive development in his graphical systems of
predicate, relational, and modal logic [Rob]. More
recently, these ideas were revived and supplemented in
an alternative interpretation by G. Spencer-Brown [SpB].
Both these authors used other forms of enclosure where we
use parentheses [here, "(" and ")"], but the structural
topologies of expression and the functional varieties of
of interpretation are fundamentally the same.
While working with expressions solely in propositional
calculus, the use of plain parentheses to represent logical
connectives is simplest to write and easiest to read for
both human and machine parsers. In our present discussion
we preserve this form of expression in tables and set-off
displays, but in contexts where parentheses are needed for
functional notation we use a distinctive font for logical
operators. (For example, Broadway: ( , , , ) .)
The briefest expression for logical truth is the empty
word, usually denoted [epsilon] or [lambda] in formal
languages, where it forms the identity element for
concatenation. To make it visible in our text, we denote
it by the equivalent expression "(())", or, especially if
operating in an algebraic context, by a simple "1". Also
when working in an algebraic mode, we use the plus sign
"+" for exclusive disjunction. Thus, we may express the
following paraphrases of of algebraic forms.
| A + B |
= |
(A,
B) |
= |
(B, A) |
| A + B + C |
= |
((A,
B), C) |
= |
(A,
(B,
C)) |
We should be careful to note that these last expressions
are not equivalent to the form (A, B, C).
Table 1. Syntax & Semantics of a Calculus for Propositional Logic
| Expression |
Interpretation |
Other Notations |
| " " |
True. |
1 |
| "()" |
False. |
0 |
| "A" |
A. |
A |
| "(A)" |
Not A. |
A'
~A |
| "A B C" |
A and B and C. |
A & B & C
A · B · C |
| "((A)(B)(C))" |
A or B or C. |
A v B v C |
| "(A (B))" |
A implies B.
If A then B. |
A Þ
B |
| "(A, B)" |
A not equal to B.
A exclusive-or B. |
A ¹
B
A + B |
| "((A, B))" |
A is equal to B.
A if & only if B. |
A = B
A Û
B |
| "(A, B, C)" |
Just one of
A, B, C
is false. |
A'B·C v
A·B'C v
A·B·C' |
| "((A),(B),(C))" |
Just one of
A, B, C
is true.
Partition all
into A, B, C. |
A·B'C' v
A'B·C' v
A'B'C |
"((A, B), C)"
"(A, (B, C))" |
Oddly many of
A, B, C
are true.
One or all of
A, B, C
are true. |
A + B + C
A·B·C v
A·B'C' v
A'B·C' v
A'B'C |
| "(X, (A),(B),(C))" |
Partition X
into A, B, C.
Genus X comprises
species A, B, C. |
X'A'B'C' v
X·A·B'C' v
X·A'B·C' v
X·A'B'C |
? The usage that one often sees, of a plus sign "+" to represent
inclusive disjunction, and the reference to this operation as
"boolean addition", is a misnomer on at least two counts. Boole
used the plus sign to represent exclusive disjunction (or at least,
an operation of aggregation restricted in its logical interpretation
to cases where the represented sets are disjoint [Boo, 32]), as any
mathematician with a sensitivity to the ring and field properties of
algebra would do. "The expression x + y seems indeed uninterpretable,
unless it be assumed that the things represented by x and the things
represented by y are entirely separate; that they embrace no individuals
in common" [Boo, 66]. It was only later that Peirce and Jevons treated
inclusive disjunction as a fundamental operation, but these authors, with
a respect for the algebraic properties that were already associated with
the plus sign, used a variety of other symbols for inclusive disjunction
[Sty, 177, 189]. It seems to have been Schröder who later reassigned the
plus sign to inclusive disjunction [Sty, 208]. Additional information,
discussion, and references can be found in [Boo] and [Sty, 177-263].
Aside from these historical points, which never really count against a
current practice which has gained a life of its own, this usage does have
a further disadvantage of cutting or confounding the lines of communication
between algebra and logic. For this reason, we are forced to avoid it here.
Out of the dimness opposite equals advance....Always
substance and increase,
Always a knit of identity....always distinction....
always a breed of life.
-- Walt Whitman, Leaves of Grass, [Whi, 28]
A Functional Conception of Propositional Calculus
In the general case, we start with a set of logical features {a1, ..., an}
that represent logical properties of objects or propositions about the world.
In concrete examples the features {ai} commonly appear as capital letters from
an "alphabet" like {A, B, C, ...} or as meaningful words from a linguisitic
"vocabulary" of codes. This language can be drawn from any sources, whether
natural, technical, or artificial in character and interpretation. In the
application to dynamic systems we tend to use the letters {x1, ..., xn} as
our coordinate propositions, and to interpret them as denoting properties
of a system's "state", that is, as propositions about its location in
configuration space. Because we have to consider non-deterministic systems
from the outset, we often use the word "state" in a loose sense, to denote
the position or configuration component of a contemplated state vector,
whether or not it ever gets a deterministic completion.
The set of logical features {a1, ..., an} provides a basis for generating
an n-dimensional "universe of discourse" that we denote by [a1, ..., an].
It is useful to consider each universe of discourse as a unified categorical
object that incorporates both the set of points áa1, ..., an ñ and the set of
propositions F : áa1, ..., an ñ -> B that are implicit with the ordinary picture
of a venn diagram on n features. Thus, we regard [a1, ..., an] as an ordered
pair of type (Bn, (Bn->B)), and we abbreviate this last type designation as
(Bn+->B), or even more succinctly as [Bn].
Table 2 exhibits the scheme of notation we use to formalize the domain of
propositional calculus, corresponding to the logical content of truth tables
and venn diagrams. Although it overworks the square brackets a bit, we also
use the equivalent notations n or [n] to denote the data type of a finite set
on n elements.
Table 2. Fundamental Notations for Propositional Calculus
Symbol
|
Notation
|
Description
|
Type
|
A
|
{a1, ..., an}
|
Alphabet of logical features.
|
n º [n]
|
Ai
|
{(ai), ai}
|
Coordinate dimension i.
|
B
|
A
|
á Añ = á a1, ..., anñ
= {‹a1, ..., an›}
= A1´ ... ´An
= ÕiAi
|
Set of interpretations,
cells, points, or vectors
in the universe of discourse.
|
Bn
|
A*
|
(l : A->B)
|
Space of linear functions on A.
|
(Bn)* @ Bn
|
A^
|
(A->B)
|
Set of boolean functions on A.
|
Bn->B
|
A•
|
[A] = [a1, ..., an]
= (A, A^)
= (A+->B)
= (A, (A->B))
|
Universe of discourse
based on the features
{a1, ..., an}.
|
(Bn, (Bn->B))
º (Bn+->B)
º [Bn]
|
...
Tables of Propositional Forms
To the scientist longing for non-quantitative techniques, then,
mathematical logic brings hope. It provides explicit techniques
for manipulating the most basic ingredients of discourse.
-- W.V. Quine, Mathematical Logic, [Qui, 7-8]
To prepare for the next phase of discussion, Tables 6 and 7 recollect
and summarize all the propositional forms on one and two variables.
Here, the propositional forms are represented over bases of boolean
coordinates as complete sets of truth-valued functions. Adjacent to
their names and specifications, we list the simplest expressions in
our formal calculus which correspond to these functions. For the sake
of orientation, a couple of common notations are listed in the columns
parallel to the forms we use. As simple and as circumscribed as these
low-dimensional universes may seem now, a careful exploration of their
differential extensions will involve us in sufficient complexity to
demand our attention for a time.
Propositional forms on one variable correspond to boolean functions
F : B1 -> B. In Table 6 these functions are listed in a variant form
of truth table, one which transposes the axes of the usual arrangement.
Each function Fi is indexed by the string of values it takes on the points
of the universe X• = [A] @ B1. The binary index generated in this way can
be converted to a decimal equivalent, and these are used as conventional
names for the Fi, as shown in the initial column of the Table. In their
own right, the 21 points of the universe X• are coordinated as a space
of type B1, this in light of the universe X• being a functional domain
where the coordinate projection A takes on its values in B.
Propositional forms on two variables correspond to boolean functions F : B2->B.
In Table 7 each function Fi is indexed by the values it takes on the points of
the universe X• = [A, B] @ B2. Converting the binary index thus generated to
a decimal equivalent, we obtain the functional nicknames listed in the initial
column. The 22 points of the universe X• are coordinated as a space of type B2,
as indicated in the heading of the Table, where the coordinate projections
A and B run through the different combinations of their values in B.
Table 6. Propositional Forms on One Variable
•
|
|
1 0
|
F
|
F
|
F
|
F0
|
F00
|
0 0
|
()
|
False.
|
0
|
F1
|
F01
|
0 1
|
(A)
|
Not A.
|
~A
|
F2
|
F10
|
1 0
|
A
|
A.
|
A
|
F3
|
F11
|
1 1
|
(())
|
True.
|
1
|
Table 7. Propositional Forms on Two Variables
•
|
|
1 1 0 0
1 0 1 0
|
F
|
F
|
F
|
F0
|
F0000
|
0 0 0 0
|
()
|
False.
|
0
|
F1
|
F0001
|
0 0 0 1
|
(A)(B)
|
Neither A nor B.
|
~A & ~B
|
F2
|
F0010
|
0 0 1 0
|
(A) B
|
B and not A.
|
~A & B
|
F3
|
F0011
|
0 0 1 1
|
(A)
|
Not A.
|
~A
|
F4
|
F0100
|
0 1 0 0
|
A (B)
|
A and not B.
|
A & ~B
|
F5
|
F0101
|
0 1 0 1
|
(B)
|
Not B.
|
~B
|
F6
|
F0110
|
0 1 1 0
|
(A, B)
|
A not equal to B.
|
A + B
|
F7
|
F0111
|
0 1 1 1
|
(A B)
|
Not both A and B.
|
~A v ~B
|
F8
|
F1000
|
1 0 0 0
|
A B
|
A and B.
|
A & B
|
F9
|
F1001
|
1 0 0 1
|
((A, B))
|
A equal to B.
|
A = B
|
F10
|
F1010
|
1 0 1 0
|
B
|
B.
|
B
|
F11
|
F1011
|
1 0 1 1
|
(A (B))
|
Not A without B.
|
A Þ B
|
F12
|
F1100
|
1 1 0 0
|
A
|
A.
|
A
|
F13
|
F1101
|
1 1 0 1
|
((A) B)
|
Not B without A.
|
A Ü B
|
F14
|
F1110
|
1 1 1 0
|
((A)(B))
|
A or B.
|
A v B
|
F15
|
F1111
|
1 1 1 1
|
(())
|
True.
|
1
|
#End Citation==#====#====#====#====#====#====#====#====#====#
#%%%%%%%%%#%%%%%%%%%#%%%%%%%%%#%%%%%%%%%#%%%%%%%%%#%%%%%%%%%#