------------------------------------------------------------------------ Subject: Recursive Definition of WFF of FOPL ------------------------------------------------------------------------ In Friday's class (3 April), I gave you a recursive definition of a well-formed formula (WFF) of FOPL. In this document, I want to elaborate on it a bit. As a reminder, here's the definition (actually, it's a slightly modified version of what I gave you in lecture): 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 FOPL. Recursive case: Let p,q be WFFs of FOPL. 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 FOPL. Closure clause: Nothing else is a WFF of FOPL. ======================================================================== 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! (This is one of the modifications from what I said in lecture; another is below.) -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 in the recursive definition, as I had in lecture. 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 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.