Predicate Logic
From Wff to Proposition
Subjects to be Learned
- interpretation
- satisfiable wff
- invalid wff (unsatisfiable wff)
- valid wff
- equivalence of wffs
Contents
Interpretation
A wff is, in general, not a proposition.
For example, consider the wff x P(x), where
P(x) means that x is non-negative (greater than or equal to 0).
This wff is true
if the universe is the set {1, 3, 5}, the set {2, 4, 6}
or the set of natural numbers, for example, but it is not true if the universe is the set
{-1, 3, 5}, or the set of integers, for example.
Further more the wff x Q(x, y),
where Q(x, y) means x is greater than y,
for the universe {1, 3, 5} may be true or false depending on the value of y.
As one can see from these examples, the truth value of a wff is determined by the universe, and the
values assigned to the
free variables. The specification of the universe and an assignment of a value to
each free variable in a wff is called an interpretation
for the wff*.
For example, specifying the set {1, 3, 5} as the universe and assigning 0
to the variable y, for example, is an interpretation for the wff
x Q(x, y),
where Q(x, y) means x is greater than y.
x Q(x, y) with that interpretation reads,
for example, "Every number in the set {1, 3, 5} is greater than 0".
As can be seen from the above example, a wff becomes a proposition when it is given an interpretation.
There are, however, wffs which are always true or always false under any interpretation.
Those and related concepts are discussed below.
Satisfiable, Unsatisfiable and Valid Wffs
A wff is said to be satisfiable if there exists an interpretation
that makes it true, that is if there are a universe and an assignment of values to the free
variables that make the wff true.
For example, x N(x), where
N(x) means that x is non-negative, is satisfiable. For if the universe
is the set of natural numbers,
the assertion
x N(x) is true,
because all natural numbers are non-negative.
Similarly x N(x) is also satisfiable.
However, x [N(x)
N(x)] is not satisfiable because it can never be true.
A wff is called invalid or
unsatisfiable,
if there is no interpretation that makes it true.
A wff
is valid if it is true for every interpretation.
For example, the wff
x P(x)
x P(x)
is valid for any predicate name P ,
because
x P(x)
is the negation of x P(x).
However, the wff
x N(x) is satisfiable but not valid.
Equivalence
Two wffs W1 and W2 are
equivalent
if and only if W1 W2
is valid, that is if and only if
W1 W2
is true for all interpretations.
For example x P(x) and
x
P(x)
are equivalent for any predicate name P . So are
x [ P(x) Q(x) ]
and [ x P(x)
x Q(x) ] for any predicate names
P and Q .
*
Note that we are not dealing with predicate variables here. Thus
no interpretation of predicate variables is considered here.
Test Your Understanding of Equivalence etc.
Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit. There are two sets of questions.
Next -- English to Logic Translation
Back to Schedule
Back to Table of Contents