Predicate Logic

From Wff to Proposition



Subjects to be Learned

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