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

------------------------------------------------------------------------
Subject: 191: FUNCTIONAL COMPLETENESS
------------------------------------------------------------------------

Here is another example of "functional completeness", the property that
some combinations of connectives has that allows you to represent any
proposition using only those connectives and no others.  

To prove that a set of connectives is functionally complete, you need to 
show that all other connectives can be defined in terms of the given
set.

Note:  Below, I use "equiv" instead of the triple-bar for logical
equivalence.
------------------------------------------------------------------------

To show -,v are functionally complete:

* show that any proposition of the form (p ^ q) 
  can ie written as a logically equivalent proposition using only -,v:

	(p ^ q) equiv --(p ^ q), by Double Negation
	        equiv -(-p v -q), by DeMorgan			(*)

	Note:  to prove the equivalences, can use truth tables.

	i.e., we don't need the ^ connective;
		can make do with only -,v

* show that any proposition of the form (p -> q)
  can be written as a logically equiv proposition using only -,v:

	(p -> q) equiv (-p v q)

* show that any proposition of the form (p <-> q)
  can be written as a logically equiv proposition using only -,v:

	(p <-> q) equiv ((p -> q) ^ (q -> p))			(+)
	          equiv ((-p v q) ^ (-q v p))
	          equiv -(-(-p v q) v -(-q v p)), by (*) above	

	Note: to prove this, only need to construct t-table
	for the equivalence in (+), because we have already
	proved the other equivalences, above.

* show that any proposition of the form (p + q)
  can be written as a logically equiv proposition using only -,v:

	(p + q) equiv ((p v q) ^ -(p ^ q))
	        equiv ((p v q) ^ (-p v -q)), by DeM
	        equiv -(-(p v q) v -(-p v -q)), by DeM