0.3 Discrete structures logic  (Page 15/23)

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:

1. True and False are wffs.

2. Each propositional constant (i.e. specific proposition), and each propositional variable (i.e. a variable representing propositions) are wffs.

3. Each atomic formula (i.e. a specific predicate with variables) is a wff.

4. If A, B, and C are wffs, then so are ¬A, (A ⋀B), (A ⋁ B), (A→B), and (A ↔B).

5. 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. )

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.

From wff to proposition

Interpretation

A wff is, in general, not a proposition. For example, consider the wff ∀x P(x). Assume that 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, specific predicates assigned to the predicate variables such as P and Q, and the values assigned to the free variables. The specification of the universe and predicates, and an assignment of a value to each free variable in a wff is called an interpretation for the wff.