Well-formed Formulas of Predicate Logic

The rules for constructing well-formed formulas (WFFs) of predicate logic are as follows:

Any predicate letter followed by any constant is a WFF. For example: Pq
The result of prefixing any WFF with ‘~’ is a WFF. For example: ~Pq
The result of joining any two WFFs with ‘•’, ‘∨’, ‘⊃’, or ‘≡’ and enclosing the result in parentheses is a WFF. For example: (~Pq ⊃ Rs)
The result of prefixing any WFF with a quantifier, and using the corresponding variable instead of some (or all) constants, is a WFF. For example: (∀x)(~Px ⊃ Rx)

The fourth rule can be tricky, so let me explain it further. A quantifier may be attached to the left side of any WFF, just like the ‘~’. The resulting formula, in turn, may be used as part of a larger formula. (For instance, it may be joined to another WFF as indicated in Rule 3.) The formula to which the quantifier was first attached—i.e., the smallest complete formula to the right of the quantifier—is called the scope of the quantifier. For example, compare the following two formulas:

(∀x)(Px ⊃ Qx)

((∀x)Px ⊃ Qx)

In the first formula, the quantifier ‘(∀x)’ is attached to the conditional as a whole, so its scope includes the entire conditional, highlighted here in yellow:

(∀x)(Px ⊃ Qx)

However, in the second formula, the quantifier is attached to the antecedent of the conditional, so its scope includes only the antecedent:

((∀x)Px ⊃ Qx)

When a variable appears within the scope of a quantifier that uses the same lowercase letter, it is called a bound variable. Rule 4 implies that in a WFF of predicate logic, all variables must be bound. In other words, variables (lowercase letters ‘x’, ‘y’, and ‘z’) may be used instead of constants (letters ‘a’ through ‘w’) anywhere in a WFF, provided they are bound by a quantifier of the same variable. So, rule 4 can be summarized as follows:

Variables may only be used within the scope of a matching quantifier.

The first of the two formulas above is well-formed (it is a WFF), because both occurrences of the variable ‘x’ are bound by the quantifier ‘(∀x).’ But the second formula is not well-formed because it contains an unbound variable, highlighted here in red:

((∀x)Px ⊃ Qx)

To illustrate how rule 4 works, here are several examples of formulas that are well-formed, compared with similar formulas that are not well-formed because they break rule 4:

Pa - This is a WFF according to rule 1.
Px - This is not a WFF. The variable ‘x’ is used without a quantifier, so it is unbound.

(∀x)(Px ⊃ Qx) - This is a WFF. The variable ‘x’ is used within the scope of a matching quantifier.
(∀x)(Py ⊃ Qy) - This is not a WFF. The variable ‘y’ doesn’t match the quantifier, so it is unbound.

((∃y)Py ⊃ Qb) - This is a WFF. The variable ‘y’ is used within the scope of a matching quantifier.
((∃y)Py ⊃ Qy) - This is not a WFF. The second ‘y’ appears outside the scope of ‘(∃y)’, so it is unbound.

Now that rule 4 has been explained, let’s look at a few more examples of WFFs. The following examples show how complex formulas can be constructed from simpler ones in accordance with the four rules of syntax:

Qb	- a simple WFF (rule 1)
~Qb	- prefixing the above with ‘~’ (rule 2)
(∃x)~Qx	- prefixing the above with ‘(∃x)’ and using ‘x’ instead of the constant (rule 4)
((∃y)~Qy ∨ (∀x)Px)	- joining the above with another WFF using ‘∨’ (rule 3)

(Pa ⊃ ~Qb)	- joining two WFFs with ‘⊃’ and enclosing the result in parentheses (rule 3)
(∀x)(Px ⊃ ~Qx)	- prefixing the above with ‘(∀x)’ and using ‘x’ instead of both constants (rule 4)
(∀x)(Pa ⊃ ~Qx)	- similar to the previous example, but ‘x’ replaces only the second constant (rule 4)
(∃y)(∀x)(Py ⊃ ~Qx)	- prefixing the above with ‘(∃y)’ and using ‘y’ instead of the constant (rule 4)

((∃x)Px • Qb)	- joining ‘(∃x)Px’ and ‘Qb’ with ‘•’ and enclosing the result in parentheses (rule 3)
(∀y)((∃x)Px • Qy)	- prefixing the above with ‘(∀y)’ and using ‘y’ instead of the constant (rule 4)