========================================================================
Subject:  Miscellaneous Topics on Recursion
========================================================================

There are a few topics on recursion that I'm not going to have time to
cover in lecture, but I do want to make sure that you know about them,
so I'm going to discuss them here.
========================================================================

1.  Recursive Definitions of Data Structures
------------------------------------------------------------------------
We've defined functions recursively (e.g., Fibonacci, factorial,
addition, multiplication) and we defined a predicate recursively (being
divisible by 3).

It's also possible to define sets and other data structures recursively.
One such data structure that's important in computer science
applications, including artificial intelligence, are "strings".

Please read "A Recursive Definition of Strings", available from the
Directory of Documents webpage on Recursion and Induction, or directly
at:	http://www.cse.buffalo.edu/~rapaport/191/F09/strings.html


2.  Recursive Definition of "Well-Formed Formula" of FOL
------------------------------------------------------------------------
We can also give a recursive definition of the language of FOL.
This is a way of expressing the grammar (i.e., the syntax) of the
language.  We begin by recursively defining the notion of a "well-formed
[i.e., grammatical] formula", and then define "proposition" in terms of
that:

Base case:

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

Recursive case:

        Let p,q be WFFs of FOL.  
        Let v be a variable.
        Then:

        1       -p
        2       (p v q)
        3       (p ^ q)
        4       (p -> q)
        5       (p <-> q)
        6       Avp
        7       Evp

        are (molecular) WFFs of FOL.

Closure clause:  Nothing else is a WFF of FOL.

Then we can define:

	p is a proposition =def p is a WFF with no free variables.

Here are some examples.

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

Q(c)                    where c 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(a,b)                 well-formed by recursive case 1 & the base case

-Q(c)                   well-formed by recursive case 1 & the base case

(P(a,b) v -Q(c))        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(a,b) v -Q(c)) -> -P(a,b))

                        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(a,b) v -Q(c)) -> -P(a,b))

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

Note first that this way of doing things does not require brackets 
around the scope of the quantifier.

Note also 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 FOL.  Is (A + B) a WFF of FOL?  

Answer:  
Not according to the above definition.  But surely it "should be"
considered as a WFF of FOL, 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
FOL.  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 FOL.


3.  Structural Induction
------------------------------------------------------------------------
"Structural induction" is a proof strategy for showing that some
predicate P is true of a data structure that is defined recursively.

Just like mathematical induction, it has a base case and an inductive
case.  Let X be some data structure (e.g., a set, or a string, or a
wff).  Let P be some predicate.

base case:  	Show P(X) for the base case of X's recursive definition
recursive case: Show that if P(X) holds for each of the basic
				building-block objects X used to
				construct new objects X' in the
				recursive definition

			  then P(X') holds for the newly constructed
				objects X'

Here's the general pattern for the data structure of "wff of
propositional logic":  

to show that for any wff p of propositional logic, P(p),
we need to do 2 things:

	base case:  Show P(p) for atomic propositions p
	inductive case:  
		Show that for any propositional wffs p,q:
		[P(p) ^ P(q)
		->
		P(-p) ^ P(p ^ q) ^ P(p v q) ^ P(p -> q) ^ P(p <->q)]

Here's an example:

	(Notation:  x e S for:  x is a member of set S)

Thm:  (for all p e WFFs-of-propositional-logic)
	[# of left parentheses of p = # of right parentheses of p]

e.g., ((p v q) ^ (r -> s)) has 3 left parentheses and 3 right parentheses

(Notation:  #LP(p) for:  The number of left parentheses of p
	    #RP(p) for:  The number of right parentheses of p )

proof by structural induction:

base case: Let p be an atomic proposition.
	   Show #LP(p) = #RP(p):

		trivial:  #LP(p) = 0 = #RP(p)

ind. case: Let p,q be wffs of propositional logic.
	Suppose #LP(p) = #RP(p)
	and     #LP(q) = #RP(q)	--this is the inductive hypothesis

	Show:

	case 1: #LP(-p) = #RP(-p):
		proof:  #LP(-p) = #LP(p), because "-" doesn't add
					  any parentheses
				= #RP(p), by ind hyp
				= #RP(-p), because "-" doesn't add
					   any parentheses.

  	cases 2-5:  We need to show #LP(p ^ q) = #RP(p ^ q)
				and #LP(p v q) = #RP(p v q)
				and #LP(p -> q) = #RP(p -> q)
				and #LP(p <-> q) = #RP(p <-> q)

	But all 4 of these cases will have very similar proofs;
	So, "without loss of generality", let * be any of these 4
	binary connectives. (i.e., we don't have to prove 4 separate
	cases; we'll let "*" be a kind of variable ranging over
	binary connectives, prove the theorem for "*", and then
	we're done)

	Show #LP(p * q) = #RP(p * q):
	#LP(p * q) = 1 + #LP(p) + #LP(q), because there's that initial
					  left parenthesis just before
					  "p"
		   = 1 + #RP(p) + #RP(q), by the ind hyp
		   = #RP(p) + #RP(q) + 1, by arithmetic
		   = #RP(p * q), because there's that final right
				 parenthesis just after "q".  QED
========================================================================