========================================================================
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
========================================================================