From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Sun Mar 30 16:45:28 2008
Date:         Sun, 30 Mar 2008 16:45:11 -0400
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191:  Recursive Definition of WFF of FOPL
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191:  Recursive Definition of WFF of FOPL
------------------------------------------------------------------------

In Friday's class (28 March), I think that I started to give you a
recursive definition of a well-formed formulat (WFF) of FOPL and then
somehow got off track.  So, here it is:

Base case:

	Let P be an n-place predicate
	Let t1,...,t_n be terms (i.e., variables or constants).
	Then P(t1,...,t_n) is a(n atomic) WFF of FOPL.

Recursive case:

	Let a,b be WFFs of FOPL.  (Note:  I used "alpha" and "beta" in class,
					but I can't type them here)
	Let v be a variable.
	Then:

	1	-a
	2	(a v b)
	3	(a ^ b)
	4	(a -> b)
	5	(a <-> b)
	6	Ava
	7	Eva

	are (molecular) WFFs of FOPL.

Closure clause:  Nothing else is a WFF of FOPL.
========================================================================

Here are some examples.

P(t,s)			where t,s are constants;
			well-formed, according to the base case

Q(r)			where r is a constant;
			well-formed, according to the base case

P(x,y)			where x,y are variables;
			well-formed, according to the base case

Note that the first two of these are propositions (i.e., they can have a
truth value), but the third one is only a propositional function (it
cannot have a truth value, because it contains a free variable).

So:  not all WFFs are propositions!

-P(t,s)			well-formed by recursive case 1 & the base case
-Q(r)			well-formed by recursive case 1 & the base case

(P(t,s) v -Q(r))	well-formed by rec case 2, because each of the
			constituent WFFs is well-formed, the first one
			by the base case, and the second one by rec
			case 2 (& the base case)

((P(t,s) v -Q(r)) -> -P(t,s))

			well-formed by rec case 4, because each of the
			constituent WFFs is well-formed, the first one
			(i.e., the antecedent) by the previous example
			and the second one (i.e., the consequent) by
			the third example.

Ax((P(t,s) v -Q(r)) -> -P(t,s))

			well-formed by rec case 6, because the scope of
			the quantifier is well-formed by the previous
			example.

Note that the quantifier's variable, x, is "vacuous":  It does not
appear in the scope.  This is odd, but legitimate.  Here's a real
example:

	Ax[2+2=4]

This says:  For all things x in the domain, 2+2=4.  That's true of
anything in any domain!

One final example:

ExP(x), where x is a variable.  This is well-formed by rec case 7,
because P(x) is well-formed by the base case.

Question:  Let "+" be the symbol for exclusive disjunction.  Let A,B be
WFFs of FOPL.  Is (A + B) a WFF of FOPL?  

Answer:  Not according to the above definition.  But surely it "should
be" considered as a WFF of FOPL, right?  Here's how we can use it
without changing the definition of WFF:

We can define the symbol "+" as follows:  Let A, B be any 2 WFFs of
FOPL.  Then let (A + B) be an **abbreviation** for:

	((A v B) ^ -(A ^ B))

In other words, any time that we use (A + B), we would just be being
lazy, and should really write out the full definition, which **is** a
WFF of FOPL.