Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


fom
Posts:
1,968
Registered:
12/4/12


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


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 firstorder logic, Tarski and Monk associate the negation symbol with the settheoretic 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 selfdual if it coincides with its dual: thus, complementation is selfdual."
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 selfduality 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 wellformed 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 wellformed formulas.
The namespace of logical constants has been given as a 21point 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 20lines.
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:
OOOO \ \ 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 fouratom Boolean block are just
AND, NOR, NIF, NIMP
the fourcoatoms 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 threeatom 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 wellformed 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 wellformed formulas uses the NOR connective and the symbol of negation is an abbreviation according to
A <> NOR(A,A)


Date

Subject

Author

12/8/12


fom

12/11/12


fom


