Math Forum Discussions

fom

Posts: 1,037
Registered: 12/4/12

fom - 09 - a canonical complete connective
Posted: Dec 8, 2012 6:16 AM

Plain Text

In "Cylindrical Algebras" by
Tarski and Monk, there is a chapter
on duality. Because the topic
of the material involves the
coincidence of certain geometric
notions with first-order logic,
Tarski and Monk associate the
negation symbol with the set-theoretic
notion of complementation.

The free cylindrical algebra of
formulas has a signature:

<Phi, \/, /\, -, F, T, E_i, v_i=v_j>, i,j<omega

the signature for the dual algebra
is

<Phi, /\, \/, -, T, F, A_i, -(v_i=v_j)>, i,j<omega

with respect to which Tarski and
Monk make the observation:

"...we easily see that the
duals of the dual notions
are the original notions,
e.g.,

dual(dual(E_k))=E_k

A notion is called self-dual
if it coincides with its dual:
thus, complementation is
self-dual."

This assertion is correct when
when working in a mathematical
context such as a real Euclidean
space. But, in so far as it
might be applied to the negation
symbol in general -- that is, as
the transformation of the signatures
might imply for the cylindrical
algebras of formulas-- the apparent
self-duality masks the fact that
the complete connectives NOR and
NAND can be used to eliminate
negation. Just as the OR and AND
connectives in the signature
above are dual to one another,
fixing a canonical form for the
elimination of negation exchanges
dual connectives.

Indeed, it exchanges canonical
representations for all the
well-formed formulas. That is,
there is a

Phi_NOR

of formulas that exchanges with
the dual formulas

Phi_NAND

In his work on algebraic logic,
Paul Halmos observed that logicians
focus on provability whereas
mathematicians seem to focus on
falsifiability. In a manner that
can be made precise, this reflects
the duality of NAND and NOR.

The construction here fixes a
preference for the use of a complete
connective in the recursive generation
of well-formed formulas.

The namespace of logical constants
has been given as a 21-point
projective geometry. The naming
scheme for the geometry uses the same
names for lines as for points. This
reflects the relationship of dual
structures in projective geometry.

The names isolated to form the nor
algebra demarcate an affine plane within
the projective plane. That affine
plane has 20-lines.

We use the line names to label an
ortholattice given by the orthogonality
diagram:

OTHER
*
/ |
/ |
/ |
/ |
/ | NOR NIF
SOME *------*-------------*
|\ /|
| \ / |
| \ / |
| X |
| / \ |
| / \ |
|/ \|
*-------------*
NIMP AND

The Greechie diagram for this lattice
shows that it is an amalgam of two Boolean
blocks, one on four atoms and one on
three atoms:

O-----O-----O-----O
\
\
O
\
\
O

The top of this lattice is TRU
The bottom of this lattice is THIS

From the orthogonality diagram, it
can be seen that the atoms of the
four-atom Boolean block are just

AND, NOR, NIF, NIMP

the four-coatoms are

NAND, OR, IF, IMP

and the connectivity in the lattice
is precisely what one is accustomed
to seeing for the free Boolean algebra
on two generators. The names
corresponding to the generators
are

FIX, LET

and their orthocomplements are

FLIP, DENY

For the three-atom Boolean block,
the three atoms are just

NOR, SOME, OTHER

while the three coatoms are

OR, ALL, NO

The amalgam is an atomic amalgam
so that the shared vertices in
the lattice are

TRU, OR, NOR, THIS

With regard to the earlier remarks,
had the namespace been constructed
for emphasizing falsifiability,
the loci labelled with

TRU, NTRU

would have their names exchanged,
the top of the ortholattice would
have been THIS, and the bottom
of the ortholattice would have
been NTRU.

Moreover, the orthogonality diagram
would have had the form

NO
*
/ |
/ |
/ |
/ |
/ | AND NIF
ALL *------*-------------*
|\ /|
| \ / |
| \ / |
| X |
| / \ |
| / \ |
|/ \|
*-------------*
NIMP NOR

For this alternative construction, the
complete connective used for the
recursive generation of well-formed formulas
would be NAND and the symbol of negation
would have been an abbreviation according
to

-A <-> NAND(A,A)

For the construction chosen, the recursive
generation of well-formed formulas uses
the NOR connective and the symbol of
negation is an abbreviation according
to

-A <-> NOR(A,A)