From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Mon Feb  4 10:10:24 2008
Date:         Mon, 4 Feb 2008 10:09:48 -0500
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191: NAND
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191: NAND
------------------------------------------------------------------------

Your HW introduced the NOR, or "dagger", connective.  Here's its "dual":

Sheffer's "stroke" connective, or NAND:
========================================================================

Def:  (p | q) =def -(p ^ q)

Truth table:

	p	q	(p^q)	-(p^q)	(p|q)

	T	T	  T	F	  F
	T	F	  F	T	  T
	F	T	  F	T	  T
	F	F	  F	T	  T

Thm:  | is functionally complete (!)

pf:  First, how to represent -p:

	-p must be F when p is T
	A|B is F only when both A,B are T

	So:  represent -p by (p|p)

	t-table:  p	p	(p|p)

  		  T	T	  F  (see first line of table above)
		  F	F	  T  (see 4th line of table above)

     Next, how to represent (p^q):

	(p^q) equiv --(p^q), by DN
	      equiv -(p|q), by def of |
	      equiv ((p|q) | (p|q)), by previous representation of "-"

Finally, because in HW #2 it was proved that -,^ are functionally
complete, it follows that | is, too.  (I.e., all other connectives can
be represented in terms of -,^ and thence in terms of |.)