First-Order Predicate Calculus

 

The propositional calculus provides adequate tools for reasoning about propositional wffs, which are combinations of propositions. But a proposition is a sentence taken as a whole. With this restrictive definition, propositional calculus doesn't provide the tools to do everyday reasoning. For example, in the following argument it is impossible to find a formal way to test the correctness of the inference without further analysis of each sentence:

All computer science majors own a personal computer.

Socrates does not own a personal computer.

Therefore Socrates is not a computer science major.

To discuss such an argument, we need to break up the sentences into parts. The words in the set (All, own, not) are important to understand the argument. Somehow we need to symbolize a sentence so that the information needed for reasoning is characterized in some way. Therefore we will study the inner structure of sentences.

The statement "x owns a personal computer" is not a proposition because its truth value depends on x. If we give x a value, like x = Socrates, then the statement becomes a proposition because it has the value true or false. From the grammar point of view, the property "owns a personal computer" is a predicate, where a predicate is the part of a sentence that gives a property of the subject. A predicate usually contains a verb, like "owns" in our example. The word predicate comes from the Latin word praedicare, which means to proclaim.

From the logic point of view, a predicate is a relation, which of course we can also think of as a property. For example, suppose we let p(x) mean “x owns a personal computer." Then p is a predicate that describes the relation (i.e., property) of owning a personal computer. Sometimes it's convenient to call p(x) a predicate, although p is the actual predicate. If we replace the variable x by some definite value such as Socrates, then we obtain the proposition p(Socrates). For another example, suppose that for any two natural numbers x and y we let q(x, y) mean "x < y" Then q is the predicate that we all know of as the "less than" relation. For example, the proposition q(1, 5) is true, and the proposition q(8, 3) is false.

Let p(x) mean "x is an odd integer." Then the proposition p(9) is true, and the proposition p(20) is false. Similarly, the following proposition is true:

.

We can describe this proposition by saying, "There exists an element x in the set {2, 3, 4, 5} such that p(x) is true." By letting D = {2, 3, 4, 5} the statement can be shortened to "There exists x Î D such that p(x) is true." If we don't care about the truth of the statement, then we can still describe the preceding disjunction by saying, "There exists x Î D such that p(x)" Still more formally, we can write the expression

$ x Î D: p(x).

 Now if we want to consider the truth of the expression for a different set of numbers, say S, then we would write

$ x Î S: p(x).

This expression would be true if S contained an odd integer. If we want to consider the statement without regard to any particular set of numbers, then we write

$ x p(x).

 This expression is not a proposition because we don't have a specific set of elements over which x can vary. Thus $ x p(x) cannot be given a truth value. If we don't know what p stands for, we can still say, "There exists an x such that p(x)" The symbol $ x is called an existential quantifier.

Now let's look at conjunctions rather than disjunctions. Suppose we have the following proposition:

.

This conjunction can be represented by the expression " x Î D: p(x), where D = {1, 3, 5, 7}. We say, "Every x in D is an odd integer." If we want to consider the statement without regard to any particular set of numbers, then we write

" x p(x).

The expression " x p(x) is read, "For every x p(x)". The symbol " x is called an universal quantifier. Let's see how the quantifiers can be used together to represent certain statements. If p(x, y) is a predicate and we let the variables x and y vary over the set D = {0, 1}, then the proposition

can be represented by the following expression:

To see this, notice that each of the two disjunctions in the proposition can be expressed in the following form, where x Î D:

Now we use the universal quantifier "x to represent the conjunction of the two disjunctions to obtain the desired expression, as follows:

                                                         .

Now let's go the other way. We'll start with an expression containing different quantifiers and try to write it as a proposition. For example, if we use the same set of values D = {0, 1}, the expression

denotes the proposition

.

It's easier to see why this is the case. All we need to do is evaluate the expression as follows:

                                                       .

Of course, not every expression containing quantifiers results in a proposition. For example, if  D = {0, 1}, then the expression  can be written as follows:

.

To obtain a proposition, each variable of the expression must be quantified or assigned some value in D. We'll discuss this shortly, when we talk about semantics.

Now let's look at two examples, which will introduce us to the important process of formalizing English sentences with quantifiers.

EXAMPLE. We'll formalize the three sentences about Socrates that we listed at the beginning of the section. Let P be the set of all people, let cs(x) mean that x is a computer science major, and let pc(x) mean that x owns a personal computer. Then the sentence "All computer science majors own a personal computer" can be formalized as follows:

.

The sentence "Socrates does not own a personal computer" becomes

Ø pc(Socrates).

The sentence "Socrates is not a computer science major" becomes

Ø cs(Socrates).

EXAMPLE (Natural Numbers). Suppose we consider the following two elementary facts about the natural numbers N:

1. Every natural number has a successor.

2. There is no natural number whose successor is 0.

Let's formalize these sentences. We'll begin by writing down a semiformal version of the first sentence:

For each x Î N there exists y Î N such that the successor of x is y.

If we let s(x, y) mean that the successor of x is y, then the formal version of the sentence can then be written as follows:

.

Now let's look at the second sentence. It can be written in a semiformal version as follows:

There does not exist x Î N such that the successor of x is 0.

The formal version of this sentence is Ø $ x Î N : s(x, 0).

These notions of quantification belong to a logic called first-order predicate calculus. The words "first-order" refer to the fact that quantifiers can quantify only variables that occur in predicates. To discuss first-order predicate calculus, we need to give a precise description of its well-formed formulas and their meanings.