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