Predicate Logic
Well-Formed Formula for First Order Predicate Logic
--- Syntax Rules
Subjects to be Learned
- wff (well formed formula)
- atomic formula
- syntax of wff
Contents
Not all strings can represent propositions of the predicate logic.
Those which produce a proposition
when their symbols are interpreted must follow the rules given below, and they are
called wffs(well-formed formulas) of the first order predicate logic.
Rules for constructing Wffs
A predicate name followed by a list of variables such as P(x, y), where P is
a predicate name, and x and y are variables,
is called an atomic formula.
Wffs are constructed using the following rules:
- True and False are wffs.
- Each propositional constant (i.e. specific proposition), and each propositional
variable (i.e. a variable representing propositions) are wffs.
- Each atomic formula (i.e. a specific predicate with variables) is a wff.
- If A, B, and C are wffs, then so are A,
(A B), (A B),
(A B), and (A B).
- If x is a variable (representing objects of the universe of discourse), and A is a wff,
then so are x A and
x A .
(Note : More generally, arguments of predicates are something called
a term. Also variables representing predicate names
(called predicate variables) with a list of variables can form atomic
formulas. But we do not get into that here. Those who are interested
click here.)
For example, "The capital of Virginia is Richmond." is a specific proposition.
Hence it is a wff by Rule 2.
Let B
be a predicate name representing "being blue"
and let
x be a variable.
Then B(x) is an atomic formula meaning "x is blue". Thus it is a
wff by Rule 3. above. By applying Rule 5. to B(x),
xB(x) is a wff and so is
xB(x).
Then by applying Rule 4. to them
x B(x)
x B(x)
is seen to be a wff.
Similarly if R is a predicate name representing
"being round". Then
R(x) is an atomic formula. Hence it is a wff.
By applying Rule 4 to B(x) and R(x),
a wff B(x) R(x) is obtained.
In this manner, larger and more complex wffs can be constructed following the rules given above.
Note, however, that strings that can not be constructed by using those rules are not wffs.
For example, xB(x)R(x),
and B( x ) are NOT wffs,
NOR are B( R(x) ), and
B( x R(x) ) .
One way to check whether or not an expression is a wff is to try to state it in English.
If you can translate it into a correct English sentence, then it is a wff.
More examples: To express the fact that Tom is taller than John, we can use
the atomic formula taller(Tom, John), which is a wff.
This wff can also be part of some compound statement
such as
taller(Tom, John)
taller(John, Tom),
which is also a wff.
If x is a variable representing people in the world, then taller(x,Tom),
x
taller(x,Tom),
x taller(x,Tom),
x y taller(x,y)
are all wffs among others.
However, taller( x,John) and taller(Tom
Mary, Jim),
for example, are NOT wffs.
Test Your Understanding of Wff Construction
Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit. There are two sets of questions.
Below \A represents the universal and \E the existential quantifiers, respectively.
Next -- From Wff to Proposition
Back to Schedule
Back to Table of Contents