Well-Formed Formula of Predicate Logic

 

To give a precise description of a first-order predicate calculus, we need an alphabet of symbols. For this discussion we'll use several kinds of letters and symbols, described as follows:

Individual variables: x, y, z

Individual constants: a, b, ñ

Function constants: f, g, h

Predicate constants: p, q, r

Connective symbols: Ø, ®, Ù, Ú

Quantifier symbols: $, "

Punctuation symbols: (, )

From time to time we will use other letters, or strings of letters, to denote variables or constants. We'll also allow letters to be subscripted. The number of arguments for a predicate or function will normally be clear from the context. A predicate with no arguments is considered to be a proposition.

A term is either a variable, a constant, or a function applied to arguments that are terms. For example, x, a, and f(x, g(b)) are terms. An atomic formula (or simply atom) is a predicate applied to arguments that are terms. For example, p(x, a) and q(y, f(c)) are atoms.

We can define the wffs – the well-formed formulas – of the first-order predicate calculus inductively as follows:

Basis: Any atom is a wff.

Induction: If W and V are wffs and x is a variable, then the following expressions are also wffs:

(W), Ø W, W Ú V, W  Ù V, W ® V, $ x W, and " x W.

To write formulas without too many parentheses and still maintain a unique meaning, we'll agree that the quantifiers have the same precedence as the negation symbol. We'll continue to use the same hierarchy of precedence for the operators ->, л, v, and —». Therefore the hierarchy of precedence now looks like the following:

Ø, $ x, " x (highest, do first)

Ù

Ú

® (lowest, do last)

If any of the quantifiers or the negation symbol appear next to each other, then the rightmost symbol is grouped with the smallest wff to its right. Here are a few wffs in both unparenthesized form and parenthesized form:

 

Unparenthesized Form

" x Ø $ y " z p(x, y, z)

$ x p(x) Ú q(x)

"x p(x) ® q(x)

$ x Ø p(x,ó) ® q(x) Ù r(y)

$ x p(x) ® " x q(x) Ú p(x) Ù r(x)

Parenthesized Form

" x (Ø ($ y (" z p(x, y, z))))

($ x p(x)) Ú q(x)

(" x p(x)) ® q(x)

($ x (Ø p(x,ó))) ® (q(x) Ù r(y))

($ x p(x)) ®((" x q(x)) Ú (p(x) Ù r(x)))

 

Because wffs are defined inductively, there are easy techniques to check whether or not an arbitrary expression is a wff. For example, let's show that the following expression is a wff:

$ x p(x,y) ® q(x).

There are two approaches: The bottom-up approach starts with basis case of atoms; the top-down approach starts with the overall structure of the wff.

Bottom-Up

Start with p(x, y) and q(x). These expressions are atoms. So it follows that they are wffs by the basis case. Therefore $ x p(x,y) is a wff by the induction case. Finally, $ x p(x,y) ® q(x) is a wff by the induction case.

Top-Down

Start by noticing that the expression has the form W ® V where W = $ x p(x,y) and V = q(x). So the expression is a wff if we can show that W and V are wffs. V is a wff by the basis case. W has the form $ x U, where U = p(x, y). Since U is a wff by the basis case, it follows that W is a wff by the induction case. Therefore $ x p(x,y) ® q(x) is a wff.

Now let's discuss the relationship between the quantifiers and the variables that appear in a wff. When a quantifier occurs in a wff, it influences some occurrences of the quantified variable. The extent of this influence is called the scope of the quantifier, which we define as follows:

In the wff $ x W, W is the scope of the quantifier $ x

In the wff "x W, W is the scope of the quantifier "x.

For example, the scope $ x in the wff

$ x p(x, y)

is p(õ, y) because the parenthesized version of the wff is ($ x p(x,y)) ® q(x). On the other hand, the scope of $ x  in the wff  p(x,y) ® q(x) is p(x,y) ® q(x).

An occurrence of the variable x in a wff is said to be bound if it lies within the scope of either $ x or "x or if it's the quantifier variable x itself.

Otherwise, an occurrence of õ is said to be free in the wff. For example, consider the following wff:

$ x p(x,y) ® q(x).

The first two occurrences of õ are bound because the scope of $ õ is p(x, y). The only occurrence of ó is free, and the third occurrence of õ is free.

So every occurrence of a variable in a wff can be classified as either bound or free, and this classification is determined by the scope of the quantifiers in the wff. Now we're in position to discuss the meaning of wffs.

Semantics

Up to this point a wff is just a string of symbols with no meaning attached. For a wff to have a meaning, we must give an interpretation to its symbols so that the wff can be read as a statement that is true or false. For example, suppose we let p(x) mean”x is an even integer" and we let x be the number 236. With this interpretation, p(x) becomes the statement “236 is an even integer," which is true.

As another example, let's give an interpretation to the wff

" x $y s(x,y).

We'll let s(x, y) mean that the successor of x is y, where the variables x and y take values from the set of natural numbers N. With this interpretation the wff becomes the statement "For every natural number x there exists a natural number y such that the successor of x is y," which is true.

Before we proceed any further, we need to make a precise definition of an interpretation. Here's the definition:

Interpretations

An interpretation for a wff consists of a nonempty set D, called the domain of the interpretation, together with an assignment that associates the symbols of the wff to values in D as follows:

Each predicate letter must be assigned some relation over D. A predicate with no arguments is a proposition and must be assigned a truth value.

Each function letter must be assigned a function over D.

Each free variable must be assigned a value in D. All free occurrences of a variable x are assigned the same value in D.

Each constant must be assigned a value in D. All occurrences of the same constant are assigned the same value in D.

So there can be many interpretations for a wff. To describe the meaning of an interpreted wff, we need some notation. Suppose W is a wff, x is a free variable in W, and t is a term. Then the wff obtained from W by replacing all free occurrences of x by t is denoted by the expression

W(x/t).

The expression x/t is called a binding of x to t and can be read as "x gets t" or “x is bound to t" or “x has value t" or “x is replaced by t". We can read W(x/t) as "W with x replaced by t" or "W with x bound to t." For example, suppose we have the following wff:

W = p(x) Ú $ x q(x, y).

We can apply the binding x/a to W to obtain the wff 

W(x/a) = p(a) Ú $ x q(x, y).

We can apply the binding y/b to W(x/a) to obtain the wff

W(x/a) (y/b) = p(a) Ú $ x q(x, b).

We often want to emphasize the fact that a wff W contains a free variable x. In this case we'll use the notation

W(x).

 When this is the case, we write W(t) to denote the wff W(x/t). For example, if
W = p(x)
Ú $ x q(x, y), and we want to emphasize the fact the x is free in W, we'll write

W(x) = p(x) Ú $ x q(x, y).

Then we can apply the binding x/a to W by writing

W(a) = p(a) Ú $x q(x,y).

Now we have all the ingredients to define the meaning, or semantics, of wffs in first-order predicate calculus.

The Meaning of a Wff

Suppose we have an interpretation with domain D for a wff.

1.     If the wff has no quantifiers, then its meaning is the truth value of the statement obtained from the wff by applying the interpretation.

2.     If the wff contains quantifiers, then each quantified wff is evaluated as follows:

$ x W is true if W(x/d) is true for some d Î D. Otherwise, $ x W is false.

" x W is true if W(x/d) is true for every d Î D. Otherwise, " x W is false.

The meaning of a wff containing quantifiers can be computed by recursively applying this definition. For example, consider a wff of the form "x $y W, where W does not contain any further quantifiers. The meaning of "x $y W is true if the meaning of ($y W )(x/d) is true for every d Î D. We can write

($y W )(x/d) = $y W (x/d).

So for each d Î D  we must find the meaning of$y W (x/d). The meaning of $y W (x/d) is true if there is some element e Î D such that W(x/d)(y/e) is true.

Let's look at a few examples that use actual interpretations.

EXAMPLE. The meaning of the wff "x $y s(x, y) is true with respect to the interpretation D = N, and s(x, y) means "the successor of x is y." The interpreted wff can be restated as "Every natural number has a successor."

EXAMPLE. Let's consider the "isFatherOf” predicate, where isFatherOf(x, y) means "x is the father of y." The domain of our interpretation is the set of all people now living or who have lived. Assume also that Jim is the father of Andy. The following wffs are given along with their interpreted values:

isFatherOf(Jim, Andy) = true,

$x isFatherOf(x, Andy) = true ,

"x isFatherOf(x, Andy) = false,

"x $y isFatherOf(x, y) = false,

"y $x isFatherOf(x, y) = true,

$x"y isFatherOf(x, y) = false,

$y"x isFatherOf(x, y) = false,

$x $y isFatherOf(x, y) = true,

$y $x isFatherOf(x, y) = true,

"x "y isFatherOf(x, y) = false,

"y "x isFatherOf(x, y) = false.