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.